K-means聚类算法.ppt

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 求K,K-means算法性能分析 优点： 1、k-均值算法框架清晰，简单，容易理解。 2、对于处理大数据集，这个算法是相对可伸缩和高效的，计算的复杂度为O(NKt)，其中N是数据对象的数目，t是迭代的次数。一般来说，KN，tN 。 3、当结果类是密集的，而类与类之间区别明显时，它的效果最好。,缺点： 1、要求必须事先给出要生成的类的数目k，这个k值的选定是非常难以估计。 2、对初值敏感，对于不同的初始值，可能会导致不同的聚类结果。 3、对于“噪声“和孤立点数据敏感，少量的该类数据能够对平均值产生极大影响。,K-means算法变体,（一）k-medoids算法（K-中心点算法） 不采用聚类中对象的平均值作为参照点，而是选用聚类中位置最中心的对象，即中心点（medoid）作为参照点。,K-中心点算法思想： 首先随机选择k个对象作为中心，把每 个对象分配给离它最近的中心。 然后随机地选择一个非中心对象替换中心对象，计算分配后的距离改进量。聚类的过程就是不断迭代，进行中心对象和非中心对象的反复替换过程，直到目标函数不再有改进为止。,K- medoids算法流程如下： 1、任意选取K个对象作为初始中心点（O1,O2,OiOk）。 2、将余下的对象分到各个类中去（根据与中心点最相近的原则）； 3、对于每个类（Oi）中，顺序选取一个Or，计算用Or代替Oi后的消耗E（Or）。选择E最小的那个Or来代替Oi。这样K个中心点就改变了。,其中：p是空间中的样本点， oj是类簇 cj 的中心点。 4、重复2、3步直到K个medoids固定下来。,K-means算法与K- medoids算法结果对比：,K-means算法变体,（二）K-means+算法 使用K-means算法时，我们可以在输入的数据集中随机的选择k个点作为初始的聚类中心，但是随机选择初始点可能会造成聚类的结果和数据的实际分布相差很大。,不同初始点，结果不同。,k-means+算法选择初始聚类中心的基本思想是：初始的聚类中心之间的相互距离要尽可能的远。 1、从输入的数据点集合中随机选择一个点作为第一个聚类中心。 2、对于数据集中的每一个点x，计算它与最近聚类中心的距离D(x)。 3、选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大。,对于每个点，我们都计算其和最近的一个聚类中心的距离D(x)并保存在一个数组里，然后把这些距离加起来得到Sum(D(x)。再取一个随机值Random(0 Random Sum)然后用Random -= D(x)，直到其=0，此时的点就是下一个聚类中心。 4、重复2和3直到k个聚类中心被选出来,K-means算法与k-means+算法选取初始点对比：,K-means k-means+,K-means算法变体,（三）Fuzzy C-Means（模糊C均值算法FCM） 是用隶属度确定每个数据点属于某个聚类的程度的一种聚类算法。 隶属矩阵U允许有取值在0-1间的元素。不过，加上归一化规定，一个数据点的隶属度的和总等于1：,把n个元素xi（i=1,2,n）分为c个模糊组， 目标函数： 其中，m是大于1的实数，加权实数。uij 是xi属于类别j隶属度，cj是类j的聚类中心。,算法步骤： 1、用值在0，1间的随机数初始化隶属矩阵U，使其满足下面的约束条件： 2、计算c个聚类中心ci，i=1,c。,3、更新隶属度U矩阵。 4、算法停止条件： 其中0 1。,K-means算法和Fuzzy C-Means算法结果对比：,谢谢！,