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

1、改進(jìn)C均值聚類算法C均值算法屬于聚類技術(shù)中一種基本的劃分方法，具有簡單、快速的優(yōu)點(diǎn)。 其基本思想是選取c個數(shù)據(jù)對象作為初始聚類中心，通過迭代把數(shù)據(jù)對象劃分到 不同的簇中，使簇內(nèi)部對象之間的相似度很大，而簇之間對象的相似度很小。對C 均值算法的初始聚類中心選擇方法進(jìn)行了改進(jìn)，提出了一種從數(shù)據(jù)對象分布出發(fā)動態(tài)尋找并確定初始聚類中心的思路以及基于這種思路的改進(jìn)算法。1、C-均值聚類算法給出n個混合樣本，令I(lǐng) =1，表示迭代運(yùn)算次數(shù)，選取c個初始聚合中心 Zj(1)，j 2,c ；計(jì)算每個樣本與聚合中心的距離 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個新的集合中心：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-均值算法中，選擇不同的初始聚類中心會產(chǎn)生不同的聚類結(jié)果且有不 同的準(zhǔn)確率，此方法就是如何找到與數(shù)據(jù)在空間分布上盡可能相一致的初始聚類 中心。對數(shù)據(jù)進(jìn)行劃分，最根本的目的是使得一個聚類中的對象是相似的，而不同 聚類中的對象是不相似的。如果用距離表示對象之間的相似性程度，相似對象之間的距離比不相似對象之間

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

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

5、U中刪除這兩個數(shù)據(jù)對象，返回(2)執(zhí)行；將最終形成的k個集合中的數(shù)據(jù)對象分別進(jìn)行算術(shù)平均，從而形成k個初 始聚類中心。從這c個初始聚類中心出發(fā)，應(yīng)用c均值聚類算法形成最終聚類。2)基于取樣思想的改進(jìn)C均值算法首先對樣本數(shù)據(jù)采用K-meanj算法進(jìn)行聚類，產(chǎn)生一組聚類中心。然后將這 組聚類中心作為初始聚類中心，在采用 K-mea nj算法進(jìn)行聚類。在此，也可以在第一步中，對樣本數(shù)據(jù)采用K-meanj算法進(jìn)行n次聚類運(yùn)算，每次 產(chǎn)生一組聚類中心，對n組聚類中心進(jìn)行算術(shù)平均，從而得到 c組初始聚類中心。基于取樣思想的改進(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