聚类是一个NP 完全问题 - 请参阅聚类的一个定义和聚类的另一个定义的证明。

是否P=NP的问题尚未得到解答，但似乎复杂性类别不同。

如果是这样，那么没有多项式时间算法，如 pam 算法可以解决问题。

当面对一个 NP 完全问题时，我们可以通过寻找近似算法来解决它。波纹管的近似比率为2。

Gonzalez, TF (1985)，“集群以最小化最大集群间距离”，理论计算。科学。38, 293-306。

然而，pam 走向不同的方向，它是一种随机贪心算法。因此，它寻找最佳解决方案，但我猜它通常会失败并找到局部最优。

似乎 pam 在难以计算 k-means的常规情况下失败。在幻灯片 24 上，有一个示例对于诸如算法之类的 k-means 来说很难，但 DBSCAN聚类效果很好。

尝试建造一个！

我们需要一个稳定但不是最优的集群分配。因此，中心点成为其集群中的中心点，并且每个对象都被分配到其最近的中心点。但是有一个更好的解决方案。

让我们从简单的开始。一维，每个集群三个点，星号表示集群中心。

Data: 1 2 3     6 7 8
Sol1:   *         *

现在让我们通过将一个对象从中心移开来修改它。

Data:1 2 3     6 7                 15
Sol1:  *         *
Sol2:    *                         *

Sol2 的成本为 2+1+0+3+4+0=10。但很难到达那里。PAM 很可能会卡在第一个解决方案中，其成本为 1+0+1+1+0+8=11。如果没有，您可能需要增加集群的间距，或移动异常值。

上述示例的 R 代码示例：

> pam(c(1:3,6,7,15), k = 2, medoids = c(2,5))$med
     [,1]
[1,]    2
[2,]    7

> pam(c(1:3,6,7,15), k = 2, medoids = c(2,6))$med
     [,1]
[1,]    3
[2,]   15