基于改進成對約束擴充的標簽傳播聚類算法

收稿日期：2022-05-31；修回日期：2022-07-20

作者簡介：吳穎豪（1998-），男，福建泉州人，碩士研究生，主要研究方向為商務智能與數據挖掘；劉虹（1973-），女（通信作者），福建古田人，副教授，碩導，博士，主要研究方向為供應鏈與物流管理、灰色系統、智能算法（963558692@qq.com）；張岐山（1962-），男，黑龍江綏化人，教授，博導，博士，主要研究方向為數據挖掘、系統優化與仿真.

摘 要：

針對半監督聚類算法性能受到成對約束數量多寡的限制問題，現有的研究大都依賴于原始成對約束的數量。因此，首先提出了基于灰關聯分析的成對約束初始化算法（initialization algorithm of pair constraints based on grey relational analysis，PCIG）。該算法通過均衡接近度計算數據對象間的相似度，并根據相似度的取值來確定可信區間，然后借鑒網絡結構初始化方法來擴充數據對象間的成對關系。最后，將其應用于標簽傳播聚類算法。通過在五個基準數據集上進行實驗，基于改進成對約束擴充的標簽傳播聚類算法與其他方法相比NMI值和ARI值有所提升。實驗結果證明了改進成對約束擴充可以有效改善標簽傳播算法的聚類效果。

關鍵詞：半監督聚類；成對約束；標簽傳播；灰關聯分析

中圖分類號：TP301.6"" 文獻標志碼：A""" 文章編號：1001-3695（2022）12-010-3592-06

doi：" 10.19734/j.issn.1001-3695.2022.05.0244

Label propagation clustering algorithm based on

improved pairwise constraint expansion

Wu Yinghao， Liu Hong， Zhang Qishan

（College of Economics amp; Management， Fuzhou University， Fuzhou 350000， China）

Abstract：

To address the problem that the performance of semi-supervised clustering algorithms is limited by the number of pairwise constraints， most of the existing research relies on the number of original pairwise constraints， this paper firstly proposed the PCIG. The algorithm calculated the similarity between data objects by degree of balance and approach， and determined the confidence interval based on the value of similarity， then expanded the pairwise relationships between data objects by drawing on the initialization method of network structure. Finally， it was applied to the label propagation clustering algorithm. Through the experiments on 5 benchmark datasets， the label propagation clustering algorithm based on improved pairwise constraint expansion has improved NMI and ARI values compared with other methods. Experimental results show that improving pairwise constraint expansion can effectively improve the clustering effect of label propagation algorithm.

Key words：semi-supervised clustering; pairwise constraints; label propagation; grey relational analysis

0 引言

基于數據的機器學習方法可以分為有監督學習、無監督學習以及半監督學習［1］。其中，聚類是機器學習的常用算法，屬于無監督學習［2］，主要思想是只根據數據對象本身的特征進行類別劃分。隨著大數據時代的來臨，數據庫中的數據呈指數級增長［3］，大量的無標記數據中混雜著少量有標記數據或者其他類型的先驗信息。但傳統的聚類算法不僅無法利用這些信息，而且結果可能與先驗信息不一致［4］，因此結合半監督學習的聚類算法成為研究熱點。根據信息形式的不同，半監督學習中的監督信息可以分為標簽信息和成對約束［5］。

文獻［6］提出的標簽傳播聚類算法（label propagation algorithm，LPA）是一種典型的基于標簽信息的半監督學習算法，其基本思想是相似節點應該具有相同的類標簽。在成對約束應用場景下，標簽傳播聚類算法的性能會受到原始成對約束（pairwise constraints，PC）［7］數量的影響。當原始成對約束稀疏時，算法的表現不佳。針對原始成對約束稀疏導致的半監督學習方法效果不佳的問題，有學者通過在聚類過程中擴充原始成對約束的數量來解決該問題。例如，Lu等人［8］在約束譜聚類中，將原始成對約束通過近鄰傳播進行擴充。Klein等人［9］在層次聚類過程中，利用度量學習隱式擴充原始成對約束。但在算法過程中擴充原始成對約束，針對的是特定聚類算法，不能直接用于標簽傳播聚類算法。因此，還有學者提出專門的成對約束擴充算法，在聚類前先擴充原始成對約束。比如，Wang等人［10］根據給定半徑選擇約束鄰域，在低維空間投影中將原始成對約束通過其傳遞性擴展到鄰域中，最后應用到約束K均值算法中。Wei等人［11］利用成對約束的傳遞性和對稱性對其進行擴充。楊帆等人［12］提出了一種基于安全性的成對約束擴充方法，利用原始成對約束形成初始傳遞閉包對其進行擴充。

目前針對原始成對約束擴充的研究已經有了一定成果。一是在聚類過程中擴充成對約束，但該方法主要依靠成對約束的性質進行擴充，且僅針對特定算法設計；二是在聚類過程前擴充成對約束，雖然可以增加成對約束的數量，但效果依然受到原始成對約束的限制。因此，本文提出了一種基于灰關聯分析的成對約束擴充算法。該算法旨在挖掘隱藏在數據對象間的成對關系，從而在原始成對約束稀疏的情況下減少對原始成對的依賴，提高標簽傳播聚類算法的性能。

1 相關工作

1.1 基于差異信息理論的灰關聯分析

基于差異信息理論的灰關聯分析是張岐山教授［13］在傳統灰關聯分析的基礎上從差異信息的角度建立的一套信息序列的熵理論。在灰關聯分析方面，將均衡度的概念引入到灰關聯分析中，克服了傳統灰關聯分析可能存在的局部點關聯傾向問題。

定義1 灰關聯度［13］。設X為灰關聯因子集，X=（x1，x2，…，xi，…，xn），n≥2，xi={xi（k）|k∈K}，K={1，2，…，m}，m≥3，x0為參考列，xi為比較列，x為分辨系數，Ri=（γ（x0（k），xi（k））為第i個比較列的灰關聯系數，則稱映射

Map： Ri→Pi

Pi（x0（k），xi（k））=γ（x0（k），xi（k））∑nk=1γ（x0（k），xi（k））（1）

為灰關聯系數分布映射。第i個比較列的所有灰關聯度值的全體構成灰關聯度序列記為P，且∑nk=1Pi（x0（k），xi（k））=1。

定義2 灰關聯系數熵［13］。設X為灰關聯因子集，X=（x1，x2，…，xi，…，xn），n≥2，xi={xi（k）|k∈K}，K={1，2，…，m}，m≥3， x0為參考列，xi為比較列， x為分辨系數，Ri=（γ（x0（k），xi（k））為第i個比較列的灰關聯系數，P={Pi|i≥2}為灰關聯度序列集合，則稱函數

H（Pi）=-∑nk=1Piln Pi（2）

為第i個比較列的灰關聯系數熵。

定義3 均衡度［13］。設H（Pi）為第i個比較列的灰關聯系數熵，Hm為灰關聯系數的最大灰關聯系數熵，則稱

B（x0，xi）=H（Pi）/Hm（3）

為第i個比較列的均衡度，其中Hm=ln（n），n為灰關聯因子集的因子數。

定義4 均衡接近度［13］。設B（x0，xi）和γ（x0，xi）分別為第i個比較列的均衡度和灰關聯系數，則稱函數

BY（X0，Xi）=B（x0，xi）×γ（x0，xi）（4）

為第i個比較列的均衡接近度。

均衡接近度可以從數據序列整體上衡量數據間的關聯性，不僅不需要確定任何額外參數，而且可以有效地克服點關聯傾向問題。

1.2 網絡結構初始化

最大信息系數（maximal information coefficient，MIC）用于衡量兩個變量X和Y之間的關聯程度［14］。王守會等人［15］利用最大信息系數進行網絡結構初始化，如果變量實例Ｘ和Ｙ間的MIC值滿足式（5）中的任何一個，則等價于在網絡結構中兩者間可能存在一條連邊。

ORMIC（X，Y）≥αMICmax（X）MIC（Y，X）≥αMICmax（Y）（5）

其中：α為控制因子，一般取值為0.9［16］；MICmax表示MIC值矩陣中每一行（列）的最大值。

1.3 成對約束

成對約束由Wagstaff等人［17］最先用于指導聚類過程，包括表示兩個數據對象必須在同一個簇中的必連約束（must-link）和表示兩個數據對象不能在同一個簇中的勿連約束（cannot-link）。由于成對約束表示的是兩個數據對象的等價關系，所以它具有自反性、對稱性和傳遞性［18］。基于這些性質，可以得到以下推論。

推論1［18］ 假設存在數據集合X和必連約束集合M，對于不同的數據對象xi、xj和xh有：

（xi，xj）∈M∧（xj，xh）∈M（xi，xh）∈M

推論2［18］ 假設存在數據集合X、必連約束集合M、勿連約束集合C，對于不同的數據對象xi、xj和xh有：

（xi，xj）∈M∧（xj，xh）∈C（xi，xh）∈C

2 PCIG算法構建

本文采用均衡接近度來衡量節點間的相似程度，與傳統的距離方法等相比，該方法可以根據節點自身的屬性序列，從整體上衡量節點之間的相似程度，而且不需要引入任何額外參數。下面以iris數據集為例，隨機取6個實例（每個類別各取2個，見表1）計算相互之間的均衡接近度值，如表2所示。基于灰關聯分析的成對約束初始化算法由三個子算法組合而成，分別為相似度可信區間算法、必連約束擴充算法以及勿連約束擴充算法。

將相似度矩陣S除對角線外每行（列）最大值記為BYmax（表2中粗體標識），將矩陣每行（列）最小值記為BYmin（表2中下畫線標識）。

2.1 相似度可信區間

本文通過數據對象間相似度值來擴充成對約束，首先需要確定數據對象間存在成對關系的相似度值取值范圍，即相似度可信區間。例如在表2中，BY（X0，X2）和BY（X1，Y2）都為所在行的最大值，這表示數據對象X0和X1都有概率與X2存在必連約束。若都存在，則根據必連約束的性質可知，數據對象X0和X1間也存在必連約束。但是X0和X1兩者間的相似度并沒有達到最大值BYmax，所以不能簡單地用最大的BY值來代表存在必連約束。下面給出了具體定義來確定可信的相似度取值區間的方法。

定義5 設數據集D={X1，X2，…，Xn}，n∈N，N=（1，…，m），m≥2。BYmax（Xi）表示相似度矩陣S第i行（除對角線外）的最大值，BYmax（Yj）表示相似度矩陣S第j列（除對角線外）的最大值。BYmin（Xi）表示相似度矩陣S第i行的最小值，BYmin（Yj）表示相似度矩陣S第j列的最小值。如果存在Xi，Xj∈D（i≠j），使得BY（Xi，Xj）滿足式（6），稱該值為極大化最大值，記為MABYk。將所有極大化最大值構成的集合記為MABY。

BY（Xi，Xj）≥BYmax（Xi）BY（Xi，Xj）≥BYmax（Yj） （6）

如果存在Xi，Xj∈D（i≠j），使得BY（Xi，Xj）滿足式（7），稱該值為極小化最小值，記為MIBYk。將所有極小化最小值構成的集合記為MIBY。

ORBYmin（Xi，Xj）≤BYmin（Xi）BYmin（Xi，Xj）≤BYmin（Yj） （7）

由定義1可知，表2對應的極大化最大值集合MABY={0.74， 0.76， 0.81， 0.85}和極小化最小值集合MIBY={0.38， 0.40， 0.41， 0.42， 0.44， 0.47}。雖然可以把上述集合的上下限直接作為取值區間，但考慮到以下兩個可能的問題：a）區間長度與數據對象的取值有關，可能存在區間長度過大使得兩個區間重合的情況；b）取值的精度可能會對實驗結果產生一定影響。因此，還需進一步定義相似度可信區間。

定義6 設MABY為數據集D對應的極大化最大值集合，max（MABY）和min（MABY）（保留兩位小數）表示集合MABY的最大值和最小值。如果max（MABY）－min（MABY）≤0.1，則稱區間

［min（MABY），max（MABY）］（8）

為數據集D對應的必連約束的相似度可信區間，記為MVRB。否則稱區間

［max（MaxBY）－0.1，max（MaxBY）］（9）

為必連約束的相似度可信區間MVRB。之所以保證區間長度在0.1之內，是為了使可能存在成對約束的相似度取值盡可能接近。類似地，勿連約束的相似度可信區間的定義如下所示。

定義7 設MIBY分別為數據集D對應的極小化最小值集合。max（MIBY）和min（MIBY）（保留兩位小數）表示集合MIBY的最大值和最小值。如果max（MIBY）－min（MIBY）≤0.1，則稱區間

［min（MIBY），max（MIBY）］（10）

為數據集D對應的勿連約束的相似度可信區間，記為CVRB；否則，勿連約束的相似度可信區間CVRB如式（11）所示。

［min（MIBY），min（MIBY）+0.1］（11）

由定義2和3可得基于灰關聯分析的可信區間算法，詳細流程見算法1。

算法1 基于灰關聯分析的可信區間算法

輸入： 數據集D。

輸出： 可信區間MVRB和CVRB; 相似度矩陣BYn×n。

計算數據集中所有數據對象的均衡接近度，構建相似度矩陣BYn×n

將矩陣BYn×n中每行（除對角線）的最大值記為BYmax（Xi），每列（除對角線）的最大值BYmax（Yj）；將矩陣BY中每行的最小值記為BYmin（Xi），每列的最小值記為BYmin（Yj）。

for i=1：n do //遍歷所有行

for j=1：n do //遍歷所有列

if BY（Xi，Xj）≥BYmax（Xi） and BY（Xi，Xj）≥BYmax（Yj） do

MABY={MABYk=BY（Xi，Xj）} /*滿足式（6）加入極大化最大值集合*/

if BY（Xi，Xj）≤BYmin（Xi） or BY（Xi，Xj）≤BYmin（Yj） do

MIBY={MIBYk=BY（Xi，Xj）} /*滿足式（7）加入極小化最小值集合*/

if max（MABY）－min（MABY）≤0.1 do

MVRB=［min（MABY），max（MABY）］ //滿足條件取值范圍為式（8）

else

MVRB=［max（MABY）－0.1，max（MABY）］ /*不滿足條件取值范圍為式（9）*/

if max（MIBY）－min（MIBY）≤0.1 do

CVRB=［min（MIBY），max（MIBY）］ //滿足條件取值范圍為式（10）

else

CVRB=［min（MIBY），min（MIBY）+0.1］ /*不滿足條件取值范圍為式（11）*/

return MVRB， CVRB， BYn×n

根據算法1可知，表2對應的必連約束的相似度可信區間為［0.75，0.85］，勿連約束的相似度可信區間為［0.38，0.47］。如果存在原始成對約束，那么在得到可信區間后，將必連約束對應的數據對象間的相似度修改為1，將勿連約束對應的數據對象間的相似度修改為0。

2.2 必連約束擴充算法

得到相似度可信區間后，可以據此判斷數據對象間是否存在必連約束。數據對象間存在必連約束，與網絡結構中節點間存在連邊相似。文獻［16］中使用的網絡結構初始化方法，其目的是在保持網絡結構連通的情況下，初始的連邊盡可能地少。但是與本文盡可能多地挖掘必連約束的初衷相違背，因此不能直接用于必連約束的擴充。基于此，本文參考網絡結構初始化方法，定義了新的必連約束擴充算法。

定義8 設數據集D={X1，X2，…，Xn}，n∈N，N=（1，…，m），m≥2，VRB表示數據集D對應的相似度可信區間。對于數據對象Xi，如果Xj∈D滿足

BY（Xi，Xj）≥α" i≠j，α∈VRB （12）

稱這些節點為Xi的必連候選序列，記做MXi；所有的必連候選序列組成的集合稱為必連候選集合，用MX表示。其中，參數α控制了必連候選序列的數量和可信度。

由于可能有數值特征相似實際卻不屬于同一類的數據對象，所以相似度在該范圍內的數據對象間不一定都有必連約束。本文通過設置閾值得到每個數據對象的必連候選序列，從而保證數據對象相似度值在可信區間內，就表示兩者間存在必連約束。由定義3可知，閾值α的取值對于算法的性能至關重要，因此如何判斷選擇的α值是否合適是一個關鍵問題。必連候選序列是針對每個數據對象得到的，所以不同的必連候選序列會有交集。根據必連約束的傳遞性，可以得到推論1。如果參數α的取值合適，根據必連約束的傳遞性，必連候選序列應滿足以下推論。

推論1 若MXi∩MXj≠，則對于任意的Xi∈MXi，Xj∈MXj有

ORBY（Xj，Xi）∈VRBBY（Xi，Xj）∈VRB （13）

由定義4和推論1，可以得到基于灰關聯分析的必連約束擴充算法流程，見算法2。

算法2 基于灰關聯分析的必連約束擴充算法

輸入： 可信區間VRB，相似度矩陣BYn×n，參數β。

輸出： 必連約束集合M。

while α≤max（VRB） do // α初始值為min（VRB）

初始化數組MX，UM，M

for i=1：n do //遍歷所有行

for j=1：n do

if BY（Xi，Xj）≥α and i≠j do

add Xj to MXi"" //滿足條件（12）放入必連序列MXi

if Mi.lengthgt;0 do

add MXi to MX

for i=1：m do

for j=1：i do

if MXi∩MXj！=none do

MXi=MXi∪MXj //合并兩個必連序列為一個，另一個刪除

初始化指示值Flag //初始為1

for Item in MX do

for i in Item do

for j in Item do

if BY（Xi，Xj）VRB do

Flag=0

break

if Flag=0 do

break

if Flag=0 do

break

if Flag=0 do

α+=0.01 //每循環一次加0.01

else

break

M=MX

return M //返回必連約束集合

根據算法2，可得表2對應的α=0.76，必連候選集合MX={MX1={1，2}，MX2={2，1}，MX3={3，4}，MX4={4，3}}。可以發現集合MX中的候選序列間確實會存在交集，甚至存在完全一樣的情況。因此，對存在交集的必連候選序列取并集，將合并后的新集合稱為必連序列UM，所有的必連序列構成的集合稱為必連約束集合M={UM1={1，2}，UM2={3，4}}。

2.3 勿連約束擴充算法

上文中的必連約束擴充算法僅僅考慮了數據對象之間的必連關系，并不能保證不同的必連序列UM之間存在勿連關系。因此，不能根據成對約束的性質直接利用必連集合M擴充勿連約束，而是需要新的勿連約束擴充算法來得到。下面介紹該算法的具體定義。

定義9 設數據集D={X1，X2，…，Xn}，n∈N，N=（1，…，m），m≥2，MIBY為極小化最小值集合，MMIBY=min（CVRB）表示極小化最小值集合中的最小值，如果Xi，Xj∈D（i≠j）滿足

ORBY（Xi，Xj）≤MMIBY/γBY（Xj，Xi）≤MMIBY/γ （14）

稱節點Xi和Xj之間有勿連關系，記做Ck，所有的勿連關系組成的集合稱為勿連約束集合，記做C。其中，參數γ一般為0.9。

由定義5，下面給出基于灰關聯分析的勿連約束擴充算法。

算法3 基于灰關聯分析的勿連約束擴充算法

輸入： 相似度矩陣BYn×n，參數β。

輸出： 必連約束集合UC。

初始化集合C

for i=1：n do

for j=1：n do

if BY（Xi，Xj）≤MMIBY/γ do

add （Xi，Xj） to C" //滿足式（13）的節點對放入集合中

return C

根據算法3和勿連約束的相似度可信區間［0.38，0.47］可知，表2對應的MMIBY=0.38。將表2中滿足集合C條件的均衡接近度值標為-1，如表3所示。可以發現這些約束有較高的可信度，且沒有錯誤標記的情況。

2.4 時間與空間復雜度分析

本節對基于灰關聯分析的成對約束初始化算法的時間與空間復雜度進行分析，按上文所述該算法整體可以分成三個部分，接下來對每個部分進行時間復雜度分析。假設數據集包含數據對象個數n。在算法1中，計算任意兩個實例間的均衡接近度的時間復雜度為O（n），尋找極大化最大值集合和極小化最小值集合的時間復雜度為O（n2），得到可信區間時間復雜度為O（4），因此算法1整體時間復雜度為O（n2+n+1），即O（n2）。假設必連集合包含必連序列個數合并前后分別為m1和m2，必連序列包含數據對象個數合并前后分別為k，其中m2，klt;lt;n，m1，klt;n。在算法2中，針對每個α值得到必連約束集合，時間復雜度為O（（n×（n+1）+0.5×m1×（m1－1）+m2×k2）），因為m2，klt;lt;n，所以該時間復雜度最壞為O（1.5n2）；α的取值需要所在的可信區間長度被限制在0.1且保留兩位小數，因此最多執行10次上述步驟，時間復雜度最壞為O（15n2），算法2整體時間復雜度為O（15n2）。算法3中遍歷1次矩陣的時間復雜度為O（n2）。整個算法在最壞情況下的時間復雜度為O（16n2），本文針對的數據集包含的數據對象ngt;gt;16，因此算法時間復雜度可以看做O（n2）。空間復雜度分析，本文算法主要在n×n的矩陣上進行計算，其他的運算過程中用到的集合和列表等都遠小于它，因此本文總的空間復雜度為O（n2）。

3 實驗與結果分析

3.1 實驗準備

本文所有實驗均采用Python語言實現；實驗運行環境的操作系統為Windows 10，64 bit，CPU為1.8 GHz，內存為16 GB。實驗數據從UCI機器學習數據倉庫［14］中選取5個有代表性的數據集，表4給出了數據集的相關信息。

實驗采用標準互信息（NMI，式（15））［19］和調整蘭德系數（ARI，式（16））［20］兩種指標對算法的性能進行測評。上述兩種指標的取值均在0～1，且越接近1表示算法效果越好。

NMI=-2∑|X|i ∑|Y|jP（i，j）log（P（i，j）P（i）P（j））∑|X|iP（i）log（P（i））+∑|Y|jP（j）log（P（j））（15）

其中：X代表聚類結果；Y代表真實類；P（i，j）表示數據對象在X中屬于i類，在Y中屬于j類的聯合分布概率；P（i）表示數據對象在X中屬于i類的概率；P（j）表示數據對象在Y中屬于j類的概率。

ARI=∑ijC2nij-［∑iC2ai∑jC2bj］/C2N12［∑iC2ai+∑jC2bj］-［∑iC2ai∑jC2bj］/C2N（16）

其中：真實類的數量為i；聚類簇的數量為j；C表示組合數；N為數據集包含的數據對象總數；ai為屬于第i類的數據對象數量；bj屬于第j簇的數據對象數量；nij為既屬于第i類又屬于第j簇的數據對象數量。

3.2 消融實驗

為了驗證PCIG算法是否可以提升基于成對約束的標簽傳播算法的聚類效果，本文選取了基于安全性的成對約束擴充算法（extended algorithm of pairwise constraints based security，PCES）［12］。將PCIG算法擴充后的成對約束作為先驗信息的標簽傳播聚類算法（LPA-PCIG）和原始成對約束作為先驗信息的標簽傳播算法（LPA-PC）以及經過PCES算法擴充后的成對約束作為先驗信息的標簽傳播算法（LPA-PCES）進行消融實驗。分別隨機抽取數據對象總數的15%和20%對應數量的原始成對約束10組，且均利用成對約束的性質進行擴充。兩個算法分別在每組數據上運行10次，取平均值作為最終結果。實驗結果通過計算NMI和ARI的平均值來展示。表5和6列出了消融實驗相應的評價指標取值。

根據表5和6的結果，可以得到消融實驗的柱狀圖，如圖1～4所示。從圖中可以直觀地看出，將PCIG算法擴充后的成對約束應用于標簽傳播聚類算法，在所有實驗數據集上，相比于其他算法，聚類效果都有了不同程度的提高。

3.3 對比實驗設置

為了驗證PCIG算法提升的效果是否顯著，本文選取Lu等人［21］提出的基于成對約束的標簽傳播算法（label propagation based pairwise constraints，PCLP），將原始成對約束作為先驗信息執行該算法（PCLP-PC）的對比實驗。PCLP-PC算法同樣在分別在15%和20%對應數量的原始成對約束數據上運行10次，且均利用成對約束的性質進行擴充，取平均值作為最終結果。實驗結果通過計算NMI和ARI的平均值來展示。表7和8列出了對比實驗相應的評價指標取值。

根據表7和8的結果，可以得到對比實驗的柱狀圖，如圖5～8所示。從圖中可以直觀地看出，將PCIG算法擴充后的成對約束應用于標簽傳播聚類算法后，在heart、breast和bank數據集上聚類效果優于PCLP算法，尤其是在bank數據集上效果最為顯著。

3.4 實驗結論

從消融實驗可以看出，通過本文提出的PCIG算法對成對約束進行擴充后用于標簽傳播算法（LPA），在五個數據集上聚類結果的NMI值和ARI值均優于對比算法。這表明在多樣的應用環境中，對于LPA而言，PCIG算法擴充得到的成對約束不僅數量有所增加，而且安全性也有所保證。

從對比實驗可以看出，LPA-PCIG在heart、breast和bank三個數據集上優于改進后的PCLP-PC，而在iris和wine數據集表現較差，尤其是在wine數據集上。這表明本文提出的PCIG算法在數據量更大的數據集上可以擴充得到更多的成對約束，能夠彌補LPA在成對約束監督信息應用場景下的不足，從而得到更好的聚類結果。

4 結束語

本文針對在成對約束類型的監督信息應用場景下，傳統的LPA存在的聚類效果不佳的問題，提出了一種基于灰關聯分析的初始成對約束初始化算法。該算法通過在標簽傳播聚類過程前，對已知的初始成對約束進行擴充得到更多的監督信息，從而改善LPA的聚類表現。最后經過消融實驗和對比實驗驗證了該算法的有效性。但是通過實驗也可以看到，應用PCIG后的LPA并不總是會因為更多的成對約束信息而優于已有的改進算法，事實上LPA本身存在的不穩定性也會影響實驗結果。因此，下一步的工作會集中于對標簽傳播的算法過程進行改進，進一步提高基于PCIG的標簽傳播算法的聚類效果。

參考文獻：

［1］章永來，周耀鑒. 聚類算法綜述 ［J］. 計算機應用，2019，39（7）： 1869-1882. （Zhang Yonglai，Zhou Yaojian. Review of clustering algorithms ［J］. Journal of Computer Applications，2019，39（7）： 1869-1882.）

［2］ Aggarwal C C，Reddy C. Data clustering： algorithms and applications ［M］. London： Taylor and Francis Group，2014： 4-7.

［3］王慧玲，宋威，王晨妮. 稀疏和標簽約束半監督自動編碼機的分類算法 ［J］. 計算機應用研究，2019，36（9）： 2613-2617. （Wang Huiling，Song Wei，Wang Chenni. Semi-supervised auto-encoder using sparse and label regularizations for classification ［J］. Application Research of Computers，2019，36（9）： 2613-2617.）

［4］Dinler D，Tural M K. Robust semi-supervised clustering with polyhedral and circular uncertainty ［J］. Neurocomputing，2017，265： 4-27.

［5］朱恒東，馬盈倉，代雪珍. 自適應半監督鄰域聚類算法 ［J］. 山東大學學報： 工學版，2021，51（4）： 24-34. （Zhu Hengdong，Ma Yingcang，Dai Xuezhen. Adaptive semi-supervised neighborhood clustering algorithm ［J］. Journal of Shandong University： Enginee-ring Science，2021，51（4）： 24-34.）

［6］Zhu Xiaojin，Ghahramani Z. Learning from labeled and unlabeled data with label propagation， CMU-CALD-02-107 ［R］. Pittsburgh，PA：Carnegie Mellon University，2002：2803-2808.

［7］Dinler D，Tural M K. Robust semi-supervised clustering with polyhedral and circular uncertainty ［J］. Neurocomputing，2017，265： 4-27.

［8］Lu Zhengdong，Carreira-Perpinan M A. Constrained spectral clustering through affinity propagation ［C］//Proc of IEEE Conference on Computer Vision and Pattern Recognition. Piscataway，NJ： IEEE Press，2008： 1-8.

［9］Klein D，Kamvar S D，Manning C D. From instance-level constraints to space-level constraints： making the most of prior knowledge in data clustering ［C］// Proc of the 19th International Conference on Machine Learning. San Francisco，CA：Morgan Kaufmann Publishers Inc.，2002： 307-314.

［10］Wang Hongjun，Li Tao，Li Tianrui，et al. Constraint neighborhood projections for semi-supervised clustering ［J］. IEEE Trans on Cybernetics，2014，44（5）： 636-643.

［11］Wei Siting，Li Zhixin，Zhang Canlong. Combined constraint-based with metric-based in semi-supervised clustering ensemble ［J］. International Journal of Machine Learning and Cybernetics，2018，9（7）： 1085-1100.

［12］楊帆，王俊斌，白亮. 基于安全性的成對約束擴充算法 ［J］. 計算機科學，2020，47（9）： 324-329. （Yang Fan，Wang Junbin，Bai Liang. Extended algorithm of pairwise constraints based security ［J］. Computer Science，2020，47（9）： 324-329.）

［13］張岐山. 灰朦朧集的差異信息理論 ［M］. 北京： 石油工業出版社，2002. （Zhang Qishan. Difference information theory of grey hazy set ［M］. Beijing： Petroleum Industry Press，2002.）

［14］Reshef D N，Reshef Y A，Finucane H K，et al. Detecting novel associations in large data sets［J］.Science，2011，334（6062）： 1518-1524.

［15］王守會，覃飆. 基于集成學習和反饋策略的貝葉斯網絡結構學習 ［J］. 計算機學報，2021，44（6）： 1051-1063. （Wang Shouhui，Qin Biao. Bayesian network structure learning by ensemble learning and feedback strategy ［J］. Chinese Journal of Computers，2021，44（6）： 1051-1063.）

［16］Zhang Yinghua，Zhang Wensheng，Xie Yuan. Improved heuristic equivalent search algorithm based on maximal information coefficient for Bayesian network structure learning ［J］. Neurocomputing，2013，117： 186-195.

［17］Wagstaff K，Cardie C. Clustering with instance-level constraints ［C］// Proc of the 17th International Conference on Machine Learning. San Francisco，CA：Morgan Kaufmann Publishers Inc.，2000：1103-1110.

［18］Yu Zhiwen，Kuang Zongqiang，Liu Jiming，et al. Adaptive ensembling of semi-supervised clustering solutions ［J］. IEEE Trans on Know-ledge and Data Engineering，2017，29（8）： 1577-1590.

［19］Dom B E. An information-theoretic external cluster-validity measure ［J］. Uncertainty in Artificial Intelligence，2001，27（3）： 137-145.

［20］Hubert L，Arabie P. Comparing partitions ［J］. Journal of Classification，1985，2（1）： 193-218.

［21］Lu Zhiwu，Peng Yuxin. Exhaustive and efficient constraint propagation： a graph-based learning approach and its applications ［J］. International Journal of Computer Vision，2013，103（3）： 306-325.