K均值改进聚类ppt课件

基于取样思想的改进C均值聚类,1,目 录,C-均值算法的缺陷分析 改进C均值算法的分析 matlab编程所用到函数介绍 matlab算法程序介绍 结果分析 结论,2,一. C-均值算法的缺陷分析,1.聚类个数C需要预先给定 有的算法是通过类的自动合并和分裂，得到较为合理的类型数目C，例如用ISODATA算法，得到初始的聚类数目C。然后运用C均值算法进行聚类分析。 聚类数目C值的确定也可根据方差分析理论，F统计量来确定最佳分类数，并应用模糊划分嫡来验证最佳分类数的正确性。,3,一. C-均值算法的缺陷分析,2.算法对初值敏感 在 C-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果，这也成为 C-means算法的一个主要问题。对于该问题的解决，许多算法采用遗传算法进行初始化，以内部聚类准则作为评价指标。,4,一. C-均值算法的缺陷分析,3.局部极小解的问题 聚类问题本质是一个优化问题的，这就是通过一种迭代运算使得系统的目标函数达到一个极小值。但是这个目标函数在状态空间中不是一个非凸函数，它有许多极小值，其中只有一个是全局极小值，而其他的都是局部极小值。求解的目标是得到全局最小值，而不是其它的局部极小值。这也是目前一些聚类算法，经常会遇到的总是,常会在求解过程中陷入局部最优，而得不到全局最优。,5,二.改进C均值算法的分析,在K均值算法中，选择不同的初始聚类中心会产生不同的聚类结果且有不同的准确率，此方法就是如何找到与数据在空间分布上尽可能一致的初始聚类中心。对数据进行划分，最根本的目的是使一个聚类中的对象是相似的，而不同聚类中的对象是不相似的。如果用距离表示对象之间的相似性程度，相似对象之间的距离比不相似对象之间的距离要小。如果能够寻找到K个初始中心，它们分别代表了相似程度较大的数据集合，那么就找到了与数据在空间分布上相一致的初始聚类中心。,6,二.改进C均值算法的分析,目前，初始聚类中心选取的方法有很多种，在此仅介绍两种： 1.基于最小距离的初始聚类中心选取法 (1) 计算数据对象两两之间的距离; (2) 找出距离最近的两个数据对象,形成一个数据对象集合A1 ,并将它们从总的数据集合U中删除; (3) 计算A1 中每一个数据对象与数据对象集合U 中每一个样本的距离,找出在U中与A1 中最近的数据对象,将它并入集合A1 并从U 中删除, 直到A1 中的数据对象个数到达一定阈值; (4) 再从U中找到样本两两间距离最近的两个数据对象构成A2 ,重复上面的过程,直到形成k个对象集合; (5) 最后对k个对象集合分别进行算术平均,形成k个初始聚类中心。,7,二.改进C均值算法的分析,2.基于取样思想的改进C均值算法 基于以上对C均值算法的分析，我提出自己的改进算法。首先采用对所给的样本数据进行K-means算法进行聚类，产生一组聚类中心。然后将这组聚类中心作为初始聚类中心，在采用n次K-means算法进行聚类。然后判断两次聚类得到的中心是否一致，直到一致则结束聚类。在此，也可以在第一步中，对样本数据采用K-means算法进行n次聚类运算，每次产生一组聚类中心，对n组聚类中心进行算术平均，从而得到c组初始聚类中心。,8,三.matlab编程所用到函数介绍,1.IDX,C = kmeans(data,k) IDX：聚类结果 C：聚类中心 k：分类个数 data：要聚类的数据集合，每一行为一个样本。,9,三.matlab编程所用到函数介绍,mean函数 函数原型：mean(A，dim) 参数： A 待求解均值的矩阵 dim 默认dim=1，就会求每一列的均值；当dim=2时，就会求每一行的均值。,10,四.matlab算法程序介绍,程序主要包括两部分，一个聚类中心的提取，另一个是重新进行聚类划分。 %计算初始聚类中心 clc; clear; %使用c-均值得到初始分类 function yy=Kmeans2()； data=xlsread(E: 模式识别数据data')%载入数据 IDX,C = kmeans(data,4); C y=1:59; z=data,IDX' x=z;y; %初始聚类中心的提取 %kmeans初始算得的聚类中心在矩阵C中 x1=;x2=;x3=;x4=; for i =1:59,11,四.matlab算法程序介绍,if x(4,i)=1 x1=x1,x(:,i); elseif x(4,i)=2 x2=x2,x(:,i); elseif x(4,i)=3 x3=x3,x(:,i); else x(4,i)=4 x4=x4,x(:,i); end end format short g x1=C(1,:)' x2=C(2,:)' x3=C(3,:)' x4=C(4,:)',12,四.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; while xx=xxx xx=xxx; %迭代求解聚类中心 d1=; d2=; d3=; d4=; for i=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; end d1,d2,d3,d4 %d1,d2,d3,d4 %这四组数据分别存储了49个点分别与四个聚类中心的距离,13,四.matlab算法程序介绍,ww1=;ww2=;ww3=;ww4=; %取与聚类中心最近的那个点，并将其归入相应类 for i =1:size(z,2) if min(d1(i),d2(i),d3(i),d4(i)=d1(i) ww1=ww1,x(:,i); elseif min(d1(i),d2(i),d3(i),d4(i)=d2(i) ww2=ww2,x(:,i); elseif min(d1(i),d2(i),d3(i),d4(i)=d3(i) ww3=ww3,x(:,i); else ww4=ww4,x(:,i); end end x1=ww1(1:3,:); x2=ww2(1:3,:); x3=ww3(1:3,:);,14,四.matlab算法程序介绍,x4=ww4(1:3,:); xxx=mean(x1,2),mean(x2,2),mean(x3,2),mean(x4,2) yyy=xxx' end ww1 ww2 ww3 ww4 plot3(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,15,五.结果分析,C = 1.0e+03 * 1.2106 1.8780 2.9579 2.3327 3.0789 1.0759 0.3010 3.2228 2.2502 1.7332 1.7356 1.9762 ww1 = 1 至 6 列 864.45 877.88 1418.8 1449.6 867.81 1494.6 1647.3 2031.7 1775.9 1641.6 2334.7 2072.6 2665.9 3071.2 2772.9 3405.1 2535.1 2550.5 4 6 16 25 32 39 7 至 10 列 1243.1 1495.2 1125.2 1269.1 1814.1 1957.4 1594.4 1910.7 3441.1 3498 2937.7 2702 42 53 54 56,16,五.结果分析,ww2 = 1 至 6 列 2352.1 2297.3 2092.6 2205.4 2949.2 2802.9 2557 3340.1 3177.2 3243.7 3244.4 3017.1 1411.5 535.62 584.32 1202.7 662.42 1985 8 14 15 18 19 22 7 至 12 列 2063.5 2375 2271.9 2336.3 2144.5 2201.9 3199.8 3347 3483 2640.3 2501.6 3196.2 1257.2 975.31 946.7 1599.6 591.51 935.53 24 35 36 43 45 49 13 列 2232.4 3077.9 1298.9 50,17,五.结果分析,ww3 = 1 至 6 列 373.3 222.85 401.3 363.34 104.8 499.85 3087.1 3059.5 3259.9 3477.9 3389.8 3305.8 2429.5 2002.3 2151 2462.9 2421.8 2196.2 2 5 9 10 12 13 7 至 12 列 172.78 341.59 291.02 237.63 460.69 198.83 3084.5 3076.6 3095.7 3077.8 3274.8 3250.4 2328.7 2438.6 2088.9 2252 2173 2445.1 23 27 28 29 34 38 13 至 16 列 354 426.31 343.07 24.22 3300.1 3105.3 3271.7 3447.3 2373.6 2057.8 2036.9 2145 44 46 48 55,18,五.结果分析,ww4 = 1 至 6 列 1739.9 1756.8 1803.6 1571.2 1845.6 1692.6 1675.2 1652 1583.1 1731 1918.8 1867.5 2396 1515 2163.1 1735.3 2226.5 2109 1 3 7 11 17 20 7 至 12 列 1680.7 1651.5 1702.8 1877.9 1831.5 1783.6 1575.8 1713.3 1639.8 1861 1713.1 1598 1725.1 1570.4 2068.7 1975.3 1604.7 2261.3 21 26 30 31 33 37 13 至 18 列 1597 1598.9 1507.1 1580.1 1962.4 1802.1 1921.5 1921.1 1556.9 1752.1 1595 1725.8 2126.8 1623.3 1954.5 2463 1836 1966.3 40 41 47 51 52 57 19 至 20 列 1817.4 1860.5 1927.4 1782.9 2328.8 1875.1 58 59,19,五.结果分析,20,六.结论,本文鉴于初始聚类中心对C均值聚类算法的影响，以及C均值聚类算法的不足，构造了改进C均值的聚类算法。该算法通过两种方法选取初始聚类中心，然后在给定初始聚类中心的基础上再次使用K均值聚类算法，从而得出聚类结果。全部样本与已知样本完全符合。,21,