|
来源：hainingwyx 链接：www.jianshu.com/p/59b510bafb4d
写在之前
想看程序参数说明的请到：
http:///stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html http:///stable/modules/generated/sklearn.tree.DecisionTreeRegressor.html#sklearn.tree.DecisionTreeRegressor http://www./Program/Python/201604/830424.shtml
本文是Scikit-learn中的决策树算法的原理、应用的介绍。
正文部分
决策树是一个非参数的监督式学习方法，主要用于分类和回归。算法的目标是通过推断数据特征，学习决策规则从而创建一个预测目标变量的模型。如下如所示，决策树通过一系列if-then-else 决策规则 近似估计一个正弦曲线。
决策树优势：
简单易懂，原理清晰，决策树可以实现可视化 数据准备简单。其他的方法需要实现数据归一化，创建虚拟变量，删除空白变量。(注意：这个模块不支持缺失值) 使用决策树的代价是数据点的对数级别。 能够处理数值和分类数据 能够处理多路输出问题 使用白盒子模型(内部结构可以直接观测的模型)。一个给定的情况是可以观测的，那么就可以用布尔逻辑解释这个结果。相反，如果在一个黑盒模型(ANN)，结果可能很难解释 可以通过统计学检验验证模型。这也使得模型的可靠性计算变得可能 即使模型假设违反产生数据的真实模型，表现性能依旧很好。
决策树劣势：
可能会建立过于复杂的规则，即过拟合。为避免这个问题，剪枝、设置叶节点的最小样本数量、设置决策树的最大深度有时候是必要的。 决策树有时候是不稳定的，因为数据微小的变动，可能生成完全不同的决策树。 可以通过总体平均(ensemble)减缓这个问题。应该指的是多次实验。 学习最优决策树是一个NP完全问题。所以，实际决策树学习算法是基于试探性算法，例如在每个节点实现局部最优值的贪心算法。这样的算法是无法保证返回一个全局最优的决策树。可以通过随机选择特征和样本训练多个决策树来缓解这个问题。 有些问题学习起来非常难，因为决策树很难表达。如：异或问题、奇偶校验或多路复用器问题 如果有些因素占据支配地位，决策树是有偏的。因此建议在拟合决策树之前先平衡数据的影响因子。
分类
DecisionTreeClassifier 能够实现多类别的分类。输入两个向量：向量X，大小为[n_samples,n_features]，用于记录训练样本；向量Y，大小为[n_samples]，用于存储训练样本的类标签。
from sklearn import tree X = [[0, 0], [1, 1]] Y = [0, 1] clf = tree.DecisionTreeClassifier() clf = clf.fit(X, Y) clf.predict([[2., 2.]]) clf.predict_proba([[2., 2.]]) #计算属于每个类的概率
能够实现二进制分类和多分类。使用Isis数据集，有：
from sklearn.datasets import load_iris from sklearn import tree iris = load_iris() clf = tree.DecisionTreeClassifier() clf = clf.fit(iris.data, iris.target) # export the tree in Graphviz format using the export_graphviz exporter with open('iris.dot', 'w') as f: f = tree.export_graphviz(clf, out_file=f) # predict the class of samples clf.predict(iris.data[:1, :]) # the probability of each class clf.predict_proba(iris.data[:1, :])
安装Graphviz将其添加到环境变量，使用dot创建一个PDF文件。dot -Tpdf iris.dot -o iris.pdf
# 删除dot文件 import os os.unlink('iris.dot')
如果安装了pydotplus，也可以在Python中直接生成：
import pydotplus dot_data = tree.export_graphviz(clf, out_file=None) graph = pydotplus.graph_from_dot_data(dot_data) graph.write_pdf('iris.pdf')
可以根据不同的类别输出不同的颜色，也可以指定类别名字。
from IPython.display import Image dot_data = tree.export_graphviz(clf, out_file=None, feature_names=iris.feature_names, class_names=iris.target_names, filled=True, rounded=True, special_characters=True) graph = pydotplus.graph_from_dot_data(dot_data) Image(graph.create_png())
更多地可以看到分类的效果：
回归
和分类不同的是向量y可以是浮点数。
from sklearn import tree X = [[0, 0], [2, 2]] y = [0.5, 2.5] clf = tree.DecisionTreeRegressor() clf = clf.fit(X, y) clf.predict([[1, 1]])
本文前面提到的例子：http:///stable/auto_examples/tree/plot_tree_regression.html#sphx-glr-auto-examples-tree-plot-tree-regression-py
# Import the necessary modules and libraries import numpy as np from sklearn.tree import DecisionTreeRegressor import matplotlib.pyplot as plt # Create a random dataset rng = np.random.RandomState(1) X = np.sort(5 * rng.rand(80, 1), axis=0) y = np.sin(X).ravel() y[::5] += 3 * (0.5 - rng.rand(16)) # Fit regression model regr_1 = DecisionTreeRegressor(max_depth=2) regr_2 = DecisionTreeRegressor(max_depth=5) regr_1.fit(X, y) regr_2.fit(X, y) # Predict X_test = np.arange(0.0, 5.0, 0.01)[:, np.newaxis] y_1 = regr_1.predict(X_test) y_2 = regr_2.predict(X_test) # Plot the results plt.figure() plt.scatter(X, y, c='darkorange', label='data') plt.plot(X_test, y_1, color='cornflowerblue', label='max_depth=2', linewidth=2) plt.plot(X_test, y_2, color='yellowgreen', label='max_depth=5', linewidth=2) plt.xlabel('data') plt.ylabel('target') plt.title('Decision Tree Regression') plt.legend() plt.show()
多输出问题
多输出问题时需要预测多个输出的监督式学习问题。即Y是一个2d的向量，大小为[n_samples, n_outputs]。
当输出之间不相关时，一个简单的解决办法是建立n个独立模型。对于每一个输出，使用这些模型独立预测这每个输出。由于输出是和相同的输入相关的，所以一个更好的办法是建立一个能够持续预测所有输出的单一模型。首先，系统需要的训练时间更少了，因为只建立了一个模型。其次准确性也会得到提高。
决策树的策略需要修改以支持多分类问题。
叶子上存储n个输出变量 使用不同的标准计算所有n输出的平均减少
这一节是关于 DecisionTreeClassifier 和DecisionTreeRegressor的一些知识点。如果一个决策树的输出向量Y大小为[n_samples, n_outputs]，预测量有：
多输出的回归的例子：输入X是一个单一的值，输出Y是输入X的Sine和Cosine。
Multi-output Decision Tree Regression (http:///stable/auto_examples/tree/plot_tree_regression_multioutput.html#sphx-glr-auto-examples-tree-plot-tree-regression-multioutput-py) 
多输出的分类的例子：Face completion with a multi-output estimators(http:///stable/auto_examples/plot_multioutput_face_completion.html#sphx-glr-auto-examples-plot-multioutput-face-completion-py)
输入X是上半脸的像素，输出Y是下半脸的像素。
参考文献：
复杂度
通常生成一个二进制树运行时间为
查询时间为
虽然构建的算法意图建立一个均衡的树，但是不总是均衡的。假设子树保持均衡，每个节点的消耗为 
以查找使熵最大减少的特征。每个节点的消耗为 
，使得整个树的消耗为 
Scikit-learn提供了建立决策树的一种更加高效的实现。简单的实现，在每次划分时，将会重新计算类标签的直方图(分类)或者均值(回归)。将所有相关样本特征预分类保留标签计数，将每个节点的复杂度减少为 
，同时将整体复杂度减少为
。默认是开启的，一般来说会使得训练更快，但是如果关闭，则训练深层决策树的时候训练会变慢。 使用小贴士
如果数据量大，决策树容易过拟合。样本和特征的比例非常重要。如果决策树样本少，特征多，非常可能过拟合。 可以考虑事先做维度约减(PCA，ICA)，以产生一个特征之间区别性大的决策树 通过export将你的训练的决策树可视化，使用max_depth =3作为一个初始的树的深度，有一个数据拟合决策树模型的大概感觉，然后逐渐增加深度 数据的样本量的增加将加深决策树的深度，使用max_depth控制决策树的尺寸以防止过拟合 使用min_samples_split 或者 min_samples_leaf来控制叶节点的样本数量。一个非常小的数量往往意味着过拟合，而一个较大的数可以防止过拟合。可以将min_samples_leaf=5作为一个初始值。如果样本数据变化巨大，可以采用一个浮点数。两者的区别在于min_samples_leaf保证了叶节点最小的数量，min_samples_split能够建立任意数量的叶子节点，在文学上用到也更多 如果样本是有权重的，可以使用min_weight_fraction_leaf来实现基于权重的预修剪规则来优化决策树结构 决策树内部使用np.float32向量，如果样本不是这个形式的，将产生一个数据集的样本 如果数据矩阵X是非常稀疏的，建议在拟合和预测之前转换为稀疏矩阵csc_matrix。稀疏矩阵将比稠密矩阵快数量级的速度
决策树算法：ID3,C4.5,C5.0,CART
ID3是由Ross Quinlan在1985年建立的。这个方法建立多路决策树，并找到最大的信息增益。当树长到最大的尺寸，经常应用剪枝来提高决策树对未知数据的一般化。
C4.5是ID3的进一步延伸，通过将连续属性离散化，去除了特征的限制。C4.5将训练树转换为一系列if-then的语法规则。可确定这些规则的准确性，从而决定哪些应该被采用。如果去掉某项规则，准确性能提高，则应该实行修剪。
C5.0较C4.5使用更小的内存，建立更小的决策规则，更加准确。
CART和C4.5很相似，但是它支持数值的目标变量（回归）且不产生决策规则。CART使用特征和阈值在每个节点获得最大的信息增益来构建决策树。
scikit-learn使用一个最佳的CART算法
数学公式
训练向量
i=1,…和标签向量
，决策树递归地划分空间，以使得相同标签的样本被分到一起。用Q表示在节点m的数据，对于每一个候选划分
由特征j和阈值
，将数据划分为
两个子集
m节点的不纯度用函数H()计算，
选择参数是的不纯度最小：
递归以上，直至达到最大可允许的深度，
或者
分类标准
类k在节点m的比例：
Gini不纯度：
交叉熵：
误分类：
回归标准
参考文献
http:///stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html#sklearn.tree.DecisionTreeClassifier https://en./wiki/Decision_tree_learning https://en./wiki/Predictive_analytics L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth, Belmont, CA, 1984. J.R. Quinlan. C4. 5: programs for machine learning. Morgan Kaufmann, 1993. T. Hastie, R. Tibshirani and J. Friedman. Elements of Statistical Learning, Springer, 2009.
关注「Python开发者」 看更多精选Python技术文章 ↓↓↓
|
