融合馬爾可夫聚類的實體間關系消解方法*

常雨驍，龐 琳，賈巖濤，林海倫,2，王元卓，劉 悅，劉春陽

1.中國科學院 計算技術研究所 網(wǎng)絡數(shù)據(jù)科學與技術重點實驗室，北京 100190

2.中國科學院大學，北京 100049

3.國家計算機網(wǎng)絡應急技術處理協(xié)調(diào)中心，北京 100029

融合馬爾可夫聚類的實體間關系消解方法*

常雨驍1,2+，龐 琳3，賈巖濤1，林海倫1,2，王元卓1，劉 悅1，劉春陽3

1.中國科學院 計算技術研究所 網(wǎng)絡數(shù)據(jù)科學與技術重點實驗室，北京 100190

2.中國科學院大學，北京 100049

3.國家計算機網(wǎng)絡應急技術處理協(xié)調(diào)中心，北京 100029

隨著面向網(wǎng)絡大數(shù)據(jù)的知識庫的不斷出現(xiàn)，它們各自都包含海量的實體以及實體間的關系。然而許多有相同含義的關系并沒有統(tǒng)一名稱，針對這種情況，提出了一種基于馬爾可夫聚類（Markov cluster algorithm，MCL）的實體間關系融合方法。該方法首先計算關系間的語義相似度，然后利用關系間的語義相似度作為有邊的權重，構建無向圖，并利用馬爾可夫聚類算法進行聚類。實驗表明，該方法相比層次聚類和k-means聚類方法在聚類純度上有一定提高，并且更加方便使用。

馬爾可夫聚類；知識庫；實體間關系

1 引言

近年來，隨著互聯(lián)網(wǎng)、云計算等IT技術的不斷發(fā)展，網(wǎng)絡數(shù)據(jù)快速增長，網(wǎng)絡大數(shù)據(jù)給傳統(tǒng)的信息處理方式帶來了挑戰(zhàn)[1]。當然，大數(shù)據(jù)也帶來了更多機遇，因為大數(shù)據(jù)中包含著大量知識，其信息量遠遠超過紙質書籍。然而，機器要理解大數(shù)據(jù)中的知識并不容易，正如人類在學習新語言時需要“背單詞”一樣，機器也需要一本“字典”，因此需要構建一個“知識庫”來存放靜態(tài)知識，這些知識包括命名實體以及實體間關系，實體包括人、地點、機構等，關系則多種多樣，如父母、同學、同事等。這些知識以三元組的形式表示，三元組（S，P，O）作為知識的基本表示形式，其中S代表主體，P是客體，O是二者之間的某種關系，本文簡稱關系。一個簡單的三元組例子，如（美國，總統(tǒng)，奧巴馬），其中美國、奧巴馬是兩個實體，總統(tǒng)是二者間關系。

當前比較知名的知識庫有DBpedia、Freebase等，其中DBpedia包含1 900萬實體和1億關系，F(xiàn)reebase包含6 800萬實體和10億關系[2]。表面上看，知識庫中的關系數(shù)量巨大，但實際上有相當數(shù)量的關系只是名字不同意思相同，卻被當作兩種不同關系，如“父親爸爸家父”都表示“父親”的意思，但字面不完全一致，可能被當作不同關系，因此需要對同義但不同名稱關系進行消解。關系消解就是對不同關系的同義性進行判定，將同義不同名的關系進行對齊，映射到相同的標簽。關系消解可以提升知識庫整體數(shù)據(jù)質量，方便后續(xù)計算，如利用實體間關系進行推理，發(fā)掘實體間隱含關系等。

關系的消解實際是短文本的合并，現(xiàn)有的短文本合并方法主要有兩類：一類是基于聚類的方法。通過聚類算法將語義相似的短語聚合到同一簇中，達到消解的目的。另一類是分類的方法。分類方法需要事先確定短語的種類，然后對每一類短語準備訓練數(shù)據(jù)，通常需要大量人工標注，提取每類關系的特征，包括詞語本身特征、上下文特征等，然后訓練分類器再利用分類器將關系打上標簽，最后達到合并的目的。聚類和分類方法都各有優(yōu)缺點：分類方法的優(yōu)勢是只要訓練數(shù)據(jù)質量好，一般分類結果準確率較高，但缺陷是必須預先確定或估計出最終關系的種類，然后進行特征提取模型訓練，而當有新型關系出現(xiàn)時則無法處理了。另外分類方法容易出現(xiàn)過擬合現(xiàn)象，對不同數(shù)據(jù)集有不同的效果。聚類方法的優(yōu)點是不需要大量人工標注，易于實施，但缺點是聚類結果受閾值、簇合并策略影響較大。另外聚類方法時間開銷較大，分類方法只有模型訓練的時間開銷較大，但后續(xù)計算時間開銷不大。

在分析分類算法、聚類算法的各種優(yōu)缺點后，本文提出了一種“基于馬爾可夫聚類的實體間關系消解方法”。馬爾可夫聚類（Markov cluster algorithm，MCL）是一種基于圖的聚類算法。該算法由Dongen[3]提出。

具體的講，本文的創(chuàng)新點是提出了融合詞法和語義的相似度計算方法，然后給出了基于MCL的關系聚類方法。該方法與層次聚類方法相比，聚類純度指標有了一定提高，在兩種聚類算法簇數(shù)相同的情況下，在不同規(guī)模數(shù)據(jù)集上，MCL聚類純度平均能夠提高7%、20%。

本文組織結構如下：第2章介紹相關工作；第3章研究中文短語語義相似度計算；第4章討論基于MCL的關系融合方法；第5章是實驗和評價；第6章總結全文。

2 相關工作

關系消解通常采用基于短文本的分類和聚類兩大類方法?；诜诸惖年P系消解方法的代表性工作有文獻[4-6]。例如范小麗等人在文獻[4]中針對語料集不平衡情況下分類效果差的問題，通過調(diào)整正相關和負相關互信息特征的比例，區(qū)分相關特征，給出了改進的互信息特征選擇方法，提高了分類效果。在文獻[5]中，臺德藝等人為了提高在同類中頻繁出現(xiàn)，類內(nèi)均勻分布的具有代表性的特征詞的權重，引入了特征詞分布集中度系數(shù)改進IDF函數(shù)，用分散度系數(shù)進行加權，提出了TF-IIDF-DIC權重函數(shù)，在實驗中證明了基于TF-IIDF-DIC的K-NN文本分類算法宏平均比基于TF-IDF的算法提高了6.79%。

基于聚類的關系消解方法的代表性工作有文獻[7-11]。在文獻[7]中，Song等人為了解決在缺少上下文時短文本語義難以理解的問題，通過使用一個包含大量概念的知識庫，提升了算法對短文本的理解能力，開發(fā)了一個貝葉斯推理機制來概念化單詞和短文本，在聚類實驗中提升了聚類效果。在文獻[8]中，Yates等人提出了一種領域無關并且基于無監(jiān)督學習的關系消解方法。此方法通過概率模型計算關系之間以及包含關系的斷言式之間的相似度，依據(jù)相似度將具有相同含義的關系聚合在同一簇中，在TREC語料集上，此方法取得了97.3%的準確率和94.7%的召回率。在文獻[9]中，金春霞等人針對中文短文本特征詞詞頻低，存在大量變形詞的特點提出了一種基于《知網(wǎng)》擴充相關詞集構建動態(tài)文本向量的方法，利用動態(tài)向量計算中文短文本的內(nèi)容相似度，提升了聚類效果。

總的來說，若采用基于分類的關系消解方法需要事先知道類別種類，然后選擇合適的特征訓練分類器，當特征選擇不恰當?shù)臅r候，分類效果就會有所下降。基于聚類的關系消解方法在計算關系之間的語義相似度時，如何快速、簡單地計算語義相似度并且得到高質量聚類結果是一個問題。

針對上述情況，本文提出了基于馬爾可夫圖聚類的關系消解方法，并且給出了一種基于《同義詞詞林》的中文短語語義相似度計算方法。通過在不同規(guī)模數(shù)據(jù)集上實驗，證明了本文方法與傳統(tǒng)層次聚類方法相比，在聚類結果簇數(shù)相同時，純度有所提升。

3 詞語相似度計算

詞語相似度是兩個中文短語語義相似性的度量值，本文在利用MCL方法進行詞語聚類時，也需要計算詞語相似度。本文采用的是基于語義字典的詞語相似度計算方法，語義詞典選擇的是《同義詞詞林》，本文主要介紹詞語相似度計算。

3.1 同義詞詞林

《同義詞詞林》由梅家駒等人于1983年編纂而成，這本詞典不僅包含了一個詞語的同義詞，也包含了一定數(shù)量的同類詞，即廣義的相關詞[12]。哈爾濱工業(yè)大學利用眾多詞語相關資源，完成了一部具有漢語大詞表的同義詞詞林擴展版。同義詞詞林擴展版收錄詞語近7萬條，全部按意義進行編排。本文的詞語相似度計算使用同義詞詞林擴展版本。

《同義詞詞林》按照樹狀層次結構把所有收錄的詞條組織到一起，把詞匯分成大、中、小3類，小類下有很多詞群，詞群又進一步分成若干行。《同義詞詞林》共提供了5層編碼：第1級用大寫英文字母表示；第2級用小寫英文字母表示；第3級用二位十進制整數(shù)表示；第4級用大寫英文字母表示；第5級用二位十進制整數(shù)表示。如“Aa01C01=眾人人人人們”，稱Aa01C01是“眾人”的一個義項，具體編碼如表1所示。

Table 1 Thesaurus dictionary encode表1《同義詞詞林》詞語編碼表

表1中的編碼位是從左到右排列，第8位的標記有3種，分別是“=”、“#”、“@”。其中“=”代表“相等”、“同義”；“#”代表“不等”、“同類”，屬于相關詞語；“@”則表示“獨立”，即表示它在詞典中既沒有相關詞，也沒有同義詞。

由于漢語詞語在不同語境下有不同語義，《同義詞詞林》的編寫者也考慮到了這點，在《同義詞詞林》中一個漢語詞語可能對應多種不同編碼，稱詞語的每種編碼方式為詞語的一個義項。本文用sim(a,b)表示兩個義項或兩個詞語a和b的相似度。具體計算方法將在下節(jié)給出。

3.2 相似度計算

本節(jié)主要介紹如何基于《同義詞詞林》計算漢語短語語義相似度。首先介紹義項相似度計算方法，然后介紹短語相似度計算方法。

3.2.1 義項相似度計算

前文介紹了《同義詞詞林》的編碼方式，義項相似度計算主要是對兩個編碼進行比較，并得出計算結果，下面分幾種情況進行介紹。

第一種情況，當兩個義項編碼完全一致，但是編碼最后一位是“#”時，代表兩個義項是同類詞語，但意思不相同。如義項“Ab04A03#”有兩個詞語“女嬰”、“男嬰”，二者是同類詞語，但是意思不完全一致，這種情況下，將二者相似度記為0.5。

第二種情況，某一個義項以“@”結束，則表明此義項是獨一無二的，沒有同義詞，將這個義項和其他任何義項的相似度記為0。

第三種情況，兩義項a、b不完全一致，只有部分相同，則通過式（1）計算：

其中，i的取值為[1,5]，表示兩個義項在第i層開始不同。舉一個簡單例子說明：

Ad03A01=本地人當?shù)厝送林寥送林?/p>

Ad03A02=村里人全村人

Ad03A03@家里人

以計算“本地人”的義項“Ad03A01”和“村里人”的義項“Ad03A02”的相似度為例，因為兩個義項在第5級出現(xiàn)不同，所以

在一詞多義的情況下，以兩個詞最相近的義項的相似度作為兩個詞的相似度。如詞語“認真”有兩種意思，既可以形容人做事情認真仔細，也可以形容某人對于某事當真、信以為真。《同義詞詞林》本身考慮到了這種情況，“認真”在詞林中有兩個義項，分別是Ee27A01和Gb14A04，因此在計算時，用最相似的義項之間的相似度作為兩個詞的相似度，如算法1所示。

算法1計算兩個詞語的相似度

輸入:兩個中文詞語A、B

輸出:A和B的語義相似度sim(A,B)

1.如果A或B在《同義詞詞林》中沒有出現(xiàn)，sim(A, B)=0

2. 找出A的所有義項，記為{a1,a2,…,am}

3. 找出B的所有義項，記為{b1,b2,…,bn}

4. sim(A,B)=0

5. For i from 1 to m

6. For j from 1 to n

7. 利用式（1）計算sim(ai,bj)

8. if(sim(ai,bj)＞sim(A,B))sim(A,B)=sim(ai,bj)

9. End for

10. End for

11. 返回sim

算法1只能計算兩個都在《同義詞詞林》中出現(xiàn)過的詞語，如果某個詞語沒有在《同義詞詞林》中出現(xiàn)，則它與任何其他詞語的相似度都記為0。

3.2.2 短語相似度計算

上文介紹了義項相似度計算方法，這里將進一步介紹短語相似度的計算方法?！锻x詞詞林》只是包含了部分基本詞語的義項，而很多常見名詞性短語在《同義詞詞林》中是沒有的，這就需要新的方法計算相似度。

對于任意兩個中文短語A、B，利用分詞工具進行分詞并去除虛詞“的”“地”“得”等，分別得到短語A分詞后的詞序列a1a2…,an和短語B分詞后的詞序列b1b2…,bn。首先通過式（3）定義兩個相同長度詞序列的相似度，記兩個詞序列分別為Seq1、Seq2，其中Seq1=a1a2…an，Seq2=b1b2…bn。

其中，sim(ai,bi)的計算可參照式（1）。

式（2）的兩個詞序列Seq1、Seq2必須是等長的，ai、bi是兩個詞，進一步的，利用算法2計算兩個短語A、B的語義相似度。

算法2計算兩個短語的相似度

輸入：兩個中文短語A、B

輸出：語義相似度

1.對A、B分別進行分詞得到兩個詞序列seqA、seqB

2.記len為length(seqA)和length(seqB)最小的一個

3.從seqA取出len個詞，枚舉這些詞的一個排列S1

4.從seqB取出len個詞，枚舉這些詞的一個排列S2

5.if(sim(S1,S2)>max)max=sim(S1,S2)

6.重復3～5直到枚舉完所有可能的組合

7.返回max

在算法2中，利用ICTCLAS分詞工具進行中文分詞，通過算法2，可以計算任意兩個中文短語的相似度。

4 基于馬爾可夫聚類的關系融合算法

馬爾可夫聚類算法（MCL）是一種基于圖的聚類算法。它首先將要聚類的元素表示成賦權圖[13]，圖中的點是聚類元素，圖中的邊通過計算元素間的相似度得到。具體地，當兩個元素間的相似度為0時，其在圖中對應的點之間沒有邊相連。否則，這兩個元素對應的點之間存在一條邊，其權重等于二者的相似度。

4.1MCL背景介紹

MCL圖聚類是基于圖的聚類算法，一般聚類算法是將聚類對象看作是高維空間內(nèi)的點，通過一系列運算，將高維空間內(nèi)的點劃分成若干簇，使得同一簇內(nèi)各點之間的距離較近，而不同簇間各點距離較遠。圖聚類算法則是將聚類對象看成是一個有向圖或無向圖，目標是將圖內(nèi)點聚成若干簇，使得一個漫游者從簇內(nèi)的某個點“出發(fā)”，那么到達同一簇內(nèi)點的概率大于到達簇外點的概率。通過在圖上進行隨機游走過程，就可以發(fā)現(xiàn)在圖的某些區(qū)域邊是比較密集的，可以聚成一簇。MCL通過計算馬爾可夫鏈實現(xiàn)在圖上進行隨機游走。

MCL算法主要有兩個過程，分別是擴展（expansion）和膨脹（inflation），這兩個過程都是對狀態(tài)轉移矩陣進行操作。記一個狀態(tài)轉移矩陣為M，M的維數(shù)就是圖中點的個數(shù)，M不一定是對稱矩陣，M中的每一列表示某一時刻從某一個點出發(fā)，下一時刻到達其余點各自的概率。

擴展過程是模擬隨機游走過程，即取正整數(shù)e，對當前狀態(tài)轉移矩陣自乘e次，得到新的狀態(tài)轉移矩陣，這一過程相當于在原狀態(tài)轉移矩陣上進行了一次e步的隨機游走。例如一個只有兩個定點的圖，狀態(tài)轉移矩陣，狀態(tài)轉移矩陣中第i列第j行的元素表示如果漫游者當前從頂點i出發(fā)，則下一時刻他出現(xiàn)在頂點j的概率，狀態(tài)轉移矩陣的每列的和為1。假設旅行者在第0時刻從頂點1出發(fā)，則第2時刻，他仍然出現(xiàn)在頂點1的概率是0.6×0.6+0.4× 0.2=0.44。同理也可以得到他出現(xiàn)在其他頂點的概率，此時狀態(tài)轉移矩陣。

膨脹過程是一個矩陣規(guī)則化過程，是對狀態(tài)轉移矩陣的各列進行規(guī)則化，其處理公式如式（3）所示：

其中，M是狀態(tài)轉移矩陣；M*是規(guī)則化得到的矩陣；τ是松弛系數(shù)；k是M的行數(shù)；p是行下標；q是列下標。式（3）的作用是把轉移矩陣的列進行規(guī)則化得到規(guī)則化矩陣M*。例如當τ=2時，向量經(jīng)過式（3）規(guī)則化的結果是。

4.2 基于MCL的關系融合算法

4.1節(jié)介紹了MCL算法的相關背景，本文主要工作是利用MCL圖聚類算法，解決關系融合問題，如算法3所示。

算法3基于MCL的關系融合算法

輸入:關系集合{r1r2…rn}，θ，τ

輸出:關系簇的集合{C1C2…Cm}

1.令n為關系集合中關系的個數(shù)

構造圖G，G的鄰接矩陣為Mn×n

初始化鄰接矩陣Mn×n為對角形矩陣，其中對角線上元素都為1

2.For i from 1 to n

3.For j from i+1 to n

4.ifsim(ri,rj)>= θ Mij=sim(ri,rj)

5.elseMij=0

6.End if

7.End for

8.End for

9. 在M上進行一次隨機游走，并用松弛系數(shù)τ規(guī)則化，得到M′

10. if||M-M′||2＜0.05break

11.M=M′

12.repeat 9～11

13.使用廣度優(yōu)先遍歷計算圖G的每個連通分支，每個連通分支都是一個關系簇

14.返回所有關系簇

算法3中輸入是一系列關系，如“父親”、“爸爸”、“兒子”、“媽媽”等，輸出結果格式為每行是一個結果簇，包含若干關系，用空格分開。本文通過設定相似度過濾系數(shù)θ對相似度矩陣M的數(shù)據(jù)進行過濾，這樣做可以有效降低噪聲。因為有些關系如“兒子”和“兄弟”肯定是不同的關系，但是通過前文所述的語義相似度計算，兩者相似度并不會等于0，也就是在圖上“兒子”和“兄弟”兩個節(jié)點之間會產(chǎn)生一條邊，雖然這條邊權重不高，但是還是會給MCL的擴展過程帶來干擾。因此通過設定過濾系數(shù)直接把一些較低的相似度去掉，這樣可以有效提升結果質量。

為了保證可靠性，利用Dongen開發(fā)的開源工具[14]運行9～13行的MCL過程。Dongen在開發(fā)文檔中提到松弛系數(shù)τ將會對聚類簇數(shù)產(chǎn)生主要影響，因此在實驗中主要調(diào)節(jié)松弛系數(shù)τ和相似度過濾系數(shù)θ。

5 實驗和結果

本文給出不同聚類方法進行比較。首先介紹本實驗采用的兩個關系消解數(shù)據(jù)集和實驗的評價指標等。然后給出不同聚類方法在關系消解數(shù)據(jù)上的實驗結果和分析。

5.1 實驗準備

本文主要探討的是MCL圖聚類算法在關系融合上的效果。實驗數(shù)據(jù)集是從公開采集的百度百科頁面抽取得到的一系列形容人與人之間關系的短語，如“父親”、“母親”、“兄弟”等，并且通過人工標注，得到了其中200個關系的消解結果。通過人工標注，把這200個關系總共分成了34個類別，作為實驗的一個數(shù)據(jù)集。為了測試不同聚類方法在不同規(guī)模數(shù)據(jù)集上的聚類效果，進一步地，從這34類關系中隨機選擇其中的11個類別，這11個類別包含了100個關系，將這些關系作為另一個小規(guī)模的數(shù)據(jù)集。表2是第一

個數(shù)據(jù)集的部分關系。

Table 2 Sample of dataset表2 數(shù)據(jù)集部分樣例

本文選擇的聚類結果評價指標是純度。對于要聚類的元素集合，已知每個元素的類別標簽，記為?={C1C2…Cn}，Ci是第i個類別所有元素的集合。經(jīng)過聚類方法得到的結果集合為Ω={ω1ω2…ωm}，ωi是聚類結果中第i個簇，元素是通過聚類算法聚合而成。純度計算公式如式（4）所示：

需要指出的是，必須在聚類簇數(shù)相同的情況下對不同聚類方法的純度進行比較。這是因為不考慮聚類結果的簇個數(shù)，在聚類結果是每簇只有一個元素的情況下，利用式（4）計算得到的純度是1。因為每一類只有一個元素，所以式（4）退化為若干個1相加，最終計算結果也是1。但是實際結果肯定不應該是每簇一個元素，在這種情況下計算得到的純度會與實際情況相差很大。因此在下文的實驗結果中，只統(tǒng)計聚類結果的簇數(shù)量與實際答案中簇數(shù)量接近時的聚類純度，這樣可以有效避免上述情況。

本次實驗的對比方法是層次聚類算法，采用相同的詞語語義相似度計算方法。在層次聚類過程中，計算簇間各點間距離的平均值作為簇間距離，通過設定閾值作為聚類終止條件。

5.2 實驗結果

5.2.1 參數(shù)調(diào)整

首先對MCL算法的參數(shù)進行調(diào)整。根據(jù)算法3，MCL算法有兩個參數(shù)。首先看松弛系數(shù)τ對聚類簇數(shù)的影響，如表3所示。

Table 3 Relationship betweenτand cluster number表3 松弛系數(shù)τ對聚類簇數(shù)的影響

可以看出τ與聚類簇數(shù)是正相關的，τ越大，聚類簇數(shù)越多。這是因為τ越大，在后續(xù)實驗中，將通過調(diào)整τ，控制聚類結果簇數(shù)。

接下來，給出MCL算法中，相似度過濾系數(shù)θ對純度的影響。測試數(shù)據(jù)集為100個關系，共11個類別，對于不同的θ取值，分別進行聚類，并且對聚類得到11簇的結果計算其純度，結果如表4所示。

Table 4 Influence ofθon clustering purity表4 相似度過濾系數(shù)θ對聚類純度的影響

從表4的結果可以看出，當聚類結果是11簇的情況且θ取值0.5時，聚類結果的純度最高。也就是說，語義相似度計算得到的兩個短語相似度如果低于0.5，就可以認為兩者完全不同，θ起到了消除噪聲的作用。而隨著θ進一步加大，在超過0.5以后，無論如何調(diào)整參數(shù)，聚類簇數(shù)都不可能等于11。這是因為θ取值過大會把原圖上的邊去掉太多，導致有些不該獨立出來的部分獨立成一簇。從結果上看，在相同數(shù)據(jù)集上，當θ取值范圍在0.2～0.6內(nèi)，分別進行過濾并聚類后得到的結果，當結果簇數(shù)都為11時，純度最高和最低分別是0.772 2和0.613 8，最高比最低可以提升25%左右。因此，取θ=0.5進行后續(xù)實驗。

5.2.2 不同聚類方法的比較

表5是在11個類別100個關系的數(shù)據(jù)集上，MCL算法和層次聚類、k-means聚類方法的結果比較。表6是34個類別共200個關系的數(shù)據(jù)集上，MCL算法和層次聚類的結果比較。

Table 5 Comparison of clustering result with 100 relations in 11 types表5 11個類別共100個關系的聚類結果比較

Table 6 Comparison of clustering result with 200 relations in 34 types表6 34個類別共200個關系的聚類結果比較

在表5中，數(shù)據(jù)集有11個類別共100個關系，MCL聚類結果比層次聚類結果的純度平均提升了約20%，比k-means聚類提高約40%。在表6中，數(shù)據(jù)集有34個類別共200個關系，MCL聚類結果比層次聚類結果的純度平均提升了約7%，比k-means聚類提高約30%?？梢钥闯?，在不同規(guī)模的數(shù)據(jù)集下，MCL算法的效果都比層次聚類以及k-means聚類效果好。

6 總結

本文提出了一種基于MCL圖聚類的關系消解方法，并給出了一個簡單的基于《同義詞詞林》的計算中文短語語義相似度的算法。在利用MCL圖聚類算法的預處理階段，通過設定相似度過濾系數(shù)θ將圖上的邊進行過濾，并在相同數(shù)據(jù)集上進行實驗，通過調(diào)節(jié)θ，聚類純度可以得到25%的提升。另外，實驗表明，基于MCL圖聚類的關系消解方法比基于層次聚類的關系消解方法在聚類純度上可以平均提升7%、20%左右。目前，本文計算中文短語語義相似度是基于字典的方式，接下來將融合新的方法計算中文短語語義相似度，以進一步提升關系消解的準確度。

[1]Wang Yuanzhuo,Jin Xiaolong,Cheng Xueqi,et al.Network big data:present and future[J].Chinese Journal of Computers, 2013,36(6):1125-1138.

[2]Zhang Jing,Tang Jie.Knowledge graph:the focus of the next generation of search engine[J].Communications of the CCF,2012,9(4):64-68.

[3]Dongen S.A cluster algorithm for graphs[R].Amsterdam: CWI,Centre for Mathematics and Computer Science,2000.

[4]Fan Xiaoli,Liu Xiaoxia.Study on mutual information-based feature selection in text categorization[J].Computer Engineering andApplications,2010,46(34):123-125.

[5]Tai Deyi,Wang Jun.Improved feature weighting algorithm for text categorization[J].Computer Engineering and Applications,2010,46(9):197-199.

[6]Forman G.BNS feature scaling:an improved representation over TF-IDF for SVM text classification[C]//Proceedings of the 17th ACM Conference on Information and Knowledge Management,Napa Valley,USA,Oct 26-30, 2008.New York:ACM,2008:263-270.

[7]Song Yangqiu,Wang Haixun,Wang Zhongyuan,et al.Short text conceptualization using a probabilistic knowledgebase [C]//Proceedings of the 22nd International Joint Conference on Artificial Intelligence,Barcelona,Spain,Jul 16-22, 2011.Menlo Park,USA:AAAI,2011:2330-2336.

[8]Yates A,Etzioni O.Unsupervised methods for determining object and relation synonyms on the Web[J].Journal ofArtificial Intelligence Research,2009,34(1):255-296.

[9]Jin Chunxia,Zhou Haiyan.Chinese short text clustering based on dynamic vector[J].Computer Engineering and Applications,2011,47(33):156-158.

[10]Wu Wentao,Li Hongsong,Wang Haixun,et al.Towards a probabilistic taxonomy of many concepts,MSR-TR-2011-25[R].Microsoft Research,2011.

[11]Karandikar A.Clustering short status messages:a topic model based approach[D].Maryland:University of Maryland,2010.

[12]Tian Jiule,Zhao Wei.Words similarity algorithm based on Tongyici Cilin in semantic Web adaptive learning system [J].Journal of Jilin University:Information Science Edition,2010,28(6):602-608.

[13]Trudeau R J.Introduction to graph theory[M].Courier Corporation,2013.

[14]Dongen S.Performance criteria for graph clustering and Markov cluster experiments[R].Amsterdam:CWI,Centre for Mathematics and Computer Science,2000.

附中文參考文獻：

[1]王元卓,靳小龍,程學旗.網(wǎng)絡大數(shù)據(jù):現(xiàn)狀與展望[J].計算機學報,2013,36(6):1125-1138.

[2]張靜,唐杰.下一代搜索引擎的焦點:知識圖譜[J].中國計算機學會通訊,2012,9(4):64-68.

[4]范小麗,劉曉霞.文本分類中互信息特征選擇方法的研究[J].計算機工程與應用,2010,46(34):123-125.

[5]臺德藝,王俊.文本分類特征權重改進算法[J].計算機工程與應用,2010,46(9):197-199.

[9]金春霞,周海巖.動態(tài)向量的中文短文本聚類[J].計算機工程與應用,2012,47(33):156-158.

[12]田久樂,趙蔚.基于同義詞詞林的詞語相似度計算方法[J].吉林大學學報:信息科學版,2010,28(6):602-608.

CHANG Yuxiao was born in 1990.He is an M.S.candidate at University of Chinese Academy of Sciences.His research interests include open knowledge network and data mining,etc.

常雨驍（1990—），男，中國科學院計算技術研究所碩士研究生，主要研究領域為開放知識網(wǎng)絡，數(shù)據(jù)挖掘等。

PANG Lin was born in 1985.She received the Ph.D.degree from Chinese Academy of Sciences.Now she is an engineer at National Computer Network Emergency Response Technical Team/Coordination Center of China.Her research interests include information security and data mining,etc.

龐琳（1985—），女，中國科學院計算技術研究所博士，現(xiàn)為國家計算機網(wǎng)絡應急技術處理協(xié)調(diào)中心工程師，主要研究領域為信息安全，數(shù)據(jù)挖掘等。

JIAYantao was born in 1983.He received the Ph.D.degree from Nankai University in 2012.Now he is an assistant researcher at University of Chinese Academy of Sciences.His research interests include open knowledge network, social computing and combinational computing,etc.

賈巖濤（1983—），男，2012年于南開大學獲得博士學位，現(xiàn)為中國科學院大學助理研究員，主要研究領域為開放知識網(wǎng)絡，社會計算，組合算法等。

LIN Hailun was born in 1987.She received the Ph.D.degree from University of Chinese Academy of Sciences. Her research interests include open knowledge network and data mining,etc.

林海倫（1987—），女，中國科學院大學博士，主要研究領域為開放知識網(wǎng)絡，數(shù)據(jù)挖掘等。

WANG Yuanzhuo was born in 1978.He is an associate professor and M.S.supervisor at University of Chinese Academy of Sciences.His research interests include social computing,open knowledge network and network security analysis,etc.

王元卓（1978—），男，博士，中國科學院大學副研究員、碩士生導師，主要研究領域為社會計算，開放知識網(wǎng)絡，網(wǎng)絡安全分析等。

LIU Yue was born in 1971.She received the Ph.D.degree from University of Chinese Academy of Sciences.Now she is an associate professor and M.S.supervisor at Chinese Academy of Sciences.Her research interests include text mining,Web search,complex network analysis and social computing,etc.

劉悅（1971—），女，博士，中國科學院計算所副研究員、碩士生導師，主要研究領域為文本挖掘，Web搜索，復雜網(wǎng)絡分析，社會計算等。

LIU Chunyang was born in 1962.He is an engineer at National Computer Network Emergency Response Technical Team/Coordination Center of China.His research interests include information security and data mining，etc.

劉春陽（1962—），男，國家計算機網(wǎng)絡應急技術處理協(xié)調(diào)中心工程師，主要研究領域為信息安全，數(shù)據(jù)挖掘等。

Entity Relation Resolution Method by Integrating Markov ClusterAlgorithm*

CHANGYuxiao1,2+,PANG Lin3,JIAYantao1,LIN Hailun1,2,WANGYuanzhuo1,LIUYue1,LIU Chunyang3
1.Research Center of Web Data Science&Engineering,Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190,China
2.University of ChineseAcademy of Sciences,Beijing 100049,China
3.National Computer Network Emergency Response Technical Team/Coordination Center of China,Beijing 100029,China
+Corresponding author:E-mail:changyuxiao1990@163.com

Recent years,the development of knowledge bases is very fast.They store large scale of entities and the relations between entities.However,most of the relations which have the same meanings are not in the same form. It is necessary to resolute the relations.For this purpose,this paper proposes an approach based on Markov clusteralgorithm to cluster the relation with same meanings.Firstly,this paper calculates the semantic similarity between every two relations,and then it uses the relation similarity as weighted-edge to build a graph.Finally,this paper runs a Markov cluster algorithm on the graph and gets the result of relation clusters.Experiments show that the proposed approach has a higher purity than hierarchy cluster and k-means cluster.

Markov cluster;knowledge base;relation between entities

10.3778/j.issn.1673-9418.1509084

A

TP319

*The National Natural Science Foundation of China under Grant Nos.61173008,61232010,60933005,61402442,61402022, 61303244(國家自然科學基金);the National Basic Research Program of China under Grant Nos.2013CB329602,2014CB340405 (國家重點基礎研究發(fā)展計劃(973計劃));the Science and Technology Nova Program of Beijing under Grant No.Z121101002512063 (北京市科技新星計劃項目);the Natural Science Foundation of Beijing under Grant No.4154086(北京市自然科學基金青年基金項目);the Research Program on Medical Imaging of the ChineseAcademy of Sciences under Grant No.KGZD-EW-T03-2(中科院醫(yī)學影像項目);the Technology Innovation and Transformation Program of Shandong Province under Grant No.2014CGZH1103(山東省自主創(chuàng)新及成果轉化專項).

Received 2015-09,Accepted 2016-12.

CNKI網(wǎng)絡優(yōu)先出版:2016-12-14,http://www.cnki.net/kcms/detail/11.5602.TP.20161214.1122.002.html

CHANG Yuxiao,PANG Lin,JIAYantao,et al.Entity relation resolution method by integrating Markov cluster algorithm.Journal of Frontiers of Computer Science and Technology,2017,11(4)：511-519.