algorithm - 聚类数量未知的无监督聚类

Question

我有一大组 3 维向量。我需要根据欧氏距离对它们进行聚类，以便任何特定聚类中的所有向量彼此之间的欧氏距离小于阈值“T”。

我不知道有多少集群存在。最后，可能存在不属于任何簇的单个向量，因为它与空间中任何向量的欧氏距离不小于“T”。

此处应使用哪些现有算法/方法？

Answer 1

您可以使用 hierarchical clustering .这是一种相当基本的方法，因此有许多可用的实现。例如，它包含在 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 层次聚类模块 (single/complete/average... linkage) 也支持其中一些方法。根据你的帖子，我想你会想使用 complete 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

从那个地方复制的图片:

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