曹景振 賈新磊 李松丹

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

關(guān)鍵詞：協(xié)同過濾；個(gè)性化推薦；ACM在線評(píng)測(cè)；時(shí)間權(quán)重；難度權(quán)重

隨著ACM-ICPC和CCPC等大學(xué)生程序設(shè)計(jì)競(jìng)賽的發(fā)展，越來越多的高校搭建了ACM在線評(píng)測(cè)（Online Judge，OJ）平臺(tái)。在線評(píng)測(cè)平臺(tái)題目較多，剛?cè)腴T的用戶往往存在選題盲目的問題，針對(duì)此問題，通過利用所有用戶的歷史做題記錄來實(shí)現(xiàn)智能題目推薦系統(tǒng)，來幫助新手選擇題目，提高學(xué)生編寫程序、分析和解決問題的能力。

本文主要研究基于物品的協(xié)同過濾算法在ACM在線評(píng)測(cè)平臺(tái)的題目推薦系統(tǒng)中的改進(jìn)及應(yīng)用，目的是在現(xiàn)推薦算法研究成果的基礎(chǔ)上，根據(jù)在線評(píng)測(cè)平臺(tái)特性改進(jìn)推薦系統(tǒng)算法，進(jìn)一步提高推薦質(zhì)量，幫助用戶選到更適合的題目。

1 推薦系統(tǒng)概述

推薦系統(tǒng)主要是根據(jù)用戶抽象的興趣特點(diǎn)和具體的歷史購買行為，向用戶推薦其可能感興趣的信息或者物品?；ヂ?lián)網(wǎng)迅速發(fā)展也帶來了網(wǎng)上信息量的大幅度增長，出現(xiàn)了信息超載問題，為用戶產(chǎn)生了困擾，而內(nèi)容提供商把優(yōu)質(zhì)的內(nèi)容正確推送給感興趣的用戶的操作難度不斷加大。而個(gè)性化推薦系統(tǒng)恰恰可以解決這個(gè)問題，對(duì)海量數(shù)據(jù)進(jìn)行挖掘，研究用戶的興趣偏好，并對(duì)其用戶興趣進(jìn)行建模，由系統(tǒng)發(fā)現(xiàn)用戶的興趣點(diǎn)，從而引導(dǎo)用戶發(fā)現(xiàn)自己的信息需求。

1.1 主要算法

推薦算法毫無疑問是推薦系統(tǒng)中最重要、最核心的組成部分，對(duì)推薦系統(tǒng)具體表現(xiàn)的優(yōu)劣起著決定性的作用。目前主要的推薦算法包括：協(xié)同過濾推薦，基于內(nèi)容推薦，基于知識(shí)推薦，基于關(guān)聯(lián)規(guī)則推薦和多種推薦算法組合推薦[1]。每種推薦算法都有自己的優(yōu)缺點(diǎn)，也有自己具體的適用環(huán)境。

1.2 應(yīng)用現(xiàn)狀

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

2 基于物品的協(xié)同過濾推薦算法

協(xié)同過濾推薦技術(shù)被認(rèn)為是推薦系統(tǒng)算法中應(yīng)用最為成功的技術(shù)之一。它通常采用最近鄰（K-Nearest-Neighbor，KNN）算法，利用用戶的歷史記錄來計(jì)算用戶之間的距離，然后利用目標(biāo)用戶的最近鄰用戶對(duì)物品評(píng)價(jià)來預(yù)測(cè)目標(biāo)用戶對(duì)其他未評(píng)價(jià)物品的感興趣程度，系統(tǒng)從而根據(jù)這一感興趣程度來對(duì)目標(biāo)用戶進(jìn)行推薦。協(xié)同過濾的優(yōu)點(diǎn)是對(duì)推薦物品本身沒有特殊的要求，能處理一些數(shù)據(jù)結(jié)構(gòu)不規(guī)則或不完整，不方便用二維邏輯來表現(xiàn)的復(fù)雜對(duì)象，如電影、新聞、題目等，因此適合ACM在線判題平臺(tái)的題目推薦系統(tǒng)使用。

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

2.1 建立數(shù)據(jù)模型

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

模型建立完成后，對(duì)題目數(shù)據(jù)矩陣通過矩陣相乘的方式進(jìn)行時(shí)間權(quán)重和難度權(quán)重的賦權(quán)。

2.1.1 時(shí)間權(quán)重

現(xiàn)有的基于物品的協(xié)同過濾算法的題目推薦系統(tǒng)在推薦內(nèi)容計(jì)算過程中，往往將用戶做題歷史數(shù)據(jù)等同對(duì)待，這樣不能挖掘出用戶當(dāng)下的做題愛好。因?yàn)殡S著時(shí)間的推移，用戶的做題興趣會(huì)不斷變化，做題水平會(huì)不斷提高，所以一個(gè)用戶感興趣的題目最可能和他近期做過的題目相似。為此引入時(shí)間權(quán)重，增加近期的做題歷史數(shù)據(jù)在推薦題目生成過程中的重要性，來提高推薦系統(tǒng)的推薦準(zhǔn)確率。

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

2.1.2 難度權(quán)重

現(xiàn)實(shí)中基于物品的協(xié)同過濾推薦算法應(yīng)用往往會(huì)增加對(duì)流行物品的懲罰度，因?yàn)榱餍形锲吠腿我馕锲返南嗨贫榷己芨摺Ｆ溥壿嬙贠J上也是同樣適用的，即OJ題目中的簡(jiǎn)單題難度較低，很容易解答，一般是僅供練習(xí)編程語言語法的題目，而且通常做過這些題目的用戶比較多，這種題目的歷史提交數(shù)據(jù)會(huì)對(duì)推薦系統(tǒng)的推薦結(jié)果造成干擾。因此對(duì)簡(jiǎn)單題進(jìn)行降權(quán)，來使推薦題目質(zhì)量更高，使用戶做推薦的題目時(shí)，通過題目難度的適當(dāng)增加或者題目知識(shí)點(diǎn)的有效擴(kuò)寬，來提升自己的編程能力。

可以通過計(jì)算AC率，即某道題目所有提交系統(tǒng)判定正確的次數(shù)占總提交次數(shù)的百分比，來粗略為該題目難度賦值，也可以由經(jīng)驗(yàn)豐富的用戶手動(dòng)對(duì)每道題自定義難度數(shù)值，這樣推薦效果會(huì)更好。

2.2 相似度計(jì)算

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

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

公式中的分子為兩個(gè)向量的內(nèi)積，即兩個(gè)向量相同位置的數(shù)字相乘。

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

2.3 尋找k最近鄰

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

2.4 獲得推薦矩陣

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

3 推薦算法優(yōu)化效果分析

推薦系統(tǒng)算法的效果檢驗(yàn)一般采用將現(xiàn)有的所有數(shù)據(jù)按比例分為訓(xùn)練集和比較集P，然后將訓(xùn)練集的數(shù)據(jù)經(jīng)過設(shè)計(jì)好的推薦系統(tǒng)處理，得出結(jié)果集S，并將結(jié)果集與比較集進(jìn)行比較，通過計(jì)算APC平均預(yù)測(cè)覆蓋率來比較優(yōu)化前推薦算法與優(yōu)化后推薦算法的推薦效果[3]。APC公式如下：

3.1 數(shù)據(jù)集

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

3.2 測(cè)試對(duì)比

將OJ用戶的解題數(shù)據(jù)分為訓(xùn)練集和比較集，分別用優(yōu)化前和優(yōu)化后的協(xié)同過濾算法產(chǎn)生推薦結(jié)果，推薦結(jié)果和比較集對(duì)比得到平均預(yù)測(cè)覆蓋率APC，如圖1所示。測(cè)試中，訓(xùn)練集和比較集的比例為8：2，算法選取解題個(gè)數(shù)大于10的用戶解題數(shù)據(jù)，推薦給用戶題目個(gè)數(shù)為5道。

通過數(shù)據(jù)比較，優(yōu)化后的算法的推薦質(zhì)量較原有算法有顯著提高。

4 結(jié)語

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

并且推薦系統(tǒng)的個(gè)性化推薦方面還可以進(jìn)一步改進(jìn)，比如添加推薦風(fēng)格，用戶可以選擇（對(duì)算法部分）單一鉆研或廣泛涉獵等不同風(fēng)格，推薦系統(tǒng)也會(huì)因此改變對(duì)該用戶的推薦題目的整體傾向?；蛘哌M(jìn)行多種推薦算法組合推薦使用，進(jìn)一步提高推薦準(zhǔn)確率。

[參考文獻(xiàn)]

[1]陶彩霞，袁海.靈活適應(yīng)不同業(yè)務(wù)的個(gè)性化推薦系統(tǒng)研究[J]電信科學(xué)，2014 （8）：131-135.

[2]楊永權(quán).基于協(xié)同過濾技術(shù)的個(gè)性化圖書推薦系統(tǒng)研究[J]河南圖書館學(xué)刊，2014 （6）：119-122.

[3]孫權(quán)，賀細(xì)平.協(xié)同過濾算法在ACM在線評(píng)測(cè)推薦系統(tǒng)中的應(yīng)用研究[J]電腦與信息技術(shù)，2015（6）：11-14.