關(guān)鍵詞：密度峰值聚類;網(wǎng)格;半監(jiān)督;STING;成對約束

中圖分類號：TP399 文獻標(biāo)志碼：A

0 引言（Introduction）

聚類是用于大量數(shù)據(jù)分析和數(shù)據(jù)處理的基礎(chǔ)。近年來，聚類分析在不同的領(lǐng)域都得到了廣泛的應(yīng)用，如數(shù)據(jù)分析、圖像分析、生物學(xué)研究、醫(yī)療診斷、市場研究等[1-2]。聚類方法也有多種分類，有基于劃分的聚類方法、基于分層的聚類方法、基于密度的聚類方法等，但基于密度的聚類方法可以在不需要預(yù)先知道類簇的數(shù)量的條件下，對任意形狀的數(shù)據(jù)集進行聚類和對數(shù)據(jù)集中的噪聲數(shù)據(jù)進行有效的處理。因此，基于密度的聚類方法受到了研究者的廣泛關(guān)注。

本文以密度峰值聚類算法為基礎(chǔ)算法，提出了一種基于網(wǎng)格的半監(jiān)督密度峰值聚類（Grid-based Semi-supervised DensityPeak Clustering，GS-DPC）算法。該算法使用網(wǎng)格聚類算法———統(tǒng)計信息網(wǎng)格法（Statistical Information Grid，STING），對數(shù)據(jù)集進行網(wǎng)格劃分，拓展了大數(shù)據(jù)聚類的空間，并提高了聚類的效率;在對數(shù)據(jù)點進行分配的過程中，引入成對約束集，提高了聚類的質(zhì)量。

1 相關(guān)研究（Related research）

2014年，RODRIGUEZ等[3]提出了密度峰值聚類（DensityPeak Clustering，DPC）算法，該聚類算法的參數(shù)較少，不需要迭代就可以快速地找到任意形狀的數(shù)據(jù)集的聚類中心，但該算法對于截斷距離的選取具有主觀性，而截斷距離決定了局部密度的大小，會直接影響聚類的結(jié)果，并且該算法無法對大規(guī)模數(shù)據(jù)集進行快速有效的聚類。如果一個數(shù)據(jù)集的規(guī)模較大，密度峰值聚類算法的時間復(fù)雜度為O（n2），要得到聚類結(jié)果需耗費較長的時間。

為了能夠有效并快速地處理大規(guī)模數(shù)據(jù)集，SARANG[4]說明了STING算法是一種基于層次統(tǒng)計信息網(wǎng)格的空間數(shù)據(jù)挖掘方法，其思想是在不求助于單個對象的情況下回答整個類別的查詢和聚類問題，并且這些聚類技術(shù)在計算上的空間復(fù)雜度僅為O（n）。

考慮到密度峰值聚類算法時間復(fù)雜度高的問題，部分學(xué)者將網(wǎng)格聚類算法與密度峰值聚類算法相結(jié)合，由于網(wǎng)格聚類算法和密度峰值聚類算法在聚類思想和原理上有一定的差異，將它們結(jié)合起來可以充分發(fā)揮各自的優(yōu)勢，并彌補彼此的不足。因此，在密度峰值聚類算法的基礎(chǔ)上引入網(wǎng)格聚類算法，提出的新算法不僅具有密度峰值聚類算法的優(yōu)點，還能快速地對大規(guī)模數(shù)據(jù)集進行聚類[5-6]。DU等[7]提出了一種新的基于網(wǎng)格的聚類算法，首先，使用標(biāo)準(zhǔn)網(wǎng)格結(jié)構(gòu)定義節(jié)點的密度估計;其次，使用迭代邊界檢測策略區(qū)分核心節(jié)點和邊界節(jié)點;最后，結(jié)合兩種聚類策略對核心節(jié)點進行分組并分配邊界節(jié)點，提高了對不同密度集群的識別能力。DING等[8]使用采樣方法減少距離計算，通過改進的TI搜索策略識別近似代表，使用DPC算法對近似代表進行聚類，提高處理大規(guī)模數(shù)據(jù)集的能力。

為了避免浪費已知的數(shù)據(jù)信息，有部分學(xué)者充分利用少量的已知信息與聚類算法相結(jié)合，這是因為少量的已知信息可以作為先驗知識，并通過聚類算法將其傳遞給未標(biāo)記數(shù)據(jù)，這種知識遷移可以幫助聚類算法更準(zhǔn)確地劃分?jǐn)?shù)據(jù)簇，提高了聚類結(jié)果的質(zhì)量。GOEL[9]利用線性插值插補技術(shù)先插補數(shù)據(jù)集缺失的特征，并且在使用半監(jiān)督聚類的過程中不僅考慮了缺失的特征，還考慮了數(shù)據(jù)集的可用知識（標(biāo)簽）。徐久成等[10]在隸屬度計算中加入半監(jiān)督的函數(shù)式，重新定義了半監(jiān)督模糊C均值聚類的目標(biāo)函數(shù)，應(yīng)用TWED（Time Warp Edit Distance）代替?zhèn)鹘y(tǒng)的歐氏距離，從而更精確地度量時間序列數(shù)據(jù)與聚類中心之間的距離。

由于傳統(tǒng)的密度峰值聚類算法依賴于數(shù)據(jù)點的局部密度和距離的計算，而監(jiān)督信息可以為聚類添加先驗知識和專家指導(dǎo)。因此，部分學(xué)者為了提高密度峰值聚類算法的聚類質(zhì)量，在使用密度峰值聚類算法聚類的過程中引入了監(jiān)督信息指導(dǎo)聚類，從而對聚類結(jié)果進行更準(zhǔn)確的判斷和解釋，提高了聚類的準(zhǔn)確性，解決了類別不平衡的問題。例如：羅丹等[11]利用Must-link約束疊加數(shù)據(jù)點的密度、Cannot-link約束分離n 級最近鄰居，從而得到聚類中心，提高了聚類的效果。劉如輝等[12]利用相對密度方式度量節(jié)點密度，并使用約束信息指導(dǎo)聚類的過程。

以上研究對密度峰值聚類算法進行了一定程度的改進，引入網(wǎng)格提高了密度峰值聚類算法的計算效率;引入監(jiān)督信息指導(dǎo)聚類過程，提高了聚類的質(zhì)量和魯棒性，但忽略了由于引入網(wǎng)格帶來的精確度問題和引入監(jiān)督信息帶來的計算效率問題。因此，如何利用數(shù)據(jù)本身的特殊信息提升規(guī)模數(shù)據(jù)聚類效率成為新的研究方向，本文提出了一種基于網(wǎng)格的半監(jiān)督密度峰值聚類算法。

2 相關(guān)知識（Related knowledge

2.1STING網(wǎng)格聚類算法

STING是一種無監(jiān)督的多分辨率聚類技術(shù)[13]，該聚類算法基于網(wǎng)格的計算是獨立于查詢的，并且計算效率高，但聚類算法的質(zhì)量通常與數(shù)據(jù)對象的數(shù)量無關(guān)，而是取決于網(wǎng)格結(jié)構(gòu)最底層的粒度，如果劃分的粒度較細(xì)，需要計算的網(wǎng)格就會增加，從而提高了計算效率;如果劃分的粒度較粗，有些邊界點可能會劃分到其他類簇的網(wǎng)格中，導(dǎo)致聚類的精確度下降。

定義1（STING網(wǎng)格劃分[5]）：根據(jù)公式（1）計算網(wǎng)格劃分的尺度參數(shù)ε，對數(shù)據(jù)空間進行網(wǎng)格劃分。

ε=n/k （1）

其中：n 是樣本數(shù)據(jù)集中數(shù)據(jù)點的個數(shù)，k 是數(shù)據(jù)空間維度的個數(shù)，則每個維度被分為ε 等分。

2.2 密度峰值聚類算法RODRIGUEZ等[3]于2014年在Clustering by fast searchand find of density peaks 一文中提出一種新穎的有關(guān)密度的聚類算法，即密度峰值聚類算法，該算法有兩個基本的假設(shè)：自身的密度較大，而周圍都是其他密度較低的數(shù)據(jù)點;與其他密度大的數(shù)據(jù)點距離相對較遠(yuǎn)。密度峰值聚類算法中有局部密度和相對距離兩個參數(shù)。密度峰值聚類算法綜合考慮了局部密度和相對距離的特征，能夠發(fā)現(xiàn)具有不同密度水平的簇，并在不需要預(yù)先指定簇數(shù)目的情況下進行聚類，它在處理各種類型的數(shù)據(jù)集時具有一定的優(yōu)勢，并且對于噪聲點和邊界點的處理也相對魯棒。

定義2（局部密度）：局部密度的兩種計算公式如下。

3 基于網(wǎng)格的半監(jiān)督密度峰值聚類算法（Gridbasedsemi-supervised density peak clusteringalgorithm）

3.1 算法描述

目前，聚類技術(shù)在眾多領(lǐng)域都得到了廣泛應(yīng)用，人們對聚類算法的要求越來越高，而密度峰值聚類算法作為一種使用密度進行聚類的無監(jiān)督聚類算法，雖然該算法的聚類質(zhì)量比其他聚類算法的聚類質(zhì)量高，但是該算法沒有利用少量的已知信息指導(dǎo)聚類，并且無法快速有效地處理大規(guī)模的數(shù)據(jù)集，而高質(zhì)量的先驗信息不僅可以指導(dǎo)沒有標(biāo)注的樣本進行正確聚類，提高聚類結(jié)果的準(zhǔn)確性，還可以加快聚類的收斂速度。因此，本文使用STING網(wǎng)格劃分技術(shù)對樣本數(shù)據(jù)集進行網(wǎng)格劃分，計算每個網(wǎng)格的網(wǎng)格代表點，克服了密度峰值聚類算法中主觀選擇截斷距離dc 的缺陷;在分配數(shù)據(jù)點的過程中，引入成對約束集即Must-link約束和Cannot-link約束，要求每個被分配的數(shù)據(jù)點滿足成對約束集，從而提高聚類質(zhì)量。

3.2 相關(guān)定義

定義4（成對約束集[11]）：成對約束集中包括Must-link約束和Cannot-link約束，Must-link約束表示兩個數(shù)據(jù)樣本點必須屬于同一個類簇;Cannot-link約束表示兩個數(shù)據(jù)樣本點必須屬于不同的類簇。

3.4 違反約束的分配規(guī)則

對于一個有k 個類簇的數(shù)據(jù)集，若在選取完聚類中心后，對非中心點進行分配的過程中，沒有按照給定的成對約束集進行分配，則需要計算兩點之間的距離重新進行分配，可能出現(xiàn)的情況如下。

情況1：若存在兩個數(shù)據(jù)樣本點A 和B 都屬于Must-link約束集，但兩個數(shù)據(jù)點被分配到不同的類簇中，則采用最近距離進行分配，計算數(shù)據(jù)點A 到類簇1和類簇2的距離并計算數(shù)據(jù)點B 到類簇1和類簇2的距離，將計算獲得的4個距離進行比較，選擇距離最小的類簇進行分配。

情況2：若存在兩個數(shù)據(jù)樣本點A 和B 都屬于Cannot-link約束集，但兩個樣本數(shù)據(jù)點A 和B 被分配到了同一個類簇中，則將遍歷到的第一個數(shù)據(jù)樣本點A 或B 按照約束規(guī)則進行分配，將另一個數(shù)據(jù)樣本點B 或A 分配給次近中心點所在的類簇中。

情況3：若存在4個數(shù)據(jù)樣本點A、B、C、D，其中數(shù)據(jù)點A與數(shù)據(jù)點D 為Must-link約束集，數(shù)據(jù)點C 與數(shù)據(jù)點D 為Cannot-link約束集，數(shù)據(jù)點D 在數(shù)據(jù)點A 和數(shù)據(jù)點C 之間，則計算數(shù)據(jù)點D 到數(shù)據(jù)點A 的距離和數(shù)據(jù)點D 到數(shù)據(jù)點C 的距離，將兩者進行比較，數(shù)據(jù)點D 的分配規(guī)則遵循距離最近的數(shù)據(jù)點的分配規(guī)則，違反約束的數(shù)據(jù)點分配圖如圖1所示。

3.5 算法步驟

基于網(wǎng)格的半監(jiān)督的密度峰值聚類算法步驟如下。

GS-DPC算法

輸入：樣本數(shù)據(jù)點X= x₁，x₂，…，x_n ，Must-link約束集，Cannot-link約束集

輸出：聚類結(jié)果

步驟1：根據(jù)STING網(wǎng)格劃分技術(shù)，將樣本數(shù)據(jù)集X =x₁，x₂，…，x_n 映射到相應(yīng)的網(wǎng)格中。

步驟2：根據(jù)公式（5）計算每個網(wǎng)格的網(wǎng)格代表點。

步驟3：根據(jù)公式（6）計算局部密度和公式（7）計算相對距離。

步驟4：以局部密度ρ 作為決策圖的橫軸，以相對距離δ 作為決策圖的縱軸，選取聚類中心。

步驟5：引入成對約束集對非中心點進行分配。

步驟6：得到聚類結(jié)果。

GS-DPC算法流程圖如圖2所示。

4 實驗分析（Experiment analysis）

為了驗證本文算法的有效性，將提出的GS-DPC算法與DPC算法、DBSCAN算法和SDPC算法[14]分別應(yīng)用于iris數(shù)據(jù)集、aggregation數(shù)據(jù)集、cth3數(shù)據(jù)集、breast數(shù)據(jù)集、lineblobs數(shù)據(jù)集、t7數(shù)據(jù)集進行實驗。實驗在Intel（R）Core（TM） i5處理器、Windows 11操作系統(tǒng)和Python3.7的環(huán)境下進行。

4.1 數(shù)據(jù)集

本文使用表1中的6個數(shù)據(jù)集對所提出的算法進行驗證。

從表1中可以看出，除了breast數(shù)據(jù)集，其他數(shù)據(jù)集的維數(shù)都較低，并且樣本量大于1 000個的數(shù)據(jù)集有兩個，分別為cth3數(shù)據(jù)集和t7數(shù)據(jù)集。

4.2 聚類效果評價指標(biāo)

本文選用了3個評價指標(biāo)即精確度（ACC）、調(diào)整蘭德系數(shù)（ARI）和調(diào)整互信息（AMI）對各數(shù)據(jù)集的聚類結(jié)果進行評價，3個評價指標(biāo)的計算方式如下。

（1）精確度（ACC）

4.3 結(jié)果分析

本文將iris數(shù)據(jù)集、lineblobs數(shù)據(jù)集和t7數(shù)據(jù)集等在不同的約束強度下進行聚類得到的結(jié)果進行對比，約束集的比例分別為0%、5%、10%、15%、20%、25%和30%。實驗中的成對約束是隨機產(chǎn)生的，隨機選擇不同百分比對應(yīng)數(shù)量的成對約束對作為每次實驗的固定先驗信息，并且對每個數(shù)據(jù)集重復(fù)運行20次，取20次聚類結(jié)果的平均值作為GS-DPC算法在確定的成對約束數(shù)量下每個數(shù)據(jù)集的聚類結(jié)果，約束強度對比結(jié)果如圖4所示。

根據(jù)圖3可知，iris數(shù)據(jù)集、lineblobs數(shù)據(jù)集和aggregation數(shù)據(jù)集在約束強度為10%時，聚類結(jié)果的精確度分別提升了2.90百分點、5.60百分點和2.10百分點，因此本文選取10%作為約束強度進行實驗分析。

根據(jù)表2可知，對于上述6個數(shù)據(jù)集，GS-DPC算法的3個評價指標(biāo)均高于DBSCAN算法、DPC算法和SDPC算法，說明GS-DPC算法的聚類結(jié)果與真實情況更加吻合。例如：在t7數(shù)據(jù)集應(yīng)用中，GS-DPC算法的精確度、調(diào)整互信息、調(diào)整蘭德系數(shù)分別為56.60%、64.84%、44.76%，而其他3個聚類算法的精確度均小于50.00%，調(diào)整互信息均小于64.84%，調(diào)整蘭德系數(shù)均小于40.00%。DBSCAN算法對輸入的參數(shù)敏感，所以該聚類算法不能很好地進行數(shù)據(jù)聚類;DPC算法作為一種基于密度的聚類算法，相對于傳統(tǒng)的聚類算法能夠獲得較高的聚類質(zhì)量，但計算效率較低;SDPC算法和GS-DPC算法作為以密度峰值聚類算法為基礎(chǔ)的改進算法，可以處理任何形狀的數(shù)據(jù)集，兩個聚類算法均引入了網(wǎng)格以提高聚類的效率，但SDPC算法的聚類質(zhì)量較低，而GS-DPC算法加入了成對約束集，彌補了由于網(wǎng)格引起的精確度問題，相比于SDPC算法，能夠更加準(zhǔn)確地識別數(shù)據(jù)點所屬類簇，避免將數(shù)據(jù)點分配到錯誤的類簇中，提高了聚類算法對數(shù)據(jù)結(jié)構(gòu)和特征的識別能力。

根據(jù)圖4可知，在iris、aggregation、breast、lineblobs、cth3和t7這6個數(shù)據(jù)集中，雖然GS-DPC算法引入成對約束集需要消耗一定的時間，但是無論是大數(shù)據(jù)集還是小數(shù)據(jù)集，GS-DPC算法都比DPC算法消耗的時間短，計算效率更高。對于iris數(shù)據(jù)集，GS-DPC算法的運行時間相比DPC 算法平均降低了38.76百分點，相比SDPC算法平均降低了4.06百分點;對于cth3數(shù)據(jù)集，GS-DPC算法的運行時間相比DPC算法平均降低了54.54百分點，相比SDPC算法平均降低了0.53百分點。對于這6個數(shù)據(jù)集，GS-DPC算法運行時間相比DPC算法平均降低了32百分點。這是由于DPC算法需要計算數(shù)據(jù)點與數(shù)據(jù)點之間的距離，而SDPC算法和GS-DPC算法引入了網(wǎng)格劃分技術(shù)，使用網(wǎng)格單元代替數(shù)據(jù)點進行聚類，極大地節(jié)省了時間，因此GS-DPC算法提高了聚類的效率。

5 結(jié)論（Conclusion）

為了解決密度峰值聚類計算時間較長的問題，本文充分利用數(shù)據(jù)部分已知特征信息，提出了一種基于網(wǎng)格的半監(jiān)督密度峰值聚類（GS-DPC）算法，使用STING網(wǎng)格劃分技術(shù)對網(wǎng)格進行劃分，將數(shù)據(jù)集映射到網(wǎng)格單元中，提高了聚類的效率;針對密度峰值聚類算法中局部密度的計算涉及參數(shù)截斷距離dc，而截斷距離dc 的選取具有主觀性的問題，在計算局部密度時，直接使用網(wǎng)格單元內(nèi)數(shù)據(jù)點的個數(shù)作為局部密度值，簡化了局部密度的計算;對非聚類中心點進行分配時，引入了監(jiān)督信息即Must-link約束和Cannot-link約束，提高了聚類的精確度。本文中成對約束集是隨機選擇的，下一步將研究如何主動獲取成對約束信息并與密度峰值聚類算法相結(jié)合，從而更有效地利用成對約束信息指導(dǎo)聚類，得到更好的聚類結(jié)果。

作者簡介：

楊金瑞（1999-），女，碩士生。研究領(lǐng)域：數(shù)據(jù)智能分析，網(wǎng)絡(luò)輿情。

劉繼（1974-），男，博士，教授。研究領(lǐng)域：數(shù)據(jù)智能分析，網(wǎng)絡(luò)輿情。