algorithm - 使用距离矩阵聚类对象

Question

假设有几个对象:o1、o2、o3……

还有一个距离/差异矩阵 D，其中包含每对对象的距离。

例如Dij 是 oi 和 oj 之间的距离/相异度。

如何将这些对象聚类成组以便:

每组中每对对象之间的距离小于预定义的阈值。

Answer 1

这是我想做的:

1. 当且仅当距离不超过阈值时，形成两点相连的图。

2. 找到图中最大的点组，使得对于每个组，每个组成员都与其他组成员有一条边。

关键在于步骤 (2) - 它是 the clique problem , 并且是 NP 完全的。

以下是您可以改为执行的操作:

1. 按 complete-linkage clustering 对点进行聚类，其中提到的第二种算法 CLINK 的成本为 O(N²)。

2. 当形成的簇之间的距离超过阈值时停止算法，或者沿着树向下走，使得簇是边高于阈值然后低于阈值的子树。

对于完全链式聚类，两个簇之间的距离是任意两点之间的最大距离，每个点来自一个簇，因此如果将以这种方式形成的距离为 d 的两个簇连接起来形成合并簇，则每对合并簇中的点之间的距离最多为 d。

因为我假设我不仅在时间 O(N²) 内解决了一个 NP 完全问题(这意味着 P = NP，证明/反证 is unlikely to be this easy )，第二种方法不一定提供与第一个集群一样整洁的集群 - 但我还没有彻底考虑这个问题以确切知道权衡是什么。