02.决策树算法(decision tree)
1.决策树算法
1. 机器学习中分类和预测算法的评估：
准确率
速度
强壮性：一个算法有一些关键值缺失的情况下，这个算法还能不能表现的非常好
可规模性：一个算法不仅在小规模数据上的表现，当数据呈指数增长还能不能规模化。
可解释性：算法做出一些特征值的选择和归类能不能符合我们的观察和研究，能否易于解释。
2. 什么是决策树/判定树（decision tree)?
判定树是一个类似于流程图的树结构：其中，每个内部结点表示在一个属性上的测试
每个分支代表一个属性输出（三个分支，sunny，overcast，rain三个输出）
每个树叶结点代表类或类分布（第三行为树叶）
树的最顶层是根结点（第一行为根节点）
3. 机器学习中分类方法中的一个重要算法
4. 构造决策树的基本算法
4.1 熵（entropy）概念：（念shang）
信息和抽象，如何度量？
1948年，香农提出了 ”信息熵(entropy)“的概念
一条信息的信息量大小和它的不确定性有直接的关系，要搞清楚一件非常非常不确定的事情，或者是我们一无所知的事情，需要了解大量信息==>信息量的度量就等于不确定性的多少
例子：猜世界杯冠军，假如一无所知，猜多少次？（世界杯有三十二支球队）
编号1-32，采用二分法，五次能猜出来。
比特(bit)（0或1）来衡量信息的多少
如果每一个队夺冠几率相等，都是1/32，刚好等于6，如果夺冠几率不等，那么最后是比6要小的。
变量的不确定性越大，熵也就越大
4.2 决策树归纳算法 （ID3）
1970-1980， J.Ross. Quinlan, ID3算法
选择属性判断结点是一个非常重要的问题
信息获取量(Information Gain)：Gain(A) = Info(D) – Infor_A(D)
通过A来作为节点分类获取了多少信息（没有它和有它的差）
类似，Gain(income) = 0.029, Gain(student) = 0.151, Gain(credit_rating)=0.048
所以，选择age作为第一个根节点
重复……信息熵最大的成为结点
算法：
树以代表训练样本的单个结点开始（步骤1）。
如果样本都在同一个类，则该结点成为树叶，并用该类标号结束（步骤2 和3）。
否则，算法使用称为信息增益的基于熵的度量作为启发信息，选择能够最好地将样本分类的属性（步骤6）。该属性成为该结点的“测试”或“判定”属性（步骤7）。在算法的该版本中，
所有的属性都是分类的，即离散值。连续属性必须离散化。
对测试属性的每个已知的值，创建一个分枝，并据此划分样本（步骤8-10）。
算法使用同样的过程，递归地形成每个划分上的样本判定树。一旦一个属性出现在一个结点上，就不必该结点的任何后代上考虑它（步骤13）。
递归划分步骤仅当下列条件之一成立停止：
(a) 给定结点的所有样本属于同一类（步骤2 和3）。
(b) 没有剩余属性可以用来进一步划分样本（步骤4）。在此情况下，使用多数表决（步骤5）。
这涉及将给定的结点转换成树叶，并用样本中的多数所在的类标记它。替换地，可以存放结点样本的类分布。
(c) 分枝
test_attribute = a i 没有样本（步骤11）。在这种情况下，以 samples 中的多数类
创建一个树叶（步骤12）
4.3 其他算法：
C4.5算法: Quinlan
Classification and Regression Trees (CART)算法: (L. Breiman, J. Friedman, R. Olshen, C. Stone)
共同点：都是贪心算法，自上而下(Top-down approach)
区别：属性选择度量方法不同：
C4.5算法 （gain ratio)
CART算法(gini index),
ID3 (Information Gain)：利用信息增益，信息获取度获取增益
4.4 如何处理连续性变量的属性？
将连续变量离散化
5. 树剪枝叶 （避免overfitting)
Overfitting：训练集分支过细，在测试集的表现可能会不好。
5.1 先剪枝：分到一定程度就不向下分了。
5.2 后剪枝：分好之后，将后面的树叶剪掉。
6. 决策树的优点：
直观，便于理解，小规模数据集有效
7. 决策树的缺点：
处理连续变量不好：连续需要离散化，阈值选择可能不是特别准确。
类别较多时，错误增加的比较快
可规模性一般：数据集大了，算法复杂度增加的非常大。
Program：编程的方法
2.决策树(decision tree)应用
1. Python
2. Python机器学习的库：scikit-learn
2.1： 特性：
简单高效的数据挖掘和机器学习分析
对所有用户开放，根据不同需求高度可重用性
基于Numpy, SciPy和matplotlib
开源，商用级别：获得 BSD许可
2.2 覆盖问题领域：
分类（classification)
回归（regression)
聚类（clustering)
降维(dimensionality reduction)
模型选择(model selection)
预处理(preprocessing)
3. 使用用scikit-learn
安装scikit-learn: pip, easy_install, windows installer
安装必要package：numpy， SciPy和matplotlib， 可使用Anaconda (包含numpy, scipy等科学计算常用package）
安装注意问题：Python解释器版本（2.7 or 3.4？）, 32-bit or 64-bit系统
4. 例子：
文档： http://scikit-learn.org/stable/modules/tree.html
解释Python代码
安装 Graphviz： http://www.graphviz.org/
配置环境变量
转化dot文件至pdf可视化决策树：dot -Tpdf iris.dot -o outpu.pdf
代码如下：
from sklearn.feature_extraction import DictVectorizer #输入格式上的一些要求 import csv #原始文件存储在csv文件中，csv与程序在一个文件夹。 from sklearn import preprocessing from sklearn import tree # 决策树 #from sklearn.externals.six import StringIO #读写的过程 data = open(\'jueceshu.csv\', \'rt\')#数据读取 reader = csv.reader(data) headers = next(reader) print(headers) #RID\', \'age\', \'income\', \'student\', \'credit_rating\', \'class_buys_compute\'] featureList = [] # 特征集 labelList = [] # 标签集 for row in reader: # 最后一列是标签,构造标签集 labelList.append(row[len(row) - 1]) # 构造特征集 rowDict = {} for i in range(1, len(row) - 1): # header里面是属性名，用来作键值 rowDict[headers[i]] = row[i] featureList.append(rowDict) print(featureList) # 一行行打印出来 vec = DictVectorizer() # 将特征转化为向量 dummyX = vec.fit_transform(featureList).toarray() print(\'dummyX:\' + str(dummyX)) # 输出向量中每一项的含义 print(vec.get_feature_names()) print(\'labelList:\' + str(labelList)) # 将标签变成列向量 lb = preprocessing.LabelBinarizer() dummyY = lb.fit_transform(labelList) print(\'dummyY:\' + str(dummyY)) # 利用tree中的分类器来创建决策树 clf = tree.DecisionTreeClassifier(criterion=\'entropy\') # 用ID3的算法 信息熵大小 #clf 是指分类器 clf = clf.fit(dummyX, dummyY) print(\'clf:\' + str(clf)) # 画决策树 with open(\'jueceshu.dot\', \'w\') as f: # 把feature_name返回 f = tree.export_graphviz(clf, feature_names=vec.get_feature_names(), out_file=f) oneRowX = dummyX[0, :].reshape(1, -1) print(\'oneRowX:\' + str(oneRowX)) # 构造新的情况，并预测 newRowX = oneRowX newRowX[0][0] = 0 newRowX[0][2] = 1 newRowX.reshape(1, -1) print(\'newRowX:\' + str(newRowX)) # 用模型预测 predictedY = clf.predict(newRowX) print(\'predictedY:\' + str(predictedY))