聚类算法是在没有给定标签和样本值的前提下进行数据划分,是典型的无监督学习(unsupervised learning)算法。聚类试图将数据集中的样本划分成若干个不相交的子集,称为“簇”,或“类”。一个好的样本划分肯定是簇内的样本相似度高,而簇与簇之间的样本相似度低。
基于原型的聚类
簇是对象的集合,其中每个对象到定义该簇的原型的距离比其他簇的原型距离更近,例如在下面的k-means算法中,原型就是簇的质心。
1.k-means算法
k-means算法把数据集划分为k个簇,划分依据是簇的每一个样本点到质心(均值)的最小化平方误差和,即欧氏距离。欧氏距离越小,则代表这一个簇的紧密程度越大,簇内的样本相似度越高。
给定样本集D={x1,x2,...,xm}D={x1,x2,...,xm},k-means算法得到的簇划分C={C1,C2,...,Ck}C={C1,C2,...,Ck}最小化平方误差
E=∑i=1k∑x∈Ci||x−μi||22E=∑i=1k∑x∈Ci||x−μi||22
其中μi=1|Ci|∑x∈Cixμi=1|Ci|∑x∈Cix 为簇CiCi的均值向量
但直接求解欧氏距离最小值并不容易,因此采用迭代求解的方法。1.首先随机选取k个质心,遍历每一个样本点,把样本点归入距它最近的质心所代表的簇中。
2.重新计算质心位置,即当前簇中的样本点的均值。 3.重复以上两步,直到算法收敛(更新不再产生划分变动),或者达到停止条件。
k值需要预先指定,而很多情况下k值难以确定,这是k-means的一个缺陷。
k-means的迭代过程本质上是坐标上升的过程。k-means是必定会收敛的,但是和梯度下降一样,只能保证收敛到局部最优,而不能保证收敛到到全局最优。因此初始质心的选择对算法的结果影响十分巨大。
坐标上升法每次通过更新函数中的一维,把其他维的参数看成常量,迭代直到当前维度收敛,再通过多次的迭代计算其他维度以达到优化函数的目的。
因为k-means算法是求均方误差,因此对于一些偏差较大的噪声点非常敏感,因此在k-means基础上可以做适当优化。
K-medoids算法就是一种优化算法,它和k-means唯一不同之处是:k-medoids算法用类中最靠近中心的一个样本点来代表该聚类,而k-means算法用质心来代表聚类。可以减少噪声点带来的影响。
二分K均值法也是一种优化算法,二分K均值法初始时将所有点看成一个簇,在簇的数量小于K的时候进行迭代,算法的核心是选择一个簇一分为二,这里一分为二的方法还是K均值法,只不过K变成了2。二分K均值依次计算每个簇一分为二后新的总平方误差,选择划分后总体平方误差最小的簇进行划分。这样就尽可能避免了k-means落入局部最优的情况。
2.学习向量量化(Learning Vector Quantization)
学习向量量化(LVQ)也是试图找到一组原型来刻画聚类结构,但与k-means不同的是,LVQ的样本带有类别标记。
给定样本集D={(x1,y1),(x2,y2),...,(xm,ym)}D={(x1,y1),(x2,y2),...,(xm,ym)},每个样本xjxj是一个n维向量,yjyj是类别标记,LVQ的目标是学得一组n维原型量{p1,p2,...,pq}{p1,p2,...,pq},每一个原型向量代表一个簇的原型。原型向量的簇标记为ti∈γti∈γ
同样,LVQ也是采用迭代求解的方法。