Spark隨機深林擴展

看風景D人 2016-10-07

展開全文

本文目的

當前spark（1.3版）隨機森林實現(xiàn)，沒有包括OOB錯誤評估和變量權重計算。而這兩個功能在實際工作中比較常用。OOB錯誤評估可以代替交叉檢驗，評估模型整體結果，避免交叉檢驗帶來的計算開銷?，F(xiàn)在的數(shù)據(jù)集，變量動輒成百上千，變量權重有助于變量過濾，去掉無用變量，提高計算效率，同時也可以幫助理解業(yè)務。所以，本人在原始代碼基礎上，擴展了這兩個功能，下面記錄實現(xiàn)過程，作為備忘錄（參考代碼）。

整體思路

Random Forest實現(xiàn)中，大多數(shù)內(nèi)部對象是私有（private[tree]）的，所以擴展代碼使用了org.apache.spark.mllib.tree的命名空間，復用這些內(nèi)部對象。實現(xiàn)過程中，需要放回抽樣數(shù)據(jù)，Random Forest的原始實現(xiàn)是放在局部變量baggedInput中，外部無法訪問，所以擴展代碼必須冗余部分原始代碼，用于訪問baggedInput變量。原始實現(xiàn)中，會先將LabeledPoint轉(zhuǎn)成裝箱對象TreePoint，但是在計算OOB時，需要LabeledPoint，所以需要實現(xiàn)TreePoint到LabeledPoint的轉(zhuǎn)換邏輯。對于連續(xù)變量，取每個箱的中間值作為反轉(zhuǎn)后的結果；離散變量不需要做修改。當然為什么取中間值，為什么取三分之一或其他什么地方？因為在裝箱過程中，數(shù)據(jù)的分布信息已丟失，所以取0.5是一個可以接受的選擇。

OOB錯誤評估

原理

OOB是Out-Of-Bag的縮寫，顧名思義，使用那些out of bag的數(shù)據(jù)進行錯誤度量。隨機森林在訓練開始時，會根據(jù)樹的數(shù)量n，進行n次有放回采樣，用于訓練每一棵樹。放回采樣，必然導致一部分數(shù)據(jù)被選中，另外一部分數(shù)據(jù)沒有選中，選中了就放到bag中，沒有選中的就是out of bag。平均而言，每次放回采用中，37%的數(shù)據(jù)不會被選中，詳細推導見附錄【Out Of Bag概率】。這些沒有選中的數(shù)據(jù)不參與建模，所以可以作為驗證數(shù)據(jù)，評估模型效果。對于每一條記錄，若參與了m棵樹的建模，則n-m樹沒有參與建模，那么就可以將這剩下的n-m棵樹作為子森林，進行分類驗證，列子如下：

	Tree 1	Tree 2	Tree 3	Tree 4	Tree 5	Tree 6	Tree 7
Data 1		*		*		*
Data 2	*	*			*	*
Data 3	*		*				*
Data 4	*		*	*			*
Data 5		*			*		*

上面的表格中，每行表示一個記錄，每列表示一顆樹，"*"表示該記錄參與了某棵樹的建模。對于Data 1，參與了Tree 2,4,6的建模過程，那么可選取Tree 3,5,7作為子隨機森林模型，并計算Data 1的分類結果。

實現(xiàn)

上面提到了OOB的原理和評估方法，下面介紹如何實現(xiàn)，

private def computeOobError(

strategy: Strategy,

baggedInput: RDD[BaggedPoint[TreePoint]],

bins: EnhancedRandomForest.BinList,

forest: RandomForestModel): Double = {

val actualPredictPair = baggedInput

.map(x => {

val labeledPoint = EnhancedTreePoint.treePointToLabeledPoint(

x.datum, bins, strategy)

(x.subsampleWeights.zipWithIndex.filter(_._1 == 0)

.map(_._2).map(index => forest.trees(index)), labeledPoint)

})

.filter(_._1.size > 0) // 過濾掉無樹的森林

.map({

case (oobTrees, labeledPoint) => {

val subForest = new RandomForestModel(strategy.algo, oobTrees)

(labeledPoint.label, subForest.predict(labeledPoint.features))

}

})

val totalCount = actualPredictPair.count

assert(totalCount > 0,

s"OOB error measure: data number is zeror")

strategy.algo match {

case Regression => actualPredictPair.map(x => Math.pow(x._1 -

x._2, 2)).reduce(_ + _) / totalCount

case Classification => actualPredictPair.filter(x => x._1 !=

x._2).count.toDouble / totalCount

}

上面函數(shù)截取了oob實現(xiàn)的主邏輯，baggedInput是一個特殊的數(shù)據(jù)結構，用于記錄每一條記錄選中的信息。比如需要建立10棵樹，那么bagged有10列，每一列記錄了在當前這棵樹，該記錄被選中了幾次。所以，使用0標示那些沒有選中的記錄。得到了那些當前數(shù)據(jù)沒有參與建模的樹后，構建字隨機森林模型并預測結果，最后通過真實數(shù)據(jù)與預測數(shù)據(jù)，計算OOB錯誤評估。對于回歸問題，使用平方錯誤；分類問題，使用錯誤率。當然，錯誤的評估方式，后面還可以擴展。

變量重要性

原理

如何描述變量重要性，一種直觀的理解是變量越重要，如果混淆它，那么模型效果會越差?；煜幚碛袔追N方案，比如根據(jù)某種隨機分布，加減隨機值，或者隨機填充值。但是需要額外的參數(shù)，并且會影響原有的數(shù)據(jù)分布。所以，采取隨機排序混淆變量，這樣不會改變原始的數(shù)據(jù)分布，也不需要而外的參數(shù)。

具體做法是如下：

計算整體OOB(D)

選取變量i，隨機排序，計算OOB(D_i)
針對所有變臉，重復步驟2，
重要性I(i) = OOB(D_i)-OOB(D)

I(i)越高，說明變量i越重要；如果I(i) = 0,那么說明變量i沒有什么作用；如果I(i) < 0,那么說明變量i有很明顯的噪音，對模型產(chǎn)生了負面影響。

實現(xiàn)

實現(xiàn)的難點是隨機排序，在大規(guī)模分布式數(shù)據(jù)上，實現(xiàn)隨機排序至少需要一次排序，會非常消耗計算資源。擴展代碼中使用了一個小技巧，利用spark隨機森林的內(nèi)部結構TreePoint，避免排序，提高隨機排序效率。因為TreePoint是裝箱數(shù)據(jù)，每個變量的值是箱索引，一般不超過100個。所以只需要將箱索引進行隨機排序，就可以達到對整個數(shù)據(jù)進行隨機排序的目的。

private def computeVariableImportance(

strategy: Strategy,

baggedInput: RDD[BaggedPoint[TreePoint]],

bins: EnhancedRandomForest.BinList,

forest: RandomForestModel,

oobError: Double): Array[Double] = {

(0 until bins.size).par.map(featureIndex => {

val binCount = if (strategy.categoricalFeaturesInfo.contains(featureIndex)) { // category feature

strategy.categoricalFeaturesInfo(featureIndex)

} else { // continuous feature

bins(featureIndex).size

}

val shuffleBinFeature = Random.shuffle((0 until binCount).toList) // 每個元素對應shuffle后的數(shù)據(jù)

val shuffleOneFeatureBaggedInput = baggedInput.map(x => {

val currentFeatureBinIndex = x.datum.binnedFeatures(featureIndex)

x.datum.binnedFeatures(featureIndex) = shuffleBinFeature(currentFeatureBinIndex)

})

computeOobError(strategy, shuffleOneFeatureBaggedInput, bins, forest) - oobError

}).toArray

}

上面的使用中，使用list.par.map的并發(fā)操作，同時對所有的變量計算重要性，具體的調(diào)度有spark服務器控制，最大限度利用spark的資源。

聚合模型穩(wěn)定的理論依據(jù)

隨機森林背后的主要思想是聚合模型（Ensemble Model）。為什么聚合模型效果好于單一模型（理論推導，請參考附錄【聚合模型錯誤評估】）？直觀的理解，當很多模型進行投票時，有一些模型會犯錯，另外一些模型正確，那么正確的投票會與錯誤的投票抵消，整體上只要最終正確的投票多于錯誤的投票，哪怕多一票，那么就會得到正確的結果。由于相互抵消，所以聚合效果比單一模型穩(wěn)定。聚合模型中，需要模型間具有較大差異，這樣才能覆蓋數(shù)據(jù)的不同方面，這也是為什么隨機森林在數(shù)據(jù)的行和列兩個維度上，添加隨機過程，用于增大模型之間的差異。

引用一句諺語，"三個臭皮匠，頂一個諸葛亮"，可以形象的解釋。比如這里有101個臭皮匠，假設他們對一件事情的判斷正確的概率是0.57，而諸葛亮對這件事情判斷正確的概率是0.9。那么，假設這101個臭皮匠通過投票判斷，那么概率可以達到0.92（R代碼：sum(dbinom(51:101,101,0.57))），比諸葛亮強！

總結

通過擴展這兩個功能，重新溫習了臺大《機器學習技法》相關課程，同時在真實數(shù)據(jù)上檢驗了Random Forest的模型效果。實踐檢驗了整理，學以致用，感覺很滿足。同時，在閱讀org.apache.spark.mllib.tree源代碼的時候，學習到了一些分布式數(shù)據(jù)集上算法實現(xiàn)的技巧。希望這些分享對你有用。

參考資料

附錄

Out Of Bag概率

設N為樣本大小，那么N次有放回抽樣中，一次沒有選中的概率可以表示如下，