基于改進(jìn)相似度與類中心向量的半監(jiān)督短文本聚類算法*

李曉紅，冉宏艷，龔繼恒，顏 麗，馬慧芳

(西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，甘肅 蘭州 730070)

1 引言

隨著社交網(wǎng)絡(luò)的興起，產(chǎn)生了海量的短文本數(shù)據(jù)，如網(wǎng)絡(luò)評論、新聞標(biāo)題、微博等，它們攜帶了豐富的數(shù)據(jù)信息，成為一種新的具有極大挖掘價值的信息資源，對此類數(shù)據(jù)的分類需求也日益凸顯出來。但是，短文本具有內(nèi)容短、信息描述能力弱、主題分散等特點(diǎn)，使得已有的文本聚類方法應(yīng)用于短文本時面臨嚴(yán)重的特征稀疏問題[1]，導(dǎo)致短文本聚類效果并不理想；在實(shí)際聚類任務(wù)及其應(yīng)用中，有時又能獲得一些帶有少量監(jiān)督信息的數(shù)據(jù)，如何有效地利用這些監(jiān)督信息進(jìn)行短文本聚類也成為了研究人員高度關(guān)注的問題。而半監(jiān)督學(xué)習(xí)(Semi-supervised Clustering)[2,3]可在監(jiān)督信息較少的情況下完成對大量未標(biāo)注數(shù)據(jù)的有效組織，并獲得很好的效果。近幾年，半監(jiān)督學(xué)習(xí)方法以其顯著的實(shí)用性價值在機(jī)器學(xué)習(xí)、網(wǎng)絡(luò)信息安全、文本挖掘等領(lǐng)域獲得了廣泛應(yīng)用。

目前,聚類方法與半監(jiān)督學(xué)習(xí)相結(jié)合的算法已有較多研究結(jié)果。根據(jù)監(jiān)督信息的類型將半監(jiān)督聚類分為三類。一類是基于限制的方法，即利用事先提供的數(shù)據(jù)之間“必連”(Must-link)與“不連”(Cannot-link)的成對約束信息實(shí)現(xiàn)聚類，代表性的方法有：Wagstaff等人[4]提出的帶約束的K均值聚類算法COP-Kmeans(ConstrainedK-means clustering)算法，要求每一步劃分都滿足已知的約束對信息，最終得到滿足所有約束的聚類結(jié)果。另一類是基于樣本標(biāo)記信息的方法，如Wang等人[5]提出將深度表示學(xué)習(xí)和K-means聚類結(jié)合設(shè)計(jì)聚類目標(biāo)函數(shù)，并利用少量加標(biāo)數(shù)據(jù)和大量未加標(biāo)數(shù)據(jù)對目標(biāo)函數(shù)進(jìn)行迭代優(yōu)化，從而實(shí)現(xiàn)短文本半監(jiān)督聚類；Zhang等人[6]也利用深度學(xué)習(xí)模型進(jìn)行短文本聚類，但是該方法是將聚類過程和表示過程分離開來進(jìn)行的。更多的則是將上述兩類方法進(jìn)行集成完成聚類，典型的有：趙衛(wèi)中等人[7]提出的一種結(jié)合啟發(fā)式的主動學(xué)習(xí)策略，獲取成對約束集合，改善聚類性能；肖宇等人[8]引入標(biāo)記數(shù)據(jù)或成對約束信息對相似度矩陣進(jìn)行調(diào)整，提出了基于近鄰傳播算法的半監(jiān)督聚類方法，該方法的不足之處是相似度矩陣元素值的調(diào)整比較極端。

本文通過對帶標(biāo)記數(shù)據(jù)所含信息量的分析與學(xué)習(xí)，提出一種依據(jù)詞項(xiàng)類別區(qū)分能力的強(qiáng)弱，按類別抽取并構(gòu)建強(qiáng)類別區(qū)分度詞項(xiàng)集合的策略，并且將其應(yīng)用到短文本相似性度量方法中，使短文本之間相似性的度量更加有效和準(zhǔn)確。同時，提出利用短文本與類中心向量之間的相似程度來決定它們的類別，從而形成基于改進(jìn)相似度和類中心向量的半監(jiān)督短文本聚類算法ISaCV(Improved Similarity and Class-center Vector)，來提高聚類性能，算法結(jié)構(gòu)如圖1所示。

Figure 1 Algorithm structure圖1 算法結(jié)構(gòu)圖

2 背景知識

假設(shè)少量帶類標(biāo)的短文本Dl={(d1,y1),…(di,yi),…,(dl,yl)}，di是m維短文本,yi∈{1,2,…,k}為類標(biāo)簽，大量無類標(biāo)的短文本Du={dl+1,dl+2,…,dl+u}。半監(jiān)督聚類就是利用Dl中的監(jiān)督信息將短文本集合D={d1,…,dn}中的短文本劃分到k個簇C1,…,Cr,…,Ck中。n是短文本總數(shù)量，n=l+u。顯而易見，D=Dl∪Du，且C={C1,…,Cr,…,Ck}。

2.1 期望交叉熵

(1)

(2)

其中，P(t)表示特征t在文本中出現(xiàn)的概率，P(Cr)表示屬于第Cr類的文本在數(shù)據(jù)集中出現(xiàn)的概率，P(Cr|t)表示文本在包含特征t的條件下屬于類別Cr的概率。如果P(Cr|t)較大，并且相應(yīng)的P(Cr)又比較小，則說明特征t和類別Cr強(qiáng)相關(guān)，對分類的影響大。

綜合公式(1)和公式(2)，可推導(dǎo)出更加合理的期望交叉熵的表示形式:

(3)

其中，分子部分衡量了詞項(xiàng)t對類別Cr的指示能力，分母部分衡量了詞項(xiàng)t對短文本集合剩余部分(即C-Cr)的類別指示性。公式(3)有效地避開了那些對所有類都有較好表征能力的詞項(xiàng)的篩選。

2.2 類中心向量

通常，同類數(shù)據(jù)相似度較高，分布緊密。為了計(jì)算文本與類別之間的相似性，本文使用已知類別信息的類中心向量來代表該類。假設(shè)C_cen(r)表示第r類(Cr)的類中心向量，|Cr|表示Cr類所包含短文本的數(shù)目。計(jì)算方法如下所示：

(4)

將公式(4)計(jì)算所得的所有類的類中心向量進(jìn)行合并，構(gòu)成加標(biāo)數(shù)據(jù)集上的類中心向量集合，用Cen來表示。

Cen={C_cen(1),…,C_cen(r),…,C_cen(k)}

(5)

2.3 強(qiáng)類別區(qū)分度

首先，給出強(qiáng)類別區(qū)分度及強(qiáng)類別區(qū)分度詞項(xiàng)的定義。

定義1(強(qiáng)類別區(qū)分度SCD(Strong Category Differentiation))[10]設(shè)C_diff(t,Cr)表示特征詞t對類別Cr的類別區(qū)分度，則有：

C_diff(t,Cr)=tf-idf(t,Cr)*ECE′(t,Cr)

(6)

定義2(強(qiáng)類別區(qū)分度詞項(xiàng)SCDI(Strong Category Differentiation Item)) 對于任意詞項(xiàng)t，如果滿足條件C_diff(t,Cr)≥g，其中g(shù)為篩查閾值，0

由上述定義可知，一個詞項(xiàng)具有強(qiáng)類別區(qū)分能力應(yīng)具備這兩個條件[11]：(1)能夠準(zhǔn)確地表達(dá)短文本的主要內(nèi)容；(2)對特定類別具有較強(qiáng)的指示能力，即有較強(qiáng)的類別傾向性。條件(1)可通過向量空間模型中詞的詞頻-逆文檔頻率tf-idf(term frequency-inverse document frequency)值來衡量該詞對于文本的重要程度,即一個詞在某文本中出現(xiàn)頻率tf越高，而在其他文本中出現(xiàn)的頻率idf越低，則該詞越能表達(dá)文本的主題，相應(yīng)的tf-idf值也越大。條件(2)中詞的類別指示能力可通過公式(3)所示的特征詞的期望交叉熵來度量。ECE′(t,Cr)越大，特征詞t與某個類Cr越相關(guān)，且與其他類別越疏遠(yuǎn)，說明該特征詞t對類Cr的指示能力越強(qiáng)。

3 改進(jìn)的相似性度量方案

3.1 抽取強(qiáng)類別區(qū)分度詞項(xiàng)

通常，在不同類別中詞的指示能力不同。根據(jù)定義2，在Dl中按類別抽取具有強(qiáng)類別區(qū)分能力的特征詞，構(gòu)成強(qiáng)類別區(qū)分度詞項(xiàng)組成的集合，并將其作為先驗(yàn)知識來指導(dǎo)和訓(xùn)練短文本的分類。抽取算法見算法1。

算法1強(qiáng)類別區(qū)分度詞項(xiàng)抽取算法(ESCDI)

輸入：Dl={(d1,y1),…(di,yi),…,(dl,yl)}，閾值g，類別數(shù)k。

輸出：強(qiáng)類別區(qū)分度詞項(xiàng)集合Q={Q1,…,Qr,…,Qk}。

初始化：Q=?，Q1,…,Qk={?},r=1；

對每一個詞項(xiàng)t，重復(fù)執(zhí)行以下操作

forr=1 tokdo

利用公式(3)計(jì)算ECE′(t,Cr)；

按照公式(6)計(jì)算C_diff(t,Cr);

ifC_diff(t,Cr)≥g

thenQr=Qr∪{t};break;

forr=1 tokdo

Q=Q∪Qr；

returnQ;

3.2 改進(jìn)的短文本間的相似性度量方案

相似性度量能否真實(shí)有效地反映文本之間的相似程度，對于短文本聚類的質(zhì)量至關(guān)重要，因此有必要設(shè)計(jì)合理有效的相似性計(jì)算方案。

余弦相似度是通過測量兩個文本向量夾角的余弦值來度量兩個文本之間的相似性的。假設(shè)文本di可表示為向量di=(wi1,wi2,…,wim)，則任意兩個文本di與dj之間的相似性可用下面的公式計(jì)算：

(7)

從強(qiáng)類別區(qū)分度詞項(xiàng)的定義可推知，兩個文檔共同包含強(qiáng)類別區(qū)分度詞集合Qr中的詞項(xiàng)越多，則它們在類別Cr上就越相似[12]。下面給出文本di，dj在某個類別上基于強(qiáng)類別區(qū)分度詞的相似度公式：

(8)

其中，f(di,t)表示強(qiáng)類別區(qū)分度詞t在文檔di中的出現(xiàn)頻率，|Qr|為第r類強(qiáng)類別區(qū)分度詞項(xiàng)集合Qr的大小。則在整個數(shù)據(jù)集上，基于強(qiáng)類別區(qū)分度詞項(xiàng)的相似度定義為k個類別上文檔di與dj之間相似度的最大值，公式如下:

(9)

由于公式(7)中的余弦相似度基于短文本包含的初始特征，忽略了詞與類別之間蘊(yùn)含的聯(lián)系，而這種聯(lián)系卻極有可能有利于實(shí)現(xiàn)文檔的正確劃分。而公式(9)中基于帶強(qiáng)類別區(qū)分度詞項(xiàng)的相似性考慮了詞的類別傾向性，對類別的指示更加明確，恰好可以作為余弦相似度的有效補(bǔ)充。本文綜合考慮以上因素，給出如下所示的更全面有效的相似度計(jì)算方法來度量文本之間的相似性：

sim(di,dj)=asimCOS(di,dj)+

(1-a)simSCD(di,dj)

(10)

其中，α是相似度調(diào)節(jié)因子，取值為α∈[0,1]。

4 算法描述及復(fù)雜度分析

4.1 半監(jiān)督聚類算法流程

本文提出的半監(jiān)督短文本聚類算法就是通過對已知的少量加標(biāo)數(shù)據(jù)的學(xué)習(xí)，獲得對應(yīng)類別的類中心向量。通過改進(jìn)的相似度公式計(jì)算短文本與類中心向量的相似程度，再將每個未加標(biāo)數(shù)據(jù)對象劃分到與其最相似的類中心向量所代表的類中，由此達(dá)到對所有未加標(biāo)數(shù)據(jù)聚類的目的。算法偽代碼如算法2所示。

算法2基于改進(jìn)相似度與類中心向量的半監(jiān)督短文本聚類算法(ISaCV)

輸入：Dl={d1,d2,…,dl}，Du={dl+1,dl+2,…,dl+u}，C={C1,…Cr,…,Ck}，閾值g，類別數(shù)k。

輸出：簇矩陣C。

初始化：Cen=?；

for eachdi∈Du,i=l+1,l+2,…,ndo{

調(diào)用算法1抽取并構(gòu)建強(qiáng)類別區(qū)分度詞項(xiàng)集合：Q=ESCDI(Dl,g,k);

根據(jù)公式(4)和公式(5)構(gòu)造類中心集合：Cen={C_cen(1),…,C_cen(r),…,C_cen(k)}；

Max=0;label=0;

for eachC_cen(r)∈Cen,r=1,…,kdo{/*C_cen(r)為第r類的類中心向量*/

根據(jù)公式(10)計(jì)算sim(di,C_cen(r));

ifsim(di,C_cen(r))>Max

then {Max=sim(di,C_cen(r));label=r};}

將文檔di劃分到簇Clabel中,同時將di加入到加標(biāo)文檔集Dl;

Clabel=Clabel+{di},Dl=Dl+{di};

Du=Du-{di};//將di從未加標(biāo)文檔集中刪除

}

returnC;

4.2 時間復(fù)雜度分析

5 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文所提短文本分類算法的有效性，精心設(shè)計(jì)了三個實(shí)驗(yàn)對算法進(jìn)行驗(yàn)證，并提出相應(yīng)的評價指標(biāo)對實(shí)驗(yàn)結(jié)果進(jìn)行評價。三個實(shí)驗(yàn)分別是：(1)閾值g和參數(shù)α的變化對算法性能的影響；(2)不同的相似度計(jì)算方法對聚類結(jié)果的影響；(3)比較不同聚類算法之間的性能差別。另外，本文采用F1值和純度(Purity)[13]來客觀評價算法的聚類效果，其中，F(xiàn)1值是綜合查全率與查準(zhǔn)率的評估指標(biāo)，對聚類結(jié)果優(yōu)劣的整體區(qū)分能力非常強(qiáng)；純度簡單計(jì)算所有簇中被正確聚類的文本數(shù)與總文本數(shù)的比值，值在0～1之間，值越大表示聚類結(jié)果越好。

5.1 實(shí)驗(yàn)數(shù)據(jù)

本文以新浪網(wǎng)站中各類新聞標(biāo)題為實(shí)驗(yàn)數(shù)據(jù)，利用爬蟲軟件爬取了有代表性的8個類別。實(shí)驗(yàn)數(shù)據(jù)如表1所示。在本實(shí)驗(yàn)中，將每個類別中10%的數(shù)據(jù)加標(biāo)以便提供監(jiān)督信息，其余90%用來評價聚類性能，同時，將這8類數(shù)據(jù)混合在一起形成了待聚類的短文本集合D，共8 442條新聞標(biāo)題。

Table 1 Dataset information of the experiment表1 實(shí)驗(yàn)數(shù)據(jù)集信息

5.2 實(shí)驗(yàn)結(jié)果與分析

5.2.1 閾值g和參數(shù)α對算法性能的影響

圖2給出了強(qiáng)類別區(qū)分度詞項(xiàng)的數(shù)目(注：圖中用|SCDI|表示)的變化趨勢，從實(shí)驗(yàn)結(jié)果來看，隨著g的增大，篩選出來的強(qiáng)類別區(qū)分度詞越來越少，符合強(qiáng)類別區(qū)分度詞項(xiàng)的定義，而且g的變化對強(qiáng)類別區(qū)分度詞項(xiàng)數(shù)目的影響極大。

為了進(jìn)一步測試閾值g與相似度調(diào)節(jié)參數(shù)α對聚類結(jié)果的影響，表2和表3展示了g=0.551和g=0.561，α∈{0.3,0.35,0.4,0.45,0.5,0.55,0.6,0.65,0.7}時，聚類的各個F1值?？梢园l(fā)現(xiàn)在兩張表中，調(diào)節(jié)因子α=0.35的聚類效果均是最好的；而且，當(dāng)確定α=0.35時，g=0.551對應(yīng)的F1值比g=0.561的F1值高，所以g=0.551，α=0.35時本文算法的聚類效果最佳。當(dāng)α<0.35時，相似度計(jì)算公式中余弦相似度所占比重過小，忽略了文本原始特征對分類結(jié)果的重要作用。反

之，當(dāng)α過大時，基于強(qiáng)類別區(qū)分度詞項(xiàng)的相似度所占比重越小，強(qiáng)類別區(qū)分度詞項(xiàng)的類別指示性越弱，導(dǎo)致強(qiáng)類別區(qū)分度詞對分類結(jié)果的影響越小。

圖3給出了強(qiáng)類別區(qū)分度詞項(xiàng)數(shù)目(用|SCDI|表示)對聚類結(jié)果的影響，可以看出，在(253，1142]，算法的F1值隨著強(qiáng)類別區(qū)分度詞項(xiàng)數(shù)目的增大而逐漸增大，強(qiáng)類別區(qū)分度詞項(xiàng)數(shù)目|SCDI|=253時，F(xiàn)1值達(dá)到最大值；但是當(dāng)強(qiáng)類別區(qū)分度詞項(xiàng)數(shù)目|SCDI|>253時，算法的F1值反而逐漸減小。并且|SCDI|=253時，g=0.551，恰好與表2和表3的結(jié)果相吻合。

綜合圖2、表2、表3和圖3，強(qiáng)類別區(qū)分度詞項(xiàng)的數(shù)目隨g的變化波動較大，而且也影響到參數(shù)α的取值，因此對聚類的性能影響較大。為顯示算法的效率與精確性，在后續(xù)實(shí)驗(yàn)中，取g=0.551，α=0.35，強(qiáng)類別區(qū)分度詞項(xiàng)數(shù)目為|SCDI|=253。

Figure 2 Effect of g on |SCDI|圖2 g對強(qiáng)類別區(qū)分度詞項(xiàng)數(shù)目|SCDI|的影響

類別F1α=0.3α=0.35α=0.4α=0.45α=0.5α=0.55α=0.6α=0.65α=0.7環(huán)境63.6970.8270.0268.3467.6067.2367.7465.1764.81計(jì)算機(jī)81.6684.5383.8882.8583.2182.2782.5281.3180.69交通55.5663.5162.0560.5060.1159.8358.4957.6257.14教育55.8563.8363.1060.9660.4859.5257.4458.3557.14經(jīng)濟(jì)59.5965.4264.6664.3063.6763.0460.9061.5261.31軍事56.3964.2463.3662.2360.3460.6157.7659.8759.74醫(yī)藥60.6869.4768.7867.9065.2667.5563.1665.9765.97藝術(shù)65.1171.4670.3768.9670.0768.6767.2868.6766.67

Table 3 Effect of α on F1 when g=0.561表3 g=0.561時，α對F1值的影響

Figure 3 Effect of |SCDI| on F1圖3 強(qiáng)類別區(qū)分度詞項(xiàng)數(shù)目|SCDI|對聚類F1值的影響

5.2.2 相似度對算法性能的影響

圖4是本文ISaCV算法分別利用三種不同的相似度計(jì)算公式得到的聚類結(jié)果。從圖4中可以看出，使用改進(jìn)的相似度計(jì)算公式(對應(yīng)圖4中的(COS+SCD)后在各個類別上都取得了最優(yōu)效果，基于強(qiáng)類別區(qū)分度詞項(xiàng)(SCD)的相似度余弦相似度的效果最差，基于余弦夾角(COS)的相似度效果居中。說明本文提出的將基于強(qiáng)類別區(qū)分度詞項(xiàng)的相似度和基于余弦夾角的相似度進(jìn)行整合是正確的，能較好地處理特征稀疏的短文本之間的相似性的度量。

Figure 4 Comparison of F1 among different similarity calculation methods圖4 不同相似度計(jì)算公式下聚類的F1值

5.2.3 不同聚類算法的性能對比

針對本實(shí)驗(yàn)所提供的數(shù)據(jù)集，分別選擇PCS(Pairwise Constrained Semi-supervised text clustering)[14]、K-means與ISaCV算法進(jìn)行了聚類性能對比。

首先，算法時間復(fù)雜度主要體現(xiàn)為聚類算法收斂所需的時間消耗。實(shí)驗(yàn)所用計(jì)算機(jī)配置：CPU為Corei72.60 GHz，內(nèi)存8 GB，硬盤600 GB，編程語言為Java。在數(shù)據(jù)集規(guī)模不同的情況下，三種聚類算法的時間消耗如圖5所示，PCS算法復(fù)雜度遠(yuǎn)高于ISaCV算法，K-means算法的時間復(fù)雜度略高，ISaCV算法收斂時間最短，時間復(fù)雜度最低。

Figure 5 Comparison of time complexity among the three algorithms圖5 不同聚類算法的時間復(fù)雜度對比

其次，聚類準(zhǔn)確性方面，從圖6和圖7可以看出，不論是F1值還是純度，K-means算法的聚類效果最差，說明短文本特征稀疏及高維的問題對傳統(tǒng)空間向量方法影響很大，而且只采用歐氏距離來判斷相似性，計(jì)算結(jié)果不準(zhǔn)確，從而造成誤分。PCS算法效果稍好一點(diǎn)，但是此方法不能充分利用有價值的監(jiān)督信息，聚類效果無法達(dá)到最好。ISaCV算法的聚類效果最好，因ISaCV算法逐步擴(kuò)展加標(biāo)數(shù)據(jù)，并及時更新類別信息，隨著監(jiān)督信息量的增加，使得聚類準(zhǔn)確率逐步提升，得到了較好的聚類效果。尤其是“計(jì)算機(jī)”類的聚類效果突出，主要原因在于該類別的詞匯與其他類別詞匯混淆較少，強(qiáng)類別區(qū)分度詞項(xiàng)抽取準(zhǔn)確，詞項(xiàng)的類別指示能力較強(qiáng)，使得聚類效果提升明顯。綜合兩個指標(biāo)的評價結(jié)果，ISaCV算法都有著較好的聚類結(jié)果，同時也表明了監(jiān)督信息對聚類性能的影響。

Figure 6 Comparison of F1 among the three clustering algorithms圖6 不同聚類算法的F1值

Figure 7 Comparison of purity among the three clustering algorithms圖7 不同聚類算法的純度

6 結(jié)束語

本文利用少量帶類標(biāo)的數(shù)據(jù)提取具有強(qiáng)類別區(qū)分能力的特征詞并構(gòu)成集合，計(jì)算得到基于強(qiáng)類別區(qū)分度詞的相似度，并進(jìn)一步將其與基于余弦夾角的相似度進(jìn)行融合，設(shè)計(jì)了更有效合理的相似度度量公式，從而達(dá)到短文本之間相似性的準(zhǔn)確計(jì)算。再通過計(jì)算已知類別類中心向量與未加標(biāo)數(shù)據(jù)之間相似度的策略，來實(shí)現(xiàn)對未加標(biāo)文本劃分類別的目的。實(shí)驗(yàn)結(jié)果顯示，本文方法能有效地根據(jù)短文本數(shù)據(jù)的特點(diǎn)利用半監(jiān)督信息提高聚類效果。未來工作的重點(diǎn)是考慮從語義層面對短文本進(jìn)行合理有效的擴(kuò)展，同時考慮能否將類別信息轉(zhuǎn)化為約束信息，從而將聚類問題轉(zhuǎn)化為優(yōu)化問題，最后是對參數(shù)的合理擇優(yōu)等問題進(jìn)行進(jìn)一步嘗試來提高算法性能。