本站小編為你精心準備了知識網絡中的關聯推理參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

《計算機研究與發展雜志》2016年第二期

摘要

網絡大數據時代的到來使得知識網絡中時空信息越來越豐富．現有的知識網絡描述模型對知識的時空信息刻畫不足．研究證明，利用網絡中知識的時空信息以及相關性，能夠提高網絡中知識間的關聯推理的準確率．針對以上問題，首先提出了一種包含時空信息的演化知識網絡表示模型，然后研究在該網絡模型上的關聯推理問題，提出了一種基于背包問題的知識間關聯推理方法．在多個數據集上的實驗證明了所提出的關聯推理方法的有效性以及對大規模知識網絡的適應性．

關鍵詞

關聯推理；演化知識網絡；背包問題；鏈接延展模式；知識庫

網絡大數據時代，數據不再僅僅是簡單的采集對象，其背后其實蘊含著大量豐富、復雜、關聯的知識［1］．當前網絡數據是廣泛可用的，所缺乏的只是從中提取知識的能力．有效利用網絡大數據價值的主要任務不僅僅是是獲取越來越多的數據，也需要從已有的數據中挖掘更多有用的知識［2］，構建成知識庫，便于對知識更充分地利用，因此基于網絡的大規模知識庫的構建是最近流行的一個研究方向，現有的大規模知識庫有YAGO［3－4］，DBpedia［5］，Probase［6］等．基于大規模知識庫的關聯推理是從海量信息中挖掘知識實現知識庫增長的有效手段之一［7］，其主要目的是利用已有的大規模知識網絡推理或者預測知識網絡中隱含的關系．目前，關聯推理已經在個性化推薦、社區發現、知識問答等方面得到廣泛應用［8］．現有的關于知識網絡中關聯推理的研究，采用的方法主要有有監督學習、半監督學習以及無監督學習等．目前的研究更多的是基于異構信息網絡的關聯推理，這里的異構信息網絡包含多種不同類型的實體與關系，例如人物、地點、組織機構、電影、論文等，以及它們之間可能產生的各種類型的關系．現實中典型的異構信息網絡有計算機科學文獻網絡DBLP和互聯網電影資料庫IMDB．

研究證明，在含有時間信息的異構網絡中進行關聯推理時，考慮時間信息得到的推理結果比未考慮時間信息得到的結果更好，例如文獻［9－10］．同樣地，由相關研究工作［11－12］證實，加入空間信息會對異構信息網絡上的關聯推理帶來更大的提升．例如，文獻［13］已證明，融合了空間信息的關聯推理可以獲得更好的推理結果，但是在文獻［13］中的研究，僅僅考慮了一種類型實體間的關聯推理，并非異構信息網絡．目前，基于異構信息網絡且對網絡中的時空信息加以利用進行關聯推理的相關研究還很少．針對知識網絡中時空信息的不斷豐富，而現有的一些知識網絡模型無法很好地刻畫這些信息的問題，我們首先提出一個融合時間與空間信息的演化知識網絡表示模型．與傳統的異構信息網絡不同，演化知識網絡中的點和邊都有相應的時間演化函數和空間演化函數，用于表示點和邊上的時間信息和空間信息．利用這些時空函數可以詳細刻畫出現實中的實體自身的時空演化特點以及實體間關系的時空演變．例如在學術網絡中，傳統的異構信息網絡只能推理多種類型的實體之間存在的不同類型的關系，卻沒有時序的概念，無法表達不同關系產生的先后順序、關系存在的時間范圍以及關系產生的地點等．

這些信息對于關系預測和推薦是不可或缺的重要因素，且對于關聯推理也具有重要意義．基于演化知識網絡提出了一種新的關聯推理方法．由于知識網絡中的關聯推理是知識挖掘的重要手段，而在知識挖掘中我們最關注的無疑是推理結果的正確性，因此我們提出新的關聯推理方法旨在提高關聯推理的準確率及對大規模數據的適應性．總結起來，本文貢獻可歸納為以下2點：1）提出了一個演化知識網絡表示模型，將知識的時空信息融入到整個知識網絡中，為知識的演化和計算提供更多的信息．2）研究了基于演化知識網絡的關聯推理方法．具體講，提出一種基于混合背包問題的關聯推理方法KP－LIM，提高關聯推理的準確率和推理效率．實驗證明，與當前流行的關聯推理方法相比，我們提出的關聯推理方法得到了更好的推理效果，在準確率上有8％～37％的提高，且在千萬規模的數據集上的實驗證明我們的方法依然有效．下面詳細介紹關聯推理的相關研究工作．目前主流的關聯推理方法是運用機器學習的算法進行關聯推理，基本上可被分為2類：有監督學習方法［13－18］和無監督學習方法［10，19－21］．其中文獻［13］是有監督學習方法的經典代表，它將關聯推理問題當成一個分類問題，利用經典的邏輯回歸方法訓練模型實關聯推理．盡管有監督學習的方法比較流行，但是它們也存在許多弊端，例如訓練復雜度高、平衡性較差、難以選擇合適的特征等．相反，無監督的方法不需要關于數據分布的先驗知識，避免了有監督學習的訓練復雜度高等問題，對于大規模數據具有更強的適應性．無監督的方法主要是通過定義一些指標來刻畫網絡中實體間的相似度來實現關聯推理，例如文獻［19］是近期無監督關聯推理的典型代表，它以經典的共同鄰居（commonneighbour，CN）方法為基礎，加入節點連通性、邊連通性以及部分時間信息等信息進行關聯推理，但該方法只利用了網絡中的局部信息．我們的提出的推理方法KP－LIM也是一種無監督學習方法，該方法定義了一個拓撲特征———鏈接延展模式（LE模式），將全圖的結構特征以及網絡中的時空間信息融入到背包問題的參數中，利用背包問題的求解對LE模式進行選擇，再利用選出的模式實現關聯推理．另一方面，目前流行的關聯推理方法大部分是應用于異構信息網絡上的，即網絡中的實體與邊的類型是多種多樣的，例如文獻［9，15，22］等．

近期又有許多工作將時間信息融入了異構信息網絡中，并利用這些信息來提高關聯推理的準確性．我們提出的演化知識網絡模型既包含知識的時間信息也包含知識的空間信息，并利用這些信息進一步提高了關聯推理的準確率．需要特別指出的是，YAGO2［4］中已經提出了一個基于時空信息知識網絡的模型SPOTL，但是這個模型主要解決了YAGO2知識庫上的知識檢索與查詢問題，并未將時空信息應用到關聯推理問題上．綜上所述，由于現有的知識網絡對于知識的時空信息的描述能力有限，導致在進行關聯推理時無法對時空信息進行充分地利用，限制關聯推理準確率的提高，因此我們提出一種融合了時空信息的知識演化網絡模型，并提出一種基于該網絡的推理方法，提高關聯推理的準確率．

1演化知識網絡模型

本節我們主要提出一個演化知識網絡模型和定義在該網絡上的一種特殊的子網絡———鏈接延展模式．

1．1演化知識網絡演化知識網絡是一個異構的演化的多重圖，且圖中的節點和邊都包含時間與空間信息．具體定義如下：定義1．演化知識網絡．給定一個時間集合T，空間集合S，則演化知識網絡GT，S可定義為一個8元組：GT，S＝（V，E，，φ，θ，τ，λ，η），其中，V是演化知識網絡中節點的集合；E有向邊的集合，它的具體表示形式是一個3元組（u，v，r），這里u，v∈V，r∈R，其中R是邊的所有類型構成的集合；：V→A是節點類型的計算函數，使得每個節點通過該計算函數，可得到唯一的類型（v）∈A，這里A為頂點的所有類型構成的集合；φ：E→R表示在邊集合中某一條邊的計算函數，且每一個實體對間最多有｜R｜條邊；θ表示圖中邊的時間屬性信息，用來描述一條邊的發生以及存在的時間信息；τ是邊的空間屬性信息；λ是節點的時間屬性信息，η是節點的空間屬性信息．在這個演化知識網絡模型中，我們記錄了圖中節點與邊的時間和空間信息．這里的時間信息是一系列離散的時間戳，空間信息則是一系列離散的地理位置信息．演化知識網絡的可演化性主要體現在可通過感知網絡中產生的新變化與自身進行比較，發現新知識，并實現自我更新．網絡中的節點和邊都有時間戳信息，它們都會隨著時間的變化而演變，例如對于當前國家元首這個節點，會隨著節點任職期滿而自動更新為前任領導人，這便體現了網絡的時空可演化性．

1．2鏈接延展模式基于我們提出的演化知識網絡，本文著重研究在該網絡上的關聯推理問題．關聯推理的主要目的是，利用知識庫中已有的知識作為基礎推理出兩實體間可能存在的新關系．這里我們做的關聯推理不僅僅要推理出新的邊，還要給出邊的類型．推理的主要思路是：首先構造出所有可能存在的鏈接延展模式；然后建立一個混合背包問題模型，將每一個模式看作背包問題中待選擇的物品；通過背包問題的求解，選擇出對于關聯推理有意義的模式；利用這些模式在圖中進行匹配，推理出新的關系．首先引入演化知識網絡中的鏈接延展（linkextendable，LE）模式的定義，簡稱為LE模式．定義2．鏈接延展模式．已知一個關系集R，知識網絡GT，S，我們定義GT，S上的一個子網絡H＝（V′，E′），V′A，E′R，在這個子網絡中任意兩節點都可通過一條邊進行關聯，如果這個子網絡中有n個節點，則稱其為n元模式，我們將這個子網絡叫做鏈接延展模式．由圖2可知，對于不同的LE模式的定義我們可以找到它相應的實例，且對于同一個LE模式可以有多個不同的實例．在進行關聯推理時，我們需要將LE模式進行分解，使其成為可用來實現關聯推理的新的LE模式．例如圖2（a）表示的一個LE模式，我們可將其拆解為3個可用于關聯推理的新的模式，如圖3所示：在圖3（a）中，我們將相連的兩條邊作為關聯推理的條件，單獨的一條邊作為推理的結論．在進行關聯推理時，若已知在3個節點他們的類型滿足圖3（a）中Au—P—Au的要求，且節點類型為Au—P和P—Au的節點對之間的關系分別為cite和write，則我們可推出兩節點間存在cite關系．例如在圖2（a）中，我們已知Tom和Lily類型為作者，paper1的類型為論文，且已知Tom引用了paper1，Lily寫了paper1，則根據圖3（a）中的LE模式，我們可推理Tom和Lily之間存在引用關系．需要指出的是，在網絡中利用這些模式進行推理的結果并非全部正確，例如圖1（b）所代表的模式的含義是，某一位作者寫了2篇文章，可得出這2篇文章之間存在引用關系，而事實上這個引用關系可能不存在，因此，對于網絡中包含的所有的模式構成的集合，我們需要利用背包問題的思想，從中選出置信度較高且涵蓋關系類型更廣泛的模式子集，并用子集中的所有模式進行關聯推理．

2關聯推理方法

2．1基于混合背包問題的關聯推理方法（KP－LIM）為了實現基于某一演化知識網絡GT，S上的關聯推理，首先需要找出網絡中所有可能存在的可用于關聯推理的模式，通過混合背包問題求最優解的思想對不同模式進行選擇．下面我們先簡要介紹一下背包問題．背包問題（knapsackproblem）是一種組合優化的NP完全問題，可以描述為：給定一組物品，每種物品都有自己的重量和價值，在限定的總重量M內，我們如何選擇才能使物品的總價值最高．這里我們將不同的模式看作背包問題中要裝進背包中的物品，因此每個模式需要有相應的重量Weight和價值Value兩個參數．我們從不同LE模式在網絡中匹配的實例個數以及正確的實例個數的角度，給LE模式的2個參數重量Weight和價值Value做了以下定義．為了求解上面的混合背包問題，我們將問題拆解成2個0－1背包問題：1）多重選擇背包問題，即在約束為耗費小于M＊（M＊＜M）條件下，從每個分類中選出一個結果，這個步驟主要是保證每個分類中都有一個LE模式被選擇出來，即在后期做推理時，每種關系都可能被推理出來；2）常規的背包問題，在耗費小于M－M＊約束下我們可以從剩下的所有模式中選擇更多意義的模式，提高推理的召回率．

2．2算法及分析實現關聯推理的過程可主要分為以下3個步驟：1）構造可能存在的LE模式．已知演化知識網絡GT，S上的邊的所有類型，則任意3種類型的邊的組合可構成一個候選LE模式．2）背包問題實現模式選擇．遍歷全圖，找出不同模式相應的所有實例，計算得到不同模式的Weight和Value，通過混合背包問題的求解選出有意義的LE模式．3）利用選出的模式在網絡中進行匹配得到推理結果．下面算法1中給出我們提出的關聯推理算法的實現．一般的遍歷全圖找不同模式的實例的方法是，對于每一個模式，遍歷圖中的所有節點；對于某一個節點，遍歷它所有的邊，如果滿足模式要求，則以該邊的另一個端點為起點遍歷其他所有的邊，看是否滿足模式要求，依此類推．假設共有m個不同實例，全圖有n個節點，且圖中節點的平均出度入度和為r，則該運算的復雜度為O（mnr3）．以上方法雖然容易實現，運算復雜度卻很高，效率低下，因此算法2利用了一些技巧降低了時間復雜度．首先，我們不針對每個模式遍歷一遍全圖來找實例，而是做一個映射表，在這個映射表中不同模式對應的值為到當前為止該模式匹配上的實例個數，因此只需遍歷一遍全圖即可得到所有模式的實例個數．由于這里我們采用的模式均為3元模式，基于三角形的特殊構造，對于每個節點的具體匹配過程，我們不需要從一個節點出發，以廣度優先的思想遍歷3層關系，只需要從一個節點出發，找出它自身的所有關系，任意2個關系為一組，若這2個關系對的終點之間也存在關系則可構成一個LE模式，將映射表中的相應模式的value值加1即可．該算法經過優化后的時間復雜度為O（nr2）．

3實驗

本節我們將詳細介紹相關的實驗結果，驗證我們提出的基于混合背包問題的關聯推理方法KP－LIM的合理性與有效性，以及KP－LIM方法對于大數據環境的適應性．

3．1實驗數據集及參數選擇我們采用來自不同領域的數據構建成2個演化知識網絡進行關聯推理實驗．這2個演化知識網絡的數據分別來自于學術領域和電影領域，均包含了多種不同類型的節點和關系．其中學術網中的數據是從知名的學術文章網站Soscholar①上用網絡爬蟲爬取得到的，在這個網絡中包含：1000萬個作者（A）、700萬篇論文（P）、50萬個雜志（M）、1．4萬個會議（C）和5萬個關鍵詞（K）．我們選用論文的發表時間以及會議的召開時間作為網絡中時間信息，選機構所在地構成網絡中的空間信息．對于電影網，它的數據主要來自于對知名電影網站IMDB上的電影信息的爬取．該網主要包括：演員（Ac）和導演（D）共4530159個，電影（M）2132383部，我們選取電影上映時間、拍攝地等信息作為電影知識網絡的時間與空間信息．在表1和表2中分別列舉了學術網和電影網中所有的實體間的直接關系．需要指出的是，表中羅列的是從元數據中抽取的直接關系．對于學術網，已知邊的類型數，則根據LE模式的特點可以找出所有可能存在的LE模型，去掉一些不可能存在的模式，最終，對于學術網我們可得到了124個不同的模式．同理對于電影網，我們共得到18個模式．實驗過程中，我們在圖中隨機隱藏掉占整個網絡中所有關系數量的指定比例的關系以及它們所有的附加信息，實驗過程中通過改變這個比例來比較不同方法的推理能力，這里由于我們做的是關聯推理，而不是關系預測或時序關聯推理，因此在隱藏關系時不考慮關系的時間順序．為了驗證我們提出的方法的有效性，在實驗中我們將KP－LIM方法與2種最近比較流行的關聯推理方法進行比較，一個是經典的有監督算法的代表邏輯回歸方法［14］（簡稱Logistic），另一個是文獻［8］中提出的方法M－CN＋ANC＋OAWpress（簡稱CN），它是一種典型的無監督學習方法．對于邏輯回歸方法，我們是將每一個LE模式作為一維特征，構造訓練數據，通過邏輯回歸算法進行學習，學出每個特征的系數，在進行關聯推理時給出一個實體對，匹配不同的模式．如果沒有模式可以匹配上，則推理兩節點間沒有關系；如果有模式匹配上則不同的關系可以得到一個分數，當分數大于某一閾值時，我們推理這兩節點間存在這種關系．實驗可得，當閾值選擇為0．6時，邏輯回歸的推理效果最好，因此在后面的比較實驗中，我們選擇閾值為0．6．而對于CN方法，在給出實體對后，針對每種關系可計算出一個得分．同理我們選擇一個閾值，當得分大于該閾值時，推理兩實體間存在某一關系，實驗可知當閾值選擇0．8時效果最好。為了確定M＊和M的具體值，我們首先固定M的值、變更M＊的值，來研究M＊的值變化對于關聯推理效果的影響，找出推理結果最優時M＊的值；然后固定M＊的值，在（M＊，Mmax）的范圍內調節M的值，找出推理結果最優的M值，最終可通過實驗確定出2個參數的值．圖4給出了對學術網進行參數調節的過程，其中圖4（a）～（d）分別代表M＝6，7，8，10時對M＊的值進行調節得到的測試結果．從圖4可知，當M＝7，M＊＝5時，對于學術網上的關聯推理結果最好．同理我們對電影網上的數據進行測試，得到當M＝3，M＊＝2時結果最優．

3．2實驗結果及分析本節我們會通過實驗進行3方面的比較：1）比較KP－LIM與Logistic和CN方法間的關聯推理準確率；2）演化知識絡網與傳統的異構信息網絡的比較；3）KP－LIM算法對于大數據的適應性的性能測試．

3．2．1不同關聯推理方法的推理效果比較在進行不同關聯推理方法的比較實驗時，我們選擇準確率作為評價指標，主要是因為基于大規模知識網絡的關聯推理，推理結果的正確與否具有決定性作用，推理結果作為知識必須要保證其準確性，因此這里我們選準確率作為指標．實驗結果如表4所示，主要比較了3種不同方法的準確率，在這里α表示隱去的關系數量占全圖關系總數量的比例．隨著α的增加，KP－LIM方法的表現均優于其他2種方法，與有監督算法Logistic相比，我們的方法在學術網上準確率獲得了2％～62％的提高；對于CN方法，我們的方法獲得了28％～70％的提高，平均提高量分別為29％和37％．同理在電影網上，我們的方法分別獲得了和1％～22％和20％～30％的提高，平均提高值分別為8％和24％．綜合以上結果可得出結論，KP－LIM方法在不同的數據集上，比當前比較流行的2種方法均取得更好的推理結果．其主要原因是，我們的方法將不同模式的特點以及全圖的背景知識信息融入到背包問題中，通過背包問題的求解，從模式集合中選出高質量的模式進行關聯推理；而Logistic采用了所有的模式，僅僅通過訓練數據給不同的模式學習出不同的系數，既未將全部的背景知識信息加以利用，模型的好壞完全受訓練數據好壞的影響，又未對模式進行篩選；而CN方法只考慮了待推理的2個實體的相關關系，對圖的結構信息利用不充分，因而它的準確率最低．

3．2．2演化知識網絡與傳統網絡的比較在3．2．1節中我們通過實驗證明了KP－LIM與其他幾個關聯推理中的經典方法在準確率上有較大的提高，其功于我們提出的基于混合背包問題的模式選擇策略色優越性，同時我們猜想演化知識網絡模型自身也對與推理結果的準確率的提高有一定499趙澤亞等：大規模演化知識網絡中的關聯推理的幫助．因此，我們分別在演化知識網絡（EKN）和異構信息網絡（HIN）中采用KP－LIM方法進行關聯推理，比較2個網絡中的推理效果．在2個網絡中，我們分別隱掉相同的關系，再對這些關系類型進行推理，由于傳統的異構信息網絡中沒有時間信息，因此只能采用弱化的KP＿LIM方法進行模式選擇，即模式價值的定義有所改變，改為與該模式所有匹配的實例的個數．推理結果如圖5所示：由圖5可知，隨著隱掉邊的比例的變化，EKN上的推理準確率始終比HIN高，提高比例為1．9％～87％．由此可見，演化知識網絡與異構信息網絡相比對關聯推理有一定的幫助，這主要是因為演化知識網絡中包含點與邊的時空信息，這些信息對于關聯推理的準確率的提高具有重要意義．值得注意的是，隨著隱掉邊的比例的增加，兩者的推理準確率均呈下降趨勢，這是由于隱掉邊的比例越大，已有的可用于推理的知識越少，因此推理的準確率有一定的下降．

3．2．3KP－LIM的性能測試由于在大數據環境下，數據量急劇增長，能否適應大數據的挑戰，也是衡量一個算法好壞的重要方面，因此，下面我們對KP－LIM方法的計算性能進行測試．首先分別構造不同大小的知識網絡，測試在不同規模的網絡上KP－LIM進行關聯推理的時間消耗，這里我們將網絡中的點的數量從100萬逐漸增加到1000萬，并記錄下推理時間的變化，如圖6所示．由圖6可知，隨著網絡規模的迅速增加，我們提出的KP－LIM推理方法時間消耗的增長緩慢．當網絡規模擴大了10倍，推理耗時僅從8．372s增加到15．726s．在算法2我們也對KP－LIM方法的時間復雜度進行了分析，該算法的主要時間消耗集中在遍歷全圖找不同模式實例的過程，復雜度為O（nr2），這里n代表網絡中節點的個數，r為節點的出入度，因此隨著網絡規模的增加，r的變化較小，因此整個算法的時間消耗主要受到網絡中節點的個數n的影響，因而隨著網絡規模的增加算法的時間消耗呈線性增長．綜上所述，我們提出的關系KP－LIM不僅在推理準確率上取得了較好的結果，其計算成本也并沒有對著網絡規模的擴大而呈指數增長，因此KP－LIM的計算性能也能夠滿足大規模知識網絡對關聯推理性能與效率的要求．

4總結與展望

本文首先提出了一個融合了時間與空間信息的演化知識網絡，基于該網絡提出了一種關聯推理方法．實驗證明我們的方法比當前流行的一些關聯推理方法取得了更高的準確率，且在大數據的環境下依然擁有較好適應性．但該KP－LIM方法也存在一定的局限性，例如對于網絡中已有的關系數量有一定的依賴性、無法很好地應對冷啟動問題，且對于網絡中的空間信息利用不夠．因此，關于這個工作，仍有以下4個需要研究的方向：1）KP－LIM方法對知識網絡中已有的關系數量的依賴性較強，當面對冷啟動問題時，如何保證推理的準確率有待進一步研究；2）對于演化知識網絡中的空間信息的利用有限，下一步可研究如何更充分地利用網絡中的時空信息，進一步提高推理效果；3）從知識表示的角度，研究知識網絡的演化性和關聯推理，是近年來知識網絡的關聯推理研究的新方向，相關工作包括文獻［23］；4）研究時序關系的推理，即推理知識網絡中關系產生的時間，是進一步研究知識網絡演化性的又一重要方向，相關工作包括文獻［24］．

作者：趙澤亞 賈巖濤 王元卓 靳小龍 程學旗 單位：中國科學院網絡數據科學與技術重點實驗室 解放軍信息工程大學 中國天繪衛星中心