今天主要講述K-中心點聚類算法，並附有詳細的案例來幫助大家理解。K-中心點聚類算法也稱K-medoids聚類算法。
K-中心點聚類算法簡介
第二章中講了K-means聚類算法，但是K-means聚類算法最大的一個缺點就是對於離群點是敏感的，一個具有很大的極端值的數據對象可能會顯著地扭曲數據的分佈。採用誤差平方和準則函數作為聚類性能評價準則更是嚴重惡化了這一影響。為了降低這種敏感性，可以不採用簇中對象的均值最為參照點，而是在每個簇中選出一個實際的對象來代表該簇。其餘的每個對象聚類到與其最相似的代表性對象所在的簇中。這樣的劃分方法仍然是基於最小化所有對象與其對應的參照點之間的相異度之和的原則來執行。通常，該算法重複迭代，直到每個代表對象都成為它的簇的實際中心點，或是最靠中心的對象。這種算法稱為K-中心點聚類算法。
對於K-中心點聚類，首先隨意選擇初始代表對象/種子，只要能夠提高聚類質量，迭代過程就繼續用非代表對象替換代表對象。聚類結果的質量用代價函數來評估，該函數量度對象與其簇的代表對象之間總的相異度。
K-中心點聚類算法原理
K-中心點聚類算法選用簇中位置最中心的對象作為代表對象，試圖對n個對象給出k個劃分。
代表對象也被稱為是中心點，其他對象則被稱為非代表對象。
最初隨機選擇K個對象作為中心點，該算法反覆地用非代表對象來代替代表對象，試圖找出更好的中心點，以改進聚類的質量。
在每次迭代中，所有可能的對象對被分析，每個對中的一個對象是中心點，而另一個是非代表對象。
對可能的各種組合，估算聚類結果的質量。一個對象Oi被可以產生誤差平方總和減少的對象代替。在一次迭代中產生的最佳對象集合成為下次迭代的中心點。
為判定一個非代表對象Oh是否是當前一個代表對象Oi的好的替代，對每一個非中心點對象Oj，下面的四種情況被考慮：
第一種情況：Oj當前隸屬於中心點對象Oi。如果Oi被Oh所代替作為中心點，且Oj離某個中心點Om最近，i≠m，那麼Oj被重新分配給Om。
第二種情況：Oj當前隸屬於中心點對象Oi。如果Oi被Oh所代替作為中心點，且Oj離Oh最近，那麼Oj被重新分配給Oh。
第三種情況：Oj當前隸屬於中心點Om，m≠i。如果Oi被Oh代替作為中心點，而Oj依然離Om最近，那麼對象的隸屬不發生變化。
第四種情況：Oj當前隸屬於中心點Om，m≠i。如果Oi被Oh代替作為一箇中心點，且Oj離Oh最近，那麼Oi被重新分配給Oh。
每當重新分配發生時，誤差平方和E所產生的差別對代價函數有影響。因此，如果一個當前的中心點對象被非中心點對象所代替，代價函數表徵誤差平方和所產生的差別。替換的總代價是所有非中心點對象所產生的代價之和。
如果總代價是負的，那麼實際的誤差平方和將會減小，Oi可以被Oh替代。
如果總代價是正的，則當前的中心點Oi被認為是可接受的，在本次迭代中沒有變化。
總代價定義如下：
總代價
其中，Cjih表示Oj在Oi被Oh代替後產生的代價。
四種情況的代價函數
下面我們將介紹上面所述的四種情況中代價函數的計算公式，其中所引用的符號有：Oi和Om是兩個原中心點，Oh將替換Oi作為新的中心點。其中相異度或距離函數d的選擇因數據類型不同而可以有不同的選擇，對於K-中心點聚類算法一般選擇曼哈頓距離，具體的計算公式可以參考同系列文章《常用數據挖掘算法從入門到精通 第二章 K-means聚類算法》中有關於相似度或者距離評價準則計算的詳細介紹和計算公式。
代價函數計算公式
代價函數計算圖示
K-中心點聚類算法步驟
算法 K-中心點算法
輸入：簇的數目K和包含n個對象的數據庫。
輸出：K個簇，使得所有對象與其最近中心點的相異度總和最小。
（1） 任意選擇K個對象作為初始的簇中心點；
（2） REPEAT
（3） 指派每個剩餘的對象給離它最近的中心點所代表的簇；
（4） REPEAT
（5） 選擇一個未被選擇的中心點Oi；
（6） REPEAT
（7） 選擇一個未被選擇過的非中心點對象Oh；
（8） 計算用Oh代替Oi的總代價並記錄在S中；
（9） UNTIL 所有的非中心點都被選擇過；
（10） UNTIL 所有的中心點都被選擇過；
（11） IF 在S中的所有非中心點代替所有中心點後計算出的總代價有小於0存在 THEN 找出S中的用非中心點替代中心點後代價最小的一個，並用該非中心點替代對應的中心點，形成一個新的K箇中心點的集合；
（12）UNTIL 沒有再發生簇的重新分配，即所有的S都大於0.
K-中心點聚類算法實例
假如空間中的五個點｛A、Ｂ、Ｃ、Ｄ、Ｅ｝如下圖所示，各點之間的距離關係如下表所示，根據所給的數據對其運行K-中心點聚類算法實現劃分聚類（設K=2）。
初始樣本點和樣本點間距離表
第一步
第二步
總代價計算
總代價計算結果圖示
第一次迭代結果
相關推薦
