我有一大组 3 维向量。我需要根据欧几里得距离对它们进行聚类，以使任何特定聚类中的所有向量彼此之间的欧几里得距离小于阈值“T”。
我不知道存在多少个集群。最后，可能存在不属于任何集群的单个向量，因为它的欧几里德距离与空间中的任何向量都不小于“T”。
这里应该使用哪些现有的算法/方法？
问问题
55141 次
6 回答
84
您可以使用层次聚类。这是一种相当基本的方法，因此有很多可用的实现。例如，它包含在 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 库）：
从那个地方复制的图像：
如您所见，每种算法都对需要考虑的集群的数量和形状做出了一些假设。无论是算法强加的隐含假设还是参数化指定的显式假设。
于 2012-04-13T08:12:55.783 回答
23
moooeeeep 的答案建议使用层次聚类。我想详细说明如何选择聚类的阈值。
一种方法是根据不同的阈值t1、t2、t3 ……计算聚类，然后计算聚类“质量”的度量。前提是具有最佳聚类数的聚类质量将具有质量度量的最大值。
我过去使用的一个优质指标的例子是 Calinski-Harabasz。简而言之：您计算平均集群间距离并将它们除以集群内距离。最佳聚类分配将具有彼此分离最多的聚类，以及“最紧密”的聚类。
顺便说一句，您不必使用层次聚类。您还可以使用类似k的方法，为每个k预先计算它，然后选择具有最高 Calinski-Harabasz 分数的k。
如果您需要更多参考资料，请告诉我，我会在硬盘上搜索一些论文。
于 2012-04-13T17:45:37.227 回答
12
查看DBSCAN算法。它基于向量的局部密度进行聚类，即它们之间的距离不能超过某个ε ，并且可以自动确定聚类的数量。它还考虑离群值，即ε-邻居数量不足的点，不属于集群的一部分。维基百科页面链接到一些实现。
于 2012-04-13T09:50:15.020 回答
0
使用OPTICS，它适用于大型数据集。
OPTICS: Ordering Points To identify the Clustering Structure 与 DBSCAN 密切相关，找到高密度的核心样本并从中扩展集群1。与 DBSCAN 不同，它为可变邻域半径保持集群层次结构。比 DBSCAN 的当前 sklearn 实现更适合在大型数据集上使用
from sklearn.cluster import OPTICS
db = OPTICS(eps=3, min_samples=30).fit(X)
根据您的要求微调eps、min_samples 。
于 2019-03-15T12:00:36.593 回答
0
您可能没有解决方案：当任何两个不同的输入数据点之间的距离总是大于 T 时，就会出现这种情况。如果您只想从输入数据中计算聚类的数量，您可以查看 MCG，一种层次聚类具有自动停止标准的方法：请参阅https://hal.archives-ouvertes.fr/hal-02124947/document上的免费研讨会论文（包含参考书目）。
于 2020-09-15T07:45:31.710 回答
0
我想通过使用层次聚类来添加到 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，连接数将是您想要的集群数。所以在这里我为 4 个集群选择阈值 = 1。
threshold = 1
clusters_list = hierarchy.fcluster(ward_array, threshold, criterion="distance")
print("Clustering list: {}".format(clusters_list))
现在 cluster_list 中的每个值都将是 ori_array 中对应点的指定 cluster-id。
于 2020-11-11T06:53:49.700 回答