K-means聚类算法.ppt
- 文档编号:13483501
- 上传时间:2023-06-14
- 格式:PPT
- 页数:36
- 大小:4.18MB
K-means聚类算法.ppt
《K-means聚类算法.ppt》由会员分享,可在线阅读,更多相关《K-means聚类算法.ppt(36页珍藏版)》请在冰点文库上搜索。
K-means聚类算法,聚类,基本思想:
物以类聚,人以群分聚类就是把数据按照相似性归纳成若干类别,同一类中的数据彼此相似,不同类中的数据相异。
聚类分析可以建立宏观的概念,发现数据的分布模式,以及可能的数据属性之间的相互关系,聚类基本概念:
将数据对象集划分成事先未知的分组或类别聚类的原则:
类内相似度高,类间相似度低相似度为某种距离函数D(xi,xj)聚类既可以作独立分析工具考察数据分布结构,也可作其他分析方法的预处理步骤缺点:
对聚类结果的评价一般都是主观的基本分类将数据对象集划分成事先未知的分组或类别,K-means算法:
基于距离的聚类算法,采用距离作为相似性的评价指标,两个对象的距离越近,其相似度就越大。
认为类是由距离靠近的对象组成的,因此把得到紧凑且独立的类作为最终目标。
聚类示意,基于欧氏距离的三维空间中的聚类基于质心的聚类算法,A1,A2,B1,x,y,z,个人客户分群示例,个人客户分群,分群要求做到组间差异化最大组内相似性最大,假设数据集合为(x1,x2,xn),并且每个样本xi为d维的向量,K-means聚类目标,在给定分类组数k(kn)值的条件下,将原始数据分成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、算法框架清晰,简单,容易理解;2、对于处理大数据集,这个算法是相对可伸缩和高效的,计算的复杂度为O(NKt),其中N是数据对象的数目,t是迭代的次数;3、当结果类是密集的,而类与类之间区别明显时,它的效果最好。
缺点:
1、必须事先给出类的数目K,K常难以估计;2、对初值敏感,不同始值,可能会导致不同的聚类结果;3、对于“噪声”和孤立点数据敏感,;4、不能对任意形状的数据进行聚类。
K-means无法聚类数据形状,通过修改聚类公式,K-means能聚类的数据形状,importmatplotlib.pyplotaspltimportnumpyasnpimportpandasaspdfromsklearn.clusterimportKmeansX=loaddata()#userdefinedfunctionkmeans=KMeans(n_clusters=4)kmeans.fit(X)y_kmeans=kmeans.predict(X),K-means算法变种,
(一)k-medoids算法(K-中心点算法)不采用聚类中对象的平均值作为参照点,而是选用聚类中位置最中心的对象,即中心点(medoid)作为参照点。
K-medoids算法思想:
首先随机选择k个对象作为中心,把每个对象分配给离它最近的中心。
然后随机地选择一个非中心对象替换中心对象,计算分配后的距离改进量。
聚类的过程就是不断迭代,进行中心对象和非中心对象的反复替换过程,直到目标函数不再有改进为止。
K-medoids算法流程如下:
1、任意选取K个对象作为初始中心点(O1,O2,Oi,Ok)。
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(0RandomSum)然后用Random-=D(x),直到其=0,此时的点就是下一个聚类中心。
4、重复2和3直到k个聚类中心被选出来,K-means算法与k-means+算法选取初始点对比:
K-meansk-means+,K-means算法变体,(三)FuzzyC-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个聚类中心cj,j=1,c。
3、更新隶属度U矩阵。
4、算法停止条件:
其中01。
K-means算法和FuzzyC-Means算法结果对比:
数据挖掘十大经典算法,数据挖掘国际会议ICDM在2006年12月评选出来数据挖掘领域的十大经典算法,C4.5,K-means,SVM,TheApriori,EM,Page-Rank,Ada-Boost,KNN,NaveBayes,CART,谢谢!
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- means 算法