使用未知聚类数的成对距离进行聚类？

Question

我有一组对象{obj1，obj2，obj3，...，objn}。我已经计算了所有可能对之间的成对距离。这些距离存储在一个n*n矩阵M中，其中Mij是obji和objj之间的距离。因此，自然而然地看到M是一个对称矩阵。

现在我希望对这些对象执行无监督聚类。经过一些搜索，我发现谱聚类（Spectral Clustering）可能是一个不错的选择，因为它处理这种成对距离的情况。

然而，在仔细阅读其描述后，我发现它不适用于我的情况，因为它需要作为输入的群集数量。在聚类之前，我不知道群集的数量。必须由算法在执行聚类时找出，就像DBSCAN一样。 考虑到这些，请建议适合我情况的一些聚类方法，其中：

1. 所有成对距离都可用。
2. 群集的数量未知。

- Sibbs Gambling

---

DBSCAN有什么问题吗？它不需要知道簇的数量... - Has QUIT--Anony-Mousse

@Anony-Mousse 我不确定“相对距离”是否适合。 - Sibbs Gambling

你从来没有提到“相对距离”。那是什么？距离总是相对值……事实上，DBSCAN只需要一个二进制的“近”决策，参见广义的DBSCAN。 - Has QUIT--Anony-Mousse

@Anony-Mousse 抱歉！打错了，应该是“成对距离”而不是 - Sibbs Gambling

好的，DBSCAN 显然可以处理这个。DBSCAN 是基于距离而不是坐标的（k-means 需要坐标来计算平均值 - 但是 DBSCAN 没有这个限制）。所以你真的应该尝试一下 DBSCAN。 - Has QUIT--Anony-Mousse

@Anony-Mousse 很酷！我非常感谢你的帮助！我会去尝试一下！ - Sibbs Gambling

Answer 1

有许多可能的聚类方法，没有一种可以被认为是“最好的”，一切都取决于数据，就像往常一样：

• 如果您想使用谱聚类，但不知道聚类数目，请查看自调谱聚类或一些确定聚类数目的方法
• 如果您考虑其他算法，可以尝试：
  • DBSCAN
  • OPTICS
  • 密度链接聚类
  • 层次聚类

- lejlot

---

请注意，它是DBSCAN，而不是DBScan。这是一个缩写，N代表噪声，例如。它并不真正“扫描”数据库，但是使用索引结构可以加速搜索。列出最受欢迎的索引结构可获得+1分。 - Has QUIT--Anony-Mousse

Answer 2

你可以尝试使用多维缩放（MDS）。在使用MDS将类似距离的数据转换为几何图像后，您可以应用常见的聚类方法（如k-means）进行聚类。更多信息请参见这里和这里。

- chaohuang

Answer 3

使用sklearn聚类算法中的metric='precomputed'参数非常容易。您可以使用成对距离矩阵来拟合模型，而不是使用原始特征。

具体步骤如下（如果需要创建成对距离矩阵）：

def my_metric(x, y):
   # implement your distance measure between x and y

def create_pairwise_dist(X_data):
   # create a matrix of pairwised distances between all elements in your X_data
   # for example with sklearn.metrics.pairwise.pairwise_distances
   # or scipy.spatial.distance.pdist
   # or your own code

X_data = <prepare your data matrix of features>
X_dist = create_pairwise_dist(X_data)

# then you can use DBSCAN

dbscan = DBSCAN(eps=1.3, metric='precomputed')
dbscan.fit(X_dist)

- alperovich

Answer 4

需要翻译的内容如下：

要求事先确定聚类数量的聚类方法比试图估计聚类数量的方法更为常见。您可以在Cross Validated上获得更好的答案。然而，最近解决这个问题的一些方法包括：

• 通过间隙统计量估计数据集中的聚类数量，由Tibshirani、Walther和Hastie提出，将聚类内部分散变化与适当参考空值分布的期望变化相比较。这种方法有一个R实现。
• 通过预测强度进行聚类验证，由Tibshirani和Walther提出，将“聚类视为监督分类问题，我们还必须估计‘真实’类标签。产生的‘预测强度’度量评估了可以从数据中预测多少组以及预测的准确程度。”

- Simon

---

谢谢你的回答！也许我没有很清楚地表达问题，实际上“成对距离”在我的情况下更为重要。也就是说，我们可以先忽略未知类别数量的问题。对于“成对距离”的任何其他评论吗？ - Sibbs Gambling

成对距离是衡量物品之间差异的典型方法。在我使用过的所有聚类算法中，都需要每对物品之间的某种差异度量作为输入，但在某些情况下，还有其他合理的差异度量，例如每对物品之间距离的平方。 - Simon

Answer 5

如果您喜欢概率聚类，还有一种迄今为止没有人提出的方法是贝叶斯非参数方法（狄利克雷过程先验是最简单的情况）。您可以使用多项式似然函数进行计数型数据的处理，或者使用多元高斯似然函数来处理连续性数据。

- Ben Allison

Answer 6

你是否考虑过相关聚类？
如果你仔细阅读那篇论文的第2.1节，你会看到对恢复的聚类数量的概率解释。

你需要对M矩阵进行的唯一修改是设置一个阈值，决定哪些距离被认为是“相同的”，哪些距离太大，应该被视为“不同的”。

前面提到的论文的第7.2节涉及到完整矩阵的聚类，其中恢复潜在聚类数量是任务的重要部分。

- Shai

Answer 7

你可以尝试使用分层聚类。它有两种类型：

• 凝聚式或“自下而上”的方法：每个观测值从自己的一个簇开始，当向上移动层次结构时，成对的簇合并为一个。
• 分裂式或“自上而下”的方法：所有观测值都从一个簇开始，随着向下移动层次结构，递归地执行分裂。

- Alexander Kuznetsov