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

Ответ 1

Вы можете использовать иерархическую кластеризацию . Это довольно простой подход, поэтому доступно множество реализаций. Это, например, включено в Python scipy.

См., например, следующие script:

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 (single/complete/average... linkage). По вашему сообщению, я думаю, вы хотели бы использовать полную привязку.

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

Существуют и другие алгоритмы, которые будут работать лучше, что станет актуальным в ситуациях с большим количеством точек данных. Как и другие ответы/комментарии, вы также можете взглянуть на алгоритм 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

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

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

Ответ 2

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

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

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

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

Сообщите мне, если вам нужно больше ссылок, и я буду расчесывать свой жесткий диск для некоторых документов.

Ответ 3

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