K-means優化 （Kmeans++, ISODATA, Kernal k-means）

1. Kmeans++

原始的kmeans算法随機的選取資料中的k個點作為聚類中心，是以每次聚類的效果可能會有很大的差別，而且初始點選的不好，會很大程度上影響聚類的結果，為了解決此問題引入了K-means++，它的核心思想是：

    a, 在資料集上随機選取一個樣本點作為第一個初始化的聚類中心

    b, 按照下面思路選擇出其餘的聚類中心：（聚類中心互相距離越遠越好）

        計算每個樣本點距已經初始化的聚類中心之間的距離，并選擇其中最短的距離d（x）,(即距離最近聚類中心的距離)

        以機率選擇距離最大的樣本作為新的聚類中心 (距離目前聚類中心越遠的點有更高的機率)，重複上述過程，直到k個聚類中心都被确定

                                                   p=d(x)^2/sum(d(x)^2) (最短距離平方/最短距離平方和)

    c, 然後按照普通的K-means算法進行聚類

2. ISODATA

原始的k-means有一個問題是，k值需要預先人為确定，并且在整個算法中無法更改，當遇到高次元，和資料量較大時，一般很難确定k值得大小。ISODATA就是根據此問題的改進，它的核心思想是：

    當屬于某個類别的個體過多時把這個類别去掉（合并操作），反之當某個類别的樣本數過多，分散程度過大時，把這個類别分位兩個子類别（分裂操作）。

ISODATA輸入：

    a, 預期的Ko值：還是需要使用者輸入K值得變動範圍【Ko/2,2Ko】

    b, 每個類所要求的最少樣本數Nmin：分裂操作的門檻值，當樣本分散程度較大需要進行分裂時，必須保證分裂後的樣本數大于Nmin，合并操作的門檻值，當類别樣本小于Nmin，需要進行合并。

    c, 最大方差Sigma: 衡量樣本的分散程度，當樣本的分散程度大于Sigma時就有可能進行分裂操作。

    d, 兩個聚類中心允許的最小距離dmin：合并操作的門檻值，當兩個聚類中心小于dmin，則需要對這兩個聚類進行合并

相比kmeans和kmeans++， ISODATA需要額外指定較多的參數，并且某些參數同樣很難确定指出一個合理的值，是以ISODATA實際使用中并沒有K-means++受歡迎。

具體算法步驟：

1. 随機選擇Ko個樣本作為聚類中心
2. 對于每個樣本xi，計算到每個聚類中心的距離，并配置設定到距離最小的cluster中
3.  判斷每個cluster中樣本數目是否小于Nmin，如果小于Nmin丢棄該cluster，并将其元素配置設定到最近的cluster中。
4.  重新計算每個類的聚類中心
5.  如果K <= Ko/2, cluster太少，需要進行分裂操作
6.  如果K >= 2Ko. Cluster 太多，需要合并
7.  跳轉至2，直到達到最大疊代次數，

分裂操作

1. 計算每個類别下所有樣本的方差
2. 選出最大的方差

   

   :
3. 如果某個類的方差

   

   : >Sigma, 并且該類包含樣本數目>=2Nmin, 則進行分裂，并前往步驟4
4. K=K+1， 更新聚類中心，mi1 = mi + 

   

   ,  mi2 = mi - 

   

   :

合并操作

1. 計算目前聚類中心兩兩之間的距離D（i，j）
2. 當D（i，j） < dmin， 需要進行合并，合并後的聚類中心位置為:

                  Mnew = (nimi + njmj) / (ni + nj),

          ni和nj分表表示兩個類别中的樣本個數，mi和mj分表表示兩個類原本的聚類中心，新的聚類中心可以看作是對這兩個類别進行權重求和，若果一個類所包含的樣本數較多，所合成的新類就會更偏向它。 

3. kernal Kmeans:

傳統K-means采用歐氏距離進行樣本間的相似度度量，但是并不是所有的資料集都适用這種度量方式，參考SVM中和函數的思想，Kernal Kmeans 就是将所有樣本映射到另一個特征空間在進行聚類，就能解決此問題。