Должно ли расстояние быть «метрикой», чтобы иерархическая кластеризация действовала на нем?

9

Допустим, мы определяем расстояние, которое не является метрикой , между N элементами.

На основании этого расстояния мы затем используем агломерационную иерархическую кластеризацию .

Можем ли мы использовать каждый из известных алгоритмов (одиночная / максимальная / средняя связь и т. Д.), Чтобы получить значимые результаты? Или, другими словами, в чем проблема с их использованием, если расстояние не является метрикой?

clustering multilevel-analysis metric hierarchical-clustering Таль Галили
источник
Какие "предметы" в вашем случае? (Я спрашиваю, имеет ли это какое-либо отношение к психометрии, потому что если это так, я бы порекомендовал взглянуть на кластеризацию элементов или Revelle, W. Иерархический кластерный анализ и внутреннюю структуру тестов , MBR (1979) 14 : 57.)
ЧЛ

Ответы:

7

Требования к расстояниям зависят от метода иерархической кластеризации. Одиночные, полные, средние методы нуждаются в расстояниях, чтобы быть неотрицательными и симметричными. Методы Уорда, центроида и медианы нуждаются (в квадрате) в евклидовом (что даже более узкое определение, чем метрическое) расстояния, чтобы получить геометрически значимые результаты.

(Можно проверить, является ли его / ее матрица расстояний евклидовой, дважды центрировав ее [см. Мой ответ здесь ] и посмотрев на собственные значения; если не найдено отрицательных собственных значений, тогда расстояния действительно сходятся в евклидовом пространстве.)

ttnphns
источник
Спасибо. Следующий вопрос: должно ли неравенство треугольника выполняться для единичных, полных, средних методов? и если какое-то расстояние (например) не является симметричным, какую проблему оно представляет для этих методов? (Спасибо!)
Тал Галили
1
Классические методы иерархической кластеризации могут принимать только симметричную матрицу: расстояние от A до B = от B до A. Существуют и другие специальные методы для работы с асимметричными (вы можете Google). Что касается треугольного неравенства - это не обязательное условие для методов, которые вы упоминаете. (Тем не менее, общепринятое мнение о «расстоянии» как о чем-то, что связано с неравенством, поэтому стоит подумать о том, чтобы наложить его, если оно отсутствует. Для этого итеративно добавьте небольшую константу к расстояниям и проверьте. И если вы продолжите добавлять по достижении это тогда вы скоро прибудете на евклидовы расстояния)
ttnphns
5

Нет, расстояние не должно быть метрикой. Например, он может быть ультраметрическим:

d(A,B)≤max(d(A,C),d(B,C))

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

Хонг Оои
источник
Спасибо, Хонг. Я помню, что методы преобразования некоторых объектов в hclust требуют, чтобы дендрограмма была ультраметрической - я думаю, если это связано с тем, что вы написали. В любом случае, спасибо за ответ.
Тал Галили