一種K－均值聚類(lèi)的改進(jìn)算法及其應(yīng)用

江京亞，郭慶勝，陳 旺，周賀杰，陳 勇

（1．武漢大學(xué) 資源與環(huán)境科學(xué)學(xué)院，湖北 武漢430079；2．湖北省鄂東地質(zhì)大隊(duì)，湖北 孝感432000）

聚類(lèi)分析是人類(lèi)理性認(rèn)識(shí)自然，科學(xué)分析世界的主要手段之一。自1994年，李德仁院士在國(guó)際上首次提出空間數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)（Knowledge Discovering and Data Mining）這一概念以來(lái)，聚類(lèi)分析在信息領(lǐng)域得到空前發(fā)展，至今已成為空間數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)的主要技術(shù)手段之一［1］。近十年來(lái)，聚類(lèi)分析已經(jīng)成為數(shù)據(jù)挖掘中的一個(gè)熱點(diǎn)，得到廣大學(xué)者的關(guān)注。綜合國(guó)內(nèi)外多年的研究成果［1－5］，聚類(lèi)分析常用的算法基本可分為基于劃分的算法、基于層次的算法、基于密度的算法、基于圖論的算法、基于模型的算法、基于格網(wǎng)的算法及其混合算法等七類(lèi)方法［1］。

K－均值聚類(lèi)是一種基于劃分的經(jīng)典聚類(lèi)算法，由于其簡(jiǎn)單、高效，已被廣泛應(yīng)用于諸如圖像處理、模式識(shí)別、人工智能和市場(chǎng)銷(xiāo)售等領(lǐng)域。然而K－均值聚類(lèi)其本身卻存在很多缺陷，如對(duì)初始聚類(lèi)中心的依賴性和對(duì)少量噪聲點(diǎn)的敏感性。本文正是為了較好克服這兩方面的缺陷，基于k－dist圖（又稱第k鄰近距離圖）提出了一種改進(jìn)K－均值聚類(lèi)算法。通過(guò)數(shù)據(jù)集的第k鄰近距離圖，獲得噪聲范圍去除噪聲點(diǎn)，同樣地在第k鄰近距離圖中取得點(diǎn)聚集區(qū)域范圍，從中選取距離相距最遠(yuǎn)且盡量靠近真實(shí)簇中心的k′（為了區(qū)別第k鄰近距離圖中的參數(shù)k，聚類(lèi)類(lèi)別數(shù)用k′表示）個(gè)數(shù)據(jù)點(diǎn)作為初始簇中心。實(shí)驗(yàn)證明改進(jìn)算法能很好地去除噪聲點(diǎn)影響，減少迭代次數(shù)，得到穩(wěn)定的聚類(lèi)結(jié)果。

1 K-均值聚類(lèi)算法

K－均值聚類(lèi)算法是應(yīng)用最為廣泛的一種空間聚類(lèi)方法［4］，其基本思想是：在數(shù)據(jù)集范圍內(nèi)，隨機(jī)選取k′個(gè)對(duì)象作為初始簇中心，然后將數(shù)據(jù)集中每個(gè)對(duì)象分配到離它最近的初始簇中心分為一類(lèi)。處理完后，整個(gè)數(shù)據(jù)集暫時(shí)被劃分為k′個(gè)簇，更新簇中心（一般是取此簇中所有對(duì)象的平均值），重復(fù)上述步驟直到達(dá)到一定迭代次數(shù)或滿足一定的平方誤差準(zhǔn)則為止。

K－均值算法由于是在數(shù)據(jù)集范圍內(nèi)隨機(jī)選取初始簇中心，難以正確反映數(shù)據(jù)集的性質(zhì)，聚類(lèi)結(jié)果波動(dòng)較大，穩(wěn)定性差。與此同時(shí)，在更新簇中心時(shí)，采取簇內(nèi)所有對(duì)象的平均值，少量遠(yuǎn)離數(shù)據(jù)聚集區(qū)的噪聲點(diǎn)的加入會(huì)使計(jì)算結(jié)果產(chǎn)生誤差，偏離真正的聚類(lèi)中心，較大地影響聚類(lèi)結(jié)果，甚至可能產(chǎn)生不準(zhǔn)確的結(jié)果。

近些年，針對(duì)K－均值聚類(lèi)算法對(duì)初始中心的依賴性和對(duì)噪聲點(diǎn)的敏感性，許多學(xué)者提出了改進(jìn)算法。文獻(xiàn)［2］在K－均值算法引入混合粒子群優(yōu)化算法思想，將k′個(gè)聚類(lèi)中心整體作為一個(gè)粒子，尋找最優(yōu)解得到聚類(lèi)結(jié)果。該方法能改善K－均值聚類(lèi)對(duì)于初始聚類(lèi)中心依賴的缺陷，加快收斂速度，具有很好的全局尋優(yōu)能力。文獻(xiàn)［3］基于高密度區(qū)域數(shù)據(jù)被低密度區(qū)域數(shù)據(jù)所分割的思想，從高密度區(qū)域選取k′個(gè)相距最遠(yuǎn)的點(diǎn)作為初始聚類(lèi)中心，能很好體現(xiàn)數(shù)據(jù)的分布情況，消除算法對(duì)初始聚類(lèi)中心的依賴。文獻(xiàn)［4］用迪杰斯特拉最短距離作為數(shù)據(jù)對(duì)象之間的距離，初始中心選擇距離和平均值最小的數(shù)據(jù)對(duì)象，進(jìn)行K－均值聚類(lèi)。該方法能消除噪聲點(diǎn)的影響，取得較好的聚類(lèi)結(jié)果。這些改進(jìn)算法雖在一定程度上克服某一方面的缺陷，如對(duì)初始中心點(diǎn)依賴性，但無(wú)法兼顧噪聲點(diǎn)影響，或者消除噪聲點(diǎn)，初始聚類(lèi)中心選取卻無(wú)法顧及，而且實(shí)現(xiàn)起來(lái)都比較復(fù)雜。

2 第k鄰近距離圖

在待聚類(lèi)分析的數(shù)據(jù)集中，計(jì)算每個(gè)數(shù)據(jù)對(duì)象離它最近的第k個(gè)數(shù)據(jù)對(duì)象的距離（文章后面就稱第k鄰近距離），然后將此距離序列降序排列，繪制成一個(gè)折線圖，即為第k鄰近距離圖，圖1為人工數(shù)據(jù)集Point1及其第4鄰近距離圖。橫坐標(biāo)代表第k鄰近距離排序后的點(diǎn)序列號(hào)（和實(shí)際讀入的數(shù)據(jù)序列順序不同），縱軸代表橫軸序列點(diǎn)所對(duì)應(yīng)的第k鄰近距離。

第k鄰近距離圖最早是由Martin Ester［5］等為確定一種密度聚類(lèi)－DBSCAN方法的鄰域半徑參數(shù)而做的圖，曲線走向變化較大的那個(gè)數(shù)據(jù)對(duì)象所對(duì)應(yīng)的第k鄰近距離即為鄰域半徑（如圖1（b）中箭頭所指的縱坐標(biāo)值）。第k鄰近距離圖能很好地反映一個(gè)數(shù)據(jù)集的分布情況。曲線從左邊以陡峭的趨勢(shì)快速下降到一個(gè)臨界值－臨界第k鄰近距離，然后以較小的第k鄰近距離趨于平緩，即為數(shù)據(jù)聚集的地帶。由于噪聲點(diǎn)數(shù)量少，分布離散，因此從左邊開(kāi)始下降速度較快，呈陡峭形勢(shì)，而在數(shù)據(jù)聚集區(qū)域，數(shù)據(jù)對(duì)象的第k鄰近距離都相對(duì)較小，較為集中，曲線呈平緩趨勢(shì)。數(shù)據(jù)對(duì)象的第k鄰近距離越小，其為簇中心的可能性越大，反之，其為噪聲點(diǎn)的可能性越大。

文獻(xiàn)［5］研究發(fā)現(xiàn)，第k鄰近距離圖中當(dāng)k＞4時(shí)，如k＝8，繪制出來(lái)的曲線整體趨勢(shì)與k＝4繪出的曲線變化很小，因此本文取k＝4。

圖1 Point1數(shù)據(jù)集及其第4鄰近距離圖

3 改進(jìn)后的K-均值算法

3．1 算法思想及流程

做出數(shù)據(jù)集的第4鄰近距離圖，由于數(shù)據(jù)對(duì)象的第4鄰近距離越小，其為簇中心的可能性越大，反之，則其為噪聲點(diǎn)的可能性越大，因此需要找出噪聲臨界點(diǎn)（曲線趨勢(shì)顯著變化的那個(gè)數(shù)據(jù)點(diǎn)）所對(duì)應(yīng)的第4鄰近距離（稱臨界第4鄰近距離），然后從數(shù)據(jù)集中清除那些第4鄰近距離大于臨界第4鄰近距離所對(duì)應(yīng)的數(shù)據(jù)點(diǎn)，得到整理后的數(shù)據(jù)集。接著在第4鄰近距離圖中平緩帶（數(shù)據(jù)點(diǎn)密集段）所對(duì)應(yīng)的數(shù)據(jù)點(diǎn)集中選取相距最遠(yuǎn)的k′個(gè)數(shù)據(jù)點(diǎn)作為初始簇中心，然后按照最近距離將各個(gè)數(shù)據(jù)分配到離它最近的簇中心，更新簇中心，直到達(dá)到一定迭代次數(shù)或滿足一定的誤差平方準(zhǔn)則為止。

改進(jìn)算法主要是基于第4鄰近距離圖，獲得噪聲范圍去除噪聲點(diǎn)，然后選取盡量靠近數(shù)據(jù)聚集區(qū)的k′個(gè)初始簇中心，因此迭代次數(shù)少，聚類(lèi)穩(wěn)定，同時(shí)消除噪聲點(diǎn)的影響，所得結(jié)果較好。

3．2 去除噪聲點(diǎn)

噪聲點(diǎn)往往是遠(yuǎn)離數(shù)據(jù)聚集區(qū)的孤立點(diǎn)，數(shù)量不多，因此處在4－鄰近圖中陡峭的一段中。做出第4鄰近距離圖后，找到臨界第4鄰近距離，將此距離作為數(shù)據(jù)點(diǎn)的第4鄰近距離的閾值，去除那些第4鄰近距離大于該臨界第4鄰近距離所對(duì)應(yīng)的數(shù)據(jù)點(diǎn)，即得到去噪后的數(shù)據(jù)集。

輸入：含n個(gè)對(duì)象的待聚類(lèi)數(shù)據(jù)集P

輸出：去噪后數(shù)據(jù)集P1，第4鄰近距離圖

具體步驟如下：

1）讀取數(shù)據(jù)集P，計(jì)算P中每個(gè)數(shù)據(jù)對(duì)象pi（i＝1，2，3，…，n）的第4鄰近距離，并存儲(chǔ)在temp Dist（pi）中。

2）將temp Dist（pi）降序排序，并制作出第4鄰近距離圖。

3）順序計(jì)算圖中相鄰3點(diǎn)之間的轉(zhuǎn)角ɑ，找到最大轉(zhuǎn)角ɑ所對(duì)應(yīng)的數(shù)據(jù)點(diǎn)，將該數(shù)據(jù)點(diǎn)設(shè)為臨時(shí)臨界點(diǎn)，然后依據(jù)第4鄰近距離圖人工判斷其合理性，若不符合數(shù)據(jù)分布特征，則重新指定。確定該臨界點(diǎn)的第4鄰近距離為臨界第4鄰近距離dist－Threshol d（如圖1（b）中箭頭所指臨界點(diǎn)所對(duì)應(yīng)的第4鄰近距離）。

4）將每個(gè)數(shù)據(jù)點(diǎn)的第4鄰近距離與dist－Threshol d比較，若大于或等于dist－Threshol d，則該點(diǎn)是噪聲點(diǎn)，從P中刪除該點(diǎn)，否則保留此點(diǎn)。

5）處理完所有數(shù)據(jù)后得到去噪后數(shù)據(jù)集P1，同時(shí)將第4鄰近距離圖保留下來(lái)。

如圖2所示，對(duì)于數(shù)據(jù)集Point1，選用傳統(tǒng)K－均值聚類(lèi)算法處理得到的多個(gè)聚類(lèi)結(jié)果中較好的一個(gè)，如圖2（a）中所示，其最終生成的3類(lèi)簇中包含大量噪聲點(diǎn)，簇的中心（圖2（a）中十字架所在位置）也偏離了真正的簇中心，而采用本文方法得到的結(jié)果，則去除了噪聲點(diǎn)只保留了數(shù)據(jù)點(diǎn)聚集的3個(gè)簇，簇的中心也在數(shù)據(jù)集正中間，聚類(lèi)效果較好。但是必須注意到很多數(shù)據(jù)的分布并不是很理想化，即數(shù)據(jù)聚集區(qū)和噪聲點(diǎn)可以明顯區(qū)分開(kāi)，很多數(shù)據(jù)簇的界線是模糊的，如圖3所示，此時(shí)將最大轉(zhuǎn)角a對(duì)應(yīng)的數(shù)據(jù)點(diǎn)設(shè)置為臨時(shí)臨界點(diǎn)，依據(jù)第4鄰近距離圖，發(fā)現(xiàn)其并不合理，應(yīng)順序后移重新設(shè)置臨界點(diǎn)，而其第4鄰近距離作為臨界第4鄰近距離。

圖2 傳統(tǒng)K-均值聚類(lèi)與改進(jìn)K-均值聚類(lèi)結(jié)果比較

圖3 point2數(shù)據(jù)集及其第4鄰近距離圖

3．3 k′個(gè)初始簇中心的確定

經(jīng)過(guò)去噪后的數(shù)據(jù)集P1沒(méi)有噪聲點(diǎn)的干擾，可以開(kāi)始進(jìn)行K－均值聚類(lèi)。在第4鄰近距離圖中找到數(shù)據(jù)點(diǎn)密集分布的那個(gè)平緩帶，提取第4鄰近距離的范圍C（事實(shí)上在去噪的同時(shí)提取第4鄰近距離的最大值和最小值），找到第4鄰近距離在此范圍內(nèi)的數(shù)據(jù)集P2，取最小的第4鄰近距離所對(duì)應(yīng)的那個(gè)點(diǎn)作為第1個(gè)初始簇中心k′1，然后在數(shù)據(jù)集P2選取離k′1最遠(yuǎn)的數(shù)據(jù)點(diǎn)作為第2個(gè)初始中心k′2，同理第3個(gè)初始簇中心k′3選取離k′1，k′2最遠(yuǎn)的點(diǎn)，以此類(lèi)推直到k′個(gè)初始簇中心都找到為止。

輸入：去噪后數(shù)據(jù)集P1，聚類(lèi)個(gè)數(shù)k′

輸出：k′個(gè)初始簇中心集合

具體步驟如下：

1）利用去噪時(shí)制作的第4鄰近距離圖，找出數(shù)據(jù)點(diǎn)密集分布的平緩帶C，其中第4鄰近距離dist－Threshol d可作為C的上界，下界則為最小4－鄰近距離。

2）從數(shù)據(jù)集P1中選擇第4鄰近距離在C段的數(shù)據(jù)點(diǎn)，完成選擇后得到數(shù)據(jù)集P2。

3）將最小第4鄰近距離所對(duì)應(yīng)的數(shù)據(jù)點(diǎn)作為第1個(gè)初始簇中心k′1，在P2中找到距離k′1最遠(yuǎn)的數(shù)據(jù)點(diǎn)作為第2個(gè)初始簇中心k′2，同理，第3個(gè)初始簇中心k′3選取離k′1，k′2最遠(yuǎn)的數(shù)據(jù)點(diǎn)，即得到的k′3與k′1，k′2之間的最小距離最大。以此類(lèi)推，直到找到k′個(gè)初始簇中心。

4）輸出k′個(gè)初始簇中心集合。

圖4即為數(shù)據(jù)集Point1的初始簇中心選擇，十字架所在位置即為初始簇中心，圖4（b）是改進(jìn)后的K－均值聚類(lèi)方法選取的初始簇中心，初始簇中心已經(jīng)很靠近數(shù)據(jù)點(diǎn)聚集區(qū)了，迭代次數(shù)少，聚類(lèi)穩(wěn)定，而圖4（a）則是傳統(tǒng)K－均值算法中選取的初始簇中心，它們已經(jīng)偏離了真正的數(shù)據(jù)聚集區(qū)，增加了迭代次數(shù)，產(chǎn)生的結(jié)果也有誤差。

圖4 改進(jìn)前后K-均值聚類(lèi)初始簇中心

4 實(shí)驗(yàn)結(jié)果及其應(yīng)用

數(shù)據(jù)來(lái)源于網(wǎng)絡(luò)爬蟲(chóng)軟件在2013年6月采集到的47個(gè)類(lèi)型130 683個(gè)興趣點(diǎn)集，本文從中選用了屬于河北省張家口市，類(lèi)型為“小區(qū)”的251個(gè)子點(diǎn)集，每個(gè)數(shù)據(jù)點(diǎn)包含9個(gè)屬性，共有3個(gè)聚類(lèi)。運(yùn)用本文改進(jìn)的K－均值聚類(lèi)算法后得出的實(shí)驗(yàn)結(jié)果見(jiàn)圖5。

圖5 改進(jìn)算法后所得結(jié)果

從圖5可以看出，改進(jìn)算法去除了少量的噪聲點(diǎn)（圖5（a）中三角板所在位置），獲得了3個(gè)主要小區(qū)點(diǎn)密集分布區(qū)域（圖5（b）中3個(gè)斑塊，也是點(diǎn)集的凸包），效果較好。由于傳統(tǒng)的K－均值聚類(lèi)處理該數(shù)據(jù)集的不穩(wěn)定性，進(jìn)行了10次實(shí)驗(yàn)，取其迭代次數(shù)平均值（見(jiàn)表1），為3．6次，而采用本文算法只需迭代2次，實(shí)驗(yàn)結(jié)果也比較滿意。在運(yùn)行時(shí)間上，傳統(tǒng)K－均值平均運(yùn)行1 367．9 ms，而本文算法只需738．6 ms，效率提高了46%。這是由于改進(jìn)算法選取的初始簇中心是盡量靠近點(diǎn)集密集區(qū)的數(shù)據(jù)點(diǎn)，離真正的簇中心很接近，聚類(lèi)迭代次數(shù)少，只需2次就能完成聚類(lèi)，實(shí)驗(yàn)結(jié)果穩(wěn)定，效率高。

表1 改進(jìn)前后K-均值聚類(lèi)算法迭代次數(shù)和執(zhí)行時(shí)間

聚類(lèi)分析是信息挖掘的有效工具之一。通過(guò)K-均值聚類(lèi)分析居民居住小區(qū)的聚集區(qū)域，往往可以得到很多信息。例如，選址一直是關(guān)系經(jīng)營(yíng)者盈利與否的關(guān)鍵問(wèn)題［6］，商場(chǎng)建在那里才能保證人流量足夠大，當(dāng)然也可以結(jié)合小區(qū)周?chē)纳虉?chǎng)、超市等數(shù)據(jù)點(diǎn)一起分析，怎樣才能確定既不和其它商場(chǎng)或超市沖突又能保證足夠客流量的最佳位置。利用本文改進(jìn)的K－均值聚類(lèi)算法對(duì)小區(qū)數(shù)據(jù)點(diǎn)去噪，聚類(lèi)得到3個(gè)小區(qū)點(diǎn)數(shù)據(jù)集，進(jìn)而生成3個(gè)數(shù)據(jù)集的凸包，得到小區(qū)密集區(qū)域，即居民常住區(qū)域，可以直觀地觀察到居民的生活范圍。為居民提供服務(wù)的行業(yè)，如餐廳，服裝店，商場(chǎng)、KTV等等可以選擇在其周?chē)?，保證其利潤(rùn)最大化。同時(shí)，本文提出的算法也可以用來(lái)確定傳染病重癥區(qū)，合理安排救治人員；劃分旅游景點(diǎn)聚集區(qū)，規(guī)劃最佳旅游路線等等，實(shí)用性較好。

5 結(jié)束語(yǔ)

針對(duì)K－均值聚類(lèi)對(duì)初始簇中心選取的依賴性和對(duì)噪聲點(diǎn)的敏感性，基于第k鄰近距離圖，提出了一種改進(jìn)的聚類(lèi)算法。該算法去除第k鄰近距離較大的噪聲點(diǎn)后，選取處于第k鄰近距離圖中平緩帶－數(shù)據(jù)點(diǎn)密集區(qū)中的k′個(gè)相距最遠(yuǎn)的數(shù)據(jù)點(diǎn)作為初始簇中心。實(shí)驗(yàn)證明了改進(jìn)后算法迭代次數(shù)少，聚類(lèi)穩(wěn)定，所得結(jié)果理想。與此同時(shí)，結(jié)合實(shí)際應(yīng)用，驗(yàn)證了本文算法的實(shí)用性，希望能為選址、規(guī)劃等一些特定問(wèn)題決策提供參考。

［1］鄧敏，劉啟亮，李光強(qiáng)，等．空間聚類(lèi)分析及應(yīng)用［M］．北京：科學(xué)出版社，2011．

［2］但漢輝，張玉芳，張世勇．一種改進(jìn)的 K－均值聚類(lèi)算法［J］．重慶工商大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，26（2）：144－147．

［3］傅德勝，周辰．基于密度的改進(jìn)K均值算法及實(shí)現(xiàn)［J］．計(jì)算機(jī)應(yīng)用，2011，31（2）：432－434．

［4］仇新玲．K－均值聚類(lèi)算法改進(jìn)及應(yīng)用［D］．北京：北京郵電大學(xué)，2012．

［5］ESTER M，KRIEGEL H－P，SANDER J，et al．A densitybased algorit h m for discovering clusters in large spatial databases with noise［C］／／KDD－96：Proceedings of 2nd Inter national Conference on Knowledge Discovery and Data Mining．Menlo Par k：AAAI Press，1996：226－231．

［6］付金輝，趙軍喜，高源．基于灰色預(yù)測(cè)法的超市選址模型研究［J］．測(cè)繪工程，2013，22（5）：46－50．

［7］WANG M，WANG A P，LI A B．Mining spatial－temporal clusters fro m geo－database［J］．Lect Notes Artif Intell，2006，4093：263－270．

［8］殷君偉．K－均值聚類(lèi)算法改進(jìn)及其在服裝生產(chǎn)的應(yīng)用研究［D］．蘇州：蘇州大學(xué)，2013．

［9］鄭丹，王潛平．K－Means初始聚類(lèi)中心的選擇算法［J］．計(jì)算機(jī)應(yīng)用，2012，32（8）：2186－2188．

［10］劉艷麗，劉希云．一種基于密度的 K－均值算法［J］．計(jì)算機(jī)工程與應(yīng)用，2007，43（32）：153－155．