2023年隨機(jī)森林實驗報告

隨機(jī)森林實驗報告實驗?zāi)康膶崿F(xiàn)隨機(jī)森林模型并測試。實驗問題Kaggle第二次作業(yè)Non-linearclassification算法分析與設(shè)計一.算法設(shè)計背景：.隨機(jī)森林的原子分類器一般使用決策樹，決策樹又分為擬合樹和分類樹。這兩者的區(qū)別在于代價估值函數(shù)的不同。.根據(jù)經(jīng)驗，用擬合樹做分類的效果比分類樹略好。.對于一個N分類問題,它總是可以被分解為N個2分類問題，這樣分解的好處是其決策樹更加方便構(gòu)造，更加簡樸，且更加有助于用擬合樹來構(gòu)建分類樹。對于每一個2分類問題，構(gòu)造的樹又叫CART樹，它是一顆二叉樹。.將N個2分類樹的結(jié)果進(jìn)行匯總即可以得到多分類的結(jié)果。.CART樹構(gòu)造:trace.pusn(u);〃樹的初始化(插入頭節(jié)點(diǎn))完成后，正式開始決策樹的構(gòu)建while(!trace.empty()){intcurrent_node=trace.topO；trace.popQ;intcontainer[2]={0};(*Tree).getPartition(current_node,container);〃判斷當(dāng)前節(jié)點(diǎn)是否成功分割if(container[0]!=-1){trace.push(container[l]);trace.push(container[0]);}}〃訓(xùn)練完成，計算輸出下面再重點(diǎn)說一下函數(shù):booldecisionTree::getPartition(intindex,intcontainer[2]){這個函數(shù)是單棵決策樹構(gòu)造的核心，調(diào)用這個函數(shù)，假如當(dāng)前節(jié)點(diǎn)的Gini值己經(jīng)為0,那么這個函數(shù)會計算當(dāng)前節(jié)點(diǎn)的擬合值：if(Nodes[index].gini==0||Nodes[index].layer>=MaxLayerNum/*||/4Nodes[index].dataSet.sizeO<10*/){Nodes[mdex].isLeaf=1;〃計籟葉子節(jié)點(diǎn)的擬合值doublesum=0;for(inti=0;i<Nodes[index].datalndex.size();++i){sum?=trainOut[Node$(index].dataIndexIi]];//Node$[index].res[ii}Node$[mdex].value=sum/Node$[index].dataIndex.$izeO；containerfO]=container[l]=-1;returnfalse;d-結(jié)束條件是gini==0||層數(shù)等于10假如當(dāng)前節(jié)點(diǎn)不滿足結(jié)束分割條件，那么函數(shù)將對屬性進(jìn)行抽樣，抽樣的方法是打亂后取前se1ectedColumns列。然后調(diào)用getNodeA11r(s,index)獲取當(dāng)前節(jié)點(diǎn)的備選分割值，這里的s是抽取的屬性的列號的集合?！ǐ@得打亂后的索引，并選取前面的25個作為選取的列的索引，傳遞給getAttr,獲得所需要的分割值vector<pairl>sequence(numparametres-2);srand((unsigned)time(NULL));for(i=0;i<sequencesizeQ;++i){sequence[i].index=i;sequence(i).value=rand();)std::sort(sequence.begin()rsequence.endO.cmp);vector<int>s(SelectedColumns);for(inti=0;i<SelectedColumns;++i){s(i]=sequence[i].index;在得到備選的屬性分割值后，將進(jìn)入循環(huán)，尋找最優(yōu)分割點(diǎn)for(i=0;i<SelectedColumns;++i){vector<double>::iteratorcursorfor(cursor=Nodes[index].attributes[ij.beginO；cursor!=Nodes(index].attributes[i].endO；??cursor){temp_gini=computeGini(index,s(ij,"cursor);if(min_gini>temp_gini){min_gini=temp_gini;par_label=s[i];par_value=*cursor;.最終結(jié)果計算在main函數(shù)中，我們將四個線程所得的transformOutT相加,最后遍歷取每一行最大值的下標(biāo),即可得到最終結(jié)果。六.算法優(yōu)化.應(yīng)用了數(shù)組+校建樹取代了普通的函數(shù)遞歸建樹，加快了建樹速度。.在傳遞每個節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)據(jù)集時，使用了傳遞數(shù)據(jù)集的索引而非數(shù)據(jù)自身，這樣做的好處是，本來假如傳遞?條數(shù)據(jù)需要復(fù)制617個double類型的數(shù)量，而現(xiàn)在只需要傳遞?個Ini型的索引，這種快了617倍的數(shù)據(jù)集傳遞方式使程序運(yùn)營效率提高了10倍以上。.在每個屬性中選擇備選分割值的時候，采用了一種下采樣的策略。即：假如該節(jié)點(diǎn)的數(shù)據(jù)集大小小于某一數(shù)值，則將這個數(shù)據(jù)集的這個屬性的所有值都納入候選分割值列表。但是假如大于了這個閾值，則將屬性所相應(yīng)的列進(jìn)行排序后再進(jìn)行等間距采樣得到樣本數(shù)等于閾值的子集作為候選分割集。代碼詳見getPartition().這樣做的好處是需要計算的分割gini值大大減少了(本人取的采樣閾值時100,相比原數(shù)據(jù)集，樣本空間縮小了盡30倍)，這里也再一次加速了程序運(yùn)營。但是這個優(yōu)化隨機(jī)而來的?個問題是：有也許每次分割都不是最佳分割。.使用了C++I1的vihread＞庫進(jìn)行了并行實現(xiàn)，開出4個線程，程序相比單線程加速了4倍。七.并行實現(xiàn)C++11〈thread〉庫創(chuàng)建線程，為每個線程賦予獨(dú)立的數(shù)據(jù)容器，并將隨機(jī)森林提成等量的4部分（由于我使用的是4個線程）。即,每個線程中執(zhí)行的函數(shù)承擔(dān)1/4規(guī)模的隨機(jī)森林的構(gòu)造，實現(xiàn)代碼如下:threatthreadl(mainInThread.transformOutPerTimeTl,trainlnPerTimeTl,tran$formTe$tOutTl,&Treel);threadthread2(mainInThread,transformOutPerTimeT2,trainInPerTimeT2,transformTestOutT2,&Tree2);threat：thread3(mainInThread,transformOutPerTimeT3,trainInPerTimeT3,transformTestOutT3,&Tree3);threadthread4(mainInThread,transformOutPerTimeT4,trainInPerTimeT4,transformTestOutT4,&Tree4);threadl.join();thread2.join();thread3.join();thread4.join();intmainInThread(inttransformOutPerTime_[][type$Num+1].doubletrainInPerTime_l][numparametres-2],doubletransformTestOut[]/廉財?shù)厝肟趂or(inttimes=0;times<ForestSize/4;times++){最后將4個線程得到的結(jié)果累加再做轉(zhuǎn)換即可得到最終結(jié)果。r(inti=0;i<testsetNum;++i)(for(intj=0;j<typesNum+1;++j){tran$formTestOut(i](fltransform!estOutTl[i](j]?transformTe$tOutT2[i](j]?transformTestOutT3[i](j]?tran$formTe$tOutT4[i][j);)八.測試結(jié)果樹的數(shù)量每輪Train樣本決策樹最大層數(shù)分割備選屬性數(shù)每個屬性采樣數(shù)運(yùn)營時間準(zhǔn)確率260312972001001.7min0.926003129720010017min0.9432600031297200100170min九.并行效率對比十.總結(jié)本次實驗，我們構(gòu)造了決策樹以及隨機(jī)森林，構(gòu)造基本模型我用了一天時間，但是構(gòu)造出來的模型面臨著執(zhí)行速度很慢的瓶頸。其因素在于（1）沒有對屬性列進(jìn)行采樣（2）沒有在選取每一列的時候?qū)@一列的值進(jìn)行采樣（3）在構(gòu)造決策樹子節(jié)點(diǎn)的時候傳遞的是數(shù)據(jù)集而不是索引，這導(dǎo)致我的決策樹雖然是對的的，但是幾乎一分鐘才干構(gòu)造一棵CART,這樣的CART要用來構(gòu)造隨機(jī)森林幾乎是不也許的事情（時間上存在很大瓶頸），然后我逐個針對這些問題進(jìn)行了優(yōu)化，例如傳遞數(shù)據(jù)集采用的是索引,對屬性及屬性集采樣等等。此外，在構(gòu)造決策樹時，我發(fā)現(xiàn)雖然屬性列很多，但往往取很少的列，很少的層，較少的分割節(jié)點(diǎn)同樣能取到比較好的效果，這對于速度提高的方面是有良好的指導(dǎo)意義的。此外決策樹本質(zhì)上是做折線函數(shù)擬合，因此，過擬合是存在的，這就意味著決策樹單棵假如層數(shù)過高效果將會非常不好，這一點(diǎn)也在KAGGLE的結(jié)果上體現(xiàn)了，過擬合仍然是隨機(jī)森林面臨的挑戰(zhàn)。并且粗略的了解了一下C++的多線程，多線程可以充足調(diào)用起CPU資源，速度加快了很多,是以后實現(xiàn)算法時需要考慮的方向。輸入：訓(xùn)練數(shù)據(jù)集D,停止訓(xùn)練條件輸出：CART決策樹根據(jù)訓(xùn)練數(shù)據(jù)集，從根節(jié)點(diǎn)開始，遞歸地對每個節(jié)點(diǎn)進(jìn)行以下操作，遞歸構(gòu)造二叉決策樹(1)設(shè)節(jié)點(diǎn)的訓(xùn)練數(shù)據(jù)集為D,計算現(xiàn)有特征對該數(shù)據(jù)集的基尼系數(shù)，此時，對每一個特征A,對于每一個可能的劃分值a,根據(jù)大于a及小于等于a將訓(xùn)練數(shù)據(jù)集分成DI,D2兩部分。計算gini系數(shù)公式如下：Giniseparate=胃*Gini(Dl)+仲Gini(D2);Gini(D)=1-ENiP力(2)在所有可能特征A以及其所有可能劃分點(diǎn)a中，選擇gini系數(shù)最小的特征及切分值，將D1和D2分配到左右兩個子節(jié)點(diǎn)去。(3)對左右節(jié)點(diǎn)分別遞歸的調(diào)用(1),(2),直到滿足一定條件為止。6.隨機(jī)森林構(gòu)造：(1)隨機(jī)取樣，降低樹與樹之間的關(guān)聯(lián)性RF在每次構(gòu)造一棵決策樹時，先隨機(jī)的有放回的從訓(xùn)練集中抽取(60%)或n(sizeoftrainingset)個樣本D,在每個節(jié)點(diǎn)分裂前，先隨機(jī)從總共M個特征中選取m個(m?M,一般取根號M)作為分裂用的候選特征，這有效降低了樹與樹之間的關(guān)聯(lián)性。二.算法思緒：將一個N分類問題轉(zhuǎn)化為N個二分類問題。轉(zhuǎn)化方法是:構(gòu)造N棵二叉擬合樹，這里假設(shè)N為26,然后我們給N棵二叉樹依次標(biāo)號為1,2,3...26。1號樹的結(jié)果相應(yīng)于該條記錄是不是屬于第一類，是則輸出1,否則輸出0.2號樹的結(jié)果相應(yīng)于該條記錄是不是屬于第二類，是則1否則0,依此類推。這樣,我們的26棵二叉樹的結(jié)果就相應(yīng)了26個下標(biāo)。例如對于某條記錄，這26個二叉樹的結(jié)果按序號排列為{0,00,0,0,0,0,0,0,0.0.0,0,0,0,...1,0},那么這條記錄的分類應(yīng)當(dāng)為25。要將一個26維的0,1序列變回一個索引，我們只需要找出這個序列中值最大的元素的索引，這個索引即是序列號。我們將上面的26棵分別對26個索引做是否判斷的二分類樹視為一個整體，在多線程的環(huán)境下，構(gòu)造多個這樣的整體，然后進(jìn)行求和運(yùn)算，最后取出每個結(jié)果序列中值最大的元素的下標(biāo)作為分類值，那么久得到了我們想要的結(jié)果，隨機(jī)森林完畢。三.算法流程：.讀入訓(xùn)練集trainset,測試集testset.將訓(xùn)練集分割為輸入trainIn,輸出trainOut.這里假設(shè)類別數(shù)N為26,將trainOui[記錄條數(shù)]映射為transformTrainOu([訓(xùn)練記錄數(shù)][26].初始化transformTeslOut[測試記錄數(shù)][26]所有為0.Fori=1:ForcstSize://對訓(xùn)練集采樣，這里要注意輸入和輸出一致[samp1eln,transformSampleOut]=TakeSample(trainIn,transforrnTrainOut)Forcategory=1：26：//CartTrce數(shù)組存放著26棵二分類樹CartTree[calegory]=TrainCar(Tree(sampleln,transformSampleOut);end//transformTest0ut[測試記錄數(shù)][26]為承接二分類樹輸出的容器foril=I:testSetNum：Forcategory=1:26:transformTestOut[il][categoryJ+=predict(CartTreelcategory],testset[il])endEndEnd6.遍歷transformTrainOut[],將其每?行的最大值的下標(biāo)作為該行記錄的索引值。四.決策樹及隨機(jī)森林的配置.決策樹在這里，我們每一次26分類是由26棵CART共同完畢的,CART的costfunclion采用的是gini系數(shù)，CART的最大層數(shù)為7,分裂停止條件為當(dāng)前節(jié)點(diǎn)GINI為?；蛘弋?dāng)前節(jié)點(diǎn)所在層數(shù)到達(dá)了7..隨機(jī)森林a.隨機(jī)森林每次循環(huán)的訓(xùn)練集采樣為原訓(xùn)練集的b.對于森林中每一棵決策樹每一次分割點(diǎn)的選取，對屬性進(jìn)行了打亂抽樣，抽樣數(shù)為25,即每次分割只在25個屬性中尋找最合適的值。并且對于每個選取的屬性，我們進(jìn)行了行采樣。即假如這個屬性所擁有的屬性值數(shù)大于30,我們選取其中30個作為分割候選,假如小于30,則所有納入分割候選。五.代碼詳解1.訓(xùn)練集/測試集的讀入a.在dataDefine.h中定義了:9definenumparametres619//619〃￡錄中的字段與數(shù)#definetrainsetNum6239//100〃訓(xùn)練隼的記錄朝RffdefinetestsetNum1560//100#definetypesNum26//26〃類型數(shù)?^definenodesNum200//200訓(xùn)練集記錄列數(shù)numparamctrcs(ID(1)+參數(shù)數(shù)量(617)+輸出(1)=619)訓(xùn)練集記錄條數(shù)transetNum測試集記錄條數(shù)tcstsetNum分類類型數(shù)typesNum而在main.cpp中，我們聲明了全局變量doubletrainIn[trainsetNum][numparametres-2];〃訓(xùn)doubletrainOut[trainsetNum][l];.〃訓(xùn)隼集輸出?doubletestin(testsetNum][numparametres-2];//..IetestOut(te)inttrainID[trainsetNum];.intte$tiD[testsetNum];〃測試算每一行記錄的IDtrainin用于裝載訓(xùn)練集輸入，IrainOut用于裝載訓(xùn)練集的輸出（這里trainOut是二維數(shù)組是出于模型假如泛化，那么輸出值不一定只有一個的情況，在本次實驗中并未派上什么真正用場，可以將trainOut看作一個普通一維數(shù)組）。trainID用于裝載訓(xùn)練集中每一行的第一列ID號。lestIn,teslID則相應(yīng)測試集的輸入和ID號。這里注意，沒有l(wèi)eslOut的因素是測試集的結(jié)果理論上應(yīng)當(dāng)是不存在的。然后通過自己編寫的讀入函數(shù)readDataCtrainxsv","testcsv");讀入測試集合訓(xùn)練集，這個函數(shù)將分別裝載我們在前面提到的trainIn.trainOut、trainID>testIn.testID。這個函數(shù)使用的fstream逐行讀入的方法，這里不做詳述。.訓(xùn)練集輸出轉(zhuǎn)化為相應(yīng)的26維01數(shù)組transformOut[typesNum]在dataDefine.h中，我們定義了分類類別數(shù)typesNum:在main.cpp中,我們定義了全局變量transformOut[typesNum]inttransformOut[trainsetNum][typesNum+1]={0};//類別數(shù)這里的transformOut是用于儲存將trainOut每行的值映射為?行相應(yīng)的26維01序列后所產(chǎn)生的結(jié)果。這里面的相應(yīng)關(guān)系是：例如trainOut[10]中的值是13那么transformOut[10]]⑶=l,transformOut[l0][除13外其他列]=0;假如值是14,那么14列為1,其他列為0,行號代表的是它們相應(yīng)的是第幾條記錄;trainOutllO]和transforni0ut[l0J都表達(dá)的是第10行的分類值為某個值，只是表達(dá)方式不同。前者用數(shù)字表達(dá)，后者將相應(yīng)下標(biāo)的值置1表達(dá)。轉(zhuǎn)換接口由1。@in.cpp中的函數(shù)voidindexTransform(inttransformres[Ht.pesK+1],doubleogres[][l]);/戶弓啟始W出丫，化力Y」,”,定義,它的輸入?yún)?shù)依次為轉(zhuǎn)換輸出的承接容器transformres，盛放原始輸出的容器org它所做的事情是將transformresfi][orges[i]]的值置1.并行構(gòu)建隨機(jī)森林在main.cpp中，我們構(gòu)建了doubletrainInPerTime[perTimeNum][numparametres-2];doubletrainInPerTimeTl[perTimeNum][numparametres-2];doubletrainInPerTimeT2[perTimeNum][numparametres-2];doubletrainInPerTimeT3[perTimeNum][numparametres-2];doubletrainInPerTimeT4[perTimeNum][numparametres-2];inttransformOutPerTime[perTimeNum][typesNum+1]={0};inttransformOutPerTimeTl[perTimeNum][typesNum+1]={0};inttransformOutPerTimeT2(perTimeNum][typesNum+1]={0};inttransformOutPerTimeT3[perTimeNum][typesNum+1]={0};inttransformOutPerTimeT4[perTimeNum](typesNum+1]={0};doubletransformTestOutTl[testsetNum][typesNum+1]={0};doubletransformTestOutT2(testsetNum][typesNum+1]={0};doubletransformTestOutT3[testsetNum][typesNum+1]={0};doubletransformTestOutT4[testsetNum][typesNum+1]={0};trainInpefTime代表的是隨機(jī)森林算法中通過采樣環(huán)節(jié)后選取的訓(xùn)練輸入.TransformOutPerTime代表的是與trainInperTime相應(yīng)的轉(zhuǎn)換輸;||transformtestOut是承接本支線程的所有CART樹的決策值之和的結(jié)構(gòu)，這與算法思緒是相應(yīng)的，我們將所有CART樹的預(yù)測結(jié)果在意個轉(zhuǎn)換輸出容器上累加，然后對于每行取該行最大列的卜標(biāo)，即可得到由隨機(jī)森林得到的分類結(jié)果。我們可以看此這幾個變量都是只有最后的TX有區(qū)別，事實上，反復(fù)的創(chuàng)建相似的變量只是為了方便多線程操作不會沖突。多線程入口:

decisionTree&tasd=Treel;threadthreadl(mainInThread,transformOutPerTimeTl,trainlnPerTimeTl,transformTestOutTl,&Treel);threadthread2(mainInThread,transformOutPerTimeT2,trainIr?PerTimeT2,transformTestOutT2,&Tree2);threadthread3(mainInThread,transformOutPerTimeT3,trainInPerTimeT3,transformTestOutT3,&Tree3);threadthread4(mainInThread,transformOutPerTimeT4,trainInPerTimeT4,transformTestOutT4,&Tree4);這里使用的是C++11的〈thread〉庫，簡樸好用。每一個線程的隨機(jī)森林框架定義在main.cpp的每一個線程的隨機(jī)森林框架定義在main.cpp的這個函數(shù)采用循環(huán)的方式，每次循環(huán)，對訓(xùn)練集及相應(yīng)轉(zhuǎn)換輸出進(jìn)行打亂后采樣，然后輸入TRAIN(trainInPerTime_,transformOutPerTime_,transformTestOuCTree);中進(jìn)行一輪決策樹的訓(xùn)練,這一輪訓(xùn)練將會生成26棵CART樹，相應(yīng)26個分類值。這里輸入的參數(shù)Tree就是我們所用的決策樹容器，這里注意，我們一個線程中只需要公用一個決策樹結(jié)構(gòu)即足夠了.在訓(xùn)練完畢后，我們用ItransformTestOut[i][j]在訓(xùn)練完畢后，我們用ItransformTestOut[i][j]='累加訓(xùn)練結(jié)果。4一輪訓(xùn)練26棵樹由于26棵CART樹才干完整的等價于一棵26分類樹，因此我們將構(gòu)建這26棵CART樹的過程當(dāng)作是一個整體。這個過程由函數(shù)TRAIN(trainInPerTime_,transformOutPerTime_,transformTestOuCTree);實現(xiàn)。它的輸入依次是本輪的訓(xùn)練輸入（通過了卜.采樣，隨機(jī)森林規(guī)定的），相應(yīng)的轉(zhuǎn)換訓(xùn)練輸出，以及一個決策樹容器Tree。決策樹的定義我們將在下文中描述。這個函數(shù)有一個校stack<int>trace;〃用于追蹤樹的遍歷過程，這里我們假定用的是先根遍歷;并且有一個從1：26的循環(huán)for(inttypesN=1;typesN<=typesNum;typesN++){每次循環(huán)會建立一棵關(guān)于相應(yīng)的分類值得CART樹，CART樹的構(gòu)造是由棧trace維護(hù)的，trace維護(hù)的是一個先序的遍歷順序。當(dāng)循環(huán)完畢后，將會計算本輪的轉(zhuǎn)換輸出結(jié)果的變更:for(inti=0;i<testsetNum;++i){//testresPerTime[i][typesN]=TputeRes(testIn[i]);transformTestOut_[i][typesN]+=(*Tree).computeRes(testIn[i]);5.每科CART樹的構(gòu)造CART樹的數(shù)據(jù)結(jié)構(gòu)如下:structdecisionTree{doubletrainIn(perTimeNum][numparametres-2];inttrainOut[perTimeNum];nodeNodes[nodesNum];〃在建樹時需要使用的可用節(jié)點(diǎn)索引記錄intusableNode;trainIntrainOut相應(yīng)于輸入該樹的輸入輸出集,Nodes表達(dá)的是節(jié)點(diǎn)序列，在這里我們的樹的構(gòu)造使用的是數(shù)組，且樹的節(jié)點(diǎn)間的索引是通過索引值維護(hù)的，這顆樹非常緊密(假如只看NODES是看不出節(jié)點(diǎn)間的層級關(guān)系的)。它有如下成員函數(shù)：decisionTree。。；voidsetDecisionTree(doubletrainln_[][numparametres-2],inttrainOut」]);boolgetPartition(intindex,intcontainer。)；doublecomputeGini(intindex,intlabel,doublevalue);//doublecomputeNodeGini(intindex);〃計算某一節(jié)點(diǎn)的GinidoublecomputeRes(double[numparametres-2]);〃訓(xùn)練完成后,用于癡809函數(shù),輸入是窩試輸入向?TOC\o