徐圣兵,林上鈞,鐘國(guó)祥
1. 廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,廣東 廣州 510006
2. 廣東工業(yè)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院,廣東 廣州 510520
在大數(shù)據(jù)時(shí)代,對(duì)數(shù)據(jù)進(jìn)行人工標(biāo)注往往需要耗費(fèi)大量的人工成本,從而使得研究如何有效利用少量帶標(biāo)注對(duì)象開(kāi)展知識(shí)學(xué)習(xí)成為機(jī)器學(xué)習(xí)中的一個(gè)重要課題。因此,如何在只有少量指導(dǎo)信息的情況下去學(xué)習(xí)知識(shí)是目前一個(gè)很重要的研究議題。常見(jiàn)的半監(jiān)督信息[1-4]有2類:一類是少部分對(duì)象帶類標(biāo)簽信息;另一類是少量對(duì)象間的成對(duì)約束信息。其中,成對(duì)約束信息因其標(biāo)注成本低且有效,而被眾多半監(jiān)督核聚類[5-8]所采用。但是,成對(duì)約束信息的測(cè)度目前還沒(méi)有一個(gè)統(tǒng)一標(biāo)準(zhǔn),進(jìn)而限制了成對(duì)約束指導(dǎo)信息的有效利用。因此,如何有效測(cè)度和利用成對(duì)約束指導(dǎo)信息成為半監(jiān)督學(xué)習(xí)算法研究領(lǐng)域的一個(gè)亟待解決的新議題。
Wang[9]引入對(duì)象間隸屬度交互效應(yīng)測(cè)度,基于模糊數(shù)學(xué)理論將軟聚類思想推廣應(yīng)用到非球形數(shù)據(jù),提出了基于成對(duì)約束的半監(jiān)督模糊核聚類算法(semi-supervised kernel-based fuzzy c-means with pairwise constraints,PCKFCM)。目前基于成對(duì)約束的核聚類算法研究主要集中在以下兩方面:1)對(duì)象方面。Wang[10]利用動(dòng)態(tài)加權(quán)給對(duì)象空間上每個(gè)對(duì)象分配一個(gè)動(dòng)態(tài)權(quán)值,以解決對(duì)象對(duì)類簇貢獻(xiàn)不均衡的問(wèn)題,形成了基于成對(duì)約束的動(dòng)態(tài)加權(quán)半監(jiān)督模糊核聚類算法(DKFCM)。王勇臻等[11]提出了利用主動(dòng)學(xué)習(xí)的方法選擇對(duì)象,以解決初始化對(duì)象不具代表性的問(wèn)題。王小玉[12]利用成對(duì)約束調(diào)整對(duì)象間的關(guān)系,以解決密度相差比較大的簇進(jìn)行有效聚類的問(wèn)題,提出了基于共享近鄰的成對(duì)約束譜聚類算法。2)核函數(shù)方面。Wang[13]提出了面向成對(duì)約束半監(jiān)督模糊核聚類的核參數(shù)優(yōu)化算法,以解決核函數(shù)參數(shù)影響聚類性能的問(wèn)題。Kusunoki[14]提出利用Boolean核函數(shù)解決類簇可解釋性的問(wèn)題。Zhang等[15]利用自適應(yīng)核方法指導(dǎo)標(biāo)注傳播,實(shí)現(xiàn)高維數(shù)據(jù)分類。但目前對(duì)于成對(duì)約束核聚類的研究中,還缺少對(duì)成對(duì)約束指導(dǎo)信息的有效測(cè)度方面的關(guān)注。
為了解決上述問(wèn)題,本文提出基于交叉熵測(cè)度的成對(duì)約束核函數(shù)聚類算法。交叉熵作為成對(duì)約束對(duì)象隸屬度選擇的信息度量工具,以此為基礎(chǔ)而提出了本文的最小-最大交叉熵隸屬度學(xué)習(xí)準(zhǔn)則。以此準(zhǔn)則為基礎(chǔ),形成基于交叉熵測(cè)度的成對(duì)約束核函數(shù)聚類算法。與其他算法的性能對(duì)比實(shí)驗(yàn)表明:本算法的對(duì)象類簇劃分更加有效,同時(shí)也說(shuō)明本算法能更加有效利用成對(duì)約束指導(dǎo)信息提升聚類性能。
成對(duì)約束[16]一般可以分為正關(guān)聯(lián)約束(mustlink)和負(fù)關(guān)聯(lián)約{束(cannot-link)2種}約束。設(shè)mustlink集合則表示與屬于同一類{,記這種關(guān)系為};設(shè)cannot-link集合,若則表示與屬于不同類,記這種關(guān)系為;成對(duì)約束關(guān)系示意如圖1所示。
圖1 成對(duì)約束示意
將成對(duì)約束指導(dǎo)信息引入到核聚類算法是一種提升聚類性能的有效途徑。核聚類算法利用Mercer核[17]將原始空間上的對(duì)象映射到高維特征空間上,從而實(shí)現(xiàn)對(duì)象線性可分。如圖2所示,在二維空間上呈環(huán)狀分布的非球形數(shù)據(jù)難以被有效劃分,但通過(guò)核方法映射到三維空間上便可實(shí)現(xiàn)線性可分。
圖2 核函數(shù)映射
在FCM算法[18]基礎(chǔ)上,模糊核聚類算法[19](KFCM)的目標(biāo)函數(shù)如下:
在此基礎(chǔ)上,一種用對(duì)象間隸屬度二次項(xiàng)測(cè)度方法[9]來(lái)表示成對(duì)約束的核模糊算法PCKFCM被提出。PCKFCM算法的目標(biāo)函數(shù)如下:
式中的第1部分繼承FKC算法處理非球形數(shù)據(jù)的方法;第2部分是成對(duì)約束違反的懲罰項(xiàng);為平衡參數(shù)。PCKFCM算法用對(duì)象隸屬度交互相乘的測(cè)度來(lái)指導(dǎo)學(xué)習(xí)過(guò)程。
1948年,Shannon[20]借鑒熱力學(xué)中熵的概念,將其引入到信息論中,提出了信息熵(也稱為香農(nóng)熵)。信息熵量化了對(duì)象包含的不確定性,而交叉熵作為信息熵的拓展,量化了對(duì)象間不確定性的差異程度,也是信息論研究中的重要領(lǐng)域,在機(jī)器學(xué)習(xí)、模式識(shí)別等眾多領(lǐng)域有著廣泛的應(yīng)用。尤其在深度學(xué)習(xí)領(lǐng)域中,交叉熵可以作為一種損失函數(shù)用來(lái)評(píng)判學(xué)習(xí)效果。因此在CEMFKCPC(cross-entropy-measure based fuzzy kernel clusting algorithm with pairwise constraints)算法中,我們將交叉熵引入到成對(duì)約束指導(dǎo)信息度量中。
從對(duì)象交叉熵定義的數(shù)學(xué)表達(dá)式中可以推出如下關(guān)系式[21]:
為便于討論,式(2)右邊2項(xiàng)依次記為:
定義3 最小-最大交叉熵隸屬度學(xué)習(xí)準(zhǔn)則
圖3 最小-最大交叉熵隸屬度學(xué)習(xí)準(zhǔn)則示意
圖4 交叉熵指導(dǎo)算法學(xué)習(xí)過(guò)程
CE-sSC(cross-entropy semi-supervised clusting based on pairwise constraints)算法[21]是在極大熵聚類算法的基礎(chǔ)上,利用成對(duì)約束的一種交叉熵的信息表達(dá)方法,擴(kuò)展得到了一種基于成對(duì)約束的交叉熵半監(jiān)督聚類算法。該方法能有效利用少量的成對(duì)約束監(jiān)督信息在線性可分的類簇上提高聚類性能,但對(duì)于非線性可分的類簇難以得到較好的效果(如圖5中的左圖)。在實(shí)際生產(chǎn)環(huán)境中,大多數(shù)情況的類簇都是非線性可分的,因此,在CE-sSC基礎(chǔ)上,本文引入核函數(shù)處理非線性可分?jǐn)?shù)據(jù)。
圖5 核函數(shù)實(shí)現(xiàn)示意
如圖5,結(jié)合成對(duì)約束信息,利用核函數(shù)將原本非線性可分的類簇映射到另一個(gè)空間后實(shí)現(xiàn)線性可分。
根據(jù)以上定義和分析,構(gòu)造CEM-FKCPC算法的目標(biāo)函數(shù)如下:式中目標(biāo)函數(shù)的符號(hào)說(shuō)明如表1。
表1 符號(hào)說(shuō)明
由此得到聚類中心更新公式:
同理,由以下式子:
可以得到隸屬度迭代公式:
據(jù)上述CEM-FKCPC算法推導(dǎo)過(guò)程和迭代公式,給出CEM-FKCPC算法具體步驟如下:
CEM-FKCPC算法的時(shí)間復(fù)雜度主要由兩部分組成:1)聚類中心矩陣,由于類簇?cái)?shù)遠(yuǎn)遠(yuǎn)小于對(duì)象數(shù)據(jù)個(gè)數(shù)所以其時(shí)間復(fù)雜度為;2)隸屬度矩陣,其時(shí)間復(fù)雜度為。其中為對(duì)象數(shù)據(jù)集對(duì)象個(gè)數(shù),為對(duì)象數(shù)據(jù)集的維度,表示成對(duì)約束關(guān)系的對(duì)象個(gè)數(shù)。當(dāng)算法迭代t次時(shí),算法的時(shí)間復(fù)雜度為。在實(shí)際算法的應(yīng)用過(guò)程中,由于信息獲取成本限制,監(jiān)督信息難以獲取或只能獲取少部分,則有。因此,算法的時(shí)間復(fù)雜近似線性的。
為了檢驗(yàn)CEM-FKCPC算法的聚類性能,實(shí)驗(yàn)用基于交叉熵的CE-sSC算法[21]、二次項(xiàng)測(cè)度的PCKFCM算法[9]、DKFCM算法[10]和傳統(tǒng)的kmeans算法、KFCM算法[19]作為對(duì)比實(shí)驗(yàn)。在所有的實(shí)驗(yàn)中,使用高斯作為核函數(shù),設(shè)置算法迭代終止條件閾值為,最大迭代次數(shù)。實(shí)驗(yàn)過(guò)程中,對(duì)每個(gè)數(shù)據(jù)集分別固定成對(duì)約束數(shù)目,選擇 0、10、20、30、40、50對(duì)進(jìn)行實(shí)驗(yàn)。對(duì)各數(shù)據(jù)集中每個(gè)固定數(shù)目的成對(duì)約束都進(jìn)行10次重復(fù)實(shí)驗(yàn),每次實(shí)驗(yàn)從數(shù)據(jù)集中隨機(jī)抽取相應(yīng)數(shù)目的成對(duì)約束,用于指導(dǎo)各算法對(duì)數(shù)據(jù)集的聚類學(xué)習(xí)。由于上述部分算法可能受初值選擇的影響,為此在每次實(shí)驗(yàn)過(guò)程中算法運(yùn)行100次后取平均作為該次實(shí)驗(yàn)結(jié)果,最后對(duì)10次重復(fù)實(shí)驗(yàn)的結(jié)果取平均作為該固定數(shù)目成對(duì)約束實(shí)驗(yàn)的最終結(jié)果。
1) 性能指標(biāo)
對(duì)于采用的各種聚類算法,實(shí)驗(yàn)將采用如下性能指標(biāo)評(píng)估聚類算法性能。
Rand Index[22]度量定義為
式中:TP:同一類的對(duì)象被分到同一個(gè)簇;FP:不同類的對(duì)象被分到同一個(gè)簇;TN:不同類的對(duì)象被分到不同簇;FN:同一類的對(duì)象被分到不同簇。1,算法性能越好;數(shù)值越接近0,算法性能越差。
2) 標(biāo)準(zhǔn)數(shù)據(jù)集
實(shí)驗(yàn)標(biāo)準(zhǔn)數(shù)據(jù)集分別選用UCI常用的數(shù)據(jù)集和人工合成的非球型數(shù)據(jù)集[23](見(jiàn)表2)。其中,Iris數(shù)據(jù)集和Wine數(shù)據(jù)集廣泛應(yīng)用于各類算法性能測(cè)試,具有較高的直觀性和可靠性。人工合成的非球型數(shù)據(jù)可以檢驗(yàn)核方法對(duì)線性不可分?jǐn)?shù)據(jù)的聚類性能。X型、拋物線型數(shù)據(jù)如圖6所示。
表2 標(biāo)準(zhǔn)數(shù)據(jù)集信息
除此之外,為了更能體現(xiàn)上述聚類算法在實(shí)際應(yīng)用中的聚類性能,本文從文獻(xiàn)[24]當(dāng)中選取基于基站定位數(shù)據(jù)的商圈分析和基于多污染因素的區(qū)域空氣質(zhì)量評(píng)價(jià)等實(shí)際應(yīng)用案例。其中,基站定位數(shù)據(jù)的商圈分析案例根據(jù)手機(jī)運(yùn)營(yíng)商的用戶的歷史定位數(shù)據(jù)進(jìn)行數(shù)據(jù)分析,歸納出商圈的人流特征和規(guī)律,識(shí)別出不同的商圈,從而達(dá)到為合適區(qū)域進(jìn)行運(yùn)營(yíng)商促銷活動(dòng)的目的。而空氣質(zhì)量評(píng)價(jià)案例則是關(guān)于環(huán)境質(zhì)量評(píng)價(jià)方面的相關(guān)應(yīng)用,空氣質(zhì)量評(píng)價(jià)是環(huán)境質(zhì)量評(píng)價(jià)中的一個(gè)重要組成部分,空氣質(zhì)量一般受多個(gè)污染因素相互作用影響,從多污染因素角度出發(fā)更能客觀準(zhǔn)確地反映環(huán)境質(zhì)量狀況,考慮SO2、NO、NO2等多個(gè)相關(guān)污染因素,通過(guò)采集和預(yù)處理得到空氣質(zhì)量數(shù)據(jù),用以對(duì)空氣質(zhì)量進(jìn)行評(píng)價(jià)。因此,本文采用商圈用戶特征數(shù)據(jù)集Y1和空氣質(zhì)量數(shù)據(jù)集Y2這兩個(gè)工業(yè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)數(shù)據(jù)均已標(biāo)準(zhǔn)化,其中以文獻(xiàn)[24]的劃分結(jié)果作為數(shù)據(jù)集Y1和Y2的標(biāo)簽,便于進(jìn)行聚類性能對(duì)比,數(shù)據(jù)如表3和表4。
圖6 人工合成數(shù)據(jù)集
表3 Y1數(shù)據(jù)集部分?jǐn)?shù)據(jù)
表4 Y2數(shù)據(jù)集部分?jǐn)?shù)據(jù)
根據(jù)實(shí)驗(yàn)設(shè)置與上述的實(shí)驗(yàn)方案,通過(guò)隨機(jī)抽取已知的成對(duì)約束監(jiān)督信息指導(dǎo)算法聚類學(xué)習(xí),實(shí)驗(yàn)結(jié)果如下:
由圖7(a)、(b)可以看出,在Iris和Wine數(shù)據(jù)集上,基于交叉熵測(cè)度的CEM-FKCPC算法在不同的成對(duì)約束數(shù)量均優(yōu)于其余算法,在實(shí)驗(yàn)中,控制成對(duì)約束數(shù)量在50對(duì)以內(nèi),證明了利用交叉熵表達(dá)成對(duì)約束的CEM-FKCPC算法只需利用少量的監(jiān)督信息就能達(dá)到較好的聚類性能。對(duì)于X型(如圖7(c)),4種半監(jiān)督算法在少量的成對(duì)約束條件下,整體聚類性能都不高,但CEM-FKCPC算法的聚類性能依然高于其余算法。對(duì)于拋物線型數(shù)據(jù)(如圖7(d)),CEM-FKCPC算法隨著成對(duì)約束數(shù)量的增加,聚類性能逐漸超越PCKFCM算法和CE-sSC算法。同時(shí),CEM-FKCPC算法的成對(duì)約束對(duì)聚類性能的提升效果優(yōu)于CE-sSC等算法。由結(jié)果分析知道,對(duì)于非球形數(shù)據(jù),CEM-FKCPC算法合理利用成對(duì)約束監(jiān)督信息的核聚類算法能更好地處理非球形數(shù)據(jù),提高聚類性能。
由圖7(e)可以看出,在Y1數(shù)據(jù)集上,CEMFKCPC算法的RI值一直都優(yōu)于其他4種算法。對(duì)于Y2數(shù)據(jù)集(圖7(f)),在成對(duì)約束數(shù)量在0~15時(shí),CE-sSC算法RI值要高于CEM-FKCPC算法,但成對(duì)約束數(shù)量在20~50時(shí),CEM-FKCPC算法RI值上升趨勢(shì)明顯,逐步趕超其余算法。因此,根據(jù)RI值的比較可以看出,基于交叉熵測(cè)度的CEM-FKCPC算法能更有效地利用成對(duì)約束信息。此外,從圖7總體上看,與傳統(tǒng)的k-means和FKCM算法比較可以看出,CEM-FKCPC算法優(yōu)于這類傳統(tǒng)算法。
圖7 聚類結(jié)果
1)針對(duì)基于成對(duì)約束的核聚類中,如何合理高效地利用成對(duì)約束監(jiān)督信息,同時(shí)更好地表達(dá)成對(duì)約束信息并作出明確解析等問(wèn)題,本文引入交叉熵作為成對(duì)約束信息度量,提出新的成對(duì)約束框架CEM-FKCPC。
2)相比于已有的成對(duì)約束度量,交叉熵度量方法更能表達(dá)整體的不確定性信息。通過(guò)UCI經(jīng)典數(shù)據(jù)集、合成的非球形數(shù)據(jù)集和實(shí)際工業(yè)數(shù)據(jù)集的實(shí)驗(yàn)表明,CEM-FKCPC算法能有效地利用少量的成對(duì)約束監(jiān)督信息提高聚類性能。
3)對(duì)比CE-sSC、PCKFCM、DKFCM算法,基于成對(duì)約束的核聚類算法CEM-FKCPC對(duì)于線性不可分?jǐn)?shù)據(jù)有更好的聚類效果。