基于物品的協同過濾算法在ACM在線評測推薦系統中的改進及應用

曹景振 賈新磊 李松丹

摘 要：針對ACM在線評測平臺中練習題目數量較多，新用戶選題盲目的問題，文章主要研究了基于物品（item-based）的協同過濾算法，根據在線評測推薦系統的特性采用了余弦相似性來計算題目之間的相似程度，并且在此基礎上加入時間權重和難度權重。實驗結果表明，改進后的算法比原有推薦算法的推薦質量和準確度有顯著提高。最后將改進后的推薦算法部署到在線評測平臺上，幫助用戶選到合適的題目練習，提高用戶編寫程序解決問題的能力。

關鍵詞：協同過濾；個性化推薦；ACM在線評測；時間權重；難度權重

隨著ACM-ICPC和CCPC等大學生程序設計競賽的發展，越來越多的高校搭建了ACM在線評測（Online Judge，OJ）平臺。在線評測平臺題目較多，剛入門的用戶往往存在選題盲目的問題，針對此問題，通過利用所有用戶的歷史做題記錄來實現智能題目推薦系統，來幫助新手選擇題目，提高學生編寫程序、分析和解決問題的能力。

本文主要研究基于物品的協同過濾算法在ACM在線評測平臺的題目推薦系統中的改進及應用，目的是在現推薦算法研究成果的基礎上，根據在線評測平臺特性改進推薦系統算法，進一步提高推薦質量，幫助用戶選到更適合的題目。

1 推薦系統概述

推薦系統主要是根據用戶抽象的興趣特點和具體的歷史購買行為，向用戶推薦其可能感興趣的信息或者物品。互聯網迅速發展也帶來了網上信息量的大幅度增長，出現了信息超載問題，為用戶產生了困擾，而內容提供商把優質的內容正確推送給感興趣的用戶的操作難度不斷加大。而個性化推薦系統恰恰可以解決這個問題，對海量數據進行挖掘，研究用戶的興趣偏好，并對其用戶興趣進行建模，由系統發現用戶的興趣點，從而引導用戶發現自己的信息需求。

1.1 主要算法

推薦算法毫無疑問是推薦系統中最重要、最核心的組成部分，對推薦系統具體表現的優劣起著決定性的作用。目前主要的推薦算法包括：協同過濾推薦，基于內容推薦，基于知識推薦，基于關聯規則推薦和多種推薦算法組合推薦[1]。每種推薦算法都有自己的優缺點，也有自己具體的適用環境。

1.2 應用現狀

推薦系統在互聯網上有非常好的應用，如電子商務、新聞資訊等方面。電子商務網站，如亞馬遜、淘寶等，利用個性化推薦系統，像實體店中的導購一樣為消費者提供推薦服務，幫助客戶完成購買行為。新聞資訊類如廣告語為“你關心的，才是頭條！”的今日頭條，就通過其成熟的推薦系統為用戶定制個性化的新聞資訊和短視頻等，其應用一經推出，便迅速獲得海量的用戶，用戶粘性在所有移動應用中名列前茅。

2 基于物品的協同過濾推薦算法

協同過濾推薦技術被認為是推薦系統算法中應用最為成功的技術之一。它通常采用最近鄰（K-Nearest-Neighbor，KNN）算法，利用用戶的歷史記錄來計算用戶之間的距離，然后利用目標用戶的最近鄰用戶對物品評價來預測目標用戶對其他未評價物品的感興趣程度，系統從而根據這一感興趣程度來對目標用戶進行推薦。協同過濾的優點是對推薦物品本身沒有特殊的要求，能處理一些數據結構不規則或不完整，不方便用二維邏輯來表現的復雜對象，如電影、新聞、題目等，因此適合ACM在線判題平臺的題目推薦系統使用。

基于物品的協同過濾的原理是通過分析用戶的歷史行為記錄來計算物品間的相似度，而不是利用物品的內容屬性，然后再根據物品的相似度和用戶的歷史行為為用戶生成推薦內容。

2.1 建立數據模型

分別從OJ平臺的服務器數據庫里讀取用戶字典，題目數據，難度數據及每個用戶最后AC的25道題目的數據，生成矩陣或者列表，作為協同過濾算法模型的輸入數據。用戶字典列表包括用戶編號與用戶ID。題目數據矩陣包括所有正確提交的提交用戶和題號。

模型建立完成后，對題目數據矩陣通過矩陣相乘的方式進行時間權重和難度權重的賦權。

2.1.1 時間權重

現有的基于物品的協同過濾算法的題目推薦系統在推薦內容計算過程中，往往將用戶做題歷史數據等同對待，這樣不能挖掘出用戶當下的做題愛好。因為隨著時間的推移，用戶的做題興趣會不斷變化，做題水平會不斷提高，所以一個用戶感興趣的題目最可能和他近期做過的題目相似。為此引入時間權重，增加近期的做題歷史數據在推薦題目生成過程中的重要性，來提高推薦系統的推薦準確率。

在實際運算中，取每個用戶最后25次正確的提交，計算最終推薦度時，讓每次提交有不同的權重，即倒數第n次正確提交的題目所占權重為l/log（n+l），這樣能保證越靠后的提交權重越大。

2.1.2 難度權重

現實中基于物品的協同過濾推薦算法應用往往會增加對流行物品的懲罰度，因為流行物品往往和任意物品的相似度都很高。其邏輯在OJ上也是同樣適用的，即OJ題目中的簡單題難度較低，很容易解答，一般是僅供練習編程語言語法的題目，而且通常做過這些題目的用戶比較多，這種題目的歷史提交數據會對推薦系統的推薦結果造成干擾。因此對簡單題進行降權，來使推薦題目質量更高，使用戶做推薦的題目時，通過題目難度的適當增加或者題目知識點的有效擴寬，來提升自己的編程能力。

可以通過計算AC率，即某道題目所有提交系統判定正確的次數占總提交次數的百分比，來粗略為該題目難度賦值，也可以由經驗豐富的用戶手動對每道題自定義難度數值，這樣推薦效果會更好。

2.2 相似度計算

基于物品的協同過濾算法首先要計算題目之間的相似度，目前常用的幾種計算相似度（Simlarity， sim）的方法如下。

（1）基于余弦的相似度計算，通過計算兩個向量之間的夾角余弦值來表示物品之間的相似程度，公式如下：

公式中的分子為兩個向量的內積，即兩個向量相同位置的數字相乘。

（2）調整的余弦相似度計算，由于基于余弦的相似度計算沒有考慮不同用戶的打分情況，可能有的用戶偏向于給高分，而有的用戶偏向于給低分，該方法通過減去用戶打分的平均值消除不同用戶打分習慣的影響，公式如下：

2.3 尋找k最近鄰

上面已經計算出題目之間的相似度，為了減少計算時間，只保留選擇每個題目最近鄰的k 個題目。在保留相似度矩陣中每行前k+l個元素（k個最近鄰居加上題目本身），其他元素全部置0。并且為了減少后面計算量及去除一些相似度較低的元素，在這將前一步計算出的稠密矩陣轉換為稀疏矩陣。

2.4 獲得推薦矩陣

將相似度矩陣乘以用戶題目完成情況矩陣，得到一個格式為題目數行，用戶數列的矩陣，題目完成情況的值只存在0和1兩種情況，所以第α行第b列的元素表示的就是第b個用戶所做的所有題目與第α道題目的相似度之和。然后求任意題目與其它所有題目的相似度之和，將兩個矩陣相除，就得到了推薦矩陣。然后將用戶已經做過的題目通過在矩陣中置0值的方法去掉后，將對矩陣每列的值進行升序排序，越靠前的題目推薦程度越大，最后選出前k個題目，將其題號輸出給用戶。

3 推薦算法優化效果分析

推薦系統算法的效果檢驗一般采用將現有的所有數據按比例分為訓練集和比較集P，然后將訓練集的數據經過設計好的推薦系統處理，得出結果集S，并將結果集與比較集進行比較，通過計算APC平均預測覆蓋率來比較優化前推薦算法與優化后推薦算法的推薦效果[3]。APC公式如下：

3.1 數據集

測試采用了信陽師范學院OJ從2017年5月至今所有用戶的正確解題數據作為實驗的數據集，截至2017年11月19日，數據庫中約有1 500道題，450名用戶，總共34 100條解題記錄，其中正確的解題記錄有22 815條，占總解題記錄的67.5%。

3.2 測試對比

將OJ用戶的解題數據分為訓練集和比較集，分別用優化前和優化后的協同過濾算法產生推薦結果，推薦結果和比較集對比得到平均預測覆蓋率APC，如圖1所示。測試中，訓練集和比較集的比例為8：2，算法選取解題個數大于10的用戶解題數據，推薦給用戶題目個數為5道。

通過數據比較，優化后的算法的推薦質量較原有算法有顯著提高。

4 結語

本文通過在原有推薦系統的算法上，結合ACM在線評測系統特性，添加了時間權重和難度權重，提高了推薦質量，為每一個用戶提供更好的個性化題目推薦。時間權重考慮到用戶的近期興趣變化，使推薦結果更接近實際，最終提高了推薦準確率；難度權重使推薦結果更能幫助用戶選到有水平的好題目，進行練習從而提高編程水平。

并且推薦系統的個性化推薦方面還可以進一步改進，比如添加推薦風格，用戶可以選擇（對算法部分）單一鉆研或廣泛涉獵等不同風格，推薦系統也會因此改變對該用戶的推薦題目的整體傾向。或者進行多種推薦算法組合推薦使用，進一步提高推薦準確率。

[參考文獻]

[1]陶彩霞，袁海.靈活適應不同業務的個性化推薦系統研究[J]電信科學，2014 （8）：131-135.

[2]楊永權.基于協同過濾技術的個性化圖書推薦系統研究[J]河南圖書館學刊，2014 （6）：119-122.

[3]孫權，賀細平.協同過濾算法在ACM在線評測推薦系統中的應用研究[J]電腦與信息技術，2015（6）：11-14.