溫柳英，龐 柯

(西南石油大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，四川 成都 610500)

0 引 言

經(jīng)典高效的聚類算法有：K-Means、DBSCAN、Mean Shift(MS)、DPeak等[1-4]。K-Means算法往往只適用于球形數(shù)據(jù)集或者凸型數(shù)據(jù)集[5，6]。DBSCAN和DPeak算法通過計(jì)算數(shù)據(jù)的密度，可以識別具有任意形狀的數(shù)據(jù)集，一般情況下密度較高的區(qū)域數(shù)據(jù)質(zhì)量較高，而密度較低的區(qū)域數(shù)據(jù)更有可能是噪聲點(diǎn)。然后現(xiàn)實(shí)世界中的數(shù)據(jù)往往既是非球形，同時(shí)也含有噪聲，給聚類算法帶來了巨大的挑戰(zhàn)。

研究人員提出了MS的各種優(yōu)化算法[7-10]。比如文獻(xiàn)[11]提出了一種避免更新全部數(shù)據(jù)集的方法，該方法減少了算法的時(shí)間復(fù)雜度，但是算法的精度有所下降。文獻(xiàn)[12]結(jié)合MS過程，提出一種新的提高聚類精度的方法，但是引入了幾個(gè)需要人工調(diào)整的參數(shù)。

鑒于此，本文對原始的均值漂移算法進(jìn)行了優(yōu)化，提出了一種基于Cover-Tree[13]的自適應(yīng)均值漂移聚類算法(MSCT)，在計(jì)算漂移向量的過程中引入了最近鄰的概念，通過樣本點(diǎn)在Cover-Tree數(shù)據(jù)結(jié)構(gòu)中的K個(gè)近鄰來計(jì)算一個(gè)新的KnnShift向量。

1 相關(guān)算法介紹

1.1 均值漂移算法介紹

均值漂移聚類算法的基本原理是使用迭代的方法遍歷數(shù)據(jù)集中的所有樣本點(diǎn)，搜索點(diǎn)將沿著樣本點(diǎn)密度增加的方向“漂移”到當(dāng)前數(shù)據(jù)集樣本局部密度最大的區(qū)域。該算法是通過密度函數(shù)梯度的非參數(shù)估計(jì)方法推導(dǎo)獲得的，其中非參數(shù)估計(jì)方法是從數(shù)據(jù)集出發(fā)對樣本密度函數(shù)的估計(jì)。它不需要任何先驗(yàn)知識，在任意形狀的數(shù)據(jù)分布下都有效，其中最常用的是核密度估計(jì)方法。

給定一個(gè)大小為n的數(shù)據(jù)集Xi∈Rd，i=1，2，…n。 使用核函數(shù)K(x) 的密度估計(jì)為

(1)

其中，h是核函數(shù)的半徑參數(shù)(也被稱為帶寬)。式(1)中的K(x) 核函數(shù)被定義為

K(x)=ck(x2)

(2)

其中，c是一個(gè)標(biāo)準(zhǔn)常量，式(2)就是均值漂移過程的數(shù)學(xué)理論依據(jù)，密度函數(shù)估計(jì)f(x) 是每個(gè)樣本點(diǎn)處的核函數(shù)加權(quán)求和的結(jié)果。

圖1表示了一個(gè)均值漂移的迭代過程，其中圓點(diǎn)表示數(shù)據(jù)集中的一個(gè)實(shí)例，在大小為n的d維數(shù)據(jù)集Xi∈Rd中，任意選擇一個(gè)數(shù)據(jù)點(diǎn)xi進(jìn)行一次均值漂移過程，直到數(shù)據(jù)集中所有的數(shù)據(jù)點(diǎn)都進(jìn)行過一次完整的均值漂移過程。

圖1 一個(gè)均值漂移過程

1.2 最近鄰算法介紹

作為鄰近搜索[14，15]的一種形式，最近鄰居搜索是在給定集合中找到最接近給定點(diǎn)的點(diǎn)的優(yōu)化問題。緊密度通常用不相似函數(shù)表示：對象越不相似，函數(shù)值就越大。

在最近鄰搜索算法中，基于樹的各種優(yōu)化算法不斷提出，且被應(yīng)用于各種密度聚類算法的優(yōu)化中。比如K-D Tree[16]，雖然K-D Tree非常的有效，但是它只能在低維數(shù)據(jù)集上有較好的表現(xiàn)。之后人們提出了一種和K-D Tree原理相似的算法——VP Tree。與K-D Tree使用一個(gè)超平面來將數(shù)據(jù)點(diǎn)劃分為兩個(gè)部分相似，VP Tree使用了優(yōu)勢點(diǎn)的概念，通過計(jì)算其它點(diǎn)與優(yōu)勢點(diǎn)的距離來將數(shù)據(jù)點(diǎn)一分為二。之后Alina等提出了一種新的最近鄰優(yōu)化算法Cover-Tree，它可以以O(shè)(log(n)) 的時(shí)間復(fù)雜度完成一次最近鄰查找，提高了最近鄰算法的效率。

2 基于Cover-Tree的均值漂移聚類算法

2.1 MSCT原理

原始的MS算法聚類效果十分依賴于帶寬參數(shù)的主觀選取，在處理分布不均勻，密度變化大的數(shù)據(jù)集時(shí)，算法的聚類結(jié)果不夠精確。在原始算法計(jì)算均值漂移向量的過程中，會(huì)計(jì)算一個(gè)數(shù)據(jù)點(diǎn)在某個(gè)帶寬范圍內(nèi)所有的點(diǎn)。這樣一個(gè)計(jì)算過程可以被轉(zhuǎn)換為Knn問題。

本文將最近鄰的概念引入到了MS算法局部密度的計(jì)算過程中，獲得密度梯度估計(jì)公式如式(3)所示

(3)

式(1)中核函數(shù)K(x) 會(huì)先計(jì)算出點(diǎn)x帶寬范圍h內(nèi)所有的點(diǎn)，之后計(jì)算出這些點(diǎn)的重心。對于數(shù)據(jù)集中所有的xi來說，在數(shù)據(jù)集不同的密度范圍內(nèi)，這個(gè)帶寬范圍h是一個(gè)固定的值，無法自適應(yīng)數(shù)據(jù)集不同密度區(qū)域。

式(3)中核函數(shù)K(x) 的帶寬參數(shù)被替換為最近鄰問題中的k，根據(jù)樣本點(diǎn)x在Cover-Tree數(shù)據(jù)集中的k個(gè)近鄰來計(jì)算每一步的漂移向量，記此時(shí)的漂移向量為Knn-Shift。此方法在不同數(shù)據(jù)集以及不同數(shù)據(jù)密度上都能自適應(yīng)的產(chǎn)生一個(gè)帶寬范圍h。

f(x) 被定義為點(diǎn)x具有核函數(shù)K(x) 的多元核密度估計(jì)，此時(shí)結(jié)合核函數(shù)式(2)可獲得式(4)計(jì)算結(jié)果

(4)

式中的第二部分，即為Knn-Shift如式(5)所示

(5)

給定一個(gè)點(diǎn)xi，其第t次迭代過程可以由如下公式表示

(6)

圖2展示了通過最近鄰k獲得Knn-Shift向量的一個(gè)示意圖，此時(shí)k=3。MSCT算法首先會(huì)使用輸入的數(shù)據(jù)構(gòu)建一個(gè)Cover-Tree數(shù)據(jù)集，之后會(huì)通過輸入的參數(shù)k計(jì)算每一個(gè)樣本點(diǎn)的Knn-Shift。

圖2 Knn-Shift 漂移過程

2.2 Cover-Tree的構(gòu)建算法

數(shù)據(jù)集S上的Cover-Tree數(shù)據(jù)結(jié)構(gòu)是一個(gè)有層級結(jié)構(gòu)的樹，它的每個(gè)層級都是其下方層級的“覆蓋”。樹的每個(gè)層級都有一個(gè)下標(biāo)i，該下標(biāo)隨著樹層級的下降而減小。

令Ci表示數(shù)據(jù)集S中與Cover-Tree第i層節(jié)點(diǎn)相關(guān)的點(diǎn)集，我們有如下定義：

定義1 嵌套：Ci?Ci-1

即一旦點(diǎn)p∈S出現(xiàn)在Ci中，那么樹中的每個(gè)比i低的層級都有一個(gè)與p關(guān)聯(lián)的節(jié)點(diǎn)。

定義2 覆蓋：?p∈Ci-1，?q∈Ci。

使得d(p，q)<2i， 且q是p的父節(jié)點(diǎn)。其中d(p，q) 表示兩點(diǎn)之間的距離。

定義3 分隔：?p，q∈Ci， 有d(p，q)<2i。

算法1的Cover-Tree構(gòu)建算法是一個(gè)遞歸算法，算法中的第一步會(huì)創(chuàng)建一個(gè)空的Cover-Tree數(shù)據(jù)結(jié)構(gòu)Q，Qi是第i層所有點(diǎn)的集合。之后的步驟會(huì)對數(shù)據(jù)集S中的每一個(gè)樣本點(diǎn)p進(jìn)行插入操作，每一次的插入操作都從Q的根節(jié)點(diǎn)開始，并根據(jù)定義2對距離的定義來進(jìn)行插入，將數(shù)據(jù)集S中的所有點(diǎn)進(jìn)行插入操作后獲得一個(gè)Cover-Tree數(shù)據(jù)集Q。

算法1: BuildCoverTree

輸入: 數(shù)據(jù)集S, Cover-TreeQi, 層級i

輸出: Cover-Tree數(shù)據(jù)集Q

(2)Ifd(p,q)<2i then

(4)IfBuildCoverTree(p,Qi-1,i-1)=null&&d(p,Qi)≤2ithen

(5) 選擇q∈Q且滿足d(p,q)≤2i的p

(6) 將p插入children(q)中

(7)EndIf

(8)else

(9) returnnull

(10)else

(11) returnnull

(12)EndIf

2.3 MSCT算法

圖3展示了MSCT算法的框架，對于任意一個(gè)數(shù)據(jù)集，MSCT首先會(huì)使用算法1來構(gòu)建一個(gè)Cover-Tree數(shù)據(jù)集，之后在MeanShift過程中結(jié)合該數(shù)據(jù)集和輸入的參數(shù)k計(jì)算出一個(gè)新的Knn-Shift量，通過Knn-Shift的值來判斷一個(gè)樣本點(diǎn)的漂移過程是否結(jié)束。當(dāng)數(shù)據(jù)集所有樣本點(diǎn)完成漂移過程后，按照MeanShift算法的分配策略進(jìn)行最終的舉例，獲得聚類結(jié)果。

圖3 MSCT算法框架

MSCT算法的具體步驟如算法2所示。

算法2: MSCT算法

輸入: 數(shù)據(jù)集S, 近鄰k

輸出: 聚類結(jié)果C

(1)Q=BuildCoverTree(S,Qi,i)//算法1

(2)Forxq∈Sdo

(3)KnnShift=∞ //初始化漂移向量

(4)FSOld=?,FSNew=?//初始化頻率數(shù)組

(5)While(KnnShift≠0)

(6)M=FindNearrest(Q,xq,k)

(7) 集合M中的點(diǎn)FxM訪問頻率加1

(9)xq=xq+KnnShift

(10)Endwhile

(11)IfC=?then

(12)C.Add(cq)

(13)else

(14)IfFSOld>FSNewthen

(15)xq∈COld

(16)else

(17)xq∈CNew

(18)C.Add(cNew)

(19)endif

(20)endif

(21)endfor

在MSCT算法中，第(1)行首先通過算法1構(gòu)建一個(gè)Cover-Tree數(shù)據(jù)集。第(2)行對數(shù)據(jù)集S中的每一個(gè)樣本點(diǎn)進(jìn)行一次Knn-Shift操作。第(3)、第(4)行為初始化過程，記此時(shí)的Knn-Shift向量為一個(gè)極大值，數(shù)據(jù)集S中的每一個(gè)樣本點(diǎn)都有兩個(gè)名為頻率計(jì)數(shù)標(biāo)志的量，分別記為FSOld、FSNew。第(5)行通過Knn-Shift量的值來控制漂移過程的結(jié)束。第(6)行為在Cover-Tree數(shù)據(jù)集Q中找到當(dāng)前樣本點(diǎn)xq的k個(gè)最近鄰，記為集合M。第(7)行將集合M中的元素頻率計(jì)數(shù)標(biāo)志量加1。第(8)行通過獲得的集合M使用式(5)來計(jì)算一個(gè)新的Knn-Shift量。第(9)行使用新的Knn-Shift計(jì)算下一個(gè)虛擬的樣本點(diǎn)xq。第(11)～第(20)行執(zhí)行MeanShift算法最后的聚類分配策略，按照漂移過程中不斷更新的頻率計(jì)數(shù)標(biāo)志來劃分最終的聚類。

2.4 復(fù)雜度分析

MSCT算法的主要過程分為兩個(gè)部分，首先第一部分為通過輸入的數(shù)據(jù)集創(chuàng)建并初始化一個(gè)Cover-Tree數(shù)據(jù)結(jié)構(gòu)即算法1，這個(gè)過程的空間復(fù)雜度為數(shù)據(jù)集的維度O(n)， 時(shí)間復(fù)雜度為O(nlog(n))。 第二部分為算法2的第(2)行至第(21)行，這個(gè)部分為對數(shù)據(jù)集的每一個(gè)點(diǎn)進(jìn)行一次Knn-Shift操作，總的時(shí)間復(fù)雜度為O(tnlog(n))，t為一次Knn-Shift過程中的迭代次數(shù)。所以MSCT算法總的時(shí)間復(fù)雜度為O(nlog(n)+tnlog(n))=O(tnlog(n))， 空間復(fù)雜度為O(n)。

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

為了驗(yàn)證實(shí)驗(yàn)算法的有效性，本文采用了一系列的數(shù)據(jù)集進(jìn)行詳細(xì)的對比實(shí)驗(yàn)，數(shù)據(jù)集使用了聚類算法評測時(shí)常用的一些數(shù)據(jù)集，其中包括UCI(University of California Irvine)數(shù)據(jù)集和人工數(shù)據(jù)集。

實(shí)驗(yàn)對比部分，我們選取了幾種常見的聚類算法作為對比，分別為MeanShift、DBScan、K-means。評價(jià)指標(biāo)選擇調(diào)整互信息(adjusted mutual information，AMI)、調(diào)整蘭德系數(shù)(adjusted rand index，ARI)、FMI指數(shù)(Fowlkes-Mallows index，F(xiàn)MI)。它們的取值范圍分別為：AMI∈[0，1]、 ARI∈[-1，1]、 FMI∈[0，1]。 在之后的表格實(shí)驗(yàn)數(shù)據(jù)中，這3種指標(biāo)的值越大，就表明該算法越有效，算法效果越好，它們的取值范圍為-1到1之間的浮點(diǎn)數(shù)。

實(shí)驗(yàn)中使用到的數(shù)據(jù)集如表1和表2所示。本次實(shí)驗(yàn)使用Java編程實(shí)現(xiàn)，Windows10操作系統(tǒng)，硬件配置為Inter Core i7-9700k CPU @ 3.60 GHz，16 GB RAM， RTX2080S顯卡。

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

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

本文中使用了6個(gè)人工數(shù)據(jù)集，以及2個(gè)UCI數(shù)據(jù)集進(jìn)行了仿真實(shí)驗(yàn)，數(shù)據(jù)集的基本信息見表1、表2。

由表中數(shù)據(jù)可知，選取的數(shù)據(jù)集包含了不同的數(shù)據(jù)維度和數(shù)據(jù)數(shù)量。

表3給出了MSCT算法與標(biāo)準(zhǔn)的MS算法以及DBScan，K-means算法的詳細(xì)實(shí)驗(yàn)對比，表中的各評價(jià)指標(biāo)值均保留結(jié)果小數(shù)點(diǎn)后三位，表格中的數(shù)字加粗值表示當(dāng)前算法相比其它對比算法有較好的聚類結(jié)果，其中MSCT的輸入?yún)?shù)為最近鄰的個(gè)數(shù)K(整數(shù))，MS算法的輸入?yún)?shù)為帶寬參數(shù)(浮點(diǎn)數(shù))，參數(shù)輸入設(shè)置參考了文獻(xiàn)[5]。

表3 各聚類算法評價(jià)指標(biāo)

表3中的數(shù)據(jù)都是人工數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果。從表中可以看出，在AMI、ARI、FMI評價(jià)指標(biāo)上，自適應(yīng)MSCT算法在Aggregation、Flame、R15、D31、S1數(shù)據(jù)集上獲得了最優(yōu)的聚類效果，自適應(yīng)MSCT算法是在原始MS算法上進(jìn)行改進(jìn)獲得的結(jié)果。

圖4圖5是Iris數(shù)據(jù)集和Abalone數(shù)據(jù)集分別使用DBSCAN、MS、MSCT算法進(jìn)行實(shí)驗(yàn)獲得的結(jié)果。

圖4 Iris數(shù)據(jù)集聚類效果

圖5 Abalone數(shù)據(jù)集聚類效果

這兩個(gè)數(shù)據(jù)集都選自于UCI數(shù)據(jù)集，其中Iris數(shù)據(jù)集有150個(gè)樣本數(shù)據(jù)，3個(gè)類簇，除了一個(gè)密度較大的類簇以外，其余兩個(gè)類簇的樣本點(diǎn)的分布較為接近且分散，數(shù)據(jù)集的密度分布不均勻。由圖4可以看出，DBSCAN算法在這一數(shù)據(jù)集上獲得了4個(gè)類簇，圖上的4個(gè)方框區(qū)域，原算法MS和改進(jìn)的算法MSCT獲得的結(jié)果總體是相似的，都得到了3個(gè)聚類的正確結(jié)果，但是在中心密度較大的區(qū)域，一部分?jǐn)?shù)據(jù)樣本上，MSCT算法獲得了更好的聚類結(jié)果，而DBSCAN算法在聚類過程中獲得了不太精確的聚類結(jié)果。圖5的Abalone數(shù)據(jù)集有4177個(gè)樣本數(shù)據(jù)，8個(gè)屬性，3個(gè)簇類，這一數(shù)據(jù)集數(shù)據(jù)樣本維度較多，數(shù)據(jù)分布復(fù)雜，由圖5可以看出，在這一數(shù)據(jù)集上DBSCAN算法聚類效果不太理想，而原始的MS算法在聚類過程中在數(shù)據(jù)密度分布變化較明顯的區(qū)域(圖5上方的區(qū)域)獲得了錯(cuò)誤的類簇個(gè)數(shù)，MSCT算法得到的聚類結(jié)果明顯好于MS算法。

圖6是R15數(shù)據(jù)集，該數(shù)據(jù)將有600個(gè)樣本數(shù)據(jù)，15個(gè)類簇，數(shù)據(jù)集分布分為外圍的低密度區(qū)域，以及中心的高密度區(qū)域兩個(gè)部分。能看到3種算法都獲得了比較好的結(jié)果，這是因?yàn)樽鳛橐环N密度聚類算法，該數(shù)據(jù)集在不同的密度區(qū)間上的劃分有明顯區(qū)別，3種算法都能在該種類型數(shù)據(jù)集上獲得很好的聚類結(jié)果。

圖6 R15數(shù)據(jù)集聚類效果

從表3以及圖6至圖8的數(shù)據(jù)中可以看出，在大多數(shù)人工數(shù)據(jù)集上，自適應(yīng)MSCT算法相較于其它對比算法在3個(gè)評價(jià)指標(biāo)上都獲得得更好的結(jié)果，MSCT算法提出的針對數(shù)據(jù)集分布不均勻，密度變化大的Knn-shift方法，能夠很好解決帶寬參數(shù)選取敏感的問題，解決人為參與實(shí)驗(yàn)時(shí)的主觀性問題。在表3中我們發(fā)現(xiàn)。MSCT算法在Pathbased數(shù)據(jù)集上的表現(xiàn)不如其它對比算法表現(xiàn)好，通過分析數(shù)據(jù)集發(fā)現(xiàn)，該數(shù)據(jù)集的數(shù)據(jù)分布與其它實(shí)驗(yàn)數(shù)據(jù)集有很大區(qū)別，MSCT算法在聚類過程中正確的獲得了聚類個(gè)數(shù)，但是在分配過程中，由于其中一個(gè)聚類的分布區(qū)域過大，將這一聚類中的某些數(shù)據(jù)點(diǎn)進(jìn)行了錯(cuò)誤的分類。

對MSCT算法在這一類數(shù)據(jù)集出現(xiàn)的問題進(jìn)行了分析，主要原因如下：

(1)對于某些數(shù)據(jù)集來說(如實(shí)驗(yàn)中的Pathbased數(shù)據(jù)集)，不同類之間的密度差異較小，且類中的數(shù)據(jù)點(diǎn)分布較為接近，這對于MSCT算法來說有較高難度進(jìn)行正確劃分。

(2)MSCT算法在對所有數(shù)據(jù)集進(jìn)行Knn-shift之后的合并過程中，優(yōu)先選取了類間距離最近的類簇進(jìn)行了合并，在Pathbased這類數(shù)據(jù)集上，這種合并方法并不是最優(yōu)的。

針對以上發(fā)現(xiàn)的問題，之后的研究會(huì)在現(xiàn)有基礎(chǔ)上改進(jìn)類簇的合并過程，在合并過程中考慮多種因素的影響，如簇內(nèi)相似性、簇間相似性等等，來優(yōu)化合并過程。

圖7和圖8是Aggregation，S1數(shù)據(jù)集的聚類結(jié)果圖，由圖中可以看出，兩種數(shù)據(jù)集不同密度區(qū)域的樣本點(diǎn)有比較接近的一部分，3種對比算法算法主要在每一部分樣本點(diǎn)的邊緣部分的分類上有不同的聚類結(jié)果，從圖7個(gè)圖8中可以看出在某些樣本點(diǎn)的聚類結(jié)果上，MS算法沒有正確獲得聚類結(jié)果(圖7和圖8中使用虛線方框標(biāo)記的部分樣本點(diǎn))，再結(jié)合表3中的有效性評價(jià)指標(biāo)AMI、ARI、FMI的值，可以得到結(jié)論MSCT算法在大多數(shù)密度變化較大的數(shù)據(jù)集上獲得了比原算法更優(yōu)的聚類結(jié)果，聚類效果更好。

圖7 Aggregation數(shù)據(jù)集聚類效果

圖8 S1數(shù)據(jù)集聚類效果

4 結(jié)束語

本文中將Cover-Tree算法應(yīng)用到了原始的MeanShift算法中，得到了新的MSCT算法，解決了帶寬參數(shù)對聚類結(jié)果的影響，實(shí)驗(yàn)結(jié)果表明能獲得更加精確的聚類結(jié)果，MSCT算法適用于處理樣本密度變化大的數(shù)據(jù)集，在這些數(shù)據(jù)集上有比原始算法更好的表現(xiàn)。

實(shí)驗(yàn)過程中也發(fā)現(xiàn)一些可以進(jìn)一步優(yōu)化的問題，本文主要是針對漂移過程進(jìn)行了改進(jìn)，之后會(huì)嘗試對漂移過程之后的類簇合并過程進(jìn)行優(yōu)化，以及將MSCT算法應(yīng)用于實(shí)際問題。