基于圖數據庫的電影知識圖譜應用研究

陸曉華，張宇，錢進（.四川大學計算機學院，成都　60065；.成都航空職業技術學院，成都　60065；.重慶市通信服務產業有限公司移動服務分公司，重慶　40400）

基于圖數據庫的電影知識圖譜應用研究

陸曉華1，張宇2，錢進3
（1.四川大學計算機學院，成都610065；2.成都航空職業技術學院，成都610065；3.重慶市通信服務產業有限公司移動服務分公司，重慶404100）

0　引言

知識圖譜，也被稱為科學知識圖譜、知識域可視化或知識域映射地圖，是顯示科學知識的發展進程與結構關系的的一系列各種不同的圖形。它用可視化技術描述知識資源及其載體，挖掘、分析、構建、繪制和顯示知識及它們之間的相互聯系[1]。

具體來說，知識圖譜是把應用數學、圖形學、信息可視化技術、信息科學等學科的理論與方法與計量學引文分析、共現分析等方法結合，用可視化的圖譜形象地展示學科的核心框架、發展歷史、前沿領域以及整體知識架構的多學科融合的一種研究方法。它把復雜的知識領域通過數據挖掘、信息處理、知識計量和圖形繪制而顯示出來，揭示知識領域的動態發展規律，為學科研究提供切實的、有價值的參考[1]。

近些年，隨著大數據時代的到來，知識圖譜已經在其他領域有所應用。Google早在2012年就發布了“知識圖譜”，利用知識圖譜將Google的搜索結果進行知識系統化。當用戶在搜索某一關鍵詞時，Google就會在搜索結果的右邊給出該關鍵詞相關的信息，極大地方便了人們對信息的搜索。2013年2月，百度也推出了自己的知識圖譜。不同于基于關鍵詞搜索的傳統搜索引擎，知識圖譜可用來更好地查詢復雜的關聯信息，從語義層面理解用戶意圖，改進搜索質量。例如在百度的搜索框里輸入“馬云”的時候，搜索結果頁面的右側還會出現與“馬云”相關的人物，如圖1（a）所示；另外，對于包含邏輯關系的搜索語句例如 “馬云妻子”，百度能準確返回他的妻子“張瑛”，如圖1（b）所示。這就說明搜索引擎通過知識圖譜真正理解了用戶的意圖。

知識圖譜的構建主要包括知識單元的構建、知識單元間關系的構建和知識的可視化三個部分。其中前兩個部分是構建知識圖譜的最基本任務。以往的知識圖譜研究多基于文獻來進行研究，將關鍵詞、摘要等結構化信息可以直接作為知識單元進行構建。而大數據概念的興起，將研究者的目光集中到互聯網的海量數據上來。這其中的信息多為非結構化的文本，而且還含有大量雜訊，要對這些信息進行語義分析，提取出能用于可視化知識圖譜的知識單元并抽取出知識單元之間的關系就相當復雜了。另外，傳統的關系型數據庫經歷幾十年的發展，雖然具備較高的安全性和數據一致性，能夠依賴簡單的數據結構表達豐富的語義信息，但是對于知識圖譜這樣連接相對豐富，查詢復雜的數據結構，效率上考慮已經不適用了。在本文中，將對IMDB數據進行抓取并抽取出命名實體和實體關系，并通過Neo4j圖數據庫建立一個電影知識圖譜。

圖1　百度搜索知識圖譜應用

1　知識圖譜構建流程

知識圖譜的構建流程[2]通常包含下面幾個重要的環節：構建知識單元、單元關系抽取以及結構化展示。在實現上，流程通常如圖2所示。通常我們把數據獲取和數據清洗歸結為數據準備階段。構建知識單元的操作主要為提取文本中的命名實體信息；單元關系抽取主要是抽取出上一步提取出的命名實體之間的關系；結構化展示即為利用數據可視化技術對提取出的實體和關系進行可視化處理。

在實現上，構建知識圖譜通常首先會從維基百科、百度百科等資源中提取所需內容。本文的系統使用的電影及電影人數據來自于IMBD網站。利用爬蟲技術從互聯網空間中抓取的文本包含HTML標簽等雜訊，需要進行數據清洗。數據準備完成之后，我們通過統計機器學習算法提取文本中的命名實體，繼而通過特殊的正則模式匹配找出實體之間的關系，并將其持久化為csv文件。最后，我們將所有命名實體及實體關系導入Neo4j圖數據庫，以供數據可視化及知識圖譜內部聯系的查詢。

1.1數據來源

基于目前的研究和技術，通常的知識圖譜具有以下幾種類型[3]：（1）領域無關的知識圖譜；（2）特定領域的知識圖譜；（3）跨語言的知識圖譜。其中特定領域的知識圖譜，雖然內容不及領域無關知識圖譜廣泛，但是能夠囊括特定領域中的知識內容，更具有針對性，所以在特定領域中具有很好的應用。例如，宜信將知識圖譜技術成功應用在互聯網金融領域，創立了全球首個基于金融知識圖譜的金融云平臺，為客戶提供個性化的金融服務，取得了很好的效果。

知識圖譜類型的多樣化導致了知識圖譜構建方法的多樣化，一般來說，根據知識圖譜數據來源劃分，又可以將知識圖譜構建的方法分為基于網絡百科資源的知識圖譜構建方法、基于結構化數據的知識圖譜構建方法、基于半結構化數據的知識圖譜構建方法和基于非結構化數據的知識圖譜構建方法。

本文的系統數據采集自IMDB（互聯網電影數據庫）電影資料庫。IMDB是一個關于電影、電影演員、電視節目、電視明星、電子游戲和電影制作小組的在線數據庫。它是目前全球互聯網中最大的一個電影資料庫，里面包括了幾乎所有的電影，以及1982年以后的電視劇集。我們通過IMDB的電影及演員介紹頁面釆集各類實體信息，如圖3所示分別為IMDB電影頁面和演員頁面。通過對頁面標簽的正則匹配，我們可以提取出電影中的演職人員名單及其對應的角色；同樣，對于演員頁面可以提取出其參與拍攝的電影及其飾演的角色。由此，我們可以得到演員-飾演-角色的關系。另外，對于電影而言，還可以抽取出例如電影分級、發行時間、發行公司、電影類型、電影評分等屬性；同樣，演員還有身高、生日、性別等人物屬性。

圖2　知識圖譜構建流程

圖3　IMBD電影及人物頁面

1.2命名實體識別

知識圖譜構建流程中的知識單元構建通常是指提取文本中命名實體的識別。命名實體識別（Named Entity Recognition，簡稱NER），又稱作“專名識別”，是指識別文本中具有特定意義的實體，主要包括人名、地名、機構名、專有名詞等。命名實體識別技術是信息抽取、信息檢索、機器翻譯、問答系統等多種自然語言處理技術必不可少的組成部分。

基于統計機器學習的命名實體提取方法通常包括：隱馬爾可夫模型（Hidden Markov Model，HMM）、最大熵 （Maxmium Entropy，ME）、支持向量機（Support Vector Machine，SVM）、條件隨機場 （Conditional Ran-dom Fields，CRF）[4]。在這4種學習方法中，最大熵模型結構緊湊，具有較好的通用性，主要缺點是訓練時間復雜性非常高，有時甚至導致訓練代價難以承受，另外由于需要明確的歸一化計算，導致開銷比較大。而條件隨機場為命名實體識別提供了一個特征靈活、全局最優的標注框架，但同時存在收斂速度慢、訓練時間長的問題。一般說來，最大熵和支持向量機在正確率上要比隱馬爾可夫模型高一些，但是隱馬爾可夫模型在訓練和識別時的速度要快一些，主要是由于在利用Viterbi算法求解命名實體類別序列的效率較高。隱馬爾可夫模型更適用于一些對實時性有要求以及像信息檢索這樣需要處理大量文本的應用，如短文本命名實體識別。

在本文的系統實現中，我們的命名實體提取使用的是NLTK[10]庫中的最大熵算法。命名實體提取示例如圖4（a）所示。NLTK的命名實體識別使用的是MaxEnt分類器，其工作時有兩個原則：①總是試圖保持均勻分布（即最大化熵）；②保持其統計概率與經驗數據一致。NLTK提供了一個持久化的pickle文件，即為通過手動標記語料庫訓練出的MaxEnt分類器實例。

1.3實體關系抽取

在知識圖譜構建過程中，單元關系抽取通常在命名實體提取之后進行，就是提取出命名實體之間的聯系。基于目前的研究，已經有許多關系實體關系抽取方法被應用在各種實驗系統當中。這些方法所遵循的技術方法基本可以歸納為：基于模式匹配的關系抽取、基于詞典驅動的關系抽取、基于機器學習的關系抽取、基于Ontology的關系抽取以及混合抽取方法[5]。

在關系抽取研究領域，普遍使用基于模式匹配的關系抽取方法。這種抽取方法通過運用語言學知識，在執行抽取任務之前，構造出若干基于語詞、基于詞性或基于語義的模式集合并存儲起來。當進行關系抽取時，將經過預處理的語句片段與模式集合中的模式進行匹配。一旦匹配成功，就可以認為該語句片段具有對應模式的關系屬性。

圖4　

在本文的系統中，一旦我們提取出命名實體，就可以基于模式匹配提取出它們之間的關系。如前所述，我們通常會尋找指定類型的命名實體之間的關系。進行這一任務的方法之一是首先尋找所有 （X，α，Y）形式的三元組，其中X和Y是指定類型的命名實體，α表示X和Y之間關系的字符串。NLTK提供了特殊的正則匹配方式，可以方便對詞性、命名實體類別等進行模式匹配，提取出我們感興趣的元組。圖4（b）示例演示了使用NLTK抽取組織-地名關系的過程。同樣，我們可以使用NLTK編寫各種模式匹配抽取出人-人、人-電影之間的關系。

2　圖數據庫設計

在數據存儲領域，關系模型曾經是數據存儲的主流，近年來逐漸被NoSQL數據庫取代。NoSQL，泛指非關系型的數據庫，通常分為鍵值（Key-Value）存儲數據庫、列存儲數據庫、文檔型數據庫和圖數據庫。圖5（a）是來自db-engines網站的統計數據，展示了2013年以來各類數據庫系統的使用情況，其中，圖數據庫的使用率上漲了5倍多。

圖形數據庫中每個對象是一個節點，而對象之間的關系是一條邊。相對于關系數據庫來說，圖形數據庫善于處理大量復雜、互連接、低結構化的數據，這些數據變化迅速，需要頻繁的查詢——在關系數據庫中，由于這些查詢會導致大量的表連接，從而導致性能問題，而且在設計使用上也不方便。圖形數據庫適合用于社交網絡，推薦系統等專注于構建關系圖譜的系統。圖數據庫用圖來存儲數據，是最接近高性能的一種用于存儲數據的數據結構方式之一。

知識圖譜是基于圖的數據結構，它的存儲方式主要有兩種形式：RDF存儲格式和圖數據庫[6]。圖數據庫的代表有 Neo4J、Titan、OrientDB、DEX、AllegroGraph、GraphDB等。圖5（b）展示了目前比較流行的基于圖存儲的數據庫性能情況。基于S Jouili的研究，Neo4j[7]在存儲查詢等方面性能均優于其他圖數據庫，在工業上具有廣泛的應用[8]。

通常，現實生活中的實體和關系普遍都比較復雜當然，而且常常查詢涉及到1度以上的關聯查詢，如果使用關系型數據庫存儲知識圖譜會形成性能瓶頸。對于復雜的關系網絡，基于圖數據庫存儲優勢非常明顯。首先，在關聯查詢的效率上會比傳統的存儲方式有顯著的提高。當涉及到2~3度的關聯查詢時，基于知識圖譜的查詢效率會比關系型數據庫高出幾千倍甚至幾百萬倍。其次，基于圖的存儲在設計上會非常靈活，一般只需要局部的改動即可。例如我們有一個新的數據源，我們只需要在已有的圖譜上插入就可以。與此相反，關系型存儲方式靈活性方面就比較差，它所有的Schema都是提前定義好的，如果后續要改變，它的代價就非常高。最后，把實體和關系存儲在圖數據結構是一種符合整個故事邏輯的最好的方式。

在本文的系統中，我們設計的節點主要有兩種類型，分為Movie和Person類型，而關系類型主要有4種，分別為：ACTED_IN、DIRECTED、PRODUCED、WROTE。具體的，Movie還有電影分級、發行時間、發行公司、電影類型、電影評分等屬性；而Person也有身高、生日、性別等屬性。此外，所有的關系都是有向邊，例如ACTED_IN就是一條有Person指向Movie的邊，其屬性是演員在該電影中飾演的角色名。

3　系統實現及實驗結果

圖5　

本文的系統主要使用Python實現，主要分為3個模塊：數據采集模塊、數據提取模塊以及Neo4j圖數據庫導入模塊。數據采集模塊主要是通過Python的url-lib2庫爬取相關的IMDB網頁，然后使用BeautifulSoup庫清洗掉網頁中的HTML標簽，這樣得到的純文本數據以供后面的數據提取工作。命名實體的識別和實體關系的提取主要是通過Python的NLTK庫實現。我們將識別出的命名實體及關系分別存儲為csv文件，以方便后續導入Neo4j圖數據庫。在最新版本的Neo4j系統中，提供了一個大規模并行的可伸縮csv導入工具，該工具為Neo4j目錄./bin/neo4j-import。在使用neo4jimport時，需要將待導入的csv文件表頭定制為指定格式——顯示地節點指定 ID和 LABEL以及邊的START_ID和END_ID等。

本文所構建的電影知識圖譜示意如圖6所示，其中，（a）圖為全量數據可視化之后的局部截圖，（b）為隨機查詢的25條邊視圖以及它們之間的聯系；（c）為隨機查詢的25個節點視圖以及它們之間的聯系。從我們構建的電影知識圖譜，可以非常容易地分析電影節點及電影人節點，以及它們之間的關系，推理出演員之間是否認識或者間接認識，從而推斷出是否存在合作的可能等。

Neo4j系統提供了名為Cypher的查詢語言。Cypher是一種可以對圖形數據庫進行查詢和更新的圖形查詢語言，它類似于關系數據庫的SQL語言。Cypher的語法并不復雜，但是它的功能卻非常強大，它可以實現SQL難以實現的功能。在本文的知識圖譜中，我們可以通過編寫Cypher查詢語句，探索數據內部的關系。例如，六度分割理論中曾指出任何兩個人之間所間隔的人不會超過六個。只要數據足夠完整，釆用Cypher可以很容易地找到任何兩個人之間是通過哪些人聯系起來的，而這一點是SQL很難實現的。

程序1所示的Cypher語句，可以查詢Kevin Bacon 和Meg Ryan之間到最短路徑，如圖8（a）所示：Kevin Bacon和 Tom Cruise合作出演過電影 A Few Good Men；而Tom Cruise和Meg Ryan通過Top Gun結識。

相似地程序2所示的查詢語句，可以查詢到Tom Hanks和Tom Cruise兩位演員之間相距1跳的聯系。查詢結果如圖8（b）所示。

圖6　電影知識圖譜示例

知識圖譜的另一個應用是可以用于推薦系統。這其中，最著名的就是 Taher H.Haveliwala設計的PersonalRank算法[9]：在計算所有節點相對于用戶u的相關度時，PersonalRank算法從用戶u對應的節點開始游走，每到一個節點都以1-d的概率停止游走并從u重新開始，或者以d的概率繼續游走，從當前節點指向的節點中按照均勻分布隨機選擇一個節點往下游走。這樣經過很多輪游走之后，每個頂點被訪問到的概率也會收斂趨于穩定，這個穩定的概率就可用進行排名。在本文的系統中，我們可以編寫簡單的Cypher語句給Tom Hanks推薦好友，推薦結果如表1所示。

基于Neo4j圖數據構建的電影知識圖譜系統，具有界面友好，查詢方便，應用廣泛的特點，在工業上具有廣闊的前景。本文雖然提出了基于圖數據庫的電影知識圖譜研究實現，然而系統中還存在著許多不足和可以提高的地方。首先，我們只是提供了有限類型的邊和點節點；此外，僅僅提供了基于Cypher的查詢功能，還未集成相關的圖算法。后續工作中我們將結合Spark GraphX[11]，運用圖算法進行大規模的知識圖譜分析，進而可以方便的實現社區發現、用戶影響力、人群劃分等功能。

表1　Tom Hanks推薦結果

圖8　Cypher查詢示例

[1]秦長江，侯漢清．知識圖譜——信息管理與知識管理的新領域[J]．大學圖書館學報，2009（1）：30-37，96．

[2]金貴陽,呂福在,項占琴.基于知識圖譜和語義網技術的企業信息集成方法[J].東南大學學報：自然科學版,2014（02）:250-255. [3]梁秀娟.科學知識圖譜研究綜述[J].圖書館雜志,2009（6）:58-62.

[4]孫鎮,王惠臨.命名實體識別研究進展綜述[J].現代圖書情報技術,2010（6）:42-47.

[5]徐健,張智雄,吳振新.實體關系抽取的技術方法綜述[J].現代圖書情報技術,2008（8）:18-23.

[6]Abreu D D,Flores A,Palma G,et al.Choosing Between Graph Databases and RDF Engines for Consuming and Mining Linked Data[J]. Cold,2013.

[7]Webber J.A Programmatic Introduction to Neo4j[J].Addison Wesley Pub Co Inc,2012:217-218.

[8]Jouili S,Vansteenberghe V.An Empirical Comparison of Graph Databases[C].2013 International Conference on Social Computing.IEEE Computer Society,2013:708-715.

[9]Haveliwala T H.Topic-Sensitive PageRank:a Context-Sensitive Ranking Algorithm for Web Search[J].Knowledge&Data Engineering IEEE Transactions on,2003,15（4）:784-796.

[10]Loper E,Bird S.NLTK:The Natural Language Toolkit[C].Proceedings of the ACL-02 Workshop on Effective Tools and Methodologies for Teaching Natural Language Processing and Computational Linguistics-Volume 1.Association for Computational Linguistics, 2002:63-70.

[11]Xin R S,Gonzalez J E,Franklin M J,et al.GraphX:a Resilient Distributed Graph System on Spark[C].First International Workshop on Graph Data Management Experiences&Systems.ACM,2013:1-6.

張宇（1962-），教授，研究方向為模式識別，

錢進，工程師，研究方向為通信傳輸

Knowledge Graph;Graph Database;Neo4j

Implementation of Movie Knowledge Graph Based on Graph Database

LU Xiao-hua1，ZHANG Yu2，QIAN Jin3
（1．College of Computer Science Sichuan University,Chengdu 610065 2.Chengdu Aeronautic Polytechnic,Chengdu 610065；3.Chongqing Communcation Industry Services Co.Ltd.,Chongqing 404100）

1007-1423（2016）07-0076-08

10.3969/j.issn.1007-1423.2016.07.018

陸曉華（1988-），男，江蘇蘇州人，碩士，研究方向為機器學習、計算機視覺

2015-01-12

2016-02-25

知識圖譜是一種基于圖的數據結構，由節點和邊組成，其本質上屬于語義網絡。近年來，伴隨著大數據概念的提出，知識圖譜已經成為是當前的研究熱點。由于非結構化文本的知識提取和數據可視化這兩方面的技術難點，目前知識圖譜應用主要局限于搜索引擎和問答系統等方面。著眼于電影知識圖譜的設計與實現，通過引入圖數據庫Neo4j，為知識圖譜的實現提供一種新的思路。

知識圖譜；圖數據庫；Neo4j

Knowledge graph is a graph-based data structure,consisting of nodes and edges,and it is essentially a semantic network.In recent years, along with the proposed concept of big data,knowledge graph has become the current research focus.As technical difficulties of knowl-edge extraction of unstructured text and data visualization,the current applications of knowledge graph mainly limited in the aspects of search engine and Q/A system.Focuses on the design and implementation of movie knowledge graph,by the introduction of the Neo4j graph database,provides a new way of thinking for the realization of knowledge graph.