Как кластеризовать объекты (без координат) - PullRequest
Новая
       39

Как кластеризовать объекты (без координат)

8 голосов
/ 28 марта 2009

У меня есть список непрозрачных объектов. Я могу только рассчитать расстояние между ними (не правда, просто установив условия для задачи): 

class Thing {
    public double DistanceTo(Thing other);
}

Я бы хотел сгруппировать эти объекты. Я хотел бы контролировать количество кластеров, и я бы хотел, чтобы «закрытые» объекты находились в одном кластере: 

List<Cluster> cluster(int numClusters, List<Thing> things);

Может ли кто-нибудь предложить (и дать ссылку на ;-)) некоторые алгоритмы кластеризации (чем проще, тем лучше!) Или библиотеки, которые могут мне помочь?

Уточнение Большинство алгоритмов кластеризации требуют размещения объектов в некотором N-мерном пространстве. Это пространство используется для поиска "центроидов" скоплений. В моем случае я не знаю, что такое N, и при этом я не знаю, как извлечь систему координат из объектов. Все, что я знаю, это то, насколько далеко находятся два объекта. Я хотел бы найти хороший алгоритм кластеризации, который использует только эту информацию.

Представьте, что вы группируете на основе "запаха" объекта. Вы не знаете, как разместить «запахи» на 2D-плоскости, но вы точно знаете, похожи ли эти два запаха или нет.

Ответы [ 5 ]

6 голосов
/ 05 апреля 2009

Я думаю, что вы ищете K-Medoids . Это как K-означает, что вы заранее указываете количество кластеров, K , но это не требует, чтобы у вас было понятие "усреднения" объектов, которые вы кластеризуете, как K-средних делает.

Вместо этого у каждого кластера есть представитель medoid , который является членом кластера, ближайшего к середине. Вы можете думать об этом как о версии K-средних, которая находит «медианы» вместо «означает». Все, что вам нужно, это метрика расстояния для кластеризации, и я использовал это в некоторых своих работах по тем же причинам, на которые вы ссылаетесь.

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

  1. PAM является базовой O (n ^ 2) реализацией K-medoids.
  2. CLARA - это гораздо более быстрая, пробная версия PAM. Он работает путем кластеризации случайно выбранных подмножеств объектов с PAM и группирования всего набора объектов на основе подмножества. С этим вы все равно сможете быстро получать очень хорошие кластеризации.

Если вам нужна дополнительная информация, вот статья , в которой дается обзор этих и других методов K-medoids.

3 голосов
/ 28 марта 2009

Вот схема алгоритма кластеризации, который не требует K-средних для нахождения центроида.

  1. Определить расстояние между всеми объектами. Запишите n большинство отдельных объектов.
    [ находит корни наших кластеров, время O (n ^ 2) ]
  2. Назначьте каждому из этих n случайных точек n новых отдельных кластеров.
  3. Для каждого другого объекта:
    [ назначить объекты кластерам, время O (n ^ 2) ]
    1. Для каждого кластера:
      1. Рассчитать среднее расстояние от кластера до этого объекта путем усреднения расстояния каждого объекта в кластере до объекта.
    2. Назначить объект ближайшему кластеру.

Этот алгоритм, безусловно, будет кластеризовать объекты. Но его время выполнения составляет O (n ^ 2) . Кроме того, он руководствуется теми первыми n выбранными точками.

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

2 голосов
/ 28 марта 2009

Вот быстрый алгоритм. 

While (points_left > 0) {
 Select a random point that is not already clustered
 Add point and all points within x distance 
   that aren't already clustered to a new cluster.
}

Либо прочитайте страницу википедии . Кластеризация K-средних - хороший выбор:

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

Шаги алгоритма: 

* Choose the number of clusters, k.
* Randomly generate k clusters and determine the cluster centers, or
  directly generate k random points as cluster centers.
* Assign each point to the nearest cluster center.
* Recompute the new cluster centers.
* Repeat the two previous steps until some convergence criterion is
  met (usually that the assignment hasn't changed).

Основные преимущества этого алгоритма его простота и скорость, позволяет работать с большими наборами данных. Его недостаток в том, что он не дают одинаковый результат с каждым прогоном, поскольку полученные кластеры зависят от начальные случайные назначения. Это минимизирует внутрикластерную дисперсию, но не гарантирует, что результат имеет глобальный минимум дисперсии. Другая Недостатком является требование для понятие средства быть определяемым что не всегда так. Для таких Наборы данных вариант K-Medoids является необходимо.

1 голос
/ 05 апреля 2009

Филогенетический анализ последовательности ДНК регулярно использует иерархическую кластеризацию на текстовых строках с матрицами расстояний [выравнивания]. Вот хороший учебник по R для кластеризации:

(Ярлык: перейти прямо к разделу «Иерархическая агломерация» ...)

Вот некоторые другие библиотеки [language]:

Этот подход может помочь определить, сколько [k] «естественных» кластеров существует и какие объекты использовать в качестве корней для подходов k-средних, описанных выше.

1 голос
/ 29 марта 2009

Как насчет этого подхода:

  1. Назначить все объекты одному кластеру.
  2. Найдите два объекта, a и b , которые находятся в одном кластере, k и которые находятся на максимальном расстоянии друг от друга. Чтобы уточнить, должен быть один a и b для всего набора, а не один a и b для каждого кластера.
  3. Разделите кластер k на два кластера, k1 и k2 , один с объектом a и один с объектом b .
  4. Для всех других объектов в кластере k , добавьте их в k1 или k2 , определив минимальное среднее расстояние до всех других объектов в этом кластере.
  5. Повторяйте шаги 2-5, пока не будут сформированы N кластеров.

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

...