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

2、林構造： 2 算法思路：將一個N分類問題轉化為N個二分類問題。轉化方法是：構造N棵二叉擬合樹，這里假設N為26，然后我們給N棵二叉樹依次標號為1，2，3.26。1號樹的結果對應于該條記錄是不是屬于第一類，是則輸出1，否則輸出0.2號樹的結果對應于該條記錄是不是屬于第二類，是則1否則0，依此類推。這樣，我們的26棵二叉樹的結果就對應了26個下標。例如對于某條記錄，這26個二叉樹的結果按序號排列為0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，.1,0，那么這條記錄的分類應該為25。要將一個26維的0，1序列變回一個索引，我們只需要找出這個序列中值最大的元素的索引，這個索引即是序列號。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17、數據容器，并將隨機森林分成等量的4部分（因為我使用的是4個線程）。即，每個線程中執行的函數承擔1/4規模的隨機森林的構造，實現代碼如下：最后將4個線程得到的結果累加再做轉換即可得到最終結果。8 測試結果樹的數量每輪Train樣本決策樹最大層數分割備選屬性數每個屬性采樣數運行時間準確率260312972001001.7min0.926003129720010017min0.9432600031297200100170min9 并行效率對比10 總結 本次實驗，我們構造了決策樹以及隨機森林，構造基本模型我用了一天時間，但是構造出來的模型面臨著執行速度很慢的瓶頸。其原因在于（1）沒有對屬性列進行采樣（2）沒有在選取每一列的時候對這一列的值進行采樣（3）在構造決策樹子節點的時候傳遞的是數據集而不是索引，這導致我的決策樹雖然是正確的，但是幾乎一分鐘才能構造一棵CART，這樣的CART要用來構造隨機森林幾乎是不可能的事情（時