劉昕宇　徐柔　聶盼紅　鄭金龍

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

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

中圖分類號：TP391? ? ? 文獻標識碼：A

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

1 引言

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

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

2 系統(tǒng)概述

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

3 推薦模塊設計

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

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

1） 構建用戶-題目評分矩陣

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

3） 基于閾值的鄰居用戶

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

4） 預測推薦

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

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

4.1 第三方平臺賬號管理

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

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

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

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

本系統(tǒng)使用的訓練數(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分別表示用戶編號，題目編號和運行結果，從而構建用戶-題目評分矩陣[7]，當通過該題（簡稱AC）表示成status為1，將其余結果合并為解答錯誤（簡稱WA） 表示成status為0。用戶-題目矩陣的大小為1262×7647，矩陣中233140個位置存在有效值，數(shù)據(jù)稀疏率為2.4%，部分數(shù)據(jù)如圖3所示，其中行表示用戶，列表示題目。

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

5 推薦結果分析

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

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

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

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

6 總結

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

參考文獻：

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

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

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

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

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

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

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

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

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