基于局部密度信息熵均值的密度峰值聚類算法

唐風(fēng)揚(yáng)，覃仁超，熊 健

(西南科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，四川 綿陽 621010)

0 引言

近幾年，隨著全球存儲(chǔ)信息量與數(shù)據(jù)量的爆炸式增長(zhǎng)，在給各行業(yè)帶來機(jī)遇的同時(shí)也帶來了巨大的挑戰(zhàn)，即如何高效地處理這些信息與數(shù)據(jù)。聚類算法作為數(shù)據(jù)處理的關(guān)鍵技術(shù)，本質(zhì)是將一組數(shù)據(jù)劃分為不重疊的子集的過程，每個(gè)子集都是一個(gè)聚類，所以同一聚類中的點(diǎn)彼此相似，而與其他聚類中的點(diǎn)不相似。聚類算法不僅是數(shù)據(jù)挖掘的一種重要手段，還是機(jī)器學(xué)習(xí)理論與技術(shù)中的重要數(shù)據(jù)預(yù)測(cè)和分析方法之一，在模式識(shí)別[1]、圖像處理[2]、文獻(xiàn)計(jì)量學(xué)，生物信息學(xué)等領(lǐng)域得到了廣泛應(yīng)用。

1 研究現(xiàn)狀

聚類算法常用在無監(jiān)督學(xué)習(xí)中，算法通過學(xué)習(xí)未作標(biāo)記的樣本以此來揭示數(shù)據(jù)的內(nèi)在規(guī)律，完成數(shù)據(jù)的分類。隨著近年來不斷的深入研究，通常將其分為以下幾類，基于劃分的聚類如K-MEANS[3]算法，然而該算法聚類效果的好壞取決于人工選擇的聚類中心且有著對(duì)樣本中的異常點(diǎn)敏感的缺點(diǎn)。為此衍生出了利用聚類中心相互間隔距離較遠(yuǎn)思想的K-MEANS++算法，雖然方法簡(jiǎn)單，但非常有效；而改變中心點(diǎn)選取策略的K-MEDOIDS算法在小樣本的數(shù)據(jù)中有著更好的噪聲魯棒性；利用遺傳算法，粒子群等優(yōu)化算法進(jìn)行初始值尋優(yōu)的多種改進(jìn)方法都有著良好效果。其他經(jīng)典算法中有將空間劃分為矩陣，基于網(wǎng)絡(luò)多分辨率聚類技術(shù)的STING[4]算法和利用層次方法進(jìn)行聚類和規(guī)約數(shù)據(jù)的BRICH[5]算法。DBSCAN[6]算法作為具有代表性的密度聚類算法，提出了密度可接近性與密度可連性的概念，將具有足夠密度大小的區(qū)域劃分成簇，在帶噪聲的空間中能識(shí)別形狀各異的簇，但參數(shù)的人工選擇限制了算法的效果。而為了解決這個(gè)問題，OPTICS[7]算法應(yīng)運(yùn)而生，算法為聚類的分析生成簇的排序，從這個(gè)排序中可以得到DBSCAN算法的多種聚類結(jié)果。這些算法在性能上有很大差異，如K-MEANS只能識(shí)別凸球形簇，STING算法具有很快的速度，但是準(zhǔn)確度不高，而BRICH算法可以簡(jiǎn)單對(duì)數(shù)據(jù)進(jìn)行預(yù)處理并識(shí)別噪聲點(diǎn)，但在數(shù)據(jù)是非超球體的分布簇的情況下效果一般。DBSCAN在不規(guī)則簇的識(shí)別上效果顯著，也有不錯(cuò)的抗噪聲能力，但在面對(duì)數(shù)據(jù)維度升高時(shí)效果明顯下降[8]。

2014年6月，Rodriguez等人在Science上發(fā)表了DPC[9]算法，這是一種基于距離和密度的算法，能夠找到任意形狀的聚類中心，與傳統(tǒng)算法相比，該算法無需迭代目標(biāo)函數(shù)就能找到高密度點(diǎn)，并且實(shí)現(xiàn)簡(jiǎn)單。然而該算法需要通過經(jīng)驗(yàn)設(shè)置距離閾值dc完成密度的計(jì)算。目前為止許多學(xué)者對(duì)算法進(jìn)行了改進(jìn)，其中一部分改進(jìn)算法根據(jù)數(shù)據(jù)集自身數(shù)據(jù)情況自適應(yīng)求得最佳距離閾值dc[10-14]，這種做法一定程度上優(yōu)化了距離閾值dc的選擇，但各方法的適用數(shù)據(jù)集不同。文獻(xiàn)[15]通過構(gòu)建Ball-Tree 縮小樣本局部密度和距離的計(jì)算范圍減少了計(jì)算量，文獻(xiàn)[16]基于塊的不相似性度量計(jì)算樣本間的相似度,引入樣本的 K近鄰度量,定義新的局部密度。文獻(xiàn)[17]等通過改變聚類中心的定義，并將鄰域中的密度極值點(diǎn)確定為聚類中心，然后會(huì)選擇到超過簇?cái)?shù)目的聚類中心，文獻(xiàn)[18]等引入K近鄰的思想來計(jì)算距離閾值dc和每個(gè)點(diǎn)的局部密度，文獻(xiàn)[19]等定義了從屬的概念來描述相對(duì)密度關(guān)系，并使用從屬的數(shù)量作為識(shí)別聚類中心的標(biāo)準(zhǔn)。文獻(xiàn)[20]等利用網(wǎng)絡(luò)劃分的方法，解決計(jì)算歐氏距離時(shí)花費(fèi)過多時(shí)間的問題。文獻(xiàn)[21]等不僅引入KNN思想解決局部密度的計(jì)算，并且運(yùn)用PCA對(duì)高維數(shù)據(jù)降維。

本文針對(duì)距離閾值dc選擇存在的問題，定義局部密度捕獲范圍并利用局部密度信息熵均值進(jìn)行優(yōu)化，通過設(shè)置距離閾值一定倍數(shù)的參數(shù)確定局部密度捕獲范圍，使得在分類錯(cuò)誤的情況下通過對(duì)相對(duì)距離進(jìn)行密度的加權(quán)重新獲得正確的分類數(shù)量和分類中心。通過DPC算法與信息熵的結(jié)合使用，即使在不規(guī)則圖形中也能夠排除異常點(diǎn)的干擾，準(zhǔn)確快速地找到正確的分類中心和分類數(shù)量，實(shí)驗(yàn)證明在不同的數(shù)據(jù)集中均取得了良好的效果。

2 密度峰值聚類算法

2.1 算法原理

DPC算法認(rèn)為簇中心擁有如下特征：(1)數(shù)據(jù)點(diǎn)與其他密度大的點(diǎn)有相對(duì)遠(yuǎn)的距離[22]；(2)數(shù)據(jù)點(diǎn)本身密度大于包圍它周圍的點(diǎn)。通過定義ρi和δi來表示數(shù)據(jù)點(diǎn)的密度與相對(duì)距離，然后選取兩者中雙方值都相對(duì)較大的點(diǎn)作為簇中心，最后將其他非中心點(diǎn)歸到其最近的更高密度點(diǎn)完成聚類。

2.2 算法過程

首先通過計(jì)算得到對(duì)于數(shù)據(jù)集S={x1,x2,x3,...,xn}中，數(shù)據(jù)點(diǎn)xi與xj的歐氏距離dij，計(jì)算公式如式(1):

(1)

計(jì)算數(shù)據(jù)點(diǎn)xi的局部密度ρi。

截?cái)嗪擞?jì)算公式如式(2):

(2)

dij為數(shù)據(jù)點(diǎn)xi與xj的歐式距離，dc為能囊括總數(shù)據(jù)量1%至2%的距離閾值，其中函數(shù)X如式(3)所示：

(3)

高斯核計(jì)算公式如式(4)：

(4)

截?cái)嗪艘噪x散值估計(jì)出的密度全為整數(shù)，有重復(fù)值，而高斯核以連續(xù)值估計(jì)出的密度因此不會(huì)產(chǎn)生重復(fù)值，因此當(dāng)不同點(diǎn)擁有相同局部密度的情況下使用高斯核進(jìn)行計(jì)算會(huì)取得更好的效果，故本文中采取高斯核密度計(jì)算公式。

計(jì)算數(shù)據(jù)點(diǎn)xi的相對(duì)距離δi,公式如式(5)～(6):

(5)

(6)

公式(5)中δi表示對(duì)于數(shù)據(jù)點(diǎn)xi，到有高于它局部密度點(diǎn)的最近距離，(6)中δi是當(dāng)其數(shù)據(jù)點(diǎn)xi在數(shù)據(jù)集S中局部密度最大時(shí)的距離。一般密度大的數(shù)據(jù)點(diǎn)的距離參數(shù)δi要比其它鄰近點(diǎn)大。

在計(jì)算完每個(gè)點(diǎn)的局部密度ρi和相對(duì)距離δi之后，以密度為橫坐標(biāo)，相對(duì)距離為縱坐標(biāo)畫出相對(duì)距離/密度圖在其中選取密度和距離值相對(duì)大的點(diǎn)作為聚類中心。不過文獻(xiàn)[4]中提到通過設(shè)置決策函數(shù)：

γi=ρi×δi

(7)

來繪制決策圖賦值確定聚類中心。其中具有更大γi的點(diǎn)xi會(huì)具有更高成為聚類中心點(diǎn)的可能性。為此，將γi降序排序，在二維平面圖中畫出決策圖，找到γi較大的點(diǎn)xi作為聚類中心，DPC算法將非中心點(diǎn)歸并到密度比當(dāng)前點(diǎn)高且距離最近點(diǎn)以完成聚類。

2.3 算法的不足

DPC極其依賴參數(shù)距離閾值dc的選擇，相同的數(shù)據(jù)集在不同的距離閾值dc下有非常大的差別，在Rodriguez等人的文章中指出dc選擇能囊括總數(shù)據(jù)的1%～2%數(shù)量(下文簡(jiǎn)稱dc=n%)的數(shù)值，這種局限性突出在一些特殊的數(shù)據(jù)集中，并且對(duì)不同的數(shù)據(jù)集難以進(jìn)行距離閾值dc的選擇。

目前普遍認(rèn)為距離閾值dc選擇過小時(shí)，可能會(huì)在同一簇內(nèi)找出多個(gè)密度峰值，從而得到過多的聚類中心導(dǎo)致聚類失敗，極端情況下距離閾值dc小于數(shù)據(jù)集中各個(gè)點(diǎn)的最小歐氏距離，這時(shí)每個(gè)數(shù)據(jù)點(diǎn)都將單獨(dú)成為一個(gè)類別；如果距離閾值dc選擇過大，會(huì)使得區(qū)分度過低，從而不同的簇往往會(huì)被分到同一聚類中心，導(dǎo)致簇中心的少選從而聚類失敗，極端情況是距離閾值dc超過了數(shù)據(jù)點(diǎn)中各個(gè)點(diǎn)的最大歐式距離，這會(huì)把所有數(shù)據(jù)歸為一個(gè)類別。

3 基于局部密度信息熵均值優(yōu)化的聚類算法

3.1 信息熵

假設(shè)X為隨機(jī)型離散變量，那么它在有限范圍內(nèi)的取值R={x1,x2,x3,...,xn},而其中xi出現(xiàn)的概率為Pi，同時(shí)設(shè)Pi=P{X=xi}，則對(duì)于x信息熵的公式定義為式(8)所示：

(8)

信息熵作為一種計(jì)算屬性權(quán)重的經(jīng)典算法一般用來計(jì)算數(shù)據(jù)的離散度。熵值一般與離散程度成反比，即數(shù)據(jù)某指標(biāo)越小的熵值說明該指標(biāo)離散程度越大，同時(shí)該指標(biāo)也有更大的信息量。

3.2 局部密度捕獲范圍

針對(duì)DPC算法在計(jì)算相對(duì)距離和密度時(shí)并未考慮數(shù)據(jù)點(diǎn)空間分布特性的影響，而是從全局的角度出發(fā)通過使鄰近樣本數(shù)占比達(dá)到全部樣本的一定數(shù)量，計(jì)算距離閾值來確定密度進(jìn)而算出相對(duì)距離的時(shí)候數(shù)據(jù)密度和相對(duì)距離分布不均勻，多個(gè)密度峰值被劃分至同一個(gè)聚類中心和一個(gè)簇中心存在多個(gè)密度峰值的問題。

本文提出一種局部密度捕獲范圍，用來捕獲數(shù)據(jù)點(diǎn)附近一定范圍內(nèi)的點(diǎn)以供后續(xù)計(jì)算使用，通過設(shè)置參數(shù)w來確定某點(diǎn)的局部密度捕獲范圍。

定義1:局部密度捕獲范圍。局部密度捕獲范圍表示能包含某一區(qū)域內(nèi)全部數(shù)據(jù)點(diǎn)的范圍，記作w如式(9)所示：

w=c×dc

(9)

其中:參數(shù)c在多次實(shí)驗(yàn)中顯示取距離閾值dc的0.5～5倍時(shí)有最佳效果。

3.3 局部密度信息熵均值的計(jì)算

本文中將信息熵與局部密度相結(jié)合，通過計(jì)算某點(diǎn)的局部密度信息熵均值，確定該點(diǎn)相對(duì)于周圍點(diǎn)的密度分布情況。相對(duì)距離相近但局部密度不同的點(diǎn)，在決策圖上通常難以區(qū)分，但可以通過以其相對(duì)距離乘以局部密度信息熵均值來解決，在相對(duì)距離相近的情況下，局部密度相差小的點(diǎn)相對(duì)局部密度相差大的點(diǎn)擁有更大的局部密度信息熵均值，從而讓局部密度相差大的點(diǎn)的相對(duì)距離變小,進(jìn)而使決策圖中的相應(yīng)的值變小，以此來區(qū)別出數(shù)據(jù)密度點(diǎn)中可能被誤分為聚類中心的點(diǎn)。

定義2：局部密度信息熵均值。局部密度信息熵均值表示局部范圍內(nèi)數(shù)據(jù)點(diǎn)的分布情況，某一點(diǎn)的局部密度信息熵的值與該點(diǎn)附近密度分布離散程度成反比，記作H(X)。

局部密度信息熵均值的計(jì)算公式如式 (10)所示：

(10)

其中:

(11)

N為點(diǎn)xi半徑小于局部密度捕獲范圍w內(nèi)的所有點(diǎn)的數(shù)量。

在加權(quán)之后由于權(quán)數(shù)值較小，故為使加權(quán)效果更加顯著，在反復(fù)實(shí)驗(yàn)中類比sigmoid，log等函數(shù)之后發(fā)現(xiàn)log一類的對(duì)數(shù)函數(shù)由于沒有明確上界會(huì)將密度較大的點(diǎn)的相對(duì)距離過于放大，從而難以產(chǎn)生效果，而sigmoid函數(shù)無法產(chǎn)生有效的區(qū)分度，但使用反正切函數(shù)acrtan能夠更好地將正確簇中心與錯(cuò)誤簇中心區(qū)別，故選用使用反正切公式來處理H(X)得出全新加權(quán)系數(shù)H′(X)如式(12)所示：

(12)

3.4 加權(quán)后相對(duì)距離

使用原相對(duì)聚類δ新加權(quán)系數(shù)H′(X)相乘得到加權(quán)后相對(duì)距離δe如式(13)所示。

δe=H′(X)×δ

(13)

3.5 新的決策函數(shù)γe

使用新的加權(quán)相對(duì)距離δe與密度ρ相乘得到γe如式(14)，從而繪制新的決策圖。

γe=ρ×δe

(14)

3.6 聚類中心的選取

如圖1所示，點(diǎn)A和點(diǎn)B屬同一簇，但點(diǎn)B具有較高的局部密度和距離δ，在DPC中在距離閾值dc取值較小時(shí)會(huì)把A,B點(diǎn)看作兩個(gè)聚類中心點(diǎn)，而LDDPC算法通過對(duì)相對(duì)距離δe進(jìn)行加權(quán)，使得B的相對(duì)距離δe變小，從而將A,B點(diǎn)歸為同一簇中完成正確的聚類。

圖1 錯(cuò)誤聚類示例

經(jīng)過反正切公式(11)和相對(duì)距離加權(quán)公式(12)的運(yùn)算之后，在γe上決策圖的聚類中心變得清晰可分。在決策圖中很容易看到非聚類中心點(diǎn)之間排列緊密，且相互之間的差值非常小，這時(shí)只需選取決策函數(shù)γe較大且相互差距大的點(diǎn)作為聚類中心即可。經(jīng)LDDPC算法處理后相比DPC算法能夠更快速更直接地選取正確的聚類中心。

4 算法流程

算法處理流程如下。

步驟1：輸入待檢測(cè)的數(shù)據(jù)集S={x1,x2,x3,...,xn}和dc以及參數(shù)w；

步驟2：將數(shù)據(jù)集按照公式(1)求出歐氏距離；

步驟3：分別代入公式(4)～(6)求出每個(gè)數(shù)據(jù)點(diǎn)xi的ρi與δi；

步驟4：按照公式(10)～(12)算出每個(gè)數(shù)據(jù)點(diǎn)的局部密度信息熵均值H(X)和加權(quán)后的系數(shù)H′(X)；

步驟5：根據(jù)公式(13)和公式(14)算出加權(quán)后每個(gè)點(diǎn)xi的相對(duì)距離δei以及γei；

步驟6：根據(jù)γe的決策圖計(jì)算出聚類中心；

步驟7：將每個(gè)數(shù)據(jù)按照最近距離數(shù)據(jù)點(diǎn)的類別分類；

步驟8：輸出實(shí)驗(yàn)結(jié)果。

5 實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)環(huán)境

LDDPC算法通過python3.7.9實(shí)現(xiàn)與處理。實(shí)驗(yàn)環(huán)境：操作系統(tǒng)為win10 64位，CPU為I5-7300HQ，主頻2.5 GHz，內(nèi)存為16 G。為了驗(yàn)證算法性能，將在下文的實(shí)驗(yàn)中把DPC算法與LDDPC算法效果相比較。

5.2 實(shí)驗(yàn)說明

實(shí)驗(yàn)一與實(shí)驗(yàn)二數(shù)據(jù)集詳見表1，為了驗(yàn)證算法的有效性和適應(yīng)性，故實(shí)驗(yàn)中選取的dc值中即有小于1%，大于2%也有1%～2%正常取值區(qū)間內(nèi)DPC算法無法正常發(fā)揮效果的值,通過實(shí)驗(yàn)驗(yàn)證錯(cuò)誤聚類中的聚類過多和過少的情況下LDDPC算法仍能發(fā)揮的效果。

表1 實(shí)驗(yàn)一與實(shí)驗(yàn)二所用數(shù)據(jù)集

5.3 實(shí)驗(yàn)一：DPC算法分類錯(cuò)誤時(shí)通過LDDPC算法獲得正確分類

圖2至圖4為在Aggregation數(shù)據(jù)集中，當(dāng)dc=1.3%時(shí)的效果圖，決策圖和聚類結(jié)果圖，圖2為密度ρ和相對(duì)距離δ的原始分布，圖(a)為原始算法得出的分布情況而圖(b)為L(zhǎng)DDPC算法處理后(即密度ρ和加權(quán)后相對(duì)距離距離δe)的分布，圖3和圖4中可以看到圖(a)DPC算法中簇?cái)?shù)過多而導(dǎo)致分類的失敗，決策圖中能看到超過簇?cái)?shù)7個(gè)的相對(duì)大的γ值，而圖(b)LDDPC算法處理后，在決策圖上能夠明顯分辨出7個(gè)相對(duì)大的γe值，從而成功分為7個(gè)類。在圖5至圖7為數(shù)據(jù)集Flame中，為dc取值為3.6%時(shí)的對(duì)比圖,從圖5(a)，圖6(a)，圖7(a)中可以明顯看出距離閾值取值的失敗導(dǎo)致出現(xiàn)4個(gè)簇中心的多分類情況，此時(shí)同一個(gè)簇中擁有多個(gè)聚類峰值，而在圖5(b)，圖6(b)，圖7(b)中在LDDPC算法的處理下決策圖中僅出現(xiàn)2個(gè)相對(duì)較大的γe值，說明同一簇中多余的聚類峰值的消失，于是數(shù)據(jù)成功分成2個(gè)類別。

圖2 在Aggregation數(shù)據(jù)集下的相對(duì)距離/密度圖對(duì)比圖

圖3 在Aggregation數(shù)據(jù)集下的決策圖對(duì)比圖

圖4 在Aggregation數(shù)據(jù)集下的聚類結(jié)果對(duì)比圖

圖5 在Flame數(shù)據(jù)集下的相對(duì)距離/密度對(duì)比圖

圖6 在Flame數(shù)據(jù)集下的決策圖對(duì)比圖

圖7 在Flame數(shù)據(jù)集下的聚類結(jié)果對(duì)比圖

通過實(shí)驗(yàn)可以看到以上數(shù)據(jù)集均被錯(cuò)誤地分成了多個(gè)類別，并且從決策圖可以看出分布并不明顯，稍有不慎就會(huì)誤選，將密度ρ和相對(duì)距離δ乘積γ較大的點(diǎn)選為聚類中心，導(dǎo)致同一簇中存在多個(gè)聚類峰值的情況，而在LDDPC算法下通過γe構(gòu)建決策圖從而被正確的分類，并且新決策圖中γe值顯示非中心點(diǎn)與中心點(diǎn)具有更大的差值，相比原決策圖更加清晰可分，不會(huì)因不慎而錯(cuò)選多選而導(dǎo)致出現(xiàn)不正確的簇?cái)?shù)的情況出現(xiàn)。

5.4 實(shí)驗(yàn)二：DPC算法分類正確時(shí)獲得更加清晰的決策圖

圖8至圖10展示了R15數(shù)據(jù)集在dc=2%時(shí)正確聚類情況，通過圖8和圖9的對(duì)比可以看出，在LDDPC算法的處理下，相比DPC算法中原來的相對(duì)距離δ，經(jīng)局部密度信息熵加權(quán)后的加權(quán)相對(duì)距離δe具有更大的值，聚類中心點(diǎn)和非中心點(diǎn)在新決策圖中的γe值與原決策圖中的γ值相比差值變大，這使在決策圖中尋找聚類中心時(shí)更加容易。同理圖11至圖13是數(shù)據(jù)集D31在dc=2%時(shí)，經(jīng)過LDDPC算法處理前后的對(duì)比，圖11(a)與圖11(b)相比DPC算法區(qū)分度更明顯，相對(duì)距離δ整體上移，在決策圖中同樣體現(xiàn)為γe值的整體上移，與R15中同樣在處理后增加了決策圖的辨識(shí)度，能夠更好地把真實(shí)簇中心從其他高密度峰值的虛假簇中心中分離，從而能夠更加精確快速地完成31個(gè)類別的數(shù)據(jù)集的分類。

圖8 在R15數(shù)據(jù)集下的相對(duì)距離/密度對(duì)比圖

圖9 在R15數(shù)據(jù)集下的決策圖對(duì)比圖

圖10 在R15數(shù)據(jù)集下的聚類結(jié)果對(duì)比圖

圖11 在D31數(shù)據(jù)集下的相對(duì)距離/密度對(duì)比圖

圖12 在D31數(shù)據(jù)集下的決策圖對(duì)比圖

圖13 在D31數(shù)據(jù)集下的聚類結(jié)果對(duì)比圖

以上實(shí)驗(yàn)說明數(shù)據(jù)集在LDDPC算法處理過相對(duì)距離δ之后在不影響DPC算法本身效果的同時(shí)還使得在決策圖上尋找聚類中心時(shí)更加容易。

5.5 實(shí)驗(yàn)三：高維數(shù)據(jù)集測(cè)試

為了進(jìn)一步驗(yàn)證算法的有效性，實(shí)驗(yàn)三中選取了UCI數(shù)據(jù)集中的3個(gè)高維數(shù)據(jù)集分別為Iris,Wine,Seed進(jìn)行測(cè)試，實(shí)驗(yàn)選用的數(shù)據(jù)集詳細(xì)信息如表2，DPC與LDDPC算法實(shí)驗(yàn)結(jié)果的對(duì)比如表3。

表2 實(shí)驗(yàn)三所用數(shù)據(jù)集

表3 實(shí)驗(yàn)三實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)三在dc值的選擇上仍然選擇了一個(gè)小于1%，一個(gè)大于2%，一個(gè)介于1%～2%之間且分類錯(cuò)誤的3個(gè)具有代表性的dc值。在圖14中可以看到(a)圖被誤分成了2類，而(b)圖中決策圖上出現(xiàn)了3個(gè)γe值相對(duì)大的點(diǎn)，通過對(duì)相對(duì)距離進(jìn)行的加權(quán)找到了隱藏的真實(shí)聚類中心，即一共3個(gè)正確的聚類中心；而圖15(a)，圖16(a)圖中被多分成了4類的情況下，經(jīng)過LDDPC算法處理之后明顯看到?jīng)Q策圖上γe值相對(duì)大的點(diǎn)由4個(gè)變?yōu)?個(gè)，即通過對(duì)相對(duì)距離的加權(quán)使同一簇中原有的兩個(gè)密度峰值減少為一個(gè)，排除了錯(cuò)誤的聚類中心，數(shù)據(jù)集成功地被重新分成了正確的3類，測(cè)試效果表明算法在DPC分類錯(cuò)誤時(shí)能夠使分類正確，且可以明顯提升算法的準(zhǔn)確率。

圖14 在Iris數(shù)據(jù)集下的決策圖對(duì)比圖

圖15 在Wine數(shù)據(jù)集下的決策圖對(duì)比圖

圖16 在Seed數(shù)據(jù)集下的決策圖對(duì)比圖

6 結(jié)束語

針對(duì)傳統(tǒng)的DPC算法在距離閾值選取不當(dāng)時(shí)無法正確分類的情況，本文提出了局部密度捕獲范圍和利用局部密度信息熵均值的加權(quán)算法(LDDPC)，成功在距離閾值使分類錯(cuò)誤的情況下通過對(duì)數(shù)據(jù)點(diǎn)的相對(duì)距離進(jìn)行其局部密度信息熵均值的加權(quán)使分類正確。該算法克服了DPC算法對(duì)距離閾值取值敏感的缺點(diǎn)，在數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果可以證明，通過LDDPC算法在DPC算法的距離閾值取值不當(dāng)導(dǎo)致分類錯(cuò)誤時(shí)，得以正確分類，并且提高準(zhǔn)確率。