基于水波傳播特性的半監(jiān)督密度聚類算法

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695（2025）08-011-2329-06

doi：10.19734/j. issn.1001-3695.2025.01.0016

Semi-supervised density clustering algorithm based on water wave propagation characteristics

Feng Yanchaola，Wang Jiela，LiYatinglb，Cai Jianghuila.2，Yang Haifenglat （1..ScolfoerSeceamp;TohlofectinEgng，nUiesifSee amp; TaiyuanO30024，China；2.ScholofComputercienceamp;Technology，North UniversityofChina，TaiyuanO3O51China）

Abstract：Semi-superviseddensityclusteringoptimizes theclustering performance by integrating supervised informationand densityfeatures.However，whenthedataisunevenlydistributed，thetraditionalsemi-superviseddensityclusteringalgorithm isoftendificulttocapturelocaldensitydiferencesduetotheglobaldensitythresholdsettingandinsufcientuseofcostraint information，resulting inlimitedrecognitionabilityofsparseregionalclusters.Toddressthischallnge，thispaperproposed a semi-upervised densityclustering algorithm based on water wave propagation characteristics（SDR）.Inspiredbythe“constantwavecenter”and“amplitudeattenuation”characteristicsof water waves，SDR simulatedthe tendencyof clustercenter stabilityanddensitydecreasingfromcentertoboundary，andidentifiesinitialsubclustersbylocaldensitydiferences.Thealgorithmfurther utilized the neighborinfluencetoassigntheremainingpoints tothesubclusters，and dynamicallmerged these subelustersbasedonthelabelatachmentdegreeTheexperimentalresultson5syntheticdatasetsand7realdatasetsconfim the validity of SDR algorithm in sparse region clustering task.

KeyWords：semi-supervised learning;density-based clustering；water wave propagation；constrained optimizatior

0 引言

聚類是一種數(shù)據(jù)分析技術(shù)，它將數(shù)據(jù)集中的樣本劃分為若干個(gè)簇，確保同一簇內(nèi)的樣本具有較高的相似性，而不同簇之間的樣本相似性較低，從而揭示數(shù)據(jù)集的內(nèi)在結(jié)構(gòu)和模式。聚類算法可以分為劃分聚類、層次聚類、密度聚類、網(wǎng)格聚類、譜聚類等。其中，密度聚類因其在捕捉多樣化簇形狀方面的靈活性而備受推崇。該技術(shù)已被廣泛應(yīng)用于圖像處理[]、生物學(xué)[2]、時(shí)間序列預(yù)測(cè)[3]等領(lǐng)域。

由于聚類算法的無監(jiān)督特性，它本質(zhì)上屬于不適定問題[4]。為了克服這一挑戰(zhàn)，半監(jiān)督聚類算法（SSC）引人了有限的監(jiān)督信息來引導(dǎo)聚類過程。在過去幾十年中，SSC因其在眾多實(shí)際應(yīng)用中的卓越表現(xiàn)而受到廣泛關(guān)注。其中，半監(jiān)督密度聚類算法將半監(jiān)督學(xué)習(xí)與基于密度的聚類技術(shù)相結(jié)合，通過利用監(jiān)督信息來優(yōu)化聚類過程并提升其性能。Bohm等人[5]提出一種HISSCLU算法，該算法利用標(biāo)簽信息在預(yù)處理時(shí)增強(qiáng)對(duì)象的可分離性，使它可以在不同簇之間沒有自然邊界的情況下進(jìn)行聚類劃分，提高聚類性能。Lelis等人[6提出了一種SSDBCSAN算法。該算法旨在為最接近的未標(biāo)記數(shù)據(jù)分配相同的標(biāo)簽，通過標(biāo)簽計(jì)算每個(gè)聚類的自適應(yīng)半徑。Ruiz等人[7]提出了一種C-DBSCAN算法。該算法是一種基于約束的方法，保證所有的成對(duì)約束都得到滿足。Zhao等人[8]提出一種Constrained-DBSCAN算法。該算法在向簇中添加數(shù)據(jù)對(duì)象時(shí)必須滿足成對(duì)約束，根據(jù)必須鏈接的傳遞性得到傳遞閉包，然后更新不能鏈接約束集，直到簇被完全發(fā)現(xiàn)。Yang等人[9]提出一種基于多密度信息的自適應(yīng)半監(jiān)督聚類方法。該算法可以在不知道簇?cái)?shù)量的情況下，利用標(biāo)簽信息自適應(yīng)地確定不同大小、形狀和密度的簇結(jié)構(gòu)。Ren等人[10]提出一種SSDC算法。該算法生成大量的臨時(shí)簇，利用樣本的成對(duì)約束和臨時(shí)簇的相鄰信息將臨時(shí)簇合并為簇。 Vu^[11] 提出了一種高效的基于半監(jiān)督圖的聚類算法SSGC，該算法通過 k 近鄰圖與頂點(diǎn)之間的相似性度量來重新定義局部密度，并在聚類過程中使用標(biāo)簽來提高聚類質(zhì)量。楊金瑞等人[1]提出一種GS-DPC算法，該算法利用網(wǎng)格得到每個(gè)點(diǎn)的局部密度值，然后利用成對(duì)約束知道聚類過程。

然而，它們常因全局密度閾值設(shè)定與約束信息利用不足，導(dǎo)致未能充分捕捉聚類間樣本密度的差異性，特別是在密度分布不均的情況下，這種局限性制約了它們?cè)谙∈钄?shù)據(jù)區(qū)域識(shí)別簇的能力。為此，提出一種受水波啟發(fā)的半監(jiān)督密度聚類算法（SDR），SDR模擬了水波向外擴(kuò)散時(shí)水波的振幅逐漸衰減進(jìn)行聚類。SDR算法的核心思想是將簇心到簇邊界的變化類比于水波的擴(kuò)散過程。具體來說，SDR算法通過模擬水波的“波心恒定”和“振幅衰減”特性來分析相鄰數(shù)據(jù)點(diǎn)之間的密度差異及其對(duì)周圍空間的影響來識(shí)別并生成初始子簇。與傳統(tǒng)算法相比，這種機(jī)制通過引入水波傳播特性，將簇心到簇邊界的變化類比于水波的擴(kuò)散過程，能夠更自然地適應(yīng)不同密度區(qū)域之間的過渡，從而更準(zhǔn)確地劃分簇邊界。隨后將剩余點(diǎn)依據(jù)其鄰居受子簇的影響程度將它們分配給相應(yīng)的子簇。這種策略充分考慮了數(shù)據(jù)點(diǎn)之間的局部密度差異和空間關(guān)系，與傳統(tǒng)的基于全局密度或簡(jiǎn)單距離度量的分配方法相比，能夠更合理地將數(shù)據(jù)點(diǎn)分配到與其密度和空間位置相匹配的子簇中，從而提高聚類結(jié)果的準(zhǔn)確性。最后子簇根據(jù)邊界點(diǎn)的標(biāo)簽附著度合并，形成最終的簇結(jié)構(gòu)，這種方法不僅充分利用了有限的監(jiān)督信息，還能夠有效避免因誤合并而導(dǎo)致的簇結(jié)構(gòu)錯(cuò)誤。與僅依賴于距離或密度閾值的合并方法相比，具有更強(qiáng)的適應(yīng)性，有效聚類數(shù)據(jù)分布不均的復(fù)雜數(shù)據(jù)集。

1相關(guān)研究

半監(jiān)督密度聚類主要使用兩種約束信息[13]：

a）成對(duì)約束。成對(duì)約束由必須鏈接（ML）約束和不能鏈接（CL）約束組成。ML中的一對(duì)給定的數(shù)據(jù)點(diǎn)指定它們應(yīng)屬于同一簇中，CL中的一對(duì)數(shù)據(jù)點(diǎn)不能屬于同一簇。

對(duì)于一個(gè)數(shù)據(jù)集 D ，成對(duì)約束（ML和CL）集表示如下（a）ML={（x_a，x_b）|l_a=l_b，?a，b} ，點(diǎn) x_a 和 x_b 屬于同一簇。

（b）CL={（x_a，x_b）|l_a≠l_b，?a，b} ，點(diǎn) x_a 和 x_b 屬于不同簇。其中：l表示點(diǎn) x 的標(biāo)簽。

成對(duì)約束具有以下兩種特性：

（a）對(duì)稱性。 （x_a，x_b）∈ML?（x_b，x_a）∈ML，（x_a，x_b）∈ CL?（x_b，x_a）∈CL

（b）傳遞性。 （x_a，x_b）∈ML∧（x_b，x_c）∈ML?（x_a，x_c）∈ ML，（x_a，x_b）∈CL∧（x_b，x_c）∈CL?（x_a，x_c）∈CL （20

雖然成對(duì)約束可以作為先驗(yàn)知識(shí)指導(dǎo)聚類，提高聚類效果。但成對(duì)約束若存在矛盾，不僅無法助力聚類，還會(huì)削弱聚類效果，降低結(jié)果的準(zhǔn)確性和可靠性，如圖1所示，實(shí)線和虛線分別表示ML和 CL ○

圖1中 ，x_a，x_j∈C₁，x_b，x_e，x_k∈C₂ ，在分配點(diǎn) x_c 時(shí)，兩個(gè)ML存在約束矛盾導(dǎo)致分配失敗。在分配點(diǎn) x_d 時(shí)，同時(shí)存在ML和CL約束矛盾導(dǎo)致分配失敗。在分配點(diǎn) x_i 時(shí)，兩個(gè)CL存在約束矛盾導(dǎo)致分配失敗。

圖1約束矛盾的示例 Fig.1Example ofaconstraint contradiction

b）標(biāo)簽約束。相較于成對(duì)約束，標(biāo)記約束更為簡(jiǎn)潔明了，它直接指定某個(gè)數(shù)據(jù)點(diǎn)歸屬于特定的簇，避免了成對(duì)約束可能出現(xiàn)的約束沖突問題。但在非均勻分布的數(shù)據(jù)集中，標(biāo)簽約束可能導(dǎo)致聚類中心偏向數(shù)據(jù)密集區(qū)域，降低了算法在稀疏區(qū)域識(shí)別簇的能力。

2 SDR算法

2.1 基本原理

眾所周知，水波在水面上的傳播過程中，隨著傳播距離的增加，波幅逐漸減小，對(duì)周圍水面的影響也隨之減弱。然而，無論水波在擴(kuò)散過程中如何演變，它們始終源自同一波心的事實(shí)是不變的。這一現(xiàn)象揭示了波動(dòng)傳播的基本原理。

受自然界水波傳播現(xiàn)象的啟發(fā)，水波的擴(kuò)散過程與理想簇結(jié)構(gòu)中簇心穩(wěn)定、密度從中心向邊界遞減的特性高度契合。基于此，本文提出一種新的半監(jiān)督密度聚類方法SDR。SDR包含三個(gè)步驟。首先，SDR根據(jù)相鄰點(diǎn)之間的密度變化和從中心到邊界的影響遞減趨勢(shì)將相鄰點(diǎn)分配到同一簇。隨后，將剩余節(jié)點(diǎn)根據(jù)其影響空間尋找到最適合的子簇。最后通過子簇邊界點(diǎn)之間的標(biāo)簽附著度合并子簇。

2.2準(zhǔn)備工作

在本節(jié)中，將介紹與本文算法相關(guān)的基本知識(shí)。數(shù)據(jù)集D={x_i}_i=1ⁿ ，點(diǎn) x_i 與 x_j 之間的距離表示為 d_ij 。

a）第 k 個(gè)最近鄰距離[14]。點(diǎn) x_i 的第 k 個(gè)最近鄰距離表示為 d_k（x_i） 。

b） k 近鄰[14]。點(diǎn) x_i 的 k 近鄰記為 Knn（x_i） ，集合中的點(diǎn)到x_i 的距離均不超過 d_k（x_i） ： Knn（x_i）={x_p∈D/x_i|d_ip?d_k（x_i）} 。

c）逆 k 近鄰[14]。點(diǎn) x_i 的逆 k 近鄰記為 Rnn（x_i） ，集合中的點(diǎn)的 k 近鄰包含點(diǎn) 。

基于b）和c），影響空間是 Knn（x_i） 與 Rnn（x_i） 的交集。影響空間最初在文獻(xiàn)[15]中提出，其作為一種特殊的鄰域，在估計(jì)局部密度時(shí)考慮鄰域與反向鄰域的相互作用。相比Knn（x_i） 與 Rnn（x_i） ，影響空間更能反映點(diǎn)對(duì)周邊鄰域的影響，影響空間定義如下。

d）影響空間。點(diǎn) x_i 的影響空間記為 IS（x_i）：IS（x_i）= Knn（x_i）∩Rnn（x_i） 。

e）公共鄰居[16]。點(diǎn) x_i 與點(diǎn) x_j 的公共近鄰集記為 Snn（i j ） ：Snn（i，j）=Knn（x_i）∩Knn（x_j） 。

基于e），類似文獻(xiàn)[17]，計(jì)算點(diǎn) x_i 和其 k 近鄰之間的關(guān)聯(lián)度，關(guān)聯(lián)度定義如下。

f）關(guān)聯(lián)度。點(diǎn) x_i 與點(diǎn) x_j 的關(guān)聯(lián)度記為 Sim（i，j）：Sim（i，j）= ISnn（i，j）|2 ，其中 ∣Snn（i，j） |表示點(diǎn) x_i 與點(diǎn) x_j 的公 0共鄰居個(gè)數(shù)， ε 是一個(gè)極小的正數(shù)。

通過距離直接計(jì)算點(diǎn)之間的相似性，而不關(guān)注點(diǎn)所處的環(huán)境會(huì)導(dǎo)致在一些復(fù)雜的數(shù)據(jù)集上，算法可能不會(huì)產(chǎn)生令人滿意的結(jié)果。關(guān)聯(lián)度不僅考慮了點(diǎn)之間的距離，還考慮了兩點(diǎn)之間的公共鄰居，從而能夠更準(zhǔn)確地反映點(diǎn)之間的相似性和捕捉數(shù)據(jù)點(diǎn)之間的局部密度變化。因此基于f），點(diǎn) x_i 與 k 近鄰之間的關(guān)聯(lián)度總和，即為點(diǎn) x_i 的密度，點(diǎn) x_i 的密度定義如下。

g）點(diǎn) x_i 的密度。點(diǎn) x_i 的密度記為

2.3 初始子簇

基于波動(dòng)傳播思想，SDR通過深入分析相鄰點(diǎn)之間的內(nèi)在聯(lián)系及其對(duì)周圍空間的影響，有效地識(shí)別出數(shù)據(jù)集中結(jié)構(gòu)復(fù)雜且不規(guī)則的初始子簇。具體而言，主要關(guān)注兩個(gè)核心要素：首先是簇心的精準(zhǔn)選擇，其次是子簇傳播的適當(dāng)范圍。這兩個(gè)因素共同決定了子簇的質(zhì)量和后續(xù)分析的準(zhǔn)確性。

簇心在整個(gè)初始子簇中的密度最大且對(duì)周圍影響也最大，簇心的定義如下：

a）簇心。子簇 C={x_i}_i=1^m ， ?x_j∈C ，如果 ρ_j=max{ρ_i∣i= 且 則點(diǎn) x_j 為子簇 c 的簇心，記為 c_j 。

為了生成各個(gè)初始子簇，SDR從密度極大值點(diǎn)開始尋找滿足a）的簇心。確定簇心之后，從簇心出發(fā)擴(kuò)展初始子簇。在這個(gè)過程中，為了保證子簇的高純度，初始子簇中其他點(diǎn)的影響空間個(gè)數(shù)不能與簇心的影響空間個(gè)數(shù)差異過大。將初始子簇中的點(diǎn)分為擴(kuò)展點(diǎn)和邊界點(diǎn)兩類。定義如下：

果屬 ρ_agt;ρ_bgt;ρ_c 。且子 c_a，x_b，x_c∈D，x_b∈Knn（c_a），x_c∈Knn（x_b） x_b，x_c ， c_a 屬于同一初始子簇， x_b 被定義為 c_a 的擴(kuò)展點(diǎn)， x_c 被定義為 x_b 的擴(kuò)展點(diǎn)。

c）邊界點(diǎn)。 ?x_i∈C_m，C_m∈D ，如果 x_i 不存在擴(kuò)展點(diǎn)，則 x_i 被定義為邊界點(diǎn)。 B_m 表示 C_m 中的邊界點(diǎn)集。

從簇心 開始，遍歷 Knn（c） 來識(shí)別擴(kuò)展點(diǎn)和邊界點(diǎn)，隨后為每個(gè)之前識(shí)別的點(diǎn)搜索新的可擴(kuò)展點(diǎn)，直到找不到進(jìn)一步的可擴(kuò)展點(diǎn)，即為生成單個(gè)初始子簇的過程。在生成初始子簇后，將初始子簇中的所有點(diǎn)從數(shù)據(jù)集中移除。重復(fù)該過程，直到剩余數(shù)據(jù)點(diǎn)中沒有滿足條件的簇心。

2.4擴(kuò)展初始子簇

在獲得 ?_m 個(gè)初始子簇后，數(shù)據(jù)集中還有一些剩余數(shù)據(jù)點(diǎn)，通過以下方式將 m 個(gè)初始子簇?cái)U(kuò)展為 m 個(gè)子簇。

R 表示剩余點(diǎn)的集合。將 R 中的點(diǎn)按照密度進(jìn)行排序，從密度最高的剩余點(diǎn)開始，利用該節(jié)點(diǎn)的鄰居影響空間計(jì)算子簇對(duì)該點(diǎn)的影響力。影響力計(jì)算公式如下：

其中： Inf_i，j（c_m） 表示鄰居點(diǎn) x_j 對(duì)點(diǎn) x_i 屬于子簇 c_m 的影響力，x_j∈c_m 。點(diǎn) x_j 距離點(diǎn) x_i 越近，影響力越大。 |IS（x_j）∩c_m 表示x_j 的影響空間與子簇 c_m 的交集個(gè)數(shù)， IS（j）∩cm計(jì)算屬于初始子簇 c_m 的 x_j 支持 x_i 的置信度，置信度越高，影響力越大。

根據(jù)影響力計(jì)算公式可以得到點(diǎn) x_i 的單個(gè)鄰居的影響力，然后可以獲得 Knn（x_i） 中每個(gè)鄰居的影響力。找到對(duì)點(diǎn) x_i 有最大影響力的初始子簇，將點(diǎn) x_i 與該初始子簇合并，迭代地將所有剩余點(diǎn)與初始子簇合并。圖2展示了一個(gè)擴(kuò)展初始子簇的示例。如圖2（a）所示，點(diǎn) x₃ 的3個(gè) k 近鄰分別為 x₁，x₂ ，x_4ox₄ 不屬于任何子簇，故不需要計(jì)算其影響力。點(diǎn) x₁，x₂ 都屬于子簇 C₁ 中的點(diǎn)，故不需要比較影響力，直接將點(diǎn) x₃ 與子簇 C₁ 合并，如圖2（b）所示。圖2（b）中，點(diǎn) x₄ 的3個(gè) k 近鄰分別為 _x2，x5，x6 。根據(jù)影響力計(jì)算公式計(jì)算子簇 C₁ 中的點(diǎn) x₂ 對(duì)于點(diǎn) x₄ 的影響力與子簇 C₂ 中的點(diǎn) x₅ 對(duì)于點(diǎn) x₄ 的影響力，比較影響力后可知， Inf_4，2（c₁）gt;Inf_4，5（c₂） ，將點(diǎn) x₄ 與子簇 C₁ 合并，如圖2（c）所示。圖2（c）中點(diǎn) x₆ 的3個(gè) k 近鄰分別為 x₄，x₅ ，x₇ ，計(jì)算影響力后可知， Inf_6，4（c₁）5，4（c₂）+Inf_7，4（c₂） ，將點(diǎn)x₆ 與子簇 C₂ 合并。

2.5 子簇合并

數(shù)據(jù)集被分為 ?_m 個(gè)簇后，根據(jù)標(biāo)簽信息將所有的子簇分為帶標(biāo)簽子簇 lc 和未帶標(biāo)簽子簇 uc 。為解決傳統(tǒng)合并方法在密度分布不均、簇結(jié)構(gòu)復(fù)雜的場(chǎng)景下因依賴全局閾值或簡(jiǎn)單距離度量導(dǎo)致的子簇誤合并問題，引入邊界點(diǎn)的標(biāo)簽附著度作為指導(dǎo)準(zhǔn)則。該方法充分利用標(biāo)簽信息的先驗(yàn)知識(shí)，有效克服了密度差異帶來的干擾，通過動(dòng)態(tài)評(píng)估子簇間的關(guān)聯(lián)性，顯著增強(qiáng)合并過程的可靠性和準(zhǔn)確性。具體來說，以 lc 作為監(jiān)督信息，通過最大邊界附著度將 uc 合并至 lc 中，最終的簇?cái)?shù)量與提供的標(biāo)簽種類相等。最大邊界附著度公式如下：

其中： mμ_uc（lc） 表示 uc 對(duì) lc 的附著度最大， uc 和 lc 合并。 uB 是 uc 的邊界點(diǎn)集。 μ_i（lc） 表示 uB 中的點(diǎn) x_i 對(duì) lc 的附著度，其公式為

其中： lB 是 lc 的邊界點(diǎn)集； ε 是一個(gè)極小的正實(shí)數(shù)。

Fig.2Example of extending initial subclusters

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

SDR的時(shí)間復(fù)雜度可以分為三部分：a）生成初始子簇；b）擴(kuò)展初始子簇；c）子簇合并。

在生成初始子簇前，需要進(jìn)行必要的數(shù)據(jù)準(zhǔn)備，包括：獲取每個(gè)點(diǎn)的 k 近鄰集合 K_nn 和其影響空間 本文利用 kd -tree來獲得點(diǎn)的 Knn 和 IS ，時(shí)間復(fù)雜度均為 O（n?log₂n） n 是數(shù)據(jù)集中點(diǎn)的個(gè)數(shù)。點(diǎn)間的相似度基于 Snn ，時(shí)間復(fù)雜度為 O（k ·n?d） ，k是點(diǎn)的鄰居數(shù)， d 是點(diǎn)的維數(shù)。點(diǎn)的密度基于點(diǎn)的關(guān)聯(lián)度計(jì)算，只需查詢每個(gè)點(diǎn)的 K_nn ，時(shí)間復(fù)雜度為 O（k?n） 。

構(gòu)建初始子簇時(shí)，為了方便尋找子簇心，首先生成一個(gè)按密度降序排列的點(diǎn)隊(duì)列，時(shí)間復(fù)雜度為 O（n?log₂n） 。檢查該節(jié)點(diǎn)是否是子簇心的時(shí)間復(fù)雜度 O（m?n₁），m 是子簇的個(gè)數(shù)， m 遠(yuǎn)小于 n，n₁ 是每個(gè)子簇的平均節(jié)點(diǎn)數(shù)。構(gòu)建初始子簇的時(shí)間復(fù)雜度是 O（n+n?n₁） 。這部分總的時(shí)間復(fù)雜度是O（n?log₂n） 。

擴(kuò)展初始子簇時(shí)，為了優(yōu)化效率，首先將剩余點(diǎn)按密度降序排列，時(shí)間復(fù)雜度為 為剩余點(diǎn)數(shù)量。擴(kuò)展子簇的時(shí)間復(fù)雜度是 O（n₂?m?k?d） 。在子簇中傳播標(biāo)簽的時(shí)間復(fù)雜度最大為 O（m?n₁） 。這部分總的時(shí)間復(fù)雜度小于O（n₂?log₂n₂+n₂?m?k?d+m?n₁） 。

合并子簇的過程，其實(shí)就是標(biāo)簽傳遞的過程。首先將帶標(biāo)簽子簇和不帶標(biāo)簽子簇區(qū)分開，時(shí)間復(fù)雜度為 O（m） 。將邊界點(diǎn)集分為帶標(biāo)簽邊界點(diǎn)集和不帶標(biāo)簽邊界點(diǎn)集，時(shí)間復(fù)雜度為O（m） 。標(biāo)簽傳遞的時(shí)間復(fù)雜度是 O（n₃?p） ，其中 n₃ 是不帶標(biāo)簽邊界點(diǎn)集的平均節(jié)點(diǎn)數(shù)， ?_?p 為邊界點(diǎn)集中點(diǎn)影響空間的并集點(diǎn)數(shù)。

綜上所述，SDR 的時(shí)間復(fù)雜度約為 O（n?log₂n） 。

2.7 SDR算法流程

算法 SDR

輸入：原始數(shù)據(jù)集 D ，近鄰參數(shù) k □

輸出：聚類結(jié)果 C_L 。

a）數(shù)據(jù)預(yù)處理：計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的密度 ρ 和其影響空間 IS

b）數(shù)據(jù)初始化：根據(jù)密度 ρ 對(duì)數(shù)據(jù)點(diǎn)由大到小進(jìn)行排序，記為 D_U 。c）識(shí)別簇心并從簇心出發(fā)擴(kuò)展初始子簇，識(shí)別擴(kuò)展點(diǎn)和邊界點(diǎn)，并將初始子簇中的點(diǎn)從 D_U 中移除。

d）判斷 D_U 中是否還有滿足簇心條件的點(diǎn)，若有，則跳轉(zhuǎn)到步驟c），否則，將 D_U 中剩余的點(diǎn)根據(jù)式（1）分配給相應(yīng)的初始子簇并將其

從 D_U 中移除。

e）判斷 D_U 中是否還有剩余的點(diǎn)，若有，則跳轉(zhuǎn)到步驟d），否則根據(jù)式（2）和（3）合并子簇。f）輸出聚類結(jié)果 C_L 。

3 實(shí)驗(yàn)分析

在本章中，為了驗(yàn)證算法的性能，在7個(gè)真實(shí)數(shù)據(jù)集和5個(gè)合成數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。將SDR的實(shí)驗(yàn)結(jié)果與5種對(duì)比算法進(jìn)行了比較。比較算法包括LDP-SC[18] SSE^[19] 、 EC^[20] SSDC[10]和 SSGC[11]。在實(shí)驗(yàn)中，本文方法和對(duì)比方法都是在Python3.10中實(shí)現(xiàn)的。實(shí)驗(yàn)在16GBRAM、單核CPU（ Intel^B Core（TM）i7-8750H CPU @ ）、Windows1064位操作系統(tǒng)上進(jìn)行。

3.1實(shí)驗(yàn)數(shù)據(jù)與評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)使用的數(shù)據(jù)集包括5個(gè)2D合成數(shù)據(jù)集（aggrega-tion[21]、compound[21]、complex[21]R15[21] ），圖3展示了合成數(shù)據(jù)集的分布，3個(gè)多元數(shù)據(jù)集（ z00^[22] 、 ecoli^[23] 、bank-note authentication[22]）和4個(gè)圖像數(shù)據(jù)集（ USPS^[24] 、gisette[25]COIL20[26]、Jaffe[27]）。表1總結(jié)了這12個(gè)數(shù)據(jù)集。

圖3合成數(shù)據(jù)集的分布Fig.3Distribution of synthetic datasets表1數(shù)據(jù)集Tab.1Datasets

六種算法中除SSE不需要參數(shù)外，SDR、LDP-SC和SSGC的最近鄰居 k 的取值為3～30，步長(zhǎng)為1。EC的參數(shù)δ等于 k 乘以截?cái)嗑嚯x d_c ，其中 k 取值為1～5。SSDC需要輸入√n或 作為臨時(shí)集群中心。本文隨機(jī)選擇不同類別的樣本，并使用所選擇的樣本進(jìn)一步構(gòu)建標(biāo)簽和成對(duì)約束。所有實(shí)驗(yàn)的比較都是在相同約束數(shù)量下進(jìn)行，保證實(shí)驗(yàn)公平性。為了減少約束的隨機(jī)性影響，所有實(shí)驗(yàn)結(jié)果均是十次實(shí)驗(yàn)結(jié)果的平均值。

為了評(píng)估這些算法的聚類性能，采用了三種常用的指標(biāo)，調(diào)整蘭德指數(shù)（ARI）、歸一化互信息（NMI）、精確率（ACC），其詳細(xì)計(jì)算公式為

其中： =TP+FP+TN+FN;TP表示被正確分類為正的實(shí)際為正的樣本數(shù)量； TN 表示被正確分類為負(fù)類的實(shí)際為負(fù)類的樣本數(shù)量； FP 表示實(shí)際上是負(fù)類但被錯(cuò)誤地分類為正類的樣本數(shù)量； FN 表示實(shí)際上是正類但被錯(cuò)誤地分類為負(fù)類的樣本數(shù)量； I（X，Y）=H（X）–H（X∣Y） ，表示 X 和 Y 之間的互信息；H（X） 和 H（Y） 表示 X 和 Y 的熵； H（X∣Y） 是給定 Y 后 X 的條件熵； p_i 為實(shí)驗(yàn)聚類結(jié)果； q_i 為點(diǎn) x_i 的真實(shí)標(biāo)簽。如果 Φ?x=y，δ（Φx y）=1 ，否則， δ（x，y）=0 。 map（x） 是一個(gè)最優(yōu)映射函數(shù)，它使用Kuhn-Munkres算法[28]來排列簇標(biāo)簽以匹配真實(shí)標(biāo)簽。NMI和ACC的取值均為[0，1]，ARI的取值為[-1，1]。值越大，聚類效果越好。

3.2 參數(shù)分析

SDR存在一個(gè)可調(diào)節(jié)參數(shù) k ，參數(shù) k 被用在計(jì)算節(jié)點(diǎn)密度、構(gòu)建初始子簇、擴(kuò)展剩余點(diǎn)、子簇合并上，貫穿了整個(gè)算法過程。圖4給出了SDR在5個(gè)合成數(shù)據(jù)集上參數(shù) k 的表現(xiàn)。研究結(jié)果表明，大多數(shù)數(shù)據(jù)集在 k 值較小時(shí)都能達(dá)到較高的ARI得分，顯示出較好的聚類性能，并且對(duì)參數(shù) k 不敏感，但是ARI對(duì)compound數(shù)據(jù)集上的參數(shù) k 有點(diǎn)敏感。圖5給出了SDR在7個(gè)真實(shí)數(shù)據(jù)上參數(shù) k 的表現(xiàn)，在大多數(shù)情況下，SDR可以將最佳的 k 值設(shè)置在較小的范圍內(nèi)（即 k∈[5，20] ）。

圖4不同參數(shù) k 在合成數(shù)據(jù)集上ARI表現(xiàn)比較Fig.4Comparison of ARI performance ofdifferentparameters k onsynthetic datasets

圖5不同參數(shù) k 在真實(shí)數(shù)據(jù)集上ARI表現(xiàn)比較.5Comparison of ARI performance of different parametel k on real datasets

3.3 聚類結(jié)果分析

為了保證實(shí)驗(yàn)的公平性，本文在數(shù)據(jù)集上隨機(jī)標(biāo)注約束條件。約束是通過隨機(jī)選擇標(biāo)簽構(gòu)造的，數(shù)量不超過數(shù)據(jù)集點(diǎn)總數(shù)的 10% 。記錄每組10次實(shí)驗(yàn)結(jié)果的平均值以減少標(biāo)簽隨機(jī)性對(duì)聚類結(jié)果造成的影響。圖6表示六種算法在合成數(shù)據(jù)集上的ARI表現(xiàn)。在5個(gè)合成數(shù)據(jù)集上，SDR均取得了最優(yōu)的ARI表現(xiàn)。圖7表示六種算法在真實(shí)數(shù)據(jù)集上的ARI表現(xiàn)。在大多數(shù)真實(shí)數(shù)據(jù)集上，SDR都取得最優(yōu)的ARI表現(xiàn)，而在USPS和Jaffe數(shù)據(jù)集上取得了次優(yōu)的ARI表現(xiàn)。

圖6六種算法在合成數(shù)據(jù)集上的ARI表現(xiàn)

圖7六種算法在真實(shí)數(shù)據(jù)集上的ARI表現(xiàn)

圖89展示了六種算法在合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的NMI，在合成數(shù)據(jù)集上SDR均取得最優(yōu)的NMI。在大多數(shù)真實(shí)數(shù)據(jù)集上，SDR也取得了最優(yōu)的NMI，在USPS數(shù)據(jù)集上取得次優(yōu)的NMI，在Jaffe數(shù)據(jù)集上距最優(yōu)的NMI僅差O.0117。

圖8六種算法在合成數(shù)據(jù)集上的NMI表現(xiàn)

Fig.8NMI performance of six algorithms on synthetic datasets

圖9六種算法在真實(shí)數(shù)據(jù)集上的NMI表現(xiàn)

Fig.9NMI performance of six algorithms on real datasets

圖10、11展示了六種算法在合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的ACC，在合成數(shù)據(jù)集上SDR均取得最優(yōu)的ACC。在大多數(shù)真實(shí)數(shù)據(jù)集上，SDR也取得了最優(yōu)的ACC，在ecoli與Jaffe數(shù)據(jù)集上取得次優(yōu)的NMI，在USPS數(shù)據(jù)集上距最優(yōu)的ACC僅差0.0052。這些結(jié)果說明了SDR在密度分布不均勻、簇形狀復(fù)雜的數(shù)據(jù)集上的優(yōu)越性。圖12展示了SDR算法在合成數(shù)據(jù)集上的可視化結(jié)果。結(jié)果表明，SDR算法可以清晰地識(shí)別出復(fù)雜數(shù)據(jù)集中的簇邊界，并有效聚類出稀疏區(qū)域中的簇。

圖10六種算法在合成數(shù)據(jù)集上的ACC表現(xiàn)

圖11六種算法在真實(shí)數(shù)據(jù)集上的ACC表現(xiàn)

圖12SDR算法在合成數(shù)據(jù)集上的聚類結(jié)果

2ig.12Clustering results of SDR algorithm on synthetic datasets

弗里德曼檢驗(yàn)[29]用于比較各算法的排名，表2給出了各算法的弗里德曼檢驗(yàn)平均排名。算法的平均排名越高，聚類精度越優(yōu)。在ARI的排名中，SDR、SSGC、LDP-SC、SSDC、SSE、EC的排名依次下降。在NMI的排名中，SDR與LDP-SC依次排名第一、第二，其后依次是SSGC、SSE、SSDC、EC。在ACC排名中，SDR排名第一，其后依次是EC、SSDC、LDP-SC、SSGC、SSE。整體來看，SDR擁有最優(yōu)的聚類性能。

表2算法ARI、NMI的平均排名

Tab.2Average ranking of algorithms ARI and NMI

3.4 實(shí)現(xiàn)過程

圖13展示了SDR算法在處理aggregation數(shù)據(jù)集時(shí)的實(shí)現(xiàn)過程，重點(diǎn)呈現(xiàn)了該算法在簇邊界不清晰的兩個(gè)復(fù)雜簇上的實(shí)現(xiàn)效果。如圖13所示，灰色點(diǎn)表示未帶標(biāo)簽的數(shù)據(jù)點(diǎn)，紅色和藍(lán)色點(diǎn)分別表示帶有不同標(biāo)簽的數(shù)據(jù)點(diǎn)（見電子版）。算法基于數(shù)據(jù)點(diǎn)的局部密度差異識(shí)別初始子簇。對(duì)每個(gè)點(diǎn)計(jì)算密度ρ 和影響空間 IS 。從密度最高的點(diǎn)開始，選擇滿足簇心條件的點(diǎn)作為簇心。隨后，從簇心出發(fā)擴(kuò)展初始子簇，如圖13（a）所示。圖13（b）中，生成初始子簇后，數(shù)據(jù)集中仍存在未分配的剩余點(diǎn)（未被藍(lán)色虛線包圍的點(diǎn)）。通過式（1）計(jì)算初始子簇對(duì)這些剩余點(diǎn)的影響力，從密度最大的剩余點(diǎn)開始迭代地將所有剩余點(diǎn)合并至初始子簇中，如圖13（c）所示。在圖13（c）中，若子簇中存在帶標(biāo)簽的點(diǎn)，則該子簇中的所有點(diǎn)都被標(biāo)記為相同的標(biāo)簽。在圖13（d）中，將所有子簇分為帶標(biāo)簽子簇 lc 和未帶標(biāo)簽子簇 uc ，通過式（3）計(jì)算 uc 對(duì)各 lc 的邊界附著度，通過式（2）將所有的 uc 合并至所屬的 l_c 中，如圖13（d）所示。圖13（e）展示了最終的聚類結(jié)果。經(jīng)過子簇合并，所有數(shù)據(jù)點(diǎn)被劃分至與標(biāo)簽一致的簇中，邊界稀疏區(qū)域中的點(diǎn)被正確歸類，簇邊界也更加清晰。

Fig.13Realization process of SDR algorithm

4結(jié)束語

本文提出一種有效的半監(jiān)督密度聚類算法SDR，靈感源自水波傳播的波心恒定和振幅衰減特性。該算法以關(guān)聯(lián)度替代傳統(tǒng)歐氏距離，更精準(zhǔn)地反映局部密度變化，并受水波兩種特性的啟發(fā)，模擬簇心的穩(wěn)定性及密度從中心向邊界遞減的趨勢(shì)，無須全局閾值即可捕捉局部密度差異。其由標(biāo)簽引導(dǎo)的合并子簇的策略在避免約束矛盾的同時(shí)提高了標(biāo)簽信息的利用效率。實(shí)驗(yàn)表明，SDR在密度分布不均勻、簇形狀復(fù)雜的數(shù)據(jù)集上具有很強(qiáng)的競(jìng)爭(zhēng)力。盡管SDR對(duì)參數(shù) k 存在一定的敏感性，但其基于波心恒定和振幅衰減特性的獨(dú)特聚類策略顯著提升了聚類的準(zhǔn)確性。未來的研究方向?qū)⒓杏谙齾?shù)依賴，發(fā)展更為通用的無參數(shù)半監(jiān)督密度聚類算法，以進(jìn)一步拓展其應(yīng)用范圍和提升效率。

參考文獻(xiàn)：

[1]Lian Chunfeng，Ruan Su，Denoeux T，et al.Joint tumor segmentation in PET-CT images using co-clustering and fusion based on belief functions [J].IEEETrans on ImageProcessing，2019，28（2）：755-766.

[2]MaheshwariR，Mishra AC，Mohanty SK.Anentropy-based density peakclustering for numerical gene expression datasets[J].Applied SoftComputing，2023，142：110321.

[3]BangYK，LeeCH.Fuzzytime seriesprediction usinghierarchical clustering algorithms[J].Expert Systemswith Applications， 2011，38（4）：4312-4325.

[4] XuDongkuan，TianYingjie.Acomprehensive surveyofclustering algorithms[J].AnnalsofDataScience，2015，2（2）：165-193.

[5]BohmC，PlantC.HISSCLU：ahierarchical density-based method for semi-supervisedclustering[C]//Procofthe11th InternationalConference on Extending Database Technology Advances in Database Technology.New York：ACMPress，2008：440-451.

[6]LelisL，Sander J.Semi-supervised density-based clustering[C]// Proc of the9th IEEE International Conference onData Mining.Piscataway，NJ： IEEE Press，2009： 842-847.

[7]Ruiz C，Spiliopoulou M，Menasalvas E. Density-based semi-supervisedclustering[J].Data Miningand Knowledge Discovery， 2010，21（3）： 345-370.

[8]Zhao Weizhong，He Qing，Ma Huifang，et al. Effective semi-superviseddocument clustering via active learning with instance-level constraints[J]. Knowledge and Information Systems，2012，30 （3）：569-587.

[9]Yang Yun，Li Zongze，Wang Wei，et al.An adaptive semi-supervised clustering aproach via multiple density-based information[J]. Neurocomputing，2017，257：193-205.

[10]Ren Yazhou，Hu Xiaohui，ShiKe，etal.Semi-supervised denpeak clustering with pairwise constraints [C]// Proc of the 15th Pacific Rim International Conference on Artificial Intellgence.Berlin： Springer， 2018： 837-850.

[11]Vu V V. An efficient semi-supervised graph based clustering[J]. Intelligent Data Analysis，2018，22（2）：297-307.

[12]楊金瑞，劉繼．基于網(wǎng)格的半監(jiān)督密度峰值聚類算法［J]．軟件 工程，2024，27（5）：1-6.（YangJinrui，Liu Ji.A grid-based semisupervised density peak clustering algorithm[J].Software Engineering，2024，27（5）：1-6.）

[13]Zhu Xiaojin，Goldberg AB.Introduction to semi-supervised learning [M]//Synthesis Lectures on Artificial Intelligence and Machine Learning.Berlin：Springer，2009：130.

[14]Wang Fei，Li Le，Liu Zhiqiang.Stratification-based semi-supervised clusterig algorithm for arbitrary shaped datasets[J].Information Sciences，2023，639：119004.

[15] Jin W，Tung A K H， Han J，et al.Ranking outliers using symmetric neighborhoodrelationship[C]//Proc of the1OthPacific-Asia Conference on Knowledge DiscoveryandData Mining.Berlin：Springer， 2006： 577-593.

[16]Yang Xuan，Xiao Fuyuan. An improved density peaks clustering algorithm based on the generalized neighbors similarity[J]. Engineering Applications of Artificial Intelligence，2024，136：108883.

[17]Liu Rui，Wang Hong，Yu Xiaomei. Shared-nearest-neighbor-based clustering by fast search and find of density peaks [J].Information Sciences，2018，450：200-226.

[18]Long Zhiguo，Gao Yang，Meng Hua，et al. Clustering based on local density peaks and graph cut [J]. Information Sciences，2022， 600： 263-286.

[19]Zeng Guangjie，Peng Hao，Li Angsheng，et al.Semi-supervised clusterig via structural entropy with different constraints [C]//Proc ofSIAM International Conference on Data Mining.2O24：2O8-216.

[20]Wang Shuliang，Li Qi， Zhao Chuanfeng，et al. Extreme clustering a clustering method via density extreme points [J]. Information Sciences，2021，542：24-39.

[21]FrantiP，SieranjaS.K-meanspropertisonsixclusterigbncark datasets[J].Applied Intelligence，2018，48（12）： 4743-4759.

[22]Asuncion A，Newman D.UCI machine learning repository[DB/ OL].（2007）.https：//archive. ics. uci. edu/datasets.

[23]Nakai K，Kanehisa DM.Expert system for predicting proteinlocali zationsitesingram-negativebacteria[J].Proteins：Structure， Function，and Bioinformatics，1991，11（2）：95-110.

[24]Hull JJ. A database for handwritten text recognition research [J]. IEEETranson Pattern AnalysisandMachine Intelligence， 1994，16（5）：550-554.

[25]Guyon I， Gunn S，Ben-Hur A，et al.Result analysis of the NIPS 2003 feature selection challenge[C]//Proc of the 18th International Conference on Neural Information Processing Systems. Camberidge， MA：MIT Press，2004：545-552.

[26]Nene SA，Nayar SK，Murase H. Columbia object image library （coil-20）[DB/OL].（1996）.https：//git-isl. github. io/GTDLBench/datasets/coil20/.

[27]Lyons M，AkamatsuS，KamachiM，etal.Codngfacialexpresion with Gabor wavelets [C]//Proc the 3rd IEEE International Conference on Automatic Faceand Gesture Recognition. Piscataway，NJ： IEEE Press，1998：200-205.

[28]Munkres J. Algorithms for the assignment and transportation problems [J].Journal of the Society for Industrial and Applied Mathematics，1957，5（1） ： 32-38.

[29] Zimmerman D W， Zumbo B D. Relative power of the Wilcoxon test， the Friedman test，and repeated-measuresANOVAonranks[J]. The Journal of Experimental Education，1993，62（1）：75-86.

收稿日期：2025-01-13；修回日期：2025-03-21 基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（12473105）

作者簡(jiǎn)介：馮彥超（1998—），男，山西人，碩士研究生，CCF會(huì)員，主要研究方向?yàn)閿?shù)據(jù)挖掘與并行計(jì)算；王杰（1990—），男，山西人，講師，博士，主要研究方向?yàn)閿?shù)據(jù)挖掘與機(jī)器學(xué)習(xí)；栗雅婷（195—），女，山西壺關(guān)人，博士研究生，主要研究方向?yàn)閿?shù)據(jù)挖掘與自監(jiān)督學(xué)習(xí);蔡江輝（1978—），男，山西人，教授，博士，主要研究方向?yàn)閿?shù)據(jù)挖掘與機(jī)器學(xué)習(xí)；楊海峰（1980—），男（通信作者），山西人，教授，博士，主要研究方向?yàn)閿?shù)據(jù)挖掘與機(jī)器學(xué)習(xí)（6202115310018@ stu.tyust.edu.cn）.