K-means聚类算法K-means算法是很典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。该算法认为类是由距离靠近的对象组成的,因此把得到紧凑且独立的类作为最终目标。假设数据集合为(x1, x2,…, xn),并且每个xi为d维的向量,K-means聚类的目的是,在给定分类组数k(k ≤ n)值的条件下,将原始数据分成k类: S = {S1, S2, …, Sk}在数值模型上,即对以下表达式求最小值:算法过程:(1)随机选取K个对象作为初始聚类中心;(2)将数据样本集合中的样本按照最小距离原则分配到最邻近聚类;(3)根据聚类的结果,重新计算K个聚类的中心,并作为新的聚类中心;(4)重复步骤2.3直到聚类中心不再变化。数学表达式:n:样本数。k:样本分为k类。rnk:第n个样本点是否属于第k类,属于则rnk=1,不属于则rnk=0。μK:第k个中心点。k-means要做的就是最小化这个函数。迭代的方法:1、固定μK,得到rnk。2、固定rnk,求出最优的μK。求rnk求μKK-means算法性能分析 优点:?1、k-均值算法框架清晰,简单,容易理解。 ?2、对于处理大数据集,这个算法是相对可伸缩和高效的,计算的复杂度为O(NKt),其中N是数据对象的数目,t是迭代的次数。一般来说,K<<N,t<<N。 ?3、当结果类是密集的,而类与类之间区别明显时,它的效果最好。缺点:1、要求必须事先给出要生成的类的数目k,这个k值的选定是非常难以估计。 ?2、对初值敏感,对于不同的初始值,可能会导致不同的聚类结果。 3、对于"噪声"和孤立点数据敏感,少量的该类数据能够对平均值产生极大影响。
全文预览
