k-means聚类分析

时间:2023-02-09 16:48:21

 k-means算法是machine learning领域内比较常用的算法之一。

     首先,我们先来讲下该算法的流程(摘自百度百科):

     首先从n个数据对象任意选择 k 个对象作为初始聚类中心;而对于所剩下其它对象,则根据它们与这些聚类中心的相似度(距离),分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然 后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值);不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。

      以上就是k-means的算法流程了,算法的流程其实还是比较简单的,今天我着重从数学的角度来讲一下我所理解的k-means聚类算法。

      假设我们有N个样本数据集{x1,...,xN},变量x的维数为D维,我们现在要将这些数据集分成k类(注意k已知变量)。我们将问题进行转化,可以构造这样的等式,引进D维向量μk,作为每个类的中心,我们所希望的是每个数据点与它最近的类中心的距离(这里采用平方和)最小。

      我们用数学语言来描述:

(1)

      rnk:rnk ∈ {0, 1},是一个二分变量,描述的是第n个数据点是否属于第k类,例如:rnk=1,表示第n个数据点属于k类;rnk=0,表示第n个数据点不属于k类。

      J:为目标函数,描述的是每个数据点与它类中心的平方和。

      所以整个问题就变为我们希望找到最佳{rnk},{μk},使目标函数J最小。而我们通常是通过迭代程序,连续优化变量rnk,μk。在每一步迭代程序中,我们分成两步来考虑:

     1 固定住类中心μk,也就是已知值,J是关于变量rnk的目标函数。我们要使J函数最小,只要让第n个数据点属于离当前最近的类中心所属类就行。用数学语言来表达就是:

    

     2 固定住rnk,J是关于变量μk的目标函数,我们要是J函数最小,我们对函数J进行对μk的求导,令其等于0,即:

 

然后我们直接可以根据上面等式求解μk:

 

 从等式的数学意义来看,μk就是该类数据的均值,

       然后再将{rnk},{μk}进行下一次迭代,直至整个程序收敛停止。但是要注意我们在进行全局最小化目标函数J的过程中,往往会陷入局部收敛,至于k-means的收敛性我在就不具体讨论了。最终求得的rnk,表达的也就是第n个数据点属于哪一类,即完成了聚类操作。

      需要注意的是一开始我们并不知道这k类的类中心μk值,一般的我们采取随机在样本数据中选取k个数作为类的中心,每个数据点只能属于一类,而不能属于多个类。在一般情况下,我们横量数据点与类中心的距离(或者说是数据点与类中心点的不相似性)是采用欧式距离,横量的方法也可以采用其他方法,那么我们将k-means写成一般化形式就为:

函数V()代表的就是数据点与类中心的距离。

      其实,如果我们更深入地理解k-means算法,其实应该算是mean-shift的一种特例。k-means算法在每次迭代过程中,类中心收敛的过程其实就是相当与mean-shift往高斯山峰自动移动的过程。