基于在線測(cè)評(píng)系統(tǒng)的編程題目難度研究

陳薈慧，熊楊帆，蔣滔滔，李佳

（重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400044）

1 研究背景及意義

自進(jìn)入21世紀(jì)以來，幾乎全民都在制造數(shù)據(jù)，大數(shù)據(jù)這個(gè)話題進(jìn)入了各界學(xué)者的討論范圍。數(shù)據(jù)分析是組織有目的地收集數(shù)據(jù)、分析數(shù)據(jù)，使之成為信息的過程。數(shù)據(jù)分析的目的是把隱沒在一大批看來雜亂無章的數(shù)據(jù)中的信息集中、萃取和提煉出來，以找出所研究對(duì)象的內(nèi)在規(guī)律。

程序在線測(cè)評(píng)系統(tǒng)，起源于ACM/ICPC國際大學(xué)生程序設(shè)計(jì)競賽，是為培訓(xùn)該程序競賽參賽人員開發(fā)的，但是在培訓(xùn)過程中，研究人員發(fā)現(xiàn)，OJ系統(tǒng)在大學(xué)生程序設(shè)計(jì)類課程的教學(xué)中也能發(fā)揮很大的作用，于是OJ也漸漸走入相關(guān)課程的教學(xué)中。很多高校都開發(fā)出了自己的OJ系統(tǒng)，其中較為著名的有浙江大學(xué)Online Judge（ZOJ）、北京大學(xué) Online Judge（POJ）、同濟(jì)大學(xué) Online Judge（TOJ）、西班牙 Valladolid大學(xué) Online Judge（UVA）等，值得一提的是，在本研究的過程中，重慶大學(xué)也收獲了自己的OJ系統(tǒng)，重慶大學(xué)Online Judge（CQUOJ）。

對(duì)OJ系統(tǒng)中的題目進(jìn)行難度研究，是因?yàn)樵诰€學(xué)習(xí)的學(xué)習(xí)者的編程能力良莠不齊，如何在練習(xí)的過程中對(duì)水平不同的學(xué)習(xí)者推薦有針對(duì)性的題目，是近年來OJ系統(tǒng)要解決的難題。而現(xiàn)在的多數(shù)OJ系統(tǒng)里的題目難度是靠做題人的主觀經(jīng)驗(yàn)手動(dòng)完成的，費(fèi)時(shí)費(fèi)力。OJ系統(tǒng)中保存著大量的測(cè)評(píng)數(shù)據(jù)，這些測(cè)評(píng)數(shù)據(jù)直接或間接反映了學(xué)習(xí)者的學(xué)習(xí)行為，我們就利用OJ系統(tǒng)中的原始數(shù)據(jù)，從中隨機(jī)抽取部分?jǐn)?shù)據(jù)作為研究樣本，綜合考慮各項(xiàng)因素，最終選擇對(duì)題目難度研究最有效的特征集，利用這些特征創(chuàng)建分類模型，為在線測(cè)評(píng)系統(tǒng)上的題目作自動(dòng)分類預(yù)測(cè)。

2 研究設(shè)計(jì)

2.1 研究材料

本研究的實(shí)驗(yàn)數(shù)據(jù)來自著名的在線評(píng)測(cè)系統(tǒng)Codeforces，Codeforces是一家為計(jì)算機(jī)編程愛好者提供在線評(píng)測(cè)系統(tǒng)的俄羅斯網(wǎng)站。選擇該系統(tǒng)，是因?yàn)镃odeforces是眾多OJ系統(tǒng)中為數(shù)不多的為編程試題提供難度分類的系統(tǒng)。系統(tǒng)標(biāo)記的經(jīng)驗(yàn)難度參數(shù)作為本研究中決策樹分類成果的檢驗(yàn)標(biāo)準(zhǔn)，測(cè)試模型性能。

實(shí)驗(yàn)數(shù)據(jù)選擇的是Codeforces上2016年12月-2017年12月時(shí)間段內(nèi)100多場(chǎng)比賽里的題目提交記

2.2 研究工具

本研究使用的工具中最重要的是scikit-learn包（簡稱sklearn），在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘的應(yīng)用中，sklearn是一個(gè)功能強(qiáng)大的Python包。實(shí)驗(yàn)中主要使用的部分就是sklearn.tree，模塊自帶的決策樹方法，它分為兩個(gè)決策樹模型，分別是DecisionTreeClassifier()分類決策樹模型和DecisionTreeRegressor()回歸決策樹模型。由于本研究是為了給不同題目分配不同的難度類型，實(shí)驗(yàn)中使用的是分類決策樹模型。scikit-learn中決策樹的可視化使用的是graphviz。

2.3 研究步驟

錄，每場(chǎng)比賽有5-7題，按經(jīng)驗(yàn)分別被標(biāo)記為ABCDEFG類，共600道題，其中2/3的題目用作訓(xùn)練集，1/3的題目用作測(cè)試集。每場(chǎng)比賽的提交記錄最多可到達(dá)25000條，共200多萬條提交記錄數(shù)據(jù)。

以Codeforces上采集的原始評(píng)測(cè)數(shù)據(jù)為分析對(duì)象，而原始數(shù)據(jù)往往存在錯(cuò)誤和噪音點(diǎn)，所以首先要對(duì)實(shí)驗(yàn)數(shù)據(jù)做清洗處理。其次進(jìn)行數(shù)據(jù)歸一化，更方便觀察特征之間的可比性，然后根據(jù)選擇出的特征集，結(jié)合決策樹算法創(chuàng)建分類模型，以達(dá)到在線題目難度劃分的目的，最后通過調(diào)整模型參數(shù)和剪枝操作，不斷優(yōu)化分類模型，得到最優(yōu)方案，具體步驟如下：

（1）數(shù)據(jù)的采集

為了使采集的樣本更客觀地反映題目難度，樣本選擇的是Codeforces線上比賽的提交記錄樣本，因?yàn)橐话阍诒荣惿线M(jìn)行練習(xí)時(shí)，不僅有合理的時(shí)間限制，而且學(xué)習(xí)者能夠更專心，較少受到主觀因素的打擾，這個(gè)時(shí)候的測(cè)評(píng)數(shù)據(jù)更能反映題目的客觀難度。采集數(shù)據(jù)的過程是利用python編寫的爬蟲腳本來完成的，首先確定爬取的比賽編號(hào)，然后確定該場(chǎng)比賽的開始時(shí)間與時(shí)長，爬取比賽時(shí)長內(nèi)所有提交記錄。獲取的每條原始記錄有很多特征值，如用戶名、用戶提交時(shí)刻、提交的題目難度類型、測(cè)評(píng)結(jié)果、程序運(yùn)行時(shí)長、運(yùn)行所占內(nèi)存等。

（2）數(shù)據(jù)的清洗

從Codeforces上爬取的全部都是原始數(shù)據(jù)，而且后期的用于創(chuàng)建模型的數(shù)據(jù)是經(jīng)過匯總的數(shù)據(jù)，匯總時(shí)也可能遺漏數(shù)據(jù)，所以在進(jìn)行數(shù)據(jù)分析之前，首先作數(shù)據(jù)預(yù)處理。預(yù)處理操作是對(duì)原始數(shù)據(jù)進(jìn)行數(shù)據(jù)空值和錯(cuò)誤值的檢測(cè)和清洗，除去孤立數(shù)據(jù)，將噪聲數(shù)據(jù)產(chǎn)生的影響降到最低。

（3）數(shù)據(jù)的歸一化

數(shù)據(jù)歸一化化就是要把需要處理的數(shù)據(jù)經(jīng)過處理后（通過某種算法），限制在需要的一定范圍內(nèi)。歸一化是為了后面數(shù)據(jù)處理的方便，保證程序運(yùn)行時(shí)收斂加快。本研究中的用于機(jī)器學(xué)習(xí)的樣本，是提交記錄匯總后的沒類難度類型的題目提交情況，每個(gè)樣本中包含的屬性有題目編號(hào)、題目難度類型、題目總的提交次數(shù)、題目總的通過次數(shù)（簡稱總AC量）、題目首次提交即通過的次數(shù)（簡稱1A量）、通過時(shí)的總用時(shí)（簡稱AC總用時(shí)）。屬性的取值多是整型和浮點(diǎn)型，取值范圍較大，不利于模型的訓(xùn)練，所以在不影響總體結(jié)果的前提下，對(duì)數(shù)據(jù)進(jìn)行歸一化，產(chǎn)生了AC率和1A率，以及AC平均用時(shí)。

（4）模型的創(chuàng)建

在創(chuàng)建模型時(shí)，嘗試不同的特征子集，創(chuàng)建不同的決策樹模型，并通過后期的剪枝過程，不斷優(yōu)化模型的性能，選出最優(yōu)分類模型。

3 算法及關(guān)鍵技術(shù)

根據(jù)上一章節(jié)的內(nèi)容我們知道，本研究中的分類模型如圖1所示，接下來介紹在研究過程中的算法及關(guān)鍵技術(shù)。

圖1 分類模型

3.1 決策樹分類算法

本文使用決策樹中的CART(Classification And Regression Tree)算法對(duì)數(shù)據(jù)進(jìn)行監(jiān)督分類，CART算法采用一種二分遞歸分割的技術(shù)，將當(dāng)前的樣本集分為兩個(gè)子樣本集，使得生成的每個(gè)非葉子節(jié)點(diǎn)都有兩個(gè)分支。CART算法由以下兩步組成：

決策樹生成：基于訓(xùn)練數(shù)據(jù)集生成決策樹，生成的決策樹要盡量大。

決策樹剪枝：用驗(yàn)證數(shù)據(jù)集對(duì)已生成的樹進(jìn)行剪枝并選擇最優(yōu)子樹。

（1）決策樹生成

上面說到CART算法分為兩個(gè)過程，其中一個(gè)過程進(jìn)行遞歸建立二叉樹。

設(shè) X1，X2，...，Xn代表單個(gè)樣本的 n個(gè)屬性，Y 代表所屬類別。CART算法通過遞歸的方式將n維的空間劃分為不重疊的矩形，劃分時(shí)的具體操作是：選一個(gè)自變量Xi，再選取Xi的一個(gè)值vi，vi把n維空間劃分為兩部分，對(duì)于連續(xù)變量，一部分的所有點(diǎn)都滿足Xi≤vi，另一部分的所有點(diǎn)都滿足Xi>vi,對(duì)非連續(xù)變量，屬性值的取值只有兩個(gè)，即等于該值或不等于該值。

在劃分的時(shí)候還有一個(gè)問題，選擇特征屬性和分裂點(diǎn)的標(biāo)準(zhǔn)是什么。對(duì)于CART算法來說，它采用Gini指數(shù)來度量分裂時(shí)的不純度，之所以采用Gini指數(shù)，是因?yàn)檩^于熵而言其計(jì)算速度更快一些。

具體的，在分類問題中，假設(shè)有K個(gè)類別，在決策樹的節(jié)點(diǎn)t處，第k個(gè)類別的概率為P(Ck|t)，Gini指數(shù)計(jì)算公式如下：

Gini指數(shù)即為1與類別Ck的概率平方之和的差值，反映了樣本集合的不確定性程度。Gini指數(shù)越大，樣本集合的不確定性程度越高。分類學(xué)習(xí)過程的本質(zhì)是樣本不確定性程度的減少（即熵減過程），故應(yīng)選擇最小Gini指數(shù)的特征分裂。父節(jié)點(diǎn)對(duì)應(yīng)的樣本集合為D，CART選擇特征A分裂為兩個(gè)子節(jié)點(diǎn)，對(duì)應(yīng)集合為DL與DR；分裂后的Gini指數(shù)定義如下：

其中，|?|表示樣本集合的記錄數(shù)量。

綜上所述，CART分類算法建立樹的具體流程如下：

①對(duì)于當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)集為D，如果樣本個(gè)數(shù)小于閾值或者沒有特征，則返回決策子樹，當(dāng)前節(jié)點(diǎn)停止遞歸。

②計(jì)算樣本集D的基尼系數(shù)，如果基尼系數(shù)小于閾值，則返回決策樹子樹，當(dāng)前節(jié)點(diǎn)停止遞歸。

③計(jì)算當(dāng)前節(jié)點(diǎn)現(xiàn)有的各個(gè)特征的各個(gè)特征值對(duì)數(shù)據(jù)集D的基尼系數(shù)。

④在計(jì)算出來的各個(gè)特征的各個(gè)特征值對(duì)數(shù)據(jù)集D的基尼系數(shù)中，選擇基尼系數(shù)最小的特征A和對(duì)應(yīng)的特征值a。根據(jù)這個(gè)最優(yōu)特征和最優(yōu)特征值，把數(shù)據(jù)集劃分成兩部分D1和D2，同時(shí)建立當(dāng)前節(jié)點(diǎn)的左右節(jié)點(diǎn)，左節(jié)點(diǎn)的數(shù)據(jù)集D為D1，右節(jié)點(diǎn)的數(shù)據(jù)集D為D2。

⑤對(duì)左右的子節(jié)點(diǎn)遞歸的調(diào)用①-④步，生成決策樹。

（2）決策樹剪枝

由于決策時(shí)算法很容易對(duì)訓(xùn)練集過擬合，而導(dǎo)致泛化能力差，為了解決這個(gè)問題，我們需要對(duì)CART樹進(jìn)行剪枝，來增加決策樹的返回能力。CART采用的辦法是后剪枝法，即先生成決策樹，然后產(chǎn)生所有可能的剪枝后的CART樹，然后使用交叉驗(yàn)證來檢驗(yàn)各種剪枝的效果，選擇泛化能力最好的剪枝策略。

3.2 特征提取

爬取到的原始數(shù)據(jù)集經(jīng)過統(tǒng)計(jì)，匯總出訓(xùn)練數(shù)據(jù)集。在建立分類模型之前，先要根據(jù)訓(xùn)練數(shù)據(jù)集提取特征集，在提取特征之前，我們首先對(duì)訓(xùn)練數(shù)據(jù)集中的各個(gè)特征之間的關(guān)系進(jìn)行了分析，選擇出對(duì)編程題目難度研究最為有效的特征。

（1）數(shù)據(jù)匯總

上文提到，原始數(shù)據(jù)是一條條的提交記錄，顯然，直接使用原始數(shù)據(jù)集訓(xùn)練分類模型是不可行的，必須對(duì)提交記錄進(jìn)行匯總，得到關(guān)于題目的統(tǒng)計(jì)數(shù)據(jù)作為訓(xùn)練集，創(chuàng)建分類模型。原始數(shù)據(jù)包括的屬性很多，實(shí)驗(yàn)中只統(tǒng)計(jì)可能影響題目難度的數(shù)據(jù)。匯總時(shí)，以題目編號(hào)為關(guān)鍵字，統(tǒng)計(jì)一場(chǎng)比賽中該題的總提交次數(shù)、結(jié)果為“Accepted”的總次數(shù)、首次提交就“Accepted”的次數(shù)、結(jié)果為“Accepted”的總用時(shí)。其中“Accepted”用時(shí)是通過記錄提交時(shí)間減去比賽開始時(shí)間得到的。

（2）特征粗提取過程

訓(xùn)練數(shù)據(jù)集中題目難度是離散化的幾種類型，沒有達(dá)到難度量化的程度，在研究初始時(shí)，我們就根據(jù)之前的經(jīng)驗(yàn)認(rèn)為AC量在一定程度上可以表示量化的題目難度。所以我們首先嘗試著去分析不同難度類型的題目AC量分布情況。圖2是每種類型試題的平均AC量分布情況。

圖2 平均AC量對(duì)比

圖2的平均AC量對(duì)比情況顯示了7種不同類型的題目AC量分布狀態(tài)。由這些圖可知，不同題目AC量集中分布的量和范圍因題目難度類型的不同而有明顯的不同，因此我們確定了樣本中AC量為首要研究的自變量特征。

僅僅考慮AC量時(shí)，會(huì)遇到一種情況：當(dāng)一個(gè)學(xué)習(xí)者在做練習(xí)時(shí)，經(jīng)過多次提交代碼，最終運(yùn)行出正確結(jié)果，即通過了該題，為了優(yōu)化解題過程，學(xué)習(xí)者可能會(huì)多次修改代碼并提交通過，這樣就提高了AC量，使得這個(gè)特征不能那么客觀地反映題目的難度類型。于是在分析樣本集時(shí)我們注意到了另一個(gè)很重要特征，1A量，即學(xué)習(xí)者首次提交就通過的次數(shù)。1A量不僅能有效體現(xiàn)題目難度類型，而且不存在重復(fù)提交的問題。

在處理數(shù)據(jù)時(shí)我們還得到如圖3的結(jié)論，學(xué)習(xí)者通過題目的平均用時(shí)越長，說明題目難度越大。所以把采集到的原始數(shù)據(jù)中AC總用時(shí)，即題目AC的提交時(shí)間與首次提交時(shí)間的差值之和，也作為研究對(duì)象的自變量特征。從這個(gè)變量可以看出某題從開始提交到通過的用時(shí)。

圖3 AC平均用時(shí)

通過以上分析，我們最終選擇AC量、1A量、AC總用時(shí)為模型研究的初始自變量特征。此時(shí)，對(duì)于題目Num_P_i使用（X1，X2，X3）三維特征來表示，其中 Num_P表示比賽的場(chǎng)次，i表示題目的經(jīng)驗(yàn)難度類型，取值范圍是{A,B,C,D,E,F,G}，X1是 AC 量，X2是 1A 量，X3是 AC總用時(shí)。

（3）特征再處理

①AC率：在使用AC量作自變量特征時(shí)還有一處不足，那就是在不同場(chǎng)比賽中，參賽的用戶數(shù)量不盡相同，總提交量、AC量可能存在差異過大的個(gè)別現(xiàn)象，所以為題目添加了另一個(gè)特征AC率，X4=AC量/總提交量。

②1A率：與AC量這個(gè)特征類似，1A量也是一個(gè)絕對(duì)量，也存在與AC量一樣的不足，所以用1A率替換了1A量這個(gè)特征，X2=X2/AC量。

③AC平均用時(shí)：上文中使用了AC總用時(shí)作為研究特征，但是在創(chuàng)建模型的過程中發(fā)現(xiàn)AC總用時(shí)的取值范圍太大，并不利于模型的創(chuàng)建，所以將AC總用時(shí)替換為AC平均用時(shí)，X3=X3/AC量。

綜合以上，題目 Num_P_i使用（X1，X2，X3,X4）四維特征來表示。

4 實(shí)驗(yàn)分析

4.1 采集數(shù)據(jù)

（1）原始數(shù)據(jù)集

我們知道，用于研究的原始數(shù)據(jù)是從OJ系統(tǒng)上爬取的多場(chǎng)比賽中學(xué)習(xí)者的提交記錄，在一場(chǎng)比賽中收集到的每條原始數(shù)據(jù)最主要內(nèi)容如圖4所示。

圖4 部分原始數(shù)據(jù)集

從上面的截圖可以看出，每一條原始記錄最主要的特征屬性有提交ID、提交時(shí)刻、提交用戶、題目名稱、使用語言、運(yùn)行結(jié)果、運(yùn)行時(shí)間、運(yùn)行內(nèi)存、題目難度類型。每一個(gè)用戶對(duì)同一道題可提交一到多次。

（2）訓(xùn)練數(shù)據(jù)集

通過將原始數(shù)據(jù)集里的提交記錄按照題目編號(hào)統(tǒng)計(jì)匯總，最終得到以題目編號(hào)為關(guān)鍵字的訓(xùn)練數(shù)據(jù)集，其主要內(nèi)容如下截圖所示。

4.2 特征值數(shù)量分析

以難度類型ABCDEFG的題目為例，選擇四元組特征集，對(duì)創(chuàng)建的分類模型分析。使用X1，X2，X3,X4四個(gè)特征變量執(zhí)行分類算法，對(duì)分類結(jié)果的測(cè)試如下表1所示。

表1 預(yù)測(cè)結(jié)果

4.3 實(shí)驗(yàn)結(jié)果分析

分析表1我們發(fā)現(xiàn)，ABC難度類型的題預(yù)測(cè)正確率超過了65%，D類型預(yù)測(cè)正確率52.78%，但是EFG類題目的預(yù)測(cè)正確率低于50%。之所以會(huì)產(chǎn)生如此低的正確率，是有原因的。在Codeforces系統(tǒng)上的比賽中，EFG類題目已經(jīng)屬于難度很大的題了，做題的人數(shù)很少，導(dǎo)致提交記錄很低，對(duì)這類題的訓(xùn)練度明顯不夠。這種情況下創(chuàng)建的分類樹對(duì)EFG類題目進(jìn)行預(yù)測(cè)時(shí)，并不能達(dá)到預(yù)期的結(jié)果，所以對(duì)樹的優(yōu)化必不可少。

4.4 模型優(yōu)化

從對(duì)實(shí)驗(yàn)結(jié)果的分析可知，EFG類題目屬于難度較大的題目，提交量不足、訓(xùn)練度不夠，達(dá)不到預(yù)期結(jié)果，所以在優(yōu)化分類樹時(shí)，將這三類題目當(dāng)做同一類題目處理，記作P難度類型。提交量這一因素處理影響了對(duì)EFG類題目的分類外，還影響了每種題目的AC量，而AC量在創(chuàng)建二叉樹時(shí)起到了很重要的作用，所以AC量的起伏過大對(duì)分類結(jié)果的影響也很大。于是我們將AC量作用在log()函數(shù)上，這樣就緩和AC量的過大波動(dòng)，優(yōu)化了分類樹。

通過以上優(yōu)化方法，分類樹的性能得到了很大的提高。

[1]郭嵩山,王磊,張子臻.ACM/ICPC與創(chuàng)新型IT人才的培養(yǎng)[J].實(shí)驗(yàn)室研究與探索，2007:188-192,196.

[2]李文新，郭煒.北京大學(xué)程序在線測(cè)評(píng)系統(tǒng)及其應(yīng)用[J].吉林大學(xué)學(xué)報(bào)，2005.8（23）：171-177.

[3]郭嵩山,王磊,張子臻.ACM/ICPC與創(chuàng)新型IT人才的培養(yǎng)[J].實(shí)驗(yàn)室研究與探索，2007:188-192,196.

[4]范玉玲,徐濤,王欽.基于在線測(cè)評(píng)數(shù)據(jù)的題目等級(jí)分類模型研究[J].計(jì)算機(jī)與現(xiàn)代化，2017：3（259）：37-38.

[5]姚孟臣.數(shù)量化方法在試題難度中的應(yīng)用[J].數(shù)理統(tǒng)計(jì)與管理，1993.2（2）：21-27.

[6]John D.Kelleher,Brian Mac Namee,Aoife D'Arcy.Fundamentals of Machine Learning for Predictive Data[M].Publisher:The MIT Press,2015-7-24.