基于協同過濾算法的習題系統的設計與實現

封俊

（太原學院計算機科學與工程系 山西省太原市 030032）

隨著互聯網的普及和大數據技術的發展，人們的學習方式也悄然生息地發生著變化，已經有越來越多的用戶選擇網絡習題系統隨時隨地的做著課后練習。傳統的習題系統大多采用關鍵字搜索技術，此類型系統早期為用戶提供了極大的便利，但隨著題目數量的增加，僅僅依靠關鍵字在茫茫題海中篩選出適合自身的題目，已經變得越來越難。本文將機器學習領域中的協同過濾算法引入習題系統，來為不同用戶提供個性化的題目推薦服務。

1 系統使用的相關技術

1.1 協同過濾算法

個性化推薦是一種高效的主動推送信息的手段，該項技術目前已經在各互聯網購物平臺得到廣泛應用,并取得良好的效果。然而，在習題系統領域中個性化推薦技術尚沒有得到應有的重視。在眾多個性化推薦平臺常使用的各種算法中，協同過濾算法是最為有效的。實踐中，主要采用基于用戶(User-Based)和基于項目(Item-Based)的兩種協同過濾算法，完成個性化推薦[1]。其基本原理是,在一個數據集合中計算用戶或者項目之間的相似度，由此獲得推薦值，根據推薦值的高低，將項目排序后推薦給用戶。

1.2 相似度

相似度是構成推薦優先級的依據。相似度的計算基于向量間距離，距離越短意味著相似度越高。選擇合適的相似度計算方法，可以有效提高推薦的準確率。相似度計算方法較多，并且每種方法都有各自適用的領域，經過綜合比較本文使用了以下兩種相似度計算方法：皮爾遜相關系數和余弦距離（余弦相似度）。

1.3 Mahout軟件庫

Mahout 是由Apache 軟件基金會推出的一個開源機器學習軟件庫。它主要關注機器學習的三個領域：協同過濾、分類和聚類，基于Mahout 可以實現快速構建機器學習平臺的任務[2]。Mahout 具備極為靈活的擴展能力，單機模式既可以方便的處理大量數據，當所處理的數據規模已經超過單機處理能力時，可以構建基于Hadoop的分布式計算平臺[3]。由于實驗數據規模尚未超越單臺服務器的處理能力，所以本文主要應用單機模式來實現推薦引擎。

2 基于協同過濾算法的習題系統的構建

2.1 系統主要功能

本系統在保留傳統基于關鍵字搜索引擎的基礎上，加入了基于協同過濾算法的推薦引擎[4]。搜索引擎要求用戶必須提供明確的搜索條件，在此基礎上對題庫進行搜索，向用戶呈現搜索結果。但隨著題庫規模的擴大，必然會出現信息過載現象，意味著搜索結果中會包含越來越多的干擾信息。而推薦引擎正相反，它不需要用戶提供明確的需求，其推薦算法主要基于用戶歷史行為和群體數據的分析，用戶數量越多和題庫規模越大，推薦結果的準確率就會越高。

系統結合兩種引擎技術的優點，為用戶提供高效且個性化的題目獲取手段，其運行流程如圖1 所示。

2.2 系統功能模塊

本系統按照不同功能劃分為以下幾個模塊：用戶模塊，數據存儲模塊，搜索引擎，以及推薦引擎。

（1）用戶模塊。此模塊實現用戶與系統交互相關的功能，包括用戶登錄界面、題目練習界面、用戶反饋界面等基本功能。此外，當用戶在線練習時，對其學習軌跡進行全程記錄,獲得用戶對所做題目的評分，完成推薦引擎所需數據的采集過程。

（2）數據存儲模塊。此模塊基于關系型數據庫構建，是系統基礎數據來源。主要包含注冊用戶數據表t_user、習題信息表t_exercises、用戶-題目關系表t_usr_exs，以及其他相應的輔助功能表。

（3）搜索引擎。用于接收用戶輸入的關鍵字，由此構建一個搜索請求，并根據搜索請求開始對題庫進行全文搜索。由于搜索請求不能唯一地標識題庫中的單個題目(項目)，相反，可能會有多個題目與搜索請求相匹配，因此，搜索引擎根據TF-IDF 算法對搜索結果按rating 值進行排序并返回給用戶。

（4）推薦引擎。個性化推薦是本系統的重要功能，當用戶從搜索引擎返回的結果中，選出所需題目，并完成此題目的練習之后，推薦引擎會自動向用戶推薦相關的題目。整個推薦過程無需用戶主動參與，只有當用戶對推薦結果不滿意時，才需要用戶重新輸入關鍵字進行搜索。

2.3 系統實現

由于數據存儲技術和搜索引擎技術已經比較成熟，故不再詳細敘述，本文重點闡述推薦引擎的實現過程。此推薦引擎構建于Mahout 機器學習平臺之上，由兩個模塊構成，實現了兩種推薦策略。第一種，User-Based 推薦策略，通過分析系統中所有用戶的歷史行為[5]和用戶對已完成題目的評分，發現與當前用戶興趣相似的用戶群，然后基于這些用戶的歷史偏好，為當前用戶進行相關推薦。基于用戶的推薦引擎模塊采用User-Based 推薦策略，其結構如圖2 所示。

第二種，Item-Based 推薦策略，它以題目（而不是用戶）之間的相似度為基礎，實現個性化推薦。基于項目的推薦引擎模塊采用Item-Based 推薦策略，其結構與基于用戶的推薦引擎模塊比較類似。

2.4 基于用戶的推薦引擎模塊具體實現步驟

圖1：系統流程圖

圖2：基于用戶的推薦引擎模塊結構圖

（1）構建數據模型。推薦引擎中數據的基本表示形式是偏好(preference)，它代表用戶和題目的關聯程度。偏好是一個三元組，包括用戶id、題目id 和用戶對題目的評分[6]（偏好值）。評分是一個整數，取值范圍從1 到5，其中1 代表用戶完全不認可該題目，而5 代表用戶極為認可該題目。Mahout 平臺提供了一個JDBCDataModel 接口，通過此接口可直接從數據庫“用戶-題目關系表(t_usr_exs)”中查詢出用戶id 與曾做過的題目id，以及此用戶對題目的評分，構成偏好三元組(user_id, exercise_id, pre_value)，由此構建數據模型DataModel。在DataModel 中用戶實際以向量形式來表示。

（2）計算用戶之間的相似度。用戶之間的相似度根據皮爾遜相關系數計算得來。皮爾遜相關系數常用于計算兩個向量間的相關性，計算公式如下：

其取值范圍是[-1,1]，相關系數的值越趨近于1，說明向量X和Y 的相關性越強，意味著用戶X 和Y 興趣的相似度越高；相關系數的值越趨近于0，說明向量X 和Y 的相關性越弱，意味著用戶X 和Y 興趣的相似度越低；如果相關系數為負值，則兩個用戶沒有共同的興趣。

圖3：題目推薦列表

系統中用戶之間的相似度由UserSimilarity 類表示，而PearsonCorrelationSimilarity 類的內部實現了皮爾遜相關系數的計算，通過以下代碼可以計算出用戶之間的相似度。

UserSimilarity similarity = new PearsonCorrelationSimilarity(data Model);

（3）生成最近鄰用戶的集合。將用戶之間的相似度從大到小進行排序，根據用戶鄰域計算法選出與指定用戶相似度最高的用戶群，生成最近鄰用戶的集合。用于計算用戶鄰域的方法有兩種：固定大小鄰域計算法和基于閾值的鄰域計算法。

固定大小鄰域計算法將鄰域集合的大小設為一個固定值，其實現過程較為方便快捷，但這個值過大可能會導致很多無關用戶進入集合；相反，這個值過小又可能導致很多相關用戶被排除出集合。所以需要反復測試才能為某個數據集找到最佳值，另外隨著數據集規模的擴大，鄰域集合的大小也需重新測試。

基于閾值的鄰域計算法通過設置相似度的閾值，將所有相似度超過此閾值的用戶選出，生成最近鄰用戶的集合。本系統采用了基于閾值的鄰域計算法，可以避免數據集規模持續擴大，而導致的算法參數反復修正的問題。經過驗證0.7 可以作為一個相似度閾值的合理定義。

系統中最近鄰用戶的集合由ThresholdUserNeighborhood 類代表，生成最近鄰用戶集合的代碼如下：

UserNeighborhood neighborhood = new ThresholdUserNeighborhood (0.7, similarity, dataModel);

（4）創建推薦器對象，生成題目推薦列表。經過以上三個步驟就完成了推薦數據的準備，現在可以創建推薦器對象了。

UserBasedRecommender recommender = new GenericUserBasedR ecommender(dataModel, neighborhood, similarity);

推薦器對象計算出相關項目的推薦值，根據推薦值的高低，生成題目推薦列表。

List recommendations = recommender.recommend(userId, 3);

推薦過程中為了降低服務器的計算量，提高內存使用效率，題目推薦列表中，每一個推薦項只包含兩個域：“題目id”和“推薦值”，題目推薦列表形式如圖3 所示。

（5）向用戶呈現推薦結果。由于推薦項中并沒有包含題目內容，為了向用戶呈現推薦結果，還必須根據“題目id”從數據庫習題信息表t_exercises 中查詢出完整的題目內容，生成學習界面，并返回給用戶。

2.5 基于項目的推薦引擎模塊具體實現步驟

基于項目的推薦引擎模塊與基于用戶的推薦引擎模塊的實現步驟基本相同，這里只討論兩者的不同點。

（1）計算題目之間的相似度。此模塊進行推薦的依據是題目之間的相似度，系統中題目之間的相似度根據余弦距離計算得來。余弦距離是通過計算兩個向量夾角的余弦值來衡量向量之間的相關性，計算公式如下：

其取值范圍是[-1,1]，余弦距離越趨近于1，則說明向量X 和Y 之間的夾角越接近0 度，意味著題目X 和Y 的相似度越高；余弦距離越趨近于-1，則說明向量X 和Y 之間的夾角越接近180 度，意味著題目X 和Y 的相似度越低。系統中題目之間的相似度由ItemSimilarity 類表示。

（2）無需生成近鄰題目的集合，直接通過以下代碼Recommender recommender = new GenericItemBasedRecommender(d ataModel, similarity); 創建推薦器對象，由推薦器對象生成題目推薦列表。

3 實驗結果分析

3.1 硬件環境

系統運行于PC 機上，具體配置為：4 核CPU，主頻3.2GHz，內存8G。

3.2 實驗數據

以某高校習題系統為例，選取了包含4736 名用戶和60000 道習題的數據庫作為實驗數據集，15 名學生參與系統測試。

3.3 實驗結果分析

經過多輪實驗，取實驗數據的平均值，可以得出以下結果。響應速度方面，采用User-Based 推薦策略，系統平均響應時間為1741ms；采用Item-Based 推薦策略，系統平均響應時間為2439ms。可以看出采用User-Based 推薦策略，系統響應速度更快。另一方面，參與實驗的用戶普遍反映User-Based 推薦策略的準確率更高，推薦效果更好。因此，系統中的推薦引擎以User-Based 推薦策略為主。但Item-Based 推薦策略并非完全沒用，當用戶歷史數據不足時，可采用Item-Based 推薦策略作為補充，較好的解決了系統冷啟動問題。

4 結語

在基于協同過濾算法的習題系統中，推薦引擎是系統實現個性化推薦功能的核心構成部分。本文介紹了該系統所使用的技術和工作流程，重點闡述了協同過濾算法的基本原理，以及在Mahout 平臺環境下實現推薦引擎的具體步驟，并對系統應用的兩種推薦策略進行對比測試和分析。實驗結果表明使用推薦引擎確實減少了用戶搜索請求的次數，提高了學習的效率。下一步需對系統的推薦算法進行改進,不斷提高推薦的準確率，并引入分布式計算框架，盡可能提高系統響應速度。