蔡愛杰，牟 童

(1.哈爾濱廣播電視大學(xué);2.中國科學(xué)技術(shù)大學(xué))

基于Web的實(shí)體關(guān)系發(fā)現(xiàn)的研究

蔡愛杰1，牟 童2

(1.哈爾濱廣播電視大學(xué);2.中國科學(xué)技術(shù)大學(xué))

作為Web內(nèi)容挖掘的重要組成部分，基于Web的命名實(shí)體提取與實(shí)體關(guān)系發(fā)現(xiàn)，以海量Web網(wǎng)頁中蘊(yùn)涵的海量實(shí)體及豐富的實(shí)體間關(guān)系為對象，充分利用Web數(shù)據(jù)本身的特點(diǎn)，發(fā)展一整套方法和技術(shù)，力求高效、準(zhǔn)確地提取Web網(wǎng)頁中的實(shí)體與關(guān)系.

Web;實(shí)體關(guān)系發(fā)現(xiàn);DIPRE

0 引言

Web網(wǎng)頁中存在豐富數(shù)量的命名實(shí)體，同樣，很多類型的實(shí)體間存在多種多樣的關(guān)系(Relation)，每一種關(guān)系實(shí)際對應(yīng)著一類事實(shí)(Fact)，將Web網(wǎng)頁中蘊(yùn)涵的豐富關(guān)系正確高效地提取出來，形成一個(gè)基于這些關(guān)系的事實(shí)(Fact)知識(shí)庫，不僅可以提供更高層次的信息服務(wù)，還可以為其他學(xué)科的研究提供強(qiáng)有力的支持.作為人類知識(shí)的載體，Web網(wǎng)頁包含了大量的命名實(shí)體以及它們之間的關(guān)系，網(wǎng)頁中的內(nèi)容是圍繞著其中的命名實(shí)體展開的，并反映了其中命名實(shí)體之間錯(cuò)綜復(fù)雜的關(guān)系.隨著Web規(guī)模的指數(shù)級膨脹［1］，如何在海量Web信息中定位自己所需的信息，成為一個(gè)非常緊迫的需要.

因此，為了滿足用戶日益增長的信息需求，需要研究新的技術(shù)，能夠從海量Web網(wǎng)頁中提取其中包含的各類命名實(shí)體和命名實(shí)體之間的關(guān)系，同時(shí)保留命名實(shí)體及實(shí)體關(guān)系同網(wǎng)頁、網(wǎng)頁中段落、網(wǎng)頁中句子間的對應(yīng)關(guān)系，在這樣結(jié)果的基礎(chǔ)上，一方面可以提供更高質(zhì)量的信息服務(wù)(搜索引擎，咨詢系統(tǒng))，滿足諸如上述信息需求的高質(zhì)量用戶查詢;另一方面，可以利用這些結(jié)果進(jìn)行Web知識(shí)的發(fā)現(xiàn)、總結(jié)和分析，得到更高層次的知識(shí)，更好地為社會(huì)生活服務(wù).

1 Web的實(shí)體關(guān)系發(fā)現(xiàn)的方法

對于一類關(guān)系R=(N1，N2，…，Nm)，Type(Ni)=Ti為R中第i個(gè)元素的實(shí)體類型，例如關(guān)系Birthday=(人名，出生日期)，第一個(gè)元素的實(shí)體類型為Person，第二個(gè)元素的實(shí)體類型為Time.顯然，若m=1，則R的提取對應(yīng)于Web上命名實(shí)體的提取，若m=2，則對應(yīng)于二元關(guān)系的提取，這也是最基本的關(guān)系發(fā)現(xiàn)問題，對于m≥3，則對應(yīng)于復(fù)雜關(guān)系的提取，此類問題有多種解決方法，或者將其分解為若干二元關(guān)系的提?。?］，或者將其視為一個(gè)整體，將二元關(guān)系的提取方法進(jìn)行擴(kuò)展，應(yīng)用到多元關(guān)系的提取上［3］.參考文獻(xiàn)［2］以對文本進(jìn)行句子層面的分析，對于任意兩個(gè)命名實(shí)體，利用實(shí)現(xiàn)訓(xùn)練好的分類器判斷兩者之間是否存在關(guān)系，從句子中找出可能存在關(guān)系的所有實(shí)體關(guān)系對，然后，根據(jù)實(shí)體間的關(guān)系構(gòu)建連接圖，從圖中提取出完全子圖，作為一個(gè)候選多元關(guān)系的實(shí)例.在參考文獻(xiàn)［3］中，為了發(fā)現(xiàn)Web上的top K個(gè)名人及其相關(guān)屬性，首先利用一個(gè)人工創(chuàng)建的pattern從Web上提取出一個(gè)名人集合，此pattern可以將人物的名字與性別、民族、籍貫同時(shí)提取出來，然后利用這個(gè)名人集合，基于DIPRE的思想，利用關(guān)系類型自動(dòng)擴(kuò)展等一系列方法，進(jìn)行名人信息的提取;在上述過程中，名人集合對應(yīng)的關(guān)系為四元關(guān)系，當(dāng)然，為了保證最后結(jié)果的高覆蓋率，在利用pattern進(jìn)行關(guān)系實(shí)例提取時(shí)，允許關(guān)系的某個(gè)元素為空;對于四元關(guān)系的提取，不同于參考文獻(xiàn)［2］，我們將四元關(guān)系看作本質(zhì)上與二元關(guān)系相同的關(guān)系提取，通過定義一個(gè)復(fù)雜靈活的pattern組成方式，實(shí)現(xiàn)了一種高效的多元關(guān)系提取方法.

DIPRE方法也是基于Web的實(shí)體關(guān)系發(fā)現(xiàn)的重要方法.在利用DIPRE方法進(jìn)行實(shí)體關(guān)系發(fā)現(xiàn)時(shí)，一個(gè)重要的前提是關(guān)系的類型固定，以固定類型的關(guān)系實(shí)例做為種子，進(jìn)行迭代循環(huán);顯然，Web中實(shí)體間關(guān)系有很多種，即便對于確定的兩類實(shí)體，它們之間存在的關(guān)系就有很多種，如果能夠?qū)⒛承?shí)體或者Web網(wǎng)頁中存在的全部實(shí)體間的關(guān)系類型確定下來，就可以利用這些關(guān)系的類型做為輸入，從Web網(wǎng)頁中發(fā)現(xiàn)大量這些類型關(guān)系的實(shí)例，相關(guān)的主要研究工作有參考文獻(xiàn)［4，5］.參考文獻(xiàn)［4］利用 Web 網(wǎng)頁中包含的人物間社會(huì)關(guān)系，對于一確定的人物，通過分析相關(guān)網(wǎng)頁，找出與他/她有某些類型社會(huì)關(guān)系的人物.利用Web的冗余特性，從Web網(wǎng)頁中創(chuàng)建這幾類關(guān)系對應(yīng)的關(guān)系種子，基于這些種子集合，利用DIPRE的思想，迭代得到一個(gè)較全的pattern集合，這些pattern集合中的pattern可以充分描述對應(yīng)的社會(huì)關(guān)系.這一研究與傳統(tǒng)的DIPRE方法不同，首先，它是借助與DIPRE方法，得到pattern集合，之后對于每一個(gè)實(shí)體(人物)，利用每一個(gè)pattern，找出對應(yīng)的關(guān)系人物，顯然，在利用實(shí)體+pattern進(jìn)行關(guān)系實(shí)體(人物)提取時(shí)，由于針對性很強(qiáng)，其效率會(huì)很高，并且，對于一個(gè)具體的實(shí)體，可能會(huì)得到一系列的候選關(guān)系實(shí)體，但由于Web信息的冗余性，候選實(shí)體中對應(yīng) pattern較多的實(shí)體為真實(shí)關(guān)系實(shí)體的概率要更大一些;其次，由于某些實(shí)體間關(guān)系為一對多，對于此類關(guān)系的處理，與一般的一對一的關(guān)系不同，需要保證關(guān)系實(shí)體提取的Recall，是一個(gè)需要一定研究才能保證較好效果的問題;再者，文中的人物社會(huì)關(guān)系是人工創(chuàng)建的(基于一個(gè)人物社會(huì)關(guān)系的 Ontology)，而實(shí)際上Web上存在很多種人物社會(huì)關(guān)系，如何將它們自動(dòng)提取并打上標(biāo)簽(利用關(guān)鍵詞描述)，利用這些關(guān)系類型和關(guān)系標(biāo)簽做為輸入，對每一個(gè)確定人物，得到他/她對應(yīng)的所有關(guān)系人物，也是需要深入研究的問題;并且，對人物可以這么做，對其他實(shí)體是否也一樣，還是需要有所變化，提出一個(gè)統(tǒng)一的模型或方法，也是需要進(jìn)一步思考的問題.參考文獻(xiàn)［4］僅是在此方面做了初步的工作，后續(xù)的工作會(huì)在上述方面做深入探討.

2 Web的實(shí)體關(guān)系發(fā)現(xiàn)的應(yīng)用

2.1 人物實(shí)體的關(guān)系發(fā)現(xiàn)的應(yīng)用

在各類命名實(shí)體中，人物是一類重要的實(shí)體;并且，當(dāng)前基于Web的社會(huì)網(wǎng)絡(luò)分析正在成為研究的熱點(diǎn)［6－9］，如何從Web網(wǎng)頁中提取其中蘊(yùn)涵的豐富的人物關(guān)系信息，進(jìn)而進(jìn)行社會(huì)網(wǎng)絡(luò)的構(gòu)建，進(jìn)行基于Web的研究，也是一個(gè)很重要的工作.參考文獻(xiàn)［6，7］是第一個(gè)在Web上進(jìn)行人物發(fā)現(xiàn)的系統(tǒng)，在此系統(tǒng)中，人物之間的關(guān)系由人物在同一篇網(wǎng)頁中共現(xiàn)標(biāo)識(shí)，繼而可以利用人物間關(guān)系進(jìn)行社會(huì)網(wǎng)絡(luò)的構(gòu)建，這樣關(guān)系定義方式過于簡單，關(guān)系的類型不夠自然且過于粗糙，有較大局限性.參考文獻(xiàn)［8］從某些人物的郵件收件箱開始，從中提取出聯(lián)系較為頻繁的人的名字和其他相關(guān)信息;然后，利用這些信息從Web上發(fā)現(xiàn)這些人物的個(gè)人主頁，然后基于人物的個(gè)人主頁和個(gè)人主頁鏈向的網(wǎng)頁，利用一個(gè)基于訓(xùn)練的CRF(conditional random fields)模型，從這些網(wǎng)頁中提取出對應(yīng)人物的地址、電話等聯(lián)系信息，利用這些信息和這些人物之間的關(guān)系網(wǎng)絡(luò)，進(jìn)行進(jìn)一步的社會(huì)網(wǎng)絡(luò)分析，其中人物間的關(guān)系由人物間頻繁的郵件聯(lián)系定義.于前面的工作不同，參考文獻(xiàn)［9］定義了四種存在于研究人員之間的四種關(guān)系：Co－author，Lab，Project和 Conference，人工建立了一個(gè)包含400多篇網(wǎng)頁的訓(xùn)練集，對其中包含的人物關(guān)系實(shí)例進(jìn)行了標(biāo)注，利用 C5.4［10］學(xué)習(xí)一個(gè)分類器，用于這四類關(guān)系的判別;然后，對于任意兩個(gè)人，首先利用搜索引擎得到包含這兩人名字的前五篇網(wǎng)頁，從中提取特征，利用分類器對兩人之間的關(guān)系進(jìn)行標(biāo)注.

2.2 實(shí)體關(guān)系發(fā)現(xiàn)用于檢測事件

除了人物關(guān)系的發(fā)現(xiàn)外，實(shí)體間關(guān)系的發(fā)現(xiàn)還可以用來檢測事件.參考文獻(xiàn)［11］將事件表示成事件相關(guān)的實(shí)體間的一系列關(guān)系，通過發(fā)現(xiàn)這些實(shí)體間的關(guān)系，來確定事件的發(fā)現(xiàn)，進(jìn)行事件探測.參考文獻(xiàn)［11］包含了四種事件相關(guān)的實(shí)體，對于每一種實(shí)體，它可與其他一種或多種實(shí)體結(jié)合在一起，形成一種關(guān)系，例如“＜Prize_Name，Person，Year＞”、“＜ Prize_Name，Person，Year，Area＞”或者“＜Person，Area＞”等，通過上面的事件實(shí)例可以形成這些關(guān)系的具體實(shí)例，利用這些關(guān)系實(shí)例做為種子，通過DIPRE方法可以發(fā)掘出提取這些關(guān)系的 pattern集合，繼而可以利用pattern發(fā)現(xiàn)更多此類的關(guān)系，基于這些關(guān)系，可以發(fā)現(xiàn)更多的諾貝爾頒獎(jiǎng)事件的實(shí)例.當(dāng)然，上述方法對于較為模式化的簡單事件來講，是非常適用的，而對于非模式化的事件(比如“9·11”事件等突然發(fā)生的新事件)或者較為復(fù)雜的事件，可能就不適用了.

此外，在基于Web的關(guān)系發(fā)現(xiàn)中，目前基于pattern方法工作的一個(gè)隱含的前提就是所要發(fā)現(xiàn)的關(guān)系在Web上有很豐富的關(guān)系實(shí)例，并且關(guān)系中元素在Web網(wǎng)頁中的分布相對比較集中，可以利用pattern來表示.但是，對于某些很有價(jià)值的實(shí)體間關(guān)系，雖然在Web上也有著豐富的關(guān)系實(shí)例，但其關(guān)素的分布在Web網(wǎng)頁中的分布并不是很集中，不同的元素在不同的句子中，很難用適當(dāng)?shù)膒attern來描述它們在Web網(wǎng)頁中出現(xiàn)的模式.對于這樣的問題，可以考慮對pattern的內(nèi)容進(jìn)行動(dòng)態(tài)擴(kuò)展，通過在關(guān)系中增加其他種類的相關(guān)實(shí)體，豐富原始關(guān)系，使得新關(guān)系的元素在Web網(wǎng)頁中分布變得集中，這樣就可以從網(wǎng)頁中產(chǎn)生出高質(zhì)量的pattern，用來描述此類關(guān)系在Web網(wǎng)頁中的出現(xiàn)模式.這樣，對于原始實(shí)體間關(guān)系的發(fā)現(xiàn)，就轉(zhuǎn)換成對等的新型實(shí)體間關(guān)系的發(fā)現(xiàn);當(dāng)然，如何進(jìn)行pattern內(nèi)容動(dòng)態(tài)擴(kuò)展、如何衡量最終得到的實(shí)體間關(guān)系實(shí)例的覆蓋率，還是需要深入研究的問題.此類問題是在實(shí)際的研究中發(fā)現(xiàn)的，目前并沒有相關(guān)的研究工作，也是下一步研究努力的一個(gè)方面.

3 結(jié)論

由于Web的飛速發(fā)展，Web中的內(nèi)容日趨豐富并包羅萬象，對于Web網(wǎng)頁中蘊(yùn)涵的各類命名實(shí)體進(jìn)行提取，并發(fā)現(xiàn)其中蘊(yùn)涵的豐富的實(shí)體間關(guān)系，是一件很有價(jià)值的事情，也是一件很有挑戰(zhàn)性的工作.本文從基于Web的實(shí)體間關(guān)系發(fā)現(xiàn)入手，介紹了當(dāng)前主要的研究工作，并對其中涉及的方法和技術(shù)進(jìn)行了分析.

［1］李曉明.對中國曾有過靜態(tài)網(wǎng)頁數(shù)的一種估計(jì).北京大學(xué)學(xué)報(bào)自然科學(xué)版，2003，39(3)：394－398.

［2］McDonald，Pereira R.F.，Kulick，S.，et al.Simple Algorithms for Complex Relation Extraction with Applications to Biomedical IE.In Proceedings of the 43nd Annual Meeting of the Association for Computational Linguistics(ACL－05)，2005：491－498.

［3］Yao Conglei.Discovering Top K Celebrities on the Web，2006.

［4］Yao Conglei，Di Nan ，Li Xiaoming.A Solution to Large Scale Extraction of Social Relations of Persons Based on the Web.To be appeared in Proc.of SEWM，2007.

［5］Hasegawa，T.，Sekine，S.，Grishman，R.Discovering Relations among Named Entities from Large Corpora.In Proc.of ACL－2004：415－422.

［6］Kautz H.，Selman B.，Shah M.Referral Web：combining social networks and collaborative filtering.Communications of the ACM，1997，40(3)：63-65.

［7］Harada M.，Sato S.，Kazama K..Finding authoritative people from the Web.Digital Libraries，2004.Proceedings of the Joint ACM/IEEE Conference on，2004：306 －313.

［8］Culotta A.，Bekkerman R.，McCallum A..Extracting social networks and contact information from email and the web.Proceedings of CEAS，F(xiàn)irst Conference on Email and Anti－Spam(CEAS).2004，7.

［9］Matsuo Y.，Mori J.，Hamasaki M.，et al.POLYPHONET：an advanced social network extraction system from the web.Proceedings of the 15th international conference on World Wide Web，2006：397 －406.

［10］Quinlan J.R..C4.5：Programs for Machine Learning.Morgan Kaufmann，California，1993.

［11］Cui，H.and Kan，M.Y.and Chua，T.S.Unsupervised learning of soft patterns for generating definitions from online news.In Proc.of the 13th international conference on World Wide Web，2004：90 －99.

The Study on Web－based Entity Relation Discovery

Cai Aijie1，Mu Tong2
(1.Harbin Open University;2.University of Science＆ Technology of China)

As the important basis of web content mining，current studies on web－based named entity extraction and entity relation discovery are researched，aim at developing a series of methods and techniques，to efficiently and effectively extract large numbers of named entities and entity relations from large scale web pages.

Web;Entity relation discovery;DIPRE

2010－08－14

李佳云)