Рассчитать порядок листьев дендрограммы

У меня есть пять точек, и мне нужно создать дендрограмму из них. Функция "дендрограмма" может быть использована для определения порядка расположения этих точек, как показано ниже. Тем не менее, я не хочу использовать дендрограмму, так как она медленная и приводит к ошибке для большого количества точек (я задал этот вопрос здесь, в альтернативном способе Python для поиска дендрограммы). Может кто-нибудь подскажет мне, как преобразовать вывод 'linkage' (Z) в значение "dendrogram(Z)['ivl']".

>>> from hcluster import pdist, linkage, dendrogram
>>> import numpy
>>> from numpy.random import rand
>>> x = rand(5,3)
>>> Y = pdist(x)
>>> Z = linkage(Y)
>>> Z
array([[ 1.        ,  3.        ,  0.11443378,  2.        ],
       [ 0.        ,  4.        ,  0.47941843,  2.        ],
       [ 5.        ,  6.        ,  0.67596472,  4.        ],
       [ 2.        ,  7.        ,  0.79993986,  5.        ]])
>>> 



>>> dendrogram(Z)['ivl']
['2', '1', '3', '0', '4']
>>>
Источник

2 ответа

Решение

Почему это медленно? Конечно, наивный способ вычисления кластеризации связей O(n^3) но для n=5 это так дешево, как только может...

Для формата матрицы связи Scipy, см. Этот вопрос: формат связи Scipy

Обратите внимание, что вам все равно может понадобиться отсортировать данные оптимально. Кодирование матрицы связи, приведенное выше, дает

  • Элемент 1 и кластер 3 объединяются на высоте 0,1144 (в кластер из 2 элементов, #5)
  • Элемент 0 и кластер 4 объединяются на высоте 0,7999 (в кластер из 2 элементов, #6)
  • Кластер 5 и Кластер 6 объединяются на высоте 0,6759 (в кластер из 4 элементов, #7)
  • Элемент 2 и кластер 7 соединяются на высоте 0,7999 (в кластер из 5 элементов, #8)

но это может быть упорядочено путем связывания расстояния, а не в 1d порядке для визуализации (потому что никому, кто использует кластеризацию связей, не захочется запускать дюзрограмму viusalization впоследствии). Но в любом случае, вычисление дендрограммы должно быть порядка O(n log n) если вам нужно сортировать, достаточно дешево по сравнению с фактической кластеризацией.

Что-то в этом роде должно сработать:

n = len(Z) + 1
cache = dict()
for k in range(len(Z)):
  c1, c2 = int(Z[k][0]), int(Z[k][1])
  c1 = [c1] if c1 < n else cache.pop(c1)
  c2 = [c2] if c2 < n else cache.pop(c2)
  cache[n+k] = c1 + c2
print cache[2*len(Z)]

Это может показаться линейным, но ожидаемый размер массивов log nпоэтому, в зависимости от типа вашего списка, он все еще может быть O(n log n)в то время как со связанными списками это действительно должно быть выполнимо в O(n),

Но, в конце концов, вы можете избежать иерархической кластеризации. Это популярный вводный пример кластерного анализа, потому что его действительно легко понять концептуально. Есть несколько довольно хитрых алгоритмов (SLINK) для O(n^2) сложность. Но есть более современные и мощные алгоритмы кластеризации, которые имеют меньшую сложность. На самом деле, OPTICS (Википедия) вычисляет что-то очень похожее (когда вы устанавливаете minPts=2), и когда у вас есть хорошая структура индекса, он будет работать в O(n log n), Кроме того, вы можете увеличить minPts, чтобы получить больше значимых кластеров. (Но не используйте OPTICS в Weka или ту версию Python, которая витает вокруг - ведь они оба неполные или глючные!)

Источник

Существует специальная функция для расчета линеаризованных листовых порядков в scipy. Вот. scipy.cluster.hierarchy.leaves_list.

Источник
Другие вопросы по тегам