蔡愛杰，牟 童

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

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

蔡愛杰1，牟 童2

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)論

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

［1］李曉明.對中國曾有過靜態(tài)網(wǎng)頁數(shù)的一種估計.北京大學(xué)學(xué)報自然科學(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

李佳云)