libsvm交叉驗證與網格搜索(參數選擇) – JAVA編程語言程序開發技術文章

首先說交叉驗證。


交叉驗證(Cross validation)是一種評估統計分析、機器學習算法對獨立於訓練數據的數據集的泛化能力(generalize), 能夠避免過擬合問題。
交叉驗證一般要盡量滿足:


1)訓練集的比例要足夠多,一般大於一半
2)訓練集和測試集要均勻抽樣


交叉驗證主要分成以下幾類:
1)Double cross-validation
Double cross-validation也稱2-fold cross-validation(2-CV),作法是將數據集分成兩個相等大小的子集,進行兩回合的分類器訓練。在第一回合中,一個子集作為訓練集,另一個作為測試集;在第二回合中,則將訓練集與測試集對換後,再次訓練分類器,而其中我們比較關心的是兩次測試集的識別率。不過在實際中2-CV並不常用,主要原因是訓練集樣本數太少,通常不足以代表母體樣本的分佈,導致測試階段識別率容易出現明顯落差。此外,2-CV中子集的變異度大,往往無法達到「實驗過程必須可以被復制」的要求。


2)k-folder cross-validation(k折交叉驗證)
K-fold cross-validation (k-CV)則是Double cross-validation的延伸,做法是將數據集分成k個子集,每個子集均做一次測試集,其餘的作為訓練集。k-CV交叉驗證重復k次,每次選擇一個子集作為測試集,並將k次的平均交叉驗證識別率作為結果。
優點:所有的樣本都被作為瞭訓練集和測試集,每個樣本都被驗證一次。10-folder通常被使用。


3)leave-one-out cross-validation(LOOCV留一驗證法)
假設數據集中有n個樣本,那LOOCV也就是n-CV,意思是每個樣本單獨作為一次測試集,剩餘n-1個樣本則做為訓練集。
優點:
1)每一回合中幾乎所有的樣本皆用於訓練model,因此最接近母體樣本的分佈,估測所得的generalization error比較可靠。 因此在實驗數據集樣本較少時,可以考慮使用LOOCV。
2)實驗過程中沒有隨機因素會影響實驗數據,確保實驗過程是可以被復制的。
但LOOCV的缺點則是計算成本高,為需要建立的models數量與總樣本數量相同,當總樣本數量相當多時,LOOCV在實作上便有困難,除非每次訓練model的速度很快,或是可以用平行化計算減少計算所需的時間。


libsvm提供瞭 void svm_cross_validation(const struct svm_problem *prob, const struct svm_parameter *param, int nr_fold, double *target)方法,參數含義如下:


prob:待解決的分類問題,就是樣本數據。


param:svm訓練參數。


nr_fold:顧名思義就是k折交叉驗證中的k,如果k=n的話就是留一法瞭。


target:預測值,如果是分類問題的話就是類別標簽瞭。


 


然後我們討論下參數選擇。


使用svm,無論是libsvm還是svmlight,都需要對參數進行設置。以RBF核為例,在《A Practical Guide to Support Vector Classi cation》一文中作者提到在RBF核中有2個參數:C和g。對於一個給定的問題,我們事先不知道C和g取多少最優,因此我們要進行模型選擇(參數搜索)。這樣做的目標是找到好的(C, g)參數對,使得分類器能夠精確地預測未知的數據,比如測試集。需要註意的是在在訓練集上追求高精確度可能是沒用的(意指泛化能力)。根據前一部分所說的,衡量泛化能力要用到交叉驗證。


在文章中作者推薦使用“網格搜索”來尋找最優的C和g。所謂的網格搜索就是嘗試各種可能的(C, g)對值,然後進行交叉驗證,找出使交叉驗證精確度最高的(C, g)對。“網格搜索”的方法很直觀但是看起來有些原始。事實上有許多高級的算法,比如可以使用一些近似算法或啟發式的搜索來降低復雜度。但是我們傾向於使用“網格搜索”這一簡單的方法:


1)從心理上講,不進行全面的參數搜索而是使用近似算法或啟發式算法讓人感覺不安全。


2)如果參數比較少,“網格搜索”的復雜度比高級算法高不瞭多少。


3)“網格搜索”可並行性高,因為每個(C, g)對是相互獨立的。


說瞭那麼大半天,其實“網格搜索”就是n層循環,n是參數個數,仍然以RBF核為例,編程實現如下:


for(double c=c_begin;c<c_end;c+=c_step)
        {
            for(double g=g_begin;g<g_end;g+=g_step)
            {


                      //這裡進行交叉驗證,計算精確度。


           }


        }


通過上述兩層循環找到最優的C和g就可以瞭。


附錄:


使用Cross-Validation時常犯的錯誤


由於實驗室許多研究都有用到evolutionary algorithms(EA)與classifiers,所使用的fitness function中通常都有用到classifier的辨識率,然而把cross-validation用錯的案例還不少。前面說過,隻有training data才可以用於model的建構,所以隻有training data的辨識率才可以用在fitness function中。而EA是訓練過程用來調整model最佳參數的方法,所以隻有在EA結束演化後,model參數已經固定瞭,這時候才可以使用test data。(當然如果想造假的話就把測試集的數據參與進模型訓練,這樣得到的模型效果多少會好些,因為模型本身已經包含瞭測試集的先驗知識,測試集對它來說不再是未知數據。)


那EA跟cross-validation要如何搭配呢?Cross-validation的本質是用來估測(estimate)某個classification method對一組dataset的generalization error,不是用來設計classifier的方法,所以cross-validation不能用在EA的fitness function中,因為與fitness function有關的樣本都屬於training set,那試問哪些樣本才是test set呢?如果某個fitness function中用瞭cross-validation的training或test辨識率,那麼這樣的實驗方法已經不能稱為 cross-validation瞭。


EA與k-CV正確的搭配方法,是將dataset分成k等份的subsets後,每次取1份 subset作為test set,其餘k-1份作為training set,並且將該組training set套用到EA的fitness function計算中(至於該training set如何進一步利用則沒有限制)。因此,正確的k-CV 會進行共k次的EA演化,建立k個classifiers。而k-CV的test辨識率,則是k組test sets對應到EA訓練所得的k個classifiers辨識率之平均值。


參考鏈接:


http://blog.sina.com.cn/s/blog_4998f4be0100awon.html


http://www.shamoxia.com/html/y2010/2245.html


http://fuliang.javaeye.com/blog/769440

You May Also Like