向力宏，金應(yīng)華，徐圣兵

（廣東工業(yè)大學(xué)應(yīng)用數(shù)學(xué)學(xué)院，廣東廣州510520）

聚類(lèi)分析是數(shù)據(jù)挖掘的重要組成部分，其作為常用的數(shù)據(jù)分析方法被廣泛應(yīng)用于人工智能、模式識(shí)別和機(jī)器學(xué)習(xí)領(lǐng)域中。以往的機(jī)器學(xué)習(xí)一般只考慮無(wú)標(biāo)簽和有標(biāo)簽兩類(lèi)課題，使用的方法有無(wú)監(jiān)督學(xué)習(xí)和監(jiān)督學(xué)習(xí)。傳統(tǒng)的聚類(lèi)分析主要是無(wú)監(jiān)督學(xué)習(xí)，如K-means聚類(lèi)［1］、分層聚類(lèi)［2］、密度聚類(lèi)［3］、極大熵聚類(lèi)［4］等，對(duì)于有標(biāo)簽的數(shù)據(jù)往往采用監(jiān)督學(xué)習(xí)方法，如 k-近鄰［5］、決策樹(shù)［6］、支持向量機(jī)［7］等。

現(xiàn)實(shí)生活中我們所獲得的數(shù)據(jù)大多是復(fù)雜的，數(shù)據(jù)中不僅包含了未標(biāo)記數(shù)據(jù)，而且還包含了標(biāo)記數(shù)據(jù)，無(wú)監(jiān)督學(xué)習(xí)和監(jiān)督學(xué)習(xí)在對(duì)這類(lèi)數(shù)據(jù)進(jìn)行模式求解的過(guò)程中所得到的模型精度一般。因此如何解決樣本數(shù)據(jù)標(biāo)簽不充分所導(dǎo)致的聚類(lèi)數(shù)據(jù)性能下降問(wèn)題，是近年來(lái)機(jī)器學(xué)習(xí)領(lǐng)域研究的方向之一。半監(jiān)督學(xué)習(xí)算法能夠較好地解決以上問(wèn)題，該方法能夠利用少量已有樣本數(shù)據(jù)標(biāo)記監(jiān)督信息進(jìn)行分類(lèi)。

現(xiàn)有的半監(jiān)督聚類(lèi)形式一般通過(guò)兩種先驗(yàn)信息來(lái)指導(dǎo)算法聚類(lèi)，即標(biāo)記信息和成對(duì)約束信息，由于標(biāo)記信息能夠轉(zhuǎn)化為成對(duì)約束信息，我們將所得到的成對(duì)約束信息設(shè)置為半監(jiān)督聚類(lèi)先驗(yàn)信息來(lái)進(jìn)行監(jiān)督聚類(lèi)。聚類(lèi)算法通過(guò)標(biāo)記信息的引導(dǎo)來(lái)推進(jìn)聚類(lèi)過(guò)程的劃分調(diào)整，從而不斷改善聚類(lèi)效果，這類(lèi)半監(jiān)督聚類(lèi)算法已經(jīng)有了大量開(kāi)創(chuàng)性研究，例如，尹學(xué)松等［8］提出了基于成對(duì)約束的判別型半監(jiān)督聚類(lèi)分析方法解決了高維數(shù)據(jù)計(jì)算性能不足和成對(duì)約束的違反問(wèn)題；肖宇等［9］基于近鄰傳播算法，運(yùn)用標(biāo)簽類(lèi)數(shù)據(jù)和成對(duì)約束數(shù)據(jù)構(gòu)成的相似度矩陣進(jìn)行聚類(lèi)指導(dǎo)，進(jìn)而提高近鄰傳播方法的聚類(lèi)性能；王君言等［10］基于DL1圖和KNN圖疊加圖的高光譜圖像半監(jiān)督分類(lèi)算法，構(gòu)建了空譜信息聯(lián)合的圖框架結(jié)構(gòu)，提高小樣本高光譜圖像自動(dòng)分類(lèi)的精度。成對(duì)約束信息是一種普遍存在于樣本數(shù)據(jù)之間的相互信息，這對(duì)于研究聚類(lèi)過(guò)程具有十分重大的意義。

本文延著向思源等［11］（PD-sSC算法）的研究思路，提出了一種基于閉包準(zhǔn)則的成對(duì)約束打包算法（CCPC），該算法解決了聚類(lèi)過(guò)程不受成對(duì)約束數(shù)目變大而導(dǎo)致的聚類(lèi)性能相對(duì)下降的問(wèn)題。在不降低聚類(lèi)效果的前提下，提出了一種程序改進(jìn)方法，降低了編程難度。實(shí)驗(yàn)結(jié)果表明了CCPC算法的有效性。

1 算法

1.1 構(gòu)建成對(duì)約束及閉包

首先對(duì)本文所需要的數(shù)學(xué)符號(hào)進(jìn)行定義，如表1所示。

表1 CCPC目標(biāo)函數(shù)符號(hào)定義

假設(shè)給定樣本集合空間 X=｛xi│xi∈Rd，i=1，2，…，n｝，其中，n 表示樣本點(diǎn)數(shù)，R 為實(shí)數(shù)，d 為樣本維數(shù)。本文所采用的成對(duì)約束可分為must-link約束和cannot-link約束，并將所有must-link集合記為ML，所有cannot-link集合記為CL，兩者的定義如下：

定義1 must-link，定義集合ML=｛（xi，xj）│i＜j｝，若兩個(gè)樣本滿(mǎn)足（xi，xj）∈ML，則表明xi和xj兩個(gè)樣本屬于同一類(lèi)，也稱(chēng)xi和xj存在正關(guān)聯(lián)約束關(guān)系。

圖1為成對(duì)約束must-link約束示意圖，樣本點(diǎn)用球表示，虛線(xiàn)圍成的區(qū)域樣本為同一類(lèi)簇，實(shí)心圓分別代表樣本點(diǎn)xi和xj，兩個(gè)樣本點(diǎn)之間通過(guò)直線(xiàn)連接表示must-link約束，說(shuō)明xi和xj屬于同一類(lèi)簇，滿(mǎn)足正關(guān)聯(lián)約束條件。

圖1 must-link約束關(guān)系示意圖

定義2 cannot-link，定義集合CL=｛（xk，xl）│k＜l｝，若（xk，xl）∈CL，則表明xk和xl兩個(gè)樣本不屬于同一類(lèi)，也稱(chēng)xk和xl存在負(fù)關(guān)聯(lián)約束關(guān)系。

圖2為成對(duì)約束cannot-link示意圖，球形所表示的含義與圖1一致，實(shí)心圓分別代表樣本點(diǎn)xk和xl，兩個(gè)樣本點(diǎn)之間通過(guò)虛線(xiàn)連接表示cannot-link約束，說(shuō)明兩個(gè)樣本點(diǎn)在聚類(lèi)過(guò)程中分別屬于不同的類(lèi)簇，滿(mǎn)足負(fù)關(guān)聯(lián)約束條件。

圖2 cannot-link約束關(guān)系示意圖

受尹學(xué)松等［8］研究的啟發(fā)，本文先基于must-link約束類(lèi)對(duì)數(shù)據(jù)進(jìn)行打包處理，降低原始數(shù)據(jù)成對(duì)約束容量，重新構(gòu)造新的cannot-link約束，使得算法在聚類(lèi)過(guò)程中不會(huì)產(chǎn)生違反must-link約束問(wèn)題，為了便于理解對(duì)閉包準(zhǔn)則進(jìn)行如下定義。

定義 3 假設(shè)有 3 個(gè)樣本 a1，a2，a3，滿(mǎn)足（a1，a2）∈ML，（a1，a3）∈ML，則（a2，a3）∈ML，此時(shí)稱(chēng) a1，a2，a3構(gòu)成的集合為同類(lèi)閉包，簡(jiǎn)稱(chēng)閉包。類(lèi)似地，可定義含有任意有限個(gè)樣本點(diǎn)的同類(lèi)閉包。若在某樣本點(diǎn)處沒(méi)有must-link約束，此時(shí)可約定該樣本點(diǎn)就是一個(gè)獨(dú)立的同類(lèi)閉包。

定義5設(shè)兩個(gè)閉包為A=｛a1，a2，…，aq｝和B=｛b1，b2，…，bp｝。若存在（ai，bj）∈CL，其中ai∈A，bj∈B，則稱(chēng)A，B為異類(lèi)閉包。

一旦完成基于must-link約束類(lèi)的打包，就可以用閉包中心替代整個(gè)閉包；若兩個(gè)閉包中的樣本點(diǎn)之間存在cannot-link約束，此時(shí)可設(shè)定對(duì)應(yīng)的兩個(gè)閉包中心之間存在cannot-link約束。如圖3所示，已知兩個(gè)閉包｛a1，a2，a3，a4｝和｛b1，b2，b3｝，a，b 分別為閉包中心，其中實(shí)線(xiàn)表示 must-link約束，虛線(xiàn)表示cannot-link約束，黑色節(jié)點(diǎn)為樣本點(diǎn)，白色節(jié)點(diǎn)為閉包中心；此閉包之間存在一對(duì)cannot-link約束，即（a1，b1）；打包完成后，可設(shè)定 cannot-link約束（a，b）來(lái)表示原始樣本的 cannot-link約束（a1，b1）。

圖3 must-link約束合成及cannot-link約束的閉包轉(zhuǎn)換示意圖

在完成打包操作并更新cannot-link約束后，會(huì)得到一組新樣本，記為，其中 nml為樣本量。一般地，nml＜n；另記，更新后的cannot-link約束集合為CL'。

尹學(xué)松等［8］基于數(shù)據(jù)打包操作設(shè)計(jì)了PCBKM聚類(lèi)算法。經(jīng)過(guò)分析和實(shí)驗(yàn)，可知該算法有如下兩方面不足。1）在與PD-sSC算法［1］進(jìn)行實(shí)驗(yàn)對(duì)比時(shí)發(fā)現(xiàn)，PCBKM算法在成對(duì)約束數(shù)目相對(duì)較大時(shí)表現(xiàn)優(yōu)異，但在成對(duì)約束數(shù)目較小時(shí)，聚類(lèi)效果比不上PD-sSC算法。2）PCBKM算法中step-2-（b）步驟對(duì)cannot-link約束處理得太過(guò)簡(jiǎn)單，沒(méi)有考慮異類(lèi)閉包之間可能存在的復(fù)雜的分布形式。若采用step-2-（b）步驟進(jìn)行計(jì)算，不同異類(lèi)閉包對(duì)的選擇會(huì)產(chǎn)生不同的聚類(lèi)結(jié)果。圖4列舉了較復(fù)雜的異類(lèi)閉包對(duì)的分布形式，其中帶編號(hào)的白色圓形節(jié)點(diǎn)為閉包中心（新樣本點(diǎn)），虛線(xiàn)表示cannot-link約束，橢圓結(jié)構(gòu)表示計(jì)算過(guò)程中可以選擇的異類(lèi)閉包對(duì)。以圖4的第1幅圖為例，存在3對(duì)異類(lèi)閉包配對(duì)（1，2），（1，3），（2，3）；當(dāng)用PCBKM算法中step-2-（b）步驟分別處理這三對(duì)異類(lèi)閉包的cannot-link約束時(shí)，三個(gè)閉包點(diǎn)｛1，2，3｝都有兩個(gè)聚類(lèi)結(jié)果，此時(shí)可能出現(xiàn)同一閉包點(diǎn)在不同異類(lèi)閉包的cannot-link約束對(duì)下得到不同的聚類(lèi)結(jié)果。如果想改進(jìn)step-2-（b）步驟中的這點(diǎn)不足，需要充分考慮異類(lèi)閉包對(duì)的分布形式，但是異類(lèi)閉包對(duì)的分布形式不可枚舉，圖4僅列舉了幾類(lèi)簡(jiǎn)單的情況。

圖4 異類(lèi)閉包選取結(jié)構(gòu)示意圖

為了解決以上兩個(gè)問(wèn)題，本文提出一種基于閉包準(zhǔn)則的成對(duì)約束打包算法（CCPC）。

1.2 MEC中熵項(xiàng)的推廣

一般稱(chēng)經(jīng)典MEC聚類(lèi)算法［12，14-18］所含的熵項(xiàng)為自信息熵，其僅能刻畫(huà)樣本點(diǎn)的內(nèi)部信息，代表樣本點(diǎn)自身的信息。在聚類(lèi)過(guò)程中不僅需要利用樣本內(nèi)部的信息，還需要挖掘利用其外部之間的信息。向思源等［11］引入了功效散度（power-divergence,PD）族，它可度量?jī)蓚€(gè)概率向量之間的距離，概率向量之間相似度越高，對(duì)應(yīng)的PD散度越小。具體定義如下：

由定義6可知，PD散度是一族，當(dāng)指標(biāo)p=0時(shí)PD散度也為KL（Kullback-Leibler）散度［19］，即樣本對(duì)之間的相對(duì)熵。以下給出KL散度的明確定義。

李晁銘等［13］利用相對(duì)熵（KL散度）構(gòu)造了CE-sSC聚類(lèi)算法。PD散度可隨著指標(biāo)p的改變而改變，還可將PD散度推廣到更一般的形式，例如?散度［20］?；赑D散度和相對(duì)熵之間的關(guān)系，向思源等［11］在李晁銘等［13］研究成果的基礎(chǔ)上提出了基于PD散度的PD-sSC聚類(lèi)算法，克服了CE-sSC算法中熵項(xiàng)之間的干擾問(wèn)題，提高了懲罰系數(shù)的選擇效率。

1.3 目標(biāo)函數(shù)

定義 8 懲罰系數(shù)矩陣 Γ=（Γjk）nml×nml

顯然，Γ為上三角形矩陣，其中所有γjk元素皆為正數(shù)。類(lèi)似于PD-sSC算法，通過(guò)融合懲罰項(xiàng)系數(shù)和PD散度得到目標(biāo)函數(shù)的懲罰項(xiàng)為

1.4 參數(shù)求解

由式（5）可得

將式（8）變形得到

將式（9）代入到式（6）可以得到隸屬度迭代公式為

式（6）～（10）中的參數(shù) aij定義如下

2 算法流程

總結(jié)上述推導(dǎo)，得到CCPC算法的具體流程如下：

輸入原始目標(biāo)數(shù)據(jù)集Y，懲罰系數(shù)矩陣Γ＝（Γjk）nml×nml，初始隸屬度矩陣U(0)，聚類(lèi)數(shù)c（2≤c≤nml），PD散度指標(biāo)p，算法最大迭代次數(shù)T，終止條件ε。

輸出 最優(yōu)隸屬度矩陣U和聚類(lèi)中心V。

迭代過(guò)程為：

（1）初始化迭代計(jì)數(shù)器t=0；

（2）根據(jù)式（7）和 U(t)計(jì)算出 V(t)；

（3）根據(jù)式（10）和 V(t)更新 U(t)為 U(t+1)；

（4）當(dāng)‖U(t+1)-U(t)‖≤ε或t=T時(shí)，終止算法運(yùn)算；否則，令t=t+1返回到（2）；

（5）算法收斂后，輸出最優(yōu)隸屬度矩陣U和聚類(lèi)中心V。

以上算法是對(duì)打包后的樣本集合Y進(jìn)行聚類(lèi)分析，在打包規(guī)則的基礎(chǔ)上，可將此聚類(lèi)分析結(jié)果反射到原樣本集合X上，至此才算完成原樣本組的聚類(lèi)分析。圖5列出了CCPC算法的基本框架。

圖5 CCPC算法的框架圖

在編程實(shí)現(xiàn)CCPC算法的過(guò)程中，對(duì)隸屬度向量(10)式進(jìn)行歸一化操作時(shí)，很容易碰到算術(shù)溢出問(wèn)題，此時(shí)就需要對(duì)算法流程加入若干相應(yīng)的控制項(xiàng)，這給編程帶來(lái)了難度。為解決這一問(wèn)題，定義如下的截尾指數(shù)函數(shù)

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

本文選取6個(gè)數(shù)據(jù)集對(duì)CCPC算法和其他相關(guān)的聚類(lèi)算法進(jìn)行實(shí)驗(yàn)比較。

3.1 實(shí)驗(yàn)數(shù)據(jù)與評(píng)價(jià)準(zhǔn)則

實(shí)驗(yàn)選取了UCI數(shù)據(jù)庫(kù)中的四組常用數(shù)據(jù)集，分別為breast、iris、seeds、wine數(shù)據(jù)，還選取了池塘水質(zhì)評(píng)價(jià)水色圖像特征數(shù)據(jù)集X1和用于區(qū)域環(huán)境質(zhì)量狀況評(píng)價(jià)的空氣質(zhì)量數(shù)據(jù)集X2作為實(shí)驗(yàn)數(shù)據(jù)。選取以上數(shù)據(jù)集的原因是算法性能檢測(cè)的結(jié)果直觀(guān)可靠，表2列出了數(shù)據(jù)集的特征描述。

表2 數(shù)據(jù)集的特征

在進(jìn)行實(shí)驗(yàn)之前，對(duì)所有數(shù)據(jù)集進(jìn)行中心化與標(biāo)準(zhǔn)化處理，目的是消除量綱差異。本文選擇的對(duì)比算法有基于功效散度和成對(duì)約束的半監(jiān)督聚類(lèi)的PD-sS算法［11］、基于成對(duì)約束的交叉熵半監(jiān)督聚類(lèi)的CE-sSC算法［13］、基于成對(duì)約束的K均值聚類(lèi)的PCBKM算法［8］和基于譜圖和成對(duì)約束的主動(dòng)半監(jiān)督聚類(lèi) SSC 算法［20］。

實(shí)驗(yàn)對(duì)比中采用了三種評(píng)價(jià)指標(biāo)：1）準(zhǔn)確率指標(biāo)（Accuracy Cluster，AC）：評(píng)價(jià)聚類(lèi)準(zhǔn)確程度；2）標(biāo)準(zhǔn)互信息指標(biāo)（Normalized Mutual Information，NMI）：衡量?jī)蓚€(gè)數(shù)據(jù)分布的吻合程度；3）蘭德指數(shù)（Rand Index，RI）：評(píng)價(jià)算法聚類(lèi)結(jié)果與真實(shí)情況的吻合程度。以上三種評(píng)價(jià)指標(biāo)的取值都在0至1之間，指標(biāo)值越接近1就說(shuō)明聚類(lèi)效果越好，使用多個(gè)評(píng)價(jià)指標(biāo)進(jìn)行對(duì)比能夠更加充分地評(píng)價(jià)聚類(lèi)效果。

3.2 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

實(shí)驗(yàn)前，先采取數(shù)據(jù)清洗操作，然后通過(guò)隨機(jī)抽樣方式構(gòu)建成對(duì)約束信息，在實(shí)驗(yàn)過(guò)程中，忽略數(shù)據(jù)的標(biāo)簽信息。根據(jù)數(shù)據(jù)樣本量和實(shí)驗(yàn)結(jié)果選取成對(duì)約束的數(shù)量點(diǎn)，具體信息如下：breast數(shù)據(jù)的成對(duì)約束數(shù)目設(shè)置為 20、40、60、80、100、120、140、160、180、200；iris 數(shù)據(jù)成對(duì)約束數(shù)目設(shè)置為 10、15、20、25、30、35、40、45、50、55；seeds、X2數(shù)據(jù)的成對(duì)約束數(shù)目設(shè)置為 10、20、30、40、50、60、70、80、90、100；wine、X1數(shù)據(jù)的成對(duì)約束數(shù)目設(shè)置為 8、16、24、32、40、48、56、64、72、80。進(jìn)行 1 000 次重復(fù)實(shí)驗(yàn)，求得評(píng)價(jià)指標(biāo)的平均值，將該平均值當(dāng)作評(píng)價(jià)指標(biāo)的估計(jì)值。在實(shí)驗(yàn)中，CCPC算法的實(shí)驗(yàn)參數(shù)為：功效指標(biāo)p=-1，算法迭代終止條件ε=1e-5，最大迭代次數(shù)T=100。圖6～11依次列出了表2中數(shù)據(jù)集的評(píng)價(jià)指標(biāo)估計(jì)，其中橫坐標(biāo)為成對(duì)約束數(shù)目，每幅圖中的縱坐標(biāo)分別為AC、NMI、RI評(píng)價(jià)指標(biāo)估計(jì)值。

圖6 breast數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖7 iris數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖8 seeds數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖9 wine數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖10 X1數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖11 X2數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

從圖6可看出，CCPC算法對(duì)應(yīng)的三個(gè)評(píng)價(jià)指標(biāo)都是最高的，聚類(lèi)效果表現(xiàn)最好。由于breast數(shù)據(jù)量相對(duì)較大，對(duì)比算法的SSC算法運(yùn)算速度不佳，因此在計(jì)算過(guò)程中不考慮SSC算法的主動(dòng)學(xué)習(xí)部分，只研究其半監(jiān)督聚類(lèi)算法。在成對(duì)約束數(shù)目不斷增加的過(guò)程中，PD-sSC、CE-sSC和PCBKM算法的三個(gè)指標(biāo)值都顯示下降趨勢(shì)，其中PCBKM算法的降幅最大，此趨勢(shì)是因?yàn)檫x擇了固定的懲罰項(xiàng)系數(shù)，此時(shí)，當(dāng)成對(duì)約束數(shù)目增加時(shí)，目標(biāo)函數(shù)中的懲罰項(xiàng)相對(duì)比重會(huì)增加，從而影響了聚類(lèi)效果。但CCPC算法評(píng)價(jià)指標(biāo)卻基本呈現(xiàn)上升趨勢(shì)，圖6～11都有該現(xiàn)象，這是CCPC算法的優(yōu)點(diǎn)，即對(duì)懲罰系數(shù)的選擇不敏感，具有抗干擾性。

從圖7可看出，CCPC算法的AC與RI指標(biāo)值都比其他4個(gè)算法高，NMI指標(biāo)值也僅次于SSC算法。隨著成對(duì)約束數(shù)目的增加，CCPC算法與PCBKM算法的評(píng)價(jià)指標(biāo)是單增的，PD-sSC和CE-sSC算法存在明顯的下降趨勢(shì)。雖然SSC算法的NMI指標(biāo)值最優(yōu)，但是SSC算法包含兩個(gè)對(duì)算法影響較大的超參數(shù)，并且算法運(yùn)算時(shí)間較長(zhǎng)，因此SSC算法不是最好的選擇。

從圖8可看出，CCPC算法的三個(gè)評(píng)價(jià)指標(biāo)也是優(yōu)于其他4個(gè)算法，且值都高于0.8。當(dāng)成對(duì)約束數(shù)目大于30時(shí)，PD-sSC和CE-sSC算法隨著成對(duì)約束數(shù)目的增加，聚類(lèi)性能不斷下降，而CCPC算法保持了與PCBKM算法相近的增加值，該現(xiàn)象說(shuō)明了閉包準(zhǔn)則能有效提高聚類(lèi)效果，CCPC算法吸取了PCBKM算法的優(yōu)點(diǎn)。從圖9也可看出，CCPC算法的3個(gè)指標(biāo)值都要優(yōu)于其他4個(gè)算法，算法性能與seeds數(shù)據(jù)相似，3個(gè)指標(biāo)值都大于0.8，進(jìn)一步表明CCPC算法聚類(lèi)效果最好。

從圖10可看出，當(dāng)成對(duì)約束小于32的時(shí)候，除了SSC算法其他4個(gè)算法的AC、NMI和RI指標(biāo)值之間差別較小，隨著成對(duì)約束數(shù)目的增加，CCPC算法的增長(zhǎng)趨勢(shì)明顯優(yōu)于其他算法，說(shuō)明聚類(lèi)效果優(yōu)于其他4個(gè)算法。從圖11可看出，PCBKM算法在X2數(shù)據(jù)中聚類(lèi)表現(xiàn)最好，當(dāng)成對(duì)約束數(shù)目不足時(shí)，PD-sSC和PCBKM算法性能會(huì)出現(xiàn)小幅度下降，而當(dāng)成對(duì)約束數(shù)目在20至70區(qū)間范圍內(nèi)取值時(shí)，CE-sSC算法優(yōu)于CCPC和PD-sSC算法且三類(lèi)算法效果都保持遞增趨勢(shì)。在接下來(lái)不斷增加的過(guò)程中，CCPC算法的評(píng)價(jià)值也不斷上升。

綜合圖6～11的結(jié)果，可得出CCPC算法有較好的聚類(lèi)效果。在成對(duì)約束數(shù)目增加的情況下，CCPC算法的聚類(lèi)性能呈現(xiàn)出上升趨勢(shì)；一旦成對(duì)約束數(shù)目較為充分時(shí)，CCPC算法就能夠給出優(yōu)于其他算法的聚類(lèi)結(jié)果?？傮w上，可以得出如下結(jié)論：CCPC算法優(yōu)于對(duì)比算法。

4 結(jié)語(yǔ)

為解決PD-sSC算法在處理成對(duì)約束數(shù)目相對(duì)較多時(shí)聚類(lèi)性能不夠理想的問(wèn)題，本文提出了基于閉包準(zhǔn)則和成對(duì)約束的半監(jiān)督聚類(lèi)算法（CCPC）。該算法通過(guò)引入PCBKM算法中基于must-link約束對(duì)樣本進(jìn)行打包的思想，得到了只帶更新了的cannot-link約束的新樣本組，再用PD-sSC算法進(jìn)行聚類(lèi)分析，最后根據(jù)打包原則將聚類(lèi)結(jié)果反射到原樣本組上；克服了PCBKM算法在處理cannot-link約束時(shí)的不足；糅合了PD-sSC算法和PCBKM算法的各自?xún)?yōu)點(diǎn)。實(shí)驗(yàn)結(jié)果表明，在成對(duì)約束數(shù)目較少時(shí)，CCPC算法在聚類(lèi)性能上與PD-sSC算法保持一致；在成對(duì)約束數(shù)目相對(duì)較大時(shí)，CCPC算法在聚類(lèi)性能上與PCBKM算法保持一致。因此，無(wú)論成對(duì)約束數(shù)目是大是小，CCPC算法都有不錯(cuò)的聚類(lèi)效果。