Почему кластеризация Крускала порождает субоптимальные классы?

Question

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

Я сравнил свой результат с предлагаемым оптимальным (1) с использованием индекса rand, который для k = 7 составил 95,5%. Сравнение можно увидеть по ссылке ниже.

Проблема:

Набор имеет 5 четко разнесенные кластеры, которые легко классифицировать по алгоритму, но результаты неутешительны для к> 5, что, когда вещи начинают становиться сложнее. Я считаю, что мой алгоритм правильный, и, возможно, данные особенно плохи для подхода Крускала. Известно, что агломерационная кластеризация с одиночной связью, например, Kruskal's, плохо справляется с некоторыми проблемами, поскольку она снижает оценку качества кластера до единственного сходства между двумя точками.

Идея алгоритма очень проста:

• Сделать полный граф с набором данных, с весом краев , находящихся расстояние евклидовой между парой.
• Сортировка списка по весу.
• Для каждого края (по порядку) добавьте его в остовный лес, если он не образует цикл. Остановитесь, когда пройдены все края или когда в оставшемся лесу есть k деревьев.

Bottomline: Почему алгоритм неудачу, как это? Это вина Крускаля? Если да, то почему именно? Любые предложения по улучшению результатов без отказ от Kruskal?

(1): Gionis, A., H. Mannila и P. Tsaparas, Clustering aggregation. ACM Transactions на Обнаружение знаний из данных (TKDD), 2007.1 (1): стр.1-30.

Answer 1

Это известный как одноканальный эффект.

Kruskal, по-видимому, является полу-умным способом вычисления односвязной кластеризации. Наивный подход для «иерархической кластеризации» - O(n^3), а подход Крускала должен быть O(n^2 log n) из-за необходимости сортировать края n^2.

Обратите внимание, что SLINK может выполнять односвязную кластеризацию в O(n^2) времени выполнения и O(n) памяти.

Вы пытались загрузить свой набор данных, например. в ELKI, и сравните результат с одноканальной кластеризацией.

Для того, чтобы получить результаты Бетта, попробовать другие связи (как правило, в O(n^3) выполнения) или плотности на основе кластеризации, такие как DBSCAN (в O(n^2) без индекса и O(n log n) с индексом). На этом наборе данных игрушки epsilon=2 и minPts=5 должны работать хорошо.

Answer 2

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

Answer 3

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

Видимо, это похоже на то, что К-средство может преуспеть - кроме верхнего левого, скопления почти круговые.