一種基于逆近鄰和影響空間的DBSCAN聚類分析算法

劉宏凱 張繼福

(太原科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 山西 太原 030024)

0 引 言

作為數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)的主要研究分支之一，聚類分析是一種廣泛使用的無監(jiān)督學(xué)習(xí)技術(shù)。聚類分析[1]在沒有使用任何先驗(yàn)知識(shí)情況下，側(cè)重于將數(shù)據(jù)集中的數(shù)據(jù)對(duì)象聚到簇中，目的是使簇內(nèi)的數(shù)據(jù)對(duì)象相似性最大，并使不同簇間的數(shù)據(jù)對(duì)象相似性最小?；诿芏鹊木垲愃惴╗2]是一種典型聚類分析方法，其具有處理和識(shí)別噪聲的能力，發(fā)現(xiàn)具有任意形狀的簇和自動(dòng)識(shí)別簇的能力等優(yōu)點(diǎn)，并廣泛地應(yīng)用于化學(xué)[3]、模式識(shí)別[4]、圖像處理[5]、機(jī)器學(xué)習(xí)[6]和生物學(xué)[7]等領(lǐng)域。

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)作為一類有代表性的密度聚類分析方法，具有聚類速度快、預(yù)設(shè)參數(shù)對(duì)聚類結(jié)果的影響小和有效識(shí)別噪聲對(duì)象等優(yōu)點(diǎn)[8]。但其在聚類簇?cái)U(kuò)展過程中，由于核心對(duì)象的K近鄰與逆近鄰并集中包含的其他核心對(duì)象[8]可能屬于不同密度的相鄰聚類簇，并將原本屬于不同密度簇的核心對(duì)象聚到同一個(gè)聚類簇中，從而造成在聚類簇?cái)U(kuò)展過程中，無法區(qū)分不同密度的相鄰聚類簇，未能有效地體現(xiàn)真實(shí)的數(shù)據(jù)分布。本文采用逆近鄰和影響空間相結(jié)合的思想，提出了一種密度聚類分析方法。該方法利用了逆近鄰和影響空間形成聚類簇，數(shù)據(jù)對(duì)象與其影響空間中其他核心對(duì)象的鄰域關(guān)系是對(duì)稱的，從而保證了同一影響空間中核心對(duì)象屬于同一密度的聚類簇，能夠較好地估計(jì)鄰域密度分布，并識(shí)別出不同密度的相鄰聚類簇。

1 相關(guān)工作

聚類分析是數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等領(lǐng)域中主要研究?jī)?nèi)容之一，可劃分為基于統(tǒng)計(jì)[9]、基于分層[10]、基于模型[11]、基于密度、基于網(wǎng)格[12]和基于子空間[13-16]的方法等?；诿芏鹊木垲惙治鍪菍⒚芏却笥陬A(yù)設(shè)閾值的區(qū)域定義為密集區(qū)域，并通過連接密集區(qū)域形成聚類簇。

密度聚類作為一類聚類分析方法，具有能夠發(fā)現(xiàn)任意形狀的聚類簇，可以很好地描述真實(shí)的數(shù)據(jù)分布特征，不需要預(yù)先設(shè)置要形成聚類簇的數(shù)量，數(shù)據(jù)集中數(shù)據(jù)對(duì)象的順序與聚類結(jié)果無關(guān)等優(yōu)點(diǎn)。Ester等[17]提出了著名的DBSCAN算法。此算法在聚類簇的密度不均勻、簇間距相差大時(shí)，聚類質(zhì)量較差；對(duì)于高維數(shù)據(jù)，存在“維數(shù)災(zāi)難”問題。Vadapalli等[18]提出了RECORD算法。該算法無須輸入任何預(yù)設(shè)參數(shù)，可以很好地反映數(shù)據(jù)集分布特征，但當(dāng)一個(gè)離群點(diǎn)距離兩個(gè)聚類簇的距離相等時(shí)，此算法對(duì)離群點(diǎn)簇標(biāo)簽的分配是不確定的。王晶等[19]提出了密度最大值聚類算法(MDCA)。其使用密度而不是初始數(shù)據(jù)對(duì)象作為考察簇歸屬情況的依據(jù)，能夠發(fā)現(xiàn)任意形狀的聚類簇并且不依賴初始數(shù)據(jù)對(duì)象的選擇，但此算法需要在聚類前確定密度閾值；不適合數(shù)據(jù)集密度差異較大或整體密度基本相同的情況。夏魯寧等[20]提出了可以自動(dòng)確定Eps和minPts參數(shù)的SA-DBSCAN算法，但其對(duì)于密度不同的相鄰聚類簇聚類效果較差。Cassisi等[21]提出了ISDBSCAN算法。此算法進(jìn)行離群點(diǎn)檢測(cè)階段會(huì)錯(cuò)誤地將核心對(duì)象識(shí)別為噪聲對(duì)象除去，并且引入了第二個(gè)參數(shù)，降低了聚類精度。He等[22]提出了MR-DBSCAN并行算法，此算法在嚴(yán)重偏斜的數(shù)據(jù)環(huán)境中也能實(shí)現(xiàn)理想的負(fù)載平衡。Rodriguez等[23]提出了密度峰值聚類算法(DPC),其能快速發(fā)現(xiàn)任意數(shù)據(jù)集的聚類簇中心，并能高效地進(jìn)行聚類與離群點(diǎn)去除，但該算法在數(shù)據(jù)集規(guī)模小時(shí)，主觀選擇的截?cái)嗑嚯x對(duì)聚類結(jié)果影響較大。Lü等[24]提出了ISBDBSCAN算法。其在ISDBSCAN算法的基礎(chǔ)上，提出了非核心對(duì)象聚類的方法，但當(dāng)兩個(gè)核心對(duì)象到一個(gè)非核心對(duì)象的距離相等時(shí)，此算法對(duì)非核心對(duì)象簇標(biāo)簽的分配是不確定的。Bryant等[8]提出了RNNDBSCAN算法，該算法只需要一個(gè)預(yù)設(shè)參數(shù)，但由于采用K近鄰與逆近鄰的并集進(jìn)行聚類簇?cái)U(kuò)展無法識(shí)別不同密度的相鄰聚類簇，降低了聚類精度，并且聚類簇?cái)U(kuò)展過程中占用內(nèi)存過大，降低了聚類效率。Parmar等[25]提出了基于殘差的密度峰值聚類算法(REDPC)，采用殘差計(jì)算來測(cè)量鄰域內(nèi)的局部密度，為聚類簇質(zhì)心的識(shí)別提供了更好的決策圖。

綜上所述，密度聚類分析方法存在著當(dāng)數(shù)據(jù)集大時(shí)，時(shí)間復(fù)雜度高；“維度災(zāi)難”，無法適用于高維數(shù)據(jù)集；識(shí)別邊界點(diǎn)的簇標(biāo)簽不確定；當(dāng)各個(gè)聚類簇的密度不均勻或聚類簇間的距離相差很大時(shí)，未能有效地識(shí)別或區(qū)分不同密度的相鄰聚類簇等缺點(diǎn)，從而影響了聚類分析的精度和效率。

2 相關(guān)定義

2.1 K近鄰與逆近鄰

K近鄰[26]是一種基本分類與回歸方法，其目的是查找數(shù)據(jù)對(duì)象在數(shù)據(jù)集D的K密度聚類個(gè)最近鄰數(shù)據(jù)對(duì)象。K近鄰可以應(yīng)用于分類、聚類、離群點(diǎn)檢測(cè)、模式識(shí)別和入侵檢測(cè)等領(lǐng)域中。逆近鄰是在K近鄰的基礎(chǔ)上提出來，其含義就是在數(shù)據(jù)集D中找出將給定數(shù)據(jù)對(duì)象y作為其K近鄰的數(shù)據(jù)對(duì)象集合。數(shù)據(jù)對(duì)象的逆近鄰是基于全局的角度來檢查它的鄰域，數(shù)據(jù)分布的改變會(huì)導(dǎo)致每個(gè)數(shù)據(jù)對(duì)象的逆近鄰發(fā)生改變，并且不會(huì)像K近鄰一樣隨著維數(shù)的增加會(huì)出現(xiàn)“維數(shù)災(zāi)難”問題。

定義1(K近鄰) 數(shù)據(jù)對(duì)象x的NNK(x)表示為距離x最近的K個(gè)數(shù)據(jù)對(duì)象的集合，其滿足以下條件：

?y∈D/{x,NNK(x)},z∈NNK(x):dist(x,z)

定義2(逆近鄰) 數(shù)據(jù)對(duì)象x的RNN(x)表示為某些數(shù)據(jù)對(duì)象的K近鄰中包含數(shù)據(jù)對(duì)象x的數(shù)據(jù)對(duì)象集合，其滿足以下條件：

?x,y∈D:x∈NNK(y),y∈RNN(x)

2.2 密度聚類

對(duì)于任意給定數(shù)據(jù)集D，其所包含的數(shù)據(jù)對(duì)象數(shù)為n=|D|，任意數(shù)據(jù)對(duì)象x∈D含有d維屬性，RNN(x)表示數(shù)據(jù)對(duì)象x的逆近鄰集，NNK(x)表示數(shù)據(jù)對(duì)象x的K近鄰集，dist(x,y)表示數(shù)據(jù)對(duì)象x和y之間的歐氏距離。參照文獻(xiàn)[8]，相關(guān)概念定義如下：

定義3(相似性距離度量) 在數(shù)據(jù)集D中，數(shù)據(jù)對(duì)象x和y的相似性度量dist(x,y)定義如下：

(1)

定義4(核心對(duì)象、邊界對(duì)象、噪聲對(duì)象) 在數(shù)據(jù)集D中，如果數(shù)據(jù)對(duì)象x的逆近鄰|RNN(x)|≥K，則稱x為核心對(duì)象。如果數(shù)據(jù)對(duì)象x的逆近鄰|RNN(x)|

定義5(直接密度可達(dá)性) 如果數(shù)據(jù)對(duì)象y直接密度可達(dá)數(shù)據(jù)對(duì)象x，則其滿足以下條件：

?x,y∈D:x∈NNK(y)Λ|RNN(y)|≥K

因?yàn)閿?shù)據(jù)對(duì)象的K近鄰集關(guān)系是非對(duì)稱的，所以核心對(duì)象之間的直接密度可達(dá)性是非對(duì)稱的。因?yàn)楹诵膶?duì)象與非核心對(duì)象之間的直接密度可達(dá)性也是非對(duì)稱的，所以非核心對(duì)象不具有直接密度可達(dá)性。

定義6(密度可達(dá)性) 密度可達(dá)性是直接密度可達(dá)性的擴(kuò)展，如果數(shù)據(jù)對(duì)象y密度可達(dá)數(shù)據(jù)對(duì)象x，則其滿足以下條件：存在數(shù)據(jù)對(duì)象序列x1,x2,…,xm，xm可由xm-1直接密度可達(dá)，其中:

?x1,x2,…,xm:x1=yΛxm=xΛ|RNN(y)|≥K

定義7(密度連接) 如果存在數(shù)據(jù)對(duì)象z，使得數(shù)據(jù)對(duì)象x和y可從數(shù)據(jù)對(duì)象z密度可達(dá)，則數(shù)據(jù)對(duì)象x和y是密度連接的。密度連接對(duì)于所有的數(shù)據(jù)對(duì)象都具有對(duì)稱性。

定義8(聚類簇) 如果數(shù)據(jù)集D中存在非空聚類簇C，則滿足條件：(1) 對(duì)于數(shù)據(jù)對(duì)象x和y，若數(shù)據(jù)對(duì)象x∈C且x密度可達(dá)數(shù)據(jù)對(duì)象y，則數(shù)據(jù)對(duì)象y∈C;(2) 對(duì)于數(shù)據(jù)對(duì)象x和y，有x∈C，y∈C，則x是密度連接于y。

2.3 影響空間

定義9(影響空間[18]) 在數(shù)據(jù)集D中，將數(shù)據(jù)對(duì)象x∈D的逆近鄰集RNN(x)與K近鄰集NNK(x)的交集定義為x的影響空間IsK(x)，且滿足以下條件：

IsK(x)=RNN(x)∩NNK(x)

3 基于逆近鄰和影響空間的密度聚類

3.1 影響空間與聚類簇?cái)U(kuò)展

在文獻(xiàn)[8]中，RNNDBSCAN算法采用了K近鄰與逆近鄰的并集進(jìn)行擴(kuò)展聚類簇。由定義1和定義2可知，由于數(shù)據(jù)對(duì)象K近鄰的鄰域關(guān)系和逆近鄰的鄰域關(guān)系都不具有對(duì)稱性，因此，數(shù)據(jù)對(duì)象與其K近鄰和逆近鄰并集中數(shù)據(jù)對(duì)象的鄰域關(guān)系也不具有對(duì)稱性。由定義5可知，數(shù)據(jù)對(duì)象與其K近鄰和逆近鄰并集中數(shù)據(jù)對(duì)象的直接密度可達(dá)性是非對(duì)稱的，不能保證數(shù)據(jù)對(duì)象與其K近鄰與逆近鄰并集中的數(shù)據(jù)對(duì)象同屬于相同密度的聚類簇。在密度聚類分析中，采用K近鄰與逆近鄰的并集進(jìn)行聚類簇?cái)U(kuò)展無法區(qū)分不同密度的相鄰聚類簇，從而造成聚類效果無法真實(shí)地反映數(shù)據(jù)對(duì)象的分布特征。

由定義5可知，因數(shù)據(jù)對(duì)象的K近鄰關(guān)系是非對(duì)稱的，則數(shù)據(jù)對(duì)象間的直接密度可達(dá)是非對(duì)稱的。由定義9可知，任意數(shù)據(jù)對(duì)象x∈D與其影響空間中的其他數(shù)據(jù)對(duì)象間互為K近鄰，則數(shù)據(jù)對(duì)象x與其影響空間中數(shù)據(jù)對(duì)象的鄰域關(guān)系具有對(duì)稱性。存在數(shù)據(jù)對(duì)象y∈D為核心對(duì)象(|RNN(y)|≥K)，由于核心對(duì)象y與其影響空間中的任意核心對(duì)象間互為K近鄰，使其K近鄰關(guān)系具有對(duì)稱性，保證了核心對(duì)象y與其影響空間中核心對(duì)象的直接密度可達(dá)具有對(duì)稱性。由定義7和定義8可知，核心對(duì)象y∈D的影響空間中任意數(shù)據(jù)對(duì)象是密度連接的，保證了核心對(duì)象和其影響空間中其他的核心對(duì)象屬于相同密度的聚類簇。因此，數(shù)據(jù)對(duì)象x∈D可進(jìn)行聚類簇?cái)U(kuò)展，應(yīng)滿足的條件重新描述如下：

|RNN(x)|>kΛI(xiàn)sK(x)≠NULL

(2)

在文獻(xiàn)[8]中，RNNDBSCAN算法利用數(shù)據(jù)對(duì)象的K近鄰和逆近鄰的并集進(jìn)行聚類簇?cái)U(kuò)展，因該并集中的數(shù)據(jù)對(duì)象可能屬于不同密度的相鄰聚類簇，造成了聚類算法無法識(shí)別不同密度的相鄰聚類簇這一問題。在使用影響空間進(jìn)行聚類簇?cái)U(kuò)展過程中，對(duì)于核心對(duì)象y的影響空間IsK(y)，若IsK(y)=NULL，由式(2)可知，y不滿足聚類簇?cái)U(kuò)展的條件，因此無法從核心對(duì)象y進(jìn)行聚類簇?cái)U(kuò)展，可暫且將核心對(duì)象y標(biāo)識(shí)為“候選噪聲對(duì)象”，并在噪聲處理過程中，利用其K近鄰關(guān)系將其與真正的噪聲對(duì)象區(qū)分開；若IsK(y)≠NULL，由式(2)可知，y滿足聚類簇?cái)U(kuò)展的條件。由定義9可知，因核心對(duì)象y與其影響空間IsK(y)中的任意核心對(duì)象互為K近鄰，保證了核心對(duì)象y與其影響空間IsK(y)中的任意核心對(duì)象屬于相同密度的聚類簇，提高了聚類算法區(qū)分不同密度簇的能力和聚類精度。由定義9可知，影響空間是K近鄰和逆近鄰的交集，影響空間中數(shù)據(jù)對(duì)象數(shù)明顯少于RNNDBSCAN算法進(jìn)行聚類簇?cái)U(kuò)展中使用的K近鄰和逆近鄰的并集，有效地降低了聚類算法在聚類簇?cái)U(kuò)展中對(duì)內(nèi)存的壓力，提高了聚類效率。

綜上所述，式(2)給出的聚類簇?cái)U(kuò)展條件，避免了候選噪聲數(shù)據(jù)對(duì)象參與到聚類簇?cái)U(kuò)展過程之中，有效地克服了RNNDBSCAN算法無法區(qū)分不同密度的相鄰聚類簇問題,提高了密度聚類分析精度和效率。

3.2 KRDBSCAN聚類分析算法

根據(jù)3.1節(jié)，利用逆近鄰和影響空間的思想，給出一種新穎的密度聚類算法KRDBSCAN。其聚類分析的基本步驟為：首先，為全部數(shù)據(jù)對(duì)象添加未聚類標(biāo)簽，并計(jì)算數(shù)據(jù)對(duì)象的K近鄰NNK和逆近鄰RNN；其次，從數(shù)據(jù)集中隨機(jī)選擇一個(gè)數(shù)據(jù)對(duì)象x∈D，如果數(shù)據(jù)對(duì)象x的逆近鄰|RNN(x)|

算法1KRDBSCAN(KNN-RNN-DBSCAN)

輸入：數(shù)據(jù)集D，近鄰個(gè)數(shù)K。

輸出：聚類簇CLUSTERS。

1.?x∈D:x=UNCLASSIFIED;

//添加未聚類標(biāo)簽

2.cluster=1;

//初始化簇標(biāo)簽

3.NNK(?x∈D),RNN(?x∈D)

//計(jì)算K近鄰與逆近鄰

4.FOR(?x∈D) DO

//隨機(jī)選取數(shù)據(jù)對(duì)象x

5.IFx=UNCLASSIFIEDTHEN

6.IF EXPANSION(x,K,NNK(x),RNN(x),cluster) THEN

7.cluster=cluster+1;

//聚類簇?cái)U(kuò)展過程

8.END IF

9.END IF

10.END FOR

11.PROCESSING-NOISE(x,K,NNK(x));

//噪聲處理

12.returnCLUSTERS;

//輸出聚類簇

13.END KRDBSCAN

算法2EXPANSION(x,K,NNK(x),RNN(x),cluster)

輸入：任意數(shù)據(jù)對(duì)象x∈D，近鄰數(shù)K，簇標(biāo)簽cluster，K近鄰集NNK(x)，逆近鄰集RNN(x)。

輸出：TRUE/FALSE

1.IsK(x∈D)=NNK(x∈D)∩RNN(x∈D);

//計(jì)算數(shù)據(jù)對(duì)象x的影響空間

2.IFRNN(x∈D)

3.x=NOISE;

//噪聲對(duì)象(有可能是邊界對(duì)象)

4.return FALSE;

5.ELSE

6.queue=NULL;

//初始化隊(duì)列

7.IFIsK(x)=NULL THEN

8.x=NOISE;

//候選噪聲對(duì)象

9.returnFALSE;

10.ELSE

11.queue.enqueue(IsK(x));

//將影響空間進(jìn)隊(duì)

12.assign[x+queue]=cluster;

//添加簇標(biāo)簽

13.WHILEqueue≠? DO

//廣度優(yōu)先遍歷過程

14.y=queue.dequeue();

15.IFRNN(y∈D)≥KTHEN

16.FOR(z∈IsK(y)) DO

17.IFz=UNCLASSIFIED THEN

18.queue.enqueue(z);

19.z=cluster;

20.ELSE IFz=NOISE;THENz=cluster;

21.END IF

22.END FOR

23.END IF

24.END WHILE

25.return TRUE;

//聚類簇?cái)U(kuò)展完成

26.END IF

27.END EXPANSION

3.3 KRDBSCAN算法效率分析

在KRDBSCAN中，其算法的時(shí)間復(fù)雜度主要依賴于K近鄰和逆近鄰的求解。在算法1中,計(jì)算數(shù)據(jù)集中每個(gè)數(shù)據(jù)對(duì)象的K近鄰，其時(shí)間復(fù)雜度是O(k×n2)；其次，計(jì)算數(shù)據(jù)集中每個(gè)數(shù)據(jù)對(duì)象的逆近鄰，其時(shí)間復(fù)雜度是O(n2)；在算法2中,隨機(jī)選擇一個(gè)數(shù)據(jù)對(duì)象，采用影響空間進(jìn)行聚類簇?cái)U(kuò)展，其時(shí)間復(fù)雜度是O(n2)；在算法3中,利用K近鄰進(jìn)行噪聲處理，其時(shí)間復(fù)雜度是O(n)。因此，KRDBSCAN算法的時(shí)間復(fù)雜度是O(k×n2+n2+n2+n)≈O(k×n2)。

4 實(shí)驗(yàn)與結(jié)果分析

實(shí)驗(yàn)環(huán)境：Inter Core i5-7300HQ 2.50 GHz，16 GB內(nèi)存，Windows 10操作系統(tǒng)，開發(fā)平臺(tái)為Eclipse和Rstudio。使用Java語言和R語言實(shí)現(xiàn)了KRDBSCAN算法。實(shí)驗(yàn)數(shù)據(jù)采用UCI真實(shí)數(shù)據(jù)集和人工數(shù)據(jù)集。

為了驗(yàn)證KRDBSCAN算法聚類精度和聚類效率，實(shí)驗(yàn)采用Wireless、Act-Rec、Image、optdigits、avila和letter UCI真實(shí)數(shù)據(jù)集。UCI數(shù)據(jù)集如表1所示。

表1 UCI數(shù)據(jù)集

為了驗(yàn)證KRDBSCAN算法抗噪性，實(shí)驗(yàn)采用了Ari1、Ari2和Ari3人工數(shù)據(jù)集。Ari1是維度30、數(shù)據(jù)量為20 000條的高維數(shù)據(jù)集，其分為3個(gè)聚類簇，每個(gè)簇的方差為1.0、10.0和4.0。Ari2是維度50、數(shù)據(jù)量為50 000條的高維數(shù)據(jù)集，其分為4個(gè)聚類簇，每個(gè)簇的方差為1.0、5.0、6.0和10.0。Ari3是維度為40、數(shù)據(jù)量為30 000條的高維數(shù)據(jù)集，其分為5個(gè)聚類簇，每個(gè)聚類簇的方差為1.0、3.0、8.0、14.0和17.0。人工數(shù)據(jù)集如表2所示。

表2 人工數(shù)據(jù)集

為了驗(yàn)證KRDBSCAN算法的聚類精度與聚類效率，實(shí)驗(yàn)采用了標(biāo)準(zhǔn)化互信息(NMI)、調(diào)整蘭德指數(shù)(ARI)和V-Measure度量指標(biāo)。NMI是衡量聚類結(jié)果與真實(shí)簇標(biāo)簽間一致性的重要指標(biāo)，能客觀地評(píng)價(jià)出聚類結(jié)果與真實(shí)標(biāo)簽相比的準(zhǔn)確度。ARI是衡量聚類結(jié)果和真實(shí)簇標(biāo)簽之間相似性的函數(shù)，忽略了聚類結(jié)果的排列順序。V-measure是同質(zhì)性和完整性之間的調(diào)和平均值。簇的同質(zhì)性是指聚類結(jié)果中的數(shù)據(jù)對(duì)象都來自真實(shí)簇標(biāo)簽中單個(gè)聚類簇的數(shù)據(jù)對(duì)象的指數(shù)。簇的完整性是指能夠?qū)⒄鎸?shí)簇標(biāo)簽中屬于相同聚類簇的數(shù)據(jù)對(duì)象聚為相同簇的指數(shù)。

為了實(shí)驗(yàn)驗(yàn)證本文算法KRDBSCAN在聚類精度、聚類效率和抗噪性的優(yōu)越性，采用了當(dāng)前具有代表性的密度聚類方法RNNDBSCAN[8]、ISDBSCAN[18]和RECORD[15]作為本文的對(duì)比算法。

4.1 聚類精度

在采用相同參數(shù)的情況下，標(biāo)準(zhǔn)化互信息的比較實(shí)驗(yàn)結(jié)果如圖1所示，在UCI數(shù)據(jù)集中，KRDBSCAN算法的標(biāo)準(zhǔn)化互信息要高于其他密度聚類算法。KRDBSCAN算法在擴(kuò)展聚類簇過程中使用了核心對(duì)象的影響空間，因?yàn)楹诵膶?duì)象與其影響空間中的其他數(shù)據(jù)對(duì)象具有相互直接密度可達(dá)性，并且影響空間中數(shù)據(jù)對(duì)象是密度連接的，所以確保了核心對(duì)象與其影響空間中的其他數(shù)據(jù)對(duì)象屬于相同密度的聚類簇，能夠更好地估計(jì)鄰域密度分布，顯著提高了聚類結(jié)果的精度和質(zhì)量。其中KRDBSCAN算法明顯優(yōu)于RECORD算法。其原因可能是RECORD算法引入了第二個(gè)預(yù)定參數(shù)，增加了人為因素對(duì)于聚類結(jié)果的影響，并對(duì)噪聲對(duì)象的判斷過于嚴(yán)格。在采用相同參數(shù)的情況下，調(diào)整蘭德指數(shù)的比較實(shí)驗(yàn)結(jié)果如圖2所示，在低維數(shù)據(jù)集Wireless和高維數(shù)據(jù)集optdigits中，KRDBSCAN算法的調(diào)整蘭德指數(shù)要遠(yuǎn)遠(yuǎn)優(yōu)于RNNDBSCAN、ISDBSCAN和RECORD算法，說明KRDBSCAN算法同時(shí)適用于高維數(shù)據(jù)和低維數(shù)據(jù)。其原因是在聚類簇?cái)U(kuò)展過程中引入了影響空間，而不是只考慮了K近鄰，有效避免了在高維數(shù)據(jù)中易發(fā)生的“維數(shù)災(zāi)難”問題。在采用相同參數(shù)的情況下，V-Measure的比較實(shí)驗(yàn)結(jié)果如圖3所示。在UCI數(shù)據(jù)集中，KRDBSCAN算法的V-Measure要遠(yuǎn)遠(yuǎn)優(yōu)于ISDBSCAN和RECORD算法，并略高于RNNDBSCAN算法。其原因是KRDBSCAN與RNNDBSCAN算法使用數(shù)據(jù)對(duì)象的逆近鄰識(shí)別核心對(duì)象。逆近鄰是基于全局的角度來檢查它的鄰域，數(shù)據(jù)分布的改變會(huì)使每個(gè)數(shù)據(jù)對(duì)象的逆近鄰發(fā)生改變。其可以更好地反映數(shù)據(jù)的分布特征。KRDBSCAN與RNNDBSCAN算法都采用一個(gè)預(yù)設(shè)參數(shù)，減少了人為因素對(duì)聚類結(jié)果的影響。

圖1 標(biāo)準(zhǔn)化互信息

圖2 調(diào)整蘭德指數(shù)

圖3 V-Measure

4.2 聚類分析效率

為了驗(yàn)證KRDBSCAN算法的聚類效率，實(shí)驗(yàn)在UCI數(shù)據(jù)集上將KRDBSCAN算法與RNNDBSCAN、ISDBSCAN和RECORD算法進(jìn)行運(yùn)行時(shí)間的比較。為了保證評(píng)估的準(zhǔn)確性，實(shí)驗(yàn)采用5次運(yùn)行時(shí)間取均值的方法進(jìn)行聚類效率的比較，其實(shí)驗(yàn)結(jié)果如表3所示。KRDBSCAN算法的聚類效率略高于RNNDBSCAN和RECORD算法，并且其聚類效率遠(yuǎn)遠(yuǎn)高于ISDBSCAN算法。KRDBSCAN算法雖然需要計(jì)算影響空間，但其在聚類簇?cái)U(kuò)展過程中因減少了入隊(duì)的數(shù)據(jù)對(duì)象而大大縮短了運(yùn)行時(shí)間。而RNNDBSCAN算法在聚類簇?cái)U(kuò)展過程中需將數(shù)據(jù)對(duì)象的K近鄰與逆近鄰的并集入隊(duì)，增加了算法的運(yùn)行時(shí)間。總體上，KRDBSCAN算法的運(yùn)行效率要優(yōu)于RNNDBSCAN、ISDBSCAN和RECORD算法。

表3 聚類效率比較 單位:s

4.3 抗噪性

為了驗(yàn)證KRDBSCAN算法的抗噪性，實(shí)驗(yàn)中采用EXCEL工具中的數(shù)據(jù)生成器，生成噪聲對(duì)象集，并在Ari1、Ari2和Ari3人工數(shù)據(jù)集上添加5%、10%和15%的噪聲對(duì)象，實(shí)驗(yàn)比較標(biāo)準(zhǔn)化互信息、調(diào)整蘭德指數(shù)和V-measure的變化情況。由圖4、圖5和圖6可知，隨著人工數(shù)據(jù)集中噪聲對(duì)象數(shù)比例的增大，標(biāo)準(zhǔn)化互信息、調(diào)整蘭德指數(shù)和V-measure都呈現(xiàn)降低的趨勢(shì)。其原因是隨著噪聲對(duì)象的增多，KRDBSCAN算法將一部分噪聲對(duì)象當(dāng)作邊界對(duì)象聚到聚類簇中，造成了評(píng)估指標(biāo)的降低。但KRDBSCAN算法在數(shù)據(jù)集中每增加5%的噪聲對(duì)象，評(píng)估指標(biāo)降低約0.02到0.05之間，噪聲對(duì)象對(duì)聚類結(jié)果影響并不大，KRDBSCAN算法在有噪聲的數(shù)據(jù)集下依然具有很高的聚類質(zhì)量，說明KRDBSCAN算法具有良好的抗噪性。

圖4 Ari1抗噪性

圖5 Ari2抗噪性

圖6 Ari3抗噪性

5 結(jié) 語

針對(duì)密度聚類算法RNNDBSCAN中存在的無法識(shí)別不同密度的相鄰聚類簇問題，本文給出一種新的基于逆近鄰和影響空間的密度聚類算法KRDBSCAN，與傳統(tǒng)的基于密度的算法相比，KRDBSCAN算法在三個(gè)方面都優(yōu)于當(dāng)前流行的密度聚類算法。首先，數(shù)據(jù)對(duì)象的逆近鄰是基于全局的角度來檢查它的鄰域，數(shù)據(jù)分布的改變會(huì)導(dǎo)致每個(gè)數(shù)據(jù)對(duì)象的逆近鄰發(fā)生改變，該算法采用逆近鄰能真實(shí)地反映數(shù)據(jù)集中數(shù)據(jù)的分布特征。其次，KRDBSCAN算法采用逆近鄰與影響空間相結(jié)合的思想，重新描述了聚類簇?cái)U(kuò)展的條件(|RNN(x)|>K∩Isk(x)≠NULL)，并在其擴(kuò)展過程中，采用了影響空間中的數(shù)據(jù)對(duì)象，實(shí)現(xiàn)聚類簇的迭代擴(kuò)展；由于影響空間中數(shù)據(jù)對(duì)象的直接密度可達(dá)性是對(duì)稱的，保證了數(shù)據(jù)對(duì)象與其影響空間中的數(shù)據(jù)對(duì)象，同屬于相同密度的聚類簇，因而可有效地區(qū)分不同密度的相鄰聚類簇，使KRDBSCAN算法對(duì)局部密度變化高度敏感，能夠更好地估計(jì)鄰域密度分布，提高了聚類精度。最后，KRDBSCAN算法可以隨機(jī)選擇數(shù)據(jù)對(duì)象進(jìn)行聚類，聚類結(jié)果與選取數(shù)據(jù)對(duì)象的順序無關(guān)。實(shí)驗(yàn)結(jié)果表明，KRDBSCAN算法具有良好的聚類精度、聚類效率與抗噪性，并能很好地適用于高維數(shù)據(jù)集的聚類問題。下一步的研究工作是使用Spark平臺(tái)并行化KRDBSCAN算法，使其適用于大數(shù)據(jù)分析。