k中心點算法

k中心算法的基本過程是:首先為每個簇隨意選擇一個代表對象，剩餘的對象根據其與每個代表對象的距離（此處距離不一定是歐氏距離，也可能是曼哈頓距離）分配給最近的代表對象所代表的簇；然後反覆用非代表對象來代替代表對象，以最佳化聚類質量。聚類質量用一個代價函式來表示。當一個中心點被某個非中心點替代時，除了未被替換的中心點外，其餘各點被重新分配。

為了減輕k均值算法對孤立點的敏感性，k中心點算法不採用簇中對象的平均值作為簇中心，而選用簇中離平均值最近的對象作為簇中心。

算法如下:

輸入:包含n個對象的資料庫和簇數目k；

輸出:k個簇

（1）隨機選擇k個代表對象作為初始的中心點

（2）指派每個剩餘對象給離它最近的中心點所代表的簇

（3）隨機地選擇一個非中心點對象y

（4）計算用y代替中心點x的總代價s

（5）如果s為負，則用可用y代替x，形成新的中心點

(6) 重複(2)(3)(4)(5)，直到k箇中心點不再發生變化.