基于隱喻詞擴展的短文本聚類算法

王 燁, 左萬利, 王 英

(吉林大學 計算機科學與技術學院, 符號計算與知識工程教育部重點實驗室, 長春 130012)

互聯網的飛速發展使得網絡上信息量劇增, 人們瀏覽網頁留下的信息不斷增加, 各種即時短消息大量涌現, 如人們在搜索引擎中輸入的搜索內容, 在即時聊天系統中寫入的大部分句子及各種新聞標題等. 人們希望能從這些短文本中獲取有用的資源, 并對海量的文本進行管理.

在實際應用中, 若判斷一則短消息的具體類別, 需要發現其與歸屬類的某些內在聯系以判斷其類別屬性. 根據這些內在聯系去完成各種任務, 例如: 通過聚類用戶在搜索引擎中輸入的搜索內容, 向用戶提供最相關的信息； 通過將新聞標題進行聚類, 向用戶推薦類似新聞; 減少冗余信息的沉積等. 文本聚類就是把語料集分成幾個類簇, 使其中相似的文本組織成一個類簇, 并使類簇內短文本的相似度盡可能較大, 而類簇間短文本的相似度盡可能較小. 文本聚類作為一種無監督的機器學習方法, 不需要訓練過程, 具備良好的自動化處理能力和一定的靈活性, 在文本挖掘等領域應用廣泛. 文本聚類算法主要分為劃分法、 層次法、 基于密度的方法、 基于網格的方法和基于模型的方法[1-4]. 但短文本的信息缺失使普通的文本聚類方法很難應用于此, 短文本的詞匯量少, 表達形式多樣, 易導致原應屬于同一類的兩則短文本之間幾乎沒有相同詞匯, 進而導致短文本聚類結果不準確.

目前, 對短文本聚類分析的研究主要分為兩方面: 1) 嘗試改進各種傳統的聚類方法; 2) 致力于處理短文本本身, 對較稀疏的特征進行擴展. 文獻[5-6]針對短文本特征稀疏的問題, 對短文本進行文本擴充, 從而增加了短文本信息量. Hu等[7]提出了一種基于三層結構式的處理短文本特征詞稀疏的方法, 將特征分為內部特征和外部特征, 將其融合形成特征短文本； Ni等[8]提出了一種基于查找核心詞的短文本聚類方法； 楊俊麗[9]提出了一種基于外在知識的短文本聚類方法； 袁滿等[10]提出了一種基于頻繁詞集的特征擴展方法； 韓冬雷等[11]提出了一種基于維基百科的短文本語義擴張方法. 與英文短文本聚類研究相比, 對中文短文本聚類的研究相對較少. 本文對短文本擴張進行進一步研究, 利用維基百科將短文本中的隱喻詞進行擴展, 以在一定程度上彌補短文本信息量較少的缺陷, 提升短文本聚類效果.

1 短文本聚類算法

1.1 維基百科

本文使用維基百科對短文本進行擴展. 維基百科是由多種語言分類構成的知識庫, 內容豐富, 其主題頁面之間的鏈接關系可解釋詞語之間的相關關系, 為計算詞語相關度提供了研究基礎.

圖1 維基百科的鏈入鏈出關系Fig.1 Relationship of Wikipedia chain

圖1為維基百科的鏈入鏈出關系, 其中γ列為同義詞關系, 即重定向到同一頁面的詞語,α列為γ列的入鏈接集合,β列為γ列的出鏈接集合, 本文基于維基百科的鏈接關系對詞語相關性進行計算. 使用維基百科數據庫的page,pagelinks,redirect,category,categorylinks,revision和text表, 其中: page表用于保存主題頁面的相關信息, 是維基百科系統的核心表； pagelinks表用于保存主題頁與主題頁之間的鏈接關系, 表示的鏈接關系為鏈入關系與鏈出關系； redirect表用于保存頁面中的重定向信息, 重定向信息是指一個詞語是否有其他主題與其一致, 例如“五星紅旗”重定向為“中華人民共和國國旗”, 即主題頁面“五星紅旗”的內容與主題頁面“中華人民共和國國旗”的內容一致； category表用于保存已存在的分類； categorylinks表用于保存主題頁面所屬的類別鏈接； revision表用于保存修改后頁面的信息, 每次修改形成一個新的版本； text表用于保存主題頁面的正文內容.

維基百科數據庫的各表間關系如下：

1) page.page_latest→revision.rev_id;

2) revision.rev_page→page.page_id;

3) revision.rev_text_id→text.old_id;

4) 通過page.page_id可得到redirect.rd_title, 從而可得到重定向到此頁面的所有rd_from.

由上述表可得到表間豐富的鏈接關系及主題頁面所屬類別, 通過這些關系可得到主題與主題之間的相互關系, 從而得到詞語的同義詞、 近義詞等有關聯的詞語, 為后續的短文本擴展提供基礎.

1.2 短文本關鍵詞選擇

在對短文本進行分詞以去停用詞后, 需要對文本中的字詞進行度量, 判斷其在文本中的重要程度, 即選擇關鍵詞.

TF-IDF作為一種用于文本挖掘的常用加權技術, 其作用是可用于評估一個字詞對于一個語料集中一個文本的重要程度. 如果一個字詞在文本中的出現次數越多, 則其重要程度就會成正比增加； 反之, 如果其在數據集中的出現次數越多, 則其重要程度就會成反比下降. TF-IDF的主要思想是： 在語料集中選出若干關鍵詞, 通過關鍵詞對文本進行區分. 作為關鍵詞的條件是其在一個文本中出現的頻率較高, 同時在語料集中其他文本中出現的頻率較低, 則該詞語即具有較好的類別區分能力, 適用于分類.

TF是對詞數的歸一化表示, 用于防止其偏向較長的文本. 因為長文本中重復的詞匯可能會較多, 若只計算詞語總數, 則可能導致偏差. 逆向文件頻率(IDF)是度量一個詞語在數據集中普遍重要性的指標. 計算某個詞語wi逆向文件頻率, 可由總文件數|D|除以包含該詞語wi文件的數目|{j:wi∈dj}|, 再將得到的商取對數, 即得到理想文件頻率IDF：

TF-IDF實際上是TF(wi,dj)×IDF(wi), 則

如果某個詞語在一個文本內擁有較高詞頻, 同時在整個語料集中擁有較低頻率, 則經過計算后即可得較高的權重, 可作為候選關鍵詞. 因此, TF-IDF可過濾掉一些在數據集中經常出現的詞語, 同時保留重要的詞語, 能區分出產生良好效果的詞語.

1.3 算法設計

1.3.1 相關度計算 在維基百科中的大量鏈入鏈出關系可側面反映兩個主題的相關度, Milne[12]提出了一種基于兩個頁面的入鏈接關系計算這兩個詞語的相關度方法, 以及一種基于概念間相互鏈接關系計算兩個詞語相關度的方法, 這兩種方法都是目前普遍采用的計算詞語相關度的方法.

本文采用基于入鏈接關系的方法[13]計算詞語相關度：

作為重定向的某一頁面, 其鏈入頁面很可能并不包含其同義詞的鏈入頁面, 故|a→b|中的頁面a與頁面b也需要包含其同義詞的頁面.

1.3.2 短文本擴充 短文本的詞匯量較少, 同時文本中重復詞語出現次數較少, 文本中的信息量較少, 在應用傳統文本聚類方法的情況下并不能得到較好的聚類結果. 考慮到文本中存在大量的隱喻現象, 因而需將文本中的隱喻詞進行擴展. 首先基于維基百科得到其真正表示的含義, 然后對其真正含義的同義詞進行擴展, 目的是增加文本的信息量, 從而提高文本聚類效果.

一般短文本中的隱喻詞會在維基百科中形成“歧義頁”主題頁面, 該主題頁面中列出了該詞語包含的幾種含義. 例如, 網絡中的“恐龍”一詞, 原意指出現于中生代的曾支配全球陸地生態系統超過1億6千萬年之久的多樣化優勢陸棲脊椎動物, 但在現代中文網絡中, “恐龍”一詞多指對丑女的稱呼, 在維基百科中對應的頁面為“恐龍(俗語)”, 由于此類解釋多為維基百科中消歧義頁面的內容, 所以在這里需要用到對隱喻詞進行擴展的頁面為維基百科中的消歧義頁面.

首先, 將文本dj表示為一個詞匯列表, 對于詞匯列表中的每個詞語wi進行遍歷, 查詢其是否在維基百科中存在歧義頁面. 如果存在歧義頁面, 則將除隱喻詞wp外的其他詞語表示為一個詞匯列表lj, 對于詞語列表lj中的每個詞語wlj,i, 使用上述計算詞語相關度的方法計算相關度, 并選取歧義頁面中與其相關度最大的一項作為該隱喻詞wp的真正解釋ep.

其次, 對該解釋ep進行擴展. 查詢其鏈入頁面的主題頁面集合, 對集合中的每個頁面與該頁面進行相關度計算, 由于短文本數據集選擇的是新聞標題, 文本長度較小, 故選擇相關度最大的3個頁面作為擴展選項對短文本進行擴展. 例如, 新聞標題“蘋果Apple Watch今年難在瑞士開售： 商標被搶注”, 經過分詞以及去停用詞后變為詞匯列表[“蘋果”,“Apple”,“Watch”,“今年”,“瑞士”,“開售”,“商標”,“搶注”], 經過遍歷后發現“蘋果”一詞為隱喻詞, 使用上述算法進行計算后, 得到其真正解釋為“蘋果公司”, 通過對“蘋果公司”進行擴展后, 得到與其相關度最大的3項, 分別為“蘋果電腦”、 “蘋果計算機”和“Apple_Computer”, 將這3項作為擴展詞語擴充入短文本中, 即具有增加短文本信息量的作用. 但像“小米”一詞在中文維基百科中并沒有歧義頁面, 而該詞語卻是真實存在的擁有隱藏含義的詞語. 經過探索發現, 在中文維基百科數據庫中text表的old_text中存在“other”選項“小米科技”, 即隱喻詞的發現僅通過歧義頁面還不夠, 還需對上述這類詞語進行old_text的查詢, 發現其其他用法.

1.3.3 短文本聚類 由于本文使用的語料集規模較小, 而k-means算法簡單易行, 較適用于這種規模的數據集[14-15]. 但k-means算法易導致無法收斂到全局最小值, 因此本文采用二分k-means算法對短文本進行聚類.

k-means算法是通過用戶給定類簇個數k, 通常隨機選擇k個初始點作為聚類中心, 將語料集中的每個數據點分配到離其最近質心所屬的類簇中, 然后更新每個類簇的質心為該類簇所有點的平均值[16-17]. 二分k-means算法克服了k-means算法易收斂到全局最小值的問題, 該算法首先將所有數據點作為一個簇, 然后取這些數據點的平均值作為簇中心, 將其一分為二, 最后根據分開后的兩個簇哪個可以降低總誤差就對哪個簇進行劃分, 直到達到規定類簇的個數.

算法1基于隱喻詞擴展的短文本聚類算法.

forwiindj:

ifwi在維基百科中存在歧義頁面：

查詢wi的歧義詞

else:

查詢wi的old_text頁面, 發現其其他用法

lj={wlj,i|wi?wlj}

forwlj,iinlj:

計算詞語相關度

選取相關度最大的wlj,i作為真正解釋ep

for 鏈入 inep:

計算其與ep的相關度

選取相關度最大的3個頁面作為擴展項對短文本進行擴充

將所有數據點視為一個簇

當類簇個數小于規定個數k時

對于每個類簇

計算SSE值

進行k=2的k-means聚類

計算聚類后的總誤差

選擇使總誤差最小的類簇進行一分為二的劃分.

2 實驗結果與性能分析

本文采用F-measure方法[18]進行聚類結果評價.F-measure方法通過查準率與查全率得到綜合評價的F值, 其中查準率是正確分配到一個類簇中短文本的概率, 反映每類中的內容是否集中； 查全率是同一類別的文本被分配到一個類簇中的概率, 反映同一類中的相似文本是否集中.

本文對教育、 音樂、 體育和科技4類共1 600條新浪新聞標題進行聚類分析. 通過對本文提出的基于隱喻詞擴展的短文本聚類算法進行10次交叉實驗后的聚類結果如圖2所示. 與二分k-means聚類算法相比,k-means聚類算法對于聚類中心的選擇具有較大隨機性, 易導致聚類局限性. 對擴展前后的短文本進行10次交叉實驗, 采用平均值作為聚類結果如圖3所示.

圖2 二分k-means聚類結果Fig.2 Clustering results of bisecting k-means

圖3 k-means聚類結果Fig.3 Clustering results of k-means

由圖2和圖3可見, 二分k-means方法得到的結果相對較好, 擴展前后的F值平均提高了18%, 基于隱喻詞擴展后的短文本在聚類結果上得到較大提高.

考慮到新聞標題中出現的大量人名或新鮮詞匯在中文維基百科中可能查詢不到相關內容, 因此若能考慮到這些因素, 并在本文基于隱喻詞擴展的基礎上再次進行擴展, 所得到的聚類結果可能更有效.

綜上可見, 本文采用基于隱喻詞擴展的方法對短文本進行聚類的效果得到了較大提升, 能對短文本文檔進行有效歸類.