毛 秀，冒純麗，丁岳偉

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

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

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

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

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

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

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

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

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

輸出:k 個(gè)簇類。

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

2 改進(jìn)的K－means 算法

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

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

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

定義2 鄰域半徑:

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

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

2.2 最大距離積法

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

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

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

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

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

2.3 聚類指數(shù)index

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果分析比較

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

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

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

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

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

3.2.2 index 指標(biāo)對比分析

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

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

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

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

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

4 結(jié)束語

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

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

［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］ 賈永娟.基于密度的改進(jìn)K－means 文本聚類算法研究［D］.臨汾:山西師范大學(xué)，2014.

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

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

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

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

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

［9］ 張琳，陳燕，汲業(yè)，等.一種基于密度的K－means 算法研究［J］.計(jì)算機(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 算法的雷達(dá)信號預(yù)分選方法［J］.電子科技，2013，26(11):55－58.

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

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

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