張錦宏，陳 梅，張 弛

蘭州交通大學(xué) 電子與信息工程學(xué)院，蘭州 730070

如何自動(dòng)化地分析、理解和總結(jié)數(shù)據(jù)是當(dāng)前面臨的一個(gè)主要問(wèn)題，數(shù)據(jù)聚類(lèi)分析是一種解決該問(wèn)題的有效技術(shù)[1]。聚類(lèi)分析是一種無(wú)監(jiān)督機(jī)器學(xué)習(xí)方法，其根據(jù)數(shù)據(jù)點(diǎn)間的相似性將數(shù)據(jù)點(diǎn)劃分到不同的簇中，從而識(shí)別出數(shù)據(jù)的內(nèi)在模式并提取有用的知識(shí)[2]。然而，現(xiàn)有的部分聚類(lèi)算法在處理多種類(lèi)型的復(fù)雜數(shù)據(jù)集時(shí)存在聚類(lèi)精度不理想的情況[3]，因此，提出更優(yōu)秀的聚類(lèi)算法是非常必要的。

目前相關(guān)研究人員已經(jīng)提出很多聚類(lèi)算法[3]，且被廣泛應(yīng)用于生物[4]、交通[5]、大數(shù)據(jù)[6]、電力[7]等領(lǐng)域。經(jīng)典的基于劃分的聚類(lèi)算法包括k-means[8]和k-Medoids[9]等。該類(lèi)算法的簇個(gè)數(shù)通常依賴(lài)于用戶(hù)設(shè)定，簇的數(shù)量對(duì)聚類(lèi)結(jié)果有決定性影響。此外劃分聚類(lèi)算法對(duì)非球狀簇的識(shí)別效果較差?；诿芏鹊慕?jīng)典聚類(lèi)算法之一DBSCAN（density-based spatial clustering of application with noise）[10]通過(guò)高密度區(qū)域的連通性發(fā)現(xiàn)簇，利用低密度區(qū)域?qū)Ω呙芏葏^(qū)域的隔斷性標(biāo)識(shí)不同的簇，對(duì)簇的形狀和大小不敏感，但聚類(lèi)質(zhì)量隨著簇內(nèi)點(diǎn)密度變化劇烈程度的增加而降低，且算法閾值參數(shù)難以直接確定[11]。OPTICS（ordering points to identify the clustering structure）[12]是DBSCAN 的改進(jìn)版本，該算法不顯式地生成聚類(lèi)結(jié)果，而是生成一個(gè)數(shù)據(jù)點(diǎn)的有序序列，通過(guò)調(diào)整鄰域半徑參數(shù)從而在該序列中得到相對(duì)應(yīng)的聚類(lèi)結(jié)果，但該算法對(duì)簇內(nèi)數(shù)據(jù)點(diǎn)密度變化的敏感度依然較高。Chameleon[13]是層次聚類(lèi)算法的典型代表，該算法通過(guò)動(dòng)態(tài)考慮初始小簇間的相對(duì)互連性和相對(duì)近似性將小簇歸并得到最終簇。盡管該算法可以識(shí)別任意形狀的簇，但算法運(yùn)行時(shí)間成本較高。基于網(wǎng)格的聚類(lèi)方法也是一種有效的基本聚類(lèi)方法，其中STING（statistical information grid）[14]將數(shù)據(jù)空間按層次順序分割為不同分辨率的單元格，基于每個(gè)單元中的數(shù)據(jù)統(tǒng)計(jì)信息對(duì)單元格進(jìn)行聚類(lèi)。雖然網(wǎng)格化數(shù)據(jù)空間有助于提高算法執(zhí)行速度，但其導(dǎo)致的數(shù)據(jù)空間分辨率下降在聚類(lèi)任意密度數(shù)據(jù)集時(shí)會(huì)影響結(jié)果的精度。

上述現(xiàn)有聚類(lèi)算法中存在難以識(shí)別多中心點(diǎn)任意簇、對(duì)簇內(nèi)點(diǎn)密度變化敏感[15]及閾值取值難以確定等問(wèn)題。近年來(lái)，為了應(yīng)對(duì)檢測(cè)任意形狀、任意密度簇的聚類(lèi)問(wèn)題，學(xué)者們又提出了一些新穎的聚類(lèi)算法。CFDP（clustering by fast search and find of density peaks）[16]結(jié)合了密度聚類(lèi)和劃分聚類(lèi)的特點(diǎn)，基于密度和距離識(shí)別出每個(gè)簇的聚類(lèi)中心，然后基于劃分的方法完成非聚類(lèi)中心點(diǎn)的分配，得到聚類(lèi)結(jié)果。雖然該算法可以準(zhǔn)確地識(shí)別出聚類(lèi)中心點(diǎn)，但CFDP 認(rèn)為每個(gè)聚類(lèi)中心點(diǎn)僅代表一個(gè)簇，因此會(huì)分割多中心點(diǎn)的復(fù)雜簇，且非中心點(diǎn)的分配策略具有層次依賴(lài)性，若先分配的數(shù)據(jù)點(diǎn)出現(xiàn)錯(cuò)誤會(huì)影響后續(xù)所有分配。SCC（sub-cluster component algorithm）[17]是可擴(kuò)展的層次聚類(lèi)算法，該算法使用一系列遞增的距離閾值來(lái)確定在特定輪次中合并哪些子簇。該算法在不犧牲質(zhì)量換取速度的前提下實(shí)現(xiàn)了很好的可伸縮性。MulSim（a novel similar-to-multiple-point clustering algorithm）[18]采用多點(diǎn)相似聚類(lèi)策略，在綜合考慮節(jié)點(diǎn)間以及節(jié)點(diǎn)與對(duì)方近鄰間相似關(guān)系的情況下進(jìn)行聚類(lèi)，從而可以發(fā)現(xiàn)任意形狀、大小和密度的簇?；谏鲜龇治?，可以看出基于密度進(jìn)行聚類(lèi)是識(shí)別任意簇的一種有效思路，因此本文將基于密度聚類(lèi)算法進(jìn)行進(jìn)一步研究。

為了更精確地識(shí)別出復(fù)雜數(shù)據(jù)集中的任意分布簇，本文提出自適應(yīng)閾值約束的密度簇主干聚類(lèi)算法（density backbone clustering algorithm based on adaptive threshold，DCBAT）。根據(jù)密度可達(dá)閾值，DCBAT 算法首先將可達(dá)核心點(diǎn)識(shí)別為簇主干，接著將非聚類(lèi)核心點(diǎn)分配到密度較大的最近鄰所在簇中得到初始簇，最后根據(jù)密度差閾值對(duì)初始簇進(jìn)行拆分得到最終簇。該算法考慮到數(shù)據(jù)點(diǎn)間的密度可達(dá)性往往與數(shù)據(jù)點(diǎn)的整體分布有關(guān)，因此基于數(shù)據(jù)分布自適應(yīng)地計(jì)算密度可達(dá)閾值，克服了DBSCAN 等以密度可達(dá)思想進(jìn)行聚類(lèi)時(shí)密度閾值難以直接確定的問(wèn)題。同時(shí)，復(fù)雜分布數(shù)據(jù)集中各簇的密度不均勻給聚類(lèi)帶來(lái)了一定的困難，但單個(gè)簇內(nèi)由核心到邊界方向的數(shù)據(jù)點(diǎn)密度由大到小的變化趨勢(shì)是相對(duì)穩(wěn)定的，因此該算法基于各簇內(nèi)點(diǎn)的密度差值自適應(yīng)地計(jì)算密度差閾值，根據(jù)簇內(nèi)數(shù)據(jù)點(diǎn)間的密度差值與對(duì)應(yīng)閾值的大小關(guān)系分割錯(cuò)誤合并的初始簇，克服了任意密度影響聚類(lèi)結(jié)果的問(wèn)題，提高了算法識(shí)別精度，降低了異常點(diǎn)對(duì)結(jié)果的影響。該算法時(shí)間復(fù)雜度較低，在參數(shù)不變的情況下聚類(lèi)結(jié)果唯一，具有穩(wěn)定性，可以識(shí)別任意簇。

1 相關(guān)工作

傳統(tǒng)的密度聚類(lèi)算法雖然具備識(shí)別任意簇的能力，但依然存在閾值取值不好確定、對(duì)變密度簇敏感等問(wèn)題[15]。

對(duì)于閾值取值問(wèn)題，自適應(yīng)DBSCAN 算法（selfadaptive density-based spatial clustering of applications with noise，SA-DBSCAN）[19]在DBSCAN 的基礎(chǔ)上利用數(shù)據(jù)集的統(tǒng)計(jì)特性自動(dòng)確定鄰域半徑Eps和鄰域內(nèi)對(duì)象數(shù)Minpts參數(shù)，避免了閾值取值的人工干預(yù)。自適應(yīng)基于廣度優(yōu)先搜索鄰居的聚類(lèi)算法（selfadaptive broad first search neighbors，SA-BFSN）[20-21]改進(jìn)了基于廣度優(yōu)先搜索鄰居的聚類(lèi)算法（broad first search neighbors，BFSN）中距離參數(shù)r和參數(shù)λ的確定方式，在Dk曲線(xiàn)上進(jìn)行逆高斯分布擬合確定參數(shù)r，接著分析噪聲點(diǎn)數(shù)量的分布特征選擇合適的參數(shù)λ。自適應(yīng)密度峰值聚類(lèi)（adaptive density peak clustering，ADPC）[22]對(duì)CFDP 算法進(jìn)行了改進(jìn)，使用基尼系數(shù)對(duì)CFDP 的dc參數(shù)進(jìn)行約束，從而實(shí)現(xiàn)自適應(yīng)選擇截?cái)嗑嚯xdc的目的。

對(duì)于變密度簇敏感問(wèn)題，VDBSCAN（varied density based spatial clustering of applications with noise）[23]首先利用k-dist圖識(shí)別密度層次，對(duì)每層選擇一組鄰域半徑Eps和鄰域內(nèi)對(duì)象數(shù)Minpts參數(shù)，分別調(diào)用DBSCAN算法實(shí)現(xiàn)不同密度簇的聚類(lèi)?；谶吔琰c(diǎn)檢測(cè)的變密度聚類(lèi)算法（varied density clustering algorithm based on border point detection，VDCBD）[24]通過(guò)識(shí)別簇邊界點(diǎn)發(fā)現(xiàn)簇核心結(jié)構(gòu)，依據(jù)高密度近鄰分配原則劃分邊界點(diǎn)到相應(yīng)的簇核心結(jié)構(gòu)中，以這種方式聚類(lèi)變密度簇。融合網(wǎng)格劃分與FDBSCAN 的改進(jìn)聚類(lèi)算法（fusion of grid partition and FDBSCAN clustering algorithm，G_FDBSCAN）[25]利用網(wǎng)格劃分技術(shù)將數(shù)據(jù)集分為稀疏區(qū)域和密集區(qū)域并分而治之，合并相鄰的密集區(qū)域形成子類(lèi)，根據(jù)稀疏網(wǎng)格的鄰居子類(lèi)中是否存在核心點(diǎn)判斷是否將稀疏網(wǎng)格識(shí)別為噪聲，達(dá)到識(shí)別變密度簇的目的。

受上述工作啟發(fā)，本文發(fā)現(xiàn)可以利用數(shù)據(jù)自身的統(tǒng)計(jì)特性和分布特征自適應(yīng)地確定合適的閾值，同時(shí)可以利用簇內(nèi)及簇間點(diǎn)密度變化特點(diǎn)克服變密度簇聚類(lèi)問(wèn)題。本文提出一種自適應(yīng)閾值約束的密度簇主干聚類(lèi)算法，它基于數(shù)據(jù)自身特點(diǎn)自適應(yīng)地確定算法閾值識(shí)別簇主干，并利用簇內(nèi)和簇間數(shù)據(jù)點(diǎn)密度變化的特征獲取最終聚類(lèi)結(jié)果。

2 相關(guān)定義與說(shuō)明

定義1（k近鄰）對(duì)于?xi∈D，D中與xi距離最近的前k個(gè)數(shù)據(jù)點(diǎn)定義為xi的k近鄰，記作Nk(xi)。

定義2（點(diǎn)的局部密度）對(duì)于?xi∈D，點(diǎn)xi與其近鄰點(diǎn)間的距離關(guān)系反映了xi的局部密度。點(diǎn)的局部密度與其近鄰數(shù)量成正比，與鄰居和該點(diǎn)之間的距離之和成反比。本文采用式（1）計(jì)算數(shù)據(jù)點(diǎn)的局部密度：

其中，ρi為點(diǎn)xi的局部密度，k為點(diǎn)xi的近鄰數(shù)量，disij為點(diǎn)xi與其近鄰xj之間的距離。

定義3（點(diǎn)的相對(duì)距離）對(duì)于?xi∈D，其相對(duì)距離δi定義為點(diǎn)xi與點(diǎn)xj之間的距離，其中xj的局部密度大于xi的局部密度，且距離xi最近的數(shù)據(jù)點(diǎn)，稱(chēng)xj為xi的歸屬點(diǎn)。點(diǎn)xi的相對(duì)距離δi的計(jì)算公式如下：

特殊情況下，若點(diǎn)xi具有全局最大局部密度，則：

定義4（聚類(lèi)核心點(diǎn)）潛在的聚類(lèi)核心點(diǎn)應(yīng)該具備局部密度較大和相對(duì)距離較大兩個(gè)特征，定義為：

其中，Ω是聚類(lèi)核心點(diǎn)集合。ρT是局部密度閾值，其取值為所有數(shù)據(jù)點(diǎn)密度的中位數(shù)。δT是相對(duì)距離閾值，其取值為所有數(shù)據(jù)點(diǎn)相對(duì)距離的上四分位數(shù)。

定義5（基于數(shù)據(jù)分布的數(shù)據(jù)點(diǎn)密度可達(dá)自適應(yīng)閾值）一組數(shù)據(jù)的偏度系數(shù)表征著數(shù)據(jù)分布的偏態(tài)程度，且密度可達(dá)閾值與數(shù)據(jù)集中點(diǎn)的密度分布情況息息相關(guān)?；谄认禂?shù)調(diào)整密度均值的數(shù)據(jù)點(diǎn)密度可達(dá)自適應(yīng)閾值的計(jì)算公式如下：

其中，RT表示密度可達(dá)閾值，表示數(shù)據(jù)集D中點(diǎn)的密度均值，λ為D中數(shù)據(jù)點(diǎn)密度的偏度系數(shù)，λ的計(jì)算公式如下：

其中，Q3表示D中數(shù)據(jù)點(diǎn)密度的上四分位數(shù)，Q2表示數(shù)據(jù)點(diǎn)密度的中位數(shù)，Q1表示數(shù)據(jù)點(diǎn)密度的下四分位數(shù)。

定義6（數(shù)據(jù)點(diǎn)可達(dá)）對(duì)于?xi,xj∈D，若存在一組數(shù)據(jù)點(diǎn)序列x1,x2,…,xm,…,xT∈D，其中x1=xi,xT=xj，該序列滿(mǎn)足xm的局部密度ρm大于密度可達(dá)閾值RT且xm+1∈Nk(xm)，則稱(chēng)xi到xj數(shù)據(jù)點(diǎn)可達(dá)。

定義7（基于密度分布的密度差自適應(yīng)閾值）本文新定義密度差閾值的計(jì)算公式如下：

其中，ρm_T表示單個(gè)簇的密度差閾值；ρm_ave表示一個(gè)簇中所有密度差值的均值；μ為比例系數(shù)，用于放大密度差均值。

密度差值反映一個(gè)簇中數(shù)據(jù)點(diǎn)密度變化趨勢(shì)的緩急程度，均值體現(xiàn)了一組數(shù)據(jù)的統(tǒng)計(jì)學(xué)特征，因此可以利用ρm_ave判斷簇內(nèi)密度差值的變化情況。為避免均值取值過(guò)小導(dǎo)致算法對(duì)密度變化過(guò)于敏感，將經(jīng)比例系數(shù)μ適當(dāng)放大后的密度差均值作為密度差閾值。用該閾值評(píng)判密度差值可以為是否拆分初始簇提供可靠的信息參考。

為了便于后文中描述算法，將本文中用到的定義符號(hào)整理如表1所示。

表1 DCBAT算法中常用符號(hào)定義Table 1 Definition of commonly used symbols in DCBAT algorithm

3 自適應(yīng)閾值約束的密度簇主干聚類(lèi)算法

3.1 算法思想

簇核心點(diǎn)具有較高的局部密度，且與其他簇核心點(diǎn)之間的距離相對(duì)較遠(yuǎn)。同一個(gè)簇中的核心點(diǎn)之間是密度可達(dá)的，且簇內(nèi)高密度區(qū)域到低密度區(qū)域的數(shù)據(jù)點(diǎn)密度變化趨勢(shì)相對(duì)平滑，跨簇時(shí)數(shù)據(jù)點(diǎn)密度會(huì)出現(xiàn)劇烈變化。本文立足于數(shù)據(jù)點(diǎn)的分布情況和簇內(nèi)數(shù)據(jù)點(diǎn)的密度變化趨勢(shì)提出DCBAT 算法，定義了基于數(shù)據(jù)點(diǎn)分布的密度可達(dá)自適應(yīng)閾值作為核心點(diǎn)間的可達(dá)性度量，以簇內(nèi)數(shù)據(jù)點(diǎn)密度變化趨勢(shì)作為依據(jù)決定是否對(duì)簇進(jìn)行拆分。

本文以Flame 數(shù)據(jù)集為例直觀(guān)地展示算法聚類(lèi)思想，如圖1所示。第一階段基于局部密度度量和相對(duì)距離度量準(zhǔn)則，篩選出全部數(shù)據(jù)點(diǎn)中的聚類(lèi)核心點(diǎn)，核心點(diǎn)分布如圖1（b）所示。根據(jù)數(shù)據(jù)點(diǎn)密度可達(dá)自適應(yīng)閾值檢測(cè)核心點(diǎn)間的可達(dá)性，將聚類(lèi)核心點(diǎn)劃分為若干集合，每個(gè)集合代表一個(gè)初始簇的簇主干，圖1（c）展示了簇主干。第二階段將剩余數(shù)據(jù)點(diǎn)合并到其密度較大的最近鄰所在簇中，得到初始簇，結(jié)果如圖1（d）所示。第三階段基于每個(gè)初始簇中數(shù)據(jù)點(diǎn)的密度差自適應(yīng)閾值對(duì)初始簇進(jìn)行拆分。圖1（e）繪制了圖1（d）中上方初始簇內(nèi)數(shù)據(jù)點(diǎn)密度由高到低的變化趨勢(shì)，可以看到數(shù)據(jù)點(diǎn)密度在紅框處出現(xiàn)了驟降，斷層處的兩數(shù)據(jù)點(diǎn)密度差值遠(yuǎn)大于密度差閾值，因此斷層上下的數(shù)據(jù)點(diǎn)應(yīng)屬于不同的簇。以斷層處為界將上方初始簇拆分，得到最終簇結(jié)構(gòu)，結(jié)果如圖1（f）所示。對(duì)比聚類(lèi)結(jié)果和圖1（a）所示的數(shù)據(jù)集真實(shí)分布，DCBAT 可以準(zhǔn)確識(shí)別Flame 中包括左上角兩個(gè)異常點(diǎn)在內(nèi)的每個(gè)點(diǎn)。

圖1 DCBAT算法思想示例Fig.1 Example of DCBAT algorithm idea

DCBAT算法基于密度可達(dá)閾值正確判定了聚類(lèi)核心點(diǎn)的所屬簇，準(zhǔn)確識(shí)別了非核心點(diǎn)分配策略中頂層數(shù)據(jù)點(diǎn)的所屬簇，有效降低了該策略的層次依賴(lài)性對(duì)聚類(lèi)結(jié)果的影響，提高了算法識(shí)別簇的容錯(cuò)率。DCBAT算法通過(guò)簇內(nèi)數(shù)據(jù)點(diǎn)間的密度差值與對(duì)應(yīng)閾值的大小關(guān)系判斷初始簇劃分的合理性，以大于閾值的密度差所對(duì)應(yīng)的數(shù)據(jù)點(diǎn)為界將初始簇拆分，大大提高了最終簇的識(shí)別精度，同時(shí)還可以對(duì)異常點(diǎn)進(jìn)行有效識(shí)別。

3.2 算法聚類(lèi)過(guò)程

DCBAT 算法使用點(diǎn)的近鄰數(shù)量k作為算法參數(shù)，通過(guò)3 個(gè)階段完成簇識(shí)別。DCBAT 的總執(zhí)行過(guò)程如算法1所示。

算法1DCBAT執(zhí)行總過(guò)程

在算法1 中，第2～3 行計(jì)算每個(gè)點(diǎn)的局部密度和相對(duì)距離，第5 行根據(jù)定義4 篩選出潛在的聚類(lèi)核心點(diǎn)，第7 行根據(jù)第6 行計(jì)算出的密度可達(dá)閾值RT判斷這些核心點(diǎn)之間的可達(dá)性，形成初始簇主干；接著第8 行對(duì)非聚類(lèi)核心點(diǎn)進(jìn)行分配，得到初始簇結(jié)構(gòu)；最后在第9～13 行檢測(cè)初始簇的合理性，對(duì)錯(cuò)誤合并的簇進(jìn)行拆分，得到最終的簇結(jié)構(gòu)。

3.2.1 獲取簇主干

算法1.1 識(shí)別可達(dá)核心點(diǎn)，獲取簇主干

本算法第一階段如算法1.1所示。第2～3行首先使用式（1）基于每個(gè)點(diǎn)的k近鄰計(jì)算點(diǎn)的局部密度ρi，所有ρi組成局部密度集合ρ。第4～12 行識(shí)別每個(gè)點(diǎn)的歸屬點(diǎn)。對(duì)于點(diǎn)xi，根據(jù)定義3 在其k近鄰范圍內(nèi)尋找其歸屬點(diǎn)xj，得到xi的相對(duì)距離δi；若k近鄰范圍內(nèi)不存在滿(mǎn)足條件的點(diǎn)，則在全局范圍內(nèi)進(jìn)行檢索。所有δi構(gòu)成相對(duì)距離集合δ，所有的歸屬點(diǎn)xj構(gòu)成歸屬點(diǎn)集合B。第14行取ρ的中位數(shù)和δ的上四分位數(shù)分別作為局部密度度量閾值ρT和相對(duì)距離度量閾值δT，第15 行判斷數(shù)據(jù)集中的每個(gè)點(diǎn)xi是否滿(mǎn)足定義4的要求，若滿(mǎn)足則將該點(diǎn)標(biāo)記為聚類(lèi)核心點(diǎn)，否則標(biāo)記為非核心點(diǎn)。接著第16 行利用式（4）基于數(shù)據(jù)集中點(diǎn)的密度分布情況計(jì)算密度可達(dá)閾值RT。在第17～28 行中算法隨機(jī)選擇一個(gè)聚類(lèi)核心點(diǎn)xi，根據(jù)定義6 找到xi的全部密度可達(dá)核心點(diǎn)，將xi與其密度可達(dá)的聚類(lèi)核心點(diǎn)劃分到一個(gè)簇中，生成一個(gè)初始簇的主干。然后隨機(jī)選擇一個(gè)未訪(fǎng)問(wèn)的聚類(lèi)核心點(diǎn)重復(fù)上述過(guò)程，直到訪(fǎng)問(wèn)完全部聚類(lèi)核心點(diǎn)，得到全部初始簇主干。

3.2.2 生成初始簇

算法1.2分配非核心點(diǎn)，生成初始簇

本算法第二階段如算法1.2 所示。DCBAT 按密度降序依次遍歷所有非核心點(diǎn)，將每個(gè)點(diǎn)歸并到其歸屬點(diǎn)所在簇，得到初始簇結(jié)構(gòu)。

3.2.3 拆分初始簇得到最終簇

算法1.3拆分初始簇，獲取最終簇

本算法第三階段如算法1.3 所示。為了判斷初始簇的合理性，DCBAT 以單個(gè)初始簇為單位，在第6～7 行對(duì)每個(gè)簇中的點(diǎn)按密度降序排序，并計(jì)算降序序列中相鄰兩個(gè)點(diǎn)之間的密度差值。在8～12行中使用式（6）計(jì)算出的密度差閾值找到每個(gè)簇中密度差值的異常值。第13～14 行以異常值對(duì)應(yīng)的數(shù)據(jù)點(diǎn)為界，將降序序列劃分為若干個(gè)子序列，即將初始簇劃分為若干新簇，得到最終的簇結(jié)構(gòu)。

根據(jù)所得密度差閾值，簇內(nèi)密度變化異常的初始簇在密度變化波動(dòng)較大的位置被分割為若干個(gè)子簇，即最終簇。最終簇的簇內(nèi)密度變化趨勢(shì)平穩(wěn)，且簇內(nèi)數(shù)據(jù)點(diǎn)密度分布的均勻性與密度變化趨勢(shì)相對(duì)獨(dú)立，不會(huì)影響初始簇的分割過(guò)程。

3.3 時(shí)間復(fù)雜度分析

設(shè)數(shù)據(jù)集D的大小為n，近鄰數(shù)量參數(shù)為k。

第一階段采用k-d樹(shù)[26]作為數(shù)據(jù)結(jié)構(gòu)來(lái)獲取每個(gè)數(shù)據(jù)點(diǎn)的k近鄰，所需時(shí)間復(fù)雜度為O(n×lbn)。在k近鄰的基礎(chǔ)上計(jì)算每個(gè)點(diǎn)的局部密度ρi花費(fèi)O(k×n)。計(jì)算每個(gè)點(diǎn)的相對(duì)距離并生成歸屬點(diǎn)集合B時(shí)需要遍歷k近鄰矩陣，時(shí)間復(fù)雜度為O(k×n)；若k近鄰中不存在密度較大的點(diǎn)，則需在全局范圍內(nèi)進(jìn)行檢索。對(duì)數(shù)據(jù)集D中的點(diǎn)按局部密度降序排序，這樣檢索時(shí)只需要遍歷降序序列中該點(diǎn)之前的數(shù)據(jù)點(diǎn)即可，單個(gè)數(shù)據(jù)點(diǎn)檢索的平均時(shí)間復(fù)雜度為O(0.5×n)，實(shí)驗(yàn)中發(fā)現(xiàn)在k近鄰中檢索到密度較大點(diǎn)的概率超過(guò)90%，因此計(jì)算相對(duì)距離的總時(shí)間復(fù)雜度約為O(0.9×k×n+0.1×0.5×n)。篩選聚類(lèi)核心點(diǎn)前要計(jì)算局部密度度量閾值ρT和相對(duì)距離度量閾值δT，需要對(duì)局部密度集合ρ和相對(duì)距離集合δ進(jìn)行排序，所花費(fèi)時(shí)間復(fù)雜度為O(2×n×lbn)，接著遍歷數(shù)據(jù)集D對(duì)每個(gè)數(shù)據(jù)點(diǎn)進(jìn)行判斷，時(shí)間復(fù)雜度為O(n)。最后確定核心點(diǎn)之間的可達(dá)性，在最差的情況下需要訪(fǎng)問(wèn)全部數(shù)據(jù)點(diǎn)，時(shí)間復(fù)雜度為O(n)。本階段的總時(shí)間復(fù)雜度為O(n×lbn)。

第二階段分配非核心點(diǎn)需要遍歷全部數(shù)據(jù)點(diǎn)，階段總時(shí)間復(fù)雜度為O(n)。

第三階段需要遍歷每個(gè)初始簇。首先需要將單個(gè)簇中的數(shù)據(jù)點(diǎn)按密度降序排序，然后計(jì)算每個(gè)簇中相鄰兩點(diǎn)之間的密度差值并找出差值中的異常值?？偟呐判驎r(shí)間復(fù)雜度為O(n×lbn)；計(jì)算密度差花費(fèi)時(shí)間O(n-cl)，其中cl為初始簇的個(gè)數(shù)，且cl?n；尋找異常密度差值時(shí)間復(fù)雜度為O(n)。本階段的總時(shí)間復(fù)雜度為O(n×lbn)。

綜上所述，算法的總時(shí)間復(fù)雜度為O(n×lbn)。

3.4 基于密度可達(dá)性判定核心點(diǎn)所屬簇

對(duì)于單個(gè)簇而言，核心點(diǎn)構(gòu)成的簇主干蘊(yùn)含著簇的內(nèi)部結(jié)構(gòu)信息，因此準(zhǔn)確識(shí)別簇主干可以保證聚類(lèi)的準(zhǔn)確性。簇內(nèi)部區(qū)域的局部密度相對(duì)較高，而邊緣區(qū)域和簇間區(qū)域的局部密度一般較低。構(gòu)成簇主干的核心點(diǎn)一般位于遠(yuǎn)離簇邊緣的內(nèi)部區(qū)域，由于簇內(nèi)部區(qū)域的密度高，同一簇中的核心點(diǎn)間具有更好的密度可達(dá)性；不同簇間存在低密度區(qū)域，導(dǎo)致不同簇中核心點(diǎn)間的密度可達(dá)性較差。綜上，核心點(diǎn)間是否密度可達(dá)是判斷其是否屬于同一個(gè)簇的重要依據(jù)，密度可達(dá)的核心點(diǎn)同屬于一個(gè)簇。算法第一階段借助能夠體現(xiàn)數(shù)據(jù)分布特點(diǎn)的偏度系數(shù)和體現(xiàn)數(shù)據(jù)統(tǒng)計(jì)特征的密度均值計(jì)算出合適的密度可達(dá)閾值，使用該閾值識(shí)別彼此之間密度可達(dá)的核心點(diǎn)，基于此可以有效地判斷每個(gè)核心點(diǎn)的所屬簇，為后續(xù)步驟打下良好基礎(chǔ)。

3.5 基于簇主干發(fā)現(xiàn)簇

經(jīng)典聚類(lèi)算法如k-means 根據(jù)數(shù)據(jù)點(diǎn)與簇心之間的距離關(guān)系識(shí)別簇；DBSCAN 算法從單個(gè)數(shù)據(jù)點(diǎn)出發(fā)，基于密度可達(dá)性自底向上地發(fā)現(xiàn)整個(gè)簇；CFDP算法通過(guò)識(shí)別每個(gè)簇的聚類(lèi)中心進(jìn)而發(fā)現(xiàn)簇。以上經(jīng)典算法聚類(lèi)時(shí)僅考慮了單個(gè)數(shù)據(jù)點(diǎn)，缺乏對(duì)數(shù)據(jù)內(nèi)部整體結(jié)構(gòu)的考量。DCBAT充分考慮了數(shù)據(jù)的內(nèi)部結(jié)構(gòu)，通過(guò)識(shí)別簇主干完成聚類(lèi)。簇主干是一個(gè)簇的骨架，體現(xiàn)了簇內(nèi)數(shù)據(jù)點(diǎn)的分布特征，基于簇主干聚類(lèi)不僅考慮了數(shù)據(jù)點(diǎn)間的關(guān)聯(lián)關(guān)系，還考慮了數(shù)據(jù)的內(nèi)部結(jié)構(gòu)特征，利用數(shù)據(jù)點(diǎn)與簇主干間的關(guān)系去識(shí)別簇。點(diǎn)間聯(lián)系與數(shù)據(jù)結(jié)構(gòu)特征的綜合考量保證了聚類(lèi)結(jié)果的可靠性，有助于準(zhǔn)確識(shí)別簇。

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

為了驗(yàn)證算法在任意形狀、任意密度數(shù)據(jù)集上的性能，將本文提出的算法與5 種對(duì)比算法分別在8個(gè)數(shù)據(jù)集上進(jìn)行測(cè)試。對(duì)比算法包括3 種經(jīng)典算法和兩種新算法。

4.1 實(shí)驗(yàn)數(shù)據(jù)集

本次實(shí)驗(yàn)共采用8 個(gè)數(shù)據(jù)集，其中包括5 個(gè)二維數(shù)據(jù)集（Aggregation、Compound、Spiral、Flame 和T4）和3 個(gè)多維數(shù)據(jù)集（Column_3C、Ecoli和Seeds），其中二維數(shù)據(jù)集和多維數(shù)據(jù)集分別獲取自東芬蘭大學(xué)（http://cs.joensuu.fi/sipu/datasets/）和UCI 網(wǎng)站（https://archive.ics.uci.edu/ml/datasets.php）。8 個(gè)數(shù)據(jù)集囊括了任意形狀、任意密度、含噪聲點(diǎn)、不同維度以及不同規(guī)模簇的數(shù)據(jù)分布情況。各數(shù)據(jù)集的詳細(xì)信息如表2所示。

表2 數(shù)據(jù)集信息Table 2 Information of datasets

4.2 對(duì)比算法說(shuō)明

為對(duì)比本文算法與現(xiàn)有算法之間的性能差異，本節(jié)使用5個(gè)算法與本文算法進(jìn)行對(duì)比實(shí)驗(yàn)，其中包括3種經(jīng)典算法（k-means、DBSCAN 和OPTICS）和兩種新算法（CFDP 和MulSim）。其中k-means 是劃分聚類(lèi)算法的典型代表，DBSCAN和OPTICS是基于密度的聚類(lèi)算法，CFDP 將基于密度與基于劃分兩種聚類(lèi)算法思想相結(jié)合通過(guò)尋找聚類(lèi)中心從而得到聚類(lèi)結(jié)果，MulSim基于單點(diǎn)和多點(diǎn)間的相似原則識(shí)別簇。3種經(jīng)典算法均來(lái)自Python 的“scikit-learn”庫(kù)，其余算法代碼均由其作者提供。

4.3 聚類(lèi)評(píng)價(jià)指標(biāo)

為了更直觀(guān)地比較各算法間的性能差異，本文使用精度（accuracy，Acc）、調(diào)整蘭德系數(shù)（adjusted Rand index，ARI）和歸一化互信息（normalized mutual information，NMI）對(duì)算法的性能進(jìn)行量化評(píng)價(jià)。

Acc 是數(shù)據(jù)集中正確劃分的數(shù)據(jù)點(diǎn)數(shù)N1與數(shù)據(jù)點(diǎn)總數(shù)N的比值，其計(jì)算公式為：

NMI 是一個(gè)基于信息論的聚類(lèi)結(jié)果評(píng)價(jià)標(biāo)準(zhǔn)，其計(jì)算公式為：

其中，I(Ω,C)表示聚類(lèi)結(jié)果和數(shù)據(jù)真實(shí)分布的互信息，H(Ω)和H(C)分別表示聚類(lèi)結(jié)果和數(shù)據(jù)真實(shí)分布的熵。

ARI是蘭德系數(shù)的調(diào)整形式，其衡量的是兩個(gè)數(shù)據(jù)分布的吻合程度，計(jì)算公式如下：

其中，RI表示蘭德系數(shù)，E(RI)表示蘭德系數(shù)的期望值。

3 個(gè)指標(biāo)的取值越大說(shuō)明聚類(lèi)結(jié)果越接近數(shù)據(jù)的真實(shí)分布。對(duì)于二維數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果還以散點(diǎn)圖的形式進(jìn)行了可視化展示。

4.4 DCBAT算法及對(duì)比算法的參數(shù)

引言部分已經(jīng)介紹了對(duì)比算法，DCBAT 算法和各對(duì)比算法的具體參數(shù)如表3 所示。實(shí)驗(yàn)中各算法的參數(shù)取值通過(guò)多次實(shí)驗(yàn)尋優(yōu)確定，各算法在不同數(shù)據(jù)集下的最優(yōu)參數(shù)如表4所示。通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，本文算法的密度差自適應(yīng)閾值中的比例系數(shù)μ取值為25左右時(shí)可以在各數(shù)據(jù)集得到較好的聚類(lèi)結(jié)果。

表3 DCBAT算法及各對(duì)比算法參數(shù)Table 3 Parameters description of DCBAT and compared algorithms

表4 DCBAT及對(duì)比算法在數(shù)據(jù)集上的參數(shù)取值Table 4 Parameter value of DCBAT and compared algorithms on datasets

4.5 實(shí)驗(yàn)結(jié)果及分析

4.5.1 二維數(shù)據(jù)集

圖2～圖6 分別展示了DCBAT 及對(duì)比算法在5 個(gè)二維數(shù)據(jù)集上的聚類(lèi)結(jié)果，表5 統(tǒng)計(jì)了相應(yīng)的Acc、ARI 和NMI，由于T4 數(shù)據(jù)集沒(méi)有真實(shí)類(lèi)標(biāo)，表5 中無(wú)對(duì)應(yīng)數(shù)據(jù)。

圖2 DCBAT與對(duì)比算法在Aggregation數(shù)據(jù)集上的聚類(lèi)結(jié)果Fig.2 Clustering results of DCBAT and compared algorithms on Aggregation dataset

表5 DCBAT及對(duì)比算法的聚類(lèi)指標(biāo)量化結(jié)果Table 5 Quantitative results of DCBAT and compared algorithms

（1）Aggregation數(shù)據(jù)集

Aggregation 數(shù)據(jù)集中包含典型的凸?fàn)畲?，簇?nèi)密度均勻，每個(gè)簇的密度大小相對(duì)統(tǒng)一，但不同簇中包含的數(shù)據(jù)點(diǎn)數(shù)量差異較大，且存在通過(guò)若干數(shù)據(jù)點(diǎn)相連在一起的兩對(duì)簇，這也是該數(shù)據(jù)集的聚類(lèi)難點(diǎn)所在。圖2展示了DCBAT 與對(duì)比算法在該數(shù)據(jù)集上的聚類(lèi)結(jié)果，其中圖2（g）為Aggregation 的真實(shí)簇分布情況，圖2（a）～（f）分別為DCBAT 及對(duì)比算法在該數(shù)據(jù)集上的聚類(lèi)結(jié)果。

通過(guò)圖2 和表5 可以看出，DCBAT 僅錯(cuò)誤識(shí)別一個(gè)點(diǎn)，取得了最佳的Acc、ARI 和NMI。本文算法基于合理的數(shù)據(jù)點(diǎn)密度可達(dá)閾值，通過(guò)判斷數(shù)據(jù)點(diǎn)間的可達(dá)性對(duì)隸屬于不同簇的核心點(diǎn)正確地進(jìn)行了劃分，在初始階段就確定了每個(gè)簇的簇主干，避免了簇間連通部分對(duì)聚類(lèi)結(jié)果的影響，解決了聚類(lèi)難點(diǎn)。CFDP 的Acc、ARI 和NMI 與DCBAT 并列第一，MulSim 排名第二，二者除簇間連接區(qū)域外均可以準(zhǔn)確地識(shí)別出數(shù)據(jù)點(diǎn)的所屬簇。DBSCAN算法的Acc、ARI 和NMI 排名第四，由于其采用固定的數(shù)據(jù)點(diǎn)密度可達(dá)閾值，對(duì)左上角密度較小的簇邊緣區(qū)域數(shù)據(jù)點(diǎn)未能正確識(shí)別，且受到簇間銜接部分的影響，沒(méi)有劃分開(kāi)右側(cè)的相連簇。OPTICS 算法在DBSCAN的基礎(chǔ)上進(jìn)行了優(yōu)化，但仍不能準(zhǔn)確識(shí)別簇邊緣區(qū)域的部分?jǐn)?shù)據(jù)點(diǎn)，其Acc、ARI 和NMI 排名第三。k-means 算法受到相距較近的兩個(gè)簇的尺寸影響，錯(cuò)誤地選取了簇心，導(dǎo)致未能識(shí)別出左下角的兩個(gè)相連簇。

（2）Compound數(shù)據(jù)集

Compound 數(shù)據(jù)集中包含3 類(lèi)簇，其中左上角的兩個(gè)簇距離較近且具有不均勻的簇內(nèi)密度；右側(cè)兩個(gè)簇?fù)碛胁煌拇貎?nèi)密度。左下角外圈的簇中不存在顯著的簇中心點(diǎn)。數(shù)據(jù)集的聚類(lèi)難點(diǎn)在于數(shù)據(jù)點(diǎn)分布情況錯(cuò)綜復(fù)雜，同時(shí)存在多中心點(diǎn)簇和變密度簇。圖3展示了DCBAT 與對(duì)比算法在該數(shù)據(jù)集上的聚類(lèi)結(jié)果，其中圖3（g）為Aggregation 的真實(shí)簇分布情況，圖3（a）～（f）分別為DCBAT 及對(duì)比算法在該數(shù)據(jù)集上的聚類(lèi)結(jié)果。

從圖3和表5可以看出，DCBAT算法的Acc、ARI和NMI排名第一，對(duì)Compound數(shù)據(jù)集的識(shí)別最為準(zhǔn)確，僅識(shí)別錯(cuò)誤一個(gè)點(diǎn)，且基于初始簇內(nèi)的密度變化趨勢(shì)正確地分割了右側(cè)的兩個(gè)簇。MulSim算法聚類(lèi)結(jié)果排名第二，其在識(shí)別右側(cè)兩個(gè)相鄰簇的邊界區(qū)域時(shí)遇到了困難。DBSCAN 和OPTICS 的聚類(lèi)結(jié)果指標(biāo)依次排名第三和第四，兩個(gè)算法受限于固定的密度閾值參數(shù)，不能準(zhǔn)確識(shí)別右側(cè)不同密度的簇。由于算法思想的制約，CFDP 沒(méi)能識(shí)別出左下角的多中心點(diǎn)簇。k-means對(duì)于右側(cè)的不同密度簇和左下角的無(wú)清晰中心點(diǎn)簇的聚類(lèi)效果較差。

（3）Spiral數(shù)據(jù)集

Spiral 數(shù)據(jù)集中包含3 個(gè)螺旋狀的簇，每個(gè)簇內(nèi)的數(shù)據(jù)點(diǎn)密度隨著螺旋向外延伸而遞減。圖4 展示了DCBAT 與對(duì)比算法在該數(shù)據(jù)集上的聚類(lèi)結(jié)果，其中圖4（g）為Spiral的真實(shí)簇分布，圖4（a）～（f）分別為DCBAT以及對(duì)比算法的聚類(lèi)結(jié)果。

圖4 DCBAT與對(duì)比算法在Spiral數(shù)據(jù)集上的聚類(lèi)結(jié)果Fig.4 Clustering results of DCBAT and compared algorithms on Spiral dataset

從圖4和表5可以看出，DCBAT、DBSCAN、CFDP和MulSim 算法獲得了完美的劃分結(jié)果，聚類(lèi)指標(biāo)均達(dá)到了1.000 0。k-means將數(shù)據(jù)集劃分成了3個(gè)球狀簇。OPTICS 未能正確識(shí)別螺旋尾部密度較小的數(shù)據(jù)點(diǎn)，將其劃分為了異常點(diǎn)。

（4）Flame數(shù)據(jù)集

Flame 數(shù)據(jù)集中包含兩個(gè)簇，兩個(gè)簇中的數(shù)據(jù)點(diǎn)分布比較稀疏，且簇內(nèi)密度與兩簇相連區(qū)域處的密度差異較小。圖5展示了DCBAT 與對(duì)比算法在該數(shù)據(jù)集上的聚類(lèi)結(jié)果，其中圖5（g）為Flame的真實(shí)簇分布情況，圖5（a）～（f）分別為DCBAT 以及對(duì)比算法的聚類(lèi)結(jié)果。

從圖5和表5可以清晰地看出，DCBAT完美地識(shí)別出了真實(shí)的簇結(jié)構(gòu)，取得了最好的聚類(lèi)結(jié)果，其聚類(lèi)指標(biāo)達(dá)到了1.000 0。k-means 將數(shù)據(jù)集強(qiáng)行分為3個(gè)簇，未能識(shí)別左上角的兩個(gè)異常點(diǎn)，還將下方的簇一分為二。由于上、下簇之間的數(shù)據(jù)點(diǎn)分布較為稀疏，且異常點(diǎn)距離簇較遠(yuǎn)，DBSCAN 和OPTICS 的聚類(lèi)結(jié)果較為理想，只有簇相連處的部分?jǐn)?shù)據(jù)點(diǎn)識(shí)別錯(cuò)誤。CFDP 基于數(shù)據(jù)點(diǎn)的分配策略錯(cuò)誤地將下方簇的右側(cè)部分劃分給了上方簇，導(dǎo)致聚類(lèi)效果不佳。MulSim 的聚類(lèi)結(jié)果與DBSCAN 的結(jié)果相似，效果也比較理想。

（5）T4數(shù)據(jù)集

T4 數(shù)據(jù)集中的數(shù)據(jù)不包含真實(shí)類(lèi)標(biāo)簽，但數(shù)據(jù)集中包含異常點(diǎn)，且通過(guò)散點(diǎn)圖可以容易地看出簇的數(shù)量、形狀以及周?chē)漠惓｜c(diǎn)。T4 數(shù)據(jù)集中包含任意形狀的簇。圖6展示了DCBAT 與對(duì)比算法在該數(shù)據(jù)集上的聚類(lèi)結(jié)果，圖6（a）～（f）分別為DCBAT 以及對(duì)比算法的聚類(lèi)結(jié)果。

很明顯，DCBAT 和DBSCAN 都可以正確檢測(cè)出簇結(jié)構(gòu)，并且將周?chē)南∈椟c(diǎn)判定為異常點(diǎn)，更能凸顯簇結(jié)構(gòu)。k-means 算法無(wú)法識(shí)別任意形狀簇，因此未能識(shí)別出簇結(jié)構(gòu)和異常點(diǎn)。CFDP 算法無(wú)法識(shí)別出異常點(diǎn)，且錯(cuò)誤識(shí)別了部分簇。OPTICS 將所有數(shù)據(jù)點(diǎn)劃分為兩個(gè)簇。MulSim算法正確識(shí)別出了部分異常點(diǎn)，但由于右側(cè)存在一條較為密集的數(shù)據(jù)點(diǎn)帶連接兩個(gè)簇，該算法錯(cuò)誤地將兩個(gè)簇進(jìn)行了合并。

圖2～圖6以可視化的形式直觀(guān)地展示了DCBAT和對(duì)比算法在二維數(shù)據(jù)集上的聚類(lèi)結(jié)果。為了更清晰地量化對(duì)比DCBAT 與對(duì)比算法的性能差異，圖7（a）～（c）繪制了二維數(shù)據(jù)集上3 種聚類(lèi)評(píng)價(jià)指標(biāo)的條形圖。

圖7 DCBAT與對(duì)比算法在二維數(shù)據(jù)集上的指標(biāo)條形圖Fig.7 Measurement bar diagram of DCBAT and compared algorithms on two-dimensional datasets

從圖7可以看出，DCBAT算法在4個(gè)二維數(shù)據(jù)集上的聚類(lèi)評(píng)價(jià)指標(biāo)均高于對(duì)比算法，該算法不但能識(shí)別出正確的簇結(jié)構(gòu)，且相較于對(duì)比算法具有最佳的聚類(lèi)性能。

4.5.2 多維數(shù)據(jù)集

表5 中后半部分羅列了DCBAT 與各對(duì)比算法在多維數(shù)據(jù)集Column_3C、Ecoli和Seeds上的聚類(lèi)結(jié)果評(píng)價(jià)指標(biāo)，由于高維數(shù)據(jù)集無(wú)法以散點(diǎn)圖的形式直觀(guān)地展示聚類(lèi)結(jié)果，采用聚類(lèi)評(píng)價(jià)指標(biāo)條形圖的形式來(lái)展示和對(duì)比算法性能。

圖8（a）～（c）所示為DCBAT及對(duì)比算法在3個(gè)多維數(shù)據(jù)集上的Acc、ARI和NMI指標(biāo)的結(jié)果。從圖中可以看到，DCBAT 算法的聚類(lèi)結(jié)果評(píng)價(jià)指標(biāo)整體高于對(duì)比算法，說(shuō)明其具有較強(qiáng)的識(shí)別數(shù)據(jù)真實(shí)分布的能力。

圖8 DCBAT與對(duì)比算法在多維數(shù)據(jù)集上的指標(biāo)條形圖Fig.8 Measurement bar diagram of DCBAT and compared algorithms on multi-dimensional datasets

最后，為對(duì)比算法的綜合性能，將DCBAT 及對(duì)比算法在全部數(shù)據(jù)集上的聚類(lèi)評(píng)價(jià)指標(biāo)通過(guò)箱線(xiàn)圖的形式進(jìn)行展示，結(jié)果如圖9 所示。在盒圖中，每個(gè)盒體的上下邊界表示對(duì)應(yīng)數(shù)據(jù)的上下四分位數(shù)，盒體中的實(shí)線(xiàn)表示對(duì)應(yīng)數(shù)據(jù)的中位數(shù)，自盒體延伸出的上下方的短線(xiàn)代表數(shù)據(jù)中的最大值和最小值，“×”表示異常值。通過(guò)圖9 中的盒圖可知，DCBAT 算法對(duì)應(yīng)的盒圖中各特征數(shù)據(jù)（中位數(shù)、上下四分位數(shù)和最值等）所處位置整體高于對(duì)比算法，盒體的高度整體低于對(duì)比算法，且不存在異常值，說(shuō)明該算法的聚類(lèi)評(píng)價(jià)指標(biāo)取值較大且波動(dòng)較小，算法聚類(lèi)性能相較于對(duì)比算法更優(yōu)。

圖9 DCBAT及對(duì)比算法的評(píng)價(jià)指標(biāo)盒圖Fig.9 Measurement box diagram of DCBAT and compared algorithms

綜上所述，DCBAT算法基于核心點(diǎn)可達(dá)的思想，利用簇內(nèi)數(shù)據(jù)點(diǎn)密度變化趨勢(shì)平穩(wěn)的特點(diǎn)實(shí)現(xiàn)了任意簇的高效識(shí)別，算法整體具有魯棒性。

4.6 變密度簇敏感性分析

變密度簇識(shí)別一直是聚類(lèi)分析的難點(diǎn)所在，給識(shí)別數(shù)據(jù)分布帶來(lái)了一定的阻礙。雖然變密度簇?fù)碛蟹蔷鶆虻拇貎?nèi)密度，但簇內(nèi)核心區(qū)域的局部密度總是相對(duì)較高，且簇內(nèi)密度變化趨勢(shì)相對(duì)穩(wěn)定。本文算法使用高密度區(qū)域的核心點(diǎn)生成簇主干，核心區(qū)域的高密度特性和自適應(yīng)的密度可達(dá)閾值使得簇主干的識(shí)別受簇密度變化的影響很小，降低了該過(guò)程對(duì)變密度簇的敏感性。簇主干可以體現(xiàn)一個(gè)簇的主體結(jié)構(gòu)，有效地反映了簇的內(nèi)部結(jié)構(gòu)信息，其余的低密度點(diǎn)本質(zhì)上都依托于簇主干來(lái)判定其歸屬簇，因此理論上本文算法對(duì)變密度簇不敏感。

為了驗(yàn)證本文算法對(duì)變密度簇的敏感性，本文在調(diào)整的Compound 數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。針對(duì)數(shù)據(jù)集左上角的變密度簇（如圖10（a）中紅圈所示），本文以10%為步長(zhǎng)，按80%～150%的比例縮放簇內(nèi)數(shù)據(jù)點(diǎn)間的距離來(lái)模擬簇密度變化的情景，不同縮放比例下的聚類(lèi)結(jié)果如圖10 所示，聚類(lèi)指標(biāo)如表6 所示?？梢钥闯?，在多個(gè)比例的縮放下，本文算法均能有效識(shí)別簇，評(píng)價(jià)指標(biāo)均高于0.95。當(dāng)縮放比例達(dá)到140%及以上時(shí)，由于縮放比例過(guò)大導(dǎo)致變密度簇下方邊緣區(qū)域的點(diǎn)距離整個(gè)簇過(guò)遠(yuǎn)，且更靠近左下方高密度簇，因此未能正確識(shí)別該區(qū)域的少部分點(diǎn)，但仍可以識(shí)別變密度簇中的大部分點(diǎn)。實(shí)驗(yàn)結(jié)果表明DCBAT 在調(diào)整后的Compound 數(shù)據(jù)集上的聚類(lèi)性能良好，對(duì)變密度簇不敏感，可以保證聚類(lèi)精度。

5 結(jié)束語(yǔ)

為了解決聚類(lèi)中任意簇識(shí)別困難、對(duì)簇內(nèi)密度變化敏感以及閾值確定困難等問(wèn)題，本文提出了DCBAT 算法。DCBAT 將具備高局部密度和高相對(duì)距離且彼此相互可達(dá)的數(shù)據(jù)點(diǎn)識(shí)別為簇主干，并以此為基準(zhǔn)劃分剩余數(shù)據(jù)點(diǎn)得到初始簇，接著對(duì)初始簇進(jìn)行拆分處理得到最終聚類(lèi)結(jié)果。新定義的兩種閾值基于數(shù)據(jù)分布計(jì)算得到，具有良好的自適應(yīng)性。同時(shí)，利用簇內(nèi)密度變化趨勢(shì)來(lái)決定是否拆分初始簇，更好地考慮了數(shù)據(jù)的內(nèi)部結(jié)構(gòu)，有效降低了算法對(duì)變密度簇的敏感性，提高了聚類(lèi)精度。為了驗(yàn)證DCBAT 算法的有效性，本文選擇了五種先進(jìn)算法在八個(gè)不同維度和各具特點(diǎn)的數(shù)據(jù)集上與本文算法進(jìn)行了對(duì)比實(shí)驗(yàn)。結(jié)果表明DCBAT 算法相較于對(duì)比算法具有良好的性能，能更精確地識(shí)別任意簇，對(duì)異常點(diǎn)不敏感，算法結(jié)果穩(wěn)定。在將來(lái)的研究中，擬基于簇內(nèi)密度變化趨勢(shì)進(jìn)行縱向研究，提出更多高效的聚類(lèi)算法。