基于相似性的密度峰值聚類分析算法*

劉 昱 胡立華

（太原科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院 太原 030024）

1 引言

聚類作為一種無監(jiān)督分析方法，是機器學(xué)習(xí)和數(shù)據(jù)挖掘等領(lǐng)域中的重要研究內(nèi)容之一［1］。聚類分析將數(shù)據(jù)對象歸結(jié)為一系列聚類簇，使同簇中數(shù)據(jù)對象之間相似性較高，而在不同簇中的數(shù)據(jù)對象之間相似性較低，聚類簇有效地體現(xiàn)了研究對象的分布特征和潛在共性，對于揭示事物的內(nèi)在聯(lián)系具有重要意義，并已廣泛地應(yīng)用于社會科學(xué)［2］、并行計算［3］、信息檢索［4］、機器學(xué)習(xí)［5］和數(shù)據(jù)挖掘［6］等領(lǐng)域。

DPC［7］是具有代表性的一類密度聚類分析方法，但由于對數(shù)據(jù)集的大小和密度的度量未明確定義，參數(shù)截斷距離dc選擇上存在很大隨意性，且在找到密度峰后，僅將剩余數(shù)據(jù)對象分配給距離最近的較高密度點容易導(dǎo)致誤傳播，從而導(dǎo)致復(fù)雜數(shù)據(jù)集的聚類性能較差。本文利用數(shù)據(jù)對象的K 近鄰得到局部密度，再通過與其K近鄰數(shù)據(jù)對象局部密度和距離的比值得到鄰域密度，重新定義了局部密度計算方法，有效地解決了截斷距離dc在選擇上的隨意性；其次針對數(shù)據(jù)對象之間的相似性，結(jié)合影響空間、共享K近鄰和密度比提出了一種新的數(shù)據(jù)對象相似性度量方法；根據(jù)K近鄰距離的內(nèi)聚性系數(shù)先標記低內(nèi)聚性點，再依據(jù)距離和密度相似性并結(jié)合相似近鄰思想進行聚類，改進了FKNN-DPC分配策略。

2 相關(guān)工作

近年來，其典型研究工作：Alex 等首先提出快速搜索和查找密度峰（DPC）聚類分析思想和方法；Mehmood 等提出利用基因表達微陣列和密度峰值結(jié)合算法［8］，有效為癌癥分型和腫瘤組織識別；Liu等提出共享最近鄰的密度峰快速搜索聚類算法［9］，根據(jù)共享鄰域計算點之間的相似度，并通過相似度重新定義點的局部密度，并提出自適應(yīng)距離度量方法，但是聚類算法受共享鄰居數(shù)影響較大；Xie等提出根據(jù)K近鄰的密度峰值聚類算法FKNN-DPC［10］；Xu 等提出了基于累積最近鄰度和微觀聚類合并的密度峰聚類算法［11］，重新定義局部密度，并且引入合并微集群方法提高分配精度；Du 等提出基于K近鄰和主成分分析的密度峰聚類算法［12］，利用PCA降維有效改進DPC 在高維數(shù)據(jù)集中聚類效果較差的缺點，雖然提高性能，但是聚類效果受數(shù)據(jù)對象的分布影響較大；高鑫等提出將Word2Vec 與密度峰結(jié)合的算法［13］，通過KNN 改進數(shù)據(jù)點的局部密度計算公式并通過最小二乘法選取聚類中心，有效提高搜狐新聞數(shù)據(jù)集的聚類結(jié)果。

3 DPC聚類

對于給定任意數(shù)據(jù)集X={x1,x2,…,xn} ，dij表示數(shù)據(jù)對象xi和xj之間的歐式距離，dc是由用戶設(shè)置的截斷距離，則局部密度ρi定義為

δi是數(shù)據(jù)對象xi與較高密度數(shù)據(jù)對象xj之間的最小距離，距離定義為

如果數(shù)據(jù)對象xi具有全局最高密度，則公式定義為

為了檢測數(shù)據(jù)集中的聚類簇數(shù)，DPC提出啟發(fā)式方法（決策圖），決策值γi的定義為

由上述公式，然后DPC算法將剩余的未分配的數(shù)據(jù)對象分配給距離最近的較高密度點所屬的簇。

4 基于相似性的密度峰值聚類分析

4.1 基本思想

本密度計算方法將數(shù)據(jù)對象密度分為兩部分：1）FKNN-DPC［10］的數(shù)據(jù)對象的K 近鄰局部密度；2）數(shù)據(jù)對象局部密度與其K 近鄰局部密度和距離的比值得到的鄰域密度，可有效解決人為設(shè)置截斷距離dc的問題；針對數(shù)據(jù)對象之間的相似性，結(jié)合影響空間、共享K近鄰和密度比提出一種新的數(shù)據(jù)對象相似性度量方法，依據(jù)距離和密度相似并結(jié)合近鄰思想，充分考慮擴展點與最相似的被擴展點的周圍鄰近點的距離分布情況和兩點之間的密度分布相似性，從而擴展聚類簇，改進了FKNN-DPC［10］分配策略。

對于給定任意數(shù)據(jù)集X={x1,x2,…,xn} ，xj是數(shù)據(jù)對象xi的K 近鄰數(shù)據(jù)對象，dij表示數(shù)據(jù)對象xi和數(shù)據(jù)對象xj之間的歐氏距離，則數(shù)據(jù)對象xi的局部密度ρi1為

每個數(shù)據(jù)對象xi的鄰域密度比定義為ρi2：

每個數(shù)據(jù)對象xi的真實密度定義為

根據(jù)式（8），通過計算每個數(shù)據(jù)對象的局部密度和鄰域密度比之和，有效避免K近鄰之和相同的情況，計算數(shù)據(jù)對象局部稠密情況和與其周圍鄰域的密度比值情況，真實反映數(shù)據(jù)對象在數(shù)據(jù)集中密度情況。

逆近鄰集合由文獻［14］定義，對于給定任意數(shù)據(jù)集X={x1,x2,…,xn} 中，RNNi是數(shù)據(jù)對象xi的逆近鄰集合，則數(shù)據(jù)對象xi的逆近鄰集合定義為

根據(jù)式（9），數(shù)據(jù)對象的逆近鄰集合反應(yīng)此數(shù)據(jù)對象在數(shù)據(jù)集中的被影響情況。當(dāng)數(shù)據(jù)點處在高密集區(qū)域時，通常會被較多的數(shù)據(jù)對象包圍，當(dāng)數(shù)據(jù)對象的逆近鄰對象較少時，表明此數(shù)據(jù)對象處在稀疏區(qū)域。

影響空間IS 由文獻［15］定義，則數(shù)據(jù)對象xi的IS(i)定義為

根據(jù)式（10），影響空間IS反映了數(shù)據(jù)對象之間的雙向鄰域關(guān)系，當(dāng)兩個數(shù)據(jù)對象在影響空間時，表明兩個數(shù)據(jù)對象的緊密程度大于單向K近鄰，能夠準確反映兩個數(shù)據(jù)對象的相似性較高。

共享K 近鄰由文獻［16］定義，任意兩個數(shù)據(jù)對象xi和xj的共享K近鄰個數(shù)定義如下：

對于給定任意數(shù)據(jù)集X={x1,x2,…,xn} 中，數(shù)據(jù)對象xi和xj之間的相似性定義為以下六種情況：

數(shù)據(jù)對象xi和xj存在影響空間且存在共享K近鄰，則數(shù)據(jù)對象xi和xj的相似性公式定義為

數(shù)據(jù)對象xi和xj存在影響空間但不存在共享K近鄰，則數(shù)據(jù)對象xi和xj的相似性公式定義為

數(shù)據(jù)對象xi和xj不存在影響空間但存在共享K 近鄰且xj是xi的K 近鄰，則數(shù)據(jù)對象xi和xj的相似性公式定義為

數(shù)據(jù)對象xi和xj不存在影響空間且xj不是xi的K 近鄰但存在共享K 近鄰，則數(shù)據(jù)對象xi和xj的相似性公式定義為

數(shù)據(jù)對象xi和xj不存在影響空間且不存在共享K 近鄰但xj是xi的K 近鄰，則數(shù)據(jù)對象xi和xj的相似性公式定義為

數(shù)據(jù)對象xi和xj不存在影響空間且不存在共享K 近鄰且xj不是xi的K 近鄰，則數(shù)據(jù)對象xi和xj的相似性公式定義為

上述式（12）~（17）定義數(shù)據(jù)對象之間的相似性計算方式能夠區(qū)分局部數(shù)據(jù)區(qū)域、不同簇之間的樣本。當(dāng)兩個數(shù)據(jù)對象在影響空間，我們對在影響空間內(nèi)的數(shù)據(jù)對象予以雙倍距離相似性。雙向近鄰與單向近鄰不同，單向近鄰僅僅表示某個數(shù)據(jù)對象對另外一個數(shù)據(jù)對象的聯(lián)系，不能反映兩個數(shù)據(jù)對象是否具有緊密關(guān)系。若兩個數(shù)據(jù)對象之間只存在單向近鄰，表明兩個數(shù)據(jù)對象分布在兩個不同緊密的簇或者彼此相離較遠也可能為離群點；若兩個數(shù)據(jù)對象為雙向近鄰，表明那兩個數(shù)據(jù)對象大概率分布在同簇內(nèi)或者相離較近。若兩個數(shù)據(jù)對象之間不存在影響空間但是有共享K近鄰時，表明這兩個數(shù)據(jù)對象存在共享數(shù)據(jù)對象將彼此相連，表明彼此之間具有相似性，但是相似性不高。若不存在共享K 近鄰且不存在影響空間和K 近鄰，表明兩個數(shù)據(jù)對象之間沒有相似性，這兩個數(shù)據(jù)對象的相似性為0。通過將兩個數(shù)據(jù)對象的密度做比值可得出，若密度值差異不大，比值趨近于1，表明兩個數(shù)據(jù)對象密度相似，屬于同簇中的概率較大。

數(shù)據(jù)對象xi的相似性K 近鄰集合為與xi相似性最大的K個數(shù)據(jù)對象，同時將K近鄰集合替換：

在相似性擴展聚類算法中，最常用的方法是基于距離的度量，將距離聚類中心點最近的數(shù)據(jù)對象歸屬于中心點相同的簇中，但無法考慮聚類擴展點和其周圍鄰近點的分布情況，導(dǎo)致忽略數(shù)據(jù)對象之間的密度相似性。因此在擴展聚類過程時，不僅要考慮距離相似性，同時還要考慮數(shù)據(jù)對象之間的密度分布相似性。如圖1 所示，密度之差較小時，表明同簇數(shù)據(jù)對象之間分布相似，此時兩個數(shù)據(jù)對象歸屬于相同簇的概率高。從而改進了FKNN-DPC［10］的聚類簇擴展和分配策略過程。

圖1 密度相似示意圖

對于每個未分配點xi，點xj為點xi的相似近鄰且xj已經(jīng)被分配，定義yj=c（c=1，2，…，m）表示為xj被分配所屬類標簽，wij=1/(1+dij)，γij為相似度的歸一化值，|ρi-ρj|為兩個數(shù)據(jù)對象之間的密度差異性，則歸屬度P如式（19）所示：

根據(jù)式（19），歸屬度P受兩個影響因素：1）數(shù)據(jù)對象的SimKNN；2）兩個數(shù)據(jù)對象之間的密度差異性。γij和密度差異同時決定歸屬度P，γij值越大，表明兩個數(shù)據(jù)對象距離越近，符合距離越近簇相同；密度差異越小，表明兩個數(shù)據(jù)對象之間的分布相似性越大，符合點分布相似簇相同的情況。兩個值越大表明已分配數(shù)據(jù)對象xj對未分配點xi的歸屬度影響越大，則歸屬于相同簇的概率越大。

參照文獻［7］，在聚類擴展過程中，如果兩個簇有交集，則兩個簇可能會受到交集的影響而合并為一個簇。所以根據(jù)文獻［17］篩選低密度點的方法標記低內(nèi)聚性點，數(shù)據(jù)對象xj的內(nèi)聚性β由式（20）定義，內(nèi)聚性標準值為所有點的β之和的平均值η由式（21）定義，那么低內(nèi)聚性集為低于內(nèi)聚性標準值的點集由式（22）定義。

4.2 算法描述與時間復(fù)雜度分析

算法S-DPC，輸入：數(shù)據(jù)集X，近鄰數(shù)K

輸出：簇標簽

1）數(shù)據(jù)預(yù)處理：歸一化數(shù)據(jù)。

2）依據(jù)式（3）和式（8），計算數(shù)據(jù)集X中的每個數(shù)據(jù)對象的δ和ρ值。

3）由每個數(shù)據(jù)對象的δ和ρ乘積繪制決策圖，選取決策值較高點為簇中心點，并添加至簇中心集合。

4）計算SimKNN。

5）將簇中心集合中每個未分配的數(shù)據(jù)對象j標記為已分配的簇中心，并將SimKNNj歸屬到數(shù)據(jù)對象j所在的簇，然后都添加至初始化后的隊列Queue。

6）依據(jù)式（20）、（21）和（22）計算內(nèi)聚性標準值，將內(nèi)聚性值小于標準值且未分配的數(shù)據(jù)對象標記。

7）采用近鄰擴展策略分配數(shù)據(jù)對象：

（1）選取Queue 中的第一個數(shù)據(jù)對象i，然后將滿足相似 性 值 條 件 ：Sip≥ mean （Spk） ；其 中p?SimKNNi、k?SimKNNp的對象i的未被分配且高內(nèi)聚性SimKNN分配至點i所屬的簇，并添加至Queue隊列尾部。

（2）若Queue隊列不為空，則轉(zhuǎn)至（1）。

8）使用學(xué)習(xí)概率策略分配數(shù)據(jù)對象：

（1）將步驟7）中未分配的n個數(shù)據(jù)對象構(gòu)成n×m矩陣，存儲每個未分配數(shù)據(jù)對象的，同時將矩陣每行中的最大歸屬度值max添加至列表ListP 中，最大歸屬度所屬的簇類別arg max添加至ListA中。

（2）如果還有未分配點，則搜索和分配最大歸屬度值點i對應(yīng)arg max，并轉(zhuǎn)至下一步；否則退出分配算法。

（3）更新矩陣和列表，更新SimKNNi中的每個數(shù)據(jù)對象q的歸屬度：，更新兩列表對應(yīng)的max和arg max并轉(zhuǎn)至（2）。

9）對于仍未被分配的低內(nèi)聚性數(shù)據(jù)對象，分配其到已分配的最近所在的簇中。

對S-DPC 算法進行分析，主要由以下部分構(gòu)成：計算距離為O（n2），計算共享K 近鄰為O（kn2），利用Kd-tree 查找數(shù)據(jù)對象的K 近鄰為O（nlog2(n)），計算與較高密度點最小距離為O（n2），計算逆近鄰為O（n2），計算局部密度為O（kn），計算鄰域密度比為O（kn），計算相似K近鄰為O（n2），計算內(nèi)聚性值為O（kn），近鄰擴展策略為O（n'm），學(xué)習(xí)概率策略為O（n''2）。整體的時間復(fù)雜度近似為O（kn2）。

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

實驗環(huán)境：Windows 10 64 位操作系統(tǒng)，i5-8300H 處理器，8GB RAM，編程環(huán)境為PyCharm。為了驗證算法S-DPC 性能，采用UCI 數(shù)據(jù)集，并與相關(guān)算法DPC［7］、FKNN-DPC［10］、DBSCAN［18］、AP［19］、K-means［20］進行實驗分析比較，選取6個UCI數(shù)據(jù)集，詳見表1。

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

聚類評估指標：為評估S-DPC 算法聚類性能，采用聚類準確率（Acc）、調(diào)整互信息（AMI）、調(diào)整蘭德系數(shù)（ARI）三個度量聚類性能指標［21］。

如圖2~圖4所示，S-DPC算法的聚類性能高于其他聚類算法，其主要原因是能適應(yīng)性的計算數(shù)據(jù)對象密度，正確找到聚類中心點，且擴展聚類過程中充分考慮距離和密度兩種影響因素，依據(jù)距離和密度相似并結(jié)合最相似近鄰思想，綜合擴展點與被擴展點的周圍鄰近點的距離分布情況和兩點之間的密度分布相似性擴展聚類簇，改進了FKNNDPC［10］的聚類簇擴展和分配策略過程，有效地提高聚類性能。

圖2 聚類準確率比較

圖3 調(diào)整互信息比較

圖4 調(diào)整蘭德系數(shù)比較

6 結(jié)語

本文利用數(shù)據(jù)點相似思想，提出了一種密度峰值聚類分析算法S-DPC。在本文中該算法首先將密度公式分為兩個部分，利用數(shù)據(jù)對象的K近鄰得到局部密度，再通過與其K近鄰數(shù)據(jù)對象局部密度和距離的比值得到鄰域密度值；其次針對數(shù)據(jù)對象之間的相似性，結(jié)合影響空間、共享K 近鄰和密度比提出了數(shù)據(jù)對象相似性度量方法；又結(jié)合數(shù)據(jù)對象的距離和密度相似的影響因素并與最相似近鄰結(jié)合，給出了基于距離和密度的聚類簇擴展方法，充分考慮擴展點與最相似的被擴展點的周圍情況，從而擴展聚類簇，改進了FKNN-DPC 分配策略過程，有效地提高密度聚類分析性能。