張 儀，陳 國，張再躍

(江蘇科技大學(xué) 計算機科學(xué)與工程學(xué)院,江蘇 鎮(zhèn)江 212003)

可增量的用戶短文本聚類方法研究

張 儀，陳 國，張再躍

(江蘇科技大學(xué) 計算機科學(xué)與工程學(xué)院,江蘇 鎮(zhèn)江 212003)

隨著大數(shù)據(jù)時代的到來，用戶短文本數(shù)據(jù)呈爆炸性增長，充分利用聚類分析技術(shù)獲取短文本中的有用信息顯得十分重要。聚類分析作為一種重要的知識發(fā)現(xiàn)手段，是將對象按其特征的相似程度進行歸類的過程。為此，提出了一種可增量面向用戶短文本聚類方法。該方法包括離線聚類和在線聚類兩大類，前者在短文本預(yù)處理的基礎(chǔ)上，利用無關(guān)語詞典對短文本中的無關(guān)語進行識別和清理，再利用詞類詞典對短文本進行語義歸一化；同時還提出了基于多特征融合的相似度計算方法，以實現(xiàn)對文本的相關(guān)性聚類。后者則以離線聚類結(jié)果為特征，對在線文本進行在線聚類操作，將離線聚類結(jié)果和在線聚類結(jié)果進行合并，以生成最終的聚類結(jié)果。為驗證該方法的有效性與可行性，與基于特征向量的相似度方法進行了對比實驗。實驗結(jié)果表明，該方法的聚類召回率可達73%，聚類精度達到87.7%，F(xiàn)值為79.6%，均優(yōu)于基于特征向量的方法。

短文本；語義歸一化；離線聚類；在線聚類

1 概 述

隨著互聯(lián)網(wǎng)的快速發(fā)展和大范圍普及，文本信息已成為一種重要的信息來源，如電子郵件、新聞、網(wǎng)頁等，但是文本自身所具備的無序性、多樣性和廣泛性，使得從大量的文本中獲取有用的知識成為一個難題，因此文本挖掘應(yīng)運而生。文本挖掘是指從大量的文本數(shù)據(jù)中挖掘出潛在的、事先未知的、對用戶有用的知識的過程[1]，主要方法有：關(guān)聯(lián)分析、總結(jié)、分類、聚類，其中文本聚類[2]是文本挖掘最常用的方法。文本挖掘是數(shù)據(jù)挖掘[3-4]應(yīng)用的一個具體領(lǐng)域，二者既有聯(lián)系又有區(qū)別。文本挖掘是通過處理非結(jié)構(gòu)化的文檔內(nèi)容，發(fā)現(xiàn)文檔數(shù)據(jù)集中潛在的關(guān)系和知識，從而為用戶提供有用的信息。文本聚類的效果如何主要取決于文本表示模型和文本聚類方法。

聚類分析[5]是將相似的對象放到不同的組中，使每個組中的成員對象擁有一些相似的屬性或特征，這體現(xiàn)了“物以類聚”的自然規(guī)律。文本聚類則是根據(jù)文檔內(nèi)容的相似度將文檔分為若干個簇，使得每個簇中的文檔內(nèi)容的相似度盡可能大，不同簇中的文檔相似度盡可能小。

文本表示模型就是為半結(jié)構(gòu)化或非結(jié)構(gòu)化的文本定義一個形式化的數(shù)學(xué)模型[6],用這個模型有效地表示文本。其中最具代表性的有向量空間模型[6]、概率模型[7]、概念鏈模型[8]、圖模型[9]等。向量空間模型(Vector Space Model,VSM)是近年來應(yīng)用較多且效果較好的方法之一[9]，其最大優(yōu)點在于模型簡單，可直接應(yīng)用于聚類算法。文本聚類方法有很多，比如以貝葉斯理論為基礎(chǔ)，用概率的方法進行聚類[10]，也可以將文本表示成特征向量，用距離[11]表示文本的相似度進行聚類。

目前，國內(nèi)外對文本聚類的研究主要集中在文本特征的提取、聚類算法的提出、對聚類結(jié)果的評價和聚類結(jié)果的表示。文本聚類領(lǐng)域的研究在國外起步較早且發(fā)展較快，現(xiàn)在已經(jīng)有很多研究成果應(yīng)用在文本挖掘、搜索系統(tǒng)和郵件過濾等領(lǐng)域。文本聚類可以自動提取多個文檔主題信息，消除冗余，從而自動生成一篇簡明扼要的摘要，其中哥倫比亞大學(xué)開發(fā)的多文檔自動文摘系統(tǒng)Newsblaster[12]做得比較出色。例如IBM的Intelligent Miner for Text允許企業(yè)從文本信息中獲取有價值的客戶信息，它擴展了IBM的數(shù)據(jù)采集功能，可以從文本文檔和數(shù)據(jù)源獲取信息，其功能包括識別文檔語言，建立姓名、用語或其他詞匯的詞典，提取文本的涵義，將類似的文本分組，并根據(jù)內(nèi)容將文檔歸類。

相較于國外，國內(nèi)文本聚類研究起步則較晚些，研究主要集中在科研院所和高等院校，并且取得了不錯的成績。中國科學(xué)院計算技術(shù)研究所對文本挖掘和知識檢索的研究做出了巨大貢獻，提出的基于HMM模型[13]的中文分詞算法已經(jīng)應(yīng)用到多個實際系統(tǒng)。另外，鐘國祥和王剛[14]提出了利用本體描述文本，根據(jù)本體件的語義相似度衡量文本間的相似度，算法稱為TCBO(Text Clustering Based on Ontology)；李曉光等[15]提出了一種基于信息論的潛在概念獲取與文本聚類方法。

在問答系統(tǒng)等自然語言理解應(yīng)用系統(tǒng)中，用戶大量的咨詢文本一般都是簡單語句，或者是由簡單語句構(gòu)成的復(fù)合句，稱為用戶短文本。與傳統(tǒng)的文本聚類相比，短文本聚類中的挑戰(zhàn)在于：含有的特征詞較少，容易造成描述概念信號弱、特征稀疏等問題[16]，從而影響短文本的相似度計算；由于自然語言具有高度的靈活性，特別是用戶短文本中都是口語化的表示，其中包含了很多與短文本要表達的本質(zhì)含義無關(guān)的詞語，這會對短文本的語義產(chǎn)生干擾，影響短文本的相似度計算；由于語言表達的多樣性，同樣的事物可以使用不同的詞語表示，短文本語料中有大量意義相近，但是詞性不同的詞語或短語，這也會影響短文本的語義相似度計算，從而影響聚類的準確性。

為了解決以上短文本聚類中存在的問題，提出一種短文本聚類系統(tǒng)的框架，包括基于無關(guān)語識別和詞類歸一化的相似度計算方法、基于離線聚類與在線聚類的聚類方法。

2 系統(tǒng)框架與實現(xiàn)

2.1系統(tǒng)框架

由于聚類的數(shù)據(jù)量大，如果直接利用聚類，算法效率很低，無法滿足線上應(yīng)用的需要。因此提出一種可增量的用戶短文本聚類系統(tǒng)，該系統(tǒng)將聚類分為離線聚類和在線聚類兩部分，系統(tǒng)框架如圖1所示。

圖1 系統(tǒng)框架

2.2離線聚類

短文本中含有很多與句子本身語義無關(guān)的成分，并且這些成分影響了短文本之間的句子相似度。這些與語義無關(guān)的詞語，稱為無關(guān)語。而相似度的準確性決定了聚類結(jié)果，因此首先對句子進行無關(guān)語識別，清除句子中的無關(guān)語。建立語義詞類對短文本進行語義歸一化，然后利用短文本之間的相似度，建立相似度圖，最后利用聚類算法對短文本進行聚類。圖2是離線聚類的框架圖。

圖2 離線聚類框架

系統(tǒng)框架分為4個部分：

(1)短文本干擾項的預(yù)處理：在無關(guān)語詞典的支持下，對短文本中的無關(guān)語進行識別，從而對短文本中的語義干擾項進行清理；

(2)基于詞類的語義歸一化：漢語中相同的語義有多種表達法，并且詞的形式也不一樣，因此需要對相同語義的詞或短語進行歸一化，從而提高句子間的語義相似度；

(3)相似度圖的建立：經(jīng)過預(yù)處理和語義歸一化后，求得短文本之間的相似度，建立短文本的相似度圖；

(4)短文本聚類算法：利用層次聚類算法對短文本進行聚類。

2.2.1 無關(guān)語識別

在短文本句中，存在大量的詞語與短語，而這些詞語本身對句子的語義沒有實質(zhì)的意義，從短文本中去掉這些詞，短文本的語義不發(fā)生實質(zhì)變化。例如：S1=“你好，請問一下電腦藍屏如何處理？”

在S1中“你好”、“請問一下”等詞語對S1的語義沒有意義，因此在相似度計算前需要對這些詞進行清除。

定義1(無關(guān)語)：不影響短文本語義的詞語或句子成分。

經(jīng)過長期的積累收集和獲取無關(guān)語，構(gòu)成無關(guān)語詞典。文本預(yù)處理利用無關(guān)語詞典建立雙數(shù)組Trie結(jié)構(gòu)，利用前向最大匹配進行無關(guān)語識別，然后清理短文本中的無關(guān)語。例如：S2=“電腦藍屏怎么辦呀？”，如果直接計算S1與S2的相似度，其相似度較低。但是經(jīng)過無關(guān)語識別和清理后：

2.2.2 語義歸一化

由于自然語言的隨意性，并且漢語中存在大量的意義相近、但詞性不同的詞語或短語，完全不同的句子表達的意思卻是相同的。例如：

S2=“我的筆記本電腦運行很慢?！?/p>

S3=“手提跑起程序來不動。”

在S2與S3中，意思是相近的，但是句子中的詞完全不一致，利用傳統(tǒng)的相似度算法計算S2與S3的相似度很低，因此很難將S2與S3聚類到一起。

將一些領(lǐng)域相關(guān)的表示同義的詞與短語收集起來，形成詞語語義類，利用詞語語義類對短文本進行語義歸一化。例如，在S2與S3中，定義如下詞類：

“筆記本電腦|手提|手提電腦|筆記本|個人計算機|……”

“運行|跑程序|跑起程序|運行程序|……”

“慢|很慢|非常慢|不動|……”

利用上述詞類，可以將S2與S3進行語義歸一化，從而使S2與S3語義相同。

2.2.3 短文本相似度計算

(1)構(gòu)造的特征向量空間為V={X1,X2,…,Xn}，句子S1的特征向量為V1={ω1,ω2,…,ωn}，ωi表示特征詞Xi在句子S1中出現(xiàn)的次數(shù)，句子S2的特征向量為V2={φ1,φ2,…,φn}，φi是特征詞Xi在句子S2中出現(xiàn)的次數(shù)，則S1與S2間的特征向量的相似度為：

(1)

(2)計算句子間的2-Gram相似度，分別求出句子S1和S2的2-Gram序列。

(2)

(3)計算咨詢間的搭配相似度。對句子進行搭配分析，獲取句子中的搭配對，其中Col1為S1的詞的搭配的集合，Col2為S2的詞的搭配的集合，則S1和S2間的搭配相似度為：

(3)

(4)通過多特征的相似度融合算法計算咨詢間的相似度：

Sim(S1,S2)=w1*Sim1(S1,S2)+w2*Sim2(S1,S2)+w3*Sim3(S1,S2)

(4)

其中，w1,w2,w3分別表示這三種相似度的權(quán)重，且滿足w1+w2+w3=1。

2.2.4 短文本聚類算法

由于短文本相似度矩陣非常巨大，并且很多相似度值為0(或極小)，對這些零元素進行計算和存儲會造成程序計算和存儲空間的浪費。對短文本進行多次實驗，發(fā)現(xiàn)短文本相似度小于某個閾值(α)的點非常多，因此采用基于相似度稀疏矩陣的短文本聚類方法，相似度低于α的點被排除。首先通過相似度閾值α篩選構(gòu)造了短文本相似度稀疏矩陣，采用文獻[17]中的關(guān)聯(lián)聚類(Correlation Clustering)方法對短文本相似度圖進行聚類。關(guān)聯(lián)聚類算法是一種隨機算法，主要是基于同簇中的不相似的句子數(shù)量和不同簇中的相似句子數(shù)量的最小化代價函數(shù)。修改原始算法，對邊是否剪枝或參與聚類增加權(quán)值，加入到代價函數(shù)中。算法易于初始化。利用不同的隨機數(shù)進行多次多重關(guān)聯(lián)聚類，當代價函數(shù)最小時就認為是最后的聚類結(jié)果。關(guān)聯(lián)聚類的一個重要特征是不需要告訴聚類算法簇的數(shù)量，而短文本語料也很難估計有多少個類別。短文本聚類算法如下所述：

算法1：Offline-clustering。

輸入：短文本集合D={S1,S2…}，文本相似度矩陣X，相似度閾值*，聚類閾值＊

輸出：文本集合D的一個聚類C={c1,c2…}，ci中的元素為D中的元素，最終更新后的文本相似度稀疏矩陣為X''。

1:Begin

2:排除X中小于＊的元素，形成短文本相似度稀疏矩陣X'；

3:在X'中尋找最大的且大于＊的一對點V1與V2，若找到執(zhí)行3，否則執(zhí)行算法2；

4:將V1和V2看成一個新簇，更新X'，將更新后的相似度稀疏矩陣記為X''；

5:將V1和V2合并為新簇NewCluster；

6：利用以下更新NewCluster與其他點的相似度：

(|m_cluster[nRowIndex]|*fSimRow+

|m_cluster[nColIndex]|*fSimCol)/

(|m_cluster[nRowIndex]|+|m_cluster [nColIndex]|)

7:Repeat (1)- (5) Until 滿足預(yù)先設(shè)定的終止條件；

8:End

2.3在線聚類

在線聚類是基于離線聚類結(jié)果基礎(chǔ)上進行的，從而可以減少聚類的時間。離線聚類后，給每個類都標記了一類號，利用離線聚類的結(jié)果作為聚類特征對用戶短文本進行在線聚類，然后對離線聚類和在線聚類結(jié)果進行合并生成聚類結(jié)果。算法如下所述：

算法2：Online-clustering。

輸入：在線新的短文本集合D={S1,S2…}，文本相似度矩陣X，相似度閾值*，聚類閾值＊；

輸出：文本集合D的一個聚類C={c1,c2…}，ci中的元素為D中的元素，最終更新后的文本相似度稀疏矩陣為X''。

1:Begin

2:計算當前在線文本和離線聚類后的類cluster(i)之間的相似度，通過以下方法求得：

遍歷離線類cluster(i)中的每一條咨詢，利用式(4)通過多特征的相似度融合算法計算新咨詢q和離線類咨詢qi間的相似度Sim(q,qi)，qi∈cluster(i)，cluster(q)和類cluster(i)之間的相似度為：

其中，|cluster(i)|表示類i中的咨詢的數(shù)量。

3:獲得的在線用戶咨詢與離線聚類后的每個類的相似度，形成相似度圖；

4:遍歷相似度圖，找到相似度最大的邊，如果相似度最大的邊的相似度滿足閾值條件Sim2(cluster(q),cluster(i))>β，則將該咨詢加入到cluster(i)中，否則，如果沒有找到滿足條件的類，則將該咨詢形成一個新的類newcluster；

5：利用以下更新NewCluster與其他點的相似度；

6:Repeat (2)-(5) Until 滿足預(yù)先設(shè)定的終止條件；

7:End

3 實驗結(jié)果及分析

為了評價短文本聚類方法的效果，收集了某領(lǐng)域QA系統(tǒng)中的用戶咨詢?nèi)罩?，短文本句子?shù)量2萬行，然后人工對用戶短文本進行分類，形成測試集。

聚類效果的評價指標[18]如下：

聚類召回率為：

(5)

聚類準確率為：

(6)

F值為：

(7)

其中，TP表示被正確聚在一起的文本；FN表示被錯誤分開的文本；FP表示被錯誤聚在一起的文本。

實驗包括兩個，一個采用基于特征詞向量的相似度[4]來計算短文本間的相似度，然后利用提出的聚類算法進行聚類，另一個是利用文中提出的相似度計算方法。實驗結(jié)果對比見表1。

表1 實驗結(jié)果對比

基于離線聚類的結(jié)果，對在線咨詢和離線聚類進行在線聚類，系統(tǒng)能快速響應(yīng)，結(jié)合快速咨詢?nèi)ブ?，大大降低了聚類的算法?fù)雜度，且聚類結(jié)果的準確率達85%以上?？梢?，文中方法的系統(tǒng)響應(yīng)快、精度符合實際應(yīng)用需求，有效性和準確性高，具有較高的實用性，尤其適用于領(lǐng)域問答系統(tǒng)中。

從實驗結(jié)果可以觀察出，文中方法對2萬行文本聚類比采用基于特征向量的方法效果要好，主要原因是短文本中的特征詞較少，并且用戶短文本中語義無關(guān)項比較多，從而對句子的語義產(chǎn)生干擾，使基于特征向量的相似度計算方法不準確。而文中方法能有效地用于用戶短文本聚類，但對于包含多個分句的長文本聚類的效果不是很好，原因之一是用戶文本的隨意性，多個分句中包含多個主題，從而導(dǎo)致聚類不準確。

4 結(jié)束語

針對短文本中含有的特征詞少，容易造成描述概念信號弱、特征稀疏以及聚類耗時等問題，提出了一種可增量的用戶短文本聚類方法。該方法基于將離線聚類和在線聚類相結(jié)合的聚類框架，通過離線聚類算法，利用語義無關(guān)詞典和詞類詞典對用戶咨詢進行語義預(yù)處理，從而實現(xiàn)語義的歸一化，依據(jù)基于多特征的相似度計算結(jié)果構(gòu)建相似度圖，根據(jù)相似度圖對用戶文本進行離線聚類，進而利用離線聚類的結(jié)果作為聚類特征，對在線用戶文本進行在線聚類，對離線聚類和在線聚類結(jié)果進行合并，以生成聚類結(jié)果。實驗結(jié)果表明，該方法在聚類召回率、精度以及F-值方面要優(yōu)于基于特征向量的方法。

[1] 楊占華.聚類分析研究及其在文本挖掘中的應(yīng)用[D].成都:西南交通大學(xué)，2014.

[2] Dhillon I S,Modha D S.Concept decompositions for large sp-arse text data using clustering[J].Machine Learning,2001,42(1-2):143-175.

[3] Han Jiawei,Kamber M.Data mining concepts and techniques[M].北京:機械工業(yè)出版社，2001.

[4] Apte C,Liu Bing,Pednault E P D,et al.Business applications of data mining[J].Communications of ACM,2002,45(8):49-53.

[5] Xu R,Wunsch D.Survey of clustering algorithms[J].IEEE Transactions on Neural Networks,2005,16(3):645-678.

[6] Salton G,Wong A,Yang C S.A vector space for automatic indexing[J].Communications of the ACM,1975,18(11):613-620.

[7] Fuhr N.Probabilistic models in information retrieval[J].The Computer Journal,1992,35(3):243-255.

[8] 宋韶旭.基于語義關(guān)聯(lián)的文本聚類方法[D].北京:清華大學(xué)，2006.

[9] 王永成.中文信息處理技術(shù)及其基礎(chǔ)[M].上海:上海交通大學(xué)出版社,1990.

[10] Ramoni M,Sebastiani P.Introduction to the robust Bayesian classifier[R].[s.l.]:[s.n.],1999.

[11] Cheeseman P,Stutz J.Bayesian Classification (AutoClass):theory and results[C]//Proceedings of advances in knowledge discovery and data mining.Menlo Park,CA,USA:American Association for Artificial Intelligence,1996:153-180.

[12] Hatzivassiloglou V.Simfinder:a flexible clustering tool for summarization[C]//Proceedings of NAACL workshop on automatic summarization.Pittsburgh,USA:Association for Computational Linguistics,2001:4-14.

[13] Rabiner L R.A tutorial on hidden Markov models and selected applications in speech recognition[J].Proceedings of the IEEE,1989,77(2):257-286.

[14] 王 剛，鐘國祥.一種基于本體相似度計算的文本聚類算法研究[J].計算機科學(xué)，2010,37(9):222-224.

[15] 李曉光，于 戈，王大玲，等.基于信息論的潛在概念獲取與文本聚類[J].軟件學(xué)報，2008,19(9):2276-2284.

[16] Macqueen J.Some methods for classification and analysis of multivariate observations[C]//Proceedings of the fifth Berkeley symposium on mathematical statistics and probability.[s.l.]:[s.n.],1967:281-297.

[17] Bansal N,Blum A,Chawla S.Correlation clustering[J].Machine Learning,2004,56(1-3):89-113.

[18] 曲維光，陳小荷，吉根林．基于框架的詞語搭配自動抽取方法[J].計算機工程，2004,30(23):22-24．

ResearchonScalableClusteringofUser-orientedShortText

ZHANG Yi，CHEN Guo，ZHANG Zai-yue

(School of Computer Science and Engineering，Jiangsu University of Science and Technology,Zhenjiang 212003，China)

With the advent of big data time,data of user short text has growing explosively.Acquisition of useful information from short text with clustering analysis technology is becoming most important.Clustering analysis,as a crucial means of knowledge discovery,is the process of classifying the objects according to their similarity degree of characteristics.Therefore,a scalable clustering method of user-oriented short text is proposed,which is composed of two phases,offline clustering and online clustering.The short text is pre-processed by recognizing and removing irrelevant words with irrelevant words dictionary and normalizing semantics with parts of speech dictionary in offline clustering.A similarity calculation method is proposed based on fusion of mutli-features to conduct correlation clustering on text.Then in the online clustering,the online texts are clustered via taken results of offline clustering as features.Results of clustering are produced by integration of the results from offline clustering with those of online clustering.In order to verify its effectiveness and feasibility,the contrast experiments are conducted.Experimental results show that it has achieved recall rate in clustering by 73%,clustering accuracy by 87.7% and value ofF-measure by 79.6%,which is superior to feature vector method.

short text;semantic normalization;offline clustering;online clustering

2016-07-28

2016-11-09 < class="emphasis_bold">網(wǎng)絡(luò)出版時間

時間：2017-07-19

國家自然科學(xué)基金資助項目(61371114,61170156)；江蘇科技大學(xué)海洋裝備研究院自培育項目(HZ2016004)

張 儀(1987-)，男，碩士研究生，研究方向為自然語言理解、知識獲??；張再躍，教授，博士，研究方向為知識表示與獲取。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170719.1108.006.html

TP301

A

1673-629X(2017)11-0083-05

10.3969/j.issn.1673-629X.2017.11.018