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