假设有几个对象:o1、o2、o3……
还有一个距离/差异矩阵 D,其中包含每对对象的距离。
例如Dij 是 oi 和 oj 之间的距离/相异度。
如何将这些对象聚类成组以便:
每组中每对对象之间的距离小于预定义的阈值。
最佳答案
这是我想做的:
当且仅当距离不超过阈值时,形成两点相连的图。
找到图中最大的点组,使得对于每个组,每个组成员都与其他组成员有一条边。
关键在于步骤 (2) - 它是 the clique problem , 并且是 NP 完全的。
以下是您可以改为执行的操作:
按 complete-linkage clustering 对点进行聚类,其中提到的第二种算法 CLINK 的成本为 O(N²)。
当形成的簇之间的距离超过阈值时停止算法,或者沿着树向下走,使得簇是边高于阈值然后低于阈值的子树。
对于完全链式聚类,两个簇之间的距离是任意两点之间的最大距离,每个点来自一个簇,因此如果将以这种方式形成的距离为 d 的两个簇连接起来形成合并簇,则每对合并簇中的点之间的距离最多为 d。
因为我假设我不仅在时间 O(N²) 内解决了一个 NP 完全问题(这意味着 P = NP,证明/反证 is unlikely to be this easy ),第二种方法不一定提供与第一个集群一样整洁的集群 - 但我还没有彻底考虑这个问题以确切知道权衡是什么。
关于algorithm - 使用距离矩阵聚类对象,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23668456/