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

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

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

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

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

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


cluster-analysis algorithm math
person Max    schedule 30.05.2010    source источник
comment
K-ближайшие соседи (en.wikipedia.org/wiki/KNN) - простой и эффективный алгоритм кластеризации. После небольшой настройки он должен дать вам то, что вам нужно.   -  person Amichai    schedule 30.05.2010
comment
K ближайших соседей - по происхождению алгоритм классификации (я не знаю, как его использовать в кластеризации). Одним из самых известных является кластеризация по K-средним. (en.wikipedia.org/wiki/K-means_clustering)   -  person Max    schedule 30.05.2010
comment
Насколько я знаю, в исходном виде мне понадобятся координаты для этого алгоритма, которых у меня нет. Как мне настроить его так, чтобы он работал с матрицами расстояний?   -  person Max    schedule 30.05.2010
comment
Насколько я понимаю, кластеризация k-средних - это алгоритм кластерного анализа, а не алгоритм кластеризации как таковой. K-means - прекрасный способ анализа качества кластера. Поскольку проблема кластеризации k-средних является NP-сложной, и вам нужно будет использовать какой-то другой алгоритм для приближения идеального кластера k-средних. Алгоритм Ллойда (en.wikipedia.org/wiki/Lloyd's_algorithm) не работать с матрицей расстояний, поскольку для этого требуется вычисление центроидов кластеров (также он работает только при поиске заранее определенного количества кластеров в ваших данных).   -  person Amichai    schedule 30.05.2010

Ответы (3)


arrow_upward
2
arrow_downward

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

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

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

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

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

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

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

person Amichai    schedule 30.05.2010
comment
Если у него уже есть расстояние между всеми точками, то KNN не займет много времени. Большим шагом в KNN обычно является вычисление евклидова расстояния между всеми точками. - person JSchlather; 30.05.2010

arrow_upward
1
arrow_downward

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

person Jouni K. Seppänen    schedule 30.05.2010

arrow_upward
0
arrow_downward

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 может быть модифицированный Краскал, не знаю. В этом ответе SO (кхм) используется вышеуказанное.
В качестве меры кластеризации, радиус = среднеквадратичное расстояние до центра кластера является быстрым и разумным для точек 2d / 3d.

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

person denis    schedule 10.06.2010