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

我有一个三维vector大集。 我需要根据欧几里德距离对它们进行聚类，使得任何特定聚类中的所有向量之间的欧氏距离小于阈值“T”。

我不知道有多less个集群存在。 最后，可能存在不属于任何聚类的单个vector，因为其欧几里得距离不小于空间中任何vector的“T”。

现在应该使用哪些现有的algorithm/方法？

谢谢Abhishek S

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等级聚类模块（ 单/完整/平均…连接 ）所支持。 根据你的文章，我认为你会想要使用完整的链接 。

请注意，这种方法还允许小（单点）群集，如果它们不符合其他群集的相似性标准，即距离阈值。

---

还有其他的algorithm会performance得更好，这将在大量数据点的情况下变得相关。 正如其他答案/意见build议你可能也想看看DBSCANalgorithm：

• 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

---

对于这些和其他聚类algorithm的一个很好的概述，也可以看看这个演示页（Python的scikit学习库）：

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

从该地点复制的图像：

如您所见，每个algorithm都会对需要考虑的群集的数量和形状进行一些假设。 无论是由algorithm施加的隐含假设还是由参数化指定的明确假设。

Answer 2

moooeeeep的答案build议使用层次聚类。 我想详细说明如何select聚类的阈值。

一种方法是基于不同的阈值t1 ， t2 ， t3 ，…计算聚类，然后计算聚类的“质量”度量。 前提是具有最佳聚类数量的聚类的质量将具有质量度量的最大值。

Calinski-Harabasz是我过去使用的一个高质量指标的例子。 简而言之：您计算平均簇间距离并将它们除以簇内距离。 最佳的聚类分配将具有彼此最分离的聚类，并且是“最紧密”的聚类。

顺便说一下，你不必使用分层聚类。 你也可以使用k -means之类的东西，为每个k预先计算一次，然后select具有最高Calinski-Harabasz分数的k 。

让我知道如果你需要更多的参考，我会冲刷我的硬盘一些文件。

Answer 3

查看DBSCANalgorithm。 它基于vector的局部密度进行聚类，即它们之间的距离不能超过某个ε距离，并且可以自动确定聚类的数量。 它也考虑离群点，即ε邻居数不足的点，不能成为一个簇的一部分。 维基百科页面链接到几个实现。