短文本相似度研究及其在微博話題檢測中的應用

黃賢英，陳紅陽，劉英濤

（重慶理工大學 計算機科學與工程學院，重慶400054）

0 引 言

微博話題檢測是微博短文本處理與學習的一個重要應用領域，話題檢測的質量多受微博短文本相似度計算方法的影響。該類型的短文本具有不同的特點，因此，如何利用微博短文本的特點設計高效的短文本相似度算法至關重要［1－3］。

研究者針對短文本相似度展開了一系列研究，并取得初步的成果，這些方法也常用于度量微博短文本之間的相似性：文獻 ［4］提出基于關鍵詞重疊的方法，以單個關鍵詞為語義單元度量文本之間的相似性，文本間共有關鍵詞個數與其相似性成正相關，而短文本用語非規范化，特征極度稀疏，隱含信息難以挖掘，僅基于文本間共有的關鍵詞數目度量文本的相似性存在一定的誤差；文獻 ［5］使用公共詞塊為語義單元，相較于關鍵詞重疊方法可更好地度量短文本之間的相似性，卻未考慮詞塊間的組合順序對文本相似性的影響，且公共詞塊是由連續的詞形相同或者詞義相同的詞項所組成的，公共詞塊的粒度較小；文獻 ［6］以關鍵詞為基本單元，考慮了關鍵詞之間的語義相似性與組合順序，提出從關鍵詞的詞義與詞序的角度來計算文本相似度，但文本相似性度量的語義單元是單個的關鍵詞，不具備獨立完整的語義信息表達能力。然而，它們均未涉及到微博短文本自身所具備的一些特點，實際上微博文本的發布時間，文本之間的轉發與評論等結構化信息［7，8］對文本間相似性度量也具有一定的貢獻。針對微博短文本獨有的特點，研究者提出了一些考慮微博短文本特點的相似性度量方法。周剛等［9］提出了基于微博短文本之間的轉發與評論關系，微博發布者之間的關注與好友關系來衡量微博短文本之間的相似性以實現微博話題檢測；駱衛華等［10］認為話題既具有語義特征，也具有時間特征，考慮了時間因素，引入了時間衰減函數，構建基于余弦相似度與時間相似度的文本相似性度量方法。這些方法均獨特地從微博短文本的另一角度出發來衡量微博短文本之間的相似性，具有一定的借鑒意義。

本文依據影響微博短文本相似性度量的因素 （文本間內容主題相似性、文本討論主題相關性），在新的基于公共塊序列的短文本語義相似度的基礎上，充分利用微博短文本的發布時間、文本間的轉發、評論等信息，進而形成一種基于語義關系，時間關系和社交關系的相似度算法，多角度衡量微博短文本之間的相似性，然后將該算法應用于微博話題檢測中以進一步提高話題檢測的質量。

1 基于多視角的微博短文本相似度算法

微博短文本內容長度短、表達隨意、非規范化等特點致使文本向量高維且有效特征稀疏，傳統的相似度算法并不能精確地度量微博短文本之間的相似性，本文在基于公共塊序列的短文本語義相似度的基礎上，利用微博短文本的發布時間、轉發評論等信息對該語義相似度模型進行修正，從而形成新的微博短文本相似度算法來度量文本之間的相似性。該算法首先簡介公共塊的定義以及如何尋找兩微博短文本中的公共塊；然后，在此基礎上構建基于公共塊序列的語義相似度；最后，使用微博短文本發布時間、轉發與評論等信息來修正基于公共塊序列的語義相似度。

1.1 尋找兩微博短文本中存在的公共塊

定義 公共塊是指兩個文本中詞形與詞義相同的連續的幾個詞項組合在一起的詞塊，公共塊中至少包含一個詞形相同或者詞義相同的詞項，其最大長度 （公共塊中所含的最大詞項總數）不超過較短的文本長度 （文本中所含詞項總數），最小長度 （公共塊中所含的最小詞項總數）不低于1。

尋找兩微博短文本中所存在的公共塊的算法如下描述所示。

算法：尋找兩微博短文本中存在的公共塊的算法。

輸入：微博 短 文 本D1＝｛a1，a2，...，am｝，D2＝｛b1，b2，...，bn｝

輸出：存儲微博短文本D1，D2中所存在的公共塊的集合CommonBlocksList ＝ ｛terms1，terms2，...，termsr｝，（r＜＝min（m，n））

（1）構建二維相似度矩陣M ：采用基于 《知網》的詞匯語義相似度方法［11］分別計算第一個詞項集合中的每個詞項與第二個詞項集合中每個詞項之間的語義相似度，以此構建二維相似度矩陣M ，如式 （1）所示

式中：sij——文本D1中第i個詞項與文本D2中第j個詞項之間的語義相似度值。

（2）構建詞對集合WordsPairList：①遍歷矩陣M ，尋找第一個最大相似度值 （大于0.5），依據該值在矩陣M中所處的位置 （行與列），記錄其在兩文本D1，D2中所對應的詞對＜ai，bj＞（1≤i≤m，1≤j≤n），同時將該相似度值設置為0；②按照①中所述規則尋找下一個最大相似度值，并對相應的數據信息進行記錄與更改，直至矩陣M 變為零矩陣；③找出兩文本中存在的全部詞對，并構建詞對集合WordsPairList＝｛＜p1，q1＞，＜p2，q2＞，...，＜pk，qk＞｝，其中，k∈（0，min（m，n）），p1，p2，...，pk為微博短文本D1中的詞項，而q1，q2，...，qk為微博短文本D2中的詞項，＜pi，qi＞，（1≤i≤k）則為文本D1與D2中的第i個詞項。

（3）構建公共塊集合CommonBlocksList：①遍歷詞對集合WordsPairList，取出每一個詞對中的第一個元素放入詞項集合WordsList1，第二個元素放入詞項集合WordsList2。將WordsList1＝｛p1，p2，...，pk｝中的元素按照其在文本D1中所處的先后順序進行排序，且從1開始依次順序編號，構成序列OrderList1＝｛l1，l2，...，lk｝，（li∈瓔，0≤i≤k）；將WordsList2＝｛q1，q2，...，qk｝中的元素按照其在文本D2中所處的先后順序進行排序，然后根據詞對中兩個元素的對應關系，對經過排序后的元素，進行相應的數字編號以構成序列OrderList2＝｛t1，t2，...，tk｝，（ti∈瓔，0≤i≤k）；②遍歷序列OrderList1，首先取前兩個元素，判斷其在序列OrderList2中所對應的兩個元素是否也遞增連續，若否，就從序列OrderList1中刪除當前元素之前的元素，并將這些元素所對應的詞項取出作為一個公共塊，然后轉②，直至序列OrderList1中的元素為空，轉④，否則，轉③；③繼續遍歷序列OrderList1中的下一個元素，看是否能和前面已知的元素組在一起構成公共塊，若能，則繼續遍歷該序列OrderList1中的下一個元素，直至當前所遍歷的元素與前面已知元素組合在一起不能相應地構成公共塊，則取出當前元素之前的組合元素作為公共塊，并將這些組合元素從序列OrderList1中刪除掉，轉②；④找出兩微博短文本中存在的公共塊，存儲在公共塊集合CommonBlocksList 中，它 可 表 示 為CommonBlocksList ＝｛terms1，terms2，...，termsr｝，（r ＜＝ min（m，n）），termsi（1≤i≤r）則表示該集合中的第i個公共塊。

1.2 基于公共塊序列的語義相似度

兩個微博短文本所含公共塊個數、塊內部所含詞項個數愈多，則它們的相似性就愈大；此外，公共塊之間的組合順序對文本之間的相似性也具有一定的影響。鑒于此，基于公共塊所含詞項總數與公共塊之間的組合順序共同度量文本之間的相似性如式 （2）與式 （3）所示

例如：微博文本D1－小明乘坐火車從河南鄭州到陜西西安去同學家玩。微博文本D2－乘客選取乘坐飛機從陜西西安到河南鄭州這條線路。公共塊：乘坐，從，河南鄭州，到，陜西西安。公共塊在文本D1中的順序向量r1：1，2，3，4，5；公共塊在文本D2中的順序向量r2：1，2，5，4，3。

基于公共塊序列的語義相似度算法具體描述過程如下所示。

算法：基于公共塊序列的短文本語義相似度算法。

輸入：微博短文本D1，D2

輸出：微博短文本D1，D2之間的相似度值SimCB

（1）微博短文本表示：將微博短文本D1，D2以詞項集合的 形 式 進 行 表 示。D1＝｛a1，a2，...，am｝，D2＝｛b1，b2，...，bn｝，其中ai（1≤i≤m）表示微博短文本D1中的第i個詞項，m 表示該文本的長度；bj（1≤j≤n）表示微博短文本D2中的第j個詞項，n表示該文本的長度。

（2）尋找兩微博短文本中存在的公共塊：根據上述所描述的公共塊尋找算法將兩微博短文本中存在的公共塊找出 并 以 集 合CommonBlocksList ＝ ｛terms1，terms2，...，termsr｝，（r＜＝min（m，n））的形式進行表示。

（3）基于公共塊所含詞項總數與公共塊之間的組合順序度量微博短文本之間的語義相似性按照式 （4）計算兩微博短文本中的語義相似度值SimCB。

1.3 利用微博短文本的發布時間、轉發與評論等信息修正基于公共塊序列的語義相似度

（1）微博短文本之間的轉發、評論等結構化信息蘊含著文本之間的相似性關系。從微博文本之間的社會化關系角度度量文本之間的相似性，避免了單一語義相似度的片面性。如果文本間存在轉發與評論關系，則認為它們的相似度值為1，否則，基于微博短文本內容的角度分析、度量文本之間的相似性。

（2）微博話題具有時間聚集特性，通常，一定時間段內微博文本發布時間間隔距離越短，則它們歸屬于同一個話題的可能性就越大，相似性也越大。因此，從文本發布時間的角度衡量微博短文本之間的相似性，如式 （5）所示

式中：Simtime（D1，D2）——兩微博短文本D1，D2之間的 時間相似度，而time1，time2——兩文本所對應的發布時間。

綜上所述，則基于微博短文本的發布時間對語義相似度進行修正：融合時間相似度與語義相似度來度量微博短文本在內容主題上的相似性，如式 （6）所示

α，β，γ分別表示為計算兩個微博短文本之間語義相似度和時間相似度時各自所對應的加權系數，彼此間的關系為（α＋β＋γ＝1，α＞β＞γ），α，β見式 （4）。

利用微博短文本的發布時間、轉發與評論等信息修正短文本語義相似度，以度量文本之間的相似性，具體描述過程如圖1所示。

2 實 驗

本文將新的基于多視角的微博短文本相似度算法應用在微博話題檢測中，即融入該相似性度量方法于Single－Pass聚類算法［12］中實現微博話題的檢測功能。它的具體流程如圖2所示。

2.1 實驗數據

圖1 基于多視角的微博短文本相似度算法流程

圖2 新的微博短文本相似度算法應用于微博話題檢測中的流程

本實驗所使用的數據主要來源于新浪微博中2013年08月04日至2013年08月19日所產生的數據，具體包括微博文本內容、發布時間、發布作者、回復數及轉發數等，共計16個話題，4257條微博文本數據，其中16個話題分別為 “北京樓頂別墅主人”、“全國各地持續高溫”、“斯諾登棱鏡事件”等。

2.2 實驗的評價指標

采用話題檢測與跟蹤的性能評價指標中的漏檢率、誤檢率和歸一化錯誤識別代價作為微博話題檢測的性能評測指標［13］，此3個指標的計算方法如式 （7）所示

式中：Cmiss與Cfa——漏檢率和誤檢率的代價系數，Ptarget與Pnon－target——先驗目標出現的概率和先驗目標不出現的概率，二者的和為1。通常，Cmiss與Cfa取值為1.0 和0.1；Ptarget為0.02。

本實驗通過將16個微博話題對應指標取平均值來測試觀察新的微博短文本相似度算法應用在微博話題檢測中時各個性能指標。

2.3 結果與分析

為確定式 （6）中各個加權組合系數的取值，分別取（α，β，γ）的23種取值組合情況 （精度為0.5），觀測在不同的組合情況下，將基于多視角 （時間、語義以及社會化關系）的微博短文本相似度算法應用于話題檢測時的指標－錯誤歸一化識別代價 （平均值），實驗結果表明，只有當（α，β，γ）＝（0.45，0.35，0.2）時，該指標取得最小值0.1036。因此，將（α，β，γ）的取值確定為（0.45，0.35，0.2）。

在加權組合系數確定的情況下，進行實驗一與實驗二。

（1）實驗一，將新的微博短文本相似性度量方法與文獻［5］中的相似度方法、文獻 ［6］中的相似度方法、基于公共塊序列的語義相似度和時間相似度作對比，分別與Single－Pass聚類算法相結合來實現微博話題的檢測功能，然后觀察在各種不同相似性度量方法下，微博話題檢測的平均漏檢率、誤檢率與Norm（CDet）指標，具體的實驗結果見表1。

表1 各相似性度量方法下的微博話題檢測性能對比

從表1中可觀測出，與Single－Pass聚類算法結合實現微博話題檢測的功能時，基于公共塊序列的語義相似度比時間相似度、文獻 ［5，6］中的相似度方法相比，微博話題檢測的各項指標均有所降低；且本文所提出的微博短文本相似性度量方法，相較于其它幾種方法，各項指標也得到了較大程度的降低。這主要是因為，在對文本中詞項之間詞義與詞序等語義關聯信息加以考慮的情況下，基于公共塊序列的短文本語義相似度相較于文獻 ［5，6］中的相似性度量方法可以更準確地度量文本之間的相似性；此外，在該短文本語義相似度的基礎上，充分利用微博短文本所具有的特點，基于微博短文本的發布時間、轉發與評論等信息修正該語義相似度模型，從多個角度全面地刻畫文本之間的相似性。因此，新的微博短文本相似度算法比傳統的單一相似度算法能更好地測量出微博短文本之間的相似性，進一步降低了微博話題發現的漏檢率、誤檢率與歸一化錯誤識別代價等指標。新的文本相似性度量方法能夠有效地提高微博短文本之間相似度計算的準確性。

（2）實驗二，將基于Single－Pass聚類算法的微博話題檢測方法與基于新的相似度算法＋Single－Pass聚類算法的微博話題檢測方法作比較，實驗結果見表2。

表2 各微博話題檢測方法的性能對比

從表2中所顯示出的數據，可以較為明顯地觀察出新的相似度算法與Single－Pass聚類算法結合使用時可以更好地降低話題發現的漏檢率與誤檢率等指標。其原因在于本文的話題檢測方法融入了新的基于多視角的微博短文本相似度計算方法，從微博文本的發布時間、社會化關系以及語義的角度來估量文本在內容上的相似性，社會化關系上的相關性，從而多角度地，更為準確地衡量了文本之間的相似性，在融入Single－Pass聚類算法中實現微博話題檢測的功能時，有效地將討論同一個話題的微博文本歸入一類，從而更好地降低了微博話題檢測的漏檢率與誤檢率等指標。

3 結束語

本文在對詞項之間的詞義與詞序等語義關聯信息考慮的基礎上，設計一種基于公共塊序列的短文本語義相似度，為使其可以較好地衡量微博短文本之間的相似性，又對微博文本的轉發與評論等結構化信息與時間信息加以充分利用，融合時間相似度與社交相似度以形成基于多視角的微博短文本相似性度量算法，從多個角度，更為全面、準確地衡量微博文本之間的相似性，最后結合Single－Pass聚類算法以檢測微博話題，實驗結果表明，微博話題檢測的性能判斷指標有一定幅度地降低，說明該微博短文本相似度算法準確地度量了微博文本之間的相似性，有效地提高了微博話題檢測的性能指標。

［1］SHI Rui.Internet public opinion analysis for short text ［D］.Xi’an：Xidian University，2011 （in Chinese）.［時睿.面向短文本的網絡輿情分析［D］.西安：西安電子科技大學，2011.］

［2］Rafeeque PC，Sendhilkumar S.A survey on short text analysis in web ［C］／／Third International Conference on Advanced Computing，2011：365－371.

［3］JIANG Shengyi，MAI Zhikai，PANG Guansong，et al.A survey of Micro－blog data mining ［J］.Library and Information Service，2012，56 （17）：136－142 （in Chinese）. ［蔣盛益，麥志凱，龐觀松，等.微博信息挖掘技術研究綜述 ［J］.圖書情報工作，2012，56 （17）：136－142.］

［4］WU Quan’e，XIONG Hailing.Method of sentence similarity computation by integrating multi－features［J］.Computer Systems and Applications，2010，19 （11）：110－114 （in Chinese）.［吳全娥，熊海靈.一種綜合多特征的句子相似度計算方法 ［J］.計算機系統應用，2010，19 （11）：110－114.］

［5］WANG Dong，XIONG Shihuan.Sentence similarity computing with different semantic unit measure ［J］.Journal of Xinyang Normal University，2014，27 （1）：145－148 （in Chinese）.［王東，熊世桓.用不同語義單元度量的句子相似度計算 ［J］.信陽師范學院學報，2014，27 （1）：145－148.］

［6］JIANG Chao.A Micro－blog recommendation system based on user clustering and semantic dictionary ［D］.Zhejiang：Zhejiang University，2013 （in Chinese）.［蔣超.基于用戶聚類和語義詞典的微博推薦系統 ［D］.浙江：浙江大學，2013.］

［7］FANG Yixiang.Research on multi－view topic detection method in twitter ［D］.Harbin：Harbin Institute of Technology，2012 （in Chinese）.［方一向.多視圖微博話題檢測方法研究［D］.哈爾濱：哈爾濱工業大學，2012.］

［8］YANG Wu，LI Yang，LU Ling.Micro－blog hot topics detection method based on user role orientation ［J］.Journal of Computer Applications，2013，33 （11）：3076－3079 （in Chinese）.［楊武，李陽，盧玲.基于用戶角色定位的微博熱點話題檢測方法 ［J］.計算機應用，2013，33 （11）：3076－3079.］

［9］ZHOU Gang，ZHOU Hongcheng，XIONG Xiaobing，et al.MB－SinglePass：Micro－blog topic detection based on combined similarity ［J］.Computer Science，2012，39 （10）：198－202（in Chinese）.［周剛，周鴻程，熊小兵，等.MB－SinglePass：基于組合相似度的微博話題檢測 ［J］.計算機科學，2012，39（10）：198－202.］

［10］LUO Weihua，YU Manquan，XU Hongbo，et al.The study of topic detection based on algorithm of division and multi－level clustering with multi－strategy optimization ［J］.Journal of Chinese Information Processing，2006，20 （1）：29－35 （in Chinese）.［駱衛華，于滿泉，許洪波，等.基于多策略優化的分治多層聚類算法的話題發現研究 ［J］.中文信息學報，2006，20 （1）：29－35.］

［11］LIU Qun，LI Sujian.Word’s semantic computation method based on Hownet［J］.Computational Linguistics and Chinese Information Processing，2007，31 （7）：59－76 （in Chinese）.［劉群，李素建.基于 《知網》的詞匯語義相似度計算 ［J］.計算機語言學及中文信息處理，2007，31 （7）：59－76.］

［12］LIU Gongshen，MENG Kui，XIE Jing.An improved topic detection method for Chinese Micro－blog based on incremental clustering ［J］.Journal of Software，2013，8 （9）：2313－2320.

［13］SUN Shengping.Research on Chinese Micro－blog hot topic detection and tracking ［D］.Beijing：Beijing Jiaotong University，2011 （in Chinese）.［孫勝平.中文微博客熱點話題檢測與跟蹤技術研究 ［D］.北京：北京交通大學，2011.］