基于改進位置社交的近鄰知識推薦算法*

李 月 王槐彬

（廣東交通職業技術學院信息學院 廣州 510650）

1 引言

推薦系統是隨著互聯網應用的不斷發展及互聯網數據內容不斷擴大而產生的一種系統，該系統的主要目的是從海量數據里篩選出用戶感興趣或者有價值的信息對用戶進行推薦。目前常用的海量數據檢索系統主要為搜索引擎，如Google、Baidu等。搜索引擎雖然具有應用范圍廣泛、滿足大部分用戶的信息檢索功能等優點，但是對于一些特定應用領域，如電子商務應用、在線學習系統、特定興趣范圍檢索（如影片、書籍、音樂），卻無法滿足用戶個性化、多樣化、內在需求復雜化的現狀。在特定內容的應用上，利用推薦算法構建個性化推薦系統，能有效發掘用戶潛在的隱性需求，將用戶真正需要或感興趣的內容推薦給用戶，從而提升用戶體驗，增強用戶對系統的粘性。

2 推薦系統

Resnick［1］等于 1997 年給出了推薦系統的定義。一個完整的推薦系統由用戶模型、產品模型與推薦算法3部分組成，稱為模型三元組。用戶模型用于獲取、表示、存儲用戶的瀏覽行為與購買歷史數據，這些數據可以通過顯示與隱式2種方式獲取。顯式獲取是通過用戶行為，如對產品的評分、喜歡或不喜歡某個產品等來表達對產品的偏好程度，直接得到數據；隱式獲取是通過系統對用戶行為，如網頁瀏覽、購買日志等進行自動追蹤來獲取用戶對產品的興趣偏好，間接得到數據。產品模型用于表示、存儲產品的特征屬性。推薦算法作為推薦系統的關鍵環節，主要通過挖掘用戶歷史數據中蘊含的規律來獲取用戶的興趣偏好與消費習慣［2］。不同推薦算法側重的領域不同，當前主流的推薦算法包括基于內容的推薦、基于協同過濾的推薦、混合推薦算法、基于社交網絡的推薦以及隨著網絡技術及GPS技術發展而興起的基于興趣點的推薦等。

3 社交網絡與LBSN

社交網絡是近年來隨著人與人之間溝通方式的變化而產生的一種新型交流方式，主要指不同年齡、不同職業、不同地區和不同興趣愛好的人通過網絡匯集起來，構建出的一個龐雜的交流圈。基于社交網絡的推薦算法核心思想為利用社交網絡數據捕捉用戶興趣偏好及好友信息，并根據獲取的數據為用戶進行個性化產品推薦、好友推薦與信息流的會話推薦［3］。基于位置社交的網絡（location-based social network，LBSN）屬于社交網絡的一個變種，主要通過采集用戶的位置信息建立與其他用戶的社交聯系。LBSN的簽到數據包含了豐富的用戶隱式信息，可以用這些位置簽到數據、社交關系、評論數據等內容挖掘用戶感興趣的內容，實現有價值的推薦［4］。

為用戶推薦可能感興趣的地理位置的任務稱為興趣點（point-of-interest，POI）推薦。基于LBSN算法的興趣點推薦與傳統的社交網絡推薦存在區別。LBSN興趣點推薦在模型上主要構建從用戶到地理位置的交互模型，通過挖掘用戶在簽到興趣點上的顯式數據和隱式反饋數據，經過算法計算，得到用戶有可能感興趣的興趣點進行推薦。根據融合因素不同，LBSN中的興趣點推薦算法主要分為四大類［5］：基于簽到數據的興趣點推薦算法、基于地域影響力增強的興趣點推薦算法、基于社交影響力增強的興趣點推薦算法以及基于時域影響増強的興趣點推薦算法［6］。

4 學習網絡與LBSN

學習網絡指各類以知識傳播和用戶學習為主要目的的網絡。隨著信息化技術的不斷改進和數字化學習需求的不斷增長，各類學習網絡也越來越普及。因為學習網絡中也存在用戶、學習產品等組成要素，可將其看做社交網絡的一部分。學習網絡和社交網絡相比，具有一定相似性，但由于學習網絡獨特的用戶目標，二者之間也存在明顯不同［7～9］。社交網絡中，用戶對產品的評價信息具有明顯的情感極性，會通過不同表述方式表達喜歡、不喜歡、一般等喜好程度，在學習網絡中用戶往往表達的是負面情感傾向，比如對于某個知識點不了解，那么用戶的評價可能多表現為提問、疑問、表達不理解等偏負面的評價，而對于那些已經掌握的知識點，用戶往往會進入下一個內容的學習而不予評價。在社交網絡中，推薦內容主要為用戶感興趣的產品，屬于用戶正面情感表達下得出的符合其愛好的正面情感產品［10］。在學習網絡中，如需要向用戶推薦產品，該產品應當為用戶表達困惑或不理解時與該知識點相關聯的知識點，通過關聯知識點的學習解決用戶當前學習中的疑難問題，二者的推薦目標是完全不同的。

與基于興趣點的LBSN推薦系統相比較，學習網絡中的知識推薦系統構建更接近LBSN系統的模型和算法［11］。LBSN推薦系統中，用戶通過簽到數據表達對該興趣點的正面情感評價，而用戶不喜歡的地點也不會簽到，負面情感評價數據會被忽略。這一點正好與學習網絡中用戶對知識點只表達負面情感數據而忽略正面評價數據相反。基于興趣點的LBSN中用戶的簽到次數隱含了用戶對該點的興趣評分［12］，而在學習網絡中用戶對知識點的點擊次數和時長蘊含了該用戶對該知識點的不理解程度（對于易于理解的知識點用戶不會多次學習或學習較長時間）。因此，對于以學習推薦為目的的學習網絡推薦系統，可參照基于興趣點的LBSN模型構建，通過改進LBSB推薦算法，達到學習網絡中的推薦目的。

5 改進LBSN算法的近鄰知識推薦

5.1 問題描述

學習網絡推薦的目的是利用用戶已有的訪問數據和學習網絡中的其他數據信息對用戶下一步需要訪問的知識點進行預測，并將預測結果推薦給用戶作為其學習推薦列表。將學習網絡中的知識點看做LBSN推薦系統中的興趣點，可采用經典LBSN模型中的用戶-地點模型。在學習網絡中，先構建包含2種實體的集合關系：用戶集合與知識點集合［13］。學習網絡包含 m 個用戶，集合 U=｛u1，u2，…，um｝；包含N個知識點集合K=｛k1，k2，…，kN｝。

5.2 學習網絡中的改進LBSN算法

5.2.1 構建用戶-知識點學習情況矩陣

用戶u點擊學習過的知識點k集合表示為Ku。每個知識點給予唯一標識編碼，并將用戶的學習行為記錄抽取出來，構成用戶－知識點學習評分矩陣F∈RM×N，學習情況矩陣F中每個元素fij表示用戶i在知識點j上的學習情況評分，用戶-知識點評分矩陣如表1所示。

表1 用戶-知識點評分矩陣

由于學習網絡中用戶大多不愿花時間去對已學習過的知識點作出評價，故學習網絡中無法收集到足夠的顯式評分數據。需將用戶對知識點的訪問次數或訪問時長或訪問行為方式等數據提取出來，轉化為顯式評分。如用戶點擊的次數反映了用戶對該知識點理解的難易程度隱式信息，次數越高或停留時間越長，表明該知識點對該用戶而言難度越高。對于學習行為中的隱式數據，首先對其進行預處理轉換為評分數據，評分范圍設置為1到5。如果某項知識點在某個用戶上獲得的評分為5，表示該用戶對該知識點感興趣或認為該知識點難度較高。如果評分為1則表明該用戶對該知識點不感興趣或認為該知識點非常簡單。在系統初始情況下，用戶對知識點的訪問是隨機的，可能會有大量知識點學習情況評分存在缺失。

5.2.2 構建用戶-知識點短路徑集合

在LBSN推薦算法中，認為任何事物都是相關的，但是相對于距離遠的事物，距離近的事物之間更加相關［11］。在學習網絡中，用戶在學習當前知識點A后最先訪問的知識點B往往是用戶認為和知識點A邏輯聯系最密切的內容，因此，在學習網絡中，知識點之間也存在類似LBSN系統中的興趣點距離概念。對于學習網絡中的知識點距離，可將從一個知識點A直接跳轉到另一個知識點B距離標記為1，從B再跳轉到知識點C則標記A到C的距離為2，依次獲取知識點網絡中節點的距離值，構建知識點距離矩陣。考慮經歷多次跳轉后的內容關聯緊密程度，結合三度影響力理論［14］，將不同知識點間的距離最大標記為3，也就是說從一個知識點到另一個知識點如果經歷了3次以上的跳轉那么則認為這兩個知識點間的距離非常遠，不存在強邏輯聯系。在知識點距離矩陣上融合用戶信息，并將用戶i在知識點集合K上所有低于3次的知識點跳轉提取出來，即構成了用戶-知識點之間的路徑集合。Pi表示用戶i在學習網絡中知識點學習路徑跳轉小于3次的路徑集合，則學習網絡中m個用戶在n個知識點上的用戶-知識點路徑集合M=｛P1，P2，…Pm-1，Pm｝。

5.2.3 推薦算法

在學習網絡中，相似的用戶對于知識點的學習需求也是相似的。常見的計算用戶相似度算法為余弦相似度計算，首先采用余弦相似度進行用戶相似度計算［15］。

定義用戶U和用戶V共同評分的學習知識點集合用 RU，V表示，ru，i和 rV，i分別表示用戶 U 和用戶 V對學習知識點i的評分，RU和RV則分別代表了用戶U和V對學習知識點的平均評分。用戶間的相似度通過向量間的余弦夾角度量，將用戶對項目的評分看做n維項目空間的向量，則用戶U和用戶V的相似度SUV，可按照余弦相似度公式計算：

由于學習網絡中用戶對知識點評分稀疏性的問題，為構建更為全面、有價值的推薦知識點，應根據用戶相似度擴大選取當前用戶的n個相鄰用戶［16］，并將相鄰用戶的知識點學習路徑合并構成候選路徑集合M′。根據之前確定的用戶-知識點之間的短路徑集合M′，任意用戶i與知識點l之間的（ui，kl）都可通過用戶-知識點路徑集合的特征值計算特征值向量：

根據邏輯回歸公式可知，用戶i需要去到知識點l進行學習的概率為

其中為特征向量中的特征權值，可通過訓練數據得到。根據計算到的概率ρ進行排序，依據概率從大到小選取合適數量的知識點進行推薦即可。

6 實驗與分析

本文采用超星慕課學習平臺上的學習數據作為實驗數據來源，目前超星慕課平臺上已構成一個相對完善的學習網絡，學習者之間的關聯關系包含好友關注、點贊、討論、聊天、學習者自行組建學習小組、學習者共讀書籍、共同加入同一直播或在線公開課等多種社交行為。系統中可采集學習者時間記錄空間數據，通過學習者時間記錄空間的數據解析可繪制學習者在學習空間完整的學習軌跡，如果將該軌跡上的不同知識點看做LBSN網絡中的興趣點，則完全可構建出學習網絡中的類LBSN網絡。實驗抽取超星慕課平臺某一課程學習者共計223人的學習行為記錄數據，該數據記錄的是學習者在40個知識點上的學習行為數據以及學習者之間的社交關系數據及行為數據，其中社交關系及行為數據為3699條，學習行為數據12188條。因為目前在學習網絡領域無權威算法對比推薦的效果，故該算法通過人工標記形式檢驗推薦的質量。實驗采集了160個學習網絡中參與了同一門課程學習的自愿者人工打分標記推薦效果。根據當前學習的知識點給出推薦學習的相關知識點，實驗參與者依據相關程度給出評分。

6.1 相似鄰居數量對推薦結果的影響

根據用戶相似度選擇一定數量的鄰居擴大候選學習路徑集合是改進LBSN算法中的一部分。實驗中通過調整候選鄰居參數生成不同的推薦結果，從實驗數據可以看到，當候選鄰居數遞增分別為1至10個相似鄰居時，160個人工標記對推薦效果滿意度的評價平均值整體呈上升趨勢（實驗采取5輪標記打分，分別記為實驗1到實驗5）。同時從實驗數據分析可知，當候選鄰居數為4或5時能取得較為滿意的推薦效果，但推薦質量并不會隨著候選鄰居數的增加而無限上升，即候選鄰居數存在一個最佳范圍，超出此范圍既增加了推薦計算的開銷又不會取得更好的推薦效果。

6.2 推薦對學習效果的影響

在學習網絡中加入推薦，能有效提升學習對象獲取有價值信息的效率，取得更好的學習效果。實驗選取160個學習網絡中參與了同一門課程學習的學習者在10個知識點上的學習數據進行對比，將160名學習者分為學習過程中有知識點推薦及無知識點推薦組，人數各為80人。分別采集一個星期內10個知識點下兩組學習者的平均學習時長、學習者在單個知識點上的反復學習次數、為理解單個知識點而跳轉到其他知識點進行學習的相關知識點平均學習數量以及對10個知識點進行考核的平均測驗成績進行對比，具體數據如下圖2所示。

圖2 學習效果對比

通過數據對比可知，有推薦組在平均學習時長上明顯低于無推薦組，表明學習推薦可縮短學習者對單個知識點學習理解的時間，提升其學習效率。同時，有推薦組相較于無推薦組在學習效果上能取得更好的平均成績，表明學習推薦能幫助學習者更加深入的理解所學知識點內容。

7 結語

為解決學習網絡中信息過載的問題，本文提出了一種改進LBSN算法的學習推薦算法。將學習網絡看做社交網絡及LBSN網絡的融合，通過用戶相似度計算及知識興趣點路徑計算，為用戶推薦有價值的知識點作為輔助學習的手段。實驗證明該算法能有效提升學習者的學習效率和質量。后續研究中還可深入研究學習網絡中專家用戶對學習推薦的影響因子問題以及通過挖掘學習網絡中的興趣組信息提高推薦準確性等。