基于頻繁模式的長尾文本聚類算法①

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

(中南民族大學 計算機科學學院,武漢 430074)

Twitter、微博信息傳遞的形式為短文本.短文本最大的特點是單條短文本只有幾十個字節大小,僅包含幾個到十幾個詞典詞語,很難準確抽取有效的語言特征[1].這類非規范化嚴重的短文本,具有特征信息不足,特征維度高,數據稀疏性高等特點[2,3].因此使用傳統聚類方法對此類短文本聚類時難度較大.

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

1 相關工作

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

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

2 模型描述

2.1 頻繁詞挖掘模型

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

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

定義3.文本集D中第j個文本的每一個頻繁詞對應詞集V構成的詞空間的一個維度,wM表示每一個頻繁詞對應的權重,即詞空間中的每個維度的坐標.

對于特征詞權重的計算方法運用TF-IDF 算法.其中t fij表示在文本dj中的特征詞ti的出現的標準化詞頻,則在文本dj中ti標 準化詞頻(記做t fij)計算如下：

其中,特征詞ti的 標準化逆文檔頻率記做id fi其計算公式如下：

在短文本中不同詞性重要程度不同,代表文本的重要程度不同,我們給每一個特征詞根據詞性賦予一個權值 αi.

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

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

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

2.2 文本表示模型

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

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

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

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

2.3 協同剪枝策略

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

規則一：對于初始樣本文本集D={d1,···,dN},初始聚類后得到初始結果簇Ci,從Ci選取頻繁詞作為主題詞TCi,對于初始數據集中每一個文本dN,若表示dN的頻繁詞集中包含TCi,則從初始樣本文本集D當中剔除掉文本dN,余下文本集作為下一次聚類的輸入文本.

規則二：為了防止短文本中孤立點數據對迭代聚類次數的影響,設置固定最小權重閾值P,多次迭代聚類后,對余下文本計算特征詞權重,若所有特征詞權重中最大的特征詞權重值小于最小權重閾值P,則迭代聚類結束.

3 FIPC 算法

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

圖1 頻繁項協同剪枝迭代聚類算法步驟圖

表1 部分參數含義表

實驗中采用頻繁詞閾值動態變化逐步減小的規律,上一次實驗選取頻繁詞閾值高,代表文本可信度較高,最后將文本分到指定簇的可信度高于其后實驗可信度.使得每一個文本能被唯一指派到唯一的類簇中,避免了類簇重疊問題的生產.

算法描述如下：

4 實驗結果與分析

4.1 數據集

其中,文本分類語料庫搜狗新聞數據集①包含9 個新聞類,共有17 910 個文本；NLPIR 微博英文語料庫②,包含的英文文檔數為23 萬,其中數據集的文本結構為：Id：文章編號、article：正文、discuss：評論數目、insertTime：正文插入時間、origin：來源、person_id：所屬人物的id、time：正文發布時間、transmit：轉發.本文中抽取article 中的文本短內容進行聚類,從搜狗數據集隨機選取部分數據進行實驗,如表2所示.

表2 搜狗數據描述

4.2 聚類評價指標

為了測試FIPC 算法的性能,我們需要選擇聚類評價指標,聚類評價指標分為內部評價指標和外部評價指標.我們采用文本聚類中常用的外部評價標準Fmeasure[21],它經常被用作衡量聚類方法的精度,是一種平面和層次聚類結構都適用的評價標準.Fmeasure 綜合了召回率和準確率2 種評價標準：

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

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

4.3 實驗方案設計

為了驗證本文提出的文本聚類方法,我們選用2 個文本聚類中標準的數據集來進行實驗,對照常用的基于K-means 文本聚類方法和FIC 算法.

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

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

4.4 實驗分析

我們在不同算法上分別對搜狗數據集和NLPIR微博內容語料庫進行試驗,其中對這3 種算法進行10 次實驗取平均值作為最后聚類的精度結果.對于實驗初始值聚類的中心點數K值我們設置為5,實驗過程中對于聚類結果不在我們初始簇類別里的,則設為一個新的簇類.實驗中固定最佳的最小權重閾值P=0.003和頻繁詞篩選閾值Y2=0.020,如圖2所示為相似度余弦閾值Q(Threshold)取不同值時FIPC、FIC 和K-means算法在搜狗數據集下的F-measure 的變化曲線圖.

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

對于本次實驗最后產生的類簇進行主題詞提取,我們選用提取頻繁詞來作為主題詞.統計該類簇中頻繁詞出現頻率,并且按照前10 的頻繁詞來描述主題詞.

圖2 搜狗中文數據集下三種聚類算法的精度

圖3 NLPIR 微博數據集下三種聚類算法的精度

如表3所示,可以看出FIPC 算法較之其他方法在精度上面有明顯的優勢,原因有以下幾點：

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

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

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

經過10 次試驗取平均值作為最后聚類結果得出以下3 個算法在2 個不同數據集中的精確度.

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

表3 算法F-measure 值

5 結語

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

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