algorithm - 聚类点数达到全局最小值

Question

对于多个点，例如100个点，每两个点都有一个'连接'(一个数字)，算法的目标是将这些点分成给定数量的簇(比如5个簇)，最小化集群内的总连接数。

---

输入:一个形状为 n * n 的矩阵，matrix[i][j] 描述了点 i 和 j 之间的连接(矩阵应该是对称矩阵)。簇号m。

输出:n 个点的 m 个簇。并且集群内的总连接数被最小化。

T= ∑(C⊆m)∑(i,j⊆C)M_ij

(目标是最小化上面的T)

For example: 5 points with the matrix
    1   2   3   4  5 
1  0.1 0.1 0.3 0.5 0.7
2  0.1 0.1 0.7 0.9 1.1
3  0.3 0.7 0.5 0.1 0.2
4  0.5 0.9 0.1 0.3 0.5
5  0.7 1.1 0.2 0.5 0.1
To split into 2 clusters, the splitting
Cluster 1: {1,2}
Cluster 2: {3,4,5}
has the total internal connection of T = C1 + C2 = M12 + M34 + M35 + M45 = 0.1 + 0.1 + 0.2 + 0.5 = 0.9

The splitting
Cluster 1: {1,3,4}
Cluster 2: {2,5}
Has the total internal connection  T = C1 + C2 = M13 + M14 + M34 + M25 =  0.3 + 0.5 + 0.1 + 1.1 = 2.0

目标是找到最低的内部连接

当 n 和 m 较小时这很容易，只需循环所有可能的情况以找到全局最小值。但是当 n 和 m 变大时，迭代是不可能的。

---

我已经尝试过 Kernighan–Lin 算法来解决这个问题。用随机 split 初始化，然后定义两个行为，将点插入到另一个簇中，并在两个簇中交换两个点，每次都找到能够降低簇内总连接数的行为。应用此行为，然后再次重新计算，直到不再有插入/交换可以降低总连接数。 (贪心算法策略)。

但只能达到局部最小值，初始化不同，结果也不同。是否有解决此问题以达到全局最小值的标准方法？

Answer 1

这个问题被认为是 NP 难的，所以要么你使用局部最优，要么你必须尝试所有 O(k^n) 种可能性。

您可以使用局部最优来限制您的搜索，但不能保证这会有很大帮助。