Разные результаты для hclust и agnes с использованием средней ссылки

Я применяю простую процедуру кластеризации к пользовательской смоделированной матрице подобия. (https://github.com/ewouddt/Files/blob/master/sim_col.RData)

Однако я замечаю разницу между процедурами hclust и agnes при использовании средней ссылки (Примечание: я наблюдал такое же поведение и для полной ссылки)

load("sim_col.RData") # A 606 x 606 similarity matrix
library(cluster)

c1 <- hclust(as.dist(1-sim_col),method="average")
c2 <- as.hclust(agnes(as.dist(1-sim_col),diss=TRUE,method="average"))

dev.new()
plot(c1)
dev.new()
plot(c2)

cut1 <- cutree(c1,k=20)
cut2 <- cutree(c2,k=20)
cut1
cut2

sort(table(cut1))
cut1
# cut1
# 10  18   9  19   3  20   4  11   7  15  17   5   6  12  16   2   8   1  13  14 
#  2   5   7   8  11  13  14  14  15  19  19  21  23  26  27  31  33  80  95 143
sort(table(cut2))
# cut2
# 18  20  19  11  17   7   8   4  12   5   9   3  10  16   2   6  14  13   1  15 
#  4   6   8   9   9  13  13  14  15  16  17  19  20  29  31  31  54  62 115 121

Как и ожидалось, дендрограммы выглядят по-разному из-за разного порядка hclust и agnes. Однако разрезание меток (например, на k=20) показывает разные (хотя и похожие) результаты для наблюдений. (Например, вы можете видеть, что количество этикеток различается между двумя результатами)

Я делаю глупую ошибку или hclust и agnes не должны возвращать один и тот же результат после обрезки дерева? Если две процедуры не должны возвращать один и тот же результат, в чем заключается разница двух функций?


person Ewoud    schedule 11.03.2017    source источник


Ответы (1)


За исключением однозвенного, результат кластеризации не может быть однозначно определен.

Рассмотрим следующий набор данных:

1 2 3 4

Есть три минимума: слияние 1 и 2, или 2 и 3, или 3 и 4.

За исключением одной ссылки, мы получим разные результаты в зависимости от того, объединяем ли мы сначала 2 и 3 или одну из других пар.

В частности, обычные алгоритмы не смогут гарантировать нахождение оптимального решения. Если вы хотите гарантировать это, вы, вероятно, будете NP-полным. Но это тоже может не иметь большого значения.

person Has QUIT--Anony-Mousse    schedule 11.03.2017