基于信息關(guān)聯(lián)拓?fù)涞幕ヂ?lián)網(wǎng)社交關(guān)系挖掘

劉錦文 邢凱 芮偉康 張利萍 周慧

摘要：針對(duì)目前基于監(jiān)督學(xué)習(xí)的關(guān)系抽取方法需要標(biāo)注大量訓(xùn)練數(shù)據(jù)和預(yù)先定義關(guān)系類型，提出了一種基于詞語共現(xiàn)信息構(gòu)建關(guān)聯(lián)網(wǎng)絡(luò)并在關(guān)聯(lián)網(wǎng)絡(luò)上進(jìn)行圖聚類分析的人物關(guān)系提取方法。首先，從新聞標(biāo)題數(shù)據(jù)獲得關(guān)聯(lián)度較高的500個(gè)人物對(duì)用于關(guān)系抽取研究；然后，抓取關(guān)聯(lián)人物對(duì)所在新聞數(shù)據(jù)，對(duì)其進(jìn)行預(yù)處理，并利用詞頻—逆向文檔頻率（TFIDF）得到人物對(duì)共現(xiàn)句子中的關(guān)鍵詞；其次，基于詞語共現(xiàn)信息得到詞語之間的關(guān)聯(lián)，進(jìn)而建立關(guān)鍵詞關(guān)聯(lián)網(wǎng)絡(luò)；最后，利用對(duì)關(guān)聯(lián)網(wǎng)絡(luò)進(jìn)行圖聚類分析以獲得人物關(guān)系。在關(guān)系抽取的實(shí)驗(yàn)中，與傳統(tǒng)基于詞語共現(xiàn)和模式匹配的中文實(shí)體關(guān)系提取方法相比，所提方法在準(zhǔn)確率、召回率和平衡F分?jǐn)?shù)（Fscore）上分別提升了5.5，3.7和4.4個(gè)百分點(diǎn)。實(shí)驗(yàn)結(jié)果表明，所提算法能夠在沒有標(biāo)注訓(xùn)練數(shù)據(jù)的條件下，有效地從新聞數(shù)據(jù)中抽取豐富且高質(zhì)量的人物關(guān)系數(shù)據(jù)。

關(guān)鍵詞：

社會(huì)關(guān)系抽取；共現(xiàn)統(tǒng)計(jì)；詞語關(guān)聯(lián)度；關(guān)聯(lián)網(wǎng)絡(luò)；圖聚類

中圖分類號(hào)： TP391.1 文獻(xiàn)標(biāo)志碼：A

0引言

目前，互聯(lián)網(wǎng)規(guī)模正在以指數(shù)級(jí)的速度膨脹，互聯(lián)網(wǎng)上的海量信息具有重要的價(jià)值。如何從互聯(lián)網(wǎng)上海量的信息中提取有價(jià)值的數(shù)據(jù)已經(jīng)成為了當(dāng)前研究的熱點(diǎn)問題。人物社會(huì)關(guān)系是人與人之間因?yàn)槟撤N社會(huì)存在而產(chǎn)生的關(guān)聯(lián)。人物關(guān)系提取則是挖掘這種重要關(guān)系的技術(shù)，它的主要任務(wù)是從多元結(jié)構(gòu)的互聯(lián)網(wǎng)數(shù)據(jù)中提取出人物關(guān)系三元組數(shù)據(jù)，例如，給定一個(gè)句子“姚明的妻子是葉莉”作為輸入，關(guān)系抽取算法應(yīng)該從中抽取出“〈姚明，妻子，葉莉〉”。這些事實(shí)三元組可以被用于構(gòu)建大規(guī)模、高質(zhì)量的知識(shí)庫；同時(shí)可以用于構(gòu)建海量知識(shí)圖譜和問答系統(tǒng)。

互聯(lián)網(wǎng)中存在大量的中文數(shù)據(jù)，但是關(guān)系抽取的研究主要集中在英語資源的處理上，中文語料庫上的研究較少。與英文相比，基于無結(jié)構(gòu)中文數(shù)據(jù)的人物社會(huì)關(guān)系提取研究存在如下難點(diǎn)：中文需要分詞，存在復(fù)雜的句式結(jié)構(gòu)和隱含的語義，基于單個(gè)句子進(jìn)行人物關(guān)系判定往往不夠準(zhǔn)確。目前大多數(shù)人物關(guān)系抽取研究將關(guān)系提取問題轉(zhuǎn)化為分類問題，需要訓(xùn)練數(shù)據(jù)和復(fù)雜的特征提取技術(shù)以及事先定義關(guān)系類型體系，訓(xùn)練數(shù)據(jù)往往需要大量的人工標(biāo)注工作，特征工程的設(shè)計(jì)需要大量的嘗試，構(gòu)造較為復(fù)雜。事先定義關(guān)系類型體系后，無法挖掘到新的關(guān)系類型。

針對(duì)這些問題，本文提出一種基于關(guān)鍵詞關(guān)聯(lián)網(wǎng)絡(luò)的無監(jiān)督人物關(guān)系提取方法。與上述方法有3點(diǎn)不同：

1）不依賴特定的訓(xùn)練集，面向海量的互聯(lián)網(wǎng)新聞數(shù)據(jù)，解決了有監(jiān)督問題的領(lǐng)域適應(yīng)性不強(qiáng)的問題；

2）以實(shí)體對(duì)共現(xiàn)的句子集合為研究對(duì)象，減小了依賴單個(gè)句子信息抽取關(guān)系帶來的誤差；

3）不需要事先確定的關(guān)系類型體系，能夠解決人工定義關(guān)系類型不全面的問題。

首先利用關(guān)聯(lián)分析技術(shù)得到候選人物對(duì)，然后抓取人物對(duì)共現(xiàn)新聞?wù)牟⑻崛≌臄?shù)據(jù)中的關(guān)鍵詞，最后構(gòu)建關(guān)鍵詞關(guān)聯(lián)網(wǎng)絡(luò)并進(jìn)行圖聚類得到人物關(guān)系；在實(shí)驗(yàn)部分，本文進(jìn)行了參數(shù)選擇實(shí)驗(yàn)并與傳統(tǒng)的基于詞共現(xiàn)和模式匹配的中文實(shí)體關(guān)系提取方法進(jìn)行了對(duì)比，驗(yàn)證了本文提出的關(guān)系挖掘方法的可行性和有效性。

1相關(guān)工作

二元人物關(guān)系提取主要有基于知識(shí)工程的方法和基于機(jī)器學(xué)習(xí)的關(guān)系抽取方法[1]?；谥R(shí)工程的方法需要大量的人力、物力去構(gòu)造知識(shí)庫，并且系統(tǒng)可移植性能不佳?；跈C(jī)器學(xué)習(xí)的方法已經(jīng)成為目前關(guān)系抽取領(lǐng)域的研究熱點(diǎn)。文獻(xiàn)[2]使用兩種基于特征向量的機(jī)器學(xué)習(xí)算法，Winnow和支持向量機(jī)（Support Vector Machine， SVM）在自動(dòng)內(nèi)容抽取測(cè)評(píng)會(huì)議（Automatic Content Extraction， ACE）的訓(xùn)練數(shù)據(jù)上進(jìn)行實(shí)體關(guān)系抽取，兩種算法的加權(quán)平均Fscore分別是73.08%和73.27%。文獻(xiàn)[3]針對(duì)中文實(shí)體關(guān)系提取中的句法特征的選取進(jìn)行了對(duì)比研究，并提出了新的句法特征。文獻(xiàn)[4]提出基于動(dòng)態(tài)卷積神經(jīng)網(wǎng)絡(luò)識(shí)別句子中是否含有謂詞表示的關(guān)系。文獻(xiàn)[5]提出了基于樹核的人物關(guān)系提取方法，應(yīng)用剪枝規(guī)則，語義信息的嵌入以及重采樣技術(shù)將Fscore提高3.5%。文獻(xiàn)[6]提出了面向大規(guī)模網(wǎng)絡(luò)文本的無指導(dǎo)中文的實(shí)體關(guān)系抽取方法。

在關(guān)鍵詞抽取研究方面，文獻(xiàn)[7]綜合考慮了關(guān)鍵詞在文章中的位置，詞性以及逆向文檔頻率（Inverse Document Frequency， IDF）等因素進(jìn)行關(guān)鍵詞提取。文獻(xiàn)[8]針對(duì)具有社會(huì)網(wǎng)絡(luò)特性的碎片文檔改進(jìn)現(xiàn)有的關(guān)鍵詞提取算法，從微博事件集合中提取代表該事件主要內(nèi)容的關(guān)鍵詞集合。在關(guān)鍵詞間關(guān)聯(lián)度計(jì)算方面，基于語料庫的統(tǒng)計(jì)方法通過計(jì)算詞匯的共現(xiàn)來衡量詞匯間的關(guān)聯(lián)。文獻(xiàn)[9]提出詞語關(guān)聯(lián)關(guān)系能夠有效地反映詞語間的關(guān)聯(lián)度；文獻(xiàn)[10]引入詞語關(guān)聯(lián)分布關(guān)系，提出基于互信息的詞語關(guān)聯(lián)衡量方法，提高了目標(biāo)詞語相似度計(jì)算的準(zhǔn)確性。

在聚類分析中，一種非常重要的特征模式聚類變體就是圖聚類[11]。圖聚類算法中clique算法是基于密度和網(wǎng)格的聚類算法，是一種啟發(fā)式的復(fù)雜網(wǎng)絡(luò)聚類算法，它采用子空間進(jìn)行聚類，適用于處理大數(shù)據(jù)集和高維數(shù)據(jù)。文獻(xiàn)[12]在2005年提出首個(gè)重疊社團(tuán)發(fā)現(xiàn)算法即派系過濾算法（Clique Percolation Method， CPM），此算法把社團(tuán)看作是由相互連通的完全子圖（k團(tuán)）組成。文獻(xiàn)[13]提出基于一種基于kclique覆蓋的圖挖掘算法；文獻(xiàn)[14]基于關(guān)鍵詞在文檔中的共現(xiàn)構(gòu)建關(guān)鍵詞網(wǎng)絡(luò)，并提出一個(gè)新的事件檢測(cè)算法，這個(gè)算法通過建立關(guān)鍵詞網(wǎng)絡(luò)和類似社會(huì)網(wǎng)絡(luò)分析中的社團(tuán)檢測(cè)算法來發(fā)現(xiàn)和描述事件。

2人物社會(huì)關(guān)系提取

人物關(guān)系，是指人物在其特定的社會(huì)范圍內(nèi)與他人之間存在和產(chǎn)生的關(guān)系。人物關(guān)系抽取屬于實(shí)體關(guān)系抽取的范疇，實(shí)體關(guān)系抽取的任務(wù)是從文本中識(shí)別出不同實(shí)體間的語義關(guān)系。如果這兩個(gè)實(shí)體是人物，那么它就是人物關(guān)系抽取。人物關(guān)系抽取正是要從文本中獲得人物關(guān)系，新聞數(shù)據(jù)中蘊(yùn)含許多人物關(guān)系，新聞中的人名一般較規(guī)范，利于人名識(shí)別的實(shí)現(xiàn)。本文以新聞文本數(shù)據(jù)為研究對(duì)象，主要利用詞語間的共現(xiàn)關(guān)系進(jìn)行人物關(guān)系提取。本文的人物關(guān)系提取系統(tǒng)的關(guān)鍵步驟包括數(shù)據(jù)預(yù)處理、關(guān)聯(lián)人物對(duì)提取、關(guān)鍵詞提取、詞語關(guān)聯(lián)計(jì)算與關(guān)鍵詞關(guān)聯(lián)網(wǎng)絡(luò)構(gòu)建、基于圖聚類的人物關(guān)系提取。

2.1數(shù)據(jù)預(yù)處理

數(shù)據(jù)預(yù)處理主要包括網(wǎng)頁正文提取、分句、分詞和詞性標(biāo)注、人名詞典構(gòu)建、語句選擇等處理過程。

1）網(wǎng)頁正文提取。在得到新聞網(wǎng)頁以后利用基于文本塊統(tǒng)計(jì)的新聞網(wǎng)頁提取算法獲得網(wǎng)頁的文本內(nèi)容。

2）分句。句子識(shí)別是進(jìn)行關(guān)系抽取的最初步驟，在從新聞網(wǎng)頁中抽取的正文數(shù)據(jù)中，句子和句子是相連的。需要對(duì)抽取出的純文本進(jìn)行分句操作，以文本中出現(xiàn)的中英文句號(hào)、問號(hào)、嘆號(hào)等句子終結(jié)符作為句子的分隔符。

3）分詞和詞性標(biāo)注。在這一步中，需要對(duì)已分好句的文本進(jìn)行分詞、詞性標(biāo)注與命名實(shí)體識(shí)別。在本文的研究中，使用中國(guó)科學(xué)院計(jì)算技術(shù)研究所開發(fā)的漢語語法分析系統(tǒng)（Institute of Computing Technology， Chinese Lexical Analysis System， ICTCLAS）對(duì)句子進(jìn)行分詞和詞性標(biāo)注。該系統(tǒng)是一個(gè)集分詞、詞性標(biāo)注，未登錄詞識(shí)別于一體的漢語詞法分析系統(tǒng)，其中采用了基于角色標(biāo)注的中國(guó)人名自動(dòng)識(shí)別方法。該系統(tǒng)人名識(shí)別的正確率和召回率分別達(dá)到95.57%和95.23%。本文采用ICTCLAS2011對(duì)新聞內(nèi)容進(jìn)行詞法分析，并把詞性標(biāo)注為“nr”“nr2”“nrf”的詞語作為人物名。

4）人名詞典構(gòu)建。本文關(guān)注的人名是一些社會(huì)上的名人或者有一定知名度的人名，普通人的人名在Web網(wǎng)頁中的內(nèi)容存在得較少。本文的人名詞典利用從微軟人立方關(guān)系搜索中獲取的數(shù)據(jù)進(jìn)行構(gòu)建，從中獲得包括體育人物、娛樂人物、政治人物和商界人物共4類人物的1391個(gè)人名。后續(xù)關(guān)系抽取研究基于這個(gè)人名詞典，對(duì)于人名中存在的同名問題，本文未作區(qū)分。

5）語句選擇。語句選擇是只在多語句文本中選擇最符合條件的語句，例如在研究人物關(guān)系時(shí)，首要的是在句子中至少出現(xiàn)2個(gè)或者2個(gè)以上的人物實(shí)體，這樣就可以篩選掉一些無研究?jī)r(jià)值的語句；以此類推，根據(jù)制定的相關(guān)規(guī)則，篩選出對(duì)后續(xù)處理可能有價(jià)值的句子，過濾掉無關(guān)語句，提高系統(tǒng)的處理效率。

2.2關(guān)聯(lián)人物對(duì)抽取

人物關(guān)系提取任務(wù)的第一步是要發(fā)現(xiàn)可能具有關(guān)系的人物對(duì)，然后是識(shí)別人物對(duì)的具體關(guān)系是什么。新聞標(biāo)題數(shù)據(jù)能夠高度概括和凝練新聞事實(shí)，其中也會(huì)包含有直接關(guān)聯(lián)的人物對(duì)，因此，本文利用標(biāo)題數(shù)據(jù)挖掘可能具有關(guān)系的人物對(duì)。在對(duì)數(shù)據(jù)進(jìn)行預(yù)處理以后，可以得到標(biāo)題數(shù)據(jù)中所有識(shí)別為人物名的詞，為了保證人名識(shí)別的準(zhǔn)確性，使用人名詞典對(duì)識(shí)別出的人名進(jìn)行噪聲過濾。對(duì)標(biāo)題數(shù)據(jù)進(jìn)行過濾后的人名兩兩進(jìn)行組合得到人物對(duì)。

統(tǒng)計(jì)所有標(biāo)題數(shù)據(jù)中每個(gè)人物對(duì)的出現(xiàn)頻率，人物對(duì)的出現(xiàn)頻率越高說明在新聞標(biāo)題中共現(xiàn)的次數(shù)越多，兩者存在關(guān)系的概率越高。通過這種方法過濾掉共現(xiàn)次數(shù)較少的無關(guān)人物對(duì)，減少后續(xù)處理的工作工作量。

對(duì)于剩下的共現(xiàn)次數(shù)較高的人物對(duì)，引入一種關(guān)聯(lián)度計(jì)算方法——上下文式關(guān)聯(lián)。根據(jù)兩個(gè)人名同時(shí)出現(xiàn)在一個(gè)新聞標(biāo)題中作為人物存在關(guān)聯(lián)的依據(jù)，然后基于統(tǒng)計(jì)的方法來量化這種關(guān)聯(lián)度，這里引入兩個(gè)人物實(shí)體（pi，pj）的條件概率：

P（pi|pj）=Fpi，pj/Fpj（1）

即pi，pj同時(shí)出現(xiàn)的標(biāo)題數(shù)目除以pj出現(xiàn)的標(biāo)題數(shù)目。如果人物對(duì)間計(jì)算出的條件概率較高說明人物之間的依賴關(guān)系較強(qiáng)，將式（1）中的條件概率和人物對(duì)共現(xiàn)次數(shù)結(jié)合來衡量人物對(duì)關(guān)聯(lián)度。

asso（pi，pj）=w1*P（pi|pj）+w2*coor（pi，pj）（2）

式（2）計(jì)算的人物對(duì)的關(guān)聯(lián)度，w1和w2分別是式（1）中的條件概率和人物對(duì)共現(xiàn)次數(shù)所占的權(quán)重。在實(shí)驗(yàn)中，調(diào)整w1和w2的取值，使關(guān)聯(lián)人物對(duì)的識(shí)別效果最佳。最終，將人物對(duì)按照式（2）計(jì)算的關(guān)聯(lián)度進(jìn)行排序，取關(guān)聯(lián)度最高的500個(gè)人物對(duì)用于后續(xù)人物關(guān)系提取研究。

2.3關(guān)鍵詞提取

在得到可能具有關(guān)系人物對(duì)以后，需要確定人物對(duì)之間的具體關(guān)系名，因此，需要挖掘與人物對(duì)有關(guān)的新聞數(shù)據(jù)進(jìn)行分析。本文以人物對(duì)pair=（pi，pj）為搜索條件，利用搜索引擎得到人物對(duì)的查詢結(jié)果新聞網(wǎng)頁。按照預(yù)處理部分介紹的方法對(duì)新聞網(wǎng)頁數(shù)據(jù)進(jìn)行處理，且句子中必須包含兩個(gè)人名，最終得到分詞和詞性標(biāo)注以及人名識(shí)別以后的句子集合。為了發(fā)現(xiàn)人物對(duì)相關(guān)的關(guān)鍵詞，對(duì)集合中的詞語進(jìn)行詞頻統(tǒng)計(jì)，因?yàn)閷?duì)人物關(guān)系提取作用最大的是動(dòng)詞和名詞，所以詞頻統(tǒng)計(jì)中只考慮動(dòng)詞和名詞，其他詞性的詞忽略。本文將所有詞語按照詞頻排序，詞頻統(tǒng)計(jì)結(jié)果表現(xiàn)為長(zhǎng)尾特性，即大多數(shù)的詞出現(xiàn)次數(shù)很少，少數(shù)的詞出現(xiàn)的次數(shù)較高，此處過濾掉詞頻極低的可能是噪聲的數(shù)據(jù)。

詞頻逆向文檔頻率（Term FrequencyInverse Document Frequency， TFIDF）算法在關(guān)鍵詞提取中較常使用，它原用于評(píng)估一個(gè)字詞對(duì)于一個(gè)文件集或者一個(gè)語料庫其中一份文件的重要程度，本文將用它來評(píng)估一個(gè)詞語對(duì)于表征人物對(duì)關(guān)系的重要度。其一般原理是：如果某個(gè)特征在某個(gè)人物對(duì)共現(xiàn)的句子中出現(xiàn)的詞頻較高，并且在其他人物對(duì)共現(xiàn)的句子集中很少出現(xiàn)，則認(rèn)為這個(gè)詞較能體現(xiàn)人物對(duì)的關(guān)系。本文中，詞語對(duì)于人物對(duì)關(guān)系的重要性為wij，如式（3）所示：

wij=tfij×idfj=tfij×ln（N/nj）（3）

其中：tfij指關(guān)鍵詞tj在人物對(duì)di共現(xiàn)的句子中出現(xiàn)的次數(shù)，idfi與詞tj共現(xiàn)的人物對(duì)數(shù)量成反比，N表示總的人物對(duì)數(shù)，nj指與詞tj共現(xiàn)的人物對(duì)數(shù)。將按詞頻過濾后的詞語重新按式（3）重要性進(jìn)行排序，每個(gè)人物對(duì)保留重要性最高的50個(gè)詞語。

2.4詞語關(guān)聯(lián)度計(jì)算與關(guān)鍵詞關(guān)聯(lián)網(wǎng)絡(luò)構(gòu)建

詞共現(xiàn)矩陣是詞共現(xiàn)模型的量化，詞共現(xiàn)模型是基于統(tǒng)計(jì)方法的自然語言處理領(lǐng)域的重要模型之一[7]。它的基本假設(shè)的基礎(chǔ)是：在大規(guī)模語料中，如果兩個(gè)候選詞經(jīng)常共現(xiàn)在文檔的同一窗口單元（如一句話、一個(gè)自然段等），則認(rèn)為這兩個(gè)詞在意義上是相互關(guān)聯(lián)的，并且共現(xiàn)的概率越高，其相互關(guān)聯(lián)越緊密[15]。

一個(gè)包含n個(gè)關(guān)鍵詞的共現(xiàn)矩陣被定義為：

其中： f（wi）， f（wj）分別代表詞語wi和wj的出現(xiàn)頻數(shù)， f（wi，wj）代表wi和wj共同出現(xiàn)在一個(gè)窗口的次數(shù)。參數(shù)p是一個(gè)可調(diào)的參數(shù)并且它的值在實(shí)數(shù)范圍內(nèi)。參考文獻(xiàn)[17]的設(shè)置，本文取p=50，式（5）顯示詞語之間的關(guān)聯(lián)度量是由詞語的共現(xiàn)頻率和單個(gè)的出現(xiàn)頻率所決定的。

定義1設(shè)M是得到的詞語共現(xiàn)矩陣，關(guān)鍵詞集合是W，Wi表示第i個(gè)關(guān)鍵詞，M轉(zhuǎn)化成對(duì)應(yīng)的關(guān)鍵詞關(guān)聯(lián)網(wǎng)絡(luò)圖G的定義為：

G={V，E}（6）

其中：V表示圖G的頂點(diǎn)集；Vi表示V中第i個(gè)頂點(diǎn)；V與W中元素一一對(duì)應(yīng)，即Vi對(duì)應(yīng)Wi；E表示圖G的邊集。如果2個(gè)頂點(diǎn)的關(guān)聯(lián)度大于一定的閾值，則在這2個(gè)頂點(diǎn)之間添加一條無向邊，即：

E={（Vi，Vj）|Vi，Vj∈V，Sim（Vi，Vj）>β}={（Vi，Vj）|Vi，Vj∈V，Wi，Wj∈W，Sim（Vi，Vj）>β}（7）

其中，0<β<1， β越大，詞語之間的關(guān)聯(lián)的要求越嚴(yán)格，則圖G越稀疏[18]。本文設(shè)置的β值為所有計(jì)算出的關(guān)鍵詞關(guān)聯(lián)度的中位數(shù)的T倍，實(shí)驗(yàn)部分將比較T值的選取對(duì)最終結(jié)果的影響。

2.5基于圖聚類的人物關(guān)系提取

關(guān)鍵詞關(guān)聯(lián)網(wǎng)絡(luò)建立完成以后，需要對(duì)關(guān)聯(lián)網(wǎng)絡(luò)進(jìn)行分析以發(fā)現(xiàn)人物關(guān)系。表示人物關(guān)系的關(guān)鍵詞與人物對(duì)會(huì)存在頻繁的共現(xiàn)關(guān)系，而且在關(guān)鍵詞關(guān)聯(lián)網(wǎng)絡(luò)中處于核心的位置，可以通過圖聚類的方式找到人物關(guān)系。本文使用基于團(tuán)（clique）的圖聚類方法，clique算法是基于密度和網(wǎng)格的一種聚類分析算法，對(duì)于大型高維空間數(shù)據(jù)的聚類分析具有很高的效率，能得到優(yōu)質(zhì)的聚類效果[19]。

本文利用文獻(xiàn)[13]中提出的方法檢測(cè)出關(guān)聯(lián)網(wǎng)絡(luò)中所有固定大小的clique，例如kclique。每個(gè)clique中包含若干個(gè)關(guān)鍵詞，這些關(guān)鍵詞在關(guān)聯(lián)網(wǎng)絡(luò)中都有邊相連，如3clique和4clique，分別包含3個(gè)關(guān)鍵詞和4個(gè)關(guān)鍵詞。在關(guān)鍵詞關(guān)聯(lián)網(wǎng)絡(luò)建立以后，本文使用復(fù)雜網(wǎng)絡(luò)分析工具NetworkX中的find_cliques（）函數(shù)查找關(guān)鍵詞關(guān)聯(lián)網(wǎng)絡(luò)中的所有clique。

為了利用識(shí)別出的clique挖掘人物對(duì)的關(guān)系詞，本文構(gòu)建clique之間的關(guān)聯(lián)圖。關(guān)聯(lián)網(wǎng)絡(luò)中檢測(cè)出的clique之間往往會(huì)存在共同的關(guān)鍵詞。例如，clique1={w1，w2，w3，w4}，clique2={w1，w2，w3，w5}具有共同的關(guān)鍵詞w1，w2，w3，則認(rèn)為兩個(gè)clique有關(guān)聯(lián)關(guān)系。clique間的共同出現(xiàn)關(guān)鍵詞組成集合V={w1，w2，…，wm}，共包含m個(gè)關(guān)鍵詞。以每個(gè)clique作為節(jié)點(diǎn)，clique之間的共現(xiàn)關(guān)鍵詞為邊的來建立clique關(guān)聯(lián)圖G*。

在clique關(guān)聯(lián)圖G*建立完成后，在關(guān)聯(lián)圖G*上進(jìn)行分析以挖掘在人物對(duì)關(guān)聯(lián)上重要性最高的關(guān)鍵詞。關(guān)鍵詞k在clique關(guān)聯(lián)圖G*中越多的邊中出現(xiàn)，說明該關(guān)鍵詞是關(guān)聯(lián)圖G*很多clique都包含該關(guān)鍵詞，則關(guān)鍵詞k對(duì)于識(shí)別人物對(duì)關(guān)系重要性越高。

為了識(shí)別人物對(duì)（pi，pj）之間的關(guān)系，對(duì)clique關(guān)聯(lián)圖G*中所有邊上的關(guān)鍵詞統(tǒng)計(jì)每個(gè)關(guān)鍵詞在圖中出現(xiàn)的邊數(shù)。假設(shè)集合V中的某個(gè)關(guān)鍵詞k在圖中邊上出現(xiàn)的次數(shù)為fqk，結(jié)合2.3節(jié)TFIDF（Term FrequencyInverse Document Frequency）計(jì)算出的關(guān)鍵詞權(quán)重wk，最終關(guān)鍵詞k對(duì)于人物對(duì)的重要性為Weightk：

Weightk=wk×fqk（8）

對(duì)于集合V中的所有關(guān)鍵詞按照式（8）計(jì)算的結(jié)果進(jìn)行排序，最后取集合V中所有詞語中計(jì)算結(jié)果最高的詞語作為人物對(duì)的關(guān)系詞。

3實(shí)驗(yàn)設(shè)置與結(jié)果分析

3.1數(shù)據(jù)集與評(píng)估方法

本文的實(shí)驗(yàn)數(shù)據(jù)包括如下內(nèi)容。

1）利用網(wǎng)絡(luò)爬蟲從騰訊新聞、百度新聞、網(wǎng)易新聞和新華網(wǎng)等主要新聞門戶網(wǎng)站上抓取的2006年1月到2015年5月的新聞標(biāo)題數(shù)據(jù)，共計(jì)67萬條新聞標(biāo)題，每條新聞標(biāo)題數(shù)據(jù)包括了新聞的URL和新聞的抓取時(shí)間。利用搜索引擎返回的所有候選關(guān)聯(lián)人物對(duì)搜索結(jié)果頁中的新聞網(wǎng)頁，共計(jì)22萬個(gè)網(wǎng)頁。

2）為了評(píng)估關(guān)系抽取的效果，需要對(duì)于實(shí)驗(yàn)中研究的500個(gè)人物對(duì)構(gòu)建關(guān)系評(píng)估集，即人物對(duì)的真實(shí)關(guān)系。本文利用微軟人立方關(guān)系搜索網(wǎng)站提供的結(jié)構(gòu)化人物詞條信息，共24.6萬的人物詞條。每個(gè)人物詞條中都包含人物的社會(huì)關(guān)系信息，從中可以獲得大量人物關(guān)系數(shù)據(jù)，用于構(gòu)建人物關(guān)系知識(shí)庫。從該知識(shí)庫中，可以查詢到本文研究的人物對(duì)的真實(shí)關(guān)系，本文將人物對(duì)的關(guān)系詞進(jìn)行同義詞擴(kuò)展，以獲得更多的關(guān)系。例如：“朋友”關(guān)系可以擴(kuò)展為“好友”“友人”“密友”等。擴(kuò)展以后的人物對(duì)真實(shí)關(guān)系作為實(shí)驗(yàn)的評(píng)估集，本文實(shí)驗(yàn)中抽取得到的人物對(duì)關(guān)系將與評(píng)估集中的真實(shí)關(guān)系進(jìn)行比較以評(píng)估關(guān)系抽取的效果。

關(guān)系抽取的效果使用準(zhǔn)確率（Precision）、召回率（Recall）和Fscore進(jìn)行評(píng)估。準(zhǔn)確率是所有檢測(cè)出關(guān)系詞的人物對(duì)中被確認(rèn)為正確關(guān)系的比率：

precision=Nhit/N（9）

其中：Nhit是檢測(cè)的關(guān)系正確的人物對(duì)數(shù)，N是所有檢測(cè)關(guān)系的人物對(duì)數(shù)。召回率是所有檢測(cè)出正確關(guān)系的人物對(duì)數(shù)占所有有關(guān)系的人物對(duì)數(shù)的比率：

recall=Nhit/N*（10）

其中：N*是實(shí)驗(yàn)中所有提取的人物對(duì)中存在關(guān)系的人物對(duì)。Fscore是對(duì)準(zhǔn)確率和召回率的調(diào)和平均數(shù)：

Fscore=2×precision×recallprecision+recall（11）

3.2實(shí)驗(yàn)結(jié)果分析

3.2.1實(shí)例分析

針對(duì)已提取出的人物對(duì)，查詢語料庫中人物對(duì)共現(xiàn)的句子，并按照2.3節(jié)的方法提取關(guān)鍵詞。取熱門人物對(duì)person pair=〈王菲，李亞鵬〉為例，抽取出的部分關(guān)鍵詞按照詞頻分布的情況如圖1所示，出現(xiàn)次數(shù)頻率較高的詞語占少數(shù)，大多數(shù)的詞只出現(xiàn)很少的次數(shù)。將所有的關(guān)鍵詞按照詞頻排序，過濾詞頻極低的數(shù)據(jù)，將剩余詞語用于建立關(guān)鍵詞關(guān)聯(lián)網(wǎng)絡(luò)。

利用過濾以后的關(guān)鍵詞進(jìn)行關(guān)聯(lián)計(jì)算，構(gòu)建關(guān)鍵詞關(guān)聯(lián)矩陣，然后按照2.4節(jié)中的方法構(gòu)建關(guān)鍵詞關(guān)聯(lián)網(wǎng)絡(luò)。按照2.5節(jié)中介紹的方法對(duì)該關(guān)鍵詞關(guān)聯(lián)網(wǎng)絡(luò)進(jìn)行分析，最終得到的person pair=〈王菲，李亞鵬〉的關(guān)系詞中重要性值最高的關(guān)鍵詞是“離婚”，因此，挖掘出的關(guān)系三元組〈王菲，李亞鵬，離婚〉。

3.2.2詞語共現(xiàn)窗口大小對(duì)結(jié)果的影響

為了評(píng)估參數(shù)對(duì)檢測(cè)結(jié)果的影響，本文分別設(shè)置實(shí)驗(yàn)比較窗口大小和閾值對(duì)于結(jié)果的影響。在2.4節(jié)中計(jì)算的詞語關(guān)聯(lián)度，對(duì)后續(xù)的關(guān)系詞抽取有較大的影響，根據(jù)詞語是否在同一個(gè)詞語窗口內(nèi)出現(xiàn)作為共現(xiàn)的依據(jù)?？紤]到互聯(lián)網(wǎng)上句子的長(zhǎng)度不一，所以取固定的窗口大小作為共現(xiàn)的依據(jù)。

在實(shí)驗(yàn)中，測(cè)試了6組窗口，窗口大小分別為[5，10，15，20，25，30]。詞語出現(xiàn)在窗口范圍內(nèi)則認(rèn)定為共現(xiàn)一次。圖2所示為最終關(guān)系挖掘的Precision，Recall和Fscore的效果。隨著窗口變大，更多的詞語能在窗口中共現(xiàn)，使得最終的關(guān)系提取的召回率提升，但是準(zhǔn)確率降低。計(jì)算出的Fscore值最高的窗口大小為windows length=10，因此，本文取10為窗口進(jìn)行共現(xiàn)統(tǒng)計(jì)。

3.2.3關(guān)聯(lián)度閾值β的選取

在由共現(xiàn)矩陣得到關(guān)聯(lián)網(wǎng)絡(luò)時(shí)，需要確定關(guān)聯(lián)度閾值的大小。取3.2.1節(jié)中的結(jié)果效果最好的窗口大小10，用不同的閾值β實(shí)現(xiàn)關(guān)聯(lián)網(wǎng)絡(luò)的建立。詞語間的關(guān)聯(lián)度要大于指定的閾值，才在關(guān)聯(lián)網(wǎng)絡(luò)中添加相應(yīng)的邊。本文在指定的不同閾值下，進(jìn)行關(guān)聯(lián)網(wǎng)絡(luò)構(gòu)建，并進(jìn)行后續(xù)的圖聚類得到人物關(guān)系數(shù)據(jù)，然后對(duì)人物關(guān)系的檢測(cè)結(jié)果進(jìn)行評(píng)估得到的結(jié)果如圖3所示。橫軸表示閾值相對(duì)于中位數(shù)的倍數(shù)T，縱軸是關(guān)系抽取的效果。三條曲線分別代表Precision、Recall和Fscore。在閾值比較低的時(shí)候系統(tǒng)的召回比較高，但也會(huì)引入大量的噪聲。隨著T的增大，準(zhǔn)確率提高，召回率逐漸降低?？梢姡撝翟酱髮?duì)于關(guān)系準(zhǔn)確性的判定較為謹(jǐn)慎，雖然降低了噪聲，但是增大了遺漏關(guān)系詞的風(fēng)險(xiǎn)。Fscore在T=2時(shí)候取得最大值，T>2以后，F(xiàn)score呈現(xiàn)下降的趨勢(shì)，因此在本實(shí)驗(yàn)中，選取T=2，即閾值β為中位數(shù)的2倍。

3.2.4人物關(guān)系提取效果

經(jīng)過以上實(shí)驗(yàn)結(jié)果分析，實(shí)驗(yàn)中將關(guān)鍵詞共現(xiàn)窗口大小設(shè)置為10，關(guān)聯(lián)度閾值β為中位數(shù)的2倍來建立關(guān)鍵詞關(guān)聯(lián)網(wǎng)絡(luò)，對(duì)本文研究的500個(gè)人物對(duì)進(jìn)行關(guān)系抽取。表1為利用本文的人物關(guān)系抽取方法得到的關(guān)系類型和每種關(guān)系的人物對(duì)數(shù)量，關(guān)系種類較為豐富，且本文的方法能夠挖掘出互聯(lián)網(wǎng)中實(shí)時(shí)出現(xiàn)的人物關(guān)系。

本文提出的關(guān)系抽取方法不僅不需要實(shí)現(xiàn)定義的關(guān)系類型體系，而且能保證關(guān)系抽取的有較好的效果。為了能夠?qū)υ摲椒ㄓ袦?zhǔn)確的評(píng)價(jià)，本文將其和文獻(xiàn)[20]中提出了詞共現(xiàn)關(guān)系抽?。╓ord CoOccurrence Relation Extraction， WCORE）方法的關(guān)系抽取方法在關(guān)系抽取結(jié)果上的準(zhǔn)確率、召回率和Fscore值進(jìn)行比較。文獻(xiàn)[20]中提出了方法首先利用詞共現(xiàn)來計(jì)算詞語相似度，然后采用模式匹配的技術(shù)來抽取實(shí)體之間的關(guān)系。對(duì)比方法中需要預(yù)先抽取種子模式，而待處理句子與種子模式進(jìn)行匹配的工程中存在較大的誤差。如表2所示的系統(tǒng)性能中，對(duì)比方法的準(zhǔn)確率、召回率和Fscore指標(biāo)都較低，本文的方法明顯優(yōu)于對(duì)比方法。

為了對(duì)算法的執(zhí)行時(shí)間進(jìn)行分析，本文在人物對(duì)的關(guān)鍵詞集合進(jìn)行關(guān)鍵詞關(guān)聯(lián)度計(jì)算后，進(jìn)行實(shí)驗(yàn)比較了本文提出關(guān)系抽取算法的和文獻(xiàn)[20]的方法在不同人物對(duì)數(shù)據(jù)量下的執(zhí)行時(shí)間情況。如圖4所示，其中橫軸表示算法處理的人物對(duì)數(shù)量分別是100，200，300，400，500，縱軸是人物關(guān)系抽取算法的總體執(zhí)行時(shí)間。從圖4中可以看到，隨著處理的人物對(duì)集合的增大，本文的方法呈現(xiàn)次線性（sublinear）增長(zhǎng)形式，說明本文的方法具有較好的伸縮性。與文獻(xiàn)[20]所提出的WCORE方法的比較中可以看到，在所有人物對(duì)數(shù)量下本文方法的執(zhí)行時(shí)間都少于對(duì)比方法，因此，可以看到本文提出的無監(jiān)督關(guān)系抽取方法能取得優(yōu)于對(duì)比方法的性能。

4結(jié)語

目前，中文關(guān)系抽取方面的研究較少，尤其是基于互聯(lián)網(wǎng)新聞?wù)Z料的人物關(guān)系挖掘研究更加匱乏。本文針對(duì)中文新聞數(shù)據(jù)中人物關(guān)系提取的任務(wù)，提出一種無監(jiān)督的人物關(guān)系提取方法利用詞語共現(xiàn)關(guān)系建立關(guān)鍵詞關(guān)聯(lián)網(wǎng)絡(luò)，并進(jìn)行圖聚類找到人物關(guān)系。在實(shí)驗(yàn)中，本文比較分析了詞語共現(xiàn)的窗口大小和關(guān)聯(lián)網(wǎng)絡(luò)建立時(shí)的關(guān)聯(lián)度閾值的大小對(duì)于挖掘人物關(guān)系詞結(jié)果的影響，實(shí)驗(yàn)結(jié)果顯示當(dāng)窗口大小為10，且閾值取中位數(shù)的2倍時(shí)，系統(tǒng)的表現(xiàn)最好。在對(duì)應(yīng)的參數(shù)設(shè)置下，本文的方法在準(zhǔn)確率和召回率方面優(yōu)于基于詞語共現(xiàn)和模式匹配的關(guān)系提取方法，且Fscore提升了4.4個(gè)百分點(diǎn)，執(zhí)行時(shí)間花費(fèi)上也少于對(duì)比方法。同時(shí)能夠在沒有標(biāo)注語料和預(yù)定關(guān)系類型的前提下，有效地完成從新聞?wù)Z料中挖掘人物關(guān)系的任務(wù)。

未來的工作中，將嘗試通過引入詞語位置信息改進(jìn)關(guān)鍵詞提取方法，并引入人名消歧策略解決人物關(guān)系中的人物同名問題。

參考文獻(xiàn)：

[1]

雷春雅，郭劍毅，余正濤，等.基于自擴(kuò)展與最大熵的領(lǐng)域?qū)嶓w關(guān)系自動(dòng)抽取[J].山東大學(xué)學(xué)報(bào)：工學(xué)版，2010，40（5）：141-145.（LEI C Y， GUO J Y， YU Z T， et al. Domain of automatic entity relation extraction based on seed selfexpansion and the maximum entropy machine learning [J]. Journal of Shandong University （Engineering Science Edition）， 2010， 40（5）： 141-145.）

[2]

車萬翔，劉挺，李生.實(shí)體關(guān)系自動(dòng)抽取[J].中文信息學(xué)報(bào)，2005，19（2）：1-6.（CHE W X， LIU T， LI S. Automatic entity relation extraction [J]. Journal of Chinese Information Processing， 2005， 19（2）： 1-6.）

[3]

董靜，孫樂，馮元勇，等.中文實(shí)體關(guān)系抽取中的特征選擇研究[J].中文信息學(xué)報(bào)，2007，21（4）：80-85.（DONG J， SUN L， FENG Y Y， et al. Chinese automatic entity relation extraction [J]. Journal of Chinese Information Processing， 2007， 21（4）： 80-85.）

[4]

LIANG Z， YUAN C， LENG B， et al. Recognition of person relation indicated by predicates [C]// Proceedings of the 4th CCF Conference on Natural Language Processing and Chinese Computing. Berlin： Springer， 2015： 313-324.

[5]

PENG C， GU J， QIAN L. Research on tree kernelbased personal relation extraction [C]// Proceedings of the 1st CCF Conference on Natural Language Processing and Chinese Computing. Berlin： Springer， 2012： 225-236.

[6]

秦兵，劉安安，劉挺.無指導(dǎo)的中文開放式實(shí)體關(guān)系抽取[J].計(jì)算機(jī)研究與發(fā)展，2015，52（5）：1029-1035.（QIN B， LIU A A， LIU T. Unsupervised Chinese open entity relation extraction [J]. Journal of Computer Research and Development， 2015， 52（5）： 1029-1035.）

[7]

王慶，陳澤亞，郭靜，等.基于詞共現(xiàn)矩陣的項(xiàng)目關(guān)鍵詞詞庫和關(guān)鍵詞語義網(wǎng)絡(luò)[J].計(jì)算機(jī)應(yīng)用，2015，35（6）：1649-1653.（WANG Q， CHEN Z Y， GUO J， et al. Project keyword lexicon and keyword semantic network based on word cooccurrence matrix [J]. Journal of Computer Applications， 2015， 35（6）： 1649-1653.）

[8]

周鵬，蔡淑琴，石雙元，等.基于關(guān)鍵詞抽取的微博輿情事件內(nèi)容聚合[J].情報(bào)雜志，2014，33（1）：91-96.（ZHOU P， CAI S Q， SHI S Y， et al. Content aggregation of microblogging public opinion events based on keyword extraction [J]. Journal of Intelligence， 2014， 33（1）： 91-96.）

[9]

樊興華，孫茂松.一種高性能的兩類中文文本分類方法[J].計(jì)算機(jī)學(xué)報(bào)，2006，29（1）：124-31.（FAN X H， SUN M S. A high performance twoclass Chinese text categorization method [J]. Chinese Journal of Computers， 2006， 29（1）： 124-31.）

[10]

趙軍，胡栓柱，樊興華.一種新的詞語相似度計(jì)算方法[J].重慶郵電大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，21（4）：528-532.（ZHAO J， HU S Z， FAN X H. Word similarity computation based on word link distribution [J]. Journal of Chongqing University of Posts and Telecommunications （Natural Science Edition）， 2009， 21（4）： 528-532.）

[11]

溫菊屏，鐘勇.圖聚類的算法及其在社會(huì)關(guān)系網(wǎng)絡(luò)中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件，2012，29（2）：161-163.（WEN J P， ZHONG Y. Graph clustering algorithm and its application in social network [J].Computer Applications and Software， 2012， 29（2）：161-163.）

[12]

PALLA G， DERNYI I， FARKAS I， et al. Uncovering the overlapping community structure of complex networks in nature and society [J]. Nature， 2005， 435（7043）： 814-818.

[13]

CAVIQUE L， MENDES A B， SANTOS J M A. An algorithm to discover the kclique cover in networks [C]// Proceedings of the 14th Portuguese Conference on Artificial Intelligence. Berlin： Springer， 2009： 363-373.

[14]

SAYYADI H， HURST M， MAYKOV A. Event detection and tracking in social streams [C]// Proceedings of the 3rd International AAAI Conference on Weblogs and Social Media. Menlo Park， CA： AAAI Press， 2009： 311-314.

[15]

雷鈺麗，李陽，王崇駿，等.基于權(quán)重的馬爾可夫隨機(jī)游走相似度度量的實(shí)體識(shí)別方法[J].河北師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2010，34（1）：26-30.（LEI Y L， LI Y， WANG C J， et al. Method on entity identification using similarity measure base on the weight of Markov random walk [J]. Journal of Hebei Normal University （Natural Science Edition）， 2010， 34（1）： 26-30.）

[16]

DAGAN I， LEE L， PEREIRA F C N. Similaritybased models of word cooccurrence probabilities [J]. Machine Learning， 1999， 34（1/2/3）： 43-69.

[17]

LIU J， HE L， LIN X， et al. A specific word relatedness computation algorithm for news corpus [C] // Proceedings of the 2nd International Workshop on Intelligent System and Applications. Piscataway， NJ： IEEE， 2010： 148-153.

[18]

王立霞，淮曉永.基于語義的中文文本關(guān)鍵詞提取算法[J].計(jì)算機(jī)工程，2012，38（1）：1-4.（WANG L X， HUAI X Y. Semanticbased keyword extraction algorithm for Chinese text [J]. Computer Engineering， 2012， 38（1）： 1-4.）

[19]

項(xiàng)響琴，李紅，陳圣兵.CLIQUE聚類算法的分析研究[J].合肥學(xué)院學(xué)報(bào)（自然科學(xué)版），2011，21（1）：54-58.（XIANG X Q， LI H， CHEN S B. Analysis and research on clique algorithm [J]. Journal of Hefei University （Natural Sciences）， 2011， 21（1）： 54-58.）

[20]

WANG J， YANG J， HE L， et al. Chinese entity relation extraction based on word cooccurrence [EB/OL]. [20151201] http：//www.ica.stc.sh.cn/picture/article/176/39/ff/b3ae3e1b4a5d96519bfb308c9d13/8ec889c154c748698978bb7bc5285199.pdf.