基于改進(jìn)密度的簇內(nèi)均值最小距離聚類算法

段桂芹

（廣東松山職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)與信息工程學(xué)院，廣東 韶關(guān) 512126）

0 引 言

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

1 相關(guān)算法研究現(xiàn)狀

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

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

2 密度聚類算法改進(jìn)

改進(jìn)的密度聚類算法，由初始中心選擇和簇中心迭代計(jì)算兩部分構(gòu)成。

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

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

2.1 基本概念與公式

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

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

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

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

定義3樣本xi的密度為：

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

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

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

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

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

定義6候選代表點(diǎn)間的距離矩陣定義為

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

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

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

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

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

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

2.2 算法描述

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

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

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

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

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

步驟6重復(fù)運(yùn)行步驟5，直至｜Z ｜＝k；

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

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

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

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

2.3 算法復(fù)雜度分析

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

3 實(shí)驗(yàn)仿真與分析

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

表1 UCI 數(shù)據(jù)集Tab.1 UCI dataset

3.1 算法性能對比與分析

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

圖1 聚類準(zhǔn)確率Fig.1 Clustering accuracy

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

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

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

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

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

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

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

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

3.2 其它外部評價(jià)指標(biāo)對比

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

表2 Rand 指數(shù)比較Tab.2 Comparison of rand index

表3 Jaccard 系數(shù)比較Tab.3 Comparison of Jaccard coefficient

表4 Adjusted Rand Index 參數(shù)比較Tab.4 Comparison of Adjusted Rand index parameter

4 結(jié)束語

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