宋中山,張廣凱,尹 帆,帖 軍

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院,武漢 430074)

Twitter、微博信息傳遞的形式為短文本.短文本最大的特點(diǎn)是單條短文本只有幾十個(gè)字節(jié)大小,僅包含幾個(gè)到十幾個(gè)詞典詞語,很難準(zhǔn)確抽取有效的語言特征[1].這類非規(guī)范化嚴(yán)重的短文本,具有特征信息不足,特征維度高,數(shù)據(jù)稀疏性高等特點(diǎn)[2,3].因此使用傳統(tǒng)聚類方法對(duì)此類短文本聚類時(shí)難度較大.

“長(zhǎng)尾現(xiàn)象”普遍存在口語化的短文本集中.大約40%的短文本信息集中分布在大約20%的空間中,也就是“頭”的部分,稱之為“熱點(diǎn)”,大約60%的信息分布在大約80%的空間中,即“尾”的部分,將所有非熱點(diǎn)信息累加起來就會(huì)形成一個(gè)比主流信息量還要大的信息[4].從這些“尾”部的信息中收集到有用的信息對(duì)于政府或者一些投資商了解社會(huì)異常以及人們?nèi)粘?dòng)向有很大的幫助[5,6].傳統(tǒng)聚類算法,主要通過一次篩選后得到頻繁詞來表征短文本,因“長(zhǎng)尾”部分短文本的特征詞權(quán)重很小,達(dá)不到傳統(tǒng)算法中篩選閾值,所以在挖掘頻繁詞時(shí),會(huì)忽略掉小類別短文本的特征詞,造成小類別短文本的特征信息不足,在聚類結(jié)果中小類別短文本會(huì)被劃分到不正確的簇里面,導(dǎo)致聚類的精確度降低,因此本文圍繞提高“長(zhǎng)尾”部分短文本聚類精確度的問題,提出一種頻繁項(xiàng)協(xié)同剪枝迭代聚類算法(FIPC),首先提取頻繁詞構(gòu)建頻繁詞-文本矩陣,接著使用K 中心點(diǎn)算法對(duì)文本進(jìn)行初始聚類,然后根據(jù)協(xié)同剪枝策略對(duì)原始數(shù)據(jù)集進(jìn)行剪枝得到下一次迭代聚類的文本集,重復(fù)進(jìn)行上敘過程,直到得到對(duì)小類別短文本聚類的結(jié)果簇,從而實(shí)現(xiàn)“長(zhǎng)尾”文本的聚類.實(shí)驗(yàn)結(jié)果證明,與傳統(tǒng)的K-means 聚類和FIC 算法相比,該算法能夠有效的避免類簇重疊問題,提高了“長(zhǎng)尾”短文本聚類精確度.

1 相關(guān)工作

目前國(guó)內(nèi)外的眾多學(xué)者已經(jīng)對(duì)于短文本聚類方面技術(shù)有了相關(guān)研究.基于頻繁模式的文本聚類算法,該類算法通過以頻繁模式的方式,表征文本進(jìn)行聚類[7-9].如：栗偉等人提出了ACT 算法[10],該算法將挖掘頻繁項(xiàng)來表征文本,以頻繁項(xiàng)確定文本簇的中心點(diǎn),對(duì)文本進(jìn)行完全聚類.該算法所面對(duì)的數(shù)據(jù)集為疾病的病例數(shù)據(jù),此類數(shù)據(jù)格式規(guī)范且種類少.但是該算法在進(jìn)行日常口語化文本信息提取時(shí),算法效率較低.彭敏[11]等人提出了一種基于頻繁項(xiàng)集的短文本聚類與主題抽取STCTE 框架,該框架首先對(duì)于海量短文本數(shù)據(jù)進(jìn)行打分?jǐn)?shù)篩選,留下得分高類別大的文本,結(jié)合譜聚類算法CSA_SC 算法與主題抽取模型,實(shí)現(xiàn)短文本聚類效果.該算法在處理社交網(wǎng)絡(luò)中的短文本信息時(shí),前期處理篩掉非頻繁的短文本,造成了大量的信息缺失,對(duì)一些小的類別文本沒有進(jìn)行聚類,精度不高,效果不佳.基于子樹匹配的文本聚類算法,該類算法利用文本生成元數(shù)據(jù)特征向量,設(shè)置分層權(quán)重結(jié)合語義之間關(guān)系構(gòu)建文本子樹,通過子樹之間的相似度來進(jìn)行文本匹配[12,13].該算法不能解決多義詞的問題,這對(duì)于日常短文本的聚類效果不佳.基于語料庫(kù)的短文本聚類算法,該類算法在不借助外部文本信息的情況下,引入共軛定義來表征主題詞和單詞結(jié)構(gòu),提出文本虛擬生產(chǎn)過程,達(dá)到解決文本稀疏性和聚類問題的目的.如：Zheng CT,Liu C,Wong HS[14]提出的基于主題擴(kuò)展的文本聚類算法,結(jié)合特征空間及語義空間達(dá)到提高短文本聚類精度的效果,但該算法在對(duì)于具有“長(zhǎng)尾現(xiàn)象”的文本數(shù)據(jù)聚類時(shí)效果不佳.基于主題模型的文本聚類算法,該類算法主要結(jié)合主題模型與傳統(tǒng)算法,來對(duì)海量短文本進(jìn)行聚類.如：Hung PJ,Hsu PY,Cheng MS[15]的動(dòng)態(tài)主題的Web 文本聚類,結(jié)合EM 算法與動(dòng)態(tài)主題為文本聚類特征對(duì)Web 文本進(jìn)行聚類；張雪松和賈彩燕提出的FIC 算法,首先挖掘頻繁詞集表示文本,構(gòu)建文本網(wǎng)絡(luò),運(yùn)用社區(qū)劃分算法對(duì)網(wǎng)絡(luò)進(jìn)行大范圍劃分,最后提取主題詞,進(jìn)行類簇劃分[16].該算法在處理“長(zhǎng)尾現(xiàn)象”的短文本數(shù)據(jù)時(shí),聚類精度不高.針對(duì)此類問題,彭澤映等人[17]在對(duì)實(shí)際應(yīng)用中短文本信息的“長(zhǎng)尾現(xiàn)象”進(jìn)行分析后,提出不完全聚類的思想,即在聚類的過程中集中資源處理大類別的短文本,減少資源在孤立點(diǎn)聚類上的浪費(fèi),盡量減少小類別的短文本的聚類時(shí)間,增加大類別的短文本聚類機(jī)會(huì).但該算法在處理社交網(wǎng)絡(luò)口語化,小類別文本數(shù)繁多的應(yīng)用中,容易丟失文本信息,精確度較低.

針對(duì)以上短文本聚類面臨的特征高維,小類別信息丟失的問題,本文提出頻繁項(xiàng)協(xié)同剪枝迭代聚類算法(FIPC),通過挖掘頻繁詞集,根據(jù)相關(guān)文本相似性實(shí)現(xiàn)文本聚類,得到部分聚類結(jié)果,根據(jù)協(xié)同剪枝策略,生成主題詞檢索并且剔除相關(guān)短文本,迭代進(jìn)行此聚類過程,進(jìn)而實(shí)現(xiàn)短文本聚類.具體來說主要有以下2 點(diǎn)貢獻(xiàn)：(1)采用逐步降低頻繁詞的篩選閾值,讓權(quán)重較小的頻繁詞被選中來表示短文本的特征,解決了傳統(tǒng)聚類中小類別信息被忽略的問題,同時(shí)避免了類簇重疊問題的出現(xiàn)；(2)充分利用類簇主題詞與文本之間關(guān)系,設(shè)計(jì)協(xié)同剪枝策略,減小迭代聚類中每一輪數(shù)據(jù)集,減小了每輪聚類的時(shí)間消耗.

2 模型描述

2.1 頻繁詞挖掘模型

定義1.文本數(shù)據(jù)集D由多個(gè)文本組成 D ={d1,d2,···,dN},N表示文本集的大小總數(shù),以及文本切詞之后得到的詞集V,V={t1,t2,···,tn},n表示詞匯表的大小.

定義2.特征詞：每一個(gè)文檔dN經(jīng)切詞之后得到詞集V={t1,t2,···,tn} ,詞集中的每一個(gè)詞,稱為特征詞tn.

定義3.文本集D中第j個(gè)文本的每一個(gè)頻繁詞對(duì)應(yīng)詞集V構(gòu)成的詞空間的一個(gè)維度,wM表示每一個(gè)頻繁詞對(duì)應(yīng)的權(quán)重,即詞空間中的每個(gè)維度的坐標(biāo).

對(duì)于特征詞權(quán)重的計(jì)算方法運(yùn)用TF-IDF 算法.其中t fij表示在文本dj中的特征詞ti的出現(xiàn)的標(biāo)準(zhǔn)化詞頻,則在文本dj中ti標(biāo) 準(zhǔn)化詞頻(記做t fij)計(jì)算如下：

其中,特征詞ti的 標(biāo)準(zhǔn)化逆文檔頻率記做id fi其計(jì)算公式如下：

在短文本中不同詞性重要程度不同,代表文本的重要程度不同,我們給每一個(gè)特征詞根據(jù)詞性賦予一個(gè)權(quán)值 αi.

最后文本dj中每一個(gè)特征詞的最終權(quán)重wi為詞頻因子(t fij)與逆文檔頻率(id fi)與詞性權(quán)重αi三者的乘積.如式(3)所示：

由式(3)所示特征詞的權(quán)重由三方面的因素來決定：第一方面因素為該特征詞在這個(gè)短文本中詞頻因子；第二方面為該特征詞在文本集里面的逆文檔頻率因子；第三方面為特征詞的詞性因子[18].

定義4.頻繁詞集：從詞集V挖掘權(quán)重大于頻繁詞閾值Y2的頻繁詞fk組成的集合Fi={fi,f2,···,fk}.

2.2 文本表示模型

向量空間模型(Vector Space Model,VSM)是最常用的文本表示模型[19].VSM 模型采用特征詞表征文本構(gòu)建矩陣,這對(duì)于矩陣的維度比較高,本文運(yùn)用頻繁詞表征文本,選前K個(gè)頻繁詞構(gòu)建頻繁詞-文本矩陣L,L為0-1 矩陣,其中表示矩陣L中文本dj對(duì)于頻繁詞fi的值,若文本dj中含有頻繁詞fi,則否則的表現(xiàn)形式為：

選用前K個(gè)頻繁詞來構(gòu)建矩陣L,而不選擇所有的特征詞,這樣降低了矩陣的維度,同時(shí)也解決了文本稀疏性問題.

文本向量化后的對(duì)文本進(jìn)行相似度計(jì)算,傳統(tǒng)的相似度計(jì)算的方法有幾種,例如余弦相似度和歐氏距離.本文采用余弦相似度來度量：其中,分別代表文檔向量化后的向量,設(shè)定相似度余弦閾值Q(Threshold),若兩者相似度余弦閾值大于Q(Threshold),則將兩者歸于為1 個(gè)類簇.

對(duì)于所有文本運(yùn)用K 中心點(diǎn)算法對(duì)其兩兩進(jìn)行相似度計(jì)算如式(6)所示,將相似的文檔來歸于到一個(gè)類簇中.

2.3 協(xié)同剪枝策略

如何利用主題詞與短文本之間的關(guān)系,這在提高“長(zhǎng)尾”文本聚類的精確度方面有重要的作用.對(duì)于上一次聚類結(jié)果簇,提取主題詞TCi.根據(jù)以下規(guī)則進(jìn)行剪枝策略以及迭代聚類.

規(guī)則一：對(duì)于初始樣本文本集D={d1,···,dN},初始聚類后得到初始結(jié)果簇Ci,從Ci選取頻繁詞作為主題詞TCi,對(duì)于初始數(shù)據(jù)集中每一個(gè)文本dN,若表示dN的頻繁詞集中包含TCi,則從初始樣本文本集D當(dāng)中剔除掉文本dN,余下文本集作為下一次聚類的輸入文本.

規(guī)則二：為了防止短文本中孤立點(diǎn)數(shù)據(jù)對(duì)迭代聚類次數(shù)的影響,設(shè)置固定最小權(quán)重閾值P,多次迭代聚類后,對(duì)余下文本計(jì)算特征詞權(quán)重,若所有特征詞權(quán)重中最大的特征詞權(quán)重值小于最小權(quán)重閾值P,則迭代聚類結(jié)束.

3 FIPC 算法

FIPC (Frequent Itemsets collaborative Pruning iteration Clustering framework)頻繁項(xiàng)協(xié)同剪枝迭代聚類算法步驟圖如圖1所示,該算法首先對(duì)初始樣本文本集D切詞得到具有詞性標(biāo)注的特征詞,從其中提取頻繁詞,然后構(gòu)建頻繁詞-文本向量矩陣,在文本向量化后利用K 中心點(diǎn)算法進(jìn)行聚類[20],初始聚類結(jié)束得到部分聚類結(jié)果簇,提取每一個(gè)簇中的主題詞,根據(jù)協(xié)同剪枝策略對(duì)初始樣本文本集進(jìn)行剪枝.同時(shí)減小頻繁詞閾值Y2,再對(duì)余下數(shù)據(jù)集迭代進(jìn)行第二次、第三次等多次聚類過程,經(jīng)過多次聚類之后,若余下文本特征詞滿足規(guī)則二,則迭代聚類結(jié)束,最后得到聚類結(jié)果簇{Ci}.算法中部分參數(shù)如表1所示.

圖1 頻繁項(xiàng)協(xié)同剪枝迭代聚類算法步驟圖

表1 部分參數(shù)含義表

實(shí)驗(yàn)中采用頻繁詞閾值動(dòng)態(tài)變化逐步減小的規(guī)律,上一次實(shí)驗(yàn)選取頻繁詞閾值高,代表文本可信度較高,最后將文本分到指定簇的可信度高于其后實(shí)驗(yàn)可信度.使得每一個(gè)文本能被唯一指派到唯一的類簇中,避免了類簇重疊問題的生產(chǎn).

算法描述如下：

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

4.1 數(shù)據(jù)集

其中,文本分類語料庫(kù)搜狗新聞數(shù)據(jù)集①包含9 個(gè)新聞?lì)?共有17 910 個(gè)文本；NLPIR 微博英文語料庫(kù)②,包含的英文文檔數(shù)為23 萬,其中數(shù)據(jù)集的文本結(jié)構(gòu)為：Id：文章編號(hào)、article：正文、discuss：評(píng)論數(shù)目、insertTime：正文插入時(shí)間、origin：來源、person_id：所屬人物的id、time：正文發(fā)布時(shí)間、transmit：轉(zhuǎn)發(fā).本文中抽取article 中的文本短內(nèi)容進(jìn)行聚類,從搜狗數(shù)據(jù)集隨機(jī)選取部分?jǐn)?shù)據(jù)進(jìn)行實(shí)驗(yàn),如表2所示.

表2 搜狗數(shù)據(jù)描述

4.2 聚類評(píng)價(jià)指標(biāo)

為了測(cè)試FIPC 算法的性能,我們需要選擇聚類評(píng)價(jià)指標(biāo),聚類評(píng)價(jià)指標(biāo)分為內(nèi)部評(píng)價(jià)指標(biāo)和外部評(píng)價(jià)指標(biāo).我們采用文本聚類中常用的外部評(píng)價(jià)標(biāo)準(zhǔn)Fmeasure[21],它經(jīng)常被用作衡量聚類方法的精度,是一種平面和層次聚類結(jié)構(gòu)都適用的評(píng)價(jià)標(biāo)準(zhǔn).Fmeasure 綜合了召回率和準(zhǔn)確率2 種評(píng)價(jià)標(biāo)準(zhǔn)：

其中,ni j表示簇Cj中 屬于類Kj的文本數(shù),由召回率和準(zhǔn)確率可得到表示簇Cj描 述類Kj的能力計(jì)算：

聚類的總體F-measure 值取值范圍在[0,1],值越大表示聚類效果越好.

4.3 實(shí)驗(yàn)方案設(shè)計(jì)

為了驗(yàn)證本文提出的文本聚類方法,我們選用2 個(gè)文本聚類中標(biāo)準(zhǔn)的數(shù)據(jù)集來進(jìn)行實(shí)驗(yàn),對(duì)照常用的基于K-means 文本聚類方法和FIC 算法.

對(duì)于原始數(shù)據(jù)集首先利用python 中的結(jié)巴分詞(基于機(jī)器學(xué)習(xí)的中文自然語言文本處理的開發(fā)工具)進(jìn)行切詞,樣本文本經(jīng)過切詞、剔除停用詞以及詞性標(biāo)注操作之后,得到具有詞性標(biāo)注的特征詞ti,但仍然存在這大量與主題無關(guān)或者無意義的詞語.因此在本文中需要選取閾值來篩掉不相關(guān)和無意義的詞語.

本文中有3 處參數(shù)需要涉及到閾值的選取,包括挖掘頻繁詞的頻繁詞閾值Y2、計(jì)算余弦相似度時(shí)余弦閾值Q(Threshold)、實(shí)驗(yàn)結(jié)束時(shí)最小權(quán)重閾值P.本文通過手動(dòng)調(diào)參,多次試驗(yàn)的方式,來獲得聚類最佳效果的參數(shù)閾值,其中在頻繁詞減小的過程中,要保證每次表征文本的頻繁詞數(shù)不少于5 個(gè),選擇最后實(shí)驗(yàn)結(jié)束的最小權(quán)重閾值P時(shí),最少保證詞頻最大的頻繁詞所出現(xiàn)文本的頻數(shù)不小于2.對(duì)于本次實(shí)驗(yàn),在英文數(shù)據(jù)集中,選取相似度余弦閾值步長(zhǎng)為0.005,由于中文數(shù)據(jù)中的停用詞較多以及每個(gè)文檔詞數(shù)量較少,因此采用與英文數(shù)據(jù)不同的閾值選擇方式,采用0.01 的步長(zhǎng),并且以對(duì)聚類精度影響最高的相似性余弦閾值進(jìn)行實(shí)驗(yàn).

4.4 實(shí)驗(yàn)分析

我們?cè)诓煌惴ㄉ戏謩e對(duì)搜狗數(shù)據(jù)集和NLPIR微博內(nèi)容語料庫(kù)進(jìn)行試驗(yàn),其中對(duì)這3 種算法進(jìn)行10 次實(shí)驗(yàn)取平均值作為最后聚類的精度結(jié)果.對(duì)于實(shí)驗(yàn)初始值聚類的中心點(diǎn)數(shù)K值我們?cè)O(shè)置為5,實(shí)驗(yàn)過程中對(duì)于聚類結(jié)果不在我們初始簇類別里的,則設(shè)為一個(gè)新的簇類.實(shí)驗(yàn)中固定最佳的最小權(quán)重閾值P=0.003和頻繁詞篩選閾值Y2=0.020,如圖2所示為相似度余弦閾值Q(Threshold)取不同值時(shí)FIPC、FIC 和K-means算法在搜狗數(shù)據(jù)集下的F-measure 的變化曲線圖.

圖3為3 種算法在固定最佳的最小權(quán)重閾值P=0.003和頻繁詞篩選閾值Y2=0.020之后取不同相似度余弦閾值Q(Threshold)時(shí),在NLPIR 微博英文料庫(kù)上的Fmeasure 變化曲線圖.

對(duì)于本次實(shí)驗(yàn)最后產(chǎn)生的類簇進(jìn)行主題詞提取,我們選用提取頻繁詞來作為主題詞.統(tǒng)計(jì)該類簇中頻繁詞出現(xiàn)頻率,并且按照前10 的頻繁詞來描述主題詞.

圖2 搜狗中文數(shù)據(jù)集下三種聚類算法的精度

圖3 NLPIR 微博數(shù)據(jù)集下三種聚類算法的精度

如表3所示,可以看出FIPC 算法較之其他方法在精度上面有明顯的優(yōu)勢(shì),原因有以下幾點(diǎn)：

(1)在數(shù)據(jù)處理方面,并不只是分詞和去掉停用詞,為了保留具有代表性的詞匯,采用TF-IDF 值結(jié)合詞性來篩選特征詞.

(2)運(yùn)用頻繁詞來構(gòu)建文本表示模型,文本集中挖掘出頻繁詞,有效的降低了文本表示矩陣的維度.

(3)本文采用協(xié)同剪枝的策略,結(jié)合主題詞與文本矩陣進(jìn)行協(xié)同剪枝,縮小了數(shù)據(jù)集的大小.

經(jīng)過10 次試驗(yàn)取平均值作為最后聚類結(jié)果得出以下3 個(gè)算法在2 個(gè)不同數(shù)據(jù)集中的精確度.

由表3中可以看出FIPC 算法聚類出來的Fmeasure 值相較于其他2 個(gè)算法略大,因此體現(xiàn)出該算法的聚類精確度最好.

表3 算法F-measure 值

5 結(jié)語

本文針對(duì)短文本“長(zhǎng)尾現(xiàn)象”這一特點(diǎn),提出一種新的文本聚類算法FIPC,該算法基于頻繁詞表征文本,解決了高稀疏性的問題,將經(jīng)典聚類算法K 中心點(diǎn)應(yīng)用到迭代聚類的框架中,實(shí)現(xiàn)對(duì)小類別文本進(jìn)行聚類,更精確的挖掘小類別短文本的信息,提升了聚類的準(zhǔn)確性.

本文中采用的K 中心點(diǎn)算法結(jié)合協(xié)同剪枝策略,但是K 中心點(diǎn)算法一直存在一個(gè)問題：如何選取合適的初始中心點(diǎn),本文中采用人工隨機(jī)選取初始中心點(diǎn)的方法,若能在選取合適的初始中心點(diǎn)對(duì)于實(shí)驗(yàn)結(jié)果的精確度能有更大的提高.因此在下一步工作中如何有效快捷的選取合適的初始中心點(diǎn)來進(jìn)行聚類是我們所要思考的.