[关闭]
@hainingwyx 2017-05-30T01:08:08.000000Z 字数 6368 阅读 1442

Scikit-learn中的决策树

数据挖掘


写在之前

想看程序参数说明的请到:
+ http://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html
+ http://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeRegressor.html#sklearn.tree.DecisionTreeRegressor
+ http://www.th7.cn/Program/Python/201604/830424.shtml
本文是Scikit-learn中的决策树算法的原理、应用的介绍。

正文部分

决策树是一个非参数的监督室学习方法,主要用于分类和回归。算法的目标是通过推断数据特征,学习决策规则从而创建一个预测目标变量的模型。如下如所示,决策树通过一系列if-then-else 决策规则 近似估计一个正弦曲线。

../_images/sphx_glr_plot_tree_regression_0011.png

决策树优势:

决策树劣势:

分类

DecisionTreeClassifier 能够实现多类别的分类。输入两个向量:向量X,大小为[n_samples,n_features],用于记录训练样本;向量Y,大小为[n_samples],用于存储训练样本的类标签。

  1. from sklearn import tree
  2. X = [[0, 0], [1, 1]]
  3. Y = [0, 1]
  4. clf = tree.DecisionTreeClassifier()
  5. clf = clf.fit(X, Y)
  6. clf.predict([[2., 2.]])
  7. clf.predict_proba([[2., 2.]]) #计算属于每个类的概率

DecisionTreeClassifier 能够实现二进制分类和多分类。使用Isis数据集,有:

  1. from sklearn.datasets import load_iris
  2. from sklearn import tree
  3. iris = load_iris()
  4. clf = tree.DecisionTreeClassifier()
  5. clf = clf.fit(iris.data, iris.target)
  6. # export the tree in Graphviz format using the export_graphviz exporter
  7. with open("iris.dot", 'w') as f:
  8. f = tree.export_graphviz(clf, out_file=f)
  9. # predict the class of samples
  10. clf.predict(iris.data[:1, :])
  11. # the probability of each class
  12. clf.predict_proba(iris.data[:1, :])

安装Graphviz将其添加到环境变量,使用dot创建一个PDF文件。dot -Tpdf iris.dot -o iris.pdf

  1. # 删除dot文件
  2. import os
  3. os.unlink('iris.dot')

如果安装了pydotplus,也可以在Python中直接生成:

  1. import pydotplus
  2. dot_data = tree.export_graphviz(clf, out_file=None)
  3. graph = pydotplus.graph_from_dot_data(dot_data)
  4. graph.write_pdf("iris.pdf")

可以根据不同的类别输出不同的颜色,也可以指定类别名字。

  1. from IPython.display import Image
  2. dot_data = tree.export_graphviz(clf, out_file=None,
  3. feature_names=iris.feature_names,
  4. class_names=iris.target_names,
  5. filled=True, rounded=True,
  6. special_characters=True)
  7. graph = pydotplus.graph_from_dot_data(dot_data)
  8. Image(graph.create_png())

../_images/iris.svg

更多地可以看到分类的效果:

../_images/sphx_glr_plot_iris_0013.png

回归

和分类不同的是向量y可以是浮点数。

  1. from sklearn import tree
  2. X = [[0, 0], [2, 2]]
  3. y = [0.5, 2.5]
  4. clf = tree.DecisionTreeRegressor()
  5. clf = clf.fit(X, y)
  6. clf.predict([[1, 1]])

本文前面提到的例子:http://scikit-learn.org/stable/auto_examples/tree/plot_tree_regression.html#sphx-glr-auto-examples-tree-plot-tree-regression-py

  1. # Import the necessary modules and libraries
  2. import numpy as np
  3. from sklearn.tree import DecisionTreeRegressor
  4. import matplotlib.pyplot as plt
  5. # Create a random dataset
  6. rng = np.random.RandomState(1)
  7. X = np.sort(5 * rng.rand(80, 1), axis=0)
  8. y = np.sin(X).ravel()
  9. y[::5] += 3 * (0.5 - rng.rand(16))
  10. # Fit regression model
  11. regr_1 = DecisionTreeRegressor(max_depth=2)
  12. regr_2 = DecisionTreeRegressor(max_depth=5)
  13. regr_1.fit(X, y)
  14. regr_2.fit(X, y)
  15. # Predict
  16. X_test = np.arange(0.0, 5.0, 0.01)[:, np.newaxis]
  17. y_1 = regr_1.predict(X_test)
  18. y_2 = regr_2.predict(X_test)
  19. # Plot the results
  20. plt.figure()
  21. plt.scatter(X, y, c="darkorange", label="data")
  22. plt.plot(X_test, y_1, color="cornflowerblue", label="max_depth=2", linewidth=2)
  23. plt.plot(X_test, y_2, color="yellowgreen", label="max_depth=5", linewidth=2)
  24. plt.xlabel("data")
  25. plt.ylabel("target")
  26. plt.title("Decision Tree Regression")
  27. plt.legend()
  28. plt.show()

多输出问题

多输出问题时需要预测多个输出的监督式学习问题。即Y是一个2d的向量,大小为[n_samples, n_outputs]。

当输出之间不相关时,一个简单的解决办法是建立n个独立模型。对于每一个输出,使用这些模型独立预测这每个输出。由于输出是和相同的输入相关的,所以一个更好的办法是建立一个能够持续预测所有输出的单一模型。首先,系统需要的训练时间更少了,因为只建立了一个模型。其次准确性也会得到提高。

决策树的策略需要修改以支持多分类问题。

这一节是关于 DecisionTreeClassifier 和DecisionTreeRegressor的一些知识点。如果一个决策树的输出向量Y大小为[n_samples, n_outputs],预测量有:

多输出的回归的例子:输入X是一个单一的值,输出Y是输入X的Sine和Cosine。

Multi-output Decision Tree Regression

../_images/sphx_glr_plot_tree_regression_multioutput_0011.png

多输出的分类的例子:Face completion with a multi-output estimators

输入X是上半脸的像素,输出Y是下半脸的像素。

../_images/sphx_glr_plot_multioutput_face_completion_0011.png

参考文献:

复杂度

通常生成一个二进制树运行时间为O(n_{samples}n_{features}\log(n_{samples}))查询时间为O(\log(n_{samples}))虽然构建的算法意图建立一个均衡的树,但是不总是均衡的。假设子树保持均衡,每个节点的消耗为O(n_{features})以查找使熵最大减少的特征。每个节点的消耗为O(n_{features}n_{samples}\log(n_{samples})),使得整个树的消耗为

O(n_{features}n_{samples}^{2}\log(n_{samples}))

Scikit-learn提供了建立决策树的一种更加高效的实现。简单的实现,在每次划分时,将会重新计算类标签的直方图(分类)或者均值(回归)。将所有相关样本特征预分类保留标签计数,将每个节点的复杂度减少为O(n_{features}\log(n_{samples})),同时将整体复杂度减少为O(n_{features}n_{samples}\log(n_{samples}))。默认是开启的,一般来说会使得训练更快,但是如果关闭,则训练深层决策树的时候训练会变慢。

使用小贴士

决策树算法: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算法

数学公式

训练向量x_i \in R^n,i=1,...和标签向量y \in R^l,决策树递归地划分空间,以使得相同标签的样本被分到一起。用Q表示在节点m的数据,对于每一个候选划分\theta = (j, t_m)由特征j和阈值t_m,将数据划分为Q_{left}(\theta)Q_{right}(\theta)两个子集

Q_{left}(\theta) = {(x, y) | x_j <= t_m}Q_{right}(\theta) = Q \setminus Q_{left}(\theta)

m节点的不纯度用函数H()计算,G(Q, \theta) = \frac{n_{left}}{N_m} H(Q_{left}(\theta))+ \frac{n_{right}}{N_m} H(Q_{right}(\theta))

选择参数是的不纯度最小:\theta^* = \operatorname{argmin}_\theta  G(Q, \theta)

递归以上,直至达到最大可允许的深度,N_m < \min_{samples}或者N_m = 1

分类标准

类k在节点m的比例:p_{mk} = 1/ N_m \sum_{x_i \in R_m} I(y_i = k)

Gini不纯度:H(X_m) = \sum_k p_{mk} (1 - p_{mk})

交叉熵:H(X_m) = - \sum_k p_{mk} \log(p_{mk})

误分类:H(X_m) = 1 - \max(p_{mk})

回归标准

c_m = \frac{1}{N_m} \sum_{i \in N_m} y_iH(X_m) = \frac{1}{N_m} \sum_{i \in N_m} (y_i - c_m)^2

函数 函数功能
apply(X[, check_input]) 返回每个样本的叶节点的预测序号
decision_path(X[, check_input]) 返回决策树的决策路径 [n_samples, n_nodes]
fit(X, y[, sample_weight, check_input, ...]) 从训练数据建立决策树,返回一个对象
fit_transform(X[, y]) 将数据X转换[n_samples, n_features_new]
get_params([deep]) 得到估计量的参数,返回一个映射
predict(X[, check_input]) 预测X的分类或者回归,返回[n_samples]
predict_log_proba(X) 预测输入样本的对数概率,返回[n_samples, n_classes]
predict_proba(X[, check_input]) 预测输入样本的属于各个类的概率[n_samples, n_classes]
score(X, y[, sample_weight]) 返回对于测试数据的平均准确率
set_params(**params) 设置估计量的参数
transform(*args, **kwargs) 将输入参数X减少的最重要的特征,返回[n_samples, n_selected_features]

参考文献

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注