段桂芹

（廣東松山職業(yè)技術學院 計算機與信息工程學院，廣東 韶關 512126）

0 引 言

聚類的目標是將同一簇中樣本相似度最大化，不同簇間樣本相似度最小化。根據聚類過程的不同，通常將聚類分成基于密度、劃分、模型、網格、層次5 種聚類模型［1－2］。作為經典的基于劃分模型的聚類算法，K－means 具有計算便捷、易于理解等特點［3］，由于K－means 算法的初始聚類中心選取是隨機的［4］，因此極易出現局部最優(yōu)，導致聚類結果不穩(wěn)定。此外，當樣本中存在噪聲或離群點時，聚類中心與真實中心存在較大偏差，易生成較差的聚類結果［5－6］。

1 相關算法研究現狀

為了解決聚類分析中的問題，研究者們提出了多種改進算法。Zhai 等人［7］根據相距最遠的數據對象不會劃分至同一簇的基本思想，使用最大距離選取初始聚類中心，解決了原始算法更新次數多、耗時長等問題。在此基礎上，段桂芹［8］將最大距離乘積法與K－means 算法相結合，用相對分散的數據對象構造簇中心集合，優(yōu)化了初始聚類中心，該方法在一定程度上解決了聚類結果不穩(wěn)定等問題，但依然存在迭代次數多、運算耗時長等現象。鄒臣嵩［9］針對文獻［8］的這一問題，提出了一種協(xié)同K 聚類算法。該算法通過樣本的分布情況統(tǒng)計其密度參數，選取與樣本集中心點最遠的高密度對象為首個聚類中心，再通過最大乘積法求得其余聚類中心。徐紅艷等［10］提出基于網格劃分的快速確定全局閾值算法。該方法通過網格劃分思想，將數據自適應地劃分到多個網格空間中，再利用密度估計來計算密度，進而實現快速查找類簇峰值和低谷，最終完成數據集的有效識別。雖然文獻［7－10］在一定程度上優(yōu)化了K－means 算法的初始聚類中心選擇過程，但對噪聲的影響有所忽略。潘品臣［11］根據密度參數理論，對數據集中的高密度點和非離群點區(qū)域進行了計算與識別，規(guī)避了選取噪音點為初始聚類中心以及中心分布不理想等問題。卜秋瑾［12］針對密度峰值聚類算法處理多密度峰值數據集時，人工選擇聚類中心易造成簇的誤劃分問題，提出一種結合遺傳k均值改進的密度峰值聚類算法。該算法能找到準確簇個數同時避免算法陷入局部最優(yōu)，在提高聚類質量的同時，保證了聚類質量的穩(wěn)定性。陳奕延［13］將樣本涵蓋的經典信息拓展到了模糊集上，利用尋找密度峰值的方法對模糊樣本進行聚類，提出了誤差更小的針對連續(xù)型模糊集與離散型模糊集的改進型歐氏距離，使改進后的歐氏距離具有更小的誤差。

在對上述文獻分析研究的基礎上，本文從密度聚類算法入手，從兩個方面對密度聚類算法進行了改進：一是根據高密度樣本被低密度樣本緊密圍繞這一思想，提出了新的密度計算方法。目的是提高聚類中心的代表性，解決密度參數選取敏感等問題。二是在簇更新階段，將與簇內均值距離最近的樣本點作為該簇的臨時中心，減少了迭代次數，降低運算耗時。

2 密度聚類算法改進

改進的密度聚類算法，由初始中心選擇和簇中心迭代計算兩部分構成。

（1）初始中心選擇：首先使用自定義密度公式獲取各樣本密度，將高密度樣本作為聚類中心候選代表點，并生成候選代表點集合；在集合中選取與其他候選代表點距離和最小者作為首個初始聚類中心，再使用乘積最大法完成初始聚類中心選擇，得到初始聚類中心集合，即Z＝｛z1，z2，…，zk｝。

（2）簇中心迭代計算：根據集合Z完成初次聚類，計算簇內各樣本到簇均值中心的距離矩陣。為了降低均值法所得簇中心和實際簇中心位置間的偏差，將與簇內均值距離最近的樣本作為該簇的臨時中心，生成臨時簇中心集合，即Z＝，再通過最小距離法將相關樣本劃分至所屬簇中。重復簇中心迭代計算過程，直至準則函數收斂，完成聚類。

2.1 基本概念與公式

設X為含有n個樣本的數據集，X＝｛x1，x2，…，xn｝，樣本的屬性個數為p，xi＝。X劃分為k個簇，X＝｛C1，C2，…，Ck｝，｜Ci ｜表示第i簇所含樣本個數，zk表示第k簇的中心，多個簇中心所構成的集合為Z，即Z＝｛z1，z2，…，zk｝。

定義1任意兩樣本間的歐氏距離為：

其中：i＝1，2，…，n；j＝1，2，…，n；l＝1，2，…，p

定義2任意樣本xi的距離和定義為：該樣本到數據集各樣本的距離之和。

定義3樣本xi的密度為：

本文密度的定義遵循的思路：從位置關系來看，當某個樣本xi被其它樣本緊密圍繞時，說明該樣本與其它樣本間的距離和相對較?。环粗?，當樣本xi和其它樣本的位置關系較為分散時，說明該樣本與其它樣本間的距離和相對較大。密度表達式用樣本xi和xj之間的距離做分母，用xj到全部樣本的距離之和做分子，用二者距離比值的累加和表示樣本xi被其它樣本圍繞的緊密程度，即xi的密度。

以樣本xi為例。當式（3）累加和中的分子較大時，意味著除xi外其它樣本的累加距離和也較大；當分母較小時，意味著xi到其它樣本距離的累加和較小。因此，當分子越大且分母越小時，表達式的值越大，說明xi被比自身密度低的樣本所圍繞的密集程度越大，即xi的相對密度越大，其作為簇中心的代表性越強。

定義4樣本集的平均密度定義為：

定義5候選代表點集合定義為：密度高于樣本集平均密度α倍的樣本集合

其中：xi，xj∈Ct，t＝1，2，…，k。

定義6候選代表點間的距離矩陣定義為

式中，j表示集合H所含元素個數。

定義7簇內樣本與本簇均值中心間的距離矩陣定義為：

式中，m＝1，2，…，k，Cm表示第m簇的樣本集合。

定義8簇更新后，將與簇內均值距離最近的樣本xi作為該簇的中心。xi滿足以下條件：

定義9聚類誤差平方和E的定義為

式中，xij為第i簇中第j個樣本，zi為第i簇的簇中心。

2.2 算法描述

步驟1使用式（1）～式（3）計算各樣本的密度；

步驟2使用式（4）、式（5）得到候選代表點集合H，其中參數α為1.0；

步驟3用式（1）、式（6）計算候選代表點間的距離矩陣，在H中選擇與其它候選代表點距離和最小者作為首個聚類中心z1存儲至集合Z中；

步驟4在集合H中選擇與z1距離最遠的候選代表點z2存儲至集合Z中；

步驟5從集合H中選擇滿足條件：max（d（hi，z1）×d（hi，z2））的代表點，作為z3存儲至集合Z中；

步驟6重復運行步驟5，直至｜Z ｜＝k；

步驟7使用式（1）計算X中各樣本與集合Z中各候選點的距離，并劃分至距離最小的簇中；

步驟8使用式（7）計算簇內各樣本到簇均值中心的距離矩陣，根據式（8）將距離簇內均值最近的樣本作為該簇的新中心；

步驟9重復步驟7、8，更新簇中心集合Z；

步驟10將X中的樣本按距離劃分至最近的簇中，使用式（9）計算并判斷E是否收斂，若收斂，則算法終止；若未能收斂，將跳轉至步驟7，再次更新簇中心。

2.3 算法復雜度分析

本文算法的時間復雜度為O（n2＋nkt），在初始聚類中心選擇過程中，本文算法首先計算了各樣本的密度，進而得出候選代表點集合，再使用距離乘積最大法對候選點從空間分布的角度進行了二次篩選。雖然計算量有所增加，但各中心的代表性得到增強，初步反映了樣本集的幾何結構，為簇更新次數的降低提供支撐。在簇中心更新過程中，本文算法選取與簇內均值距離最近的樣本作為該簇的臨時中心，生成了臨時簇中心集合，避免了均值法所得簇中心和實際簇中心位置存在偏差的隱患，相比均值算法，本文算法可以降低噪音的干擾，減少更新次數，降低計算開銷，提高運算效率。

3 實驗仿真與分析

實驗運行環(huán)境：CPU Intel Core i7－ 2670 2.20 GHz，硬盤1T，內存8G；操作系統(tǒng)Win10－64位；仿真軟件采用Matlab 2011b。在有效性驗證方面，采用聚類準確率、聚類各階段開銷、Rand 指數、Jaccard 系數等指標，將K－means 算法、文獻［8］中算法、文獻［9］中算法與本文算法進行了比較。實驗過程中，K－means 算法共運行200 次，取其平均值作為該算法的實驗結果。實驗數據集詳見表1。

表1 UCI 數據集Tab.1 UCI dataset

3.1 算法性能對比與分析

圖1～圖5 是K－means 算法、文獻［8－9］算法以及本文算法的聚類準確率、簇中心各階段計算開銷、簇更新次數等實驗的對比結果。由圖1 可知，在iris和wdbc 數據上，本文算法的聚類準確率明顯高于K－means算法，略高于文獻［8－9］算法，在balance、thyroid 和haberman 數據集上的聚類準確率優(yōu)于其它3 種算法。

圖1 聚類準確率Fig.1 Clustering accuracy

圖2 可知，K－means 的初始中心從樣本集中隨機選擇，耗時較少，而文獻［8－9］對初始聚類中心的選擇過程進行了優(yōu)化，一定程度上增加了計算開銷，故耗時相對較多。與文獻［8－9］相比，本文算法先對各樣本的密度進行計算，再對高密度代表點進行了二次篩選，以確定初始聚類中心集合。因此，在計算量方面開銷較大。除thyroid 數據集的耗時低于文獻［9］外，其他數據集上的耗時均略高于文獻［8－9］。

圖2 初始中心選擇耗時Fig.2 Initial center selection time

從圖3 可見，本文算法的簇中心更新耗時小于K－means 和文獻［8－9］算法。主要原因在于本文算法將與簇內均值距離最近的樣本點作為該簇的臨時中心，使得簇中心的存在更加具體。每一次更新后，簇中心的位置和樣本的分布情況會愈加明了，簇中心的代表性得到增強，從而降低了簇更新耗時。

圖3 簇中心更新耗時Fig.3 Cluster center update time consuming

從圖4、圖5 可知，本文算法在中心點迭代次數、總耗時上總體上優(yōu)于K－means 算法和文獻［8－9］算法。這是因為K－means 算法隨機選擇了初始聚類中心，使得準則函數容易收斂到局部最優(yōu)，且簇更新次數不穩(wěn)定。此外，文獻［8－9］依然沿用均值中心算法完成簇更新，并未對該階段進行優(yōu)化，未能更好地體現臨時中心點在當前簇中的代表性。

圖4 簇中心更新次數Fig.4 Number of cluster center updates

圖5 聚類總耗時Fig.5 Total clustering time

綜上，本文在初始中心選擇階段所提出的密度計算方法，使得初始中心空間分布合理，具有較強的代表性。簇更新后，簇中心的存在清晰明了，在整體上能夠減少簇更新次數，降低運算耗時。

3.2 其它外部評價指標對比

在聚類結果評價方面，除使用上述常用指標外，還使用Rand、Jaccard、Adjusted Rand Index 3 個評價指標［14－17］對5 種樣本的聚類結果加以測試對比。觀察表2～表4，在Rand 指數對比結果中，除Balance 數據集本文算法略低于文獻［8］算法外，其它4 個數據集的Rand 指數均優(yōu)于其它3 種算法；在Jaccard 系數和Adjusted Rand Index 參數對比結果中，本文算法全部優(yōu)于其它3 種算法。從幾種常見聚類指標對比實驗結果中可以看出：本文提出的改進聚類算法穩(wěn)定性更強，聚類質量更高。

表2 Rand 指數比較Tab.2 Comparison of rand index

表3 Jaccard 系數比較Tab.3 Comparison of Jaccard coefficient

表4 Adjusted Rand Index 參數比較Tab.4 Comparison of Adjusted Rand index parameter

4 結束語

本文用改進密度算法對K－means 聚類算法進行了優(yōu)化，解決了密度聚類算法的參數設置敏感、收斂時間長等問題。新算法的初始聚類中心相對分散且具有代表性，能夠在聚類初期反映出樣本的大致分布；在簇更新階段，選取了與簇內均值距離最近的樣本點作為該簇的臨時中心，使得簇中心的位置更加準確，減少了迭代次數和計算開銷。對比測試表明，新算法能夠快速準確逼近全局最優(yōu)解。