基于概念簇的多主題提取算法

2016-01-15 09:22:08馬甲林,張永軍,王志堅

智能系統學報 2015年2期

網絡出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20150302.1106.006.html

基于概念簇的多主題提取算法

馬甲林1,2，張永軍1,2，王志堅1

(1.河海大學計算機與信息學院，江蘇南京 211100； 2. 淮陰工學院計算機工程學院，江蘇淮安 223003)

摘要：現實世界存在著大量的多主題文本，多主題在信息檢索、圖書情報等領域有著廣泛的應用。傳統主題提取算法大多是針對文本整體提取一個主題，且存在缺乏語義信息、向量高維和稀疏等缺陷。以《知網》為知識庫，構建概念向量表示文本，根據概念的語義及上下文背景對同義詞進行歸并、對多義詞進行排歧，并利用概念間語義關系實現語義相似度計算；在此基礎上提出基于概念簇的多主題提取算法MEABCC，該算法通過對概念進行聚類，得到多個主題簇；在使用K-means算法進行概念聚類時，通過“預設種子”方法對其進行改進，以彌補傳統K-means算法對初始中心的敏感性所引起的時空開銷不穩定、結果波動較大的缺陷。實驗結果表明，該算法具有較好的準確率、召回率和F1值。

關鍵詞：語義；稀疏；上下文背景；知識庫；概念簇；多主題提取； K-means；MEABCC

DOI:10.3969/j.issn.1673-4785.201405066

中圖分類號：TP18 文獻標志碼：A

收稿日期：2014-06-01. 網絡出版日期：2014-03-02.

基金項目：國家自然科學青年科學基金資助項目(11201168).

作者簡介：

中文引用格式：馬甲林，張永軍，王志堅. 基于概念簇的多主題提取算法[J]. 智能系統學報， 2015, 10(2): 261-266.

英文引用格式：MA Jialin， ZHANG Yongjun, WANG Zhijian. Multi-topic extraction algorithm based on concept clusters[J]. CAAI Transactions on Intelligent Systems, 2015, 10(2): 261-266.

Multi-topic extraction algorithm based on concept clusters

MA Jialin1,2， ZHANG Yongjun1,2, WANG Zhijian1

(1. College of Computer and Information, Hohai University, Nanjing 211100,China; 2. School of Computer Engineering, Huaiyin Institute of Technology, Huaian 223003, China)

Abstract：There are a large number of multi-topic documents existing in the real world, and the extraction of multi-topic is widely used in the fields of information retrieval, library science and intelligence. In the traditional theme extraction algorithm, in most cases a theme is extracted for the whole text, which lacks of semantic information and has high-dimensional vector and sparse defects. Setting concept vectors to represent text based on the repository of cnki.net, merging synonyms and discriminating polysemy according to the semantic of concepts and context, thereby achieving the computation of semantic similarity in light of the semantic relation among concepts. The multi-topic extraction algorithm based on the concept of clusters (MEABCC) is proposed. The MEABCC acquires multiple topics by clustering concepts. The conceptual clustering made by K-means algorithm is improved through the method of presetting "default seed", which makes up the undulating time and space overlay and the unstable results. This happen to be caused by sensitivity to initial centers of traditional K-means algorithm. The experiments showed that MEABCC has good accuracy, recall and F1 values.

Keywords：semantic; sparsity; context; knowledge base; concept clusters; multi-topic extraction; K-means; MEABCC

通信作者：馬甲林. E-mail：majialin@126.com.

現實世界存在著大量的多主題文本，據統計36.85%文章包含多個主題，Sekine和Nobata主持的一項研究表明，日本新聞文章中的44.62%在談論多個話題。從文本中提取反映不同觀點的多個子主題，在信息檢索、圖書情報和信息安全等領域有著非常廣泛的應用[1-2]。大多數傳統主題提取方法是針對一篇文章從整體考慮提取一個主題，未能區分出文內混雜的多個子主題，文獻[3]認為子主題體現在主觀句子的語義中，提出CRF模型從主觀句子的極性角度提取子主題，該方法以形容詞、副詞詞性判斷句子語義的貶褒極性，未涉及其他語義信息；文獻[4]使用滑動窗口的方法可以從網絡評論文本提取局部子主題，適用于網絡評論文本；另外，常用的LDA(latent Dirichlet allocation)模型提出于2003年，該模型雖然目前使用廣泛，但LDA是一個完全基于統計的方法，在向量空間模型(VSM)下存在向量高維和稀疏、忽略詞匯語義及上下文背景等問題，同時提取過程受到同義詞和多義詞的干擾，因而在質量和效率上表現欠佳[3-5]。

本研究利用《知網》知識庫，采用概念向量模型(CVM)取代傳統VSM模型表示文本，同時在CVM模型下同義詞將被自動歸并，再根據上下文語義相關性對多義詞進行排歧處理；其次通過計算概念的語義相似度取代傳統相似度計算，在此基礎上提出基于概念簇的多主題提取算法(MEABCC)，該算法采用無監督學習的方法，通過改進經典K-means算法對文本概念進行聚類后得到多個子主題簇，其中，使用“預設種子”方法改進來K-means算法，以彌補傳統K-means算法K個初始中心選擇的隨機性所引起的時空開銷不穩定、結果波動較大的缺陷。

1概念向量模型

文本處理的首要問題是文本表示，本研究以中科院計算機語言信息工程研究中心董振東主持創立的《知網》為知識庫，建立基于概念的向量模型來表示文本。

1.1同義詞和多義詞處理

《知網》是一個以漢語和英語詞匯所代表的概念為描述對象,以揭示概念與概念之間以及概念所具有的屬性之間的關系為基本內容的常識知識庫。在《知網》中,詞匯語義描述被定義為概念。每一個詞可以表達為幾個概念，概念是由一種知識表示語言(DEF)來描述,這種用來描述概念的“詞匯”又叫義原，相比詞匯的規模,義原的數量很少。《知網》定義了1500多個義原，分為3類：基本義原、語法義原和關系義原，DEF中基本義原反映了概念的主要語義，例如：詞匯“愛好者”，在《知網》中用DEF的基本義原為：DEF={Human|人，*Fondof|喜歡，#WhileAway|休閑}，所表達的意思是：“愛好者”是個人，這個人喜歡某個東西，本詞語是和休閑相關[7]，它們之間存在語義相關性。在《知網》中，如果某個詞只有一個意思，那么這個詞對應唯一的概念，而多義詞往往對應多個概念，為了找到某個多義詞在文中的具體含義，作如下定義：

定義1 對于任意中文詞匯c0，在《知網》中描述其對應概念的DEF的基本義原集為{c1,c2,…,cm}，(m>=1)則稱c0與{ c1,c2,…,cm}屬于同一個語義類。

語義類不僅與概念對應，而且與描述概念的DEF對應，語義類揭示了詞語之間的語義聯系，描述某個DEF的基本義原在語義上是相關的，某個語義類和文章語境相符時，文中很可能出現該語義類包含的詞匯，利用這一語言現象可以消除詞匯歧義。如圖1：多義詞“水分”，在語義類包含{“植物”、“土壤”、“陽光”、“生長”}中“水分”的含義是指“物體內含有的水”，而在語義類包含{“經濟”、“數據”、“增長”、“報告”}中“水分”的含義是指“夾雜不真實成分”。

圖1　“水分”語義類示意圖 Fig.1　The semantic class schematic diagram of ′moisture′

由于漢語的復雜性，同一篇文章中一詞多義和同義詞的情況非常多，單純的機械詞頻統計方法無法處理涉及詞匯語義的問題，這是影響文本主題提取質量的一個重要因素。為了解決多義詞排歧和同義詞歸并問題，本研究利用《知網》,同義詞在概念映射階段被歸并到同一概念上；多義詞對應多個概念，根據語義類成員詞和上下文背景的語義相關性來為多義詞選擇適合該文語境的語義類。定位多義詞在文中最佳語義類的思路是：如果某個語義類所屬成員詞匯在本篇文中出現權值之和越大，說明該語義類比其他語義類更符合文章主題，則該語義類是該多義詞的在此文中最合適的語義類。詞匯wi在文章中所含的信息量H(wi)計算公式

(1)式中：ST表示待處理文本，TF(wi,ST)表示詞匯wi在文中出現的頻率，P(wi)為詞wi的概率分布。

定義2 多義詞c，它的第i個語義類Li權值為[7]

(2)式中：n為某個語義類Li成員詞在文中出現的個數。語義類權值越大，該語義類成員詞對文章主題的貢獻越大。

定義3多義詞c，在《知網》中對應多個語義類，選擇符合該文背景的最佳語義類公式為

(3)1.2 概念向量構建算法

傳統基于特征詞的向量空間模型(VSM)，認為向量是正交的，即詞匯之間互不相關。顯然，這和現實情況不符，眾所周知，文獻中各個詞匯之間存在著復雜的語義聯系[5]。利用《知網》知識庫，構建概念向量模型來表示文本，可以建立起詞匯之間語義聯系，為后續進一步的語義計算提供了可能。CVM構建過程首先對文本進行分詞和預處理后得到文本的特征集，然后對特征集中的每個特征進行概念映射；特征詞到概念的映射過程中大量的同義詞被歸并到相同的概念中，實現了強度較大的降維；其次利用《知網》概念描述語義的特點，根據語義類和上下文背景的相關性，實現多義詞排歧，其構建算法如下。

算法1概念向量構建算法

輸入：文本T；

輸出：文本T的概念向量T。

步驟如下：

3)依次查詢《知網》知識庫，對特征詞進行概念映射；

①查詢《知網》，若T的特征詞Cm對應唯一的概念，則Cm為單義詞或同義詞，直接獲取Cm的概念，轉至4)；

②: 若Cm對應多個概念，則Cm為多義詞，所以Cm對應多個語義類表示為{L1，L2，…,Lp}(p≥1) ,采用如下步驟為Cm進行多義詞排歧：

Fori=1 top

{

利用式(1)計算語義類Li所有成員詞匯的信息量；

利用式(2)計算Li權值；

}

Nexti;

4)對TG按照概念進行整理合并得到：

式中：Gq為TG集合中無重復的概念， q,i,j,k≤m；//現實同義概念的歸并；

5)輸出文本T對應概念向量T

2多主題提取算法

對于單主題提取，機械統計的主題提取方法通過詞頻統計按照權值大小抽取主題句，能夠得到質量達到簡單應用級別的主題句[6]。然而，現實中存在著大量的多主題文獻，單純的統計方法無法抽取多主題。本研究提出的MEABCC多主題提取方法是以1.2節提出的概念向量來表示文本，利用《知網》中義原的樹形層次體系結構計算義原相似度，進而計算概念的相似度，然后通過改進K-means算法對組成文本的概念進行聚類，形成多個子主題概念簇。

2.1概念相似度計算

相似度是衡量2個詞匯語義關系的一個重要指標，涉及到詞語的詞法、句法、語義甚至語用等多方面的信息。其中，對詞語相似度影響最大的是詞的語義。在《知網》中，詞匯被描述為概念，詞匯的相似度計算就轉化為對概念的相似度計算。詞語距離與詞語相似度之間有著密切的關系。2個詞語的距離越大，其相似度越低；反之，2個詞語的距離越小，其相似度越大[8]。

《知網》通過多個義原來描述概念，義原之間存在著各種復雜的關系，如：上下位關系、同義關系、對義關系等。其中，最重要的是上下位關系，所有的義原根據上下位關系構成了一個樹狀的義原層次體系, 所以可以通過計算義原距離得到概念的距離進而獲得概念的相似度[9]。假設2個義原在義原樹層次體系中的路徑距離為d，d的計算過程如下：

設義原集中的任意一個義原為wi，Li為義原wi在概念樹中的深度，a為距離初始閾值，b為滿足不等式max(L)

(4)任意2個義原wi、wj之間的距離定義

(5)式中：ωk表示第k種關系對應的權重，通常取ωk≥1。可以驗證，上述定義符合對距離函數的數學要求，式(4)、(5)反映出義原在義原層次樹中的位置越深，二者之間的距離越小，即越相似。

定義4 任意2個義原(wi,wj)之間的語義相似度

(6)式中：d是wi和wj在義原層次體系中的路徑長度,是一個正整數。θ是一個可調節的參數。

定義5設概念U和V分別由義原組(pu1, pu2,…, pun)和(pv1, pv2,…, pvm)描述，則U、V相似度為

定義6 概念U由義原組(p1, p2,…, pn)表示，概念集C由概念集合{C1,C2, …，Cm}組成，概念U和概念集C的相似度定義為U和C中所有概念相似度的最大值[7]:Sim(U,C)=Max{Sim(U,Ci)|Ci∈C}

(8) 2.2MEABCC算法

當前主題提取的方法主要有2類：基于機械統計的方法和基于語法語義分析的方法。統計的方法能夠有效利用文章表層信息抓住文章關鍵詞匯，收集文章原句輸出主題，優點是通用性好，適用于非受限區域，然而，其幾乎完全忽略詞匯語義信息，難以得到質量較高的主題，且不易提取多主題。基于語法語義分析的主題提取方法被認為比傳統的基于機械統計的方法更符合語言規律，提取的主題質量較高，但其要求極高的人工智能技術和完備的專家系統，以及領域受限等問題導致應用困難[10]。

本研究提出了基于概念簇的多主題提取算法(MEABCC)，其思路是：利用《知網》知識庫豐富的語義信息，將文本表示成為概念向量模型，改進K-means算法對概念進行語義聚類，形成多個子主題概念簇，進而得到文章對應的多個子主題關鍵詞集。

聚類算法有很多種，最典型有效的劃分法之一是K-means，K-means算法是從樣本中隨機取出K個樣本作為初始聚類中心，再通過迭代，計算每個類的中心，每個樣本被歸入到最近的中心，重新計算類中心，直到類中心不再改變。使用K-means算法進行聚類，首先要選取k個點作為初始聚類中心，然后進行反復的迭代，由于初始中心選擇具有隨機性，會導致結果和耗時隨不同的初始輸入而波動，從而引起算法不可預測的復雜度[11]。為了解決這一問題，借鑒傳統基于統計的主題提取思想，文章的主題很大程度上反映在詞共現上，做進一步的延伸，文章中的同義詞往往圍繞某一個主題，而同義詞在概念向量模型中表現為同一個概念，因而在多主題提取中，本研究提出根據概念向量中每個概念包含文章詞的個數大小進行排序，選取包含文章詞個數最多的前K個概念作為K-means聚類的初始中心的“預設種子”，這種方法可以克服K-means算法的對初始中心的敏感性。