K均值改进聚类PPT课件

.,1,基于取样思想的改进C均值聚类,.,2,目录,C-均值算法的缺陷分析改进C均值算法的分析matlab编程所用到函数介绍matlab算法程序介绍结果分析结论,.,3,一.C-均值算法的缺陷分析,1.聚类个数C需要预先给定有的算法是通过类的自动合并和分裂，得到较为合理的类型数目C，例如用ISODATA算法，得到初始的聚类数目C。然后运用C均值算法进行聚类分析。聚类数目C值的确定也可根据方差分析理论，F统计量来确定最佳分类数，并应用模糊划分嫡来验证最佳分类数的正确性。,.,4,一.C-均值算法的缺陷分析,2.算法对初值敏感在C-means算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果，这也成为C-means算法的一个主要问题。对于该问题的解决，许多算法采用遗传算法进行初始化，以内部聚类准则作为评价指标。,.,5,一.C-均值算法的缺陷分析,3.局部极小解的问题聚类问题本质是一个优化问题的，这就是通过一种迭代运算使得系统的目标函数达到一个极小值。但是这个目标函数在状态空间中不是一个非凸函数，它有许多极小值，其中只有一个是全局极小值，而其他的都是局部极小值。求解的目标是得到全局最小值，而不是其它的局部极小值。这也是目前一些聚类算法，经常会遇到的总是,常会在求解过程中陷入局部最优，而得不到全局最优。,.,6,二.改进C均值算法的分析,在K均值算法中，选择不同的初始聚类中心会产生不同的聚类结果且有不同的准确率，此方法就是如何找到与数据在空间分布上尽可能一致的初始聚类中心。对数据进行划分，最根本的目的是使一个聚类中的对象是相似的，而不同聚类中的对象是不相似的。如果用距离表示对象之间的相似性程度，相似对象之间的距离比不相似对象之间的距离要小。如果能够寻找到K个初始中心，它们分别代表了相似程度较大的数据集合，那么就找到了与数据在空间分布上相一致的初始聚类中心。,.,7,二.改进C均值算法的分析,目前，初始聚类中心选取的方法有很多种，在此仅介绍两种：1.基于最小距离的初始聚类中心选取法(1)计算数据对象两两之间的距离;(2)找出距离最近的两个数据对象,形成一个数据对象集合A1,并将它们从总的数据集合U中删除;(3)计算A1中每一个数据对象与数据对象集合U中每一个样本的距离,找出在U中与A1中最近的数据对象,将它并入集合A1并从U中删除,直到A1中的数据对象个数到达一定阈值;(4)再从U中找到样本两两间距离最近的两个数据对象构成A2,重复上面的过程,直到形成k个对象集合;(5)最后对k个对象集合分别进行算术平均,形成k个初始聚类中心。,.,8,二.改进C均值算法的分析,2.基于取样思想的改进C均值算法基于以上对C均值算法的分析，我提出自己的改进算法。首先采用对所给的样本数据进行K-means算法进行聚类，产生一组聚类中心。然后将这组聚类中心作为初始聚类中心，在采用n次K-means算法进行聚类。然后判断两次聚类得到的中心是否一致，直到一致则结束聚类。在此，也可以在第一步中，对样本数据采用K-means算法进行n次聚类运算，每次产生一组聚类中心，对n组聚类中心进行算术平均，从而得到c组初始聚类中心。,.,9,三.matlab编程所用到函数介绍,1.IDX,C=kmeans(data,k)IDX：聚类结果C：聚类中心k：分类个数data：要聚类的数据集合，每一行为一个样本。,.,10,三.matlab编程所用到函数介绍,mean函数函数原型：mean(A，dim)参数：A待求解均值的矩阵dim默认dim=1，就会求每一列的均值；当dim=2时，就会求每一行的均值。,.,11,四.matlab算法程序介绍,程序主要包括两部分，一个聚类中心的提取，另一个是重新进行聚类划分。%计算初始聚类中心clc;clear;%使用c-均值得到初始分类functionyy=Kmeans2()；data=xlsread(E:模式识别数据data)%载入数据IDX,C=kmeans(data,4);Cy=1:59;z=data,IDX;x=z;y;%初始聚类中心的提取%kmeans初始算得的聚类中心在矩阵C中x1=;x2=;x3=;x4=;fori=1:59,.,12,四.matlab算法程序介绍,ifx(4,i)=1x1=x1,x(:,i);elseifx(4,i)=2x2=x2,x(:,i);elseifx(4,i)=3x3=x3,x(:,i);elsex(4,i)=4x4=x4,x(:,i);endendformatshortgx1=C(1,:);x2=C(2,:);x3=C(3,:);x4=C(4,:);,.,13,四.matlab算法程序介绍,x=x(1:3,:);x(5,:);xx=mean(x1,2),mean(x2,2),mean(x3,2),mean(x4,2);xxx=ones(3,4);j=0;whilexx=xxxxx=xxx;%迭代求解聚类中心d1=;d2=;d3=;d4=;fori=1:size(z,2)d1=d1,round(1000*sum(x(1:3,i)-mean(x1,2).2)/1000;d2=d2,round(1000*sum(x(1:3,i)-mean(x2,2).2)/1000;d3=d3,round(1000*sum(x(1:3,i)-mean(x3,2).2)/1000;d4=d4,round(1000*sum(x(1:3,i)-mean(x4,2).2)/1000;endd1,d2,d3,d4%d1,d2,d3,d4%这四组数据分别存储了49个点分别与四个聚类中心的距离,.,14,四.matlab算法程序介绍,ww1=;ww2=;ww3=;ww4=;%取与聚类中心最近的那个点，并将其归入相应类fori=1:size(z,2)ifmin(d1(i),d2(i),d3(i),d4(i)=d1(i)ww1=ww1,x(:,i);elseifmin(d1(i),d2(i),d3(i),d4(i)=d2(i)ww2=ww2,x(:,i);elseifmin(d1(i),d2(i),d3(i),d4(i)=d3(i)ww3=ww3,x(:,i);elseww4=ww4,x(:,i);endendx1=ww1(1:3,:);x2=ww2(1:3,:);x3=ww3(1:3,:);,.,15,四.matlab算法程序介绍,x4=ww4(1:3,:);xxx=mean(x1,2),mean(x2,2),mean(x3,2),mean(x4,2)yyy=xxxendww1ww2ww3ww4plot3(ww1(1,:),ww1(2,:),ww1(3,:),s,ww2(1,:),ww2(2,:),ww2(3,:),*,ww3(1,:),ww3(2,:),ww3(3,:),o,ww4(1,:),ww4(2,:),ww4(3,:),*)%绘制三维图grid,.,16,五.结果分析,C=1.0e+03*1.21061.87802.95792.33273.07891.07590.30103.22282.25021.73321.73561.9762ww1=1至6列864.45877.881418.81449.6867.811494.61647.32031.71775.91641.62334.72072.62665.93071.22772.93405.12535.12550.546162532397至10列1243.11495.21125.21269.11814.11957.41594.41910.73441.134982937.7270242535456,.,17,五.结果分析,ww2=1至6列2352.12297.32092.62205.42949.22802.925573340.13177.23243.73244.43017.11411.5535.62584.321202.7662.421985814151819227至12列2063.523752271.92336.32144.52201.93199.8334734832640.32501.63196.21257.2975.31946.71599.6591.51935.5324353643454913列2232.43077.91298.950,.,18,五.结果分析,ww3=1至6列373.3222.85401.3363.34104.8499.853087.13059.53259.93477.93389.83305.82429.52002.321512462.92421.82196.22591012137至12列172.78341.59291.02237.63460.69198.833084.53076.63095.73077.83274.83250.42328.72438.62088.9225221732445.123272829343813至16列354426.31343.0724.223300.13105.33271.73447.32373.62057.82036.9214544464855,.,19,五.结果分析,ww4=1至6列1739.91756.81803.61571.21845.61692.61675.216521583.117311918.81867.5239615152163.11735.32226.521091371117207至12列1680.71651.51702.81877.91831.51783.61575.81713.31639.818611713.115981725.11570.42068.71975.31604.72261.321263031333713至18列15971598.91507.11580.11962.41802.11921.51921.11556.91752.115951725.82126.81623.