|
Random Forests (隨機森林） 隨機森林的思想很簡單，百度百科上介紹的隨機森林算法比較好理解。 在機器學(xué)習(xí)中，隨機森林是一個包含多個決策樹的分類器， 并且其輸出的類別是由個別樹輸出的類別的眾數(shù)而定。 Leo Breiman和Adele Cutler發(fā)展出推論出隨機森林的算法。 而 "Random Forests" 是他們的商標。 這個術(shù)語是1995年由貝爾實驗室的Tin Kam Ho所提出的隨機決策森林（random decision forests）而來的。這個方法則是結(jié)合 Breimans 的 "Bootstrap aggregating" 想法和 Ho 的"random subspace method"" 以建造決策樹的集合。 學(xué)習(xí)算法 根據(jù)下列算法而建造每棵樹：
1. 用 N 來表示訓(xùn)練例子的個數(shù)，M表示變量的數(shù)目。
2. 我們會被告知一個數(shù) m ，被用來決定當(dāng)在一個節(jié)點上做決定時，會使用到多少個變量。m應(yīng)小于M
3. 從N個訓(xùn)練案例中以可重復(fù)取樣的方式，取樣N次，形成一組訓(xùn)練集（即bootstrap取樣。）。并使用這棵樹來對剩余預(yù)測其類別，并評估其誤差。
4. 對于每一個節(jié)點，隨機選擇m個基于此點上的變量。根據(jù)這 m 個變量，計算其最佳的分割方式。
5. 每棵樹都會完整成長而不會剪枝（Pruning）（這有可能在建完一棵正常樹狀分類器后會被采用）。
優(yōu)點 隨機森林的優(yōu)點有：
1. 對于很多種資料，它可以產(chǎn)生高準確度的分類器。
2. 它可以處理大量的輸入變量。
3. 它可以在決定類別時，評估變量的重要性。
4. 在建造森林時，它可以在內(nèi)部對于一般化后的誤差產(chǎn)生不偏差的估計。
5. 它包含一個好方法可以估計遺失的資料，并且，如果有很大一部分的資料遺失，仍可以維持準確度。
6. 它提供一個實驗方法，可以去偵測 variable interactions 。
7. 對于不平衡的分類資料集來說，它可以平衡誤差。
8. 它計算各例中的親近度，對于數(shù)據(jù)挖掘、偵測偏離者（outlier）和將資料視覺化非常有用。
9. 使用上述。它可被延伸應(yīng)用在未標記的資料上，這類資料通常是使用非監(jiān)督式聚類。也可偵測偏離者和觀看資料。
10. 學(xué)習(xí)過程是很快速的。
缺點 1. 隨機森林已經(jīng)被證明在某些噪音較大的分類或回歸問題上會過擬
2. 對于有不同級別的屬性的數(shù)據(jù)，級別劃分較多的屬性會對隨機森林產(chǎn)生更大的影響，所以隨機森林在這種數(shù)據(jù)上產(chǎn)出的屬性權(quán)值是不可信的。
mahout實現(xiàn)random forests：https://cwiki./MAHOUT/random-forests.html
online Random Forests （在線隨機森林）
這是一片09年，ICCV 上的文章，效果和離線的random forest差不多，特別的牛?？梢宰龇诸悾~可以做預(yù)測，
這里介紹的主要是在線隨機決策樹，其思想主要是：每棵樹可以在線分裂。每個葉子分裂的條件是預(yù)測的數(shù)量要達到一定的值和每個葉子節(jié)點信息。
每個樹的生長主要通過預(yù)測的樣本（在線接受的樣本），每棵樹的葉子節(jié)點分裂主要根據(jù)該節(jié)點的熵或Gini
學(xué)過決策樹和信息論的，對這個概念都有了解。其中j表示第j棵樹，i表示第i個分類結(jié)果。K表示總的分類數(shù)。 對有一個給定的結(jié)合S（在線預(yù)測中給定），每棵樹上葉子節(jié)點Pj的的概率可以表示為：
如果要在Pj葉子節(jié)點分類，那么，得到二個葉子節(jié)點的概率可以用下式表示： 解釋一下 Pjls，l為left，s為測試集合。所以Pjls表示為在集合S中Pj葉子節(jié)點的分列的左節(jié)點。同理，Pjrs表示為在集合S中Pj葉子節(jié)點的分列的右節(jié)點。 那么，每棵樹上葉子節(jié)點Pj分裂必須符合以下二個條件： 1. 落在葉子節(jié)點Pj的個數(shù)必須大于一個常數(shù)（可以人工設(shè)定） 2. 葉子節(jié)點的Gini必須大于一個常數(shù)（可以人工設(shè)定），Gini計算公式如下：
以上步驟就完成整個樹的更新。
下面給出了在線隨機森林算法的流程：
步驟3. 用個possion分布確定從采樣的次數(shù)，其原理見online boosting： http://www.cnblogs.com/liqizhou/archive/2012/05/10/2494145.html 步驟6. u代表分類的類別。 步驟7. j代表第t棵樹上葉子節(jié)點。 步驟8. 統(tǒng)計第j個葉子節(jié)點的數(shù)目和計算Gini 步驟9. 判斷條件是否分裂的二個條件。 步驟10. 在符合條件的葉子節(jié)點中，選擇一個Gini最大的葉子節(jié)點作為分類節(jié)點。 以上就是online Random forests 的主要思想。 這個程序特別牛，我跑了一下，挺牛逼的，效果沒比offline mode差不多。如果你需要做online learning的話十分推薦。 以上是我個人的理解，如有錯誤，請留言告訴我，本人感激不盡。 作者：BIGBIGBOAT/Liqizhou |
|
|
and 
