基于密度和聚類指數(shù)改進的K－means 算法

毛 秀，冒純麗，丁岳偉

(上海理工大學(xué) 光電信息與計算機工程學(xué)院，上海 200093)

數(shù)據(jù)挖掘就是對龐大的數(shù)據(jù)集進行分析，從而發(fā)現(xiàn)隱藏其中未知的關(guān)系，并以數(shù)據(jù)擁有者可理解的方式對其有價值數(shù)據(jù)總結(jié)［1］。聚類分析是將數(shù)據(jù)庫中的數(shù)據(jù)按照某種規(guī)則分組或分成成若干類，使得同一類內(nèi)的數(shù)據(jù)之間相似度較高，而不同類內(nèi)的數(shù)據(jù)之間相似度較低［2］。各種聚類方法也被不斷提出和改進，每種算法都有其自身的短處和長處，因此研究和改進各種聚類算法具有一定意義。

至今已經(jīng)有多種聚類算法發(fā)展成熟，主要有基于層次的算法、基于劃分的算法、基于密度的算法、基于網(wǎng)格的算法，模糊聚類也是當下比較流行的聚類分支。現(xiàn)實中人們經(jīng)常使用K－means 聚類算法，相比于其他聚類算法，該算法在處理大數(shù)據(jù)方面性能明顯較優(yōu)［3］。目前，基于K－means 算法的聚類算法研究更是層出不窮，結(jié)合了如孤立點去除、并行化處理、密度、遺傳算法、生成樹、距離代價函數(shù)、加權(quán)等因素用于改進。K－means 算法的原理簡單、易實現(xiàn)，但抗噪聲能力差擾，聚類結(jié)果因不同中心點會大相徑庭，人為給算法輸入的k 值或偏大或偏小均會導(dǎo)致結(jié)果不理想。針對這些缺點，文獻［2］提出了基于密度優(yōu)化初始中心點的方法，文獻［4］等為了獲取k 值提出了新的聚類指數(shù)，文獻［5］結(jié)合密度和最大最小距離法優(yōu)化了中心點的選擇，文獻［6］提出的ADK－keans 算法對孤立點進行特別處理，提高穩(wěn)定性的同時收斂速度快，聚類精度高，文獻［7］先通過密度優(yōu)化初始聚類中心，針對不同的k 值聚類并計算對應(yīng)的聚類有效性指標本，從而確定最佳聚類數(shù)，本文將其算法簡稱為ASK－means算法。本文在上述工作基礎(chǔ)上，將密度、最大距離積法和聚類指數(shù)3 方面的優(yōu)勢進行集成提出了改進的Kmeans 算法，簡稱AIK－means 算法。

1 傳統(tǒng)K－means 聚類算法

K－means 聚類算法是把數(shù)據(jù)集X 中的樣本劃分到k 個簇類中，使得同一簇內(nèi)之間所有樣本之間的相似度最高，不同簇類的質(zhì)心之間的相似度最低。設(shè)定對象集合為X={x1，x2，…，xn}，樣本數(shù)為N，xi表示X中的任意對象，聚類中心點集合C={c1，c2，…，ck}。用Dist(xi，xj)衡量樣本之間的相似度，Dist(xi，xj)代表對象xi，xj之間的距離，m 為對象的維度，xik為對象xi第k 個屬性值，如下

聚類過程中一般使用的目標函數(shù)如下

其中，k 為聚類數(shù);Ci為第i 個類;ci為第i 個類的聚類中心，如下

傳統(tǒng)K－means 算法過程如下:

輸入:原始的樣本數(shù)據(jù)集X，聚類數(shù)k 值。

輸出:k 個簇類。

(1)從樣本集X 中無規(guī)則地取出k 個樣本，將其當作最原始的聚類中心。(2)分別求出X 中其他樣本到第一步選出的k 個中心的歐式距離，將其分給距其歐氏距離最小的簇類。(3)求各簇類的平均值，更新作為下一次聚類的中心，返回步驟(2);若準則函數(shù)收斂則算法終止。

2 改進的K－means 算法

2.1 與密度相關(guān)的基本概念

傳統(tǒng)的K－means 算法得到局部最優(yōu)解是因未考慮到數(shù)據(jù)的空間分布情況，無規(guī)則選取對象時會選到孤立點，根據(jù)不同的初始聚類中心得到的簇類也會相差很大。算法結(jié)合密度和距離則能避免孤立點被選中并且初始聚類中心之間也能保持一定間隔，分布稀疏。因此本文先從樣本集中獲取高密度集，再將距離因素用于高密度集優(yōu)化初始聚類中心。已知樣本集為X={x1，x2，…，xn}，維度為m，xi，xj均屬于X。

定義1 樣本密度:xi為樣本集中的任意對象，將它作為中心，δ 作為鄰域半徑，在其δ 內(nèi)的對象個數(shù)則是對象xi的密度，如下

定義2 鄰域半徑:

其中，n 為集合X 中的樣本數(shù)，通常0 ＜δ≤1，根據(jù)實驗結(jié)果選取最佳參數(shù)值。

定義3 高密度集:設(shè)定參數(shù)Minpts，樣本密度不少于這個參數(shù)的對象集合就是高密度集，m 是高密度樣本個數(shù)。

2.2 最大距離積法

最大最小距離法的缺點是選取的初始中心點之間距離較近且分布密集，使得本該劃分為一個簇類的樣本可能被分到兩個或多個簇。文獻［5］針對最大最小距離法的缺點提出的最大距離積法有較大的收斂速度和準確率，初始聚類中心點分散。采用高密度點對應(yīng)的垂直中心點能在一定程度上擴大初始中心點存在的區(qū)域，這樣有利于高密度區(qū)域能夠相互融合，提高聚類的效果。最大距離積法闡述如下:

(1)根據(jù)關(guān)于密度的相關(guān)知識，得到高密度集HP={z1，z2，…，zm}，m 為此集合中的樣本數(shù)量。

(2)選取HP 中歐氏距離最大的兩個高密度樣本對的均值作為最初的聚類中心添加入到C 中，此時C={c1，c2}。

(3)計算HP 中剩余樣本到C 中樣本的距離，若樣本zi滿足max(Dist(zi，c1)×Dist(zi，c2))，則將樣本zi及其最鄰近高密度點的均值作為下一個聚類中心記為c3，加入集合C 中。

(4)同理，若樣本zm滿足max(Dist(zm，c1)×Dist(zm，c2)×…×Dist(zm，ck－1))，則zm是最后一個聚類中心添加到集合C 中。

2.3 聚類指數(shù)index

隨著k 值增大，簇內(nèi)距離會相應(yīng)減小，而簇間距離增大，即隨著k 變化，二者朝著相反的方向改變，考慮到簇內(nèi)距離與簇間距離之間的這種關(guān)系，文獻［3］中提出的聚類指數(shù)index 能有效地判斷聚類數(shù)k。設(shè)原始樣本集合為X={x1，x2，…，xn}，聚類中心集合為C={c1，c2，…，ck}。

定義4 簇內(nèi)距離是所有簇類中每個對象到其所屬簇類中心的距離總和，如式(7)所示

定義5 簇間距離為所有簇類質(zhì)心相互間的距離求和

定義6 聚類指數(shù)為聚類緊密度與聚類顯著度之和

由定義可看出，index 達到最大時所對應(yīng)的k 為最佳聚類數(shù)。隨著k 值的增大，聚類中心之間計算距離和的數(shù)量也在增大，用平均簇間距離來定義聚類顯著度并不合理，因此本文在這一基礎(chǔ)上用平均簇間距離與聚類數(shù)的積表示聚類顯著度。

2.4 基于密度和聚類指數(shù)改進的K－means 算法

提出結(jié)合密度和聚類指數(shù)改進的K－means 算法描述如下:

輸入:樣本數(shù)據(jù)集X(樣本個數(shù)為n)，調(diào)節(jié)參數(shù)λ，常數(shù)Minpts。

輸出:最好的k 值及對應(yīng)的聚類結(jié)果。

(1)for 1 to n，根據(jù)輸入的參數(shù)λ 計算樣本集鄰域半徑δ，根據(jù)δ 計算得到每個對象xi的密度，將密度大于等于Minpts 的樣本加入到高密度集HP 中。(2)在高密度集HP 中找到距離最遠的兩個對象zi，zj及各自的最鄰近高密度點z’i，z’j組成兩個高密度點對，將各高密度點對的均值加入到初始聚類中心集合C 中，將zi，zj，z’i，z’j從HP 中刪除。(3)根據(jù)C 中的聚類中心進行聚類，并根據(jù)式(7)～式(11)計算此時的聚類指數(shù)index 值，并將其記錄保存。(4)根據(jù)最大距離積法，在HP 剩余對象中尋找下一個高密度點對，將均值作為新的初始聚類中心加入到集合C 中，并從HP 中刪除找到的高密度點對。(5)根據(jù)聚類中心集C 中的對象進行聚類，并計算對應(yīng)新的聚類指數(shù)index，與上一次的index 作比較，如果indexlast＜indexlast－1，則輸出上一次的聚類數(shù)k 及相應(yīng)的聚類結(jié)果，算法終止，否則跳轉(zhuǎn)至步驟(4)。

3 實驗及結(jié)果分析

3.1 實驗

文中的聚類數(shù)據(jù)為結(jié)構(gòu)化數(shù)據(jù)，維度是確定的，其樣本之間彼此無關(guān)，計算歐式距離作為對象相似度。為驗證本文中提出算法的有效性及適用性，實驗數(shù)據(jù)集采用了國際通用測試數(shù)據(jù)庫UCI 中的Iris 數(shù)據(jù)集、Wine 數(shù)據(jù)集和Glass 數(shù)據(jù)集［7］，數(shù)據(jù)集的樣本信息如表1 所示。

表1 數(shù)據(jù)集信息表

由于本文中提出的算法主要是基于文獻［6 ～7］中的算法進行改進的，所以分別對4 個數(shù)據(jù)集采用ADK－means 算法、ASK－means 算法和本文中提出改進的K－means 算法進行聚類對照試驗。實驗的硬件環(huán)境為Windows XP 操作系統(tǒng)，2 GB 內(nèi)存，用Java 代碼實現(xiàn)。改進的K－means 算法中，參數(shù)Minpts 和參數(shù)λ的值則是通過多次試驗根據(jù)聚類效果確定的。由于數(shù)據(jù)集各有特點，所以參數(shù)值也不同，試驗中數(shù)據(jù)集對應(yīng)的參數(shù)如表2 所示。

表2 數(shù)據(jù)集及對應(yīng)的參數(shù)列表

3.2 實驗結(jié)果分析比較

3.2.1 聚類結(jié)果對比分析

ADK－means、ASK－means 及AIK－means 算法對以上3 個數(shù)據(jù)集進行聚類得到的聚類正確率記為A、迭代次數(shù)記為I、誤差平方值記為E、測試時間記為T，結(jié)果如表3 所示。

表3 3 種算法對各數(shù)據(jù)集聚類的結(jié)果

實驗結(jié)果分析表明，表3 中算法聚類結(jié)果的運行時間取多次試驗后的得到的均值，3 個算法的聚類結(jié)果均較為穩(wěn)定，并無波動，得到的聚類數(shù)與實際聚類數(shù)完全一致。從表格中的正確率A 可看出，3 個數(shù)據(jù)集聚類結(jié)果中ASK－means 算法僅比ADK－means 算法的準確率略高，AIK－means 算法具有最高的準確度，且其誤差平方E 的值最小，也能反映其的聚類結(jié)果質(zhì)量最佳。雖AIK－means 算法對各數(shù)據(jù)集聚類時迭代次數(shù)均比ADK－means 算法多一次，但算法運行的實際時間卻要比ASK－means 少，可見其收斂速度快，算法時間復(fù)雜度低。文獻［7 ～8］中及其他類似于ASKmeans 的算法需通過對k 從2 ～kmax迭代計算各聚類評價指標的算法，相比于這些算法AIK－means 算法則減少了眾多不必要的計算，既節(jié)省了硬件資源也大幅縮短了算法的運行時間。從3 個算法的輸入來看，除ADK－means 算法需要用戶輸入聚類數(shù)k，另兩個算法均不要求k 值的輸入，AIK－means 算法能根據(jù)index的值智能判斷最佳聚類數(shù)，有效避免了人為給出k 值對聚類結(jié)果造成的不良影響。

結(jié)合以上分析可看出，基于密度和聚類指數(shù)的改進得到的AIK－means 算法比考慮了密度參數(shù)的ADKmeans 算法有更高的準確率和收斂速度，ASK－means算法準確度比ADK－means 算法略高，雖其也能在無k值輸入的前提下找到最佳的聚類數(shù)但要付出的代價遠比AIK－means 算法多，所以AIK－means 算法既有ADK－means 算法運行效率高的特點又有ASKmeans 算法能自動獲取最佳聚類數(shù)k 的特點，彌補了另外兩種算法的不足。

3.2.2 index 指標對比分析

聚類發(fā)展至今已有諸多學(xué)者提出了諸多聚類有效性指標，并沒有統(tǒng)一的評判標準，所以本文提出的算法采用了比較年輕的index 值作為聚類有效性指標，AIK－means算法中index 值的變化如圖1 所示，根據(jù)3 個算法的最終聚類結(jié)果可分別計算出index 值，如圖2 所示。

圖1 AIK－means 算法中變化的聚類指數(shù)index

圖2 3 個算法對各數(shù)據(jù)集聚類結(jié)果的index 值

以Iris 數(shù)據(jù)集為例，改進的聚類算法中，當聚類數(shù)k 由2 變成3 時，index 的值在增長，然而當k 增長到4時，index 的值驟降，說明當聚類數(shù)為3 時，得到的聚類結(jié)果聚類緊密度和聚類顯著度都達到了巔峰值，因此3 即為最佳聚類數(shù)。其余兩個數(shù)據(jù)集的聚類結(jié)果同樣驗證了這一規(guī)律，index 值會隨著k 值增大而增大，但并不單調(diào)遞增，當達到最大值后就會遞減，最大值時對應(yīng)的k 值就是數(shù)據(jù)集的最佳聚類數(shù)，對應(yīng)的聚類結(jié)果質(zhì)量自然也是最好的。若k 值選擇不當，index 的值相對于最佳聚類數(shù)對應(yīng)的index 值會小，k 值偏差越大，index 值越小，對聚類結(jié)果的影響越大。從圖2 可看出，同一數(shù)據(jù)集中AIK－means 算法的index 值最大，同一算法聚類的前提下Iris 數(shù)據(jù)集的index 值最大，可見index 值能間接反映聚類質(zhì)量，和正確率、誤差平方E 成正相關(guān)的關(guān)系。

實驗結(jié)果表明，本文提出的結(jié)合密度和聚類指數(shù)改進的K－means 算法能得到合理的聚類數(shù)，聚類中心的選取更為合理，能有效避免獨立點對聚類結(jié)果的影響，也并未形成局部最優(yōu)解的可能，聚類質(zhì)量也有大幅提升。

4 結(jié)束語

K－means 算法原理簡單、易于實現(xiàn)、收斂速度快，在各領(lǐng)域到了廣泛應(yīng)用，因此研究改進K－means 算法具有重要意義［9－12］。針對k 值需給定的缺點，學(xué)者們結(jié)合方差分析理論、全協(xié)方差矩陣、有效性指標等來解決這一問題，結(jié)合遺傳學(xué)算法則可有效避免局部最優(yōu)解，在樣本量較大時還可隨機抽取樣本量聚類，以提高算法效率［13－15］。但沒有任何算法是完美的，只有根據(jù)原數(shù)據(jù)的特點正確地選擇算法，才能在準確率和效率之間找到最佳平衡點。實驗證明了本文提出的算法去除了選取初始聚類中心的隨機性，使聚類結(jié)果穩(wěn)定，且基于密度選擇初始聚類中心能有效避免孤立點對聚類結(jié)果的影響，不會形成局部最優(yōu)解的情況。最大距離法則使得所選取的初始聚類中心足夠稀疏，以防聚類中心過度密集導(dǎo)致一個類被分成多個類，聚類指數(shù)能幫助得到最佳聚類數(shù)k。正確率的提升反映了該算法比較高的聚類質(zhì)量。

本文中的參數(shù)λ 及密度閾值Minpts 受到人的主觀能動性影響，在沒有先驗知識的前提下需通過多次嘗試決定最佳參數(shù)值，對不同的數(shù)據(jù)庫參數(shù)不同，增大了工作量，算法的伸縮性也被減弱，有待更好的方法來確定這些參數(shù)值，若能解決這一問題收斂速度可更快。隨著采用的數(shù)據(jù)集樣本量和維度的增大，樣本集若維度過高應(yīng)采用合理的方式降維，選取中心點的方式也需要根據(jù)實際情況改進使之更有合理性，算法中用歐式距離作為衡量對象相似度的標準，實際應(yīng)用中的數(shù)據(jù)大多為非結(jié)構(gòu)化數(shù)據(jù)，歐式距離并不能完全反映出對象之間的相似度，這些將是本算法下一步改進的方向。

［1］ David Hand，Heikki Mannila，Padhraic Smyth.Principles of dara mining［M］.Beijing:China Machine Press，2003.

［2］ Onoda T，Sakai M，Yamada S.Careful seeding method based on independent components analysis for k－means clustering［J］.Journal of Emerging Technologies in Web Intelligence，2012，4(1):51－59.

［3］ 賈永娟.基于密度的改進K－means 文本聚類算法研究［D］.臨汾:山西師范大學(xué)，2014.

［4］ 尹成祥，張宏軍，張睿，等.一種改進的K－means 算法［J］.計算機技術(shù)與發(fā)展，2014，24(10):30－33.

［5］ 鄧海，覃華，孫欣.一種優(yōu)化初始中心的K－means 聚類算法［J］.計算機技術(shù)與發(fā)展，2013，23(11):42－45.

［6］ 刑長征，谷浩.基于平均密度優(yōu)化初始聚類中心的K－means算法［J］.計算機工程與應(yīng)用，2014，50(20):135－138.

［7］ 何云斌，肖宇鵬，萬靜，等.基于密度期望和有效性指標的K－均值算法［J］.計算機工程與應(yīng)用，2013，49(24):105－111.

［8］ 王朔，顧進廣.基于K 值改進的K－means 算法在入侵檢測中的應(yīng)用［J］.工業(yè)控制計算機，2014，27(7):93－97.

［9］ 張琳，陳燕，汲業(yè)，等.一種基于密度的K－means 算法研究［J］.計算機應(yīng)用研究，2011，28(11):4071－4073，4085.

［10］Bhise R B，Thorat S S，Supekar A K.Importance of data mining in higher education system［J］.IOSR Journal of Humanities and Social Science，2013，6(6):18－21.

［11］Gu Chengjie，Zhang Shunyi，Liu Kai，et al.Fuzzy kernel Kmeans clustering method based on immune genetic algorithm［J］.Journal of Computational Information Systems，2011，7(1):221－231.

［12］聶曉偉.基于K－means 算法的雷達信號預(yù)分選方法［J］.電子科技，2013，26(11):55－58.

［13］翟東海，魚江，高飛，等.最大距離法選取初始簇中心的K－means 文本聚類算法的研究［J］.計算機應(yīng)用研究，2014，31(3):713－719.

［14］劉鳳芹.K－means 聚類算法改進研究［D］.濟南:山東師范大學(xué)，2013.

［15］張永晶.初始聚類中心優(yōu)化的K－means 改進算法［D］.長春:東北師范大學(xué)，2013.