Как вы сравниваете «сходство» между двумя дендрограммами (в R)?

Question

У меня есть две дендрограммы, которые я хочу сравнить друг с другом, чтобы выяснить, насколько они «похожи». Но я не знаю ни одного метода для этого (не говоря уже о коде для его реализации, скажем, в R).

Есть ли отведения?

ОБНОВЛЕНИЕ (2014-09-13):

С тех пор как я задал этот вопрос, я написал пакет R под названием dendextend для визуализации, манипуляции и сравнения дендрограммы. Этот пакет находится на CRAN и поставляется с подробной виньеткой . Включает в себя такие функции, как cor_cophenetic, cor_bakers_gamma и Bk / Bk_plot. А также tanglegram функция для визуального сравнения двух деревьев.

Answer 1

Сравнение дендрограмм не совсем то же самое, что сравнение иерархических кластеров, потому что первый включает в себя длину ветвей, а также расщепления, но я также думаю, что это хорошее начало. Я бы посоветовал вам прочитать Е. Б. Фаулкс и С. Л. Мэлловс (1983). «Метод сравнения двух иерархических кластеров». Журнал Американской статистической ассоциации 78 (383): 553–584 (ссылка) .

Их подход основан на вырубке деревьев на каждом уровне k , получении меры Bk , которая сравнивает группировки в k кластеров, а затем изучает Bk против k участков. Мера Bk основана на просмотре пар объектов и определении, попадают ли они в один кластер или нет.

Я уверен, что можно написать код на основе этого метода, но сначала нам нужно знать, как дендрограммы представлены в R.

Answer 2

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

Answer 3

посмотрите на эту страницу :

У меня также есть похожий вопрос здесь

Кажется, мы можем использовать копенетическую корреляцию, чтобы измерить сходство между двумя дендрограммами. Но, похоже, в настоящее время в R нет функции для этой цели.

РЕДАКТИРОВАТЬ в 2014,9,18: Функция cophenetic в пакете stats способна вычислять матрицу кофенетических различий. и корреляция может быть рассчитана с использованием функции cor. как указал @Tal, функция as.dendrogram вернула дерево в другом порядке, что приведет к неверным результатам, если мы вычислим корреляцию на основе результатов дендрограммы. Как показано на примере функции cor_cophenetic, функция в пакете dendextend:

set.seed(23235)
ss <- sample(1:150, 10 )
hc1 <- iris[ss,-5] %>% dist %>% hclust("com")
hc2 <- iris[ss,-5] %>% dist %>% hclust("single")
dend1 <- as.dendrogram(hc1)
dend2 <- as.dendrogram(hc2)
# cutree(dend1)
cophenetic(hc1)
cophenetic(hc2)
# notice how the dist matrix for the dendrograms have different orders:
cophenetic(dend1)
cophenetic(dend2)
cor(cophenetic(hc1), cophenetic(hc2)) # 0.874
cor(cophenetic(dend1), cophenetic(dend2)) # 0.16
# the difference is becasue the order of the distance table in the case of
# stats:::cophenetic.dendrogram will change between dendrograms!

Answer 4

Взгляните на эту страницу, которая содержит много информации о программном обеспечении, работающем с деревьями, включая дендрограммы. Я заметил несколько инструментов, которые имеют дело со сравнением дерева, хотя я лично еще не использовал ни один из них. Там также приведено несколько ссылок.

Answer 5

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

Answer 6

В сообществе филогенетиков имеется обширная литература по метрикам древовидного расстояния, которая, по-видимому, игнорируется с точки зрения компьютерных наук. См. dist.topo пакета ape для двух метрик расстояния между деревьями и нескольких ссылок (Penny and Hardy 1985, Kuhner and Felsenstein 1994), в которых рассматривается сходство разделов дерева, а также Robinson -Foulds метрика , которая имеет реализацию R в пакете phangorn.

Одна проблема заключается в том, что эти метрики не имеют фиксированного масштаба, поэтому они полезны только в случаях 1) сравнения деревьев или 2) сравнения с некоторой сгенерированной базовой линией, возможно, с помощью тестов перестановки, аналогичных тому, что Tal закончил с Baker Gamma в своем фантастическом пакете dendextend.

Если у вас есть объекты hclust или dendrogram, сгенерированные из R иерархической кластеризации, использование as.phylo из пакета ape преобразует ваши дендрограммы в филогенетические деревья для использования в этих функциях.