楊　柳，王　鈺1.山西財經(jīng)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院，太原 030006.山西大學(xué) 軟件學(xué)院，太原 030006

組塊3×2交叉驗證的F1度量的方差分析*

楊柳1+，王鈺2
1.山西財經(jīng)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院，太原 030006
2.山西大學(xué) 軟件學(xué)院，太原 030006

YANG Liu,WANG Yu.Analysis of variance of F1 measure based on blocked 3×2 cross validation.Journal of Frontiers of Computer Science and Technology,2016,10(8)：1176-1183.

摘要：在統(tǒng)計機(jī)器學(xué)習(xí)的研究中，研究者常常通過定量實(shí)驗來對照基于交叉驗證的分類算法的F1度量，為了得到統(tǒng)計可信的結(jié)論，估計它的不確定性是非常重要的。特別地，組塊3×2交叉驗證方法被大量理論和實(shí)驗驗證了它的性能優(yōu)于諸如標(biāo)準(zhǔn)K折交叉驗證的其他常用交叉驗證方法。為此，理論上研究了基于組塊3×2交叉驗證的F1度量的方差。方差的結(jié)構(gòu)表明它由塊方差、塊內(nèi)協(xié)方差和塊間協(xié)方差三部分組成，從而說明了廣泛使用的樣本方差估計可能嚴(yán)重地低估或高估真實(shí)的方差。通過條形圖方法在模擬和真實(shí)數(shù)據(jù)上進(jìn)行實(shí)驗，驗證了上述理論結(jié)果，實(shí)驗結(jié)果表明塊內(nèi)、塊間協(xié)方差和塊方差是同階的，塊內(nèi)和塊間相關(guān)性是不可忽略的。

關(guān)鍵詞：F1度量；交叉驗證；方差；分類算法；模擬實(shí)驗

1　引言

在諸如自然語言處理的統(tǒng)計機(jī)器學(xué)習(xí)應(yīng)用中，F(xiàn)1度量是分類算法性能度量的最常用指標(biāo)之一。在一篇典型的統(tǒng)計學(xué)習(xí)文章中，新提出的算法相對于以前已經(jīng)存在的算法F1值上有些許的提高，就被作者聲稱他們的方法優(yōu)于其他方法，但這些許的提高極有可能是由隨機(jī)誤差導(dǎo)致的。因此，為了得到統(tǒng)計可信的結(jié)論，需要借助于統(tǒng)計顯著性檢驗（置信區(qū)間）來判定它顯著與否。為了減小隨機(jī)性的影響，基于各種交叉驗證的統(tǒng)計檢驗方法被提出，其中最廣泛使用的基于標(biāo)準(zhǔn)K折交叉驗證和RLT交叉驗證的t檢驗方法已經(jīng)在許多文獻(xiàn)中被研究[1-5]。文獻(xiàn)[6]指出傳統(tǒng)的標(biāo)準(zhǔn)K折交叉驗證由于訓(xùn)練集中訓(xùn)練樣本重疊，常常導(dǎo)致其方差被低估，進(jìn)而影響檢驗性能，為此，他們提出了基于2折交叉驗證5次重復(fù)的5×2交叉驗證t檢驗方法。在此基礎(chǔ)上，文獻(xiàn)[7-8]提出了用于兩個分類算法性能對照的更穩(wěn)健的聯(lián)合5×2交叉驗證F檢驗和t檢驗。然而，無論是5×2交叉驗證F檢驗還是t檢驗，都是直接基于2折交叉驗證的5次獨(dú)立重復(fù)實(shí)驗進(jìn)行的，但實(shí)際上無論怎樣劃分?jǐn)?shù)據(jù)，得到的訓(xùn)練集之間都包含有相同的樣本，即它們之間實(shí)際上是不獨(dú)立的。這樣，5×2交叉驗證中的獨(dú)立性假定將導(dǎo)致5×2交叉驗證F檢驗和t檢驗中的樣本方差（嚴(yán)重）低估它們的真實(shí)方差，從而導(dǎo)致得到的檢驗是激進(jìn)的（liberal），即此檢驗由于過于自信可能容易導(dǎo)致錯誤的結(jié)論。特別地，文獻(xiàn)[9]指出5×2交叉驗證F檢驗和t檢驗由于其5次重復(fù)的訓(xùn)練和測試樣本重疊個數(shù)不同而無法進(jìn)行方差的理論分析，從而導(dǎo)致方差估計，以及進(jìn)一步的假設(shè)檢驗比較困難，為此他們提出了具有相同重疊樣本個數(shù)的組塊3×2交叉驗證的組塊3×2交叉驗證t檢驗。

然而，上述用于算法性能對照的統(tǒng)計檢驗方法都是基于損失函數(shù)的，本文考慮把組塊3×2交叉驗證應(yīng)用于F1度量。因為在自然語言處理中，真實(shí)的語料庫往往比較小，并且為了減小隨機(jī)誤差，基于交叉驗證的方法常常被用于F1度量的推斷。又文獻(xiàn)[9-11]理論和實(shí)驗驗證了組塊3×2交叉驗證方法優(yōu)于K折交叉驗證和5×2交叉驗證，為此考慮把組塊3×2交叉驗證方法應(yīng)用于F1度量。為了得到可信的統(tǒng)計顯著性檢驗或置信區(qū)間，必須對它的方差進(jìn)行分析。這樣，本文研究了基于組塊3×2交叉驗證的F1度量的方差。方差的結(jié)構(gòu)表明，廣泛使用的樣本方差估計可能嚴(yán)重地低估或高估真實(shí)的方差，并通過模擬實(shí)驗進(jìn)行了驗證。

2　性能的度量

在統(tǒng)計學(xué)習(xí)的研究中，有多個度量分類算法性能的指標(biāo)，包括泛化誤差、錯誤率、精確率、準(zhǔn)確率（precision）、召回率（recall）、F得分、ROC（receiver operating characteristics）曲線，AUC（area under the ROC curve）等[1,12-14]。本文關(guān)注于基于準(zhǔn)確率和召回率調(diào)和平均的F1值度量，它是F得分的一種特殊情形。

2.1標(biāo)準(zhǔn)的F1度量

不失一般性，本文僅考慮簡單的兩類分類問題，每個系統(tǒng)都包含兩個類別標(biāo)簽，用于標(biāo)示樣本的正例和負(fù)例。分類算法依據(jù)給定的輸入給出一個預(yù)測，通過對照預(yù)測和系統(tǒng)的真實(shí)類別標(biāo)簽，可以給出如下的一個2×2混淆矩陣。

表1中，TP（true positives）表示真實(shí)正例樣本被正確分類為正例樣本的數(shù)目；TN（true negatives）表示真實(shí)負(fù)例樣本被正確分類為負(fù)例樣本的數(shù)目；FP （false positives）表示真實(shí)負(fù)例樣本被錯誤分類為正例樣本的數(shù)目；FN（false negatives）表示真實(shí)正例樣本被錯誤分類為負(fù)例樣本的數(shù)目?；诘玫降腡P、TN、FP和FN，可以計算準(zhǔn)確率p和召回率r：

為了綜合評價準(zhǔn)確率和召回率，文獻(xiàn)中提出了如下的F1度量，它定義為準(zhǔn)確率和召回率的調(diào)和平均：

Table 1　Confusion matrix表1混淆矩陣

2.2基于組塊3×2交叉驗證的F1度量

為了檢驗算法之間性能差異的顯著性，文獻(xiàn)[6-8]提出了一個基于損失函數(shù)的隨機(jī)5×2交叉驗證方法，并通過模擬實(shí)驗驗證了它的性能優(yōu)于常用的10折交叉驗證方法。

具體地，數(shù)據(jù)集D={z1,z2,…,zn},zi=(xi,yi)∈Z是從分布P中獨(dú)立抽樣得到的，xi是輸入向量，yi是輸出變量。首先，數(shù)據(jù)集D被分成容量（大致）相等的不相交的兩部分，重復(fù)這樣的劃分5次，得到的訓(xùn)練和測試集分別被記為,i=1,2,…,5,k=1,2。這樣，基于隨機(jī)5×2交叉驗證的F1度量可以寫為：

k,i=1,2,…,5, k=1,2,是互為訓(xùn)練和測試集的，因此,i=1,2,…,5。然而，文獻(xiàn)[9]指出隨機(jī)5×2交叉驗證的方差的精確理論表達(dá)式不能得到，從而導(dǎo)致其方差估計，以及進(jìn)一步的假設(shè)檢驗比較困難。并且他們指出任意兩個2折交叉驗證之間的協(xié)方差和訓(xùn)練集之間的重疊樣本個數(shù)有關(guān)，在n/4時達(dá)到最小，見圖1。

Fig.1　Covariance curve as the change of the number of overlapped sample圖1　隨著重疊樣本個數(shù)變化的協(xié)方差曲線

接著，他們提出了具有相同重疊樣本個數(shù)（均為n/4）的泛化誤差的組塊3×2交叉驗證估計，本文把它應(yīng)用于F1度量。這樣，基于組塊3×2交叉驗證的F1度量被定義為3組2折交叉驗證的F1得分的平均：

3　組塊3×2交叉驗證的F1度量的方差結(jié)構(gòu)

鑒于組塊3×2交叉驗證是3組2折交叉驗證的平均結(jié)果，那么由方差和的方差公式知，組塊3×2交叉驗證的方差具有如下形式：

引理1[3,9]基于組塊3×2交叉驗證的F1度量的協(xié)方差矩陣具有如下簡單形式：

引理2[2,9]令U1,U2,…,UK為均值E(Uk)=β，方差Var(Uk)=Δ，協(xié)方差Cov(Uk,Uk′)=γ,k≠k′,k,k′=1,2,…, K的隨機(jī)變量，π=γ/Δ為Uk和Uk′的相關(guān)系數(shù)，分別為樣本均值和樣本方差，那么

（2）如果對所有的K上述協(xié)方差結(jié)構(gòu)都成立，即γ和Δ不依賴于K，則γ≠0；

i≠i′,k=k′或者k≠k′,i,i′=1,2,3,k,k′=1,2。

證明 由引理1和引理2知：

對任意i≠i′，有：

因此，基于引理2：

4　模擬實(shí)驗

實(shí)驗1模擬數(shù)據(jù)的兩類分類實(shí)驗。

考慮兩類分類問題：X=(X1,X2,…,Xp)為p維輸入向量（特征向量），Y={0,1}表示二元響應(yīng)變量，實(shí)驗?zāi)康臑橥ㄟ^這p個特征變量來構(gòu)造分類器對類別0和1進(jìn)行分類。特別地，假定兩類取值的概率相同，即P(Y=1)=P(Y=0)=1/2，在響應(yīng)變量Y條件下特征變量X服從正態(tài)分布，即X|Y=0～N(0,I30),X|Y=1～N (1,2I30),N(Normal)表示正態(tài)分布，I30表示30×30的單位矩陣。分別用如下4個分類器進(jìn)行分類，考察在樣本量分別為n=40,80,160,200,400,800,1 200, 1 600,2 000時組塊3×2交叉驗證的F1度量的方差以及它的三部分分量的變化。

（1）分類樹（classification trees，CT）分類器：把輸入（特征）空間劃分為一系列的區(qū)域，形成一個樹狀結(jié)構(gòu)，在每個區(qū)域擬合一個簡單模型，然后基于某個準(zhǔn)則（如誤分類誤差）進(jìn)行分類。

（2）最近鄰（nearest neighbour，NN）分類器：尋找訓(xùn)練集在輸入空間中最鄰近待考查樣本的K個樣本點(diǎn)，通過這K個點(diǎn)的投票實(shí)現(xiàn)分類。

（3）樸素貝葉斯（na?ve Bayes，NB）分類器：假定特征空間中各特征之間是獨(dú)立的，由各特征的類條件邊緣密度的乘積近似各類條件密度，然后使用貝葉斯定理進(jìn)行分類。

（4）支持向量機(jī)（suport vector machine，SVM）分類器：通過基展開（核函數(shù)）對原始特征進(jìn)行變換來擴(kuò)大特征空間，然后在擴(kuò)大的特征空間上構(gòu)造最優(yōu)分類超平面實(shí)現(xiàn)分類。

由圖2～圖5可以看到，組內(nèi)協(xié)方差ω有相對較小的影響，但組間協(xié)方差γ對方差的貢獻(xiàn)是和σ2同階的，甚至更大。實(shí)際上，隨著樣本容量的變化，σ2對總方差的解釋僅占到30%～40%。這個實(shí)驗也驗證了在F1度量上有與損失函數(shù)度量相同的結(jié)論：當(dāng)考慮組塊3×2交叉驗證的F1度量的方差時，組間的相關(guān)性不能被忽略。為了進(jìn)一步驗證這個結(jié)論，給出了在真實(shí)letter數(shù)據(jù)集上多個分類器和多個樣本量下組內(nèi)和組間相關(guān)性ρ1和ρ2的變化。

實(shí)驗2真實(shí)letter數(shù)據(jù)集上的分類實(shí)驗。

letter數(shù)據(jù)集包含20 000個樣本，16個特征變量，響應(yīng)變量Y是26個羅馬字母，實(shí)驗的目的就是通過這16個特征變量來對26個羅馬字母進(jìn)行分類[15]。為了簡化這個分類問題，類似于文獻(xiàn)[2]，把它轉(zhuǎn)化為一個二類分類問題：A～M為一類，N～Z為另一類。與模擬數(shù)據(jù)類似，在樣本量 n=40,80,160,200,400, 800,1 200,1 600,2 000時，采用分類樹（CT）、最近鄰（NN）、樸素貝葉斯（NB）、支持向量機(jī)（SVM）分類器進(jìn)行ρ1和ρ2真值的模擬。

Fig.2　Bar chart with different sample sizes for CT classifier圖2　CT分類器各樣本量下的條形圖

Fig.3　Bar chart with different sample sizes for NN classifier圖3　NN分類器各樣本量下的條形圖

Fig.4　Bar chart with different sample sizes for NB classifier圖4　NB分類器各樣本量下的條形圖

Fig.5　Bar chart with different sample sizes for SVM classifier圖5SVM分類器各樣本量下的條形圖

由表2和表3可以看到，對所有的分類器，隨著樣本量的增加，組內(nèi)相關(guān)性ρ1逐漸減小，組間相關(guān)性ρ2趨于某一個穩(wěn)定值，這和文獻(xiàn)[9]基于損失函數(shù)得出的結(jié)論是一致的。例如，在分類樹分類器下，隨著樣本量增加到2 000，ρ1已經(jīng)趨于一個接近于0的值0.007。在除了SVM的其他3個分類器下，ρ2都穩(wěn)定在一個小于0.4的范圍內(nèi)，對于SVM分類器，在樣本量為800和1 600時，ρ2超過了0.4但也小于0.5。這些都進(jìn)一步說明了在考慮組塊3×2交叉驗證的方差時，ρ1和 ρ2不能被忽略，尤其是組間的相關(guān)性。特別注意的是，在NB分類器下產(chǎn)生了負(fù)的組內(nèi)相關(guān)性，像引理2指出的那樣，它可能是因為協(xié)方差和K的選取有關(guān)導(dǎo)致的，但在此沒辦法進(jìn)行進(jìn)一步的分析，因為這里的K是固定的，等于3。其中λ1=1-

Table 2　True values ofρ1andρ2with CT and NN classifiers表2　CT和NN分類器下ρ1和ρ2的真值

文獻(xiàn)中，常常通過樣本方差來進(jìn)行方差的估計。但是，在此如果使用假定組內(nèi)和組間相關(guān)性全為0時的樣本方差

和文獻(xiàn)[6-8]中假定組間相關(guān)性為0時的樣本方差來估計Var(μ?3×2)的話，將導(dǎo)致比較大的偏差。

Table 3　True values ofρ1andρ2with NB and SVM classifiers表3　NB和SVM分類器下ρ1和ρ2的真值

由表4和表5可以看到，在所有樣本量和分類器下，λ1都是λ2的1.5倍到3倍。這表明樣本方差估計有較大的偏差，但它是方差的一個保守估計。相對于λ1，λ3雖然有和λ2一樣較小的偏差，但在一些情形下，將導(dǎo)致的激進(jìn)估計，從而導(dǎo)致獲得錯誤的結(jié)論。但無論是樣本方差估計還是作為的估計，都有比較大的偏差，因此為了進(jìn)行下一步的統(tǒng)計推斷需要構(gòu)造更合適的方差估計。

5　結(jié)束語

本文分析了基于組塊3×2交叉驗證的F1度量的方差，結(jié)果表明它可以簡化隨機(jī)3×2交叉驗證的方差為一個只包含三項協(xié)方差的組合形式。模擬實(shí)驗驗證了這個簡化的方差形式不能被進(jìn)一步地簡化，即組內(nèi)和組間協(xié)方差和方差是同階的，它們不能被忽略。

Table 4　Values ofλ1,λ2andλ3with CT and NN classifiers表4　CT和NN分類器下λ1、λ2和λ3的值

Table 5　Values ofλ1,λ2andλ3with NB and SVM classifiers表5　NB和SVM分類器下λ1、λ2和λ3的值

接下來，將研究組塊3×2交叉驗證的F1度量的方差估計問題，以及進(jìn)一步的假設(shè)檢驗和區(qū)間估計問題。

References:

[1]Hastie T,Tibshrani R,Friedman J.The elements of statistical learning:data mining,inference,and prediction[M]. Berlin:Springer,2001.

[2]Nadeau C,Bengio Y.Inference for the generalization error[J]. Machine Learning,2003,52(3):239-281.

[3]Bengio Y,Grandvalet Y.No unbiased estimator of variance of K-fold cross validation[J].Journal of Machine Learning Research,2004,5:1089-1105.

[4]Grandvalet Y,Bengio Y.Hypothesis testing for cross validation,Tech Rep 1285[R].Montreal,Canada:University of Montreal,2006.

[5]Markatou M,Tian H,Biswas S,et al.Analysis of variance of cross-validation estimators of the generalization error[J]. Journal of Machine Learning Research,2005,6(7):1127-1168.

[6]Diettetich T.Approximate statistical tests for comparing supervised classification learning algorithms[J].Neural Computation,1998,10(7):1895-1924.

[7]Alpaydin E.Combined 5×2 cv F test for comparing supervised classification learning algorithms[J].Neural Computation,1999,11(8):1885-1892.

[8]Yildiz O.Omnivariate rule induction using a novel pairwise statistical test[J].IEEE Transactions on Knowledge and Data Engineering,2013,25(9):2105-2118.

[9]Wang Yu,Wang Ruibo,Jia Huichen,et al.Blocked 3×2 cross-validated t-test for comparing supervised classification learning algorithms[J].Neural Computation,2014,26 (1):208-235.

[10]Wang Yu,Li Jihong,Li Yanfang.Measure for data partitioning in m×2 cross-validation[J].Pattern Recognition Letters, 2015,65(11):211-217.

[11]Wang Yu,Li Jihong,Li Yanfang,et al.Confidence interval for F1 measure of algorithm performance based on blocked3×2 cross-validation[J].IEEE Transactions on Knowledge and Data Engineering,2015,27(3):651-659.

[12]Fawcett T.An introduction to ROC analysis[J].Pattern Recognition Letters,2006,27(8):861-874.

[13]Lobo J,Jimenez V,Real R.AUC:a misleading measure of the performance of predictive distribution models[J].Global Ecology and Biogeography,2008,17(2):145-151.

[14]Goutte C,Gaussier E.A probabilistic interpretation of precision,recall and F-score,with implication for evaluation[C]// LNCS 3408:Proceedings of the 27th European Conference on IR Research,Santiago de Compostela,Spain,Mar 21-23,2005.Berlin,Heidelberg:Springer,2005:345-359.

[15]Frey P W,Slate D J.Letter recognition using holland-style adaptive classifiers[J].Machine Learning,1991,6(2):161-182.

YANG Liu was born in 1979.She received the M.S.degree in mathematical statistics from Shanxi University in 2006.Now she is a lecturer at Shanxi University of Finance&Economics.Her research interests include statistical machine learning,probability and statistics,etc.

楊柳（1979—），女，山西臨汾人，2006年于山西大學(xué)概率論與數(shù)理統(tǒng)計專業(yè)獲得碩士學(xué)位，現(xiàn)為山西財經(jīng)大學(xué)應(yīng)用數(shù)學(xué)學(xué)院講師，主要研究領(lǐng)域為統(tǒng)計機(jī)器學(xué)習(xí)，概率統(tǒng)計等。在國內(nèi)外多種學(xué)術(shù)期刊上發(fā)表論文10多篇。

WANG Yu was born in 1981.He received the M.S.degree in mathematical statistics from Shanxi University in 2006.Now he is a lecturer at Shanxi University.His research interests include statistical machine learning and data mining,etc.

王鈺（1981—），男，山西陽泉人，2006年于山西大學(xué)概率論與數(shù)理統(tǒng)計專業(yè)獲得碩士學(xué)位，現(xiàn)為山西大學(xué)軟件學(xué)院講師，主要研究領(lǐng)域為統(tǒng)計機(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘等。在國內(nèi)外多種學(xué)術(shù)期刊上發(fā)表論文20多篇，現(xiàn)主持國家自然科學(xué)基金項目一項，參與國家和省級基金項目多項。

*The National Natural Science Foundation of China under Grant Nos.61503228,71503151(國家自然科學(xué)基金). Received 2016-03,Accepted 2016-06.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-06-08,http://www.cnki.net/kcms/detail/11.5602.TP.20160608.0931.002.html

文獻(xiàn)標(biāo)志碼：A

中圖分類號：TP181

doi:10.3778/j.issn.1673-9418.1603082

Analysis of Variance of F1 Measure Based on Blocked 3×2 Cross Validation?

YANG Liu1+,WANG Yu2
1.School ofApplied Mathematics,Shanxi University of Finance&Economics,Taiyuan 030006,China
2.School of Software,Shanxi University,Taiyuan 030006,China
+Corresponding author:E-mail:yang_liu@sxu.edu.cn

Abstract:In the research on statistical machine learning,researchers often perform quantitative experiments to compare F1 measure of classification algorithms based on cross validation.In order to obtain statistically convincing conclusion,it is very important to estimate the uncertainty of F1 measure.In particular,the blocked 3×2 cross validation is demonstrated that its performance is superior to other cross validation methods such as the standard K-fold cross validation by theory and experiments.Thus,this paper studies theoretically the variance of F1 measure based on blocked 3×2 cross validation.The structure of variance shows that it is composed of three parts:block variance,within-block covariance and between-blocks covariance,which also implies that the commonly used sample variance may grossly underestimate or overestimate the real variance.The above theoretical results are validated by the experiments in simulated and real data sets through bar chart method.The experimental results show that the within-block covariance and between-blocks covariance are of same order as the block variance.The within-block and between-blocks correlations can not be neglected.

Key words:F1 measure;cross validation;variance;classification algorithm;simulated experiment