東 苗

(上海行健職業(yè)學(xué)院 信息技術(shù)與機(jī)電工程系,上海 200072)

隨著“互聯(lián)網(wǎng)+”的發(fā)展,各種E-learning在線學(xué)習(xí)系統(tǒng)在教育領(lǐng)域中普遍應(yīng)用,海量的網(wǎng)絡(luò)教學(xué)資源在為用戶提供了便利的同時(shí),也出現(xiàn)了“認(rèn)知過載”和“學(xué)習(xí)迷航”等問題.為解決這些問題,個(gè)性化推薦系統(tǒng)應(yīng)運(yùn)而生,根據(jù)用戶的信息需求、興趣偏好等,將匹配度高的資源推薦給用戶.推薦策略主要包括:基于內(nèi)容的推薦、協(xié)同過濾推薦、混合推薦、基于網(wǎng)絡(luò)結(jié)構(gòu)的推薦、基于關(guān)聯(lián)規(guī)則的推薦、基于知識(shí)的推薦等[1–6].學(xué)習(xí)資源的推薦與電影、音樂、旅游等商品推薦的不同之處在于:除了用戶的興趣偏好之外,還應(yīng)考慮用戶的認(rèn)知水平、學(xué)習(xí)目標(biāo)等個(gè)性化因素,以及知識(shí)點(diǎn)之間的邏輯關(guān)系.

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

因此,本文將知識(shí)圖譜融入學(xué)習(xí)資源推薦模型,構(gòu)建語義網(wǎng)絡(luò),綜合考慮用戶的興趣偏好、學(xué)習(xí)資源所涵蓋知識(shí)點(diǎn)的關(guān)聯(lián)度與中心度,建立多目標(biāo)優(yōu)化模型.使用自適應(yīng)多目標(biāo)粒子群(AMOPSO)算法得到Pareto最優(yōu)解集,進(jìn)行個(gè)性化學(xué)習(xí)資源的推薦.

1 學(xué)科知識(shí)圖譜的構(gòu)建

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

1.1 實(shí)體抽取

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

其中,nij表示詞條ti在學(xué)習(xí)資源dj中的詞頻,表示學(xué)習(xí)資源dj中的全部詞條數(shù),|D|表示課程學(xué)習(xí)資源庫中全部的文檔數(shù),表示包含ti的學(xué)習(xí)資源文檔數(shù),|N|表示學(xué)習(xí)資源dj中詞條的個(gè)數(shù).

1.2 關(guān)系抽取

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

表1 知識(shí)點(diǎn)間的關(guān)系定義

1.3 本體構(gòu)建

本文以C 語言程序設(shè)計(jì)課程為例,采用斯坦福大學(xué)開發(fā)的Protégé工具進(jìn)行本體的構(gòu)建.如圖1.

圖1 課程本體部分關(guān)系示例

2 基于知識(shí)圖譜的多目標(biāo)學(xué)習(xí)資源推薦模型的構(gòu)建

2.1 學(xué)習(xí)資源數(shù)學(xué)模型的建立

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

2.2 用戶數(shù)學(xué)模型的建立

將用戶特征模型表示為:U=(K(U),P(U)).其中,K(U)表示由用戶歷史學(xué)習(xí)行為得到的用戶知識(shí)庫.P(U)={p1,p2,p3,p4}表示用戶U的學(xué)習(xí)風(fēng)格,學(xué)習(xí)風(fēng)格的不同對(duì)學(xué)習(xí)資源類型的選擇會(huì)有影響,依據(jù)Kolb學(xué)習(xí)風(fēng)格類型將學(xué)習(xí)風(fēng)格類型分為發(fā)散型、聚合型、同化型和調(diào)節(jié)型4 種.同一個(gè)用戶會(huì)表現(xiàn)出多種學(xué)習(xí)類型的傾向,p1、p2、p3、p4分別表示用戶U屬于4種學(xué)習(xí)風(fēng)格的傾向程度,s.t.0≤p1,p2,p3,p4≤1,且

2.3 基于知識(shí)圖譜的推薦模型

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

學(xué)習(xí)資源包含的知識(shí)點(diǎn)與用戶知識(shí)庫的距離如下:

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

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

計(jì)算后得到距離K(U)最小的資源即最值得推薦的學(xué)習(xí)資源.

學(xué)習(xí)資源類型與用戶學(xué)習(xí)偏好之間的差異如下:

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

圖2 用戶知識(shí)庫與資源知識(shí)庫的關(guān)系示意圖

3 基于知識(shí)圖譜的多目標(biāo)學(xué)習(xí)資源推薦模型求解

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

3.1 自適應(yīng)多目標(biāo)粒子群算法

標(biāo)準(zhǔn)多目標(biāo)粒子群算法(MOPSO)迭代公式為:

其中,r1、r2為0～1 之間均勻分布的隨機(jī)數(shù);pi為粒子個(gè)體的最佳位置;pg為群體所發(fā)現(xiàn)的最佳位置;xi(t)為t時(shí)刻粒子的位置;vi(t)為t時(shí)刻粒子的速度;ωi為算法慣性權(quán)重;c1、c2為學(xué)習(xí)因子.

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

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

c1、c2第t次迭代時(shí)取值公式為:

其中,c1,ini和c2,ini分別代表c1、c2的初始值,c1,fin和c2,fin分別代表c1、c2的迭代終值.改進(jìn)后的速度權(quán)重自適應(yīng)變化因子 ωi可以有效的平衡算法的搜索區(qū)域,學(xué)習(xí)因子的異步變化使得粒子加強(qiáng)了算法初始階段的全局搜索能力,在算法后期有利于收斂到全局最優(yōu).

3.2 算法流程

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

Step 1.初始化種群和速度.計(jì)算目標(biāo)函數(shù)值并將非支配解加入外部種群存檔NDset.

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

Step 3.更新全局最優(yōu)位置.

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

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

圖3 AMOPSO 資源推薦流程圖

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

本文利用Matlab R2016a 實(shí)現(xiàn)上述算法,為了觀測(cè)算法的有效性和可行性,以標(biāo)準(zhǔn)MOPSO、AMOPSO做對(duì)比實(shí)驗(yàn)分析推薦性能的差別.求解后從Pareto 解集中選取Top-10 作為推薦的學(xué)習(xí)資源;若Pareto 解集中的數(shù)據(jù)小于10 條,則選擇所有的候選集作為推薦內(nèi)容.

從某網(wǎng)絡(luò)學(xué)習(xí)平臺(tái)數(shù)據(jù)中爬取了部分包含C 語言課程知識(shí)的文檔與在線學(xué)習(xí)數(shù)據(jù)信息,經(jīng)過數(shù)據(jù)清洗和分詞處理后抽取知識(shí)點(diǎn)和關(guān)系,構(gòu)建課程本體并經(jīng)過補(bǔ)全形成實(shí)驗(yàn)數(shù)據(jù)集.

4.2 算法參數(shù)設(shè)置

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

表2 算法參數(shù)設(shè)置

4.3 實(shí)驗(yàn)結(jié)果分析

為了觀察推薦效果,使用HV (Hyper Volume)值對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析.由表3和圖4可知,AMOPSO的HV 指標(biāo)最好值、均值、最差值均高于MOPSO,說明AMOPSO的收斂性和多樣性優(yōu)于MOPSO;同時(shí)AMOPSO的HV 值分布范圍窄于MOPSO,說明AMOPSO的穩(wěn)定性更好,在進(jìn)行學(xué)習(xí)資源推薦時(shí)的綜合性能更好.

表3 實(shí)驗(yàn)中HV 值的統(tǒng)計(jì)結(jié)果

圖4 MOPSO和AMOPSO的HV 箱線圖

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

圖5 MOPSO和AMOPSO的Pareto 前沿面

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

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

圖6 AMOPSO 算法慣性權(quán)重隨迭代次數(shù)變化曲線圖

4.4 收斂性能分析

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

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

由表4可知,AMOPSO的IGD 指標(biāo)均值和方差均比MOPSO 小,表明AMOPSO在收斂性和分布均勻性上均優(yōu)于標(biāo)準(zhǔn)MOPSO.

表4 實(shí)驗(yàn)中IGD 指標(biāo)的統(tǒng)計(jì)結(jié)果

4.5 推薦效用的評(píng)價(jià)指標(biāo)

本文采用五折交叉驗(yàn)證,將數(shù)據(jù)集隨機(jī)分為5 份,每次選取其中一份作為測(cè)試集,另外4 份作為訓(xùn)練集,重復(fù)5 次,每次選取不同的訓(xùn)練集.將5 次實(shí)驗(yàn)的平均值作為推薦效用的評(píng)價(jià)指標(biāo).對(duì)推薦算法結(jié)果的分析,使用3個(gè)指標(biāo):查準(zhǔn)率(Precision,P),召回率(Recall,R)以及F1-Score 值(F):

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

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

圖7 評(píng)價(jià)指標(biāo)條形圖

5 結(jié)論

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