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

1.中國科學(xué)院 計(jì)算技術(shù)研究所 網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100190

2.中國科學(xué)院大學(xué)，北京 100049

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

融合馬爾可夫聚類的實(shí)體間關(guān)系消解方法*

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

1.中國科學(xué)院 計(jì)算技術(shù)研究所 網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100190

2.中國科學(xué)院大學(xué)，北京 100049

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

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

馬爾可夫聚類；知識(shí)庫；實(shí)體間關(guān)系

1 引言

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

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

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

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

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

本文組織結(jié)構(gòu)如下：第2章介紹相關(guān)工作；第3章研究中文短語語義相似度計(jì)算；第4章討論基于MCL的關(guān)系融合方法；第5章是實(shí)驗(yàn)和評(píng)價(jià)；第6章總結(jié)全文。

2 相關(guān)工作

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

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

總的來說，若采用基于分類的關(guān)系消解方法需要事先知道類別種類，然后選擇合適的特征訓(xùn)練分類器，當(dāng)特征選擇不恰當(dāng)?shù)臅r(shí)候，分類效果就會(huì)有所下降?；诰垲惖年P(guān)系消解方法在計(jì)算關(guān)系之間的語義相似度時(shí)，如何快速、簡單地計(jì)算語義相似度并且得到高質(zhì)量聚類結(jié)果是一個(gè)問題。

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

3 詞語相似度計(jì)算

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

3.1 同義詞詞林

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

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

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

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

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

3.2 相似度計(jì)算

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

3.2.1 義項(xiàng)相似度計(jì)算

前文介紹了《同義詞詞林》的編碼方式，義項(xiàng)相似度計(jì)算主要是對(duì)兩個(gè)編碼進(jìn)行比較，并得出計(jì)算結(jié)果，下面分幾種情況進(jìn)行介紹。

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

第二種情況，某一個(gè)義項(xiàng)以“@”結(jié)束，則表明此義項(xiàng)是獨(dú)一無二的，沒有同義詞，將這個(gè)義項(xiàng)和其他任何義項(xiàng)的相似度記為0。

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

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

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

Ad03A02=村里人全村人

Ad03A03@家里人

以計(jì)算“本地人”的義項(xiàng)“Ad03A01”和“村里人”的義項(xiàng)“Ad03A02”的相似度為例，因?yàn)閮蓚€(gè)義項(xiàng)在第5級(jí)出現(xiàn)不同，所以

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

算法1計(jì)算兩個(gè)詞語的相似度

輸入:兩個(gè)中文詞語A、B

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

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

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

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

4. sim(A,B)=0

5. For i from 1 to m

6. For j from 1 to n

7. 利用式（1）計(jì)算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只能計(jì)算兩個(gè)都在《同義詞詞林》中出現(xiàn)過的詞語，如果某個(gè)詞語沒有在《同義詞詞林》中出現(xiàn)，則它與任何其他詞語的相似度都記為0。

3.2.2 短語相似度計(jì)算

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

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

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

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

算法2計(jì)算兩個(gè)短語的相似度

輸入：兩個(gè)中文短語A、B

輸出：語義相似度

1.對(duì)A、B分別進(jìn)行分詞得到兩個(gè)詞序列seqA、seqB

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

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

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

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

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

7.返回max

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

4 基于馬爾可夫聚類的關(guān)系融合算法

馬爾可夫聚類算法（MCL）是一種基于圖的聚類算法。它首先將要聚類的元素表示成賦權(quán)圖[13]，圖中的點(diǎn)是聚類元素，圖中的邊通過計(jì)算元素間的相似度得到。具體地，當(dāng)兩個(gè)元素間的相似度為0時(shí)，其在圖中對(duì)應(yīng)的點(diǎn)之間沒有邊相連。否則，這兩個(gè)元素對(duì)應(yīng)的點(diǎn)之間存在一條邊，其權(quán)重等于二者的相似度。

4.1MCL背景介紹

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

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

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

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

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

4.2 基于MCL的關(guān)系融合算法

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

算法3基于MCL的關(guān)系融合算法

輸入:關(guān)系集合{r1r2…rn}，θ，τ

輸出:關(guān)系簇的集合{C1C2…Cm}

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

構(gòu)造圖G，G的鄰接矩陣為Mn×n

初始化鄰接矩陣Mn×n為對(duì)角形矩陣，其中對(duì)角線上元素都為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上進(jìn)行一次隨機(jī)游走，并用松弛系數(shù)τ規(guī)則化，得到M′

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

11.M=M′

12.repeat 9～11

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

14.返回所有關(guān)系簇

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

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

5 實(shí)驗(yàn)和結(jié)果

本文給出不同聚類方法進(jìn)行比較。首先介紹本實(shí)驗(yàn)采用的兩個(gè)關(guān)系消解數(shù)據(jù)集和實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)等。然后給出不同聚類方法在關(guān)系消解數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果和分析。

5.1 實(shí)驗(yàn)準(zhǔn)備

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

個(gè)數(shù)據(jù)集的部分關(guān)系。

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

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

需要指出的是，必須在聚類簇?cái)?shù)相同的情況下對(duì)不同聚類方法的純度進(jìn)行比較。這是因?yàn)椴豢紤]聚類結(jié)果的簇個(gè)數(shù)，在聚類結(jié)果是每簇只有一個(gè)元素的情況下，利用式（4）計(jì)算得到的純度是1。因?yàn)槊恳活愔挥幸粋€(gè)元素，所以式（4）退化為若干個(gè)1相加，最終計(jì)算結(jié)果也是1。但是實(shí)際結(jié)果肯定不應(yīng)該是每簇一個(gè)元素，在這種情況下計(jì)算得到的純度會(huì)與實(shí)際情況相差很大。因此在下文的實(shí)驗(yàn)結(jié)果中，只統(tǒng)計(jì)聚類結(jié)果的簇?cái)?shù)量與實(shí)際答案中簇?cái)?shù)量接近時(shí)的聚類純度，這樣可以有效避免上述情況。

本次實(shí)驗(yàn)的對(duì)比方法是層次聚類算法，采用相同的詞語語義相似度計(jì)算方法。在層次聚類過程中，計(jì)算簇間各點(diǎn)間距離的平均值作為簇間距離，通過設(shè)定閾值作為聚類終止條件。

5.2 實(shí)驗(yàn)結(jié)果

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

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

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

可以看出τ與聚類簇?cái)?shù)是正相關(guān)的，τ越大，聚類簇?cái)?shù)越多。這是因?yàn)棣釉酱?，在后續(xù)實(shí)驗(yàn)中，將通過調(diào)整τ，控制聚類結(jié)果簇?cái)?shù)。

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

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

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

5.2.2 不同聚類方法的比較

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

Table 5 Comparison of clustering result with 100 relations in 11 types表5 11個(gè)類別共100個(gè)關(guān)系的聚類結(jié)果比較

Table 6 Comparison of clustering result with 200 relations in 34 types表6 34個(gè)類別共200個(gè)關(guān)系的聚類結(jié)果比較

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

6 總結(jié)

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

[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.

附中文參考文獻(xiàn)：

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

[2]張靜,唐杰.下一代搜索引擎的焦點(diǎn):知識(shí)圖譜[J].中國計(jì)算機(jī)學(xué)會(huì)通訊,2012,9(4):64-68.

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

[5]臺(tái)德藝,王俊.文本分類特征權(quán)重改進(jìn)算法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(9):197-199.

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

[12]田久樂,趙蔚.基于同義詞詞林的詞語相似度計(jì)算方法[J].吉林大學(xué)學(xué)報(bào):信息科學(xué)版,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—），男，中國科學(xué)院計(jì)算技術(shù)研究所碩士研究生，主要研究領(lǐng)域?yàn)殚_放知識(shí)網(wǎng)絡(luò)，數(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—），女，中國科學(xué)院計(jì)算技術(shù)研究所博士，現(xiàn)為國家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心工程師，主要研究領(lǐng)域?yàn)樾畔踩?，?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年于南開大學(xué)獲得博士學(xué)位，現(xiàn)為中國科學(xué)院大學(xué)助理研究員，主要研究領(lǐng)域?yàn)殚_放知識(shí)網(wǎng)絡(luò)，社會(huì)計(jì)算，組合算法等。

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—），女，中國科學(xué)院大學(xué)博士，主要研究領(lǐng)域?yàn)殚_放知識(shí)網(wǎng)絡(luò)，數(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—），男，博士，中國科學(xué)院大學(xué)副研究員、碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)樯鐣?huì)計(jì)算，開放知識(shí)網(wǎng)絡(luò)，網(wǎng)絡(luò)安全分析等。

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—），女，博士，中國科學(xué)院計(jì)算所副研究員、碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)槲谋就诰颍琖eb搜索，復(fù)雜網(wǎng)絡(luò)分析，社會(huì)計(jì)算等。

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—），男，國家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心工程師，主要研究領(lǐng)域?yàn)樾畔踩?，?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(國家自然科學(xué)基金);the National Basic Research Program of China under Grant Nos.2013CB329602,2014CB340405 (國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(973計(jì)劃));the Science and Technology Nova Program of Beijing under Grant No.Z121101002512063 (北京市科技新星計(jì)劃項(xiàng)目);the Natural Science Foundation of Beijing under Grant No.4154086(北京市自然科學(xué)基金青年基金項(xiàng)目);the Research Program on Medical Imaging of the ChineseAcademy of Sciences under Grant No.KGZD-EW-T03-2(中科院醫(yī)學(xué)影像項(xiàng)目);the Technology Innovation and Transformation Program of Shandong Province under Grant No.2014CGZH1103(山東省自主創(chuàng)新及成果轉(zhuǎn)化專項(xiàng)).

Received 2015-09,Accepted 2016-12.

CNKI網(wǎng)絡(luò)優(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.