第10.3节 Kmeans聚类算法求解
各位朋友大家好，欢迎来到月来客栈，我是掌柜空字符。
本期推送内容目录如下，如果本期内容对你有所帮助，欢迎点赞、转发支持掌柜！
10.3 -means算法求解
到目前为止，相信各位读者已经对-means聚类算法的过程有了一个大致的了解，但是我们应该如何从数学的角度来对其进行描述呢？正如笔者在介绍线性回归时所讲解的那样，对于聚类算法来讲我们同样应该找到一个目标函数来对聚类结果的好坏进行刻画。在上面笔者介绍过，聚类的本质可被看成不同样本间相似度比较的过程，把相似度较高的样本点放到一个簇中，而把相似度较低的样本点放到不同的簇中。既然如此，应该怎么来衡量样本间的相似度呢？一种最常见的做法当然是计算两个样本间的欧氏距离，即两个样本点离得越近就代表着两者间的相似度越高，并且这也是-means聚类算法中的衡量标准。
因此，根据这样的准则就可以将-means聚类算法的目标函数定义为所有样本点到其对应簇中心距离的总和，以此来刻画聚类结果的好坏程度。
10.3.1 -means算法目标函数
如图10-3所示，图(a)和图(b)为同一数据集的两种不同聚类结果，其中同种颜色表示聚类后被划分到同一个簇中，黑色圆点为聚类后的簇中心。从可视化结果来看，图(a)中的聚类结果肯定好于图(b)中的聚类结果。也就是说，可以通过最小化目标函数来得到最优解。
设为一个含有n个样本的数据集，其中第个样本表示为，为样本特征的数量。样本分配矩阵是一个个的0-1矩阵（只含有0和1），表示第个样本被分到第个簇中。为个簇中心向量，其中为第个簇中心，则-means聚类算法的目标函数可以写为
服从于约束条件
虽然式(10.1)看起来稍微有点复杂，但是其表示的含义就是求各个样本点到其对应簇中心的距离和。由于一个数据集有多个簇，每个簇中有多个样本，每个样本又有多个维度，因此式(10.1)中就存在了3个求和符号。其次，笔者再以图10-3为例来简单讲一下分配矩阵。由图10-3(a)可知，数据集中一共有两个簇，并且假设前5个样本为一个簇，后5个样本为一个簇，则其对应的分配矩阵为
10.3.2 求解簇中心矩阵
同SVM求解一样，对于目标函数(10.1)的求解依旧借助于拉格朗日乘数法。由目标函数(10.1)可知，这里一共需要求解的未知参数包括两个：簇中心矩阵和簇分配矩阵。