MATLAB 中的 K 均值算法 - 解释簇标签分配步骤

Question

我有一个来自 class 的 Matlab 代码，其中教授使用此代码执行将每个数据点分配给最近的集群的步骤，其中 c 是质心矩阵，x 是数据矩阵。

  % norm squared of the centroids; 
  c2 = sum(c.^2, 1);  

  % For each data point x, computer min_j  -2 * x' * c_j + c_j^2;
  % Note that here is implemented as max, so the difference is negated.
  tmpdiff = bsxfun(@minus, 2*x'*c, c2); 
  [val, labels] = max(tmpdiff, [], 2);

我不确定这如何等同于通过

完成集群分配的这一步的算法定义

% For every centroid j and for every data point x_i
labels(i) = `argmin||x_i - c_j||^2`

任何人都可以向我解释这是如何工作的，基本上是如何计算

min_j  -2 * x' * c_j + c_j^2

等同于

 argmin||x_i - c_j||^2

Answer 1

如果我们有一个三角形，其边长为a, b, c，那么我们知道（来自 law of cosines）

a^2=c^2+b^2-2bc*cos(alpha)

其中 alpha 是尺寸为 b 的边与尺寸为 c 的边之间的角度。

现在，考虑由三个顶点 x、c_j 和 O（R^n 的原点）构成的三角形。写 theta x 和 c 之间的角度，我们有

 argmin_j||x-c_j||^2
 =argmin_j (||x||^2+||c_j||^2 - 2*||x||* ||c_j|| * cos(theta)  )

等于

 argmin_j(||x||^2 + ||c||^2 - 2x^t c_j)

现在，记住 x 在这个最小化中是常数，所以最后一个等式正好等于

argmin_j(||c_j||^2 - 2 x^t c_j)

这是您在代码中最小化的等式。

MATLAB 中的 K 均值算法 - 解释簇标签分配步骤

K Means Algorithm in MATLAB - Explain the Cluster Label Assignment Step

matlab

k-means