本文介绍了K-means聚类算法。首先介绍了K-means算法是一种原型聚类算法，其类表示为类中心点，常用欧式距离作为相似性度量。然后由类内紧致准则给出了Kmeans的目标函数及算法流程，指出了Kmeans是一种基于硬划分的聚类算法，同时介绍了一种基于软划分（概率划分）的模糊C均值算法。最后介绍了Kmeans算法的特点，线性复杂度，初始值选取敏感，相似性度量需要结合应用场景。
作者 | 文杰
编辑 | yuquanle
原型聚类-KMeans
KMeans的类表示是聚类中心点，以点来表示类，相似性度量同样可以采用常用的距离度量。根据类紧致性准则定义失真函数为所有样本点到该样本所在类中心的失真程度和最小。
其中表示第个样本所属的类。可以看出Kmeans算法只考虑了类内相似性，没有考虑类间相似性。
对于Kmeans算法的求解采用EM算法，先假设类中心，然后根据相似性度量来划分所有样本点到类中（Kmeans是一种硬划分），根据划分后的样本点重新更新类的类中心，不断的迭代至稳定（类中心不再变化）。
KMeans算法流程
1）随机初始化类中心（选择样本中的点，或者不是样本中的点）
2）重复以下步骤直到收敛
a）遍历所有的样本点，根据相似性度量（欧式距离）将样本划分到最相似性的类
其中表示第个样本所属的类别，值为与类中心距离最近的一类.
b）遍历所有样本，对每一类，更新类中心（该类下所有样本的均值）
至于Kmeans算法的收敛性可以从EM算法角度证明，因为每一次迭代都能保证失真函数不增，所以最终一定会趋于平衡，由于类别数有限，所以有限步收敛。
可以看出在Kmeans中，所有的类划分都是硬划分，下面介绍一点软化分的模糊C均值聚类。失真函数如下：
其中表示第个样本属于类的概率，且，控制失真程度，当时，软化分也等同于硬划分，因为失真函数还是线性的，所以一般取。拉格朗日乘子可求解参数和。
模糊C均值算法流程
1）随机初始化类中心
2）重复以下步骤直到收敛：
a）遍历所有的样本点，更新概率划分矩阵
其中表示第个样本所属的类别。
b）遍历所有样本，对每一类，更新类中心（该类下所有样本的均值）：
Kmeans特点：
- 复杂度为，线性复杂度。
- 需要预先指定聚类个数，失真还是非凸，最小值为局部最小，对初始值选取敏感。
- 硬划分会出现空类，即一个类下面无样本点。
- 相似性度量决定其适合聚类的场景。
代码实战
代码语言：javascript复制KMeans::CenAndDis KMeans::kMeans(const Matrix &x,const int &kNum, const int &Iter)
{
int i = 0, j = 0, k = 0, it = 0;
double dis[MAXK];///记录一个样本到k个类中心的距离，可以采用矩阵动态申请更好，这里默认最多MAXK个类中心
Matrix kmeans;//聚类中心
kmeans=randCent(x, kNum);//随机初始化k个类中心
Matrix xOne;//存储一个样本
Matrix kOne;//存储一个聚类中心样本
Matrix kLabel;//存储每个样本的类别
kLabel.initMatrix(x._row,1,0);
double minDis = MAX;//最小的距离
for(it = 0; it < Iter; it )
{
//根据k个聚类中心划分类标签
for(i = 0; i < x._row; i )
{
xOne = x.getOneRow(i);
minDis = MAX;
for(k = 0; k < kNum; k )
{
kOne = kmeans.getOneRow(k);
dis[k] = distances(xOne,kOne);
if(dis[k] < minDis)
{
kLabel._data[i][0] = k;
minDis = dis[k];
}
}
}
//kmeans清零，当计算类中心采用 =的形式则需要清零，而下面更新kmeans同样是采用 =的形式，因为右边有一项就是kmeans
for(k = 0; k < kNum; k )
{
for(j = 0; j < x._col; j )
{
kmeans._data[k][j] = 0;
}
}
//更新kmeans
for(i = 0; i < x._row; i )
{
k = kLabel._data[i][0];
for(j = 0; j < x._col; j )
{
kmeans._data[k][j] = (kmeans._data[k][j] * i x._data[i][j]) / (i 1);//采用累加方式求均值，该方法增加计算量
//当然也可以把一类的所有样本取出来，求和再取均值，这里没有这样做，而是来一个加一个
}
}
//输出当前次EM后的聚类中心
std::cout<<"--------------------"<<std::endl;
for(k = 0; k < kNum; k )
{
for(j = 0; j < x._col; j )
{
std::cout<< kmeans._data[k][j] <<" ";
}
std::cout<<std::endl;
}
}
/**
将聚类结果保存到结构体中
*/
CenAndDis cendis;
cendis.cen.initMatrix(kNum, x._col, 0);
cendis.dis.initMatrix(x._row, 1, 0);
cendis.cen = kmeans;
///保存所有样本到其类中心的距离到结构体中
for(i = 0; i < x._row; i )
{
k = kLabel._data[i][0];
xOne = x.getOneRow(i);
kOne = kmeans.getOneRow(k);
cendis.dis._data[i][0] = distances(xOne, kOne);
}
//
double sum=0;
for(i = 0; i < x._row; i )
{
sum = cendis.dis._data[i][0];
}
std::cout<< "err=" << sum <<std::endl;
return cendis;
}The End
