改進(jìn)C均值聚類算法

1、改進(jìn)C均值聚類算法C均值算法屬于聚類技術(shù)中一種基本的劃分方法，具有簡(jiǎn)單、快速的優(yōu)點(diǎn)。 其基本思想是選取c個(gè)數(shù)據(jù)對(duì)象作為初始聚類中心，通過(guò)迭代把數(shù)據(jù)對(duì)象劃分到 不同的簇中，使簇內(nèi)部對(duì)象之間的相似度很大，而簇之間對(duì)象的相似度很小。對(duì)C 均值算法的初始聚類中心選擇方法進(jìn)行了改進(jìn)，提出了一種從數(shù)據(jù)對(duì)象分布出發(fā)動(dòng)態(tài)尋找并確定初始聚類中心的思路以及基于這種思路的改進(jìn)算法。1、C-均值聚類算法給出n個(gè)混合樣本，令I(lǐng) =1，表示迭代運(yùn)算次數(shù)，選取c個(gè)初始聚合中心 Zj(1)，j 2,c ；計(jì)算每個(gè)樣本與聚合中心的距離 D(Xk,Zj(l)，k =1,2,., n , j=1,2,c。若 D(Xk，Zi (I)

2、 = min D(Xk，Zj(l), k =1,2,n，則 w。j2,2,.,cJ1 nj計(jì)算c個(gè)新的集合中心：Zj(l 1)xkj)， j =1,2,.,c。nj kA判斷：若Zj(l 1)-Zj(I)，j =1,2,.,c，貝U 1=1 1，返回，否則算法結(jié)束。2、C-均值改進(jìn)算法的思想在C-均值算法中，選擇不同的初始聚類中心會(huì)產(chǎn)生不同的聚類結(jié)果且有不 同的準(zhǔn)確率，此方法就是如何找到與數(shù)據(jù)在空間分布上盡可能相一致的初始聚類 中心。對(duì)數(shù)據(jù)進(jìn)行劃分，最根本的目的是使得一個(gè)聚類中的對(duì)象是相似的，而不同 聚類中的對(duì)象是不相似的。如果用距離表示對(duì)象之間的相似性程度，相似對(duì)象之間的距離比不相似對(duì)象之間

3、的距離要小。如果能夠?qū)ふ业紺個(gè)初始中心，它們分別代表了相似程度較大的數(shù)據(jù)集合，那么就找到了與數(shù)據(jù)在空間分布上相一致的 初始聚類中心。目前，初始聚類中心選取的方法有很多種，在此僅介紹兩種：1)基于最小距離的初始聚類中心選取法其主要思想：計(jì)算數(shù)據(jù)對(duì)象兩兩之間的距離；找出距離最近的兩個(gè)數(shù)據(jù)對(duì)象，形成一個(gè)數(shù)據(jù)對(duì)象集合A1 ,并將它們 從總的數(shù)據(jù)集合U中刪除；計(jì)算A1中每一個(gè)數(shù)據(jù)對(duì)象與數(shù)據(jù)對(duì)象集合 U中每一個(gè)樣本的距離，找 出在U中與A1中最近的數(shù)據(jù)對(duì)象，將它并入集合A1并從U中刪除，直到A1中的 數(shù)據(jù)對(duì)象個(gè)數(shù)到達(dá)一定閾值；再?gòu)腢中找到樣本兩兩間距離最近的兩個(gè)數(shù)據(jù)對(duì)象構(gòu)成A2 ,重復(fù)上面的過(guò)程,直到形成

4、k個(gè)對(duì)象集合；最后對(duì)k個(gè)對(duì)象集合分別進(jìn)行算術(shù)平均，形成k個(gè)初始聚類中心。 這種方法和Huffman算法一樣。后一種算法介紹是是基于最小二叉樹的方法，看起來(lái)比較費(fèi)勁。算法：計(jì)算任意兩個(gè)數(shù)據(jù)對(duì)象間的距離d ( x, y), 找到集合U中距離最近的兩 個(gè)數(shù)據(jù)對(duì)象,形成集合Am (K me k),并從集合U中刪除這兩個(gè)對(duì)象；在U中找到距離集合Am最近的數(shù)據(jù)對(duì)象,將其加入集合Am并從集合U中 刪除該對(duì)象 ；重復(fù)(2) 直到集合中的數(shù)據(jù)對(duì)象個(gè)數(shù)大于等于 a3 n /k ( 0 a e1) ；如果m k,則m + 1,再?gòu)募蟄中找到距離最近的兩個(gè)數(shù)據(jù)對(duì)象，形 成新的集合Am, (1 e m k),并從集合

5、U中刪除這兩個(gè)數(shù)據(jù)對(duì)象，返回(2)執(zhí)行；將最終形成的k個(gè)集合中的數(shù)據(jù)對(duì)象分別進(jìn)行算術(shù)平均，從而形成k個(gè)初 始聚類中心。從這c個(gè)初始聚類中心出發(fā)，應(yīng)用c均值聚類算法形成最終聚類。2)基于取樣思想的改進(jìn)C均值算法首先對(duì)樣本數(shù)據(jù)采用K-meanj算法進(jìn)行聚類，產(chǎn)生一組聚類中心。然后將這 組聚類中心作為初始聚類中心，在采用 K-mea nj算法進(jìn)行聚類。在此，也可以在第一步中，對(duì)樣本數(shù)據(jù)采用K-meanj算法進(jìn)行n次聚類運(yùn)算，每次 產(chǎn)生一組聚類中心，對(duì)n組聚類中心進(jìn)行算術(shù)平均，從而得到 c組初始聚類中心?；谌铀枷氲母倪M(jìn)C均值算法程序:function yy=Kmeanj2()data=1739.9

6、4 1675.15 2395.96 樣本空間373.3 3087.05 2429.471756.771652 1514.98864.451647.312665.9222.853059.542002.33877.882031.663071.181803.581583.122163.052352.122557.041411.53401.3 3259.942150.98363.343477.952462.861571.171731.041735.33104.8 3389.832421.83499.853305.752196.222297.283340.14535.622092.623177.2158

7、4.321418.791775.892772.91845.591918.812226.492205.363243.741202.692949.163244.44662.421692.621867.52108.971680.671575.781725.12802.88 3017.11 1984.98172.783084.492328.652063.543199.761257.211449.581641.583405.121651.521713.281570.38341.593076.622438.63291.023095.682088.95237.633077.782251.961702.816

8、39.792068.741877.931860.961975.3867.812334.682535.11831.491713.111604.68460.693274.772172.992374.983346.98975.312271.893482.97946.71783.641597.992261.31198.833250.452445.081494.632072.592550.511597.031921.522126.761598.931921.081623.331243.131814.073441.072336.312640.261599.63354 3300.12 2373.612144

9、.472501.62591.51426.313105.292057.81507.131556.891954.51343.073271.722036.942201.943196.22935.532232.433077.871298.871580.11752.072463.041962.41594.971835.951495.181957.443498.021125.171594.392937.7324.22 3447.312145.011269.071910.722701.971802.071725.811966.351817.361927.42328.791860.451782.881875.

10、13;IDX,C = kmeans(data,4);Cy=1:59; z=data,IDX;x=z;y;x1=;x2=;x3=;x4=;for i =1:59if 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);endendformat short gx1=C(1,:);x2=C(2,:);x3=C(3,:);x4=C(4,:);x=x(1:3,:);x(5,:); xx=mean(x1,2),mean(x2,2),mean(x3

11、,2),mean(x4,2);xxx=ones(3,4);j=0;zwhile xx=xxxxx=xxx;d1=; d2=; d3=; d4=;for i=1:size(z,2)d仁d1,round(1000*sum(x(1:3,i)-mean(x1,2)A2)/1000;d2=d2,round(1000*sum(x(1:3,i)-mean(x2,2)A2)/1000;d3=d3,round(1000*sum(x(1:3,i)-mean(x3,2)A2)/1000;d4=d4,round(1000*sum(x(1:3,i)-mean(x4,2)A2)/1000;endd1,d2,d3,d4 w

12、w1=;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);endendx1=ww1(1:3,:);Columns 1 through 11x2=ww2(1:3,:);x3=ww3(1:3,:);x4=ww4(1:3,

13、:);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,:),ww 4(2,:),ww4(3,:),*)grid運(yùn)行結(jié)果：C =1733.21735.61976.22332.73078.91075.91210.618782957.9300.973222.82250.2ww1 =Columns 1through 1

14、11739.91756.81803.61571.21845.61692.61680.71651.51702.81877.91831.51675.216521583.117311918.81867.51575.81713.31639.818611713.1239615152163.11735.32226.521091725.11570.42068.71975.31604.7137 111720212630 3133Columns 12 through 201783.615971598.91507.11580.11962.41802.11817.41860.515981921.51921.1155

15、6.91752.115951725.81927.41782.92261.32126.81623.31954.5246318361966.32328.81875.137404147 5152575859ww2 =2352.12297.3 2092.6 2205.4 2949.2 2802.9 2063.52375 2271.9 2336.3 2144.538444648552557 3340.1 3177.2 3243.7 3244.4 3017.1 3199.833473483 2640.3 2501.61411.5 535.62 584.32 1202.7 662.421985 1257.2

16、 975.31 946.7 1599.6 591.518 14 15 18 19 2224 35 36 43 45Columns 12 through 132201.93196.2935.532232.43077.91298.949 50 ww3 =864.45877.881418.81449.6867.811494.61243.11495.21125.21269.11647.32031.71775.91641.62334.72072.61814.11957.41594.41910.72665.93071.22772.93405.12535.12550.53441.134982937.727024616 253239425354 56ww4 =Columns 1 through 11373.3222.85401.3363.34104.8499.85172.78341.59291.02237.63460.693087.13059.53259.93477.93389.8