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

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

1 引言

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

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

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

Figure 1 Algorithm structure圖1 算法結構圖

2 背景知識

假設少量帶類標的短文本Dl={(d1,y1),…(di,yi),…,(dl,yl)}，di是m維短文本,yi∈{1,2,…,k}為類標簽，大量無類標的短文本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)較大，并且相應的P(Cr)又比較小，則說明特征t和類別Cr強相關，對分類的影響大。

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

(3)

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

2.2 類中心向量

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

(4)

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

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

(5)

2.3 強類別區(qū)分度

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

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

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

(6)

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

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

3 改進的相似性度量方案

3.1 抽取強類別區(qū)分度詞項

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

算法1強類別區(qū)分度詞項抽取算法(ESCDI)

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

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

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

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

forr=1 tokdo

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

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

ifC_diff(t,Cr)≥g

thenQr=Qr∪{t};break;

forr=1 tokdo

Q=Q∪Qr；

returnQ;

3.2 改進的短文本間的相似性度量方案

相似性度量能否真實有效地反映文本之間的相似程度，對于短文本聚類的質量至關重要，因此有必要設計合理有效的相似性計算方案。

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

(7)

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

(8)

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

(9)

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

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

(1-a)simSCD(di,dj)

(10)

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

4 算法描述及復雜度分析

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

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

算法2基于改進相似度與類中心向量的半監(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{

調用算法1抽取并構建強類別區(qū)分度詞項集合：Q=ESCDI(Dl,g,k);

根據(jù)公式(4)和公式(5)構造類中心集合：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)計算sim(di,C_cen(r));

ifsim(di,C_cen(r))>Max

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

將文檔di劃分到簇Clabel中,同時將di加入到加標文檔集Dl;

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

Du=Du-{di};//將di從未加標文檔集中刪除

}

returnC;

4.2 時間復雜度分析

5 實驗結果與分析

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

5.1 實驗數(shù)據(jù)

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

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

5.2 實驗結果與分析

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

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

為了進一步測試閾值g與相似度調節(jié)參數(shù)α對聚類結果的影響，表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)在兩張表中，調節(jié)因子α=0.35的聚類效果均是最好的；而且，當確定α=0.35時，g=0.551對應的F1值比g=0.561的F1值高，所以g=0.551，α=0.35時本文算法的聚類效果最佳。當α<0.35時，相似度計算公式中余弦相似度所占比重過小，忽略了文本原始特征對分類結果的重要作用。反

之，當α過大時，基于強類別區(qū)分度詞項的相似度所占比重越小，強類別區(qū)分度詞項的類別指示性越弱，導致強類別區(qū)分度詞對分類結果的影響越小。

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

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

Figure 2 Effect of g on |SCDI|圖2 g對強類別區(qū)分度詞項數(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計算機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)濟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藝術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 強類別區(qū)分度詞項數(shù)目|SCDI|對聚類F1值的影響

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

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

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

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

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

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

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

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

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