K-means算法
1. 聚類問題
1.1. 相異度
設X={x_1,x_2,…,x_n },Y={y_1,y_2,…,y_n }，其中X,Y是兩個元素項，各自具有n個可度量特征屬性，那么X和Y的相異度可定義為：
相異度是兩個元素對實數域的一個映射，所映射的實數定量表示兩個元素的相異度。當元素的所有特征屬性都是標量時，可以用距離來作為相異度，最常用距離有歐式距離：
曼哈頓距離：
閔可夫斯基距離：
1.2. 聚類問題
聚類問題定義：給定一個元素集合D，其中每個元素具有n個可觀察屬性，使用某種算法將D劃分成k個子集，要求每個子集內部的元素之間相異度盡可能低，而不同子集的元素相異度盡可能高。其中每個子集叫做一個簇。聚類是觀察式學習，在聚類前可以不知道類別甚至不給定類別數量，是無監督學習的一種。目前聚類廣泛應用于統計學、生物學、數據庫技術和市場營銷等領域。K-means算法是一種最簡單的聚類算法。
2. K-means算法
2.1. 問題提出
上圖中有七個樣本點，將其分為兩類（K=2），如何聚類？
- 隨機在圖中取K（這里K=2）個種子點（圖中的灰色點）。
- 對圖中的所有點求到這K個種子點的距離，假如點Pi離種子點Si最近，那么Pi屬于Si點群。（上圖中，我們可以看到A，B屬于上面的種子點，C，D，E屬于下面中部的種子點）。
- 移動種子點到屬于他的“點群”的中心。（見圖上的第三步）。
- 然后重復第2和第3步，直到，種子點沒有移動（圖中的第四步上面的種子點聚合了A，B，C，下面的種子點聚合了D，E）。
2.2. 算法步驟
- 從D中隨機取k個元素，作為k個簇的各自的中心。
- 分別計算剩下的元素到k個簇中心的相異度，將這些元素分別劃歸到相異度最低的簇。
- 根據聚類結果，重新計算k個簇各自的中心，計算方法是取簇中所有元素各自維度的算術平均數。
- 將D中全部元素按照新的中心重新聚類。
- 重復第4步，直到聚類結果不再變化。
- 將結果輸出。
算法求解過程如下圖所示：
這里給出算法的一個演示地址：http://home.deib.polimi.it/matteucc/Clustering/tutorial_html/AppletKM.html。
2.3. 算法分析
由上面的算法過程知K-means的結束條件是收斂，而K-means完全可以保證收斂性。定義畸變函數如下：
J函數表示每個樣本點到其質心的距離平方和。K-means是要將J調整到最小。假設當前J沒有到最小值，那么首先固定每個類的質心u_j，調整每個樣例的所屬類別c^((i))來讓J函數減小。同樣，固定類別調整每個類的質心也可以使J減小。由于J函數是非凸函數，因此不能保證所取的最小值為全局最小值，但一般局部最優已滿足要求。若害怕陷入局部最優，可以取不同的初始值多跑幾次，取最小的J對應的u和c。
K-means算法優點是簡單實用，確定的K 個劃分到達平方誤差最小。當聚類是密集的，且類與類之間區別明顯時，效果較好。對于處理大數據集，這個算法是相對可伸縮和高效的，計算的復雜度為O(NKt)（其中N是數據對象的數目，t是迭代的次數。一般來說，K<
K-means算法缺點主要和K的選取以及初始質心的選取有關：
- K是事先給定的，這個K值的選定是非常難以估計的。很多時候，事先并不知道給定的數據集應該分成多少個類別才最合適。ISODATA算法（較為復雜，此處不介紹）通過類的自動合并和分裂，得到較為合理的類型數目K。
- K-Means算法需要初始隨機種子點，這個隨機種子點太重要，不同的隨機種子點會有得到完全不同的結果。K-Means++算法可以用來解決這個問題，其可以有效地選擇初始點。
- K-means算法對噪聲數據敏感。K-medoids算法在類中選取中心點而不是求類所有點的均值，某種程度上解決了噪聲敏感問題。
3. K-means++算法
- 從數據庫隨機挑一個隨機點當“種子點”。
- 對于每個點，我們都計算其和最近的一個“種子點”的距離D(x)并保存在一個數組里，然后把這些距離加起來得到Sum(D(x))。
- 再取一個隨機值，用權重的方式來取計算下一個“種子點”。這個算法的實現是先取一個能落在Sum(D(x))中的隨機值Random，然后用Random -= D(x)，直到其<=0，此時的點就是下一個“種子點”。
- 重復第（2）和第（3）步直到所有的K個種子點都被選出來。
- 進行K-Means算法。
K-means++算法挑選種子點的基本思想 是隨機挑選并盡量使各種子點間的距離比較遠。D(x)數組存儲了每個點到離它最近的種子點的距離，若我們在x軸的正軸方向依次表示數組中的元素，則最后的 點表示的值就是sum，Random值會落在區間[0，sum]中，并且對于數組元素值大的對應的線段，Random落在其中的概率也越大，即新選出的 “種子點”距離已有種子點遠的概率也越大。
k-means和k-means++對于初始點選取的差異如下圖所示：
k-means初始點選取
k-means++算法初始點選取
4. K-medoids算法
K-means對噪聲很敏感。K-means尋找新的類簇中心點時是對某類簇中所有的樣本點維度求平均值。當聚類的樣本點中有“噪聲”（離群點）時，在計算類簇質點的過程中會受到噪聲異常維度的干擾，造成所得質點和實際質點位置偏差過大，從而使類簇發生“畸變“。如：類簇C1中已經包含點A(1,1)、B(2,2)、C(1,2)、D(2,1)， 假設N(100,100)為異常點，當它納入類簇C1時，計算質Centroid((1+2+1+2+100)/5,(1+2+2+1+100)/5)=centroid(21,21),此時可能造成了類簇C1質點的偏移，在下一輪迭代重新劃分樣本點的時候，將大量不屬于類簇C1的樣本點納入，因此得到不準確的聚類結果。K-medoids提出了新的類簇中心點選取方式，改善了噪聲的影響。
在K-medoids算法中，每次迭代后的質點都是從聚類的樣本點中選取，而選取的標準就是當該樣本點成為新的質點后能提高類簇的聚類質量，使得類簇更緊湊。該算法使用絕對誤差標準來定義一個類簇的緊湊程度：
（p是空間中的樣本點，o_j是類簇 ,c_j的質點）
如果某樣本點成為質點后，絕對誤差能小于原質點所造成的絕對誤差，那么K-medoids算法認為該樣本點是可以取代原質點的，在一次迭代重計算類簇質點的時候，我們選擇絕對誤差最小的那個樣本點成為新的質點。
K-medoids能有效地處理數據集中的噪聲數據，聚類結果優于K-means。但是由于每次選取中心點都要計算樣本點到中心點的距離，時間復雜度增高為O(k(n-k)^2 )。因此，K-medoids只適用于有噪聲數據的小數據集。