朱國進 凌曉晨

摘 要： Online Judge系統(tǒng)（簡稱OJ），是一個編程練習的在線判題系統(tǒng)。練習者可以根據(jù)知識點和難度，選擇相應的編程題目，提交自己編寫的程序代碼，得到OJ的評測反饋。為了在OJ上搜尋到合適自己的題目，練習者常常需要花費較長的時間瀏覽題庫。針對這一問題，本文提出一種基于關聯(lián)規(guī)則挖掘的解決方案，其主要流程為：首先，收集OJ中所有練習者已做題目的數(shù)據(jù)；而后，使用關聯(lián)規(guī)則挖掘的方法，挖掘出題目之間的關聯(lián)關系；最后，依據(jù)目標練習者的做題歷史，個性化地為其推薦合適的題目。實驗結果表明，本推薦方案可為編程練習者做出有效推薦。相比原先需要從上千道題目中瀏覽尋找，練習者只需從推薦的3道題目中進行選擇即可，極大程度地節(jié)約了用戶的時間和試錯成本。

關鍵詞： 關聯(lián)規(guī)則挖掘；機器學習；推薦系統(tǒng)；數(shù)據(jù)挖掘

Abstract：Online judge system（OJ） is an online evaluation system. Users can choose programming problems according to knowledge point and difficulty submit solution code and get feedback information. In order to find appropriate problems users often have to spend plenty of time in browsing problem database. To facilitate this process this article uses the recommendation method based on the association rule mining to analyze the history data of users on the OJ and make personalized recommendation for them. The main process of this recommendation system is to collect the history data of all the users except the target users. Then the association rules are applied to get the relationship between the problems users have done. Finally the system makes recommendation for target user based on rules and history data of target users. The simulation results show that this recommendation system can make effective recommendation for users. Compared to random recommendation the usability of the recommendation has improved substantially. Rather than seeking appropriate problems from the massive problem database users now only need to pick one from 3 problems provided by the recommendation system which extremely saves time and trial cost.

Key words： association rule mining；machine learning；recommendation system；data mining

引言

隨著計算機技術和互聯(lián)網(wǎng)的不斷發(fā)展和普及，越來越多的人傾向于通過在線平臺學習和掌握計算機知識。而OJ，由于其題庫中涉獵知識面范圍廣泛、試題數(shù)目充足、評判可靠、且論壇等交流資源更加豐富，自問世以來，即為廣大專業(yè)與非專業(yè)編程愛好者和初學者創(chuàng)建提供了理想的聚集環(huán)境與空間。

但在實際使用中，編程的初學者面對海量的題庫和繁多的知識點，難以在第一時間搜尋到滿足自身需求意愿的題目，往往經(jīng)過幾番嘗試之后，依舊沒有找到適合自己能力水平和興趣偏好的題目。這勢必會影響到該部分用戶對于OJ網(wǎng)站的使用。若能利用技術手段對練習者的做題歷史數(shù)據(jù)進行數(shù)據(jù)挖掘，從而高效地為OJ用戶推薦合適的題目即已成為一個亟待探索與研究的新方向。

基于以上需求，本文依據(jù)數(shù)據(jù)挖掘和機器學習的理論，提出一種針對OJ平臺設計的推薦方案：使用關聯(lián)規(guī)則挖掘的方法，對OJ用戶做題歷史的大數(shù)據(jù)進行分析，從中推導得到題目之間的關聯(lián)規(guī)則；從而能夠運用這些關聯(lián)規(guī)則，根據(jù)目標用戶自身的做題歷史，為其定制合適的題目推薦。

關聯(lián)規(guī)則挖掘技術在數(shù)據(jù)挖掘領域有著至關重要的地位[1]。其概念最早出現(xiàn)于1993年，由Agrawal等人[2]提出，用于發(fā)現(xiàn)超市中消費者所購買商品間的隱含聯(lián)系，也就是“購物籃分析”問題，而后這一技術即快速應用于其它領域。

關聯(lián)規(guī)則挖掘的目的是充分利用積累的數(shù)據(jù)，找尋這些數(shù)據(jù)中不同事物間的潛在聯(lián)系，從而得到表征現(xiàn)實具體聯(lián)系的關聯(lián)規(guī)則。

利用此原理，便可通過規(guī)則更好地理解各題目間的關聯(lián)，并為用戶做出合適的推薦。此外，基于關聯(lián)規(guī)則的推薦還有著同樣適用于只有少量歷史行為記錄的新用戶的優(yōu)點，避免了“冷啟動”[3]問題。

實驗取得了較好的成果，該研究能服務于廣大OJ使用者和程序設計競賽參賽隊員。

1 關聯(lián)規(guī)則

1.1 相關概念

關聯(lián)規(guī)則相關概念的定義[4]可表述如下：

在關聯(lián)分析時，采用支持度和置信度來量化該過程的成功與否[5]。所以，需要預先設置最小支持度（minSupp）和最小置信度（minConf），針對低于這2個參數(shù)值的規(guī)則不予挖掘。分析可得原因如下：

（1）若某條規(guī)則的支持度太小，則代表性不強；

（2）若某條規(guī)則的置信度太小，則可靠性不夠。

定義5頻繁項集 若某項集X的支持度大于等于預設的最小支持度，即Supp（X） ≥ minSupp，則稱該項集X為頻繁項集。

定義6項集的維數(shù) 該項集中所包含項目的個數(shù)。稱維數(shù)為k的項集為k-項集。

1.2 主要流程

OJ推薦系統(tǒng)的關聯(lián)規(guī)則挖掘可分為3步，步驟內(nèi)容可分述如下[5]：

（1）參數(shù)預設。設置最小支持度minSupp和最小置信度minConf。

（2）發(fā)現(xiàn)頻繁項集。以OJ上所有用戶的歷史做題列表作為數(shù)據(jù)集，挖掘出頻繁項集X，滿足Supp（X） ≥ minSupp。

1.3 挖掘算法

關聯(lián)規(guī)則挖掘的常見算法有：Apriori算法與其擴展算法[6]，F(xiàn)P-growth算法等。本文選用Apriori算法來挖掘OJ上用戶所做題目間的關聯(lián)，為后續(xù)推薦的生成提供依據(jù)。

Apriori算法挖掘的是布爾關聯(lián)規(guī)則。所謂布爾關聯(lián)規(guī)則是指所處理的數(shù)據(jù)只表明了“有”和“無”的關系，而無需具體考慮數(shù)據(jù)在某些字段上數(shù)值的關聯(lián)。該算法經(jīng)過大量學者的研究，現(xiàn)已廣泛應用于其它領域和問題的研究中，如醫(yī)療衛(wèi)生[7]、決策分析[8]、氣象分析[9]等，并且成為了分析事物間關聯(lián)性問題的有效工具。

根據(jù)Apriori算法的思想，就可將（k-1）-項集兩兩取并集得到一組k-項集，隨后通過最小支持度minSupp剪枝去除非頻繁項集得到頻繁k-項集；重復這一過程，直到?jīng)]有新的頻繁k-項集產(chǎn)生為止。最后，通過頻繁項集推導出關聯(lián)規(guī)則，將所得的關聯(lián)規(guī)則根據(jù)最小置信度minConf進行過濾，由此得到強關聯(lián)規(guī)則，用于推薦系統(tǒng)。

算法主要包含2部分：發(fā)現(xiàn)頻繁項集和關聯(lián)規(guī)則生成。其中發(fā)現(xiàn)頻繁項集的過程可分為連接和剪枝兩步。這一過程不斷循環(huán)，直至演變生成的項集包含了數(shù)據(jù)集中的所有頻繁項。同時，使用支持度作為發(fā)現(xiàn)頻繁項集的量化指標。以OJ推薦系統(tǒng)為例，連接與剪枝的原理可設計展開如下。

例1 假設有4名學生，歷史做題情況分別為（數(shù)字代表題目id）：S1 = {1 2 3 4 5 6}，S2 = {2 3 4 5 8}，S3 = {2 3 4 8 9}，S4 = {1 5 7 9}。連接和剪枝過程則如圖1和圖2所示。

在圖1中，第一行列出了所有的1-項集，第二行表示各個1-項集在S1、S2、S3、S4中出現(xiàn)的頻次，第三行表示了1-項集在數(shù)據(jù)集I中的支持度Supp；由于1-項集{6}和{7}的支持度Supp小于設定的minSupp = 0.5，故而將其剪去。

在圖2中，剪枝后剩余的1-項集兩兩取并集得到2-項集及其支持度Supp，不滿足Supp ≥ minSupp的2-項集也將會剪去；類似地，先合并、再剪枝，得到3-項集至N-項集，便可獲得所有的頻繁項集，如{2 3 4}、 {2 3 5}、 {2 4 5}等。

2 基于關聯(lián)規(guī)則的推薦

綜上研究后，挖掘得到的關聯(lián)規(guī)則，表明了OJ編程題目之間的聯(lián)系，將目標用戶的歷史做題數(shù)據(jù)集作為規(guī)則的前繼，規(guī)則的后繼便是可以向該用戶推薦的題目集。

2.1 針對OJ的推薦方法

Apriori算法常用于購物推薦，而OJ推薦上并不完全等同于購物推薦，顧客對于曾經(jīng)購買的商品可以再次購買，而用戶并不會反復選定已經(jīng)做過的題目。用戶的做題數(shù)據(jù)存在時間上的先后順序（一般由易到難地進行練習），所以在進行題目的個性化推薦時也要考慮并利用到這種先后順序。

研究中，假設有3名學生S1，S2，S3，各自的做題情況如圖4所示。圖4中的每一行代表一位學生的做題情況，每一行里的數(shù)字代表做題的題號，題號自左向右的順序指明了每位學生的做題順序。

如圖4所示，不劃分做題周期，就圖中提供的這一周期的數(shù)據(jù)而言，將產(chǎn)生數(shù)據(jù)集為：{1 3 5 2 4 6}、 {1 2 4 3 5 6}、 {1 3 6 2 4 5}。由于3個數(shù)據(jù)集的元素相同，將生成鏈式關聯(lián)規(guī)則{1}{6}，且每一條規(guī)則的支持度Supp和置信度Conf 都為1，從而無法通過剪枝過濾掉任何一條關聯(lián)規(guī)則。

基于此，為了使推薦方法能夠給出更加細致以及符合預期的結果，需要將每個用戶的做題數(shù)據(jù)集按周期進行劃分，再進行關聯(lián)規(guī)則的挖掘。

圖5中，將用戶的做題數(shù)據(jù)按周期B劃分為2段，將產(chǎn)生如下數(shù)據(jù)集：{1 3 5}、{ 2 4 6}、 {1 2 4}、{ 3 5 6}、 {1 3 6}、{2 4 5} ，代入Apriori算法后得到的強關聯(lián)規(guī)則可如圖6所示。

劃分周期后，避免了出現(xiàn)鏈式關聯(lián)規(guī)則的情況，改進了原有算法對于數(shù)據(jù)信息挖掘的不足（忽略了時間先后順序這一信息），提高了關聯(lián)規(guī)則推薦方法對于OJ推薦的適配性。

2.2 候選結果優(yōu)化

根據(jù)規(guī)則得到的推薦結果可能有很多個。若將所有結果全部推薦給用戶，可能會讓用戶陷于無所適從的困擾。需要對推薦結果進行排序，將排在前3位的結果推薦給用戶，即本文的推薦方法最終將為每位OJ用戶推薦3道題。而推薦度就是評價候選結果推薦程度的衡量指標。

關于推薦度，推導可得如下數(shù)學公式[10]：

其中，RD為推薦度；R表示一條關聯(lián)規(guī)則；ω1和ω2既可以事先指定，也可以由推薦系統(tǒng)學習得到。公式（1）的作用是對關聯(lián)規(guī)則進行排序，找到最可靠的規(guī)則。

根據(jù)推薦度RD的數(shù)值由大到小對推薦結果依次排序，便可得到合理的推薦序列。

3 實驗評估

3.1 實驗數(shù)據(jù)

本文從東華大學的Online Judge系統(tǒng)，DHUOJ（http：//acm.dhu.edu.cn/）上，截取并下載了總計395名學生關于2 317道題的做題情況作為實驗的源數(shù)據(jù)，時間跨度為2015/04/10～2017/01/05，共計65 535條記錄。數(shù)據(jù)（單條）形式可見表1。此處對學生姓名引入了脫名處理。

在此基礎上，對數(shù)據(jù)進行清洗和篩選。這一過程主要包括內(nèi)容如下。

首先，只保留了學生提交狀態(tài)為“Accepted”的記錄，并且對于同一題，只保留學生第一次Accepted的記錄。

其次，為方便之后的關聯(lián)規(guī)則挖掘，將記錄中的所有題目進行重新編號，用編號代替題目名稱。

最后，得到的可輸入算法求取關聯(lián)規(guī)則的數(shù)據(jù)（單條）形式見表2。

3.2 推薦效果評估標準

分類準確度[11]是評價推薦結果是否正確、而且反映了用戶喜好的性能指標。這種指標多用于有著明確二分性的系統(tǒng)中。即，對于某一具體的事物，系統(tǒng)中的所有用戶只對其做出“喜歡”或“不喜歡”兩種評判。

對于OJ用戶而言，編程題可直接劃分為“做過”和“未做過”兩種狀態(tài)。因此，OJ即是一種有著明確二分標準的系統(tǒng)。故而，本文可選用準確率和召回率綜合而得的F1值來對推薦的準確性進行評估。

對于每名用戶的推薦效果，其準確率、召回率在OJ題目推薦中的計算方法如下：

其中，推薦命中的題目表示推薦的題目與用戶實際所做題目的交集。

本文保留用戶最后所做的3道題作為驗證，所以公式（3）中的用戶實際做題數(shù)在此處為3。

在實驗中，每對一名用戶做出推薦后都會伴隨一次評估，得到一個準確率和召回率。實驗結束后，對實驗中所得的準確率和召回率求出算術平均。而后根據(jù)這2個平均值，計算出OJ上推薦效果的總體F1值。此時，得到總體F1值即為用于評估推薦效果的指標。

3.3 參數(shù)評估

本實驗中，F(xiàn)1值依賴于minSupp和minConf值的選取。因此，對minSupp指定為0.015～0.035，minConf為0.25～0.75的情況下（共55種情形），運行得到的F1值進行了綜合統(tǒng)計、并繪制展示，最終效果如圖8所示。

由圖8可得，當minConf為0.30時，可獲得最大F1值。因此將最小置信度設定為0.30，此時F1值和minSupp的變化趨勢則如圖9所示。

由圖9可知，當minSupp為0.025、minConf為0.30時，可推得最大F1值的峰值為0.446。

3.4 結論分析

若選取minSupp為0.025，minConf為0.30，可為用戶做出最佳的有效推薦。在此前提下，以推薦的3題中至少有1題推薦正確為標準，準確率為74.2%。最小支持度的設定是為了保障研究挖掘到的規(guī)則質(zhì)量，若隨意調(diào)低最小支持度，可能將會對結果產(chǎn)生負面影響。

相比此前要在包含有數(shù)千道題的題庫中尋找要做的題目，現(xiàn)在這些用戶只需從推薦的幾道題（至多3道題）中進行選擇即可。在一定程度上可以幫助用戶節(jié)約瀏覽題庫的時間。

由于題庫中會存有數(shù)千題，而實驗中的93名用戶僅做了50～100題，若采用隨機推薦的方法，準確率和召回率都將非常低（接近0.000）。與其相較之下，本推薦功能已具有一定的成效。

4 結束語

本文提出了一種基于關聯(lián)規(guī)則挖掘的OJ推薦方法，通過分析OJ用戶的歷史做題數(shù)據(jù)，使用并針對OJ推薦改進現(xiàn)有的Apriori算法推導出強關聯(lián)規(guī)則、且使用規(guī)則，對目標用戶進行做題推薦。實驗結果顯示，本系統(tǒng)可對大多數(shù)用戶做出有效推薦，即保證用戶在推薦的3道題內(nèi)找到適合自己的編程題目。從根本上解決了隨機推薦方法的低準確率問題，相當程度上大幅提高了OJ推薦對于用戶的可用性。

參考文獻

[1] 王愛平 王占鳳 陶嗣干，等. 數(shù)據(jù)挖掘中常用關聯(lián)規(guī)則挖掘算法[J]. 計算機技術與發(fā)展 2010 20（4）：105-108.

[2] AGRAWAL R，SRIKANT R. Fast algorithms for mining association rules[C]//Proceedings of 20th International Conference on Very Large Databases. Santiago de Chile Chile： Morgan Kaufmann 1994：487-499.

[3] 孫冬婷，何濤，張福海. 推薦系統(tǒng)中的冷啟動問題研究綜述[J]. 計算機與現(xiàn)代化，2012（5）：59-63.

[4] 朱惠. 關聯(lián)規(guī)則中Apriori算法的研究與改進[J]. 電腦知識與技術 2014，10（12）：2697-2701.

[5] HARRINGTON P. 機器學習實戰(zhàn)[M]. 李銳，李鵬，曲亞東，譯. 北京：人民郵電出版社 2013.

[6] SCHLEGEL B KIEFER T KISSINGER T et al. PcApriori： Scalable apriori for multiprocessor systems[C]// International Conference on Scientific and Statistical Database Management. Baltimore Maryland USA：ACM 2013：1-12.

[7] CUI Xiaoyan YANG Shimeng WANG D. An algorithm of Apriori based on medical big data and cloud computing[C]//2016 4th International Conference on Cloud Computing and Intelligence Systems （CCIS）. Beijing，China：IEEE 2016： 361-365.

[8] 魏茂林. Apriori算法的改進及其在教育決策系統(tǒng)中的應用[D]. 長春：吉林大學，2010.

[9] 黃鈞晟. 云計算環(huán)境下基于Apriori算法的氣象數(shù)據(jù)關聯(lián)規(guī)則分析研究[D]. 南京：南京信息工程大學 2015.

[10]劉亞波. 關聯(lián)規(guī)則挖掘方法的研究及應用[D]. 長春：吉林大學 2005.

[11]朱郁筱 呂琳媛. 推薦系統(tǒng)評價指標綜述[J]. 電子科技大學學報 2012 41（2）：163-175