Неконтролируемая кластеризация с неизвестным количеством кластеров
Автор вопроса: London guyОтветов: 6
У меня есть большой набор векторов в 3-х измерениях. Мне нужно сгруппировать их на основе евклидова расстояния, чтобы все векторы в любом конкретном кластере имели евклидово расстояние между собой меньше порогового значения "T".
Я не знаю, сколько существует кластеров. В конце могут существовать отдельные векторы, которые не являются частью какого-либо кластера, потому что его евклидово расстояние не меньше "T" с любым из векторов в пространстве.
Какие существующие алгоритмы / подходы следует здесь использовать?
Обязательно посмотрите DBSCAN в Википедии. Has QUIT--Anony-Mousse 14.04.2012
@ Anony-Mousse Есть идеи, как я могу получить представителей кластера от DBSCAN? Divij Sehgal 02.12.2018
Кластеры DBSCAN могут иметь произвольную форму. Кто тогда будет хорошим представителем? Has QUIT--Anony-Mousse 03.12.2018
DBSCAN с примером использования: scikit-learn .org / стабильный / модули / сгенерированный / Jean Monet 28.04.2021
Вы можете использовать иерархическую кластеризацию. Это довольно простой подход, поэтому существует множество его реализаций. Например, он включен в scipy Python.
См., Например, следующий сценарий:
import matplotlib.pyplot as plt
import numpy
import scipy.cluster.hierarchy as hcluster
# generate 3 clusters of each around 100 points and one orphan point
N=100
data = numpy.random.randn(3*N,2)
data[:N] += 5
data[-N:] += 10
data[-1:] -= 20
# clustering
thresh = 1.5
clusters = hcluster.fclusterdata(data, thresh, criterion="distance")
# plotting
plt.scatter(*numpy.transpose(data), c=clusters)
plt.axis("equal")
title = "threshold: %f, number of clusters: %d" % (thresh, len(set(clusters)))
plt.title(title)
plt.show()
Это дает результат, аналогичный следующему изображению.
Пороговое значение, заданное в качестве параметра, представляет собой значение расстояния, на основе которого принимается решение о том, будут ли точки / кластеры объединены в другой кластер. Также можно указать используемую метрику расстояния.
Обратите внимание, что существуют различные методы вычисления сходства внутри и между кластерами, например расстояние между ближайшими точками, расстояние между самыми дальними точками, расстояние до центров кластеров и т. д. Некоторые из этих методов также поддерживаются модулем иерархической кластеризации scipys (одиночная / полная / средняя ... связь). Согласно вашему сообщению, я думаю, вы хотели бы использовать полную связь.
Обратите внимание, что этот подход также допускает небольшие (одноточечные) кластеры, если они не соответствуют критерию подобия других кластеров, то есть порогу расстояния.
Есть другие алгоритмы, которые будут работать лучше, что станет актуальным в ситуациях с большим количеством точек данных. Как показывают другие ответы / комментарии, вы также можете взглянуть на алгоритм DBSCAN:
Как видите, каждый алгоритм делает некоторые предположения о количестве и форме кластеров, которые необходимо учитывать. Будь то неявные предположения, налагаемые алгоритмом, или явные предположения, определенные параметризацией.
Ответ 2 · рейтинг 23 · Max
Ответ moooeeeep рекомендовал использовать иерархическую кластеризацию. Я хотел подробнее рассказать о том, как выбрать порог кластеризации.
Один из способов - вычислить кластеризацию на основе разных пороговых значений t1, t2, t3, ... и затем вычислить метрику для "качества" кластеризации. Предпосылка состоит в том, что качество кластеризации с оптимальным количеством кластеров будет иметь максимальное значение показателя качества.
Примером метрики хорошего качества, которую я использовал в прошлом, является Calinski-Harabasz. Вкратце: вы вычисляете средние расстояния между кластерами и делите их на расстояния внутри кластера. При оптимальном назначении кластеризации кластеры будут наиболее отделены друг от друга, а кластеры - наиболее "плотными".
Кстати, вам не обязательно использовать иерархическую кластеризацию. Вы также можете использовать что-то вроде k -means, предварительно вычислить его для каждого k, а затем выбрать k, у которого наивысший балл Калински-Харабаса .
Дайте мне знать, если вам понадобятся дополнительные ссылки, и я просмотрю свой жесткий диск в поисках статей.
Ответ 3 · рейтинг 12 · Fred Foo
Ознакомьтесь с алгоритмом DBSCAN. Он объединяется в кластеры на основе локальной плотности векторов, т.е. они не должны находиться на расстоянии более некоторого ε друг от друга, и может автоматически определять количество кластеров. Он также считает, что выбросы, то есть точки с недостаточным количеством ε -соседей, не являются частью кластера. На странице Википедии есть ссылки на несколько реализаций.
Ответ 4 · Ravindra babu
Используйте OPTICS, которая хорошо работает с большими наборами данных. .
ОПТИКА: упорядочивание точек для определения структуры кластеризации Тесно связана с DBSCAN, находит основные образцы с высокой плотностью и расширяет из них кластеры 1. В отличие от DBSCAN, сохраняет кластерную иерархию для переменного радиуса окрестности. Лучше подходит для использования с большими наборами данных, чем текущая реализация DBSCAN в sklearn.
from sklearn.cluster import OPTICS
db = OPTICS(eps=3, min_samples=30).fit(X)
Настройте eps, min_samples в соответствии с вашими требованиями.
Ответ 5 · Petitjean
У вас может не быть решения: это тот случай, когда расстояние между любыми двумя отдельными точками входных данных всегда больше T. Если вы хотите вычислить количество кластеров только из входных данных, вы можете посмотреть на MCG, иерархическую кластеризацию метод с критерием автоматической остановки: см. бесплатную статью семинара по адресу https://hal.archives-ouvertes.fr/hal-02124947/document (содержит библиографические ссылки).
Ответ 6 · Phạm Tùng Lâm
Я хочу добавить к ответу moooeeeep, используя иерархическую кластеризацию. Это решение работает для меня, хотя пороговое значение выбирается довольно случайно. Обратившись к другому источнику и проверив самостоятельно, я получил лучший метод, и порог можно легко выбрать с помощью дендрограммы:
from scipy.cluster import hierarchy
from scipy.spatial.distance import pdist
import matplotlib.pyplot as plt
ori_array = ["Your_list_here"]
ward_array = hierarchy.ward(pdist(ori_array))
dendrogram = hierarchy.dendrogram(hierarchy.linkage(ori_array, method = "ward"))
plt.title('Dendrogram')
plt.xlabel('Customers')
plt.ylabel('Euclidean distances')
plt.show()
Вы увидите такой график. щелкните здесь. Затем, проведя горизонтальную линию, скажем, на расстоянии = 1, количество соединений будет вашим желаемым количеством кластеров. Итак, здесь я выбираю порог = 1 для 4 кластеров.
