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

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

0 引言（Introduction）

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

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

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

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

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

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

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

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

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

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

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

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

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

ε=n/k （1）

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

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

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

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

3.1 算法描述

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

3.2 相關(guān)定義

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

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

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

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

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

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

3.5 算法步驟

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

GS-DPC算法

輸入：樣本數(shù)據(jù)點(diǎn)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）計(jì)算每個(gè)網(wǎng)格的網(wǎng)格代表點(diǎn)。

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

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

步驟5：引入成對(duì)約束集對(duì)非中心點(diǎn)進(jìn)行分配。

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

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

4 實(shí)驗(yàn)分析（Experiment analysis）

為了驗(yàn)證本文算法的有效性，將提出的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ù)集進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)在Intel（R）Core（TM） i5處理器、Windows 11操作系統(tǒng)和Python3.7的環(huán)境下進(jìn)行。

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

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

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

4.2 聚類效果評(píng)價(jià)指標(biāo)

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

（1）精確度（ACC）

4.3 結(jié)果分析

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

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

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

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

5 結(jié)論（Conclusion）

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

作者簡(jiǎn)介：

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

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