具有未知数量的簇的无监督聚类

Question

我有三个维度的大量向量.我需要基于欧几里德距离对这些进行聚类,使得任何特定聚类中的所有向量彼此之间的欧几里德距离小于阈值"T".

我不知道有多少个集群存在.最后,可能存在不属于任何聚类的个体向量,因为其欧氏距离不小于空间中任何向量的"T".

这里应该使用哪些现有的算法/方法？

Answer 1

您可以使用分层聚类.这是一种相当基本的方法,因此有很多实现可用.例如,它包含在Python的scipy中.

请参阅以下脚本:

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

从该地方复制的图像:

如您所见,每种算法都会对需要考虑的簇的数量和形状做出一些假设.无论是算法强加的隐含假设还是参数化指定的明确假设.

Answer 2

moooeeeep的答案建议使用层次聚类.我想详细说明如何选择聚类的阈值.

一种方法是基于不同的阈值t1,t2,t3 ...... 计算聚类,然后计算聚类"质量"的度量.前提是具有最佳簇数的聚类的质量将具有质量度量的最大值.

我过去使用过的高质量度量标准的一个例子是Calinski-Harabasz.简而言之:您计算群集间平均距离并将其除以群集内距离.最佳聚类分配将具有彼此分离最多的聚类和"最紧密"的聚类.

顺便说一句,您不必使用分层聚类.您还可以使用k -means之类的东西,为每个k预先计算它,然后选择具有最高Calinski-Harabasz分数的k.

如果您需要更多参考资料,请告诉我,我会在硬盘上搜索一些文件.

Answer 3

查看DBSCAN算法.它基于矢量的局部密度聚类,即它们必须不超过一些ε距离,并且可以自动确定聚类的数量.它还将异常值(即具有不足数量的ε-邻居的点)视为不是群集的一部分.维基百科页面链接到一些实现.