劉宏凱 張繼福

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

0 引 言

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

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

1 相關(guān)工作

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

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

2 相關(guān)定義

2.1 K近鄰與逆近鄰

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

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

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

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

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

2.2 密度聚類

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

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

(1)

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

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

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

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

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

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

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

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

2.3 影響空間

定義9(影響空間[18]) 在數(shù)據(jù)集D中，將數(shù)據(jù)對象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ù)對象K近鄰的鄰域關(guān)系和逆近鄰的鄰域關(guān)系都不具有對稱性，因此，數(shù)據(jù)對象與其K近鄰和逆近鄰并集中數(shù)據(jù)對象的鄰域關(guān)系也不具有對稱性。由定義5可知，數(shù)據(jù)對象與其K近鄰和逆近鄰并集中數(shù)據(jù)對象的直接密度可達(dá)性是非對稱的，不能保證數(shù)據(jù)對象與其K近鄰與逆近鄰并集中的數(shù)據(jù)對象同屬于相同密度的聚類簇。在密度聚類分析中，采用K近鄰與逆近鄰的并集進(jìn)行聚類簇?cái)U(kuò)展無法區(qū)分不同密度的相鄰聚類簇，從而造成聚類效果無法真實(shí)地反映數(shù)據(jù)對象的分布特征。

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

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

3.2 KRDBSCAN聚類分析算法

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

算法1KRDBSCAN(KNN-RNN-DBSCAN)

輸入：數(shù)據(jù)集D，近鄰個數(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ù)對象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ù)對象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ù)對象x的影響空間

2.IFRNN(x∈D)

3.x=NOISE;

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

4.return FALSE;

5.ELSE

6.queue=NULL;

//初始化隊(duì)列

7.IFIsK(x)=NULL THEN

8.x=NOISE;

//候選噪聲對象

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中，其算法的時間復(fù)雜度主要依賴于K近鄰和逆近鄰的求解。在算法1中,計(jì)算數(shù)據(jù)集中每個數(shù)據(jù)對象的K近鄰，其時間復(fù)雜度是O(k×n2)；其次，計(jì)算數(shù)據(jù)集中每個數(shù)據(jù)對象的逆近鄰，其時間復(fù)雜度是O(n2)；在算法2中,隨機(jī)選擇一個數(shù)據(jù)對象，采用影響空間進(jìn)行聚類簇?cái)U(kuò)展，其時間復(fù)雜度是O(n2)；在算法3中,利用K近鄰進(jìn)行噪聲處理，其時間復(fù)雜度是O(n)。因此，KRDBSCAN算法的時間復(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ā)平臺為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個聚類簇，每個簇的方差為1.0、10.0和4.0。Ari2是維度50、數(shù)據(jù)量為50 000條的高維數(shù)據(jù)集，其分為4個聚類簇，每個簇的方差為1.0、5.0、6.0和10.0。Ari3是維度為40、數(shù)據(jù)量為30 000條的高維數(shù)據(jù)集，其分為5個聚類簇，每個聚類簇的方差為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)，能客觀地評價出聚類結(jié)果與真實(shí)標(biāo)簽相比的準(zhǔn)確度。ARI是衡量聚類結(jié)果和真實(shí)簇標(biāo)簽之間相似性的函數(shù)，忽略了聚類結(jié)果的排列順序。V-measure是同質(zhì)性和完整性之間的調(diào)和平均值。簇的同質(zhì)性是指聚類結(jié)果中的數(shù)據(jù)對象都來自真實(shí)簇標(biāo)簽中單個聚類簇的數(shù)據(jù)對象的指數(shù)。簇的完整性是指能夠?qū)⒄鎸?shí)簇標(biāo)簽中屬于相同聚類簇的數(shù)據(jù)對象聚為相同簇的指數(shù)。

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

4.1 聚類精度

在采用相同參數(shù)的情況下，標(biāo)準(zhǔn)化互信息的比較實(shí)驗(yàn)結(jié)果如圖1所示，在UCI數(shù)據(jù)集中，KRDBSCAN算法的標(biāo)準(zhǔn)化互信息要高于其他密度聚類算法。KRDBSCAN算法在擴(kuò)展聚類簇過程中使用了核心對象的影響空間，因?yàn)楹诵膶ο笈c其影響空間中的其他數(shù)據(jù)對象具有相互直接密度可達(dá)性，并且影響空間中數(shù)據(jù)對象是密度連接的，所以確保了核心對象與其影響空間中的其他數(shù)據(jù)對象屬于相同密度的聚類簇，能夠更好地估計(jì)鄰域密度分布，顯著提高了聚類結(jié)果的精度和質(zhì)量。其中KRDBSCAN算法明顯優(yōu)于RECORD算法。其原因可能是RECORD算法引入了第二個預(yù)定參數(shù)，增加了人為因素對于聚類結(jié)果的影響，并對噪聲對象的判斷過于嚴(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ù)據(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ù)對象的逆近鄰識別核心對象。逆近鄰是基于全局的角度來檢查它的鄰域，數(shù)據(jù)分布的改變會使每個數(shù)據(jù)對象的逆近鄰發(fā)生改變。其可以更好地反映數(shù)據(jù)的分布特征。KRDBSCAN與RNNDBSCAN算法都采用一個預(yù)設(shè)參數(shù)，減少了人為因素對聚類結(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)行時間的比較。為了保證評估的準(zhǔn)確性，實(shí)驗(yàn)采用5次運(yùn)行時間取均值的方法進(jìn)行聚類效率的比較，其實(shí)驗(yàn)結(jié)果如表3所示。KRDBSCAN算法的聚類效率略高于RNNDBSCAN和RECORD算法，并且其聚類效率遠(yuǎn)遠(yuǎn)高于ISDBSCAN算法。KRDBSCAN算法雖然需要計(jì)算影響空間，但其在聚類簇?cái)U(kuò)展過程中因減少了入隊(duì)的數(shù)據(jù)對象而大大縮短了運(yùn)行時間。而RNNDBSCAN算法在聚類簇?cái)U(kuò)展過程中需將數(shù)據(jù)對象的K近鄰與逆近鄰的并集入隊(duì)，增加了算法的運(yùn)行時間?？傮w上，KRDBSCAN算法的運(yùn)行效率要優(yōu)于RNNDBSCAN、ISDBSCAN和RECORD算法。

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

4.3 抗噪性

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

圖4 Ari1抗噪性

圖5 Ari2抗噪性

圖6 Ari3抗噪性

5 結(jié) 語

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