基于覆蓋樹的自適應均值漂移聚類算法

溫柳英，龐 柯

(西南石油大學 計算機科學學院，四川 成都 610500)

0 引 言

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

研究人員提出了MS的各種優化算法[7-10]。比如文獻[11]提出了一種避免更新全部數據集的方法，該方法減少了算法的時間復雜度，但是算法的精度有所下降。文獻[12]結合MS過程，提出一種新的提高聚類精度的方法，但是引入了幾個需要人工調整的參數。

鑒于此，本文對原始的均值漂移算法進行了優化，提出了一種基于Cover-Tree[13]的自適應均值漂移聚類算法(MSCT)，在計算漂移向量的過程中引入了最近鄰的概念，通過樣本點在Cover-Tree數據結構中的K個近鄰來計算一個新的KnnShift向量。

1 相關算法介紹

1.1 均值漂移算法介紹

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

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

(1)

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

K(x)=ck(x2)

(2)

其中，c是一個標準常量，式(2)就是均值漂移過程的數學理論依據，密度函數估計f(x) 是每個樣本點處的核函數加權求和的結果。

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

圖1 一個均值漂移過程

1.2 最近鄰算法介紹

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

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

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

2.1 MSCT原理

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

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

(3)

式(1)中核函數K(x) 會先計算出點x帶寬范圍h內所有的點，之后計算出這些點的重心。對于數據集中所有的xi來說，在數據集不同的密度范圍內，這個帶寬范圍h是一個固定的值，無法自適應數據集不同密度區域。

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

f(x) 被定義為點x具有核函數K(x) 的多元核密度估計，此時結合核函數式(2)可獲得式(4)計算結果

(4)

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

(5)

給定一個點xi，其第t次迭代過程可以由如下公式表示

(6)

圖2展示了通過最近鄰k獲得Knn-Shift向量的一個示意圖，此時k=3。MSCT算法首先會使用輸入的數據構建一個Cover-Tree數據集，之后會通過輸入的參數k計算每一個樣本點的Knn-Shift。

圖2 Knn-Shift 漂移過程

2.2 Cover-Tree的構建算法

數據集S上的Cover-Tree數據結構是一個有層級結構的樹，它的每個層級都是其下方層級的“覆蓋”。樹的每個層級都有一個下標i，該下標隨著樹層級的下降而減小。

令Ci表示數據集S中與Cover-Tree第i層節點相關的點集，我們有如下定義：

定義1 嵌套：Ci?Ci-1

即一旦點p∈S出現在Ci中，那么樹中的每個比i低的層級都有一個與p關聯的節點。

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

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

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

算法1的Cover-Tree構建算法是一個遞歸算法，算法中的第一步會創建一個空的Cover-Tree數據結構Q，Qi是第i層所有點的集合。之后的步驟會對數據集S中的每一個樣本點p進行插入操作，每一次的插入操作都從Q的根節點開始，并根據定義2對距離的定義來進行插入，將數據集S中的所有點進行插入操作后獲得一個Cover-Tree數據集Q。

算法1: BuildCoverTree

輸入: 數據集S, Cover-TreeQi, 層級i

輸出: Cover-Tree數據集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算法的框架，對于任意一個數據集，MSCT首先會使用算法1來構建一個Cover-Tree數據集，之后在MeanShift過程中結合該數據集和輸入的參數k計算出一個新的Knn-Shift量，通過Knn-Shift的值來判斷一個樣本點的漂移過程是否結束。當數據集所有樣本點完成漂移過程后，按照MeanShift算法的分配策略進行最終的舉例，獲得聚類結果。

圖3 MSCT算法框架

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

算法2: MSCT算法

輸入: 數據集S, 近鄰k

輸出: 聚類結果C

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

(2)Forxq∈Sdo

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

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

(5)While(KnnShift≠0)

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

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

2.4 復雜度分析

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

3 實驗結果與分析

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

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

實驗中使用到的數據集如表1和表2所示。本次實驗使用Java編程實現，Windows10操作系統，硬件配置為Inter Core i7-9700k CPU @ 3.60 GHz，16 GB RAM， RTX2080S顯卡。

表1 UCI數據集信息

表2 人工數據集信息

本文中使用了6個人工數據集，以及2個UCI數據集進行了仿真實驗，數據集的基本信息見表1、表2。

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

表3給出了MSCT算法與標準的MS算法以及DBScan，K-means算法的詳細實驗對比，表中的各評價指標值均保留結果小數點后三位，表格中的數字加粗值表示當前算法相比其它對比算法有較好的聚類結果，其中MSCT的輸入參數為最近鄰的個數K(整數)，MS算法的輸入參數為帶寬參數(浮點數)，參數輸入設置參考了文獻[5]。

表3 各聚類算法評價指標

表3中的數據都是人工數據集的實驗結果。從表中可以看出，在AMI、ARI、FMI評價指標上，自適應MSCT算法在Aggregation、Flame、R15、D31、S1數據集上獲得了最優的聚類效果，自適應MSCT算法是在原始MS算法上進行改進獲得的結果。

圖4圖5是Iris數據集和Abalone數據集分別使用DBSCAN、MS、MSCT算法進行實驗獲得的結果。

圖4 Iris數據集聚類效果

圖5 Abalone數據集聚類效果

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

圖6是R15數據集，該數據將有600個樣本數據，15個類簇，數據集分布分為外圍的低密度區域，以及中心的高密度區域兩個部分。能看到3種算法都獲得了比較好的結果，這是因為作為一種密度聚類算法，該數據集在不同的密度區間上的劃分有明顯區別，3種算法都能在該種類型數據集上獲得很好的聚類結果。

圖6 R15數據集聚類效果

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

對MSCT算法在這一類數據集出現的問題進行了分析，主要原因如下：

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

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

針對以上發現的問題，之后的研究會在現有基礎上改進類簇的合并過程，在合并過程中考慮多種因素的影響，如簇內相似性、簇間相似性等等，來優化合并過程。

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

圖7 Aggregation數據集聚類效果

圖8 S1數據集聚類效果

4 結束語

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

實驗過程中也發現一些可以進一步優化的問題，本文主要是針對漂移過程進行了改進，之后會嘗試對漂移過程之后的類簇合并過程進行優化，以及將MSCT算法應用于實際問題。