Вопрос по algorithm, math – Неуправляемая кластеризация с неизвестным количеством кластеров

63

У меня большой набор векторов в 3 измерениях. Мне нужно сгруппировать их на основе евклидова расстояния так, чтобы все векторы в любом конкретном кластере имели евклидово расстояние между собой меньше, чем пороговое значение «T».

Я не знаю, сколько существует кластеров. В конце могут существовать отдельные векторы, которые не являются частью какого-либо кластера, потому что его евклидово расстояние не меньше, чем "T". с любым из векторов в пространстве.

Какие существующие алгоритмы / подходы следует использовать здесь?

@ Anony-Mousse Есть идеи, как мне получить представителей кластера от DBSCAN? Divij Sehgal
Кластеры DBSCAN могут иметь произвольную форму. Что было бы хорошим "представителем"? затем? Anony-Mousse
Определенно посмотрите наDBSCAN в Википедии. Anony-Mousse

Ваш Ответ

4   ответа
0

ОПТИКА, который хорошо работает с большими наборами данных.

OPTICS: Ordering Points To Identify the Clustering Structure Closely related to DBSCAN, finds core sample of high density and expands clusters from them 1. Unlike DBSCAN, keeps cluster hierarchy for a variable neighborhood radius. Better suited for usage on large datasets than the current sklearn impl,ementation of DBSCAN

from sklearn.cluster import OPTICS
db = DBSCAN(eps=3, min_samples=30).fit(X)

Тонкая настройкаeps, min_samples согласно вашему требованию

21

цию. Я хотел бы уточнить, какchoose порог кластеризации.

Одним из способов является вычисление кластеров на основе различных пороговых значений.t1, t2, t3, ... и затем вычислите метрику для "качества" кластеризации. Предпосылка заключается в том, что качество кластеризации сoptimal количество кластеров будет иметь максимальное значение показателя качества.

Примером метрики хорошего качества, которую я использовал в прошлом, является Calinski-Harabasz. Вкратце: вы вычисляете средние расстояния между кластерами и делите их на расстояния внутри кластера. Оптимальное назначение кластеризации будет иметь кластеры, которые больше всего отделены друг от друга, и кластеры, которые являются "самыми узкими".

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

Дайте мне знать, если вам понадобится больше ссылок, и я поищу на своем жестком диске некоторые бумаги.

Error: User Rate Limit Exceeded
11

DBSCAN алгоритм. Это кластеры, основанные на локальной плотности векторов, то есть они не должны быть больше, чем некоторыеε расстояние друг от друга, и может определить количество кластеров автоматически. Он также учитывает выбросы, то есть указывает на недостаточное количествоε- соседи, чтобы не быть частью кластера. Страница Википедии ссылается на несколько реализаций.

68

иерархическая кластеризация, Это довольно простой подход, поэтому существует множество реализаций. Например, он включен в PythonSciPy.

Смотрите, например, следующий скрипт:

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()

Который дает результат, подобный следующему изображению. clusters

Порог, заданный в качестве параметра, является значением расстояния, на основании которого принимается решение о том, будут ли точки / кластеры объединены в другой кластер. Используемая метрика расстояния также может быть указана.

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

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

Существуют и другие алгоритмы, которые будут работать лучше, и станут актуальными в ситуациях с большим количеством точек данных. Поскольку другие ответы / комментарии предполагают, что Вы могли бы также хотеть взглянуть на алгоритм DBSCAN:

https://en.wikipedia.org/wiki/DBSCAN http://scikit-learn.org/stable/auto_examples/cluster/plot_dbscan.html http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html#sklearn.cluster.DBSCAN

Чтобы получить хороший обзор этих и других алгоритмов кластеризации, взгляните также на эту демонстрационную страницу (из библиотеки Python's scikit-learn):

http://scikit-learn.org/stable/modules/clustering.html

Изображение скопировано с этого места:

http://scikit-learn.org/stable/auto_examples/cluster/plot_cluster_comparison.html

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

Error: User Rate Limit Exceeded London guy
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded London guy
Error: User Rate Limit Exceeded

Похожие вопросы