陳愛國，王士同

(1.江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無錫 214122； 2.香港理工大學(xué) 計(jì)算機(jī)系，香港 九龍 999077)

基于極大熵的知識(shí)遷移模糊聚類算法

陳愛國，王士同

(1.江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無錫 214122； 2.香港理工大學(xué) 計(jì)算機(jī)系，香港 九龍 999077)

針對(duì)傳統(tǒng)的聚類算法在樣本數(shù)據(jù)量不足或樣本受到污染情況下的聚類性能下降問題，在經(jīng)典的極大熵聚類算法(MEKTFCA)的基礎(chǔ)上，提出了一種新的融合歷史聚類中心點(diǎn)和歷史隸屬度這兩種知識(shí)的基于極大熵的知識(shí)遷移模糊聚類算法。該算法通過學(xué)習(xí)由源域總結(jié)出來的有益歷史聚類中心和歷史隸屬度知識(shí)來指導(dǎo)數(shù)據(jù)量不足或受污染的目標(biāo)域數(shù)據(jù)的聚類任務(wù)，從而提高了聚類性能。通過一組模擬數(shù)據(jù)集和兩組真實(shí)數(shù)據(jù)集構(gòu)造的遷移場景上的實(shí)驗(yàn)，證明了該算法的有效性。

知識(shí)遷移；極大熵；聚類算法；極大熵聚類；模糊聚類

聚類是一種常用的數(shù)據(jù)分析方法，在人工智能、模式識(shí)別和機(jī)器學(xué)習(xí)等領(lǐng)域[1-3]一直受到廣泛關(guān)注。聚類作為一種無監(jiān)督的數(shù)據(jù)分析技術(shù)，通過數(shù)據(jù)之間的疏密程度，將數(shù)據(jù)劃分到不同的數(shù)據(jù)簇中，使得簇內(nèi)的數(shù)據(jù)之間關(guān)系比較緊密，而簇之間的數(shù)據(jù)關(guān)系比較疏遠(yuǎn)。根據(jù)聚類使用方法的不同，將聚類分成常見的一些類別：基于劃分的聚類算法[4-7]、基于層次的聚類算法[8-9]、基于密度的聚類算法[10-11]、基于圖論的聚類算法[12]等。這些聚類算法在針對(duì)特定的數(shù)據(jù)集進(jìn)行聚類時(shí)，通常能獲得理想的聚類效果。但這些聚類性能的有效獲得都離不開一個(gè)必要前提，那就是進(jìn)行聚類時(shí)的數(shù)據(jù)必須是充分的，換句話說，這些聚類算法不適合處理數(shù)據(jù)不充分的情況。

但在實(shí)際生產(chǎn)、生活中，數(shù)據(jù)不充分的情況或數(shù)據(jù)受到污染的情況往往普遍存在。例如，在一個(gè)新領(lǐng)域收集數(shù)據(jù)之初，數(shù)據(jù)往往是不充足的。又或者由于受到硬件設(shè)備的不穩(wěn)定性或環(huán)境等一些因素的影響，可能會(huì)采集到受噪聲干擾的失真數(shù)據(jù)。對(duì)于不充足的數(shù)據(jù)和受到污染的數(shù)據(jù)進(jìn)行聚類分析時(shí)，如果直接采用傳統(tǒng)聚類方法，往往會(huì)造成聚類結(jié)果的不理想，甚至有時(shí)會(huì)出現(xiàn)聚類失效的結(jié)果。

如何有效解決數(shù)據(jù)量不足和數(shù)據(jù)受污染情況下的數(shù)據(jù)聚類性能問題，是近年來研究工作者的方向之一。其中，知識(shí)遷移[13]機(jī)制的引入是一種有效手段。知識(shí)遷移機(jī)制是指將歷史數(shù)據(jù)(也稱為源域)中提煉的有益知識(shí)應(yīng)用到對(duì)當(dāng)前數(shù)據(jù)(也稱為目標(biāo)域)聚類任務(wù)的指導(dǎo)，用于提高當(dāng)前數(shù)據(jù)的聚類結(jié)果。歷史數(shù)據(jù)與當(dāng)前數(shù)據(jù)之間既存在著聯(lián)系，也存在著明顯的差別。目前，應(yīng)用知識(shí)遷移機(jī)制來提高聚類性能的代表性算法有：在多任務(wù)中使用共享子空間進(jìn)行聚類的LSSMTC算法[14]、使用K均值組合方法的CombKM算法[14]、使用自學(xué)習(xí)遷移機(jī)制的STC聚類算法[15]、使用特征和樣本協(xié)同機(jī)制的Co-clustering聚類算法[16]及遷移譜聚類TSC算法[17]。這些基于知識(shí)遷移的聚類算法雖然提高了一定的聚類性能，但離實(shí)際應(yīng)用還有一定差距，且這些聚類算法在進(jìn)行聚類任務(wù)時(shí)需要完整的歷史數(shù)據(jù)集，這在一些特殊場合，如保密需要，完整的歷史數(shù)據(jù)是不可能獲得的。所以，研究一種有隱私保護(hù)的高效遷移聚類算法具有必要性和實(shí)用性。

本文在經(jīng)典的MECA聚類算法的基礎(chǔ)上，通過對(duì)MECA算法的目標(biāo)函數(shù)進(jìn)行改造，使其具有學(xué)習(xí)歷史知識(shí)的能力，進(jìn)而提高算法在樣本量不充分或受到污染情況下聚類的性能。

1 經(jīng)典極大熵聚類算法

在傳統(tǒng)C均值聚類算法的基礎(chǔ)上，通過引入具有明確物理含義的熵，產(chǎn)生出了具有簡潔的數(shù)學(xué)表達(dá)式和明確物理含義特點(diǎn)的極大熵模糊聚類算法。極大熵模糊聚類算法有很多種不同的表達(dá)形式，其中文獻(xiàn)[6-7]給出的是經(jīng)典的極大熵模糊聚類算法，其具體表述如下。

式中：xi表示第i個(gè)樣本點(diǎn)；vj表示第j類中心點(diǎn)；μij表示第i個(gè)樣本點(diǎn)隸屬于第j類的程度；‖xi-vj‖2表示第i個(gè)樣本點(diǎn)與第j類中心點(diǎn)的距離；α是正則化系數(shù)，由μij構(gòu)成隸屬度矩陣U∈RN×C，由vj構(gòu)成中心點(diǎn)矩陣V∈Rd×C。

采用拉格朗日條件極值優(yōu)化方法解得式(1)的最優(yōu)聚類中心V和隸屬度U的迭代公式為

根據(jù)上述推導(dǎo)，總結(jié)出MECA算法的具體步驟如下:

輸入 數(shù)據(jù)集X，分類數(shù)C，正則化系數(shù)α，最大迭代次數(shù)T，終止閾值ε。

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

1)初始化迭代計(jì)數(shù)器t=0,隨機(jī)初始化隸屬度矩陣U(0)。

2)根據(jù)式(2)和1)的隸屬度矩陣U(t)獲得新的類中心V(t)。

3)根據(jù)式(3)和2)獲得的類中心V(t)計(jì)算得新的隸屬度U(t+1)。

4)當(dāng)‖U(t+1)-U(t)‖<ε或者t>T時(shí)算法終止，否則跳轉(zhuǎn)到2)。

通過觀察MECA算法的具體步驟可以看出，原始的MECA算法不具有知識(shí)遷移的能力。

MECA算法在數(shù)據(jù)量充足時(shí)，可以使用上述迭代過程獲得有效的類中心和隸屬度。但當(dāng)樣本量不充足或樣本被污染的情況下，直接使用MECA算法獲得的聚類中心往往嚴(yán)重偏離實(shí)際聚類中心，甚至有時(shí)會(huì)出現(xiàn)聚類失效的情況。因此，在數(shù)據(jù)量不足或數(shù)據(jù)受到污染情況下，研究有效的聚類算法，具有必要性和實(shí)際價(jià)值。

2 基于極大熵的知識(shí)遷移模糊聚類

在知識(shí)遷移理論[13]中，當(dāng)源域數(shù)據(jù)和目標(biāo)域數(shù)據(jù)既存在一定的相關(guān)性，同時(shí)又存在著明顯的差異時(shí)，可通過對(duì)源域有益知識(shí)的充分利用來指導(dǎo)目標(biāo)域任務(wù)更好地完成。本文嘗試通過將數(shù)據(jù)量充分的源域知識(shí)遷移至數(shù)據(jù)量不足或被污染的目標(biāo)域的聚類任務(wù)中，來提高目標(biāo)域的聚類性能。

為了實(shí)現(xiàn)源域知識(shí)到目標(biāo)域遷移的目的，需要解決3個(gè)核心問題：

1)遷移什么知識(shí)；

2)如何遷移；

3)什么時(shí)候遷移。

首先，解決源域到目標(biāo)域遷移什么知識(shí)的問題。在基于劃分的聚類算法中，隸屬度和聚類中心點(diǎn)是對(duì)聚類結(jié)果具有決定性作用的兩個(gè)因素。故本文選擇隸屬度和聚類中心點(diǎn)作為被遷移的知識(shí)。

其次，需要解決如何才能實(shí)現(xiàn)將源域的隸屬度和聚類中心點(diǎn)知識(shí)遷移到目標(biāo)域的聚類任務(wù)中的問題。我們通過以下兩個(gè)規(guī)則來實(shí)現(xiàn)。

1)隸屬度重要程度受約束規(guī)則

該規(guī)則對(duì)應(yīng)的公式為

2)聚類中心點(diǎn)變化最小規(guī)則

該規(guī)則的公式為

根據(jù)上述分析，針對(duì)經(jīng)典MECA算法不具有知識(shí)遷移能力的不足，本文在MECA算法的基礎(chǔ)上結(jié)合上述兩個(gè)規(guī)則，提出基于極大熵知識(shí)遷移模糊聚類算法，即MEKTFCA算法。該算法的原理如圖1。

圖1 MEKTFCA算法原理圖Fig.1 Overall framework of MEKTFCA algorithm

MEKTFCA算法首先對(duì)源數(shù)據(jù)集，通過經(jīng)典的MECA算法獲得歷史聚類中心，然后根據(jù)目標(biāo)數(shù)據(jù)集和所獲得的歷史聚類中心，通過再次使用經(jīng)典的MECA算法獲得歷史隸屬度，最后通過MEKTFCA算法和歷史聚類中心及歷史隸屬度獲得最終的聚類結(jié)果。

融入了隸屬度重要程度受約束規(guī)則和聚類中心點(diǎn)變化最小規(guī)則得到的MEKTFCA算法的具體目標(biāo)函數(shù)為

其中

MECA算法的正則化熵項(xiàng)。同時(shí)，根據(jù)式(6)～(8)可以發(fā)現(xiàn)，當(dāng)隸屬度重要程度受約束規(guī)則的平衡因子λ=1而且聚類中心點(diǎn)變化最小規(guī)則的平衡因子β=0這種特殊情況時(shí)，MEKTFCA算法就退化為經(jīng)典的MECA算法。MEKTFCA算法的本質(zhì)是，通過調(diào)節(jié)平衡因子λ和β的大小，來調(diào)整歷史隸屬度和歷史類中心點(diǎn)對(duì)當(dāng)前聚類任務(wù)的影響，從而改善由于數(shù)據(jù)量不足和數(shù)據(jù)被污染情況下直接采用MECA算法造成聚類結(jié)果不理想的情況。

2.1 參數(shù)求解

式(6)的參數(shù)求解問題，即為在有約束條件下求解最優(yōu)的參數(shù)使得目標(biāo)函數(shù)值最小。與MECA求最優(yōu)解方法相同，我們采用拉格朗日乘子法進(jìn)行求解，首先構(gòu)造拉格朗日函數(shù)表達(dá)式,即

式中ηi為Lagrange乘子。

因?yàn)橛屑s束條件

將式(10)代入式(11)可得

將式(12)代入式(10)可得隸屬度的迭代公式為

2.2 算法步驟

根據(jù)上述的推導(dǎo)過程所獲得的隸屬度和聚類中心點(diǎn)的迭代公式，給出MEKTFCA算法的具體步驟如下。

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

2)初始化迭代計(jì)數(shù)器t=0。

3)根據(jù)式(14)計(jì)算得到新的聚類中心V(t)。

4)根據(jù)式(13)計(jì)算得到新的隸屬度矩陣U(t+1)。

5)當(dāng)‖U(t+1)-U(t)‖<ε或者t>T時(shí)算法終止，否則跳轉(zhuǎn)到3)。

以上算法步驟同時(shí)回答了實(shí)現(xiàn)知識(shí)遷移中的第3個(gè)核心問題：什么時(shí)候遷移。通過算法步驟可以看到，在算法不斷迭代過程中，隸屬度和中心點(diǎn)的迭代公式中使用到了歷史隸屬度知識(shí)和歷史類中心點(diǎn)知識(shí)。從而在算法的迭代過程中實(shí)現(xiàn)了知識(shí)的遷移。

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)設(shè)置

為驗(yàn)證本文所提MEKTFCA算法的有效性，將構(gòu)造一組模擬數(shù)據(jù)集和兩組真實(shí)數(shù)據(jù)集作為實(shí)驗(yàn)所使用的遷移場景。同時(shí)，選擇6種相關(guān)算法作為對(duì)比算法，對(duì)它們的聚類性能進(jìn)行比較。這6種算法為：在多任務(wù)中使用共享子空間進(jìn)行聚類的LSSMTC算法[14]，使用K均值組合方法的CombKM算法[14]，使用自學(xué)習(xí)遷移機(jī)制的STC聚類算法[15]，使用特征和樣本協(xié)同機(jī)制的Co-clustering聚類算法[16]，遷移譜聚類TSC算法[17]以及經(jīng)典的MECA算法[6-7]。

為了對(duì)聚類算法的結(jié)果進(jìn)行客觀比較，本文采用統(tǒng)一的NMI[18](normalized mutual information)和RI[19](rand index)兩種指標(biāo)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)價(jià)。NMI的計(jì)算公式為

式中：N代表數(shù)據(jù)集的樣本數(shù)目；Np代表聚類到p類的樣本數(shù)目；Nq代表類標(biāo)簽為q的樣本數(shù)目；Np,q代表同時(shí)聚類到p類和類標(biāo)簽為q的樣本數(shù)目。RI評(píng)價(jià)指標(biāo)的計(jì)算公式為

式中：N00代表擁有不同類標(biāo)簽的兩個(gè)樣本聚類到不同類別中的個(gè)數(shù)；N11代表擁有相同類標(biāo)簽的兩個(gè)樣本聚類到相同類別中的個(gè)數(shù)。上述兩種評(píng)價(jià)指標(biāo)值的變化范圍都為[0,1]，且值越大，代表其算法的聚類性能越好。

在MEKTFCA算法中，涉及兩個(gè)平衡因子λ和β如何取值的問題。本文采用網(wǎng)格搜索進(jìn)行遍歷尋優(yōu)，其尋優(yōu)的范圍及其他對(duì)比算法的參數(shù)設(shè)置值如表1所示。

表1 算法參數(shù)設(shè)置值

本實(shí)驗(yàn)所采用的環(huán)境是：Intel i7-5600U 2.60 GHz 8 GB RAM；Windows 8 64 bit；MATLAB R2012b。實(shí)驗(yàn)所列結(jié)果數(shù)據(jù)均是在運(yùn)行10次后求得的平均值。

3.2 模擬數(shù)據(jù)集實(shí)驗(yàn)結(jié)果和分析

該實(shí)驗(yàn)是通過構(gòu)造的模擬數(shù)據(jù)集來驗(yàn)證本文所提的MEKTFCA算法在樣本量不足和受污染情況下聚類算法的有效性。本實(shí)驗(yàn)構(gòu)造了一組源數(shù)據(jù)集S和3組目標(biāo)數(shù)據(jù)集T1、T2、T3，其中源數(shù)據(jù)集和所有的目標(biāo)數(shù)據(jù)集均包含3類2維的數(shù)據(jù)，這些數(shù)據(jù)的生成均采用高斯概率分布模型函數(shù)，生成時(shí)所使用的均值、方差及每個(gè)類別包含的樣本數(shù)如表2所示。

構(gòu)造的源數(shù)據(jù)集S共含有1 500個(gè)樣本，這個(gè)數(shù)據(jù)集數(shù)據(jù)量充足，并且能夠從該數(shù)據(jù)集中提取出對(duì)目標(biāo)數(shù)據(jù)集的聚類具有指導(dǎo)作用的有用知識(shí)。

構(gòu)造的目標(biāo)數(shù)據(jù)集T1共含有90個(gè)樣本，只占源數(shù)據(jù)集S總數(shù)據(jù)量的6%，用于代表數(shù)據(jù)量不充足的場景，雖然數(shù)據(jù)集T1與數(shù)據(jù)集S的均值存在差異，但它們的方差相同，這用于體現(xiàn)遷移學(xué)習(xí)中的源數(shù)據(jù)集與目標(biāo)數(shù)據(jù)集之間既存在著相似性，同時(shí)也存在著一定的差別的情況。

表2 模擬數(shù)據(jù)集生成的參數(shù)設(shè)置

構(gòu)造的目標(biāo)數(shù)據(jù)集T2共含有450個(gè)樣本，占源數(shù)據(jù)集S總數(shù)據(jù)量的30%。用目標(biāo)數(shù)據(jù)集T2來代表目標(biāo)數(shù)據(jù)量充分的場景。

構(gòu)造的目標(biāo)數(shù)據(jù)集T3與目標(biāo)數(shù)據(jù)集T2的均值、方差和數(shù)據(jù)量完全相同。不同的是，數(shù)據(jù)集T3在數(shù)據(jù)集T2的基礎(chǔ)上增加了方差為2、均值為0的高斯噪聲，用于代表數(shù)據(jù)量充分但受到了噪聲污染的場景。

上述構(gòu)造的4組模擬數(shù)據(jù)集的數(shù)據(jù)分布如圖2所示。

在上述構(gòu)造出來的各種遷移場景下，運(yùn)行MEKTFCA算法和6種對(duì)比算法，得到的實(shí)驗(yàn)結(jié)果如表3所示。因?yàn)門SC算法要求樣本的維數(shù)要大于聚類數(shù)目，而在模擬數(shù)據(jù)集上不滿足此條件，所以在表3中我們使用“—”來表示此算法無法運(yùn)行。

(a)數(shù)據(jù)集S

(b)數(shù)據(jù)集T1

(c)數(shù)據(jù)集T2

(d)數(shù)據(jù)集T3

場景評(píng)價(jià)指標(biāo)LSSMTCCombKMSTCCo-lusteringTSCMECAMEKTFCAS-T1NMI-mean0.67410.75940.15560.7372—0.73720.8024NMI-std0.03631.1703×10-1601.1703×10-16—1.1703×10-160.0022RI-mean0.86740.90240.60520.9014—0.90140.9175RI-std0.01941.1703×10-161.1703×10-162.3406×10-16—2.3406×10-160.0071S-T2NMI-mean0.73430.78760.16940.7719—0.76490.8348NMI-std0.032402.9257×10-170.0099—7.4015×10-170.0019RI-mean0.90590.92150.68790.9195—0.91680.9401RI-std0.012801.1703×10-160.0053—00.0011S-T3NMI-mean0.73460.77370.12610.7615—0.77460.8162NMI-std0.02851.1703×10-1600.0094—1.1703×10-161.1703×10-16RI-mean0.89950.91470.58780.9111—0.91480.9372RI-std0.01081.1703×10-1600.0026—01.1703×10-16

觀察表3的實(shí)驗(yàn)結(jié)果可以得出如下結(jié)論：

1) 源數(shù)據(jù)集是S，目標(biāo)數(shù)據(jù)集是T1，它們所代表的是數(shù)據(jù)量不足的場景。從該場景中的實(shí)驗(yàn)結(jié)果可以看出，沒有使用任何遷移機(jī)制的MECA算法，在數(shù)據(jù)量不充分的情況下，其聚類性能要明顯比使用了知識(shí)遷移的MEKTFCA算法差。因?yàn)镸ECA算法對(duì)數(shù)據(jù)量不充足的數(shù)據(jù)集進(jìn)行聚類時(shí)，產(chǎn)生的聚類中心將會(huì)嚴(yán)重偏離實(shí)際的聚類中心，進(jìn)而導(dǎo)致最終的聚類結(jié)果不理想。而MEKTFCA算法由于引入了知識(shí)遷移機(jī)制，在聚類過程中，通過學(xué)習(xí)由源數(shù)據(jù)集提取的歷史類中心和歷史隸屬度中的有用知識(shí)，有效地改善了由于數(shù)據(jù)量不足而導(dǎo)致的聚類中心偏移的問題，最終提高了聚類性能。對(duì)于另外的4種對(duì)比算法，從它們的實(shí)驗(yàn)結(jié)果可以看出，雖然這些算法都使用了不同的機(jī)制來提高聚類結(jié)果，但由于算法本身的限制，在樣本量不充足的場景下，其聚類結(jié)果不理想。

2) 源數(shù)據(jù)集是S，目標(biāo)數(shù)據(jù)集是T2，它們所構(gòu)成的是數(shù)據(jù)量較充足且無污染的場景。從該場景中的實(shí)驗(yàn)結(jié)果可以看出，由于目標(biāo)數(shù)據(jù)集T2的數(shù)據(jù)量較充分，因此所有6種算法均取得比較理想的聚類結(jié)果。這也進(jìn)一步說明了傳統(tǒng)的聚類算法進(jìn)行有效聚類的前提條件是數(shù)據(jù)量要充分。在這6種聚類算法中，由于MEKTFCA算法對(duì)源數(shù)據(jù)集所形成的歷史中心點(diǎn)和歷史隸屬度雙重有益知識(shí)進(jìn)行了學(xué)習(xí)，它的聚類結(jié)果要優(yōu)于其他5種算法。

3)源數(shù)據(jù)集是S，目標(biāo)數(shù)據(jù)集是T3，它們構(gòu)成的是數(shù)據(jù)量較充分但受到污染的場景。從該場景中的實(shí)驗(yàn)結(jié)果可以看出，當(dāng)數(shù)據(jù)受到污染時(shí)，其余5種對(duì)比算法的聚類性能要明顯差于本文提出的MEKTFCA算法。因?yàn)閿?shù)據(jù)集T3受到了污染，從而導(dǎo)致數(shù)據(jù)產(chǎn)生失真，數(shù)據(jù)集的聚類中心產(chǎn)生了顯著的偏移，數(shù)據(jù)類別之間的界限變得模糊，最終使得這五種聚類算法的聚類性能不夠理想。MEKTFCA算法在進(jìn)行聚類時(shí)，通過調(diào)整兩個(gè)平衡因子的權(quán)重來學(xué)習(xí)源數(shù)據(jù)集中有益的歷史中心點(diǎn)知識(shí)和歷史隸屬度知識(shí)，這種遷移知識(shí)的學(xué)習(xí)機(jī)制提高了MEKTFCA算法在數(shù)據(jù)被污染情況下的聚類效果。這也使得MEKTFCA算法具有一定的抗噪性能。

3.3 文本數(shù)據(jù)集實(shí)驗(yàn)結(jié)果和分析

第2個(gè)實(shí)驗(yàn)基于真實(shí)的文本數(shù)據(jù)集20 Newsgroups(20 NG)[20]構(gòu)造的目標(biāo)數(shù)據(jù)樣本量不足的遷移場景來對(duì)MEKTFCA算法的有效性進(jìn)行進(jìn)一

步驗(yàn)證。20 NG數(shù)據(jù)集包含大約20 000條新聞組信息，均勻地分布在20個(gè)不同的集合中。我們選擇這20個(gè)集合中的4個(gè)來生成兩組實(shí)驗(yàn)用的遷移場景：“comp VS sci”和“rec VS talk”。這兩組遷移場景的數(shù)據(jù)集構(gòu)成如表4所示。

表4 文本遷移場景數(shù)據(jù)集構(gòu)成

這兩組遷移場景所使用的數(shù)據(jù)集的來源見表5所示。在構(gòu)造這兩組遷移場景時(shí)，源數(shù)據(jù)集和目標(biāo)數(shù)據(jù)集之間有一定的相似性，同時(shí)又有明顯的不同。如構(gòu)造的“comp VS sci”遷移場景第1類的源數(shù)據(jù)集和目標(biāo)數(shù)據(jù)集都來自同樣的“comp”大類，但它們的子類是完全不同的。第2類的源數(shù)據(jù)集和目標(biāo)數(shù)據(jù)集與此類似。因?yàn)?0 NG數(shù)據(jù)集的原始數(shù)據(jù)的維數(shù)較大，因此實(shí)驗(yàn)之前我們使用工具BOW[21]對(duì)其進(jìn)行了降維處理。本文所提的MEKTFCA算法及其6種對(duì)比算法在此數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如表6。

表5 文本遷移場景的數(shù)據(jù)集來源

表6 文本遷移場景中7種聚類算法性能對(duì)比

觀察表6的實(shí)驗(yàn)結(jié)果可以得出如下結(jié)論：

1) MEKTFCA算法和TSC算法在遷移場景“comp VS sci”上的聚類結(jié)果較其他5種算法的聚類結(jié)果優(yōu)勢明顯。其他5種算法中，MECA算法的聚類結(jié)果最好，LSSMTC算法次之，Co-clustering算法、STC算法和CombKM算法的聚類結(jié)果明顯差于其他算法。究其原因，主要是由于在此構(gòu)造的真實(shí)場景上MEKTFCA算法和TSC算法的遷移學(xué)習(xí)機(jī)制比其他算法更有效。

2) MEKTFCA算法和TSC算法在構(gòu)造的遷移場景“rec VS talk”上的聚類結(jié)果具有同樣明顯的優(yōu)勢，而其他5種算法的聚類結(jié)果卻差很多。MECA算法因?yàn)樵诖诉w移場景下，目標(biāo)數(shù)據(jù)集的樣本量不足，且沒有引入任何遷移學(xué)習(xí)機(jī)制，導(dǎo)致最終的聚類結(jié)果較差。STC算法、CombKM算法、LSSMTC算法和Co-clustering算法盡管都使用了不同的遷移學(xué)習(xí)機(jī)制，但在此遷移場景下的效果不明顯，所以它們的聚類結(jié)果也明顯較差。而MEKTFCA算法和TSC算法在此遷移場景上的知識(shí)遷移效果明顯，故取得較好的聚類結(jié)果。

3) 進(jìn)一步觀察表6的實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，MEKTFCA算法在所構(gòu)造的兩組遷移場景上的聚類性能都明顯高于經(jīng)典的MECA算法，這主要是因?yàn)镸EKTFCA算法是在MECA算法的基礎(chǔ)上通過改變兩個(gè)平衡因子的大小來調(diào)整對(duì)歷史中心點(diǎn)和歷史隸屬度知識(shí)的學(xué)習(xí)權(quán)重。因?yàn)閷?duì)遷移知識(shí)的有效學(xué)習(xí)，所以保證了MEKTFCA算法的聚類效果始終要比MECA算法的聚類效果好。

3.4 入侵檢測數(shù)據(jù)集實(shí)驗(yàn)結(jié)果和分析

最后一個(gè)實(shí)驗(yàn)使用的是真實(shí)的入侵檢測數(shù)據(jù)集KDDCup99[22]，使用該數(shù)據(jù)集形成一個(gè)目標(biāo)數(shù)據(jù)集樣本量不足的場景，通過將MEKTFCA算法應(yīng)用到該場景，再次驗(yàn)證該算法的有效性。KDDCup99數(shù)據(jù)集來源于美國林肯實(shí)驗(yàn)室建立的一個(gè)模擬網(wǎng)絡(luò)環(huán)境中收集的網(wǎng)絡(luò)連接和審計(jì)數(shù)據(jù)。數(shù)據(jù)集中的數(shù)據(jù)包含不同類型的用戶、各種不同類型的網(wǎng)絡(luò)流量以及各種類型的網(wǎng)絡(luò)攻擊。該數(shù)據(jù)集共收集了9周時(shí)間的數(shù)據(jù)，其中7周時(shí)間的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，約含有5 000 000個(gè)網(wǎng)絡(luò)連接數(shù)據(jù)，另外2周時(shí)間的數(shù)據(jù)作為測試數(shù)據(jù)，約含有2 000 000個(gè)網(wǎng)絡(luò)連接數(shù)據(jù)。整個(gè)數(shù)據(jù)集中的訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集之間有著不同的概率分布，即整個(gè)數(shù)據(jù)集具有一定的相似性，同時(shí)也存在著一定的差異性，滿足知識(shí)遷移應(yīng)用的條件。本文基于KDDCup99數(shù)據(jù)集構(gòu)造的知識(shí)遷移場景只選擇了數(shù)據(jù)集中常見的5種類型(Normal、smurf、Neptune、satan、ipsweep)作為源數(shù)據(jù)集和目標(biāo)數(shù)據(jù)集的類別，選擇每條網(wǎng)絡(luò)連接記錄中的32個(gè)連續(xù)型的特征屬性作為樣本數(shù)據(jù)的維度，源數(shù)據(jù)集的樣本來自原始的訓(xùn)練數(shù)據(jù)集，目標(biāo)數(shù)據(jù)集的樣本來自原始的測試數(shù)據(jù)集。目標(biāo)數(shù)據(jù)集的樣本數(shù)量只占源數(shù)據(jù)集的樣本數(shù)量的10%，且樣本數(shù)量不大，表征的是目標(biāo)數(shù)據(jù)集樣本量不足的情況。具體的入侵檢測遷移場景的數(shù)據(jù)集的樣本個(gè)數(shù)、數(shù)據(jù)的維數(shù)和類別如表7所示。

表7 入侵檢測遷移場景的數(shù)據(jù)集構(gòu)成

MEKTFCA算法和其他6種對(duì)比算法在該入侵檢測數(shù)據(jù)集知識(shí)遷移場景上的執(zhí)行結(jié)果如表8所示。

表8 入侵檢測遷移場景上7種聚類算法性能對(duì)比

觀察表8實(shí)驗(yàn)結(jié)果可以看出，MEKTFCA算法在兩大性能指標(biāo)NMI和RI的均值要明顯高于其他6種對(duì)比算法。與上述兩個(gè)實(shí)驗(yàn)結(jié)果分析的原因相同，MEKTFCA算法由于從源數(shù)據(jù)集中學(xué)習(xí)了有益的歷史中心點(diǎn)和歷史隸屬度知識(shí)，并對(duì)目標(biāo)數(shù)據(jù)集的聚類過程形成有效指導(dǎo)，進(jìn)而使得MEKTFCA算法在目標(biāo)數(shù)據(jù)集樣本量不足的情況下仍能取得比其他6種算法更好的聚類性能。這同時(shí)也進(jìn)一步驗(yàn)證了對(duì)歷史知識(shí)的有效學(xué)習(xí)對(duì)當(dāng)前聚類任務(wù)的有效完成具有促進(jìn)作用。

4 結(jié)束語

由于傳統(tǒng)聚類算法在數(shù)據(jù)樣本量不足或數(shù)據(jù)受污染的情況下，其聚類效果往往不理想甚至失效，本文在經(jīng)典的MECA算法的基礎(chǔ)上通過引入知識(shí)遷移機(jī)制，提出了基于極大熵的知識(shí)遷移模糊聚類算法，即MEKTFCA算法。MEKTFCA算法通過引入的知識(shí)遷移機(jī)制使得在對(duì)數(shù)據(jù)量不足或受污染的目標(biāo)域數(shù)據(jù)進(jìn)行聚類時(shí)能夠有效學(xué)習(xí)源域中有益的歷史中心點(diǎn)和歷史隸屬度知識(shí)，進(jìn)而提高了最終的聚類結(jié)果。通過一組模擬數(shù)據(jù)集和兩組真實(shí)的數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，可以得出本文所提MEKTFCA算法較6種相關(guān)算法在聚類性能上有明顯的優(yōu)越性。本文的創(chuàng)新點(diǎn)主要是，在MECA算法的基礎(chǔ)了提出了一個(gè)新的知識(shí)遷移方法，該方法能有效解決實(shí)際生活中數(shù)據(jù)短缺和有噪聲數(shù)據(jù)場景下的聚類性能問題。此外，本文所提的MEKTFCA算法也存在著局限性，如在不同應(yīng)用場景下兩個(gè)平衡參數(shù)如何進(jìn)行有效確定的問題。這也是我們對(duì)該算法進(jìn)行進(jìn)一步研究的方向。

[1]CARIOU C, CHEHDI K. Unsupervised nearest neighbors clustering with application to hyperspectral images[J]. IEEE journal of selected topics in signal processing, 2015, 9(6): 1105-1116.

[2]ALI A, BOYACI A, BAYNAL K. Data mining application in banking sector with clustering and classification methods[C]//Proceedings of 2015 International Conference on Industrial Engineering and Operations Management. Dubai, UAE, 2015: 1-8.

[3]LI Shuai, ZHOU Xiaofeng, SHI Haibo, et al. An efficient clustering method for medical data applications[C]//Proceedings of 2015 IEEE International Conference on Cyber Technology in Automation, Control, and Intelligent System. Shenyang, China, 2015: 133-138.

[4]LIKAS A, VLASSIS N, VERBEEK J J. The global k-means clustering algorithm[J]. Pattern recognition, 2003, 36(2): 451-461.

[5]BEZDEK J C. Pattern recognition with fuzzy objective function algorithms[M]. New York: Springer, 1981: 43-93.

[6]KARAYIANNIS N B. MECA: maximum entropy clustering algorithm[C]//Proceedings of the 3rd IEEE International Conference on Fuzzy Systems. Orlando, USA, 1994, 1: 630-635.

[7]LI Ruiping, MUKAIDONO M. A maximum-entropy approach to fuzzy clustering[C]//Proceedings of 1995 the 4th IEEE International Conference on Fuzzy System. Yokohama, Japan, 1995, 4: 2227-2232.

[8]ZHANG Tian, RAMAKRISHNAN R, LIVNY M. BIRCH: an efficient data clustering method for very large databases[C]//Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. New York, NY, USA, 1996: 103-114.

[9]GUHA S, RASTOGI R, SHIM K. CURE: an efficient clustering algorithm for large databases[C]//Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data. New York, NY, USA, 1998: 73-84.

[10]ESTER M, KRIEGEL H P, SANDER J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceeding of the Second International Conference on Knowledge Discovery and Data Mining. Portland, Oregon, USA, 1996: 226-231.

[11]ANKERST M, BREUNIG M M, KRIEGEL H P, et al. OPTICS: ordering Points to Identify the Clustering Structure[C]//Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data. Philadelphia, Pennsylvania, USA, 1999: 49-60.

[12]ARIAS-CASTRO E, CHEN Guangliang, LERMAN G. Spectral Clustering based on local linear approximations[J]. Electronic journal of statistics, 2011, 5: 1537-1587.

[13]PAN S J, YANG Qiang. A survey on transfer learning[J]. IEEE transactions on knowledge and data engineering, 2010, 22(10): 1345-1359.

[14]GU Quanquan, ZHOU Jie. Learning the shared subspace for multi-task clustering and transductive transferclassification[C]//Proceedings of Ninth IEEE International Conference on Data Mining. Miami, FL, USA, 2009: 159-168.

[15]DAI Wenyuan, YANG Qiang, XUE Guirong, et al. Self-taught clustering[C]//Proceedings of the 25th International Conference on Machine Learning. New York, NY, USA, 2008: 200-207.

[16]GU Quanquan, ZHOU Jie. Co-clustering on manifolds[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA, 2009: 359-368.

[17]JIANG Wenhao, CHUNG F L. Transfer spectral clustering[M]//FLACH P A, BIE T D, CRISTIANINI N. Machine Learning and Knowledge Discovery in Databases. Berlin Heidelberg: Springer, 2012: 789-803.

[18]JING Liping, NG K M, HUANG J Z. An entropy weighting k-means algorithm for subspace clustering of high-dimensional sparse data[J]. IEEE transactions on knowledge and data engineering, 2007, 19(8): 1026-1041.

[19]LIU Jun, MOHAMMED J, CARTER J, et al. Distance-based clustering of CGH data[J]. Bioinformatics, 2006, 22(16): 1971-1978.

[20]DAI Wenyuan, XUE Guirong, YANG Qiang, et al. Co-clustering based classification for out-of-domain documents[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, NY, USA, 2007: 210-219.

[21]MCCALLUM A K. Bow: a toolkit for statistical language modeling, text retrieval, classification and clustering[EB/OL]. 1996. http://www.cs.cmu.edu/mccallum/bow.

[22]BAY S D, KIBLER D, PAZZANI M J, et al. The UCI KDD archive of large data sets for data mining research and experimentation[J]. ACM SIGKDD explorations newsletter, 2000, 2(2): 81-85.

A maximum entropy-based knowledge transfer fuzzy clustering algorithm

CHEN Aiguo1,2， WANG Shitong1

(1. School of Digital Media, Jiangnan University, Wuxi 214122, China; 2. Department of Computing, Hong Kong Polytechnic University, Kowloon 999077,China)

To address the issue of clustering performance degradation when traditional clustering algorithms are applied to insufficient and/or noisy data, a maximum entropy-based knowledge transfer fuzzy clustering algorithm is proposed. This improves the classical maximum entropy clustering algorithm for target domains by leveraging two kinds of knowledge from the source domain, i.e., historical clustering centers and historical degree of membership, into the objective function proposed for clustering insufficient and/or noisy target data. The effectiveness of the proposed algorithm is demonstrated by experiments on several synthetic and two real datasets.

knowledge transfer; maximum entropy; clustering algorithms; maximum entropy clustering; fuzzy clustering

陳愛國，男，1975年生，博士研究生，主要研究方向?yàn)槟Ｊ阶R(shí)別與機(jī)器學(xué)習(xí)。

王士同，男，1964年生，教授，博士生導(dǎo)師，中國離散數(shù)學(xué)學(xué)會(huì)常務(wù)理事，中國機(jī)器學(xué)習(xí)學(xué)會(huì)常務(wù)理事，主要研究方向?yàn)槿斯ぶ悄?、模式識(shí)別和生物信息。發(fā)表學(xué)術(shù)論文近百篇，其中被SCI、EI檢索50余篇。

2016-02-04.

日期：2017-02-27.

國家自然科學(xué)基金項(xiàng)目(61272210)；江蘇省杰出青年基金項(xiàng)目(BK20140001)；江蘇省自然科學(xué)基金項(xiàng)目(BK20130155).

陳愛國. E-mail：agchen@jiangnan.edu.cn.

10.11992/tis.201602003

http://kns.cnki.net/kcms/detail/23.1538.TP.20170227.1758.006.html

TP274

A

1673-4785(2017)12-0095-09

陳愛國，王士同.基于極大熵的知識(shí)遷移模糊聚類算法[J]. 智能系統(tǒng)學(xué)報(bào)， 2017, 12(1): 95-103.

英文引用格式：CHEN Aiguo，WANG Shitong. A maximum entropy-based knowledge transfer fuzzy clustering algorithm[J]. CAAI transactions on intelligent systems, 2017, 12(1): 95-103.