Попытка лучше понять агломерационную иерархическую кластеризацию, сравнивая результаты со scipy;почему разные выходы? - PullRequest
Новая
       48

Попытка лучше понять агломерационную иерархическую кластеризацию, сравнивая результаты со scipy;почему разные выходы?

1 голос
/ 12 мая 2019

Я пытаюсь узнать больше об агломерационной кластеризации из ресурсов в сети, придумав алгоритм, а не заимствуя рутинные процедуры;для моего примера я использую критерий с одной связью, который итеративно объединяет две самые близкие точки.

Используя мой алгоритм, я получил необходимые данные для формирования дендрограммы.Рисование одного с использованием matplotlib кажется слишком сложным, поэтому я подумал, что заимствую подпрограмму scipy dendrogram просто для черчения.Чтобы сделать это, я должен ввести свой результат таким образом, чтобы подпрограмма scipy была понятна.Ниже приведено сравнение моего алгоритма и алгоритма Сципи.Я не понимаю, как их вывод получается.Я не думаю, что сделал ошибку, но, пожалуйста, исправьте меня, если я ошибаюсь.

## GET EXAMPLE DATA
x = np.array([0, 5, 25, 125, 625])
y = np.array([0, 4, 16, 64, 256])
z = np.array([1, 1, 1, 5, 1000])
# data = np.array([x, y])
data = np.array([x, y, z])

def get_all_possible_differences_per_dim(data, dim):
    """ """
    ## ADD DIMENSION AND BROADCAST SUBTRACTION
    x = np.reshape(data[dim], (len(data[dim]), 1))
    return x - x.transpose()

def get_euclidean_distance(points):
    """ """
    ## STANDARD DISTANCE METRIX
    return np.sqrt(np.sum(np.square(points), axis=0))

def single_link(data):
    """ """
    ## GET DISTANCE MATRIX
    ndim = data.shape[0]
    all_distances = np.array([get_all_possible_differences_per_dim(data, dim) for dim in range(ndim)])
    distance_matrix = get_euclidean_distance(all_distances)
    ## PAD DISTANCE MATRIX AT/BELOW DIAGONAL WITH LARGE DIFFERENCES
    ## GET ARGSORTED INDICES OF CLOSEST DATA POINTS USING NUMBER OF ELEMENTS CONTAINED IN ABOVE-DIAGONAL DISTANCES
    ## BELOW-DIAGONAL ENTRIES[i, j] = (-1) * ABOVE-DIAGONAL ENTRIES[j, i]; AVOID OVER-COUNTING
    for row in range(len(distance_matrix)):
        for col in range(len(distance_matrix[row])):
            if row >= col:
                distance_matrix[row, col] = np.inf
    res = {}
    ## FLATTEN COPY OF DISTANCE MATRIX TO ONE DIMENSION
    arr = np.reshape(distance_matrix, -1)
    n = 2*distance_matrix.shape[0]
    ## USE ARGSORTED INDEX IN CONJUNCTION WITH NUMBER OF ROWS AND COLUMNS
    ## LOCATE i-th DATAPOINT (via ROW) WITH THE j-th DATA POINT (Via COLUMN)
    rows, cols = np.divmod(np.argsort(arr)[:n], distance_matrix.shape[0])
    ## GET INDICES
    indices = np.array([rows, cols]).T
    res['indices'] = indices
    ## GET DISTANCES AT INDICES
    res['distances'] = distance_matrix[indices[:, 0], indices[:, 1]]
    res['distance matrix'] = distance_matrix
    return res

Чтобы просмотреть результаты, полученные из алгоритма выше, 

my_result = single_link(data)
for key, value in my_result.items():
    print("\n .. {} ({}):\n{}\n".format(key, value.shape, value))

производит вывод: 

 .. distances ((10,)):
[   6.40312424   23.32380758   29.68164416  110.9954954   134.22369388
  140.48843369 1129.99513273 1189.79031766 1202.45789947 1205.88639598]


 .. indices ((10, 2)):
[[0 1]
 [1 2]
 [0 2]
 [2 3]
 [1 3]
 [0 3]
 [3 4]
 [2 4]
 [1 4]
 [0 4]]


 .. distance matrix ((5, 5)):
[[          inf    6.40312424   29.68164416  140.48843369 1205.88639598]
 [          inf           inf   23.32380758  134.22369388 1202.45789947]
 [          inf           inf           inf  110.9954954  1189.79031766]
 [          inf           inf           inf           inf 1129.99513273]
 [          inf           inf           inf           inf           inf]]

Исходя из вышесказанного, мы идентифицируем первую паруindices как [0, 1], что соответствует 0-й строке и 1-му столбцу матрицы расстояний.I-я пара индексов соответствует i-й кратчайшей дистанции.

Чтобы посмотреть результат из алгоритма scipy, запустите:

fig = plt.figure()
dn = dendrogram(scipy_result)
plt.show()
plt.close(fig)

dendrogram figure

Я вижу, что массив scipy и мой массив my_result['distances'] имеют одинаковую форму и, вероятно, соответствуют друг другу.Понятно, что они уменьшили размерность.Но так как я занимаюсь сортировкой, я должен собирать одни и те же результаты в другой форме.Может кто-нибудь помочь мне понять, что я делаю не так? 

  [1]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.cluster.hierarchy.linkage.html#scipy.cluster.hierarchy.linkage
...