Алгоритм кластеризации [оценки] с матрицей расстояний в качестве входных данных - PullRequest
Новая
       13

Алгоритм кластеризации [оценки] с матрицей расстояний в качестве входных данных

0 голосов
/ 30 мая 2010

Кто-нибудь может предложить какой-нибудь алгоритм кластеризации, который может работать с матрицей расстояний в качестве входных данных? Или алгоритм, который может оценить «добротность» кластеризации также на основе матрицы расстояний?

В данный момент я использую модификацию алгоритма Крускала (http://en.wikipedia.org/wiki/Kruskal%27s_algorithm), чтобы разделить данные на два кластера. Однако возникает проблема. Когда данные не имеют четких кластеров, алгоритм все равно создаст два кластера один кластер, содержащий один элемент, а другой - все остальные. В этом случае я бы предпочел, чтобы один кластер содержал все элементы, а другой - пустой.

Существуют ли алгоритмы, способные выполнять этот тип кластеризации?

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

Алгоритмы должны работать только с матрицами расстояния (подобия) в качестве входных данных.

Ответы [ 3 ]

2 голосов
/ 30 мая 2010

Или алгоритм, который может оценить "совершенство" кластеризации также на основе матрицы расстояний?

KNN должен быть полезен при оценке «качества» кластерного задания. Вот как это сделать:

Учитывая матрицу расстояний, каждая точка которой помечена в соответствии с кластером, которому она принадлежит («метка кластера»):

  1. Проверка метки кластера каждой точки по отношению к меткам кластера, подразумеваемым из классификации k-ближайших соседей
  2. Если k-ближайшие соседи подразумевают альтернативный кластер, эта классифицированная точка понижает общий рейтинг «благости» кластера
  3. Суммируйте вклады "рейтинга добродетели" каждого из ваших пикселей, чтобы получить общую "оценку добродетели" для всего кластера

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

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

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

1 голос
/ 30 мая 2010

Некоторые подходы, которые можно использовать для оценки количества кластеров:

0 голосов
/ 10 июня 2010

scipy.cluster.hierarchy проходит 3 шага, точно так же как Matlab (TM) clusterdata 

Y = scipy.spatial.distance.pdist( pts )  # you have this already
Z = hier.linkage( Y, method )  # N-1
T = hier.fcluster( Z, ncluster, criterion=criterion )

Здесь linkage может быть модифицированным Крускалом, не знаю. Это ТАК ответ (Гм) использует выше.
В качестве меры кластеризации радиус = среднеквадратичное расстояние до центра кластера является быстрым и разумным, для 2d / 3d очков.

Расскажите нам о своем Npt, ndim, ncluster, hier / flat? Кластеризация - это большая область, один размер подходит не всем.

...