Неконтролируемая кластеризация с неизвестным количеством кластеров

Вы можете использовать иерархическую кластеризацию. Это довольно простой подход, поэтому существует множество его реализаций. Например, он включен в 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:

• 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 scikit-learn):

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

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

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

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

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

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

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

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

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

Используйте OPTICS, которая хорошо работает с большими наборами данных. .

ОПТИКА: упорядочивание точек для определения структуры кластеризации Тесно связана с DBSCAN, находит основные образцы с высокой плотностью и расширяет из них кластеры 1. В отличие от DBSCAN, сохраняет кластерную иерархию для переменного радиуса окрестности. Лучше подходит для использования с большими наборами данных, чем текущая реализация DBSCAN в sklearn.

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

Настройте eps, min_samples в соответствии с вашими требованиями.

У вас может не быть решения: это тот случай, когда расстояние между любыми двумя отдельными точками входных данных всегда больше T. Если вы хотите вычислить количество кластеров только из входных данных, вы можете посмотреть на MCG, иерархическую кластеризацию метод с критерием автоматической остановки: см. бесплатную статью семинара по адресу https://hal.archives-ouvertes.fr/hal-02124947/document (содержит библиографические ссылки).

Я хочу добавить к ответу 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 кластеров.

threshold = 1
clusters_list = hierarchy.fcluster(ward_array, threshold, criterion="distance")
print("Clustering list: {}".format(clusters_list))

Теперь каждое значение в cluster_list будет назначенным идентификатором кластера соответствующей точки в ori_array.