我有一组三维向量。我需要根据欧几里得距离对这些向量进行聚类，使得任何特定簇中的所有向量之间的欧几里得距离都小于一个阈值”T”。
我不知道存在多少个簇。最后，可能会有一些单独的向量存在，因为它们与空间中任何向量的欧几里得距离都不小于”T”，因此不属于任何簇。
这里应该使用哪些现有算法/方法？
回答：
你可以使用层次聚类。这是一种相当基础的方法，因此有很多可用的实现。例如，它包含在Python的scipy中。
例如，请看以下脚本：
import matplotlib.pyplot as pltimport numpyimport scipy.cluster.hierarchy as hcluster# generate 3 clusters of each around 100 points and one orphan pointN=100data = numpy.random.randn(3*N,2)data[:N] += 5data[-N:] += 10data[-1:] -= 20# clusteringthresh = 1.5clusters = hcluster.fclusterdata(data, thresh, criterion="distance")# plottingplt.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()这会产生类似于以下图像的结果。
作为参数给出的阈值是一个距离值，基于此值决定是否将点/簇合并到另一个簇中。也可以指定使用的距离度量方法。
请注意，计算簇内/簇间相似性的方法有很多种，例如，最近点之间的距离，最远点之间的距离，到簇中心的距离等等。scipy的层次聚类模块也支持其中一些方法（单一/完全/平均…链接）。根据你的帖子，我认为你可能想使用完全链接。
请注意，这种方法也允许小（单点）簇的存在，如果它们不满足其他簇的相似性标准，即距离阈值。
有其他算法在处理大量数据点时表现会更好。正如其他回答/评论所建议的，你可能也想看看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库）：
从那个地方复制的图像：
如你所见，每种算法对簇的数量和形状都有一些假设，这些假设需要考虑到。无论是算法隐含的假设，还是通过参数化明确指定的假设。
