Иерархическая кластеризация эвристики

Question

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

Но, может быть, есть лучшее решение?

Спасибо

PS Спасибо всем!

На самом деле я пытался использовать k-means и некоторые варианты CLOPE, но не получил хороших результатов.

Итак, теперь я знаю, что кластеры моего набора данных на самом деле имеют сложную структуру (гораздо более сложную, чем n-сферы).

Вот почему я хочу использоватьиерархическая кластеризация.Также Я предполагаю, что кластеры выглядят как конкатенации n-размерности (например, 3D или 2D цепочка).Поэтому я использую стратегию single-link .Но меня беспокоит - как объединить разные кластеры друг с другом (, в какой ситуации мне нужно создать общий корневой кластер, и в каких ситуациях мне нужно объединить все подкластеры в один кластер?).Я использую такую ​​простую стратегию:

• Если кластеры (или векторы) расположены слишком близко друг к другу - я объединяю их содержимое в один кластер (регулируется порогом)
• Если кластеры (или векторы) находятся слишком далеко друг от друга - я создаю корневой кластер и помещаю их в него

Но используя эту стратегию, я получаю очень большие скопления деревьев .Я пытаюсь найти удовлетворительный порог.Но, может быть, может быть лучшая стратегия для создания кластерного дерева?

Вот простая картина, описывает мой вопрос:

Answer 1

A много работ было выполнено в этой области. Обычный совет - начинать с кластеризации K-средних, если у вас нет действительно веской причины поступить иначе - но K-means не выполняет иерархическую кластеризацию (обычно в любом случае), поэтому у вас может быть веская причина действуйте иначе (хотя вполне возможно сделать иерархические K-средства, выполнив первый проход для создания кластеров, затем сделайте еще один проход, используя центр тяжести каждого из этих кластеров в качестве точки, и продолжайте, пока у вас не будет как можно меньше кластеров высокого уровня по желанию).

Существует довольно много других моделей кластеризации, и довольно много работ, посвященных относительным преимуществам и недостаткам, таких как:

1. Попарная кластеризация и графические модели
2. За пределами попарной кластеризации
3. Параллельная попарная кластеризация
4. Быстрая жадная парная кластеризация расстояний. Алгоритм и его использование при раскрытии тематики. структуры в больших наборах данных.
5. Алгоритм попарной кластеризации
6. Иерархическая агломерационная кластеризация

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

Answer 2

Существует целый зоопарк кластерных алгоритмов.Среди них минимальное связующее дерево, то есть кластеризация с одиночной связью, обладает некоторыми хорошими теоретическими свойствами, как отмечается, например, при http://www.cs.uwaterloo.ca/~mackerma/Taxonomy.pdf. В частности, если вы берете минимальное связующее дерево и удаляете все ссылки, длина которых превышает некоторую пороговую длину, то получится группировкаточки в кластерах должны иметь минимальную общую длину оставшихся ссылок для любой группировки такого размера, по той же причине, по которой алгоритм Крускала создает минимальное остовное дерево.

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