0x00 前言
本文是《GBDT源碼分析》系列的第二篇,主要關(guān)注GBDT的元算法"決策樹"在scikit-learn中的實現(xiàn)晌柬。
0x01 整體說明
scikit-learn的主要源碼都在項目的sklearn文件夾下,其中sklearn/tree
里是基本樹模型的實現(xiàn)代碼荒叶,如圖,該文件夾下有以下幾個文件。
- _init_.py: 包初始化
- setup.py: 包的安裝代碼
- tree.py: DecisionTree模型的主要邏輯代碼
- export.py: tree的輸出
- *.pxd和*.pyx文件: 分別有_tree, _splitter, _criterion, _utils四個內(nèi)容共八個文件镀赌,是tree具體實現(xiàn)步驟的CPython代碼。注意具體算法實現(xiàn)的核心代碼都是用CPython际跪,即在pyx后綴的文件里商佛,其它py文件實際上可以看做模型的殼。
- 還有一個tests文件夾姆打,從tests里的內(nèi)容來看良姆,里面對tree做回歸和分類的功能,以及tree的輸出和保存(export)做了測試幔戏。
__init__.py
文件
查看_init_.py文件玛追,可發(fā)現(xiàn)tree提供的主要類/方法有5個:
- DecisionTreeClassifier: 位于tree.py
- DecisionTreeRegressor: 位于tree.py
- ExtraTreeClassifier: 位于tree.py
- ExtraTreeRegressor: 位于tree.py
- export_graphviz: 位于export_graphviz
我們最終主要關(guān)注其中的DecisionTreeRegressor和export_graphviz。
關(guān)注前者的原因是因為GDBT是基于回歸樹實現(xiàn)的闲延;后者關(guān)系到樹的可視化和輸出痊剖,對我們理解能夠獲得的模型參數(shù)有一定幫助。
0x02 數(shù)據(jù)結(jié)構(gòu):Tree
決策樹算法圍繞的中心實際上就是一顆樹慨代,這棵樹結(jié)構(gòu)在訓(xùn)練階段中被構(gòu)建邢笙,在預(yù)測階段則根據(jù)樣本特征尋找一條從根節(jié)點到某個葉子結(jié)點的路徑。這一章我們將介紹這個關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)侍匙;在源碼中氮惯,這個樹結(jié)構(gòu)是用一個名為Tree的類實現(xiàn)的
Node節(jié)點
在定義樹以前,我們需要先定義節(jié)點Node想暗。Node是一個struct妇汗,在_tree.pxd中定義。一個Node由以下變量組成:
- left_child: 左子節(jié)點的ID
- right_child: 右子節(jié)點的ID
- feature: 該節(jié)點分裂所選的特征
- threshold: 分裂點的特征值
- impurity: 該節(jié)點的不純度
- n_node_samples: 訓(xùn)練集在該節(jié)點的樣本數(shù)(置信度)
- weighted_n_node_samples: 訓(xùn)練集在該節(jié)點的加權(quán)樣本數(shù)
Tree類的變量
類Tree是一個二叉樹说莫,可以由TreeBuilder構(gòu)建(我們將在下一章介紹TreeBuilder類)杨箭。Tree的定義和s具體實現(xiàn)代碼分別在_tree.pxd和_tree.pyx文件中。
Tree類有以下一些成員變量储狭,其中“可從外部獲得的attribute”代表這些值可以通過Tree.xxx_attribute的方式讀然バ觥:
- n_features: 特征數(shù)
- n_classes: 類別數(shù),對于回歸問題是1辽狈。
- n_outputs: 多標簽問題中的標簽數(shù)慈参;對于一般的單標簽問題和回歸問題,該值取1刮萌。
- max_n_classes: max(n_classes)驮配,僅對多標簽問題時有實際意義。
- nodes: 樹中所有的節(jié)點組成的數(shù)組。
- value_stride: n_outputs * max_n_classes
- max_depth: 可從外部獲得的attribute壮锻,樹的最大深度琐旁。
- node_count: 可從外部獲得的attribute,樹的節(jié)點數(shù)猜绣。
- capacity: 可從外部獲得的attribute灰殴,樹的容量,大于等于node_count掰邢。
- children_left: 可從外部獲得的attribute验懊,所有節(jié)點的左子節(jié)點對應(yīng)的nodeID組成的數(shù)組,如果節(jié)點本身是葉子節(jié)點尸变,其左子節(jié)點為常量TREE_LEAF,即-1减俏。
- children_right: 可從外部獲得的attribute召烂,所有節(jié)點的右子節(jié)點對應(yīng)的nodeID組成的數(shù)組,如果節(jié)點本身是葉子節(jié)點娃承,其右子節(jié)點為常量TREE_LEAF奏夫,即-1。
- features: 可從外部獲得的attribute历筝,所有節(jié)點分裂所選的特征(編號)組成的數(shù)組酗昼。
- threshold: 可從外部獲得的attribute,所有節(jié)點分裂點的特征值組成的數(shù)組梳猪。
- impurity: 可從外部獲得的attribute麻削,所有節(jié)點的不純度組成的數(shù)組。
- n_node_sample: 可從外部獲得的attribute春弥,所有節(jié)點上的樣本數(shù)組成的數(shù)組呛哟。
- weighted_n_node_samples: 可從外部獲得的attribute,所有節(jié)點上的加權(quán)樣本數(shù)組成的數(shù)組匿沛。
- value: 可從外部獲得的attribute扫责,維度是(capacity, n_outputs, max_n_classes),存儲了各個節(jié)點逃呼、標簽位鳖孤、類別位中樣本的個數(shù);對于回歸問題抡笼,則是各個節(jié)點的預(yù)測值苏揣。
Tree類的方法
類Tree有以下主要的方法
- _resize: 根據(jù)Tree的capacity更改樹內(nèi)所有數(shù)組變量的長度;如果capacity是-1蔫缸,將各個數(shù)組長度加倍腿准。實際調(diào)用_resize_c方法。
- _add_node: 加入一個新節(jié)點。
- predict: 對一個樣本輸出預(yù)測值吐葱,DecisionTree算法里面predict方法實際調(diào)用的方法街望。
- apply: 對一個樣本輸出它預(yù)測所在葉子節(jié)點的標號,DecisionTree算法里面apply方法實際調(diào)用的方法弟跑。根據(jù)特征是否稀疏會調(diào)用_apply_sparse_csr方法或_apply_dense方法灾前。
- decision_path: 對一個樣本輸出它的預(yù)測路徑(經(jīng)過的節(jié)點標號),DecisionTree算法里面decision_path方法實際調(diào)用的方法孟辑。根據(jù)特征是否稀疏會調(diào)用_decision_path_sparse_csr方法或_decision_path_dense方法哎甲。
- compute_feature_importances: 輸出所有特征的重要性importance,DecisionTree里面features_importences_屬性實際調(diào)用的方法饲嗽。計算思路:遍歷所有node炭玫,如果該節(jié)點不是葉子節(jié)點,該節(jié)點分裂后不純度的下降值加到該節(jié)點分裂特征的重要性上貌虾。這樣吞加,每個特征的重要性就是該特征作為分裂特征時不純度的下降的和。最后再做一個歸一化的處理尽狠。
0x03 決策樹的構(gòu)建
決策樹的構(gòu)建過程涉及三個關(guān)鍵類:
- Criterion和Splitter:定義和實現(xiàn)了樹結(jié)構(gòu)的分裂策略衔憨。
- TreeBuilder:通過遞歸的方式從訓(xùn)練樣本中構(gòu)建樹。
Criterion(分裂點好壞的評判標準)
_criterion.pyx
里主要定義和實現(xiàn)了各種關(guān)于不純度計算的類袄膏,包括:
- Criterion: 不純度評評判標準的基類/接口
- ClassificationCriterion: 分類問題的不純度評判標準的基類
- Entropy: 交叉熵践图,一種分類criteria
- Gini: 基尼系數(shù),一種分類criteria
- RegressionCriterion: 回歸問題的不純度評判標準的基類
- MSE: 平均方差沉馆,一種回歸criteria
- MAE: 平均絕對差码党,一種回歸criteria
這里提一下Criterion表示分裂點和左右節(jié)點的方法。在Criterion類內(nèi)置的變量里悍及,有start闽瓢、pos、end這樣三個值心赶,假設(shè)樣本標簽是samples(已排序的)扣讼,則samples[start: pos]可代表分裂后的左子節(jié)點,samples[pos: end]可代表分裂后的右子節(jié)點缨叫。Criterion類在初始化時其實是空的椭符,僅當構(gòu)建樹的時候才會被使用。
Splitter(最佳分裂點的尋找方法)
_splitter.pyx
里主要定義和實現(xiàn)了分裂點的具體計算方法耻姥,包括考慮一些工程上的性能問題销钝。
- Splitter: 所有splitter的基類/接口
- BaseDenseSplitter: 非稀疏特征矩陣的splitter基類
- BestSplitter: 對非稀疏情況尋找最佳分裂的splitter
- RandomSplitter: 對非稀疏情況尋找最佳隨機分裂的splitter
- BaseSparseSplitter: 稀疏特征矩陣的splitter基類
- BestSparseSplitter: 對稀疏情況尋找最佳分裂的splitter
- RandomSparseSplitter: 對稀疏情況尋找最佳隨機分裂的splitter
同Criterion一樣,Splitter在初始化時是空的琐簇,只有TreeBuilder才會調(diào)用它蒸健,用來尋找最佳的分裂點座享。
TreeBuilder
TreeBuilder類通過遞歸的方式從訓(xùn)練樣本中構(gòu)建樹。它通過Splitter來分裂內(nèi)部節(jié)點以及給葉子節(jié)點賦值似忧。TreeBuilder類主要用來控制構(gòu)建樹的過程中的各種停止條件渣叛,以及節(jié)點分裂時的優(yōu)先度策略,包括depth-first或best-first策略盯捌。
在決策樹的參數(shù)中淳衙,TreeBuilder相關(guān)的幾個關(guān)鍵參數(shù)包括
- min_samples_split: 每個節(jié)點上最少的樣本數(shù)
- min_samples_leaf: 每個葉子節(jié)點上最少的樣本數(shù)
- min_weight_leaf: 每個葉子節(jié)點最小的權(quán)重(加權(quán)樣本數(shù)占總加權(quán)樣本數(shù)的比例)
- max_depth: 樹的最大深度
- min_impurity_split: 當節(jié)點的不純度小于該值時,節(jié)點將不再分裂
TreeBuilder有兩種饺著,DepthFirstTreeBuilder和BestFirstTreeBuilder箫攀。TreeBuilder內(nèi)構(gòu)建樹的主要過程都是在build方法內(nèi)實現(xiàn)。
0x04 決策樹算法
決策樹算法這里包含三部分:BaseDecisionTree幼衰、DecisionTreeClassifier和DecisionTreeRegressor靴跛。其中,BaseDecisionTree類是后兩者的基類渡嚣。
BaseDecisionTree
查看tree.py汤求,除了之前提到的各種具體的樹模型,有一個BaseDecisionTree類严拒,是其它所有樹模型的基類,我們先看看這個類竖独。
如同scikit-learn中所有estimator一樣裤唠,BaseDecisionTree的基類也是BaseEstimator。
它有幾個基本方法/屬性:
- _init_: 初始化構(gòu)造方法
- fit: 訓(xùn)練方法
- predict: 預(yù)測方法
- apply: 返回樣本被預(yù)測所在的葉子結(jié)點的index莹痢,在0.17版本時加入
- decisionpath: 預(yù)測結(jié)果的預(yù)測路徑种蘸,在0.18版本時加入
- feature_importances: 特征重要性
此外,BaseDecisionTree應(yīng)還包含基類BaseEstimator中的get_params和set_params方法竞膳。
init方法
構(gòu)造方法里有以下參數(shù)航瞭,即我們在調(diào)用DecisionTree模型時輸入的那些參數(shù):
- criterion: 衡量分裂的準則,對于分類樹坦辟,可選"gini"和"entropy"刊侯,分別對應(yīng)基尼純度和信息增益。對于回歸樹锉走,可選"mse"和"mae"(0.18版本時加入)滨彻,分別對應(yīng)平均平方誤差和平均絕對值誤差。
- splitter: 每一個node上分裂點選擇策略挪蹭,可選"best"和"random"亭饵。(不太懂這兩個的區(qū)別)
- max_depth: 樹的最大深度。
- min_samples_split: 分裂時要求的最小樣本數(shù)梁厉。如果類型是int辜羊,為個數(shù);如果類型是float,為總樣本數(shù)的比例(0.18版本時加入)八秃。
- min_samples_leaf: 葉子結(jié)點上最小樣本數(shù)碱妆。如果類型是int,為個數(shù)喜德;如果類型是float山橄,為總樣本數(shù)的比例(0.18版本時加入)。
- min_weight_fraction_leaf: 相較于總樣本的權(quán)重和舍悯,葉子結(jié)點上樣本的權(quán)重和所占的最小比例航棱。(舉例來說禾怠,如果sample_weight沒有設(shè)定非春,所有樣本有同樣的權(quán)重)
- max_features: 分裂時考慮的特征數(shù)泳叠。如果類型是int诈唬,為個數(shù)咸产;如果類型是float馏颂,為所占比例法焰;還可以取sqrt址愿、log2混移、auto(sqrt)祠墅;如果是None,取總特征數(shù)歌径。(注意:the search for a split does not stop until at least one valid partition of the node samples is found, even if it requires to effectively inspect more than max_features features.)
- max_leaf_nodes: 使用“最好優(yōu)先”的方式構(gòu)造樹毁嗦,使得樹最多有max_leaf_nodes個葉子』仡酰“最好優(yōu)先”中的“最好”的定義是impurity的relative reduction最大狗准。
- random_state: 確定初始隨機狀態(tài)的參數(shù)。
- min_impurity_split: 若一個節(jié)點的不純度小于該參數(shù)茵肃,停止分裂腔长,該節(jié)點成為葉子節(jié)點。
- class_weight: 只有分類樹才有的參數(shù)验残,類別label的權(quán)重捞附,可以是"balanced"、None或者一個dict您没。
- presort: fitting時是否分揀數(shù)據(jù)故俐。對于大數(shù)據(jù)集可能會是的training過程變慢,對于小數(shù)據(jù)集或限制深度的情況紊婉,可能能加快training速度药版。
fit方法
該方法的主輸入?yún)?shù)有X(特征)和y(標簽),可選參數(shù)有sample_weight喻犁、check_input槽片、X_idx_sorted何缓。下面提取部分主要代碼做說明,省略可選參數(shù)还栓、數(shù)據(jù)格式判斷碌廓、多標簽分類等內(nèi)容。省略號代表這部分代碼略過剩盒,僅描述一下主要干了些什么谷婆。
# 從X的形狀獲取樣本數(shù)和特征數(shù),n_features_是樹模型的一個attribute
n_samples, self.n_features_ = X.shape
# 判斷模型是分類還是回歸
is_classification = isinstance(self, ClassifierMixin)
# ......對y(label)做處理
# 對于多標簽分類問題辽聊,n_outputs_是多標簽的個數(shù)纪挎;對于普通的分類問題,該值為1
self.n_outputs_ = y.shape[1]
# 當模型是分類樹時
if is_classification:
# 初始化classes跟匆,這是分類樹模型的一個attibute异袄;有哪些label
self.classes_ = []
# 初始化n_classes,這是分類樹模型的一個attibute玛臂;label的個數(shù)
self.n_classes_ = []
# 初始化編碼后的label
y_encoded = np.zeros(y.shape, dtype=np.int)
# ......對label進行編碼烤蜕,同時計算self.classes_和self.n_classes_
# ......根據(jù)sample_weight對class_weight進行修正
#當模型是回歸樹時
else:
# 初始化self.classes_和self.n_classes_
self.classes_ = [None] * self.n_outputs_
self.n_classes_ = [1] * self.n_outputs_
# ......對參數(shù)進行檢查和計算,非常長的一段代碼
# 構(gòu)建樹的各種定義和過程
# 插入一段別處的代碼:在tree.py中有一段關(guān)于type和constant的定義
DTYPE = _tree.DTYPE # np.float32
DOUBLE = _tree.DOUBLE # np.float64
# 分類樹中的分裂評判標準迹冤,在_criterion.pyx中實現(xiàn)
CRITERIA_CLF = {"gini": _criterion.Gini, "entropy": _criterion.Entropy}
# 回歸樹中的分裂評判標準讽营,即各種不純度函數(shù)的計算方法,在_criterion.pyx中實現(xiàn)
CRITERIA_REG = {"mse": _criterion.MSE, "friedman_mse": _criterion.FriedmanMSE, "mae": _criterion.MAE}
# 非稀疏情況下分裂點選擇策略泡徙,在_splitter.pyx中實現(xiàn)
DENSE_SPLITTERS = {"best": _splitter.BestSplitter, "random": _splitter.RandomSplitter}
# 稀疏情況下分裂點選擇策略斑匪,在_splitter.pyx中實現(xiàn)
SPARSE_SPLITTERS = {"best": _splitter.BestSparseSplitter, "random": _splitter.RandomSparseSplitter}
# 讀入模型的分裂評判標準
criterion = self.criterion
# 如果模型的criterion不是Criterion類的實例,根據(jù)前面定義的字典對分類和回歸情況分別初始化criterion
if not isinstance(criterion, Criterion):
if is_classification:
criterion = CRITERIA_CLF[self.criterion](self.n_outputs_, self.n_classes_)
else:
criterion = CRITERIA_REG[self.criterion](self.n_outputs_, n_samples)
# 判斷輸入是否稀疏锋勺,讀入模型的分裂評判標準
SPLITTERS = SPARSE_SPLITTERS if issparse(X) else DENSE_SPLITTERS
splitter = self.splitter
# 如果模型的splitter不是Splitter類的實例,根據(jù)前面定義的字典初始化Splitter
if not isinstance(self.splitter, Splitter):
splitter = SPLITTERS[self.splitter](criterion, self.max_features_, min_samples_leaf, min_weight_leaf, random_state, self.presort)
# 初始化樹狡蝶,這里的Tree實在_tree.pyx中實現(xiàn)的
self.tree_ = Tree(self.n_features_, self.n_classes_, self.n_outputs_)
# 如果max_leaf_nodes有定義庶橱,則使用BestFirstTreeBuilder這個TreeBuilder;其它情況使用DepthFirstTreeBuilder
if max_leaf_nodes < 0:
builder = DepthFirstTreeBuilder(splitter, min_samples_split, min_samples_leaf, min_weight_leaf, max_depth, self.min_impurity_split)
else:
builder = BestFirstTreeBuilder(splitter, min_samples_split, min_samples_leaf, min_weight_leaf, max_depth, max_leaf_nodes, self.min_impurity_split)
# 構(gòu)建樹(訓(xùn)練)
builder.build(self.tree_, X, y, sample_weight, X_idx_sorted)
predict方法
# 使用訓(xùn)練得到的tree做預(yù)測
proba = self.tree_.predict(X)
# 對于分類樹
if isinstance(self, ClassifierMixin):
# 對于只有一個標簽的分類問題贪惹,取預(yù)測概率最大的類別作為輸出
if self.n_outputs_ == 1:
return self.classes_.take(np.argmax(proba, axis=1), axis=0)
# 對于多標簽的分類問題苏章,對每一列標簽分別取預(yù)測概率最大的類別作為輸出
else:
predictions = np.zeros((n_samples, self.n_outputs_))
for k in range(self.n_outputs_):
predictions[:, k] = self.classes_[k].take(np.argmax(proba[:, k], axis=1), axis=0)
return predictions
# 對于回歸樹
else:
if self.n_outputs_ == 1:
return proba[:, 0]
else:
return proba[:, :, 0]
apply方法
調(diào)用self.tree_.apply(X)
decision_path方法
調(diào)用self.tree_.decision_path(X),讀取的時候可以通過toarray()方法奏瞬。
feature_importances_
調(diào)用self.tree_.compute_feature_importances()
DecisionTreeClassifier和DecisionTreeRegressor
DecisionTreeClassifier
DecisionTreeClassifier的init和fit方法直接繼承了基類BaseDecisionTree枫绅,額外增加了predict_proba和predict_log_proba方法。
predict_proba返回輸入樣本被預(yù)測到每個類的概率硼端,即樣本被預(yù)測到的葉子節(jié)點中l(wèi)abel的分布并淋;predict_log_proba是對上述概率取log后的結(jié)果。
DecisionTreeRegressor
DecisionTreeRegressorr的init和fit方法直接繼承了基類BaseDecisionTree珍昨,無其它新增方法县耽。
Regression Example
# Very simple toy example for Regression
X = [[0, 0], [3, 2], [-2, 2]]
y = [0.5, 2.5, 1]
clf = tree.DecisionTreeRegressor()
clf = clf.fit(X, y)
# feature importance
print "feature_importances_"
print clf.feature_importances_
# clf.tree_ is the generated tree, its value represents the predicted value on each node
print "tree_.value"
print clf.tree_.value
# the decision_path
print "decision_path"
print clf.decision_path([[-2, 2]]).toarray()
"""Output
feature_importances_
[ 0.94230769 0.05769231]
tree_.value
[[[ 1.33333333]]
[[ 0.75 ]]
[[ 0.5 ]]
[[ 1. ]]
[[ 2.5 ]]]
decision_path
[[1 1 0 1 0]]
"""
樹結(jié)構(gòu)可視化
# visualization
import pydotplus
from IPython.display import Image
dot_data = tree.export_graphviz(clf, out_file=None)
graph = pydotplus.graph_from_dot_data(dot_data)
Image(graph.create_png())
Classification Example
# Very simple toy example for Classifier
X = [[0, 0], [3, 2], [-2, 2], [5, -1]]
y = ['a', 'b', 'a', 'a']
clf = tree.DecisionTreeClassifier()
clf = clf.fit(X, y)
# feature importance
print "feature_importances_"
print clf.feature_importances_
# clf.tree_ is the generated tree, its value represents the predicted value on each node
print "tree_.value"
print clf.tree_.value
# the number of classes
print "n_classes_"
print clf.n_classes_
# the classes
print "classes_"
print clf.classes_
# the decision_path
print "decision_path"
print clf.decision_path([[-2, 2]]).toarray()
"""Output
feature_importances_
[ 0.33333333 0.66666667]
tree_.value
[[[ 3. 1.]]
[[ 2. 0.]]
[[ 1. 1.]]
[[ 1. 0.]]
[[ 0. 1.]]]
n_classes_
2
classes_
['a' 'b']
decision_path
[[1 1 0 0 0]]
"""
樹結(jié)構(gòu)可視化
# visualization
import pydotplus
from IPython.display import Image
dot_data = tree.export_graphviz(clf, out_file=None)
graph = pydotplus.graph_from_dot_data(dot_data)
Image(graph.create_png())
0x05 可視化
可以通過調(diào)用export_graphviz來輸出一顆決策樹(見上一章的例子)句喷,輸出是dot格式的結(jié)果,這是一種有向圖格式兔毙,該結(jié)果可以很容易轉(zhuǎn)化成其它文件格式如png唾琼、jpeg、pdf澎剥,這樣我們就可以完成對決策樹的可視化過程锡溯。
export_graphviz方法在export.py文件里實現(xiàn),有如下參數(shù):
- decision_tree: 需要可視化的決策樹哑姚。
- out_file: 輸出的文件祭饭,可為file object或string。
- max_depth: 輸出的樹最大深度蜻懦。
- feature_names: 一個list甜癞,為特征的名稱;如果不指定宛乃,輸出結(jié)果的特征名稱就以X[0], X[1]......來表示悠咱。
- class_names: 類別的名稱。
- label: 是否在node上顯示每個展示值的名稱征炼,可選"all", "root"析既。
- filled: 是否給node上色,來表示分類中的majority class谆奥,或回歸中的extremity value眼坏。
- leaves_parallel: 是否將所有葉子節(jié)點都畫在底部。
- impurity: 是否在每個node上顯示impurity值酸些。
- node_ids: 是否在每個node上顯示node ID宰译。
- proportion: 顯示values/sample的比例還是絕對值。
- rotate: 橫著展示樹還是豎著展示樹魄懂。
- rounded: node的邊框是否是圓角的沿侈,字體是Helvetica還是Times-Roman。
- special_characters: 是否忽略特殊字符市栗。
export_graphviz中有一些子方法:
- get_color: 當filled是True時缀拭,計算node的顏色。
- node_to_str: 生成一個節(jié)點的字符串表示填帽,包括nodeID蛛淋、criteria、impurity篡腌、sample count褐荷、class distribution/regression value。
- recurse: 遞歸的遍歷每個節(jié)點嘹悼,生成整棵樹的字符串表示诚卸。
個人主頁:http://cathyxlyl.github.io/
文章可以轉(zhuǎn)載, 但必須以超鏈接形式標明文章原始出處和作者信息