王治和，曹旭琰，杜 輝

（西北師范大學(xué)計算機(jī)科學(xué)與工程學(xué)院，蘭州 730070）

0 概述

數(shù)據(jù)挖掘是從大量數(shù)據(jù)中提取有價值信息的過程，將其轉(zhuǎn)化成人們需要的且有組織的知識信息［1-2］，已在許多領(lǐng)域取得重要成果。聚類分析是數(shù)據(jù)挖掘的重要技術(shù)之一，可以作為一種獨立的工具深入了解數(shù)據(jù)集的分布情況。其主要任務(wù)是將數(shù)據(jù)集中的每一個數(shù)據(jù)樣本劃分到相應(yīng)的簇中，使簇內(nèi)的樣本彼此相似，而簇間的樣本彼此不相似［3-4］。目前，聚類分析已經(jīng)廣泛地應(yīng)用于圖像分析［5］、模式識別［6］、生物信息學(xué)［7］、知識發(fā)現(xiàn)［8］、醫(yī)學(xué)［9-10］和農(nóng)業(yè)［11］等領(lǐng)域?；诿芏鹊木垲愃惴ㄊ蔷垲惙治龅闹匾夹g(shù)之一，其中經(jīng)典算法有DBSCAN 算法［12］、OPTICS算法［13］、DENCLUE 算法［14］等。

文獻(xiàn)［12］提出的DBSCAN 算法，聚類初始點是從數(shù)據(jù)集中任意取出一個樣本，判斷其為核心點后開始聚類，增加了算法的時間開銷。該算法中的Eps和MinPts 是全局參數(shù)，在聚類過程中不能改變，所以不能正確聚類密度不均勻的數(shù)據(jù)集。因此，如何恰當(dāng)?shù)剡x擇聚類的初始點和Eps 值是提高聚類準(zhǔn)確度的關(guān)鍵因素，很多學(xué)者對此做了大量研究和改進(jìn)。文獻(xiàn)［13］提出OPTICS 算法，該算法并不產(chǎn)生數(shù)據(jù)集聚類，而是輸出一個表示數(shù)據(jù)的基于密度的聚類結(jié)構(gòu)的簇排序，克服了使用一組全局參數(shù)的缺點。但這種總是朝高密度區(qū)域擴(kuò)張的策略，使那些無法連向下一個高密度區(qū)域的低密度點往往被累積在結(jié)果序列的末尾，導(dǎo)致這些低密度點與高密度點的相鄰關(guān)系在映射時被分離［15］。文 獻(xiàn)［16］提出的OSDBSCAN 算法優(yōu)化了初始點的選擇，并結(jié)合數(shù)據(jù)集的特點自適應(yīng)計算Eps 和MinPts 值，但是引入了聚類個數(shù)k、密度參數(shù)α、倍率參數(shù)β3 個參數(shù)，不僅沒有減少人為干預(yù)，而且?guī)砀蟮膹?fù)雜性。文獻(xiàn)［17］提出VDBSCAN 算法，該算法能夠聚類密度不同的數(shù)據(jù)集，求每個數(shù)據(jù)樣本的第k個近鄰，利用k-dist 圖選取不同密度層次相應(yīng)的Eps 值，但是選取過程需要人為干預(yù)，存在很大的不確定性。文獻(xiàn)［18］提出RNN-DBSCAN 算法，使用反向最近鄰（RNN）的思想來定義密度和核心樣本，但整體的聚類效果不佳且運(yùn)行時間較長。文獻(xiàn)［19］提出ADBSCAN 算法，利用最近鄰圖（NNG）固有的性質(zhì)來識別局部高密度樣本，運(yùn)用密度估計對噪聲樣本進(jìn)行濾波，但在某些情況下，該算法有時無法識別正確的簇數(shù)，而且需要對多個參數(shù)組合進(jìn)行測試。

通過上述研究發(fā)現(xiàn)，RNN 算法對獲取全局密度最大的數(shù)據(jù)樣本起到重要作用，解決了DBSCAN 算法隨機(jī)取初始點的問題。本文提出一種新的OIRDBSCAN 算法，借鑒OPTICS 算法中核心距離和可達(dá)距離的思路，通過調(diào)整核心距離和可達(dá)距離的值得到適合該簇的半徑r，以解決DBSCAN 算法中Eps是全局參數(shù)的問題。

1 相關(guān)工作

1.1 DBSCAN 算法

DBSCAN 算法可以發(fā)現(xiàn)任意形狀的簇，并識別噪點，不需要設(shè)定具體的簇數(shù)，聚類效果穩(wěn)定。在Eps 鄰域、MinPts 密度閾值、核心點、直接密度可達(dá)、密度可達(dá)的基礎(chǔ)上設(shè)定了密度相連［20］概念。

DBSCAN 算法從任意一個點p出發(fā)，先判斷其是否是核心點，若是，尋找Eps 鄰域內(nèi)與p直接密度可達(dá)的點，將這些點放入集合U中，然后遍歷集合U中的所有核心點，尋找與它們密度可達(dá)的點，迭代上述步驟，直到集合U中沒有可擴(kuò)展的核心點，此時形成了一個完整的簇；若不是，暫時將其標(biāo)注為噪點。聚類完成其中的一個簇后，對未遍歷的數(shù)據(jù)點重復(fù)上述過程，進(jìn)行其他簇的擴(kuò)展，直至所有的點被遍歷。其中既不是核心點也不是邊界點的被稱為噪點。

1.2 點x 的k 近鄰和反向最近鄰

假設(shè)X是d維空間中的數(shù)據(jù)點集，用n表示X的大小，n=|X|。?x∈X，x∈Rd。對于X中的任意兩個點x和y，用表示兩點之間的距離，其中k的取值范圍為1≤k≤n-1。

定義1點x的k近鄰用Nk(x)=N表示，其中N滿足以下條件：

定義2點x的反向最近鄰用Rk(x)=R表示，其中R滿足以下條件：

1）R?X/{x}。

2）?y∈R：x∈Nk(y)。

下文用具體的示例對上述定義做出解釋，該數(shù)據(jù)集共有5 個點，如圖1 所示。

圖1 二維空間5 個數(shù)據(jù)點的最近鄰圖Fig.1 Nearest neighbor graph of five data points in two-dimensional space

從圖1可以看出：a點的最近鄰是b，b點和c點互為最近鄰，d點的最近鄰是c，以此類推。在k近鄰中，k取1 時為最近鄰點，k取2 時為第二近鄰點，k取n（n為正整數(shù)）時為第n個近鄰點。圖1 的最近鄰表如表1 所示，取k=1。對于反向最近鄰，需要滿足定義2 的2 個條件，具體分析如表2 所示。

表1 二維空間5 個數(shù)據(jù)點的最近鄰表Table 1 Nearest neighbor table of five data points in two-dimensional space

表2 二維空間5 個數(shù)據(jù)點的反向最近鄰表Table 2 Reverse nearest neighbor table of five data points in two-dimensional space

反向最近鄰表如表2 所示，其中以點b為例進(jìn)行分析。點c滿足?x∈X：dist(b，c)≤dist(c，x)，所以c是b的反向最近鄰點，a同理，滿足?x∈X：dist(b，a)≤dist(a，x)，所以a也是b的反向最近鄰點。其他點的分析方法類似。

2 OIR-DBSCAN 算法

2.1 設(shè)計方法

首先尋找數(shù)據(jù)集中全局密度最大的數(shù)據(jù)樣本，將該樣本作為聚類初始點，然后用自適應(yīng)半徑的方法計算出該初始點所在簇相應(yīng)的r值。以該樣本為初始點，r值為半徑開始聚類。當(dāng)一個簇聚類完成后，再從剩余的數(shù)據(jù)樣本中選出新的聚類初始點，迭代上述過程，直至所有數(shù)據(jù)樣本被劃分類別或有部分?jǐn)?shù)據(jù)樣本被當(dāng)作噪聲處理，聚類結(jié)束。

2.2 初始點優(yōu)化

在K-means 算法中初始點的優(yōu)化對算法的改進(jìn)尤為重要。盡管DBSCAN 算法中初始點的優(yōu)化對聚類結(jié)果的影響不太明顯，但從算法的角度考慮，如果初始點選擇的是全局密度最大的點，那么該點一定是核心點，可以省去判斷某個點是否是核心點的時間。本文從文獻(xiàn)［16，18］中得到啟發(fā)，改進(jìn)的算法能夠找到數(shù)據(jù)集中全局密度最大的點。

在初始點優(yōu)化思路中，運(yùn)用到1.2 節(jié)中提到的k近鄰算法和反向最近鄰。從表2 可以看出，a點和e點無反向最近鄰，b點的反向最近鄰是a和c，c點的反向最近鄰是b和d。也可以理解為：a和e沒有出現(xiàn)在任何點的好友圈中，而b出現(xiàn)在a和c的好友圈中，c出現(xiàn)在b和d的好友圈中，d出現(xiàn)在e的好友圈中。可以看出b和c在好友圈的活躍程度最高，在一定程度上證明其周圍數(shù)據(jù)點的密度較高。

首先根據(jù)反向最近鄰表計算出每個點反向最近鄰的個數(shù)m，m越大，意味著該點的活躍度越高，越有可能成為初始點。但是要計算出最終的聚類初始點，不能只根據(jù)m值，需要考慮下面這種情況，如圖2 所示（設(shè)k=1）。

圖2 52 個數(shù)據(jù)樣本考慮m 值的示意圖Fig.2 Fifty-two data samples only consider the schematic diagram of m value

觀察箭頭所指的兩個點，通過計算得出它們的反向最近鄰個數(shù)m均等于4。那么如果只考慮m，則兩者大小一樣。但圖2 中右下角箭頭所指的點所在簇的密度顯然大于左上角中箭頭所指的點所在簇的密度。因此，不能只考慮m的取值，還應(yīng)該考慮該點與k個鄰近距離和的大小，記為dist。dist 越大，密度越??；反之dist 越小，密度越大。

設(shè)數(shù)據(jù)集的相似度矩陣為MMatrix，相似度矩陣用歐式距離表示，每行按從小到大排序后，去除第一列的零元素，記為KNNMatrix。每個數(shù)據(jù)樣本對應(yīng)的m值記為minit。VValue(init)的大小決定該init 點是否可以作為聚類初始點，值越小，表明該點越適合作為聚類初始點；反之，不適合。因此，聚類初始點的判別公式如式（1）所示：

將當(dāng)前最小的VValue(init)值對應(yīng)的init 作為聚類初始點。當(dāng)一個簇聚類完成后，將已經(jīng)有聚類標(biāo)簽的點從候選init 隊列中刪除，方便重新選出下一次聚類的初始點。

初始點的選擇如圖3 所示，數(shù)據(jù)集的初始點依次為三角形、六邊形和五角星所在的點。

圖3 52 個數(shù)據(jù)樣本初始點示意圖Fig.3 Schematic diagram of initial points of fifty-two data samples

初始點的優(yōu)化算法如算法1 所示。

算法1初始點優(yōu)化

輸入k（k=4）

輸出init

步驟1求出各個樣本之間的相似度矩陣MMatrix，用歐式距離表示。

步驟2對Matrix 按行升序排序，去掉第一列的0 元素，得到矩陣KNNMatrix。

步驟3計算每個樣本的反向最近鄰個數(shù)m。

步驟4計算每個樣本的k個近鄰的距離和dist。將該樣本的序號、步驟4 計算出的dist 值和步驟3 計算出的m放入列表RNNDist 中。

步驟5計算RNNDist列表中每個對象的VValue(init)值，參考式（1），按升序排列，得到列表SortRnnDist。

步驟6取SortRnnDist 列表的第一個值對應(yīng)的init 為聚類初始點。

步驟7從第一個初始點開始的聚類結(jié)束后，將已經(jīng)有標(biāo)簽的樣本從SortRnnDist 列表中刪除，重復(fù)步驟6，選取下一次的聚類初始點，重復(fù)步驟7，迭代直至聚類結(jié)束。

2.3 自適應(yīng)半徑r

在傳統(tǒng)的DBSCAN 算法中，Eps 在聚類過程中不能改變。如果Eps 取值太小，將會導(dǎo)致數(shù)據(jù)集被分割成多個簇；如果Eps 取值太大，將會出現(xiàn)多個簇被合并的現(xiàn)象。無論哪種情況，都不能對有密度變化的數(shù)據(jù)集進(jìn)行正確聚類。為克服上述困難，引入以下3 個概念：

1）核心距離。對象p的核心距離ε'是使得p的ε'-領(lǐng)域內(nèi)至少有k個對象，即ε'是使得p成為核心對象的最小半徑閾值。對于數(shù)據(jù)集中的任意一個對象，每個對象p的ε'都不同。如圖3 所示，五角星點的ε'=0.5；六邊形點的ε'=1；三角形點的ε'=1.25。

2）ε距離。ε的取值是一個全局的參數(shù)，由用戶設(shè)定，如圖4 所示，取ε=1。

圖4 核距比之間的關(guān)系Fig.4 Relationship of kernel’s distance radio

3）核距比。表示核心距離ε'與ε距離的比值，核距比在一定程度上可以反映數(shù)據(jù)點分布的疏密情況。

在圖4 中，圖4（a）和圖4（b）的核距比均小于1，其中圖4（a）的核距比最小，得出數(shù)據(jù)之間的密度分布緊湊；圖4（b）的核距比幾乎為1，數(shù)據(jù)之間的密度分布適中；圖4（c）的核距比大于1，明顯數(shù)據(jù)較分散。但是對于核距比大于1 的數(shù)據(jù)點，存在是噪點的可能性，需要做進(jìn)一步的判斷。

設(shè)置一個參數(shù)α用來與核距比作比較，α設(shè)定的大小可以對自適應(yīng)半徑r的調(diào)節(jié)起到伸縮作用。α越小，半徑r可調(diào)整的伸縮性越大；反之，伸縮性越小。自適應(yīng)半徑r的判斷如圖5 所示。

圖5 自適應(yīng)半徑流程Fig.5 Procedure of self-adapting radius

從圖5 可以看出，r的選擇有如下3 種情況：

1）數(shù)據(jù)對象的密度緊密，當(dāng)核距比遠(yuǎn)小于α?xí)r，如果直接取r=ε'，那么半徑r取值太小，會導(dǎo)致本屬于同一個簇的數(shù)據(jù)點被分割成多個簇。所以，采用圖5 中適當(dāng)增大ε'的方法重新計算核距比，使得α落在規(guī)定區(qū)間，此時取r=ε'。

2）數(shù)據(jù)對象的密度適中，當(dāng)核距比正好落在α規(guī)定區(qū)間時，直接取r=ε。因為此時ε和ε'的大小相差甚微，所以選取值較大的ε，加快聚類速度。

3）數(shù)據(jù)對象的密度稀疏，當(dāng)核距比遠(yuǎn)大于α?xí)r，如果直接判斷為噪點，那么可能會忽略如圖2 所示的左邊簇的情況。所以，判斷該數(shù)據(jù)對象的ε'鄰域中的每個點是否有大于等于k個未被標(biāo)識的對象，若有，則說明該點附近只是密度稀疏，并不是噪點，取r=ε'；反之，則為噪點。

2.4 算法描述

通過上述初始值的選取和半徑的判定，得到init和r值，然后采用密度聚類的方法進(jìn)行聚類。第一次聚類結(jié)束之后，從剩余未被標(biāo)記的數(shù)據(jù)樣本中選出第二次聚類的初始點init′和半徑r′，進(jìn)行第二次聚類、迭代，直至所有數(shù)據(jù)樣本被劃分類別或有部分?jǐn)?shù)據(jù)做噪聲處理。

對于數(shù)據(jù)集X中的每個樣本x，標(biāo)簽用cluster表示，聚類過的樣本添加到visited 列表中，未被聚類的樣本存放在unvisited 列表中，將聚類結(jié)果存放在數(shù)組assign中。OIR-DBSCAN 算法的流程如算法2 所示。

算法2OIR-DBSCAN 算法

輸入數(shù)據(jù)集dataset

輸出assign

步驟1對數(shù)據(jù)集作歸一化處理。

步驟2根據(jù)算法1 計算出初始點init。

步驟3根據(jù)圖5 的流程圖計算出自適應(yīng)半徑r。

步驟4通過DBSCAN 算法，將和初始點init 屬于同一類的數(shù)據(jù)樣本劃分出來，cluster 加1。

步驟5執(zhí)行步驟2、步驟3。

步驟6用步驟4 的方法對剩余點聚類。

步驟7迭代，直至所有數(shù)據(jù)被聚類或部分?jǐn)?shù)據(jù)被當(dāng)作噪聲處理。

2.5 參數(shù)選擇

算法中k值是固定參數(shù)，取值為4，k主要用來控制核心距離ε'，進(jìn)而影響半徑r。參數(shù)ε人為設(shè)定。α的大小可以對自適應(yīng)半徑r的調(diào)節(jié)起到伸縮作用，經(jīng)大量實驗測試，α的取值范圍是0.25～0.8。參數(shù)MinPts 和DBSCAN 算法中的MinPts 一樣，用來控制核心點的判斷。雖然該參數(shù)也是人為設(shè)定的參數(shù)，但經(jīng)過大量實驗論證，取值范圍一般為3～15，且為正整數(shù)。

3 實驗結(jié)果與分析

為對本文算法性能進(jìn)行評估，檢測其有效性，本文進(jìn)行以下對比實驗。對比算法包括DBSCAN 算法、OPTICS 算法和RNN-DBSCAN 算法。數(shù)據(jù)集采用人工數(shù)據(jù)集和真實數(shù)據(jù)集，人工數(shù)據(jù)集包括Compound、Pathbased、Jain、Aggregation、grid.orig；真實數(shù)據(jù)集包括iris、WBC、Thyroid、Ecoli、Pima、Vote、Vowel 等。其中人工數(shù)據(jù)集如表3 所示。

表3 人工數(shù)據(jù)集Table 3 Artificial datasets

實驗環(huán)境為Inter?CoreTMi7-1065G7 CPU@1.30 GHz 1.50 GHz，內(nèi)存為16 GB，編程環(huán)境為python3.8，編譯器為Jupter Notebook、PyCharm。

聚類的評價指標(biāo)選用調(diào)整蘭德指數(shù)（ARI）［21］、歸一化交互信息（NMI）［22］、同質(zhì)性指標(biāo)（homogeneity）、完整性指標(biāo)（completeness）和同質(zhì)性與完整性的調(diào)和平均（V-measure）［23］。

ARI 是調(diào)整的RI，相對RI 來說有更高的區(qū)分度。ARI 的取值范圍是［-1，1］，數(shù)值越接近1 代表聚類結(jié)果越好，越接近0 代表聚類結(jié)果越差，計算公式如式（2）所示：

其中：max 表示取最大值；E表示期望。

ARI 計算公式如式（3）所示：

其中：i、j分別表示為真實簇類和預(yù)測簇類；nij表示聚類正確的樣本個數(shù)；max（RI）表示如果聚類結(jié)果完全正確時的值；E[RI]表示求RI 的期望值。

NMI 是一個外部指標(biāo)，通過將聚類結(jié)果與“真實”的類標(biāo)簽對比衡量聚類效果，如式（4）所示：

其中：k（C）是聚類結(jié)果的簇數(shù)；k（T）是真實聚類結(jié)果的簇數(shù)；ni是簇i的樣本個數(shù)；nj是簇j的樣本個數(shù)；ni，j是聚類結(jié)果C中屬于簇i的樣本與真實聚類結(jié)果T中屬于簇j的樣本之間的樣本個數(shù)；n是數(shù)據(jù)集的樣本總數(shù)。

同質(zhì)性h表示每個簇只包含單一類別成員的程度；完整性c表示一個給定類的所有成員分配到單一簇的程度；V-measure 表示兩者的調(diào)和平均。其中同質(zhì)性和完整性如式（5）和式（6）所示：

其中：H(C|K)是給定簇。

類的條件熵如式（7）所示：

H(C)是類的熵，計算公式如式（8）所示：

其中：n表示數(shù)據(jù)集的樣本總數(shù)；nc和nk分別表示屬于簇c和簇k的樣本數(shù)；nc，k為類c中的樣本分配給簇k的數(shù)量。

V-measure 的表達(dá)式如式（9）所示：

3.1 人工數(shù)據(jù)集

本組實驗用上述提及的5 個人工數(shù)據(jù)集進(jìn)行測試，聚類結(jié)果如圖6～圖10 所示。Compound 數(shù)據(jù)集中有若干個密度不同的簇，圖6 的實驗結(jié)果表明，只有本文提出的OIR-DBSCAN 算法能得到正確的聚類結(jié)果，而DBSCAN 算法中由于Eps 參數(shù)的局限性，誤將左上角的簇當(dāng)作噪點處理，OPTICS 算法和RNN-DBSCAN 算法的聚類結(jié)果差強(qiáng)人意；在圖7中，數(shù)據(jù)集的分布較為松散且密度分布無規(guī)律，DBSCAN 算法、OPTICS 算法和RNN-DBSCAN 算法在聚類內(nèi)部簇的過程中都會將最外層的數(shù)據(jù)樣本聚類進(jìn)來，導(dǎo)致一個簇中出現(xiàn)了很多本不屬于該簇的數(shù)據(jù)樣本，而OIR-DBSCAN 算法通過對核心距離和ε距離的調(diào)整計算出合適的半徑r，從而進(jìn)一步得到較好的聚類結(jié)果；在圖8 中，上下兩個簇有較大的密度差異，DBSCAN 算法中若Eps 取值小，則上面的簇會被分割成幾部分，如圖8（a）所示，RNN-DBSCAN算法和OPTICS 算法在聚類過程中將一個簇分成兩個，聚類效果較差，只有OIR-DBSCAN 算法能得到正確的聚類結(jié)果；在圖9 中，數(shù)據(jù)樣本的密度分布相對均勻，部分簇之間相連，經(jīng)過聚類結(jié)果分析發(fā)現(xiàn)4 種算法都有不錯的聚類效果，其中OIR-DBSCAN聚類結(jié)果最好，RNN-DBSCAN 算法次之，OPTICS 算法相對最差；在圖10 中，簇內(nèi)樣本分布均勻，但兩個簇的密度差異大且簇間距離很近，這種數(shù)據(jù)集最能充分體現(xiàn)出OIR-DBSCAN 算法的優(yōu)越性，該算法針對不同密度的簇自適應(yīng)地計算出不同的半徑r進(jìn)行聚類，得到了較好的聚類結(jié)果，而DBSCAN 算法和OPTICS 算法在聚類右下角的簇時，將離該簇最近但本屬于左簇的部分?jǐn)?shù)據(jù)樣本聚類進(jìn)來，得到了錯誤的聚類結(jié)果，RNN-DBSCAN 算法的聚類結(jié)果最差。

圖6 4 種算法在Compound 數(shù)據(jù)集上的聚類結(jié)果Fig.6 Clustering results of four algorithms on Compound dataset

圖7 4 種算法在Pathbased 數(shù)據(jù)集上的聚類結(jié)果Fig.7 Clustering results of four algorithms on Pathbased dataset

圖8 4 種算法在Jain 數(shù)據(jù)集上的聚類結(jié)果Fig.8 Clustering results of four algorithms on Jain dataset

圖9 4 種算法在Aggregation 數(shù)據(jù)集上的聚類結(jié)果Fig.9 Clustering results of four algorithms on Aggregation dataset

圖10 4 種算法在grid.orig 數(shù)據(jù)集上的聚類結(jié)果Fig.10 Clustering results of four algorithms on grid.orig dataset

通過圖6～圖10 所示的可視化對比實驗分析可以得到，在Aggregation 等數(shù)據(jù)集上，其中一部分算法也可以達(dá)到較好的聚類效果。但總體來說，無論是密度不均勻的數(shù)據(jù)集還是普通數(shù)據(jù)集，OIRDBSCAN 算法都能夠得到很好的聚類結(jié)果。4 個聚類算法在人工數(shù)據(jù)集上性能的對比如表4 所示（粗體為最優(yōu)值）。4 種算法在聚類過程中達(dá)到最優(yōu)效果的具體參數(shù)取值如表5 所示。

表5 4 種算法在人工數(shù)據(jù)集上的參數(shù)值Table 5 Parameter values of four algorithms on artificial datasets

3.2 真實數(shù)據(jù)集

在人工數(shù)據(jù)集上，OIR-DBSCAN 算法表現(xiàn)出較好的聚類結(jié)果。為進(jìn)一步驗證其聚類性能，還需要在真實數(shù)據(jù)集上進(jìn)行驗證，UCI 數(shù)據(jù)集如表6所示。

表6 UCI 數(shù)據(jù)集Table 6 UCI datasets

在UCI 數(shù)據(jù)集中，因為高維數(shù)據(jù)集可視化難度較大，所以通過聚類評價指標(biāo)ARI、NMI、homogeneity、completeness 和V-measure 進(jìn)行對比，聚類評價指標(biāo)的對比結(jié)果如表7 所示（粗體為最優(yōu)值）。在Pima 數(shù)據(jù)集中，DBSCAN 算法的NMI 值高于OIR-DBSCAN算法0.006 9，在Vote 數(shù)據(jù)集中，DBSCAN 算法的NMI 值高于OIR-DBSCAN算法0.013 9，但從整體對比結(jié)果來看，OIR-DBSCAN 算法的ARI、NMI 等評價指標(biāo)都明顯高于其他聚類算法。通過比較發(fā)現(xiàn)，OIR-DBSCAN 算法的聚類效果最好，DBSCAN 算法和OPTICS 算法次之，RNN-DBSCAN 算法效果相對最不理想。

表7 4 種算法在UCI 數(shù)據(jù)集上的評價指標(biāo)對比Table 7 Comparison of evaluation index of four algorithms on UCI dataset

4 結(jié)束語

本文提出一種優(yōu)化初始點與自適應(yīng)半徑的密度聚類算法。將反向最近鄰和相似度矩陣相結(jié)合，迭代選取每次聚類開始的初始點，該初始點即為全局密度最大的樣本。優(yōu)化DBSCAN 算法中Eps 全局參數(shù)，調(diào)整核心距離ε'和ε距離之間的核距比與參數(shù)α得出最終半徑值r，使得密度稀疏的簇和密度稠密的簇分別對應(yīng)各自適合的r值，該參數(shù)具有較好的靈活性。實驗結(jié)果證明，OIR-DBSCAN 算法可以正確聚類密度不均勻的數(shù)據(jù)集，而且對高維甚至簇間有重疊的數(shù)據(jù)集也有較好的聚類能力。本文算法在聚類大規(guī)模數(shù)據(jù)集時會出現(xiàn)聚類時間較長的現(xiàn)象，下一步將從改進(jìn)算法性能和提高聚類速度方向入手，以使算法的聚類效果達(dá)到最優(yōu)。