机器算法验证 - 质心匹配问题 - 吾爱随笔录

质心匹配问题

机器算法验证聚类算法

2022-04-09 18:22:48

对于数据集，我们有黄金标准质心说。现在，如果我们用输入上运行 k-means 算法，我们得到 k-means 质心。 $D$ $c_1, c_2, \cdots, c_n$ $D$ $n$ $k_1, k_2, \cdots, k_n$

我只是想知道，是否有任何算法/启发式来匹配和之间的质心，其中和之间的一对一映射） $k_i$ $c_j$ $i, j= 1, \cdots, n$ $k$ $c$

我试图计算和，并将与匹配，其中它们之间的距离最小。但在这种情况下和被分配给，我们不需要。 $k_p$ $c_j,\; j= 1, \cdots, n$ $k_p$ $c_r$ $k_p$ $k_q$ $c_r$

3个回答

因为 K-means 最小化方差，所以一个好的标准是最小化点对之间的距离平方和。

这是一个积分 (0/1) 线性规划。具体来说，配对可以由矩阵指定，其中如果与配对，。我们力求最小化 $\Lambda = (\lambda_{ij})$ $\lambda_{ij} = 1$ $c_i$ $k_j$ $\lambda_{ij}=0$

\sum_{i, j} λ_{i j} | c_{i} - k_{j} |^{2}

$\sum_{i,j}\lambda_{ij}|c_i - k_j|^2$

受约束（强制一对一配对）

\sum_{j} λ_{i j} = 1

$\sum_{j}\lambda_{ij}=1$

\sum_{i} λ_{i j} = 1

$\sum_{i}\lambda_{ij}=1$

λ_{i j} \in {0, 1} .

$\lambda_{ij} \in\{0,1\}.$

只要质心不超过几百个，这个问题很快就解决了。（设置问题所涉及的矩阵将很快耗尽具有数百个质心的 RAM，因为它们按比例缩放 $O(n^3)$ ，然后你可能不得不对编程有点大惊小怪。）例如，Mathematica 8 的 `LinearProgramming' 函数不需要可测量的时间，少于 $n=20$ 质心，以 400 个质心升级到大约 5 秒。

解决方案 20 分

通过线段来显示配对，该图描绘了一个最优解 $n=20$ 双变量正态质心 $c_i$ 和独立的双变量正态 K 均值解 $k_i$ .

您要解决的问题是最小成本匹配问题，特别是最小化功能的问题

$F(\pi) = \sum_i \|c_i - k_{\pi(i)}\|^2$

其中是中的所有排列。 $\pi$ $S_n$

这可以通过匈牙利算法（这是一种变相的原始对偶方法）来解决，并且需要时间。 $n^3$

听起来您可能需要考虑使用/编写能量函数。更多信息：http ://en.wikipedia.org/wiki/Optimization_%28mathematics%29#Multi-objective_optimization

我想如果您的 k 质心数量“小”，您可以为所有 ck 配对运行距离函数，并选择最小化总距离的集合作为“最佳”解决方案。
希望有帮助 -
佩里

其它你可能感兴趣的问题

上一篇多项选择投票中的均值差异下一篇绘制具有相同 z 级别的多个 binhex