算法競賽題目推薦系統(tǒng)的設(shè)計與實現(xiàn)

劉昕宇　徐柔　聶盼紅　鄭金龍

摘要：文章基于本地在線評測系統(tǒng)和第三方在線評測系統(tǒng)的大量的評測數(shù)據(jù)，利用基于用戶的協(xié)同過濾算法，設(shè)計和實現(xiàn)了競賽題目的推薦模塊，并將其引入在開源HOJ在線評測平臺。該模塊通過推薦算法給本地的系統(tǒng)用戶推薦合適的算法競賽題目，提高算法競賽訓(xùn)練的針對性和效率。

關(guān)鍵詞：協(xié)同過濾算法；HOJ；在線評測；算法競賽；推薦系統(tǒng)

中圖分類號：TP391? ? ? 文獻標(biāo)識碼：A

文章編號：1009-3044（2022）34-0054-03

1 引言

隨著“互聯(lián)網(wǎng)+教育”模式的快速發(fā)展，以程序在線評測技術(shù)為基礎(chǔ)而構(gòu)建的在線編程學(xué)習(xí)平臺在計算機教育領(lǐng)域得到了廣泛的應(yīng)用。目前，很多高校和教育機構(gòu)根據(jù)自己的實際需求開發(fā)了各自的在線評測系統(tǒng)，如國內(nèi)外的比較著名的ACM訓(xùn)練平臺HDUOJ、ZOJ、POJ、Codeforces、UVA、TopCoder、AtCoder等，還有牛客、PTA、希冀等在線編程學(xué)習(xí)平臺。其目的主要有兩個：一個是基于在線評測系統(tǒng)開展程序設(shè)計類課程的日常實踐教學(xué)，另一個是促進程序設(shè)計類競賽的組織和訓(xùn)練。同時，為了實現(xiàn)跨平臺的題目共享和競賽組織訓(xùn)練，VOJ（虛擬OJ） 也得到更加廣泛的應(yīng)用，而且部分OJ平臺已經(jīng)將虛擬評測技術(shù)引入系統(tǒng)，從而實現(xiàn)本地和遠程評測功能。

本文在開源的在線評測系統(tǒng)HOJ（Hcode Online Judge）的基礎(chǔ)上進行二次開發(fā)，通過設(shè)計網(wǎng)絡(luò)爬蟲對第三方平臺的系統(tǒng)中本校ACM集訓(xùn)隊學(xué)生的評測記錄進行收集整理，獲取用戶過題情況。在此基礎(chǔ)上利用協(xié)同過濾[1]算法對用戶做題記錄建模分析，構(gòu)建競賽題目推薦模型，由系統(tǒng)輔助用戶選擇合適的題目，從而提高訓(xùn)練效率。

2 系統(tǒng)概述

HOJ（Hcode Online Judge） [2]是基于前后端分離、分布式架構(gòu)的在線評測系統(tǒng)，支持本地和第三方評測，本系統(tǒng)是在HOJ開源評測系統(tǒng)的基礎(chǔ)上進行二次開發(fā)，在前臺模塊新增：推薦題目訓(xùn)練模塊，動態(tài)顯示系統(tǒng)推薦給用戶的競賽問題，用戶可以在本模塊選擇推薦的題目進行訓(xùn)練；新增用戶中心實現(xiàn)用戶基本信息的維護和用戶在第三方平臺的個人賬號管理，便于系統(tǒng)后臺利用用戶在第三方平臺的賬號進行數(shù)據(jù)爬取，收集用戶在第三方平臺上的做題記錄；在系統(tǒng)后臺新增：第三方平臺個人賬號管理、第三方平臺數(shù)據(jù)的統(tǒng)一管理模塊和第三方平臺學(xué)生問題提交記錄，數(shù)據(jù)爬蟲和推薦模型參數(shù)的管理等。根據(jù)不同的第三方平臺，開發(fā)爬蟲程序，從第三方系統(tǒng)獲取指定用戶的做題記錄。同時隨機從第三方平臺上爬取非本校用戶的提交記錄，優(yōu)化和改進推薦程序的效果。圖1為系統(tǒng)模塊圖，黑色粗線框為新增的功能模塊，本文重點闡述推薦功能的實現(xiàn)。

3 推薦模塊設(shè)計

在算法競賽題目推薦方面，由于競賽編程題目描述往往帶有迷惑性，題目中經(jīng)常有背景和引導(dǎo)用戶思考到錯誤方向的關(guān)鍵詞，所以關(guān)鍵詞難以精準(zhǔn)地描述題目，編程問題的相似需要研究思考難度相等或知識點相似，因此對于編程問題的個性化推薦，本文使用協(xié)同過濾推薦算法構(gòu)建推薦模型。協(xié)同過濾分為基于用戶的協(xié)同過濾和基于物品的協(xié)同過濾，對于競賽問題來說，問題之間的相關(guān)性比較復(fù)雜，選擇使用基于用戶的協(xié)同過濾算法較為合適，因為用戶之間的相似性表達了用戶編程水平的相似性，編程水平相當(dāng)?shù)挠脩裟芡ㄟ^的問題基本相同[3]。該算法主要出發(fā)點：做題記錄相近的用戶可能會對同樣的題目感興趣。

本系統(tǒng)的推薦模塊的基本流程如下：

1） 構(gòu)建用戶-題目評分矩陣

2） 使用余弦相似性計算相似度

3） 基于閾值的鄰居用戶

隨著時間的推移，系統(tǒng)中用戶數(shù)量和編程問題數(shù)量都快速增加，將導(dǎo)致用戶-題目評分矩陣維度變大，引發(fā)數(shù)據(jù)稀疏性問題將導(dǎo)致推薦的計算效率和推薦的準(zhǔn)確度下降。同時系統(tǒng)中用戶群體編程水平參差不齊，簡單問題通過的人數(shù)多，難題通過的人數(shù)少。如果使用所有用戶計算對未通過問題的評分，將會導(dǎo)致推薦結(jié)果對水平高的用戶來說偏簡單，對水平低的用戶來說偏難。因此根據(jù)相似度閾值，取出和目標(biāo)用戶更為相近的用戶。計算中用戶之間的水平更加接近，計算出的評分也更為準(zhǔn)確。

4） 預(yù)測推薦

推薦算法的最后一步，根據(jù)用戶和鄰居之間的相似度，計算對未通過問題的評分值，用戶u對問題i的預(yù)測評分用式（3） 表示。最后，將用戶所有未通過題目的評分值從大到小排序，取評分值最高的TOP-N個題目推薦給用戶，完成編程問題個性化推薦過程。

4 推薦模塊的實現(xiàn)

4.1 第三方平臺賬號管理

在程序在線評測系統(tǒng)上，每位學(xué)習(xí)者提交代碼后可以得到代碼的運行結(jié)果，包括答案正確，答案錯誤，運行超時，運行時錯誤等。評測系統(tǒng)中存儲了題目信息、用戶的提交信息和評測結(jié)果，這些數(shù)據(jù)為實現(xiàn)問題推薦提供了基礎(chǔ)[6]。根據(jù)上文提出的基于用戶協(xié)同過濾推薦模型，實現(xiàn)問題推薦功能。

為了自動爬取第三方平臺上，本集訓(xùn)隊學(xué)員的評測記錄，系統(tǒng)維護了學(xué)員的第三方平臺賬號，并且允許學(xué)生自己修改維護。

管理員可以查看到系統(tǒng)中所有錄入的用戶名，同時查看到賬號今日昨日過題數(shù)的數(shù)據(jù)，點擊用戶名可以跳到對應(yīng)第三方網(wǎng)站的用戶主頁，如圖2所示。

4.2 推薦系統(tǒng)的訓(xùn)練數(shù)據(jù)

本系統(tǒng)使用的訓(xùn)練數(shù)據(jù)目前主要來自Codeforces編程競賽平臺，后面將逐步增加其他第三方平臺。Codeforces提供了API：https：//codeforces.com/api/user.status？handle=Fefer_Ivan&from=1&count=10，通過該API接口逐一獲取在該平臺用戶的所有提交記錄。本系統(tǒng)通過爬蟲共獲取7647個題目、1262位有通過題目的用戶，共獲取556546條提交記錄，其中答案正確有249089條，占總記錄的44.75%。并不是所有表項都有意義，通過對數(shù)據(jù)的篩選，取出USERNAME，PROBLEM_ID和STATUS分別表示用戶編號，題目編號和運行結(jié)果，從而構(gòu)建用戶-題目評分矩陣[7]，當(dāng)通過該題（簡稱AC）表示成status為1，將其余結(jié)果合并為解答錯誤（簡稱WA） 表示成status為0。用戶-題目矩陣的大小為1262×7647，矩陣中233140個位置存在有效值，數(shù)據(jù)稀疏率為2.4%，部分?jǐn)?shù)據(jù)如圖3所示，其中行表示用戶，列表示題目。

從數(shù)據(jù)庫中獲取到用戶提交數(shù)據(jù)，根據(jù)前文提到的基于用戶的協(xié)同過濾模型進行計算得出圖4的問題推薦結(jié)果。針對冷啟動問題，可以向新用戶推薦通過人數(shù)多的習(xí)題。

5 推薦結(jié)果分析

推薦系統(tǒng)通過計算平均預(yù)測覆蓋率APC（Average Prediction Coverage） ，衡量系統(tǒng)的優(yōu)劣[8]，如式（4） 。

其中N表示系統(tǒng)中用戶數(shù)量，上式計算了所有用戶的平均準(zhǔn)確率，平均準(zhǔn)確率越高說明系統(tǒng)推薦的質(zhì)量越好。測試中對于數(shù)據(jù)集的數(shù)據(jù)取隨機數(shù)種子1隨機打亂，分為訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集，評估下列各種因素對推薦質(zhì)量的影響。

基于用戶的協(xié)同過濾可以選取不同的用戶相似度閾值，通過閾值可以從用戶中挑選出更加相似的用戶，將這些用戶稱為鄰居，使用鄰居用戶計算題目的推薦度，分析不同相似度閾值對推薦質(zhì)量的影響，結(jié)果如圖5所示。

因為只有少量用戶之間的相似度大于0.4，因此考慮閾值小于等于0.4的情況。在一定范圍內(nèi)相似度閾值增加，推薦質(zhì)量變差，呈現(xiàn)負(fù)相關(guān)，因為留下的用戶和被推薦者之間的關(guān)系不夠緊密。而閾值取0存在大多數(shù)用戶都有通過的簡單問題，因此準(zhǔn)確率偏高。當(dāng)閾值達到一定范圍后，用戶之間的聯(lián)系更為緊密，推薦質(zhì)量明顯上升，推薦的內(nèi)容更符合用戶當(dāng)前水平。

6 總結(jié)

本文是在開源在線評測系統(tǒng)HOJ的基礎(chǔ)進行二次開發(fā)，增加了基于協(xié)同過濾的競賽題目的推薦功能相關(guān)模塊，包括數(shù)據(jù)爬取，推薦算法等，提高競賽隊員的訓(xùn)練效率，目前推薦算法采用的數(shù)據(jù)來自本地系統(tǒng)和Codeforces系統(tǒng)的評測記錄，后面將逐步增加其他三方平臺的數(shù)據(jù)，并對算法進行逐步的優(yōu)化，提高推薦的準(zhǔn)確性。

參考文獻：

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

[2] Hcode Online Judge（HOJ） [2021-03-20].https：//gitee.com/himitzh0730/hoj.git.

[3] 閆利陽.基于Mahout的個性化圖書推薦系統(tǒng)設(shè)計與實現(xiàn)[D].蘭州：西北民族大學(xué)，2019.

[4] 王國霞，劉賀平.個性化推薦系統(tǒng)綜述[J].計算機工程與應(yīng)用，2012，48（7）：66-76.

[5] 馬宏偉，張光衛(wèi)，李鵬.協(xié)同過濾推薦算法綜述[J].小型微型計算機系統(tǒng)，2009，30（7）：1282-1288.

[6] 李明杰.面向Online Judge的學(xué)習(xí)者編程能力分析與習(xí)題推薦算法研究[D].保定：河北大學(xué)，2021.

[7] 祝云篪，趙作翰，童澄達，等.基于在線評測系統(tǒng)的編程實戰(zhàn)數(shù)據(jù)挖掘[J].電氣電子教學(xué)學(xué)報，2020，42（1）：94-98，141.

[8] 柏茂林.基于協(xié)同過濾的數(shù)學(xué)習(xí)題個性化推薦系統(tǒng)的設(shè)計與實現(xiàn)[D].錦州：渤海大學(xué)，2018.

【通聯(lián)編輯：謝媛媛】