基于知識圖譜的云端個性化測試推薦

段玉聰,邵禮旭,崔立真,高洪皓

1(海南大學 信息科學技術學院, 南海資源利用海洋國家重點實驗室, 海口 570228)2(山東大學 計算機科學與技術學院, 濟南 250100)3(上海大學 計算中心, 上海 200444)

1 引 言

知識圖譜是用于存儲計算機系統或人與計算機之間交流使用的復雜結構化和非結構化信息的知識庫.知識圖譜目前用于解釋搜索結果，探索知識空間，使文本文檔語義更加豐富或支持知識密集型應用程序，如推薦系統.推薦系統是信息過濾系統的一個子類，旨在預測用戶對一個物品的"評級"或"偏好"[1].推薦方法通常包含五種方法，分別是協同過濾方法、基于內容的方法、基于個性化的方法、基于知識的方法和混合方法.

本文分析了基于知識圖譜的測試推薦系統.引入知識圖譜的目的是提高效益，這包括了推薦結果的正確性和準確性以及推薦活動的效率.知識圖譜可以補充在基于內容的搜索中被語義隔離的項目之間的語義信息，補充的語義關系將通過調節更多的相關信息與被語意隔離的項目相比較來有效提高推薦結果的正確性.新增加的相關信息將有助于排除由孤立項目組成的不可能的語義，否則，排除這些還需要進行探索.類似的，本文也可以在這個基于知識圖譜的對比架構下來檢查協同過濾的合理性.本文還利用協同過濾以統計數據的形式說明上下文信息和時間軌跡信息，從而提高利用知識圖譜增強內容搜索功能的有效性.本文采用這種方法，根據用戶的搜索信息，測試歷史，用戶信息等來推薦試卷和考題.本文還提出了一個用于在云計算環境下的測試推薦系統MapReduce模型.

2 語義知識圖譜的功能

大量的數據、信息和知識等類型化的資源以及用戶復雜的檢索需求，導致了許多并行的、復雜的工作，用戶對推薦的滿意度和準確性的要求也大大提高.用戶希望獲得更多的個性化推薦服務.知識圖譜已經成為將知識以具有標記的有向圖形式表示并給出文本信息的語義的強大工具.知識圖譜通過將每個項目，實體和用戶作為結點，并且通過將邊緣相互聯系的那些結點進行連接來建立圖形.與UML類圖相比，知識圖譜具有豐富的自然語義，其表達機制更接近于自然語言，可以包含各種更完整的信息.過去已經提出了許多使用內容的方法，他們中并沒有很多利用內容本身和外部知識源之間的聯系，也就是知識圖譜.在基于內容的方法中，知識圖譜可以解決搜索詞之間的語義隔離，然后補充搜索詞之間的語義信息.信息表達的完整性會大大提高.知識圖譜可以檢查協同過濾對比較結構的合理性.基于內容的方法不考慮用戶的行為軌跡和偏好.基于內容的搜索和協同過濾方法給出的推薦的準確性和效率的發展趨勢是不同的，本文不能隨意地將這兩種方法組合起來使用.本文建議通過引入知識圖譜作為媒體層來組合基于內容的搜索和協同過濾方法.本文利用協同過濾方法以統計數據的形式引入上下文信息和時間軌跡信息，從而提高利用知識圖譜增強內容搜索功能的有效性.

3 語義知識圖譜的應用

3.1 知識圖譜增強的基于內容推薦方法

大多數現有的基于內容的推薦系統，通常用關鍵字描述項目，旨在根據文本內容推薦項目.然而，由于自然語言的模糊性，基于關鍵字的相似性評估可能會被誤導.此外，這種方法也可能導致結果偏離，單個和不準確的信息源是導致結果偏離的根本原因.一個搜索請求可以表示多種含義.知識圖將顯示完整的信息，使用戶能夠找到他們最想要的那一種意義.通過單詞，句子和段落表達信息的語義相關性完整性是不同的.知識圖譜構建了一個與搜索信息相關的完整的知識結構.對于每個搜索關鍵字，本文可以通過知識圖譜得到更豐富，更全面的信息.現有的建模方法對于語義信息來說并不完美.通過知識圖譜的圖形結構，本文可以簡單地表達單詞，句子，段落等.本文在圖1給出了在考試推薦系統應用的部分知識圖譜.用戶輸入的關鍵字被映射到圖譜上的某個結點.然后歷遍整個圖譜，來搜索相關結點，以補充關鍵詞與其他信息之間的語義關系，為用戶提供更準確和正確的建議.

圖1 在考試推薦系統應用的知識圖譜的一部分Fig.1 Part of the knowledge map applied in the

知識圖譜可用于更好地查詢信息復雜的相關性，從語義層面了解用戶的意圖，從而提高搜索質量.對于一個試卷推薦系統，用戶可能想要獲得試卷的電子版或者不同階段的考試卷的綜合試卷，那么數據量將變得很大，數據分析也將變得更加復雜.知識圖譜可以補充在基于內容的搜索中被語義隔離的項目之間的語義信息，補充的語義關系將通過調節更多的相關信息與被語意隔離的項目相比較來有效提高推薦結果的正確性.新增加的相關信息將有助于排除由孤立項目組成的不可能的語義，否則，排除這些還需要進行探索.例如，如圖2所示，用戶輸入的關鍵詞是公式：z+|z|=2+i.根據關鍵字確定相應的問題，用戶輸入的方程考查復變函數的知識點，相關問題可能屬于大二年級的復變函數與積分變換，可以向用戶提供相關的試卷.

圖2 知識圖譜補充語義的例子Fig.2 Example of the complementary

3.2 知識圖譜增強的協同過濾方法

協同過濾分析用戶的興趣，并找到與特定用戶類似的其他用戶，主要吸引力在于不需要任何關于用戶或項目的知識，僅基于評級矩陣進行預測，其面臨的核心問題是如何識別和發現特定用戶群，該系統的效率取決于用戶評價的質量和數量通過整合這些類似用戶給出的信息評估，本文可以預測具體用戶的偏好并提出建議.在協同過濾方法中，用戶偏好信息和用戶行為信息的統計因素很復雜，一些具有相同語義影響的因素可以重新考慮，有的因素可能具有相反的語義效應，甚至有的因素是無效的.例如，一個好學生在圖書館學習很長時間，很少去網咖玩游戲.這兩個統計在語義上是互補的.當本文使用知識圖譜來模擬這個學生時，本文可以用互補語義過濾這些冗余數據.在[2]中，作者提出了一個建議框架，從知識庫中將協作過濾與項目的不同語義表征整合到一起.本文將常識和時間行為的統計信息并入以知識處理中心.通過檢查圖中結點的相關度等信息，可以發現重要的結點，刪除冗余信息，從而提高遍歷整個圖譜的處理效率.如圖3所示，本文將具有較高相關度的結點作為重要結點.如果一個結點與關鍵結點直接相鄰，本文也將該結點當作關鍵結點.對于試卷推薦系統，本文考慮與考卷相關的信息，如用戶的測試記錄，特定用戶的興趣是不相關的因素，所以不需要考慮.

圖3 關鍵結點的部分分類Fig.3 Partial classification of key nodes

即使結點具有高的相關度，結點也可能不具有重要的語義影響.本文通過知識圖譜重組這些信息，并使用PageRank算法構建一個關鍵字識別機制來識別具有重要語義影響的結點[3].想象一個隨機行走的人，從圖4(忽略邊的方向)中的任意結點開始行走，每一步，他要么以概率1-α移動到當前結點的相鄰點，要么以概率α(復位參數)跳回到起始結點.如果重復足夠多次，這個過程將最終給出他在每個結點中的穩態概率的近似值.步行的最終結果僅由連接結構和起始結點決定.本文根據狀態概率識別關鍵結點.搜索引擎公司應用PageRank算法來計算實體的重要性.與傳統的Web圖形相比，知識圖譜中的結點從單個網頁轉換為各種類型的實體，圖的邊緣從超鏈接變為豐富的語義關系.因為不同實體和語義關系的流行程度和提取的信息的可信度是不同的，這些因素將影響最終計算結果的重要性.

圖4 通過知識圖譜對協同過濾因素重組的例子Fig.4 Examples of collaborative filtering factors

3.3 通過知識圖譜結合基于內容與協同過濾推薦

基于內容的方法不考慮用戶的行為軌跡和偏好.基于內容的搜索和協同過濾方法給出的的推薦的準確性和效率的發展趨勢是不同的，不能隨意地將這兩種方法組合起來使用.本文建議通過引入知識圖作為媒體層來組合基于內容的搜索和協同過濾方法.知識圖譜數據的基于圖形的性質使得與其他圖譜的鏈接成為可能，從而可以輕松集成多種信息，并提高信息的完整性.通過遍歷圖譜，在計算推薦列表時發現和利用項目和用戶之間的新的聯系和共同點.本文在基于知識圖譜的對比架構下來檢查協同過濾的合理性，利用協同過濾以統計數據的形式說明上下文信息和時間軌跡信息，提高利用知識圖譜增強內容搜索功能的有效性.協作信息被視為內容特征空間的附加特征，并且在該增強空間上使用基于內容的技術.通過在知識圖譜以結點的形式來構建特征項，并且利用協作特征來豐富特征向量，使用這些數據來支持基于內容的推薦引擎.在試卷推薦系統中，本文通過知識圖譜分別對試卷和用戶進行了建模，確定二者之間的聯系，并根據他們的關系結合起來.

圖5 結合基于內容和協同過濾推薦方法Fig.5 Combining content based and collaborative

在圖5中，如果用戶輸入的檢索詞是"海南"和"大學英語1"，無法確定向該用戶推薦海南某所大學的試卷.通過用戶偏好信息和行為軌跡信息，可以知道該用戶參加了海南大學高等數學期末考試，是海南大學的學生.那么推薦他海南大學的大學英語1試卷是合理的.此外，通過尋找類似的用戶，本文可以根據類似用戶的瀏覽記錄，例如試卷答案，推薦用戶更多可能感興趣的項目.本文用邏輯謂語E表示實體，用邏輯謂語Lbl(E, L)表示標簽，其中實體E包含了標簽L.他們的關系由邏輯謂語Rel(E1, E2, R)表示，其中R表示實體E1和E2的關系，例如R(E1, E2)，按公式(1)計算不同實體之間的相似度(Sim(E1，E2))：

(1)

其中Lc表示E1和E2的公共標簽，Ls表示具有相同信息的標簽.

綜上所述，Netrin-1聯合Kim-1對新生兒窒息后AKI風險預測效果比較理想，敏感度、特異度高，有利于及時發現AKI，有針對性地調整治療方案，改善預后，降低死亡率。

4 推薦系統

本文通過基于內容的方法向用戶推薦與他/她測試過的試卷或搜索的信息相關的試卷，通過協同過濾方法向用戶推薦和他做過相似測試的用戶的試卷.圖6展示了基于知識圖譜的測試推薦系統，并根據MapReduce模型應用于云端.測試推薦系統的步驟如下：

圖6 推薦系統框架Fig.6 Recommendation system framework

1)用戶通過向測試推薦系統發送請求獲得建議.當用戶登錄時，該請求將被激活.

2)測試推薦系統創建MapReduce進程，并從知識圖譜上獲取知識.

3)知識圖譜將知識返回測試推薦系統.

4)MapReduce進程的資源在獲取知識圖譜數據后準備，并且測試推薦系統客戶端將MapReduce作業提交給MapReduce模型中的主結點.

5)工作結點在主結點的控制下運行并執行Reduce操作.MapReduce將結果返回到推薦系統.

6)測試推薦系統為用戶提供推薦的試卷.

5 基于知識圖譜的云端測試推薦

為了減少延時，本文提出云端推薦系統MapReduce模型，如圖7所示，有一個主結點是作業跟蹤器，五個工作結點是任務跟蹤器.主結點初始化作業并將作業分配給工作結點.同時，主結點與工作結點保持通信，管理工作結點中作業的運行，工作結點執行映射和Reduce操作.基于內容的測試推薦系統和協同過濾測試推薦系統在客戶機中運行，創建MapReduce作業，并在作業客戶端中運行.作業客戶端從主結點獲取作業ID，并從知識圖譜系統獲取作業資源.然后作業客戶端將作業提交到主結點.知識圖譜數據拆分為4個部分.在工作結點0中運行的映射操作涉及第0部分和第2部分.在工作結點1中運行的映射操作涉及第1部分，在工作結點2中運行的映射操作涉及第3部分.工作結點0,1和2將寫入日期在地圖操作后的本地磁盤上.減少在工作結點3和4中運行的操作將讀取工作結點0,1和2上的中間日期.Reduce操作將輸出縮減的數據.在Reduce操作后，測試推薦系統將使用輸出數據作為推薦.例如，基于內容的推薦系統創建MapReduce作業，以找到與試卷1最相似的試卷.由內容考試推薦系統和協同過濾檢查推薦系統創建的MapReduce作業可以在MapReduce模型中并行執行.執行作業的步驟如下：

圖7 云端推薦系統的MapReduce模型Fig.7 MapReduce model of cloud recommendation system

1)基于內容的測試推薦系統創建MapReduce作業并在作業客戶端執行作業.

2)作業客戶端從主結點獲取作業ID，并從知識圖譜系統獲取所需的資源.然后作業客戶端將作業提交到主結點.

3)主結點分配映射操作和Reduce操作到工作結點，中間數據如圖7所示.

4)工作結點運行映射操作，結果將寫入本地磁盤. 試卷1是關鍵.值1表示紙張1和紙張之間的相似度.例如，值1 = {"試卷3"，"0.8"}.這意味著試卷1和試卷3之間的相似性為0.8.

5)工作結點執行Reduce操作并輸出結果.例如，在Reduce操作后，本文得到與試卷1相似度最高的試卷7，然后值7 = {"試卷7"，"1"}.

6)輸出結果可用于測試推薦系統中的推薦文件.

圖8 推薦準確性和時間延遲的比較Fig.8 Comparison of recommended accuracy and time delay

本文根據Web爬蟲收集的數據集來驗證本文的方法，分別存儲在知識圖數據庫(Neo4J)和通用數據庫(MySQL)中，對于每個實驗，本文從5000篇試卷中隨機抽取了一些試卷，使用不同的推薦方法來確定推薦10篇試卷的準確性和時間延遲，比較前k條推薦信息的質量，其中k是推薦列表的長度.與傳統的基于內容的方法相比，本文通過知識圖譜增強的方法可以在短時間內提供更準確的建議.在精確度差異較小的情況下，通過知識圖譜增強的協同過濾時間延遲小于傳統方法.在數據較少的情況下，基于內容的方法具有較高的準確性，但隨著數據量的增加，協同過濾方法顯示出更好的準確性和效率.本文的方法也符合這一趨勢，實驗結果如圖8所示.

6 相關工作

推薦系統是提供用戶感興趣的東西的軟件工具或其他技術[4-7].例如，圖書推薦系統，化妝品推薦系統[8]，購物推薦系統[9]，英語學習推薦系統[10]，基于對現有知識圖譜概念的拓展，可將知識圖譜劃分為數據圖譜、信息圖譜、知識圖譜和智慧圖譜[11]，并可應用于回答與5W相關的問題[12].20世紀90年代開始，推薦系統成為了一個獨立的研究領域[13].Netflix的一個團隊首次提高了其推薦系統的性能[14].推薦方法包含基于內容的方法[15]，協同過濾方法[16-18]，混合方法[19]，基于知識的方法[20]，協同過濾方法可解決冷啟動問題[21].知識圖譜旨在提取不同實體之間的關系.它可以找到新的關系事實，這是對從知識來源提取的關系的重要補充[22-24].分布式計算系統是一種編程模型，也是用于處理和生成大型數據集的相關手段[25].分布式計算系統編程模型簡化了許多數據并行的應用的實現手段[26].

7 結 論

本文提出將知識圖譜引入到非結構化語義信息中來改進搜索效率和目標有效性，語義知識豐富了基于內容的搜索，增強了所推薦內容的正確性，降低了計算復雜度.本文將統計常識和時間行為序列中的數據、信息和知識，納入以知識圖譜為資源處理框架的處理中，融合基于內容的推薦方法和協同過濾方法的優勢，知識圖譜的引入突破了順序組合限制，并且允許重復地執行屬于基于內容或協同過濾方法的中間活動，同時容納多方共享信息.本文還提出MapReduce云端測試推薦模型，以應對知識圖譜數據的快速增長.下一階段本文將繼續探索這種并行性在特定云環境中的潛在可能和自動生成處理語義豐富的知識圖譜的技術.