基于知識圖譜的多目標學習資源推薦算法①

東 苗

(上海行健職業學院 信息技術與機電工程系,上海 200072)

隨著“互聯網+”的發展,各種E-learning在線學習系統在教育領域中普遍應用,海量的網絡教學資源在為用戶提供了便利的同時,也出現了“認知過載”和“學習迷航”等問題.為解決這些問題,個性化推薦系統應運而生,根據用戶的信息需求、興趣偏好等,將匹配度高的資源推薦給用戶.推薦策略主要包括:基于內容的推薦、協同過濾推薦、混合推薦、基于網絡結構的推薦、基于關聯規則的推薦、基于知識的推薦等[1–6].學習資源的推薦與電影、音樂、旅游等商品推薦的不同之處在于:除了用戶的興趣偏好之外,還應考慮用戶的認知水平、學習目標等個性化因素,以及知識點之間的邏輯關系.

2012年谷歌正式提出了“知識圖譜”這個術語,知識圖譜旨在描述真實世界中存在的各種實體或概念,以及他們之間的關聯關系[7].在知識圖譜中,將每條知識表示為<實體,實體關系,實體>或<實體,屬性,屬性值>的三元組,將所有數據組織成一張有向圖[8].基于知識圖譜的推薦方法大致分為基于本體(Ontology)的推薦生成和基于開放鏈接數據(LOD)的推薦生成兩大類[7],近年來廣泛地應用在旅游推薦、電影/音樂推薦、電子商務和職位推薦等領域.

因此,本文將知識圖譜融入學習資源推薦模型,構建語義網絡,綜合考慮用戶的興趣偏好、學習資源所涵蓋知識點的關聯度與中心度,建立多目標優化模型.使用自適應多目標粒子群(AMOPSO)算法得到Pareto最優解集,進行個性化學習資源的推薦.

1 學科知識圖譜的構建

本體這一概念源于哲學領域,是對某一特定領域中共享概念模型的明確的形式化規范化說明,包含了“概念模型”、“明確化”、“形式化”和“共享”4 層含義[9].利用本體進行知識表示有利于呈現目標知識的邏輯關系,查詢以及共享.在學科資源本體模型中知識點是資源描述的基本單位,每個知識點對應多個相關的學習資源,包括文本、圖像、音視頻等[8].將知識點作為知識圖譜中的實體,將知識點的特征作為知識點實體的屬性,以這樣的規則關聯到知識圖譜中展開研究.本體的構建方法和表示語言有很多種,適用于不同的學科領域和工程應用.本文首先抽取知識點并挖掘知識點之間的關聯關系和知識點的屬性,然后根據知識點結構構建學科知識圖譜.

1.1 實體抽取

在學科知識圖譜中將知識點作為圖譜中的實體,實體抽取即提取出教學資源中的概念、定義、定理、性質、公式等領域術語.常用的實體抽取方法有基于規則與詞典的方法、基于傳統機器學習識別的方法、基于深度學習的抽取方法等[10].本文利用網絡爬蟲從指定的網頁上完成對學習資源文本內容數據的抓取和保存,使用中國科學院計算技術研究所分詞工具NLPIR進行數據清洗和預處理后,通過TF-IDF算法進行知識點的提取.TF-IDF算法采用文本逆頻率IDF(Inverse Document Frequency,逆文本頻率指數)對TF(Term Frequency,詞頻)值加權取權值大的作為關鍵詞.

其中,nij表示詞條ti在學習資源dj中的詞頻,表示學習資源dj中的全部詞條數,|D|表示課程學習資源庫中全部的文檔數,表示包含ti的學習資源文檔數,|N|表示學習資源dj中詞條的個數.

1.2 關系抽取

關系抽取是為了解決實體間語義鏈接的問題.Google 推出的Word2Vec 通過訓練將每個詞映射成K維實數向量后,可通過詞之間的距離(比如余弦相似度、歐氏距離等)來判斷它們之間的語義相似度,然后在詞條間建立其層次關系樹.本文中根據實際需要,定義以下5 種知識點之間的關系:前驅關系、后繼關系、包含關系、并列關系、同義關系.具體含義如表1所示.

表1 知識點間的關系定義

1.3 本體構建

本文以C 語言程序設計課程為例,采用斯坦福大學開發的Protégé工具進行本體的構建.如圖1.

圖1 課程本體部分關系示例

2 基于知識圖譜的多目標學習資源推薦模型的構建

2.1 學習資源數學模型的建立

學習資源特征用向量R=(V(R),T(R))表示.其中,V(R)={vi|1≤i≤N}表示學習資源R與N個知識點的關聯關系.資源是由一個或多個知識點組合而成的,vi即學習資源R與第i個知識點ki之間的相關系數.資源類型分為文本、圖片、音視頻、互動軟件4 種,很多學習資源同時采用多種表達方式,因此用向量T(R)={t1,t2,t3,t4}描述學習資源R采用各種知識表達方式的程度,s.t.0≤t1,t2,t3,t4≤1,且

2.2 用戶數學模型的建立

將用戶特征模型表示為:U=(K(U),P(U)).其中,K(U)表示由用戶歷史學習行為得到的用戶知識庫.P(U)={p1,p2,p3,p4}表示用戶U的學習風格,學習風格的不同對學習資源類型的選擇會有影響,依據Kolb學習風格類型將學習風格類型分為發散型、聚合型、同化型和調節型4 種.同一個用戶會表現出多種學習類型的傾向,p1、p2、p3、p4分別表示用戶U屬于4種學習風格的傾向程度,s.t.0≤p1,p2,p3,p4≤1,且

2.3 基于知識圖譜的推薦模型

本文提出基于知識圖譜的多目標學習資源推薦模型.本模型包兩個目標函數:學習資源包含的知識點與用戶知識庫的距離(Resource Knowledge Distance,RKD)和用戶對學習資源類型的偏好(Resource Type Preferences,RTP),即Func={RKD,RTP},兩者決定推薦的學習資源與用戶特征的符合程度.

學習資源包含的知識點與用戶知識庫的距離如下:

其中,K(R)表示學習資源R的所包含的知識點庫;K(U)表示用戶知識庫;ki表示學習資源R的所包含的用戶尚未掌握的知識點;S hortestPath(ki,K(U))表示知識點ki與用戶知識庫K(U)中所有知識點的最短路徑,Degree|ki|表示知識點ki的度.度為知識點在整個知識圖譜中影響力的大小,代表了知識點的重要程度[11].

如圖2示例,用戶知識庫K(U)={k1,k2,k3},每個學習資源可涵蓋一個或多個知識點,資源知識庫K(R1)={k5},K(R2)={k4,k7},K(R3)={k2,k4}.可分別計算資源到K(U)的距離:

計算后得到距離K(U)最小的資源即最值得推薦的學習資源.

學習資源類型與用戶學習偏好之間的差異如下:

其中,ti表示學習資源類型,s.t.0≤ti≤1,且pi表示用戶學習偏好,s.t.0≤pi≤1,且

圖2 用戶知識庫與資源知識庫的關系示意圖

3 基于知識圖譜的多目標學習資源推薦模型求解

個性化學習資源推薦問題是一個多目標優化問題(MOP),本文采用自適應多目標粒子群算法(AMOPSO)進行基于Pareto 非劣解集下的多目標規劃.粒子群算法(PSO)是一種模擬鳥群覓食的隨機搜索算法,能夠在一次迭代過程中產生多個Pareto 近似最優解,在求解多目標優化問題上具有較強的優勢.AMOPSO 充分利用PSO 快速收斂的優點,兼顧避免陷入局部極值的弱點,通過進化環境反饋信息來自適應調節粒子運動參數和極值擾動策略,從而有效平衡開發與開采過程,保證粒子具有很好的全局搜索能力和較快的收斂速度[12,13].

3.1 自適應多目標粒子群算法

標準多目標粒子群算法(MOPSO)迭代公式為:

其中,r1、r2為0～1 之間均勻分布的隨機數;pi為粒子個體的最佳位置;pg為群體所發現的最佳位置;xi(t)為t時刻粒子的位置;vi(t)為t時刻粒子的速度;ωi為算法慣性權重;c1、c2為學習因子.

MOPSO有迭代初期局部搜索能力較弱、迭代后期易陷于局部最優的缺點[14].為了平衡MOPSO 算法的全局搜索能力和局部更新能力,自適應多目標粒子群算法(AMOPSO)采用非線性的慣性權重因子公式,使慣性權重因子 ωi隨粒子的目標函數值而自動改變,當各粒子的目標函數值趨于一致或趨于局部最優時,使 ωi增大;當各粒子的目標函數值較為分散時,使ωi減小.

其中,fi為粒子當前的目標函數值;假定當前所有粒子的平均目標值為favg,favg1、favg2分別為目標函數值大于favg的粒子的平均目標值和目標函數值小于favg的粒子的平均目標值;α為種群多樣性的指標.

c1、c2第t次迭代時取值公式為:

其中,c1,ini和c2,ini分別代表c1、c2的初始值,c1,fin和c2,fin分別代表c1、c2的迭代終值.改進后的速度權重自適應變化因子 ωi可以有效的平衡算法的搜索區域,學習因子的異步變化使得粒子加強了算法初始階段的全局搜索能力,在算法后期有利于收斂到全局最優.

3.2 算法流程

以最小值 minFunc=min{RKD,RTP}為目標的自適應多目標粒子群算法流程(如圖3)如下:

Step 1.初始化種群和速度.計算目標函數值并將非支配解加入外部種群存檔NDset.

Step 2.將本次迭代中內部種群中的非支配解復制至NDset,并刪除其中的重復個體.計算NDset中所有個體的擁擠距離并按降序排列,取前M(設定的外部種群最大個體數)個.

Step 3.更新全局最優位置.

Step 4.根據式(11)計算自適應權重系數 ωi,粒子更新速度vi和位置xi,判斷速度和位置是否越界,如果速度越界則取邊界速度值,如果位置越界則取范圍內隨機位置.

Step 5.判斷是否滿足終止條件,如果達到則輸出NDset,獲得Pareto 最優解集;否則,t=t+1,返回Step 2 繼續運行.

圖3 AMOPSO 資源推薦流程圖

4 實驗與分析

4.1 實驗環境與數據集

本文利用Matlab R2016a 實現上述算法,為了觀測算法的有效性和可行性,以標準MOPSO、AMOPSO做對比實驗分析推薦性能的差別.求解后從Pareto 解集中選取Top-10 作為推薦的學習資源;若Pareto 解集中的數據小于10 條,則選擇所有的候選集作為推薦內容.

從某網絡學習平臺數據中爬取了部分包含C 語言課程知識的文檔與在線學習數據信息,經過數據清洗和分詞處理后抽取知識點和關系,構建課程本體并經過補全形成實驗數據集.

4.2 算法參數設置

MOPSO和AMOPSO中特征參數的選取如表2所示.

表2 算法參數設置

4.3 實驗結果分析

為了觀察推薦效果,使用HV (Hyper Volume)值對實驗結果進行分析.由表3和圖4可知,AMOPSO的HV 指標最好值、均值、最差值均高于MOPSO,說明AMOPSO的收斂性和多樣性優于MOPSO;同時AMOPSO的HV 值分布范圍窄于MOPSO,說明AMOPSO的穩定性更好,在進行學習資源推薦時的綜合性能更好.

表3 實驗中HV 值的統計結果

圖4 MOPSO和AMOPSO的HV 箱線圖

如圖5所示,使用MOPSO和AMOPSO 算法分別進行資源推薦的計算可以得到兩個不同的Pareto 前沿面.X 軸為目標函數RTP,表示學習資源類型與用戶學習偏好之間的差異;Y 軸為目標函數RKD,表示學習資源包含的知識點與用戶知識庫的距離.AMOPSO 求得的Pareto 前沿具有良好的分布特征和較好的多樣性,且收斂效果更好,表明AMOPSO在Pareto 前沿面上的尋找更有優越性,更適合求解多目標學習資源推薦問題.

圖5 MOPSO和AMOPSO的Pareto 前沿面

傳統MOPSO 算法采用固定慣性權重因子,AMOPSO中通過式(11)使慣性權重因子 ωi隨粒子的目標函數值而自動改變.在迭代初期 ωi較大,粒子以較大的步長進行全局搜索,使得算法快速收斂;在后期ωi較小,趨于精細的局部搜索,有更強的尋優能力.慣性權重隨迭代次數的變化曲線見圖6所示.

學習因子c1、c2分別調節粒子向個體最優和群體最優方向飛行的最大步長.本文通過式(12)、式(13)使學習因子異步變化,在迭代初期學習因子較大,加強了全局搜索能力;在后期學習因子較小,有利于收斂到全局最優.

圖6 AMOPSO 算法慣性權重隨迭代次數變化曲線圖

4.4 收斂性能分析

反向世代距離(Inverted Generational Distance,IGD)指標可用于評估多目標優化算法中非支配解集對真實Pareto 前沿最優解集的逼近程度.IGD 值越小,表明推薦精度越高,算法收斂性和分布性能越好[15].

其中,P表示真實Pareto 面上的最優解集,|P|為真實Pareto 面上的最優解集的個體數,Q為算法獲取的非支配解集,d(v,Q)表示個體v到種群Q的最小歐氏距離.

由表4可知,AMOPSO的IGD 指標均值和方差均比MOPSO 小,表明AMOPSO在收斂性和分布均勻性上均優于標準MOPSO.

表4 實驗中IGD 指標的統計結果

4.5 推薦效用的評價指標

本文采用五折交叉驗證,將數據集隨機分為5 份,每次選取其中一份作為測試集,另外4 份作為訓練集,重復5 次,每次選取不同的訓練集.將5 次實驗的平均值作為推薦效用的評價指標.對推薦算法結果的分析,使用3個指標:查準率(Precision,P),召回率(Recall,R)以及F1-Score 值(F):

其中,TP(True Positive)指推薦了且用戶會使用的資源,FN(False Negative)指推薦了但用戶未使用的資源,FP(False Positive)指用戶喜歡但沒推薦的資源,TN(True Negative)指用戶不喜歡且沒推薦的資源.據上述,P反映了推薦算法的推薦水平;R反映了被推薦算法所推薦的資源占用戶真正喜歡的資源的比重;F值是P和R的加權平均,均勻地反映了推薦效果.3個指標通常都是越高越好[15,16].

如圖7所示,AMOPSO在P、R、F值上均優于MOPSO,說明AMOPSO 算法在解決本問題時綜合性能較高,推薦效果更好.

圖7 評價指標條形圖

5 結論

本文在進行學習資源推薦時基于知識圖譜建立學習資源推薦模型,綜合考慮用戶的興趣偏好、用戶原有的知識結構與學習資源所涵蓋知識點之間的關聯度,建立多目標優化模型.對模型求解時使用AMOPSO 算法,個體擁擠距離降序排列進行外部種群規模的縮減和全局最優值的更新,獲得了分布特征良好的兩目標Pareto 前沿,輸出推薦資源序列.實驗時通過與經典MOPSO 算法對比并使用HV、IGD 指標對模型進行評價,驗證了其多樣性和穩定性,證明了算法良好的全局尋優和收斂性能.并采用五折交叉驗證,使用查準率、召回率以及F1-Score 值驗證了算法的推薦效用.在后續工作中將進一步完善用戶模型和學習資源模型,優化推薦算法以提升學習資源推薦性能.