K值均值算法論文

1、K值均值聚類算法在教學(xué)分組中的應(yīng)用引言：K-均值聚類是流行、經(jīng)典、簡(jiǎn)單的聚類方法之一。聚類是非監(jiān)督學(xué)習(xí)的一種方法，也是常用的統(tǒng)計(jì)數(shù)據(jù)分析技術(shù)，應(yīng)用領(lǐng)域很廣，涉及機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、模式識(shí)別、圖像分析和生物信息學(xué)等。在統(tǒng)計(jì)和機(jī)器學(xué)習(xí)中， K-均值算法是一種聚類分析方法，它將n個(gè)觀察對(duì)象分類到k個(gè)聚類，每個(gè)觀察對(duì)象將被分到與均值最接近的聚類中。其基本思想是：通過迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結(jié)果。一、K值均值聚類原理 所謂聚類問題，就是給定一個(gè)元素集合D，其中每個(gè)元素具有n個(gè)可觀察屬性，使用某種算法將D劃分成k個(gè)子集，要求每個(gè)子集內(nèi)部的元素之間相異度盡可能低，而不

2、同子集的元素相異度盡可能高。其中每個(gè)子集叫做一個(gè)簇。 與分類不同，分類是示例式學(xué)習(xí)，要求分類前明確各個(gè)類別，并斷言每個(gè)元素映射到一個(gè)類別，而聚類是觀察式學(xué)習(xí)，在聚類前可以不知道類別甚至不給定類別數(shù)量，是無監(jiān)督學(xué)習(xí)的一種。目前聚類廣泛應(yīng)用于統(tǒng)計(jì)學(xué)、生物學(xué)、數(shù)據(jù)庫技術(shù)和市場(chǎng)營(yíng)銷等領(lǐng)域，相應(yīng)的算法也非常的多。本文僅介紹一種最簡(jiǎn)單的聚類算法k均值（k-means）算法。 1.1算法簡(jiǎn)介k-means算法，也被稱為k-平均或k-均值，是一種得到最廣泛使用的聚類算法。它是將各個(gè)聚類子集內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類的代表點(diǎn)，算法的主要思想 是通過迭代過程把數(shù)據(jù)集劃分為不同的

3、類別，使得評(píng)價(jià)聚類性能的準(zhǔn)則函數(shù)達(dá)到最優(yōu)，從而使生成的每個(gè)聚類內(nèi)緊湊，類間獨(dú)立。這一算法不適合處理離散型屬性，但是對(duì)于連續(xù)型具有較好的聚類效果。1.2算法描述 1、為中心向量c1, c2, , ck初始化k個(gè)種子 2、分組: （1）將樣本分配給距離其最近的中心向量 （2）由這些樣本構(gòu)造不相交（ non-overlapping ）的聚類 3、確定中心: 用各個(gè)聚類的中心向量作為新的中心 4、重復(fù)分組和確定中心的步驟，直至算法收斂。 1.3 算 法  k-means算法 圖1.1

4、算法流程圖輸入：簇的數(shù)目k和包含n個(gè)對(duì)象的數(shù)據(jù)庫。 輸出：k個(gè)簇，使平方誤差準(zhǔn)則最小。 算法步驟：  1.為每個(gè)聚類確定一個(gè)初始聚類中心，這樣就有K 個(gè)初始聚類中心。  2.將樣本集中的樣本按照最小距離原則分配到最鄰近聚類   3.使用每個(gè)聚類中的樣本均值作為新的聚類中心。 4.重復(fù)步驟2.3直到聚類中心不再變化。 5.結(jié)束，得到K個(gè)聚類 PS1.將樣本分配給距離它們最近的中心向量，并使目標(biāo)函數(shù)值減小 i=1nmin*|Xi-Pj|21,2,···

5、;,k 2、更新簇平均值Xi=1|Ci|*xCiX3、計(jì)算準(zhǔn)則函數(shù)EE=i=1kXCi|X-Xi|2 計(jì)算準(zhǔn)則函數(shù)（2）選擇評(píng)價(jià)聚類性能的準(zhǔn)則函數(shù)       k-means聚類算法使用誤差平方和準(zhǔn)則函數(shù)來 評(píng)價(jià)聚類性能。給定數(shù)據(jù)集X，其中只包含描述屬性，不包含類別屬性。假設(shè)X包含k個(gè)聚類子集X1,X2,XK；各個(gè)聚類子集中的樣本數(shù)量分別為n1，n2,nk;各個(gè)聚類子集的均值代表點(diǎn)（也稱聚類中心）分別為m1，m2,mk。則誤差平方和準(zhǔn)則函數(shù)公式為： E=i=1kpXi|p-mi|2（3）相似度的計(jì)算根據(jù)一個(gè)簇中對(duì)象的平均值來

6、進(jìn)行。 1）將所有對(duì)象隨機(jī)分配到k個(gè)非空的簇中。 2）計(jì)算每個(gè)簇的平均值，并用該平均值代表相應(yīng)的簇。 3）根據(jù)每個(gè)對(duì)象與各個(gè)簇中心的距離，分配給最近的簇。 4）然后轉(zhuǎn)2），重新計(jì)算每個(gè)簇的平均值。這個(gè)過程不斷重復(fù)直到滿足某個(gè)準(zhǔn)則函數(shù)才停止 1.4聚類例子圖1.2數(shù)據(jù)集數(shù)據(jù)對(duì)象集合S見上表，作為一個(gè)聚類分析的 二維樣本 ，要求的簇的數(shù)量k=2。 (1)選擇O10,2   ，O20,0  為初始的簇中心，即 M1=O1=0,2M2=O2=0,0 (2)對(duì)剩余的

7、每個(gè)對(duì)象，根據(jù)其與各個(gè)簇中心的距離，將它賦給最近的簇對(duì)O3： dM1,O3=0-1.52+2-02=2.5dM2,O3=0-1.52+0-02=1.5顯然dM2,O3dM1,O3  O3，故將C2分配給 對(duì)于O4:dM1,O4=0-52+2-02=29dM2,O4=0-52+0-02=5因?yàn)椋篸M2,O4dM1,O4  所以將O4分配給C2對(duì)于O5:dM1,O5=0-52+2-02=5dM2,O5=0-52+0-22=29因?yàn)椋篸M1,O5dM2,O5  所以講O5:分配給C1 更新，得到新簇C1=O1,

8、O5和C2=O2,O3,O4計(jì)算平方誤差準(zhǔn)則，單個(gè)方差為E1=0-02+2-22+0-52+2-22=25M1=O1=0,2E2=27.25 M2=O2=0,0總體平均方差是：E=E1+E2=25+27.25=52.25（3）計(jì)算新的簇的中心。  M1=0+52,2+22=2.5,2M1=0+1.5+53,0+0+03=2.17,0 重復(fù)（2）和（3），得到O1分配給C1；O2分配給C2，O3分配給C2 ，O4分配給C2，O5分配給C1。更新，得到新簇 C1=O1,O5和C2=O2,O3,O4 中心為M1=2.5,2, M2=2.17,0單個(gè)方差分別為E

9、1=0-2.52+2-22+2.5-52+2-22=12.5E2=13.15 總體平均誤差是：E=E1+E2=12.5+13.15=25.65由上可以看出，第一次迭代后，總體平均誤差值52.2525.65，顯著減小。由于在兩次迭代中，簇中心不變，所以停止迭代過程，算法停止。二、K值均值聚類的Java實(shí)現(xiàn)以下是五個(gè)核心方法，他們分別是clusterSet（將當(dāng)前元素放到最小距離中心相關(guān)的簇中），errorSquare（誤差平方和準(zhǔn)則函數(shù)），setNewCenter（生成新的簇中心），kmeans（主方法），KmeansTest（測(cè)試） 。2.1元素的分簇將當(dāng)前元素放到最小距離中心相關(guān)的

10、簇中    private void clusterSet()           float distance = new floatk;          for (int i = 0; i < dataSet

11、Length; i+)               for (int j = 0; j < k; j+)                   distancej&#

12、160;= distance(dataSet.get(i), center.get(j);                  / System.out.println("test2:"+"dataSet"+i+",center"+j+",distance="+distancej);  &#

13、160;                           int minLocation = minDistance(distance);             &

14、#160;/ System.out.println("test3:"+"dataSet"+i+",minLocation="+minLocation);              / System.out.println();             

15、;   cluster.get(minLocation).add(dataSet.get(i);/ 核心，將當(dāng)前元素放到最小距離中心相關(guān)的簇中                    2.2兩點(diǎn)誤差平方和誤差平方和準(zhǔn)則函數(shù)    /*      * 求

16、兩點(diǎn)誤差平方的方法      *       * param element      *            點(diǎn)1      * param center  

17、0;   *            點(diǎn)2      * return 誤差平方      */      private float errorSquare(float element, float 

18、center)           float x = element0 - center0;          float y = element1 - center1;          

19、;  float errSquare = x * x + y * y;            return errSquare;            /*      * 

20、;計(jì)算誤差平方和準(zhǔn)則函數(shù)方法      */      private void countRule()           float jcF = 0;          for (int i

21、60;= 0; i < cluster.size(); i+)               for (int j = 0; j < cluster.get(i).size(); j+)          &#

22、160;        jcF += errorSquare(cluster.get(i).get(j), center.get(i);                             

23、60;      jc.add(jcF);        2.3生成新的簇中心    /*      * 設(shè)置新的簇中心方法      */      private void setNewCenter()&#

24、160;          for (int i = 0; i < k; i+)               int n = cluster.get(i).size();     &#

25、160;        if (n != 0)                   float newCenter =  0, 0          

26、         for (int j = 0; j < n; j+)                       newCenter0 += cluster.get(i).

27、get(j)0;                      newCenter1 += cluster.get(i).get(j)1;                   

28、;                 / 設(shè)置一個(gè)平均值                  newCenter0 = newCenter0 / n;    

29、60;             newCenter1 = newCenter1 / n;                  center.set(i, newCenter);     

30、60;                          2.4核心算法過程    /*      * Kmeans算法核心過程方法      */  

31、;    private void kmeans()           init();          / printDataArray(dataSet,"initDataSet");         &#

32、160;/ printDataArray(center,"initCenter");            / 循環(huán)分組，直到誤差不變?yōu)橹?#160;         while (true)            &#

33、160;  clusterSet();              / for(int i=0;i<cluster.size();i+)              /         &

34、#160;     / printDataArray(cluster.get(i),"cluster"+i+"");              /                 count

35、Rule();                / System.out.println("count:"+"jc"+m+"="+jc.get(m);                / System.o

36、ut.println();              / 誤差不變了，分組完成              if (m != 0)            

37、0;      if (jc.get(m) - jc.get(m - 1) = 0)                       break;        &

38、#160;                                       setNewCenter();       

39、0;      / printDataArray(center,"newCenter");              m+;              cluster.clear();    

40、;          cluster = initCluster();                      / System.out.println("note:the times of repeat:m

41、="+m);/輸出迭代次數(shù)              /*      * 執(zhí)行算法      */      public void execute()       &#

42、160;   long startTime = System.currentTimeMillis();          System.out.println("kmeans begins");          kmeans();      

43、60;   long endTime = System.currentTimeMillis();          System.out.println("kmeans running time=" + (endTime - startTime)         

44、60;        + "ms");          System.out.println("kmeans ends");          System.out.println();      

45、    2.5、測(cè)試java view plaincopypackage org.test;    import java.util.ArrayList;    import org.algorithm.Kmeans;    public class KmeansTest       public  

46、;static void main(String args)                /初始化一個(gè)Kmean對(duì)象，將k置為10          Kmeans k=new Kmeans(10);       

47、60;  ArrayList<float> dataSet=new ArrayList<float>();                    dataSet.add(new float1,2);          data

48、Set.add(new float3,3);          dataSet.add(new float3,4);          dataSet.add(new float5,6);          dataSet.add(new float8,9);

49、          dataSet.add(new float4,5);          dataSet.add(new float6,4);          dataSet.add(new float3,9);    

50、60;     dataSet.add(new float5,9);          dataSet.add(new float4,2);          dataSet.add(new float1,9);         

51、 dataSet.add(new float7,8);          /設(shè)置原始數(shù)據(jù)集          k.setDataSet(dataSet);          /執(zhí)行算法        

52、  k.execute();          /得到聚類結(jié)果          ArrayList<ArrayList<float>> cluster=k.getCluster();          /查看結(jié)果      &