Kmeans聚类算法详解

输入：样本集 D = { x 1 , x 2 , x 3 , . . . , x m } D=\left \{ x_{1},x_{2},x_{3},...,x_{m} \right \} D={x1​,x2​,x3​,...,xm​}；聚类簇数k.
过程：
1：从D中随机选择k个样本作为初始均值向量 { μ 1 , μ 2 , μ 3 , . . . , μ k } \left \{ \mu _{1},\mu _{2},\mu _{3},...,\mu _{k} \right \} {μ1​,μ2​,μ3​,...,μk​}
2：repeat
3： 令 C i = ∅ ( 1 ⩽ i ⩽ k ) C_{i}=\varnothing (1\leqslant i\leqslant k) Ci​=∅(1⩽i⩽k)
4： for j=1,2,…,m do
5： 计算样本 x j x_{j} xj​与各均值向量 μ i ( 1 ⩽ i ⩽ k ) \mu_{i}(1\leqslant i\leqslant k) μi​(1⩽i⩽k)的距离： d j i = ∥ x j − μ i ∥ 2 d_{ji}=\left \| x_{j}-\mu_{i} \right \|_{2} dji​=∥xj​−μi​∥2​;
6： 根据距离最近的均值向量确定 x j x_{j} xj​的簇标记： λ j = a r g m i n i ∈ { 1 , 2 , 3 , . . . , k } d j i \lambda _{j}=arg min_{i\in \left \{ 1,2,3,...,k \right \}}d_{ji} λj​=argmini∈{1,2,3,...,k}​dji​；
7： 将样本 x j x_{j} xj​划入相应的簇： C λ j = C λ j ∪ { x j } ； C_{\lambda_{j}}=C_{\lambda_{j}}\cup \left \{ x_{j} \right \}； Cλj​​=Cλj​​∪{xj​}；
8： end for
9： for i=1,2,…,k do
10: 计算新均值向量： μ i ′ = 1 ∣ C i ∣ ∑ x ∈ C i x \mu_{i}^{'}=\frac{1}{\left | C_{i} \right |}\sum _{x\in C_{i}}x μi′​=∣Ci​∣1​∑x∈Ci​​x;
11： if μ i ′ ≠ μ i \mu_{i}^{'}\neq \mu_{i} μi′​​=μi​ then
12： 将当前均值向量 μ i \mu_{i} μi​更新为 μ i ′ \mu_{i}^{'} μi′​
13： else
14： 保持当前均值不变
15： end if
16： end for
17：until 当前均值向量均未更新
输出：簇划分 C = { C 1 , C 2 , . . . , C k } C=\left \{ C_{1} ,C_{2},...,C_{k} \right \} C={C1​,C2​,...,Ck​}