王 燁, 左萬(wàn)利, 王 英

(吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室, 長(zhǎng)春 130012)

互聯(lián)網(wǎng)的飛速發(fā)展使得網(wǎng)絡(luò)上信息量劇增, 人們?yōu)g覽網(wǎng)頁(yè)留下的信息不斷增加, 各種即時(shí)短消息大量涌現(xiàn), 如人們?cè)谒阉饕嬷休斎氲乃阉鲀?nèi)容, 在即時(shí)聊天系統(tǒng)中寫(xiě)入的大部分句子及各種新聞標(biāo)題等. 人們希望能從這些短文本中獲取有用的資源, 并對(duì)海量的文本進(jìn)行管理.

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

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

1 短文本聚類(lèi)算法

1.1 維基百科

本文使用維基百科對(duì)短文本進(jìn)行擴(kuò)展. 維基百科是由多種語(yǔ)言分類(lèi)構(gòu)成的知識(shí)庫(kù), 內(nèi)容豐富, 其主題頁(yè)面之間的鏈接關(guān)系可解釋詞語(yǔ)之間的相關(guān)關(guān)系, 為計(jì)算詞語(yǔ)相關(guān)度提供了研究基礎(chǔ).

圖1 維基百科的鏈入鏈出關(guān)系Fig.1 Relationship of Wikipedia chain

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

維基百科數(shù)據(jù)庫(kù)的各表間關(guān)系如下：

1) page.page_latest→revision.rev_id;

2) revision.rev_page→page.page_id;

3) revision.rev_text_id→text.old_id;

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

由上述表可得到表間豐富的鏈接關(guān)系及主題頁(yè)面所屬類(lèi)別, 通過(guò)這些關(guān)系可得到主題與主題之間的相互關(guān)系, 從而得到詞語(yǔ)的同義詞、 近義詞等有關(guān)聯(lián)的詞語(yǔ), 為后續(xù)的短文本擴(kuò)展提供基礎(chǔ).

1.2 短文本關(guān)鍵詞選擇

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

TF-IDF作為一種用于文本挖掘的常用加權(quán)技術(shù), 其作用是可用于評(píng)估一個(gè)字詞對(duì)于一個(gè)語(yǔ)料集中一個(gè)文本的重要程度. 如果一個(gè)字詞在文本中的出現(xiàn)次數(shù)越多, 則其重要程度就會(huì)成正比增加； 反之, 如果其在數(shù)據(jù)集中的出現(xiàn)次數(shù)越多, 則其重要程度就會(huì)成反比下降. TF-IDF的主要思想是： 在語(yǔ)料集中選出若干關(guān)鍵詞, 通過(guò)關(guān)鍵詞對(duì)文本進(jìn)行區(qū)分. 作為關(guān)鍵詞的條件是其在一個(gè)文本中出現(xiàn)的頻率較高, 同時(shí)在語(yǔ)料集中其他文本中出現(xiàn)的頻率較低, 則該詞語(yǔ)即具有較好的類(lèi)別區(qū)分能力, 適用于分類(lèi).

TF是對(duì)詞數(shù)的歸一化表示, 用于防止其偏向較長(zhǎng)的文本. 因?yàn)殚L(zhǎng)文本中重復(fù)的詞匯可能會(huì)較多, 若只計(jì)算詞語(yǔ)總數(shù), 則可能導(dǎo)致偏差. 逆向文件頻率(IDF)是度量一個(gè)詞語(yǔ)在數(shù)據(jù)集中普遍重要性的指標(biāo). 計(jì)算某個(gè)詞語(yǔ)wi逆向文件頻率, 可由總文件數(shù)|D|除以包含該詞語(yǔ)wi文件的數(shù)目|{j:wi∈dj}|, 再將得到的商取對(duì)數(shù), 即得到理想文件頻率IDF：

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

如果某個(gè)詞語(yǔ)在一個(gè)文本內(nèi)擁有較高詞頻, 同時(shí)在整個(gè)語(yǔ)料集中擁有較低頻率, 則經(jīng)過(guò)計(jì)算后即可得較高的權(quán)重, 可作為候選關(guān)鍵詞. 因此, TF-IDF可過(guò)濾掉一些在數(shù)據(jù)集中經(jīng)常出現(xiàn)的詞語(yǔ), 同時(shí)保留重要的詞語(yǔ), 能區(qū)分出產(chǎn)生良好效果的詞語(yǔ).

1.3 算法設(shè)計(jì)

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

本文采用基于入鏈接關(guān)系的方法[13]計(jì)算詞語(yǔ)相關(guān)度：

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

1.3.2 短文本擴(kuò)充 短文本的詞匯量較少, 同時(shí)文本中重復(fù)詞語(yǔ)出現(xiàn)次數(shù)較少, 文本中的信息量較少, 在應(yīng)用傳統(tǒng)文本聚類(lèi)方法的情況下并不能得到較好的聚類(lèi)結(jié)果. 考慮到文本中存在大量的隱喻現(xiàn)象, 因而需將文本中的隱喻詞進(jìn)行擴(kuò)展. 首先基于維基百科得到其真正表示的含義, 然后對(duì)其真正含義的同義詞進(jìn)行擴(kuò)展, 目的是增加文本的信息量, 從而提高文本聚類(lèi)效果.

一般短文本中的隱喻詞會(huì)在維基百科中形成“歧義頁(yè)”主題頁(yè)面, 該主題頁(yè)面中列出了該詞語(yǔ)包含的幾種含義. 例如, 網(wǎng)絡(luò)中的“恐龍”一詞, 原意指出現(xiàn)于中生代的曾支配全球陸地生態(tài)系統(tǒng)超過(guò)1億6千萬(wàn)年之久的多樣化優(yōu)勢(shì)陸棲脊椎動(dòng)物, 但在現(xiàn)代中文網(wǎng)絡(luò)中, “恐龍”一詞多指對(duì)丑女的稱(chēng)呼, 在維基百科中對(duì)應(yīng)的頁(yè)面為“恐龍(俗語(yǔ))”, 由于此類(lèi)解釋多為維基百科中消歧義頁(yè)面的內(nèi)容, 所以在這里需要用到對(duì)隱喻詞進(jìn)行擴(kuò)展的頁(yè)面為維基百科中的消歧義頁(yè)面.

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

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

1.3.3 短文本聚類(lèi) 由于本文使用的語(yǔ)料集規(guī)模較小, 而k-means算法簡(jiǎn)單易行, 較適用于這種規(guī)模的數(shù)據(jù)集[14-15]. 但k-means算法易導(dǎo)致無(wú)法收斂到全局最小值, 因此本文采用二分k-means算法對(duì)短文本進(jìn)行聚類(lèi).

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

算法1基于隱喻詞擴(kuò)展的短文本聚類(lèi)算法.

forwiindj:

ifwi在維基百科中存在歧義頁(yè)面：

查詢(xún)wi的歧義詞

else:

查詢(xún)wi的old_text頁(yè)面, 發(fā)現(xiàn)其其他用法

lj={wlj,i|wi?wlj}

forwlj,iinlj:

計(jì)算詞語(yǔ)相關(guān)度

選取相關(guān)度最大的wlj,i作為真正解釋ep

for 鏈入 inep:

計(jì)算其與ep的相關(guān)度

選取相關(guān)度最大的3個(gè)頁(yè)面作為擴(kuò)展項(xiàng)對(duì)短文本進(jìn)行擴(kuò)充

將所有數(shù)據(jù)點(diǎn)視為一個(gè)簇

當(dāng)類(lèi)簇個(gè)數(shù)小于規(guī)定個(gè)數(shù)k時(shí)

對(duì)于每個(gè)類(lèi)簇

計(jì)算SSE值

進(jìn)行k=2的k-means聚類(lèi)

計(jì)算聚類(lèi)后的總誤差

選擇使總誤差最小的類(lèi)簇進(jìn)行一分為二的劃分.

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

本文采用F-measure方法[18]進(jìn)行聚類(lèi)結(jié)果評(píng)價(jià).F-measure方法通過(guò)查準(zhǔn)率與查全率得到綜合評(píng)價(jià)的F值, 其中查準(zhǔn)率是正確分配到一個(gè)類(lèi)簇中短文本的概率, 反映每類(lèi)中的內(nèi)容是否集中； 查全率是同一類(lèi)別的文本被分配到一個(gè)類(lèi)簇中的概率, 反映同一類(lèi)中的相似文本是否集中.

本文對(duì)教育、 音樂(lè)、 體育和科技4類(lèi)共1 600條新浪新聞標(biāo)題進(jìn)行聚類(lèi)分析. 通過(guò)對(duì)本文提出的基于隱喻詞擴(kuò)展的短文本聚類(lèi)算法進(jìn)行10次交叉實(shí)驗(yàn)后的聚類(lèi)結(jié)果如圖2所示. 與二分k-means聚類(lèi)算法相比,k-means聚類(lèi)算法對(duì)于聚類(lèi)中心的選擇具有較大隨機(jī)性, 易導(dǎo)致聚類(lèi)局限性. 對(duì)擴(kuò)展前后的短文本進(jìn)行10次交叉實(shí)驗(yàn), 采用平均值作為聚類(lèi)結(jié)果如圖3所示.

圖2 二分k-means聚類(lèi)結(jié)果Fig.2 Clustering results of bisecting k-means

圖3 k-means聚類(lèi)結(jié)果Fig.3 Clustering results of k-means

由圖2和圖3可見(jiàn), 二分k-means方法得到的結(jié)果相對(duì)較好, 擴(kuò)展前后的F值平均提高了18%, 基于隱喻詞擴(kuò)展后的短文本在聚類(lèi)結(jié)果上得到較大提高.

考慮到新聞標(biāo)題中出現(xiàn)的大量人名或新鮮詞匯在中文維基百科中可能查詢(xún)不到相關(guān)內(nèi)容, 因此若能考慮到這些因素, 并在本文基于隱喻詞擴(kuò)展的基礎(chǔ)上再次進(jìn)行擴(kuò)展, 所得到的聚類(lèi)結(jié)果可能更有效.

綜上可見(jiàn), 本文采用基于隱喻詞擴(kuò)展的方法對(duì)短文本進(jìn)行聚類(lèi)的效果得到了較大提升, 能對(duì)短文本文檔進(jìn)行有效歸類(lèi).