基于關(guān)聯(lián)規(guī)則挖掘的OJ推薦方法

朱國(guó)進(jìn) 凌曉晨

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

關(guān)鍵詞： 關(guān)聯(lián)規(guī)則挖掘；機(jī)器學(xué)習(xí)；推薦系統(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

引言

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

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

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

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

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

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

實(shí)驗(yàn)取得了較好的成果，該研究能服務(wù)于廣大OJ使用者和程序設(shè)計(jì)競(jìng)賽參賽隊(duì)員。

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

1.1 相關(guān)概念

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

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

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

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

定義5頻繁項(xiàng)集 若某項(xiàng)集X的支持度大于等于預(yù)設(shè)的最小支持度，即Supp（X） ≥ minSupp，則稱該項(xiàng)集X為頻繁項(xiàng)集。

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

1.2 主要流程

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

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

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

1.3 挖掘算法

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

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

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

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

例1 假設(shè)有4名學(xué)生，歷史做題情況分別為（數(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}。連接和剪枝過(guò)程則如圖1和圖2所示。

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

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

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

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

2.1 針對(duì)OJ的推薦方法

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

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

如圖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個(gè)數(shù)據(jù)集的元素相同，將生成鏈?zhǔn)疥P(guān)聯(lián)規(guī)則{1}{6}，且每一條規(guī)則的支持度Supp和置信度Conf 都為1，從而無(wú)法通過(guò)剪枝過(guò)濾掉任何一條關(guān)聯(lián)規(guī)則。

基于此，為了使推薦方法能夠給出更加細(xì)致以及符合預(yù)期的結(jié)果，需要將每個(gè)用戶的做題數(shù)據(jù)集按周期進(jìn)行劃分，再進(jìn)行關(guān)聯(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算法后得到的強(qiáng)關(guān)聯(lián)規(guī)則可如圖6所示。

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

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

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

關(guān)于推薦度，推導(dǎo)可得如下數(shù)學(xué)公式[10]：

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

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

3 實(shí)驗(yàn)評(píng)估

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

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

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

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

3.2 推薦效果評(píng)估標(biāo)準(zhǔn)

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

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

對(duì)于每名用戶的推薦效果，其準(zhǔn)確率、召回率在OJ題目推薦中的計(jì)算方法如下：

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

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

在實(shí)驗(yàn)中，每對(duì)一名用戶做出推薦后都會(huì)伴隨一次評(píng)估，得到一個(gè)準(zhǔn)確率和召回率。實(shí)驗(yàn)結(jié)束后，對(duì)實(shí)驗(yàn)中所得的準(zhǔn)確率和召回率求出算術(shù)平均。而后根據(jù)這2個(gè)平均值，計(jì)算出OJ上推薦效果的總體F1值。此時(shí)，得到總體F1值即為用于評(píng)估推薦效果的指標(biāo)。

3.3 參數(shù)評(píng)估

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

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

由圖9可知，當(dāng)minSupp為0.025、minConf為0.30時(shí)，可推得最大F1值的峰值為0.446。

3.4 結(jié)論分析

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

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)

[1] 王愛(ài)平 王占鳳 陶嗣干，等. 數(shù)據(jù)挖掘中常用關(guān)聯(lián)規(guī)則挖掘算法[J]. 計(jì)算機(jī)技術(shù)與發(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)中的冷啟動(dòng)問(wèn)題研究綜述[J]. 計(jì)算機(jī)與現(xiàn)代化，2012（5）：59-63.

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

[5] HARRINGTON P. 機(jī)器學(xué)習(xí)實(shí)戰(zhàn)[M]. 李銳，李鵬，曲亞?wèn)|，譯. 北京：人民郵電出版社 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算法的改進(jìn)及其在教育決策系統(tǒng)中的應(yīng)用[D]. 長(zhǎng)春：吉林大學(xué)，2010.

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

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

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