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

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

1 研究背景及意義

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

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

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

2 研究設(shè)計

2.1 研究材料

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

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

2.2 研究工具

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

2.3 研究步驟

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

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

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

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

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

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

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

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

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

在創(chuàng)建模型時，嘗試不同的特征子集，創(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)算法對數(shù)據(jù)進行監(jiān)督分類，CART算法采用一種二分遞歸分割的技術(shù)，將當(dāng)前的樣本集分為兩個子樣本集，使得生成的每個非葉子節(jié)點都有兩個分支。CART算法由以下兩步組成：

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

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

（1）決策樹生成

上面說到CART算法分為兩個過程，其中一個過程進行遞歸建立二叉樹。

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

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

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

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

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

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

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

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

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

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

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

（2）決策樹剪枝

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

3.2 特征提取

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

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

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

（2）特征粗提取過程

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

圖2 平均AC量對比

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

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

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

圖3 AC平均用時

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

（3）特征再處理

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

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

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

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

4 實驗分析

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

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

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

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

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

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

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

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

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

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

4.3 實驗結(jié)果分析

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

4.4 模型優(yōu)化

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

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

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

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

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

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

[5]姚孟臣.數(shù)量化方法在試題難度中的應(yīng)用[J].數(shù)理統(tǒng)計與管理，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.