支撐教學資源的推薦算法原型系統設計*

李瑋，何富樂，駱嘉偉，殷櫻

（湖南大學信息科學與工程學院，湖南長沙410008）

支撐教學資源的推薦算法原型系統設計*

李瑋，何富樂，駱嘉偉，殷櫻

（湖南大學信息科學與工程學院，湖南長沙410008）

計算機的普及和網絡的發展改變了現有的教學模式，教育資源的數字化、網絡化成為了一個必然趨勢。在這個“信息過載”的時代，推薦機制根據用戶特征興趣解決所需信息和搜索之間的矛盾。然而傳統推薦算法計算效率低下，存在可擴展性低、算法運用場景不明確等問題。Hadoop利用分布式的環境，將計算任務通過資源調度分配到集群環境中，多臺機器并行運算，減少了計算時間。所以本文在推薦算法理論和實現機制的基礎上闡述了基于項目的ItemCF的實現方法和實現過程，有效增加推薦算法的實用性，為個性化推薦和教學資源的管理提供了便利。

Hadoop；推薦機制；ItemCF；個性化推薦

互聯網在改變人類生產生活的同時，也為學習和教育帶來了一場深刻變革，這場變革就是在信息技術支撐下的教育信息化［1］。網絡中教育資源管理平臺是將多種形式的教學資源有層次地組織起來，對教學資源進行采集、管理、檢索和利用的學習輔助系統，它打破了傳統教育方式在時空上的限制，使學習者能夠更加靈活、自主地學習［2］。然而，隨著教育資源在數量和規模上的不斷擴大，網絡上的資源也呈現“爆炸式增長”，面對大量的教學資源，用戶很難從中發現適合自己的有用信息，資源利用率低。因此針對用戶的個性化推薦服務成為網絡遠程教育中亟待研究和解決的問題［3］。

推薦機制的存在就是為了消費者解決所需信息與搜索之間的矛盾。在推薦過程中，系統能夠自動地追蹤用戶的歷史行為并據此為每位用戶的興趣建模，從而給用戶推送能夠滿足他們興趣和需求的信息［2］。本文將個性化推薦技術應用在資源分配網中，對用戶和資源進行建模，利用推薦算法為用戶推薦最適合的學習資源。本文設計的原型系統也可以廣泛應用于遠程教育資源中，這樣學習者就不再是被動的網頁瀏覽者，而是信息的主動參與者［1］。

文中通過編寫mapreduce程序，構建用戶物品矩陣，構建物品相似度矩陣，獲得相似度。運用hadoop［4］搭建分布式環境，以實現算法分布式運算的效果。設計出基于Hadoop推薦算法的比較模型，對不同場景下的所得結果誤差進行繪圖分析，得出不同相似度計算方法之間優劣的結論。同時又通過定時器以及其他方式，提前將推薦的結果計算好，存儲數據庫中。對推薦時直接獲取計算好的結果進行展示，以實現實時推薦［5］的功能。

一、基于項目的推薦算法（ItemCF）

目前的推薦算法中有很多分類方法，最主要的有兩種：基于用戶的推薦算法和基于項目的推薦算法。本文采用的是基于項目的推薦算法。

基于項目的推薦算法是著重點在于項目的相似度計算。雖然該算法與基于用戶的推薦算法都是基于社會化的環境，但是在比較大型的網站上的時候，由于用戶數量往往大于相應資源的數量，以及項目的數據量是相對穩定的，在這情況下該算法不僅相似度計算量小，而且計算結果不需要頻繁更新，用戶獲得相應的更快的數據資源。

基于歐氏距離的相似性（歐氏距離）［6］是最簡單和最容易的相似度計算方法

公式（1.1）表明，當距離d（x，y）越小的時候，相似度越高。那么計算相似度的條件是用戶最少得有一個共同評分的資源，就能用該相似度；如果沒有共同評分項，那么歐式距離將失去作用。

皮爾森相似度算法［7］表現了變量之間的線性關系的緊密程度，它的這種程度用一個值域表達在［-1，1］這個范圍內。當兩個變量關系變大時，相關系數向極限值靠近。他們存在著數學上的正相關、負相關，和不存在關系。

用數學公式（1.2）表示，皮爾森相關系數等于兩個變量的協方差除于兩個變量的標準差。

該相似度算法有明顯的兩個缺點，一個在于沒有考慮評分項之間是否會有重疊的部分。其次就是當用戶之間只存在一個交集的時候，它也不能進行計算。

余弦相似度算法［6］是在向量空間中把向量之間的夾角，取其余弦值作為評判兩個資源有多少是相似的。相比距離方法的度量，該算法更注重向量間的差異是在方向上，而不是距離或他們之間的長度。

由公式（1.3）可知，類似于歐氏距離，基于余弦相似度計算方法是用戶偏好在N維坐標點。通過連接點與坐標系原點構成一條直線（矢量）。用戶之間的相似性是余弦兩個向量夾角的所得到的值。余弦相似度著重從方向上區分他們的不同，但在數值上沒有那么著重。所以在大多數的時候，余弦相似度算法是用于利用評分來將用戶興趣進行歸類以及尋找差異，同時統一了度量標準。

基于谷本系數［8］的相似性算法也稱叫Jaccard系數，是余弦相似度的延伸，也常用于文檔相似度的計算。

在公式（1.4）中X是用戶x所偏好的所有資源的集合，Y表示用戶y所偏好的所有資源的集合。在taste里，實現Tanimoto相似度的類是TanimotoCoefficientSimilarity，可以看出這種算法適用于用戶對資源的喜歡程度是0和1這個條件。主要用于處理無打分情況的偏好數據。

對數似然比［9］主要應用于自然文本語言庫中兩個詞的搭配關系問題，對數似然統計量的計算方法為：

在公式（1.5）中O表示的是實際觀測頻次，E指的是期望頻次。對數似然相似度算法原理是統計數據中有多少是重疊的，有多少是不重疊，以及都沒有的個數。主要用于處理無打分情況的偏好數據，比Tanimoto系數的計算方法更為智能。

斯皮爾曼相關性可以理解為是排列后（Rank）用戶喜好值之間的Pearson相關度。假設對于每個用戶，我們找到他最不喜歡的物品，重寫他的評分值為“1”；然后找到下一個最不喜歡的物品，重寫評分值為“2”，依此類推。然后我們對這些轉換后的值求Pearson相關系數，這就是Spearman相關系數［10］。

斯皮爾曼相關度的計算舍棄了一些重要信息，即真實的評分值。但它保留了用戶喜好值的本質特性——排序（ordering），是建立在排序的基礎上計算的。

二、原型系統的設計

基于Hadoop的推薦算法的實現和比較的主要目標是設計一個能夠比較不同算法之間的誤差，從而選取較好的推薦算法，在此場景下給用戶比較準確的推薦，不僅僅實現資源的推薦，在此基礎上還實現線下計算，線上推薦的，用戶評分，收集用戶新評分的功能。

原型系統主要實現以下幾個方面的目標：

1）基于Hadoop實現比較完善推薦系統，并保證系統的整體功能性、數據層次性以及實用性［11］。

2）解決現有推薦中準確度低的問題，以及數據存儲效率耗時長的問題［12］。

3）能夠為應用層的用戶提供準確推薦，展示不同算法之間的誤差，選取最優算法。

4）設計良好的系統框架，使得前臺和后臺的之間的分工明確，保證系統設計層次的清晰度和獨立性。

5）通過cloudstack以及Hadoop可視化進行資源調度，保證資源合理分配和系統穩定性。

系統采用的是三層架構，分別為表現層、業務邏輯數據層［13］、Hadoop數據處理層。三層體系中業務邏輯層負責功能訪問、數據訪問等操作。客戶端不直接與后臺數據庫進行信息交流，而是通過表現層與業務邏輯層的雙向通信，再有業務邏輯層與數據庫的雙向通信。Hadoop數據處理層則是進行評分數據計算，然后進行結果返回的層次。

采用線上推薦、線下計算的方式。線上用戶在瀏覽器中瀏覽的推薦數據直接從關系型數據庫中讀取推薦，既不妨礙用戶瀏覽，也不影響瀏覽速度。線下通過Hadoop計算，改進相應參數以及部分調整算法，在實現并行運算的同時，提高了計算結果的效率。然而在計算完成結果后，結果集上的數據量往往會有百萬級別，在存入數據庫的過程中會產生溢出，容易造成數據丟失。所以采用分段式存儲，根據事務或者其他條件來將數據分成相應大小的數據塊，將每一塊都按照優化后的數據庫語句執行存儲，極大地縮短了存儲的時間，而且保證了數據的完整性。通過以上模式可以很好的解決現在推薦系統中存在的普遍問題。

三、原型系統的實現

用戶可以通過瀏覽器打開推薦學習系統的用戶任意瀏覽界面，初始化界面如圖1所示。

圖1　系統初始化界面

真實的數據能夠很好地反映本文推薦算法的準確性以及可信度。為了驗證算法分析有效性，本文采用的數據集來自于開源的電影網站GroupLens Research下的MovieLine［14］的1M數據集，大概有來自6000名用戶對4000部電影的100萬條評分數據。數據集中的電影等同于我們學習資源。本文中將數據集按兩類進行劃分：測試集與訓練集。劃分的規則是按照用戶相關性系數呈現一個規律性變化（即由最高的逐漸降低）劃分的。將原始數據集隨機抽取70%作為訓練集，其余30%作為測試集。如何確定相關性系數是否變化了或者說有降低的趨勢。簡單的一個例子：隨機抽取一個用戶的所有評分數據，然后抽取與該用戶有相關的所有用戶的的資源評分，從該用戶的所有評分數據中抽取30%的真實評分作為測試數據，其余的評分以及與該用戶相關的所有用戶的資源評分作為第一次的訓練集，這個時候當前的訓練集的稀疏度肯定是最大的。然后記錄下此時的稀疏度。然后在當前的訓練集中隨機10000加入其它無相關評分數據，記錄下這個時候相關性評分數據占總評分數據的百分比，將得出的百分比與第一次的百分比進行比較，可以看出稀疏度是降低的，即為第二次的相關性的百分比。以此類推，記錄下9次的稀疏度。對于每個用戶都進行這樣的操作，再取平均值，即為所有訓練集的稀疏度，而且也呈現百分比為一個下降的趨勢。本文最后劃分的數據集系數度分別為：99.941%、89.772%、81.482%、74.593%、68.778%、63.805%、59.502%、55.743%、52.430%。將數據集輸入到原型系統中，可以分析得出不同算法以下幾個方面的比較結果。

（1）采用具有評分的數據在不同稀疏度下比較

根據評分做預測的趨勢可以從圖2看出：COOCCURRENCE算法［15］的曲線走勢是最平緩，而PEARSON_CORRELATION算法其次，但是相應的，COOCCURRENCE的誤差平均值為0.592，而EUCLIDEAN算法的誤差平均值最小，計算的相似度是最高的。故在一般情況下考慮使用EUCLIDEAN算法。因為加入評分的訓練集數目一定，而且與當前用戶相關的數據矩陣，越來稀疏的情況下，COOCCURRENCE的預測能力是最好的。故在矩陣稀疏的情況下，可以考慮使用COOCCURRENCE。也可以考慮使用調整推薦數目，推薦數據偏好增大，提高過濾閾值，增強推薦效果。

圖2　考慮評分相似性算法在不同稀疏度下的比較

（2）采用忽略評分的數據在不同稀疏度下比較

在我們實際學習環境中，用戶可能對某個學習資源不會給出具體分值，只是點擊或關注某個學習資源，即我們只知道用戶是否偏好，但是沒有打分，這種情況下也能完成學習資源的資源。忽略評分的推薦效果如圖3所示。

從沒有根據評分做預測的走勢圖3可以看出：COOCCURRENCE算法的曲線走勢是最平緩的，EUCLIDEAN算法其次，但是相應的，COOCCURRENCE的誤差平均值為9536.67，雖然也能預測到相應的項目，但是與實際評分差距太大。而EUCLIDEAN算法的誤差平均值最小，計算的相似度是最高的。故在沒有評分項進行推薦的時候考慮使用EUCLIDEAN算法。雖然之前的算法中COOCCURRENCE在有評分的情況下會比EUCLIDEAN算法較好，但是因為該算法必須依賴評分，否則誤差太大，以及PEARSON_CORRELATION完全依賴評分，故在這情況下沒有推薦數據的產生。

圖3　不考慮評分相似性算法在不同稀疏度下的比較

（3）單節點在不同數據集不同算法中獲得結果需要時間的比較

從圖4可以看出：各類算法的所需時間是不一樣的，而且他們的平均時間：PEARSON_CORRELATION＜TANIMOTO＜COSINE＜EUCLIDEAN＜LOGLIKELIHOOD＜COOCCURRENCE，所以，在一定的程度上可以考慮混合推薦或者是根據數據集，相關性稀疏度的大小來選擇不同的算法。

圖4　單節點不同算法時間比較

（4）多節點在相同數據集不同算法獲得結果需要時間的比較

從多節點走勢圖5可以看出：各類算法的在不同數量的節點上運行的時間是不一樣的，算法之間所需時間的大小為：EUCLIDEAN＞COOCCURRENCE＞LOG-LIKELIHOOD＞PEARSON_CORRELATION＞TANIMOTO＞COSINE，所以，在一定的程度上可以考慮混合推薦或者是根據數據集，相關性稀疏度的大小來選擇不同的算法。

圖5　多節點不同算法時間比較

目前推薦算法有多種，不能一概而論。對于處理不同的情況，需要考慮多方面的東西，如參數、硬件、環境等等。綜合來說，常用推薦算法的相似度計算方式有上面的這幾種，但是他們的比較合適的使用范圍卻有不同，EUCLIDEAN適用于要求評分比較準確的方向。TANIMOTO、LOGLIKELIHOOD適用于評分為0或者1的情況。COSINE適用于評分相相差不大的情況。而PEARSON_CORRELATION適用于有評分，且用戶之間相關性比較大的數據集。針對很對不同的情況，可以使用混合推薦，或者調整不同的參數，改進算法原理，比單個算法推薦要更好。

四、結語

在網絡教育中引入個性化推薦技術對教育資源進行過濾，實現教育資源的個性化推薦服務，將用戶對資源的被動接受轉變為資源對用戶的主動推送，對滿足用戶的個性化需求以及實現資源的有效利用有著重要的現實意義［16］。本文就是在基于ItemCF算法中的上進行改進和實現。在基于傳統物品推薦算法基礎上，增加了將運算在Hadoop上進行，在算法中采用了線上實時推薦、線下計算的方式，以及cloudstack的資源調度監視的方式，彌補傳統的算法中的實時推薦不足、推薦精度不夠、資源調度不能可視化等缺點。本文對基于內容的算法的基礎上進行了基于Hadoop推薦算法實現與比較。通過充分的實驗驗證和客觀的系統實現，說明該模式具有良好的實用性。

［1］姜媛媛.遠程教育資源網中的個性化資源推薦研究［D］.西安：西安電子科技大學，2011.

［2］楊帆.網絡教育資源分類及推薦機制研究［D］.北京：首都師范大學，2014.

［3］王龍.教育資源推薦服務中若干關鍵技術的研究［D］.吉林：吉林大學，2013.

［4］崔杰，李討深，蘭紅星.基于Hadoop的海量數據存儲平臺設計與開發［J］.計算機研究與發展，2012，5（z1）：12-18.

［5］吳吉義，林志潔.基于協同過濾的移動電子商務個性化推薦系統若干研究［J］.電子技術應用，2007，1（b2）：5-8.

［6］吳桂玲.基于歐氏距離和余弦相似度特征選擇的入侵檢測模型［J］.中小企業管理與科技，2010，02（b2）：230-231.

［7］Ahn H J.A new similarity measure for collaborative filtering to alleviate the new user cold-starting problem［J］. Information Sciences，2008，178（1）：37-51.

［8］文俊浩，舒珊.一種改進相似性度量的協同過濾推薦算法［J］.計算機科學，2014，41（5）：68-71.

［9］張明敏，張功萱，周秀敏.對數似然相似度算法的MapReduce并行化實現［J］.計算機工程與設計，2015，36（5）：1233-1238.

［10］Mahout的相似性度量（相似度算法）［DB/OL］. http：//blog.sina.com.cn/s/blog_546abd9f0101bt45.html.

［11］Gao，M，Wu，ZF.Userrank for item-based collaborative filtering recommendation［J］.Information Processing Letters，2011（9）：440-446.

［12］任飛，甘小冰.個性化移動電子商務優化代理仲裁機制研究［J］.計算機應用，2005，20（d4）：74-77.

［13］丁香乾.個性化推薦技術中的協同過濾算法研究［D］.海南：中國海洋大學，2011.

［14］Qian Quan，Wang Tian-Hong，Zhang Rui，Xin Ming-jun.A model of cloud data secure storage based on HDFS［A］.Computer and Information Science（ICIS）2013 IEEE/ACIS 12th International Conference on，2013：173-178.

［15］凌光，王明春，馮嘉毅.基于co-occurrence相似度的聚類集成方法［J］.計算機應用，2011，31（2）：441-445.

［16］吳夢蘭.Web內容推薦算法在遠程教育中的應用［J］.電腦知識與技術，2011，7（26）：6532-6533.

（編輯：王曉明）

TP3

A

1673-8454（2016）05-0033-05

2013年湖南省普通高等學校教學改革研究項目“基于云計算的移動應用實踐教學平臺研究與開發”（批準編號：湘教通［2013］223號）。