一.K均值聚类的定义

K均值聚类是基于样本集合划分的聚类算法，它将样本集合划分为k个子集，即k个类别，样本集合中的每个样本到其所属类别的中心距离最小，且其只能属于一个类别，所以k均值聚类是硬聚类。

二.模型定义

给定样本集合 X=left{ x_{1}，x_{2}，…，x_{n} right} ，其中n为集合中样本的个数，每个样本由一个m维特征向量表示，k均值聚类的目标是将n个样本划分到k个不同的类别中，k<n。用 G=left{ {G_{1},G_{2},…,G_{k}} right} 表示类别集合，每个类别中包含了样本集合X的一个子集，且满足以下条件：

G_{i}cap G_{j}=phi ，bigcup_{i=1}^{k}G_{i}=X ,其中i=1,2,…,k;j =1,2,…,k。

把样本从集合X划分到k个分类过程，就构成了一个多对一的函数，即G = f（X） ，其中 G=left{ {G_{1},G_{2},…,G_{k}} right} ， X=left{ x_{1}，x_{2}，…，x_{n} right} ，所以k均值聚类的模型就是一组从样本到类别的函数（从 Xrightarrow G 有多种划分方法）。

三.确定策略

因为k均值聚类模型是一个从样本到类别的函数，所以k均值聚类的策略就是通过损失最小化原则从这个函数中选择一个最优的分类方法。

1.确定k值的选择方法：

k均值聚类中的类别数k需要预先指定，实践中最优的k值事先是不知道的，通常的解决办法是：

A.首先使用层次聚类的方法，使用不同的k值对样本集合进行预分类;

B.然后对不同k值的分类结果进行评价，聚类结果的质量可以用类的平均直径来评价，通常类别数变小时，平均直径会增加，类别数变大，超过某个值以后，评价直径会不变，而这个值就是最优的k值。

2.确定样本间的距离或相似度计算方法：

k均值聚类通常采用欧氏距离的平方来来作为距离或相似度的测量指标，即： d(x_{i},x_{j})=sum_{k=1}^{m}{(x_{ki}-x_{kj})^{2}}=||x_{i}-x_{j}||^{2}

3.定义损失函数：

K均值聚类方法将样本与其所属类别的中心之间的距离总和定义为损失函数，即： W(C)=sum_{l=1}^{k}{sum_{C(i)=l}^{}{||x_{i}-bar{x}_{l}||^{2}}}

4.基于损失函数，求解不同分类中心的分类损失，将损失最小的分类作为最终分类结果，即 C^{*}=arg min_{C}W(C)=arg min_{C} sum_{l=1}^{k}{sum_{C(i)=l}^{}{||x_{i}-bar{x}_{l}||^{2}}}

四.算法实现

输入：n个样本的集合X，需要划分的类别数k；

输出：样本集合X的k个子集 C^{(k)}

1.初始化：令t=0，从样本集合X中随机的选择k样本点作为初始聚类中心 m^{(0)}=(m_{1}^{(0)}， m_{2}^{(0)}，…， m_{k}^{(0)})

2.对样本进行聚类：计算每个样本点到k个类别中心点的距离，并将其分配到与其距离最近的类别中；

3.计算新的类别的中心：计算当前每个新类别中的样本均值，将其做为新的类别中心;

4.如果如果类别中心结果收敛或满足停止条件，则输出当前聚类结果C^{(k)}，否则t = t+1，返回步骤2继续迭代。