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

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

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

1 引 言

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

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

2 語義知識圖譜的功能

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

3 語義知識圖譜的應(yīng)用

3.1 知識圖譜增強的基于內(nèi)容推薦方法

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

圖1 在考試推薦系統(tǒng)應(yīng)用的知識圖譜的一部分Fig.1 Part of the knowledge map applied in the

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

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

3.2 知識圖譜增強的協(xié)同過濾方法

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

圖3 關(guān)鍵結(jié)點的部分分類Fig.3 Partial classification of key nodes

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

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

3.3 通過知識圖譜結(jié)合基于內(nèi)容與協(xié)同過濾推薦

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

圖5 結(jié)合基于內(nèi)容和協(xié)同過濾推薦方法Fig.5 Combining content based and collaborative

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

(1)

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

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

4 推薦系統(tǒng)

本文通過基于內(nèi)容的方法向用戶推薦與他/她測試過的試卷或搜索的信息相關(guān)的試卷，通過協(xié)同過濾方法向用戶推薦和他做過相似測試的用戶的試卷.圖6展示了基于知識圖譜的測試推薦系統(tǒng)，并根據(jù)MapReduce模型應(yīng)用于云端.測試推薦系統(tǒng)的步驟如下：

圖6 推薦系統(tǒng)框架Fig.6 Recommendation system framework

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

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

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

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

5)工作結(jié)點在主結(jié)點的控制下運行并執(zhí)行Reduce操作.MapReduce將結(jié)果返回到推薦系統(tǒng).

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

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

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

圖7 云端推薦系統(tǒng)的MapReduce模型Fig.7 MapReduce model of cloud recommendation system

1)基于內(nèi)容的測試推薦系統(tǒng)創(chuàng)建MapReduce作業(yè)并在作業(yè)客戶端執(zhí)行作業(yè).

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

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

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

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

6)輸出結(jié)果可用于測試推薦系統(tǒng)中的推薦文件.

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

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

6 相關(guān)工作

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

7 結(jié) 論

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