1. 什么是 k-means 聚類(lèi)算法,？

  從網(wǎng)上找到了很多定義,，這里選取比較典型的幾個(gè)；

  K-Mean 分群法是一種分割式分群方法,，其主要目標(biāo)是要在大量高緯的資料點(diǎn)中找出

       具有代表性的資料點(diǎn),；這些資料點(diǎn)可以稱(chēng)為群中心，代表點(diǎn),；然后再根據(jù)這些

        群中心,，進(jìn)行后續(xù)的處理，這些處理可以包含

   1 ）資料壓縮：以少數(shù)的資料點(diǎn)來(lái)代表大量的資料,，達(dá)到資料壓縮的功能,；

   2 ）資料分類(lèi)：以少數(shù)代表點(diǎn)來(lái)代表特點(diǎn)類(lèi)別的資料，可以降低資料量及計(jì)算量,；

       分割式分群法的目的是希望盡量減小每個(gè)群聚中,，每一點(diǎn)與群中心的距離平方差（square error）。 

 假設(shè)我們現(xiàn)在有一組包含c個(gè)群聚的資料,，其中第 k 個(gè)群聚可以用集合 G_k來(lái)表示,，假設(shè) G_k包含n_k筆

 資料 {x₁, x₂, …, x_nk），此群聚中心為y_k,，則該群聚的平方差 e_k可以定義為：

             e_k = S _i |x_i-y_k|² ,，其中 x_i是屬於第 k 群的資料點(diǎn),。

 而這c個(gè)群聚的總和平方差E便是每個(gè)群聚的平方差總和：

E = S _k=1~c e_k

 我們分群的方法，就變成是一個(gè)最佳化的問(wèn)題,，換句話說(shuō),，我們要如何選取 c 個(gè)群聚以及相關(guān)的群中心，

 使得 E 的值為最小,。

2 ．處理流程

（ 1 ）   從 c 個(gè)數(shù)據(jù)對(duì)象任意選擇 k 個(gè)對(duì)象作為初始聚類(lèi)中心,；
（ 2 ）   循環(huán)（ 3 ）到（ 4 ）直到每個(gè)聚類(lèi)不再發(fā)生變化為止；
（ 3 ）   根據(jù)每個(gè)聚類(lèi)對(duì)象的均值（中心對(duì)象）,，計(jì)算每個(gè)對(duì)象與這些中心對(duì)象的距離,；并根據(jù)最小距離重新對(duì)相應(yīng)對(duì)象進(jìn)行劃分；
（ 4 ）   重新計(jì)算每個(gè)（有變化）聚類(lèi)的均值（中心對(duì)象）

3. java 算法的實(shí)現(xiàn)說(shuō)明

  1) 假設(shè)給點(diǎn)一組 c 點(diǎn)資料 X = {x₁, ..., x_c} ,，每一點(diǎn)都有 d 維,；給定一個(gè)群聚的數(shù)目 k, 求其

     最好的聚類(lèi)結(jié)果。

  2 ） BasicKMeans.java 主類(lèi)

        int coordCount = 250;// 原始的資料個(gè)樹(shù)

        int dimensions = 100;// 每個(gè)資料的緯度數(shù)目

        double[][] coordinates = new double[coordCount][dimensions];

  這里假設(shè) c 點(diǎn)資料為 coordinates 對(duì)象,，其中 c 為 coordCount,d 為 dimensions 相應(yīng)值,。

        int mk = 30; // 想要群聚的數(shù)目

   根據(jù)群聚數(shù)目定義 mk 個(gè)群聚類(lèi)對(duì)象

      mProtoClusters = new ProtoCluster[mK];// 見(jiàn) ProtoCluster 類(lèi)說(shuō)明

   // 首先隨機(jī)選取 mk 個(gè)原始資料點(diǎn)作為群聚類(lèi)

     mProtoClusters[i]= new ProtoCluster (coordinates[j] );//i 依此為 0 到 mk 的值； j 為 0 到 coordCount 的值

  定義一個(gè)變量用于記錄和跟蹤每個(gè)資料點(diǎn)屬于哪個(gè)群聚類(lèi)

    mClusterAssignments = new int[coordCount];

    mClusterAssignments[j]=i;// 表示第 j 個(gè)資料點(diǎn)對(duì)象屬于第 i 個(gè)群聚類(lèi)

   // 開(kāi)始循環(huán)

•    // 依次調(diào)用計(jì)算每個(gè)群聚類(lèi)的均值

   mProtoClusters[i].updateCenter(mCoordinates);// 計(jì)算第 i 個(gè)聚類(lèi)對(duì)象的均值

•    // 依次計(jì)算每個(gè)資料點(diǎn)到中心點(diǎn)的距離,，然后根據(jù)最小值劃分到相應(yīng)的群集類(lèi)中,；

  采用距離平方差來(lái)表示資料點(diǎn)到中心點(diǎn)的距離；

   //定義一個(gè)變量,，來(lái)表示資料點(diǎn)到中心點(diǎn)的距離

   mDistanceCache = new double[coordCount ][mk];

    //其中mDistanceCache[i][j]表示第i個(gè)資料點(diǎn)到第j個(gè)群聚對(duì)象中心點(diǎn)的距離,；

    //距離算法描述():

     a)依次取出每個(gè)資料點(diǎn)對(duì)象double[] coord = coordinates[i];

        b)再依次取出每個(gè)群聚類(lèi)中的中心點(diǎn)對(duì)象double[] center = mProtoClusters[j].mCenter;

        c)計(jì)算coord對(duì)象與center對(duì)象之間的距離 

     double distance(double[] coord, double[] center) {
        int len = coord.length;
        double sumSquared = 0.0;
        for (int i=0; i<len; i++) {
            double v = coord[i] - center[i];
            sumSquared += v*v; //平方差
        }
        return Math.sqrt(sumSquared);
      } 

     d)循環(huán)執(zhí)行上面的流程，把結(jié)果記錄在mDistanceCache[i][j]中,；

•       //比較出最小距離,，然后根據(jù)最小距離重新對(duì)相應(yīng)對(duì)象進(jìn)行劃分

     依次比較每個(gè)資料點(diǎn)的 最短中心距離，
      int nearestCluster(int ndx) {
        int nearest = -1;
        double min = Double.MAX_VALUE;  
        for (int c = 0; c < mK; c++) {
                double d = mDistanceCache[ndx][c];
                if (d < min) {
                    min = d;
                    nearest = c;
                }          
           }
        return nearest;
       }
  該方法返回該資料點(diǎn)對(duì)應(yīng)的最短中心距離的群聚類(lèi)的索引值,；
  比較每個(gè) nearestCluster[coordCount] 的值和mClusterAssignments[coordCount]
  的值是否相等,，如果全相等表示所有的點(diǎn)已經(jīng)是最佳距離了，直接返回,；
  否則需要重新調(diào)整資料點(diǎn)和群聚類(lèi)的關(guān)系,，調(diào)整完畢后再重新開(kāi)始循環(huán)；

  調(diào)整時(shí)需要更新下列數(shù)據(jù)：

    a)更新mProtoClusters[i]中的mCurrentMembership集合,；

       b)更新mClusterAssignments[i]中對(duì)應(yīng)的值,；

   然后重行開(kāi)始循環(huán)

   3 ） ProtoCluster.java 是一個(gè)包含代表點(diǎn)的群聚類(lèi)，該類(lèi)有兩個(gè)最主要的屬性"代表點(diǎn)"和"群中心",；

         int[] mCurrentMembership;// 用于表示每個(gè)群聚包含的數(shù)據(jù)資料點(diǎn)集合

        double[] mCenter;// 用于表示每個(gè)聚類(lèi)對(duì)象的均值,，也就是中心對(duì)象

         void updateCenter(double[][] coordinates) {

       // 該方法計(jì)算 聚類(lèi)對(duì)象的均值 ;

        // 根據(jù) mCurrentMembership 取得原始資料點(diǎn)對(duì)象 coord ，該對(duì)象是 coordinates 的一個(gè)子集,；然后取出該子集的均值,；

    取均值的算法很簡(jiǎn)單,，可以把 coordinates 想象成一個(gè) m*n 的距陣 , 每個(gè)均值就是每個(gè)縱向列的取和平均值 , 該值保

    存在 mCenter 中

       for (int i=0; i< mCurrentMembership.length; i++) {

               double[] coord = coordinates[mCurrentMembership[i]];

               for (int j=0; j<coord.length; j++) {

                        mCenter[j] += coord[j];// 得到每個(gè)縱向列的和；

               }

               f or (int i=0; i<mCenter.length; i++) {

                    mCenter[i] /= mCurrentSize; // 對(duì)每個(gè)縱向列取平均值

                }

           }