隨機(jī)森林實(shí)驗(yàn)報告

1、隨機(jī)森林實(shí)驗(yàn)報告實(shí)驗(yàn)?zāi)康膶?shí)現(xiàn)隨機(jī)森林模型并測試。實(shí)驗(yàn)問題Kaggle第二次作業(yè)Non-linear classification算法分析與設(shè)計一算法設(shè)計背景:1.隨機(jī)森林的原子分類器一般使用決策樹，決策樹又分為擬合樹和分類樹。這兩者的區(qū)別在于代價估值函數(shù)的不同。2.根據(jù)經(jīng)驗(yàn)，用擬合樹做分類的效果比分類樹略好。3.對于一個N分類問題,它總是可以被分解為N個2分類問題，這樣分解的好處是其決策樹更加方便構(gòu)造，更加簡單，且更加有利于用擬合樹來構(gòu)建分類樹。對于每一個2分類問題，構(gòu)造的樹又叫CART樹，它是一顆二叉樹。4.將N個2分類樹的結(jié)果進(jìn)行匯總即可以得到多分類的結(jié)果。5.CART樹構(gòu)造：6. 隨機(jī)森

2、林構(gòu)造： 2 算法思路：將一個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，0，0，0，0，0，0，0，0，0，0，0，0，0，0，.1,0，那么這條記錄的分類應(yīng)該為25。要將一個26維的0，1序列變回一個索引，我們只需要找出這個序列中值最大的元素的索引，這個索引即是序列號。

3、 我們將上面的26棵分別對26個索引做是否判斷的二分類樹視為一個整體，在多線程的環(huán)境下，構(gòu)造多個這樣的整體，然后進(jìn)行求和運(yùn)算，最后取出每個結(jié)果序列中值最大的元素的下標(biāo)作為分類值，那么久得到了我們想要的結(jié)果，隨機(jī)森林完成。3 算法流程：1. 讀入訓(xùn)練集trainset,測試集testset2. 將訓(xùn)練集分割為輸入trainIn,輸出trainOut3. 這里假設(shè)類別數(shù)N為26，將trainOut記錄條數(shù) 映射為 transformTrainOut訓(xùn)練記錄數(shù)264.初始化transformTestOut測試記錄數(shù)26全部為05.For i = 1 : ForestSize: /對訓(xùn)練集采樣，這里要

4、注意輸入和輸出一致 sampleIn,transformSampleOut = TakeSample(trainIn,transformTrainOut) For category = 1 : 26: /CartTree 數(shù)組存放著26棵二分類樹 CartTreecategory = TrainCartTree(sampleIn,transformSampleOut); end /transformTestOut測試記錄數(shù)26為承接二分類樹輸出的容器 for i1 = 1 : testSetNum: For category = 1 : 26: transformTestOuti1catego

5、ry += predict(CartTreecategory,testseti1) end EndEnd6. 遍歷 transformTrainOut，將其每一行的最大值的下標(biāo)作為該行記錄的索引值。4 決策樹及隨機(jī)森林的配置1.決策樹 在這里，我們每一次26分類是由26棵CART共同完成的，CART的cost function采用的是gini系數(shù)，CART的最大層數(shù)為7，分裂停止條件為當(dāng)前節(jié)點(diǎn)GINI為0或者當(dāng)前節(jié)點(diǎn)所在層數(shù)到達(dá)了7.2. 隨機(jī)森林a.隨機(jī)森林每次循環(huán)的訓(xùn)練集采樣為原訓(xùn)練集的0.5.b.對于森林中每一棵決策樹每一次分割點(diǎn)的選取，對屬性進(jìn)行了打亂抽樣，抽樣數(shù)為25，即每次分割只在

6、25個屬性中尋找最合適的值。并且對于每個選取的屬性，我們進(jìn)行了行采樣。即如果這個屬性所擁有的屬性值數(shù)大于30，我們選取其中30個作為分割候選，如果小于30，則全部納入分割候選。5 代碼詳解1. 訓(xùn)練集/測試集的讀入 a.在dataDefine.h中定義了：訓(xùn)練集記錄列數(shù)numparametres （ID（1） + 參數(shù)數(shù)量（617） + 輸出（1） = 619）訓(xùn)練集記錄條數(shù)transetNum測試集記錄條數(shù)testsetNum分類類型數(shù)typesNum而在main.cpp中，我們聲明了全局變量trainIn用于裝載訓(xùn)練集輸入，trainOut用于裝載訓(xùn)練集的輸出（這里trainOut是二維數(shù)

7、組是出于模型如果泛化，那么輸出值不一定只有一個的情況，在本次實(shí)驗(yàn)中并未派上什么真正用場，可以將trainOut看作一個普通一維數(shù)組）。trainID用于裝載訓(xùn)練集中每一行的第一列ID號。testIn,testID則對應(yīng)測試集的輸入和ID號。這里注意，沒有testOut的原因是測試集的結(jié)果理論上應(yīng)該是不存在的。然后通過自己編寫的讀入函數(shù)讀入測試集合訓(xùn)練集，這個函數(shù)將分別裝載我們在前面提到的trainIn、trainOut、trainID、testIn、testID。這個函數(shù)使用的fstream逐行讀入的方法，這里不做詳述。2. 訓(xùn)練集輸出轉(zhuǎn)化為對應(yīng)的26維01數(shù)組transformOuttype

8、sNum在dataDefine.h中，我們定義了分類類別數(shù)typesNum:在main.cpp中，我們定義了全局變量transformOuttypesNum這里的transformOut是用于儲存將trainOut每行的值映射為一行對應(yīng)的26維01序列后所產(chǎn)生的結(jié)果。這里面的對應(yīng)關(guān)系是：例如trainOut10中的值是13那么transformOut1013 = 1,transformOut10除13外其他列 = 0；如果值是14，那么14列為1，其他列為0，行號代表的是它們對應(yīng)的是第幾條記錄；trainOut10 和transformOut10 都表示的是第10行的分類值為某個值，只是表達(dá)方

9、式不同。前者用數(shù)字表示，后者將對應(yīng)下標(biāo)的值置1表示。轉(zhuǎn)換接口由main.cpp中的函數(shù)定義，它的輸入?yún)?shù)依次為轉(zhuǎn)換輸出的承接容器transformres,盛放原始輸出的容器orges。它所做的事情是將transformresiorgesi的值置13. 并行構(gòu)建隨機(jī)森林在main.cpp中，我們構(gòu)建了trainInperTime代表的是隨機(jī)森林算法中經(jīng)過采樣步驟后選取的訓(xùn)練輸入，TransformOutPerTime 代表的是與trainInperTime對應(yīng)的轉(zhuǎn)換輸出transformtestOut是承接本支線程的所有CART樹的決策值之和的結(jié)構(gòu)，這與算法思路是對應(yīng)的，我們將所有CART樹的預(yù)

10、測結(jié)果在意個轉(zhuǎn)換輸出容器上累加，然后對于每行取該行最大列的下標(biāo)，即可得到由隨機(jī)森林得到的分類結(jié)果。我們可以看出，這幾個變量都是只有最后的TX有區(qū)別，實(shí)際上，重復(fù)的創(chuàng)建相似的變量只是為了方便多線程操作不會沖突。多線程入口：這里使用的是C+11的<thread>庫，簡單好用。每一個線程的隨機(jī)森林框架定義在main.cpp的這個函數(shù)采用循環(huán)的方式，每次循環(huán)，對訓(xùn)練集及對應(yīng)轉(zhuǎn)換輸出進(jìn)行打亂后采樣，然后輸入中進(jìn)行一輪決策樹的訓(xùn)練，這一輪訓(xùn)練將會生成26棵CART樹，對應(yīng)26個分類值。這里輸入的參數(shù)Tree就是我們所用的決策樹容器，這里注意，我們一個線程中只需要公用一個決策樹結(jié)構(gòu)即足夠了.在訓(xùn)

11、練完成后，我們用累加訓(xùn)練結(jié)果。4. 一輪訓(xùn)練26棵樹因?yàn)?6棵CART樹才能完整的等價于一棵26分類樹，因此我們將構(gòu)建這26棵CART樹的過程看成是一個整體。這個過程由函數(shù)實(shí)現(xiàn)。它的輸入依次是本輪的訓(xùn)練輸入（經(jīng)過了下采樣，隨機(jī)森林要求的），對應(yīng)的轉(zhuǎn)換訓(xùn)練輸出，以及一個決策樹容器 Tree。決策樹的定義我們將在下文中描述。這個函數(shù)有一個棧并且有一個從1:26的循環(huán)每次循環(huán)會建立一棵關(guān)于對應(yīng)的分類值得CART樹，CART樹的構(gòu)造是由棧trace維護(hù)的，trace維護(hù)的是一個先序的遍歷順序。當(dāng)循環(huán)完成后，將會計算本輪的轉(zhuǎn)換輸出結(jié)果的變更：5. 每科CART樹的構(gòu)造CART樹的數(shù)據(jù)結(jié)構(gòu)如下：train

12、In trainOut對應(yīng)于輸入該樹的輸入輸出集，Nodes表示的是節(jié)點(diǎn)序列，在這里我們的樹的構(gòu)造使用的是數(shù)組，且樹的節(jié)點(diǎn)間的索引是通過索引值維護(hù)的，這顆樹非常緊密（如果只看NODES是看不出節(jié)點(diǎn)間的層級關(guān)系的）。它有如下成員函數(shù)：setDecisionTree用于給trainIn 和 trainOut 賦值getNodeSequence(node1)本來是用來輸出節(jié)點(diǎn)參數(shù)的，這里不做詳述initialize用于初始化決策樹。getNodeAttr用于得到某一節(jié)點(diǎn)的備選屬性分割值computePerNodeGini用于計算某一節(jié)點(diǎn)的GINI值，這在停止節(jié)點(diǎn)分割時有用computeNodeVal

13、ue是用于計算某一葉子節(jié)點(diǎn)的擬合值的。我們再說一下Nodes節(jié)點(diǎn)，它的結(jié)構(gòu)如下AttrbutesselectedColumns是用于存放候選的分割值的容器其余變量的功能見圖片中的文字注釋這里我們用dataIndex存放對應(yīng)記錄所在索引的方法取代了直接存放記錄，這里是一個巨大的改進(jìn)，將程序的執(zhí)行速度提高了至少10倍。在構(gòu)造一棵決策樹時，當(dāng)train函數(shù)對應(yīng)的trace棧的棧頂非空時，我們會不斷的取出棧頂元素，對其進(jìn)行操作，Index指的是節(jié)點(diǎn)所在的索引值，container用于存放這個節(jié)點(diǎn)的左右葉子索引，由于樹的構(gòu)建是由外部棧維護(hù)的，所以這個container是必不可少的，在當(dāng)前節(jié)點(diǎn)分割完成后，

14、我們會將這個節(jié)點(diǎn)的索引值出棧，如果container0的值不是-1，我們會將container0,container1入棧。建樹的對應(yīng)模塊在main.cpp下的train函數(shù)中的下面再重點(diǎn)說一下函數(shù)：這個函數(shù)是單棵決策樹構(gòu)造的核心，調(diào)用這個函數(shù)，如果當(dāng)前節(jié)點(diǎn)的Gini值已經(jīng)為0，那么這個函數(shù)會計算當(dāng)前節(jié)點(diǎn)的擬合值：結(jié)束條件是gini = 0 | 層數(shù)等于10如果當(dāng)前節(jié)點(diǎn)不滿足結(jié)束分割條件，那么函數(shù)將對屬性進(jìn)行抽樣，抽樣的方法是打亂后取前selectedColumns 列。然后調(diào)用getNodeAttr(s,index)獲取當(dāng)前節(jié)點(diǎn)的備選分割值，這里的s是抽取的屬性的列號的集合。在得到備選的屬性

15、分割值后，將進(jìn)入循環(huán)，尋找最優(yōu)分割點(diǎn)6. 最終結(jié)果計算在main函數(shù)中，我們將四個線程所得的transformOutT相加，最后遍歷取每一行最大值的下標(biāo)，即可得到最終結(jié)果。6 算法優(yōu)化1. 應(yīng)用了數(shù)組+棧建樹取代了普通的函數(shù)遞歸建樹，加快了建樹速度。2. 在傳遞每個節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)據(jù)集時，使用了傳遞數(shù)據(jù)集的索引而非數(shù)據(jù)本身，這樣做的好處是，原來如果傳遞一條數(shù)據(jù)需要復(fù)制617 個double類型的數(shù)量，而現(xiàn)在只需要傳遞一個Int型的索引，這種快了617倍的數(shù)據(jù)集傳遞方式使程序運(yùn)行效率提高了10倍以上。3. 在每個屬性中選擇備選分割值的時候，采用了一種下采樣的策略。即：如果該節(jié)點(diǎn)的數(shù)據(jù)集大小小于某一數(shù)

16、值，則將這個數(shù)據(jù)集的這個屬性的所有值都納入候選分割值列表。但是如果大于了這個閾值，則將屬性所對應(yīng)的列進(jìn)行排序后再進(jìn)行等間距采樣得到樣本數(shù)等于閾值的子集作為候選分割集。代碼詳見getPartition().這樣做的好處是需要計算的分割gini值大大減少了（本人取的采樣閾值時100，相比原數(shù)據(jù)集，樣本空間縮小了盡30倍），這里也再一次加速了程序運(yùn)行。但是這個優(yōu)化隨機(jī)而來的一個問題是：有可能每次分割都不是最佳分割。4. 使用了C+11的<thread>庫進(jìn)行了并行實(shí)現(xiàn)，開出4個線程，程序相比單線程加速了4倍。7 并行實(shí)現(xiàn)C+11<thread>庫創(chuàng)建線程，為每個線程賦予獨(dú)立的

17、數(shù)據(jù)容器，并將隨機(jī)森林分成等量的4部分（因?yàn)槲沂褂玫氖?個線程）。即，每個線程中執(zhí)行的函數(shù)承擔(dān)1/4規(guī)模的隨機(jī)森林的構(gòu)造，實(shí)現(xiàn)代碼如下：最后將4個線程得到的結(jié)果累加再做轉(zhuǎn)換即可得到最終結(jié)果。8 測試結(jié)果樹的數(shù)量每輪Train樣本決策樹最大層數(shù)分割備選屬性數(shù)每個屬性采樣數(shù)運(yùn)行時間準(zhǔn)確率260312972001001.7min0.926003129720010017min0.9432600031297200100170min9 并行效率對比10 總結(jié) 本次實(shí)驗(yàn)，我們構(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ī)森林幾乎是不可能的事情（時