K-Means聚类算法

原理简介

对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。

如果用数据表达式表示，假设簇划分为(C1,C2,...Ck)，则我们的目标是最小化平方误差E：

其中μi是簇Ci的均值向量，有时也称为质心，表达式为：

算法描述

1）针对图a所示的无标签点集，想要把他分为两类（即k=2）；

2）随机分配两个点作为每个簇的质心，如图b中的红色和蓝色的‘x’；

3）然后判断全部点到这两个质心的距离，与质心距离较近的标志为同种颜色；

4）根据新划分的簇，重新计算质心，直到达到一定的要求（比如均方误差最小等）；

5）重复c和d的过程，即将所有点的类别标记为距离最近的质心的类别并求新的质心。

算法流程

输入是样本集D={x1,x2,...xm},聚类的簇树k,最大迭代次数N；

输出是簇划分C={C1,C2,...Ck}。

1）从数据集D中随机选择k个样本作为初始的k个质心向量：{μ1,μ2,...,μk}

2）对于n=1,2,...,N

   a. 将簇划分C初始化为Ct=∅(t=1,2...k)

   b. 对于i=1,2...m,计算样本xi和各个质心向量μj(j=1,2,...k)的距离dij，将xi标记最小的为dij所对应的类别λi。此时更新Cλi=Cλi∪{xi}

  c.对于j=1,2,...,k,对Cj中所有的样本点重新计算新的质心：

  d. 如果所有的k个质心向量都没有发生变化，则转到步骤3）

3）输出簇划分C={C1,C2,...Ck}