一種改進的K-means聚類算法*

周愛武，崔丹丹，肖 云

(安徽大學 計算機科學與技術學院，安徽 合肥 230039)

聚類分析[1](clustering)是數據挖掘研究的重要領域，借助聚類分析將大量的數據對象聚成不同的類簇，使不同簇之間的相似度低，簇內的相似度高，它是一種無監督的學習算法。為了實現對數據對象的聚類，人們提出了不同的聚類算法。聚類算法主要分成基于劃分、基于密度、基于分層、基于網格和基于模型的五大類[2]。K-means(均值)聚類算法是典型的基于劃分的聚類算法，同時也是應用最廣泛的一種聚類算法。K-means聚類算法[3]主要針對處理大數據集，不但處理快速簡單，而且算法具有高效性以及可伸縮性。但是K-means聚類算法存在K值需要事先指定、隨機選擇初始聚類中心等的局限性。人們針對K-means聚類算法的這些局限性提出了不同的改進算法。劉濤等人[4]提出了基于半監督學習的K-means聚類算法的研究，用粒子群算法以及迭代搜索的思想找到優質的聚類中心進行聚類；李飛等人[5]提出了基于遺傳算法的全局搜索能力來解決初始聚類中心選擇的敏感性問題。

K-means聚類算法由于初始聚類中心是隨機選擇的，容易造成算法會陷入局部最優解甚至是無解的情況，而聚類結果的好壞直接取決于初始聚類中心的選擇。因此初始聚類中心的選擇十分重要。本文主要針對隨機選擇初始聚類中心這一缺點，提出了一種新的改進的K-means聚類算法。

1 傳統的K-means聚類算法

K-means聚類算法是解決聚類問題的一種經典算法，該算法具有簡單、快速并且能夠有效處理大數據集的特點。K-means聚類算法首先從n個數據對象中任意選取k個對象作為初始聚類中心；而對于所剩下的其他對象，則根據它們與這些聚類中心的相似度(距離)，分別將它們分配給與其最相似的類簇；然后計算該類簇中所有對象的均值；不斷重復這一過程直到標準準則函數開始收斂為止。具體步驟如下[6]：

輸入：k，data[n]；輸出：k個簇的集合，滿足聚類準則函數收斂。

(1)任意選擇k個對象作為初始中心點，例如c[0]=data[0]，…c[k-1]=data[k-1]；

(2)根據簇中對象的均值，將每個對象指派給最相似的簇；

(3)更新簇均值，即計算每個簇中對象的均值；

(4)重復步驟(2)和步驟(3)，直到準則函數不再發生變化。

2 改進K-means算法描述

2.1 相關定義

定義1 數據對象 xi(xi1，xi2，…，xip)T、xj(xj1，xj2，… ，xjp)T之間的距離用歐氏距離d(xi，xj)表示如下：

定義2 二維數據樣本點中心 center(xi，xj)：

2.2 改進算法的思想及基本步驟

影響K-means聚類算法性能的主要原因有：樣本集中孤立點以及隨機選擇初始聚類中心而造成聚類結果的不穩定以及不準確。針對K-means的這種不足，本文提出了一種新的思想：首先將樣本點中影響聚類結果的孤立點去除，然后利用坐標平移的思想來確定初始聚類中心，利用K-means算法進行聚類，最終得到可以滿足平方誤差準則函數收斂的聚類結果。

算法具體步驟：

首先排除樣本點中的孤立點：

(1)輸入樣本點，利用unique函數排除樣本點中重復的數據；

(2)計算每個樣本點與其余樣本點之間的距離存入矩陣cid中；

(3)指定孤立點的個數acnodenum，執行孤立點查找程序，即計算每個點與其余點的距離之和，找出距離最大的前acnodenum個點，即為孤立點；排除孤立點，將孤立點存入集合acnode中，并將這些點從原始數據集中刪除得到新的數據集datanew，即為本文算法第一次去除孤立點之后的樣本點集合。在第一次去除了孤立點之后，可以得到新的樣本點集合datanew。

其次對datanew樣本進行處理，從中找出k個初始聚類中心：

(4)求出樣本點集合datanew中的兩兩之間的距離存入矩陣D中；

(5)從矩陣D中找出距離最大的兩個點A和B，其最大距離記為maxinD，根據式(2)計算其中心 center和半徑(r=maxinD/2)；

(6)第二次去除孤立點：求datanew中的每個樣本點與center的距離，將大于r的樣本點加入到集合acnode中并將其從datanew中去除得到第二次去除孤立點之后的樣本點datanewsec；

(7)利用坐標平移的思想求解初始聚類中心：

①將步驟(5)中求出的A、B中的任一點加入初始聚類中心集合nc中作為第一個初始聚類中心；

②循環k-1次實現以center為參照點，將A坐標順時針移動圓心角等于2×pi/k的度數；

利用T-text分析是否已經發表A類文章的研究生對于初級知識、中級知識、高級知識、初級技能、中級技能、高級技能、態度的差異情況，經過分析，是否已經發表A類文章的研究生在初級知識、中級知識、高級知識、初級技能、中級技能、高級技能、態度因素的P值均大于0.05，沒有顯著性差異。

③最終得到包含A在內的k個點，將這個k個點作為初始的聚類中心存入矩陣nc中；

(8)利用步驟(7)中求得的初始的聚類中心nc，用K-means算法進行聚類得出滿足聚類準則函數收斂的聚類結果。

(9)計算acnode中的每個點與每個初始聚類中心的距離，將acnode中的點加入到距離初始聚類中心最近的簇中。

3 實驗結果及分析

3.1 實驗數據及實驗環境

為了便于對比分析與計算，本實驗采用的是二維數據，并且數據類型是數值型的。實驗采用了兩組測試數據：一組是隨機數據，一組是UCI數據庫中的標準數據集Iris數據集。實驗工具采用MATLAB環境編程實現。

3.2 實驗方案

3.2.1 采用隨機數據

采用傳統的隨機選擇初始聚類中心的K-means算法將本文的改進算法對隨機產生的80個樣本進行聚類，聚類的簇數設為k=4，比較其聚類結果圖。

第 1 組 ： (0.660 2，0.207 1)、(0.342 0，0.607 2)、(0.289 7， 0.629 9)、(0.341 2，0.370 5)。

第 2 組 ： (0.767 6，0.274 6)、 (0.261 0，0.193 1)、(0.719 7，0.827 6)、(0.315 8，0.620 6)。

第 3 組 ： (0.580 8，0.104 6)、 (0.815 8，0.400 6)、(0.211 4，0.445 7)、(0.623 2，0.807 5)。

第 4 組 ： (0.568 1，0.846 9)、 (0.781 2，0.575 2)、(0.211 4，0.445 7)、(0.628 6，0.122 5)。

圖1 針對隨機數據的選取四種初始聚類中心的結果圖

采用改進算法選出的初始聚類中心為(0.231 1，0.956 8)、 (0.999 6，0.795 7)、(0.8385，0.0272)和(0.0700，0.188 3)，其聚類結果如圖2所示。

由圖 1、圖 2可以看出，利用本文改進算法選出的初始聚類中心進行聚類，其聚類結果比較接近數據分布。

圖2 針對隨機數據的改進算法聚類結果

3.2.2 采用Iris數據集

Iris數據集是UCI數據庫中的一個標準數據集，包含有4個屬性，150個數據對象，可分為3類。選用Iris數據集中間二維的數據進行聚類，分別用原算法和改進算法進行實驗。對實驗結果從運行時間以及準確度上進行分析，實驗結果匯總以及分析如表1所示。

從表1可以看出，改進算法的運行時間比傳統K-means算法的運行時間要小，尤其當數據集比較大時，其運行時間小得多。從圖3中可以看出，采用改進算法其準確度明顯提高。

本文提出的改進算法雖然在查找孤立點以及計算樣本點之間的距離方面，會增加時間消耗，但是改進算法準確度較高，聚類效果較好。實驗證明該算法是切實可行的，與傳統的K-means算法相比較，有較好的聚類結果。

表1 K-means算法與本文改進算法準確率與運行時間比較

圖3 兩種算法的準確率以及運行時間的比較

[1]Han Jiawei，KAMBER M.Dataminingconceptsand techniques， second edition[M].Elsevier(Singapore)Pte Ltd，2006：251-263.

[2]張建輝.K-means聚類算法的研究與應用 [D].武漢：武漢理工大學，2007：10-14.

[3]馮超.K-means聚類算法的研究[D].大連：大連理工大學，2007：15-19.

[4]劉濤，尹紅健.基于半監督學習的K-均值聚類算法的研究[J].計算機應用研究，2010，27(3)：913-917.

[5]李飛，薛彬，黃亞樓.初始中心優化的 K-Means聚類算法[J].計算機科學，2002，29(7)：94-96.

[6]Shi Na， Liu Xumin， Guan Yong.Research on k-means clustering algorithm[C].Third International Symposium on Intelligent Information Technology and Security Informatics，2010：63-67.