基于協(xié)同過濾算法的習(xí)題系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

封俊

（太原學(xué)院計(jì)算機(jī)科學(xué)與工程系 山西省太原市 030032）

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

1 系統(tǒng)使用的相關(guān)技術(shù)

1.1 協(xié)同過濾算法

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

1.2 相似度

相似度是構(gòu)成推薦優(yōu)先級(jí)的依據(jù)。相似度的計(jì)算基于向量間距離，距離越短意味著相似度越高。選擇合適的相似度計(jì)算方法，可以有效提高推薦的準(zhǔn)確率。相似度計(jì)算方法較多，并且每種方法都有各自適用的領(lǐng)域，經(jīng)過綜合比較本文使用了以下兩種相似度計(jì)算方法：皮爾遜相關(guān)系數(shù)和余弦距離（余弦相似度）。

1.3 Mahout軟件庫

Mahout 是由Apache 軟件基金會(huì)推出的一個(gè)開源機(jī)器學(xué)習(xí)軟件庫。它主要關(guān)注機(jī)器學(xué)習(xí)的三個(gè)領(lǐng)域：協(xié)同過濾、分類和聚類，基于Mahout 可以實(shí)現(xiàn)快速構(gòu)建機(jī)器學(xué)習(xí)平臺(tái)的任務(wù)[2]。Mahout 具備極為靈活的擴(kuò)展能力，單機(jī)模式既可以方便的處理大量數(shù)據(jù)，當(dāng)所處理的數(shù)據(jù)規(guī)模已經(jīng)超過單機(jī)處理能力時(shí)，可以構(gòu)建基于Hadoop的分布式計(jì)算平臺(tái)[3]。由于實(shí)驗(yàn)數(shù)據(jù)規(guī)模尚未超越單臺(tái)服務(wù)器的處理能力，所以本文主要應(yīng)用單機(jī)模式來實(shí)現(xiàn)推薦引擎。

2 基于協(xié)同過濾算法的習(xí)題系統(tǒng)的構(gòu)建

2.1 系統(tǒng)主要功能

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

系統(tǒng)結(jié)合兩種引擎技術(shù)的優(yōu)點(diǎn)，為用戶提供高效且個(gè)性化的題目獲取手段，其運(yùn)行流程如圖1 所示。

2.2 系統(tǒng)功能模塊

本系統(tǒng)按照不同功能劃分為以下幾個(gè)模塊：用戶模塊，數(shù)據(jù)存儲(chǔ)模塊，搜索引擎，以及推薦引擎。

（1）用戶模塊。此模塊實(shí)現(xiàn)用戶與系統(tǒng)交互相關(guān)的功能，包括用戶登錄界面、題目練習(xí)界面、用戶反饋界面等基本功能。此外，當(dāng)用戶在線練習(xí)時(shí)，對(duì)其學(xué)習(xí)軌跡進(jìn)行全程記錄,獲得用戶對(duì)所做題目的評(píng)分，完成推薦引擎所需數(shù)據(jù)的采集過程。

（2）數(shù)據(jù)存儲(chǔ)模塊。此模塊基于關(guān)系型數(shù)據(jù)庫構(gòu)建，是系統(tǒng)基礎(chǔ)數(shù)據(jù)來源。主要包含注冊用戶數(shù)據(jù)表t_user、習(xí)題信息表t_exercises、用戶-題目關(guān)系表t_usr_exs，以及其他相應(yīng)的輔助功能表。

（3）搜索引擎。用于接收用戶輸入的關(guān)鍵字，由此構(gòu)建一個(gè)搜索請(qǐng)求，并根據(jù)搜索請(qǐng)求開始對(duì)題庫進(jìn)行全文搜索。由于搜索請(qǐng)求不能唯一地標(biāo)識(shí)題庫中的單個(gè)題目(項(xiàng)目)，相反，可能會(huì)有多個(gè)題目與搜索請(qǐng)求相匹配，因此，搜索引擎根據(jù)TF-IDF 算法對(duì)搜索結(jié)果按rating 值進(jìn)行排序并返回給用戶。

（4）推薦引擎。個(gè)性化推薦是本系統(tǒng)的重要功能，當(dāng)用戶從搜索引擎返回的結(jié)果中，選出所需題目，并完成此題目的練習(xí)之后，推薦引擎會(huì)自動(dòng)向用戶推薦相關(guān)的題目。整個(gè)推薦過程無需用戶主動(dòng)參與，只有當(dāng)用戶對(duì)推薦結(jié)果不滿意時(shí)，才需要用戶重新輸入關(guān)鍵字進(jìn)行搜索。

2.3 系統(tǒng)實(shí)現(xiàn)

由于數(shù)據(jù)存儲(chǔ)技術(shù)和搜索引擎技術(shù)已經(jīng)比較成熟，故不再詳細(xì)敘述，本文重點(diǎn)闡述推薦引擎的實(shí)現(xiàn)過程。此推薦引擎構(gòu)建于Mahout 機(jī)器學(xué)習(xí)平臺(tái)之上，由兩個(gè)模塊構(gòu)成，實(shí)現(xiàn)了兩種推薦策略。第一種，User-Based 推薦策略，通過分析系統(tǒng)中所有用戶的歷史行為[5]和用戶對(duì)已完成題目的評(píng)分，發(fā)現(xiàn)與當(dāng)前用戶興趣相似的用戶群，然后基于這些用戶的歷史偏好，為當(dāng)前用戶進(jìn)行相關(guān)推薦?；谟脩舻耐扑]引擎模塊采用User-Based 推薦策略，其結(jié)構(gòu)如圖2 所示。

第二種，Item-Based 推薦策略，它以題目（而不是用戶）之間的相似度為基礎(chǔ)，實(shí)現(xiàn)個(gè)性化推薦?；陧?xiàng)目的推薦引擎模塊采用Item-Based 推薦策略，其結(jié)構(gòu)與基于用戶的推薦引擎模塊比較類似。

2.4 基于用戶的推薦引擎模塊具體實(shí)現(xiàn)步驟

圖1：系統(tǒng)流程圖

圖2：基于用戶的推薦引擎模塊結(jié)構(gòu)圖

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

（2）計(jì)算用戶之間的相似度。用戶之間的相似度根據(jù)皮爾遜相關(guān)系數(shù)計(jì)算得來。皮爾遜相關(guān)系數(shù)常用于計(jì)算兩個(gè)向量間的相關(guān)性，計(jì)算公式如下：

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

圖3：題目推薦列表

系統(tǒng)中用戶之間的相似度由UserSimilarity 類表示，而PearsonCorrelationSimilarity 類的內(nèi)部實(shí)現(xiàn)了皮爾遜相關(guān)系數(shù)的計(jì)算，通過以下代碼可以計(jì)算出用戶之間的相似度。

UserSimilarity similarity = new PearsonCorrelationSimilarity(data Model);

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

固定大小鄰域計(jì)算法將鄰域集合的大小設(shè)為一個(gè)固定值，其實(shí)現(xiàn)過程較為方便快捷，但這個(gè)值過大可能會(huì)導(dǎo)致很多無關(guān)用戶進(jìn)入集合；相反，這個(gè)值過小又可能導(dǎo)致很多相關(guān)用戶被排除出集合。所以需要反復(fù)測試才能為某個(gè)數(shù)據(jù)集找到最佳值，另外隨著數(shù)據(jù)集規(guī)模的擴(kuò)大，鄰域集合的大小也需重新測試。

基于閾值的鄰域計(jì)算法通過設(shè)置相似度的閾值，將所有相似度超過此閾值的用戶選出，生成最近鄰用戶的集合。本系統(tǒng)采用了基于閾值的鄰域計(jì)算法，可以避免數(shù)據(jù)集規(guī)模持續(xù)擴(kuò)大，而導(dǎo)致的算法參數(shù)反復(fù)修正的問題。經(jīng)過驗(yàn)證0.7 可以作為一個(gè)相似度閾值的合理定義。

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

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

（4）創(chuàng)建推薦器對(duì)象，生成題目推薦列表。經(jīng)過以上三個(gè)步驟就完成了推薦數(shù)據(jù)的準(zhǔn)備，現(xiàn)在可以創(chuàng)建推薦器對(duì)象了。

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

推薦器對(duì)象計(jì)算出相關(guān)項(xiàng)目的推薦值，根據(jù)推薦值的高低，生成題目推薦列表。

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

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

（5）向用戶呈現(xiàn)推薦結(jié)果。由于推薦項(xiàng)中并沒有包含題目內(nèi)容，為了向用戶呈現(xiàn)推薦結(jié)果，還必須根據(jù)“題目id”從數(shù)據(jù)庫習(xí)題信息表t_exercises 中查詢出完整的題目內(nèi)容，生成學(xué)習(xí)界面，并返回給用戶。

2.5 基于項(xiàng)目的推薦引擎模塊具體實(shí)現(xiàn)步驟

基于項(xiàng)目的推薦引擎模塊與基于用戶的推薦引擎模塊的實(shí)現(xiàn)步驟基本相同，這里只討論兩者的不同點(diǎn)。

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

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

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

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

3.1 硬件環(huán)境

系統(tǒng)運(yùn)行于PC 機(jī)上，具體配置為：4 核CPU，主頻3.2GHz，內(nèi)存8G。

3.2 實(shí)驗(yàn)數(shù)據(jù)

以某高校習(xí)題系統(tǒng)為例，選取了包含4736 名用戶和60000 道習(xí)題的數(shù)據(jù)庫作為實(shí)驗(yàn)數(shù)據(jù)集，15 名學(xué)生參與系統(tǒng)測試。

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

經(jīng)過多輪實(shí)驗(yàn)，取實(shí)驗(yàn)數(shù)據(jù)的平均值，可以得出以下結(jié)果。響應(yīng)速度方面，采用User-Based 推薦策略，系統(tǒng)平均響應(yīng)時(shí)間為1741ms；采用Item-Based 推薦策略，系統(tǒng)平均響應(yīng)時(shí)間為2439ms。可以看出采用User-Based 推薦策略，系統(tǒng)響應(yīng)速度更快。另一方面，參與實(shí)驗(yàn)的用戶普遍反映User-Based 推薦策略的準(zhǔn)確率更高，推薦效果更好。因此，系統(tǒng)中的推薦引擎以User-Based 推薦策略為主。但I(xiàn)tem-Based 推薦策略并非完全沒用，當(dāng)用戶歷史數(shù)據(jù)不足時(shí)，可采用Item-Based 推薦策略作為補(bǔ)充，較好的解決了系統(tǒng)冷啟動(dòng)問題。

4 結(jié)語

在基于協(xié)同過濾算法的習(xí)題系統(tǒng)中，推薦引擎是系統(tǒng)實(shí)現(xiàn)個(gè)性化推薦功能的核心構(gòu)成部分。本文介紹了該系統(tǒng)所使用的技術(shù)和工作流程，重點(diǎn)闡述了協(xié)同過濾算法的基本原理，以及在Mahout 平臺(tái)環(huán)境下實(shí)現(xiàn)推薦引擎的具體步驟，并對(duì)系統(tǒng)應(yīng)用的兩種推薦策略進(jìn)行對(duì)比測試和分析。實(shí)驗(yàn)結(jié)果表明使用推薦引擎確實(shí)減少了用戶搜索請(qǐng)求的次數(shù)，提高了學(xué)習(xí)的效率。下一步需對(duì)系統(tǒng)的推薦算法進(jìn)行改進(jìn),不斷提高推薦的準(zhǔn)確率，并引入分布式計(jì)算框架，盡可能提高系統(tǒng)響應(yīng)速度。