统计学习方法--决策树 python实现_在给定数据下,使用平方误差最小原则生成二叉树

决策树模型与学习

决策树模型是一种描述对视力进项分类的树形结构。决策树由节点和有边组成，节点有两种：内部节点和叶节点。内节点表示一个特征或的户型，叶节点表示一个类。

用决策树分类，从根节点开始，对实例的某一特征进行测试，根据测试结构，将实力分配到其子节点；这时每一个子节点对应着该特征的一个取值，如此递归地对实例进行测试并分配，直到达到叶节点，最后将实例分到叶节点的类中。

决策树与if——then规则

 可以讲决策树看成一个if-then规则的集合

将决策树转换成if-then规则的过程：

由决策树的根节点到夜间点每一条路径构建一条规则路径上内部节点的特征对应着规则的条件，而叶节点的类对应着规则的结论 。决策树的路径或对于飞if-then规则集合具有一个重要的性质互斥 并且完备

 

每一个实例都被一条路径活一天规则覆盖只被一条路径或一条规则覆盖

 

决策树还表示给定条件下的条件概率分布

 

决策树学习

决策树学习的目标是根据给定的训练数据集构建一个决策树模型，是他能够对实例进行正确的分类

决策树学习的本质就是行迅雷数据集中归纳出一组分类规则名誉训练数据集不想毛段的决策树，可能有多个  也可能有一个，我们需要的是与训练数据矛盾较小的决策树，同时具有很好的泛化能力。从另一个角度看  决策树学习是由训练数据估计条件概率模型

我们最后选择的天津啊概率模型应该不仅负罪训练数据有很好的拟合，而且对未知数据有很好的预测

决策树学习用损失函数表示这一目标

通常用正则化的 极大似然函数来估计损失函数   决策树的学习策略就是以损失函数为目标函数的最小化。

决策树的学习算法是采用启发式方法，近似求解这一最优化问题，所以得到的结果是次最优

决策树的学习算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类过程，

这一过程对应着对特征空间的划分，也对应着决策树的构建

 

1，  构建根节点将所有训练数据都放在根节点

2，  选择一个最有特征，按照这一特征将训练数据集分割成自己，使得每个子集都有一个在当前条件下最好的分类。

3，  如果这些子集已经能够被基本正确分类，那么构建叶节点

4，  如果还有子集没有被正确分类，那么就对这些子集选择新的最有特征，继续对其进行分割，直到没有合适的特征为止。

5，  最后每个子集都被分到也节点上 就生产了一颗决策树

上面的决策树可能对训练数据有很好的分类能力，但是泛化能力可能很差，即发生了过拟合现象，我们需要对已生产的树进行修剪

如果特征数量很多也可以在决策树学习的开始就对特征进行选择，值选择对训练数据有足够分类能力的特征

决策树的学习算法包含特征选择，决策树生成   决策树修剪三个过程

特征的选择：

决策树学习应用信息增益准确来选择特征，跟定的训练数据集D和特征A，经验熵H（D）表示对数据集D进行分类的不确定性，而经验条件熵H（D|A）表示在特征A给定的条件下对数据集进行分类的不确定性。他们的差就是信息增益，就表示由于特征A而使对数据集D的分类的不确定性减少的程度

对于数据集D而言，信息增益依赖于特征，不同特征问问具有不同的信息增益，信息箱增益大的特征具有更强的分类能力

方法：对训练数据集或者其子集，计算没个特特征的信息增益，并比较他们的大小，选择信息增益最大的特征。

 

信息增益比

信息增益值的大小是相对于训练数据集而言的，并没有绝对的意义，当分类问题困难时也就是训练数据集的经验熵大的时候，信息增益值会偏大，繁殖信息增益值会偏下，使用信息增益比可以对这一问题进行校正

 

决策树的生成

ID3

核心是在决策树各个节点上应用信息增益准则选择特征，递归地构建决策树。

具体步骤：从根节点（root node）开始，对节点计算多有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，对由该特征的不同取值建立子节点；再对子节点递归地调用以上方法，构建决策树；知道所有特征的信息增益均很小或没有特征可以选择位置。最后得到一个决策树。

相对于用极大似然法进行概率模型的选择

ID3算法只有数的生成，所以该算法生成的树容易产生过拟合。

 

二、C4.5的生成算法

C4,5算法与ID3算法相似，C4.5算法对ID3算法进行了改进。C4.5在生成的过程中，用信息增益比来选择特征

 

 

 

 

 

决策树的剪枝

决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但是对位置的测试数据的分类却没有那么准确，即出现过拟合现象，过拟合的原因在于学习时过多地考虑如何提高训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法就是考虑决策树的复杂度，对已生成的决策树进行简化，

在决策树学习中将已生成决策数据的简化过程称为剪枝pruning。

剪枝从已生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶节点，从而简化分类树模型。

决策树的剪枝往往通过及消化决策树整体的而损失函数LOSS FUNCTION或代价函数cost function来实现，设树T的叶节点个数为|T|，t是树T的叶节点，该叶节点有个样本点，其中K类的样本点有个，k=1,2，…K，其中为叶节点t上的经验熵，α≥0为参数，则决策树学习的损失函数可以定义为

C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表示模型复杂度，参数α≥0控制两种之间的影响，较大的α促使选择较简单的树，较小的α促使选择较复杂的树。α=0意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。

剪枝就是当α确定时，选择损失函数最小的模型，即损失函数最小的子树。当α值确定时，子树越大，往往与训练数据的拟合越好，但是模型的复杂度就越高；相反，子树越小，模型的复杂度就越低，但是往往与训练数据的拟合不好，损失函数正好表示了对两者的平衡。

决策树生成只考虑了通过提高信息增益或者信息增益比对训练数据进行更好的拟合。而决策树剪枝通过优化损失函数还考虑了见笑模型复杂度。决策树生成学习局部的模型，而决策树剪枝学习整体的模型。

公式1和4定义的损失函数的极小化等价于正则化的极大似然估计。所以，利用损失函数最小化原则进行剪枝就是用正则化的极大似然估计进行模型选择。

树的剪枝算法

输入：生成算法产生的整个树T，单数α；

输出：修剪后的子树

三、CART算法

分类classification与回归树regression tree模型是一种广泛的决策树学习方法们CART同样由特种选择、树的生成及剪枝组成，既可以用于分类也可以用于回归

CART是在给定输入随机变量C条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二分叉，内部节点特种的取值为“是”“否，左侧分支是趋势为“是”的分支，，有分支是取值为“否”的分支。这样的决策树等价于递归地微分每个特征，将输入控件即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布

CART算法由两步组成：

1决策树的生成  基于训练数据及生成决策树，生成 的决策树要尽量大；

2决策树剪枝：用验证数据及对已生成的树进行剪枝并选择最优子树，这是用损失函数最小作为剪枝的标准

CART生成

决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数GINI Index最小化准则，进行特征选择，生成二叉树，

选择第j个变量和他的取值作为切分变量和切分点，并定义两个区域，

划分为两个区域。接着，对每个区域重复上述划分过程，直到满足停止条件为止，这样就生产了一颗回归树。这样的回归树通常称为最小二乘法回归树。

算法叙述（最小二乘回归树生产算法）如下：

 

2分类树的生成

分类树使用基尼指数选择最优特征，同时决定该特征的最优二值切分点。

什么是基尼系数？

分类问题中，假设有K个类，样本点属于第K类的概率为，则概率分布的基尼系数定义为：

对于二分类问题，若样本点属于第1个类的概率为P，则概率分布的基尼系数为

对于给定的样本集合D，其基尼指数为

这里是D中属于第K类的样本集，K是类的个数。

 

上图显示二分类问题中基尼系数Gini（p）、熵之半和二分类误差率的关系，基尼系数与熵之半的曲线很接近。

CART生成算法

输入：训练数据集D，停止计算的条件

输出：CART决策树

CART剪枝

 

CART的剪枝算法从“完全生长”的决策树的底端减去一些子树，是决策树变小，从而能够对位置数据有更准确的预测。

CART剪枝算法分两步：1 从生成算法产生的决策树的底端开始不断剪枝，知道其根节点形成一个子树序列；2通过交叉验证法在独立的验证数据集上对子树序列进行测试，从而选择最优子树

# -*- coding: utf-8 -*-
"""
Created on Mon Oct 23 16:24:07 2017
@author: lizheng
"""
 
# 引入必要的模型和库
from sklearn.tree import DecisionTreeClassifier
from sklearn import tree
 
from sklearn.externals.six import StringIO
import pydotplus
 
    
    
   
with open('D:\Iris.txt', 'r') as f:  
    iris = [inst.strip().split(',') for inst in f.readlines()]  
    lenses_target = []
    lenses_data = []
    for line in iris:  
        lenses_target.append(line[-1])
        lenses_data.append(line[:3])
from sklearn.cross_validation import train_test_split  #这里是引用了交叉验证          
X_train,X_test, y_train, y_test = train_test_split(lenses_data,lenses_target, random_state=1)#将数据随机分成训练集和测试集  
# =============================================================================
# print(X_train)  
# print(X_test)
# print(y_train)  
# print(y_test)
# =============================================================================
# 解析数据，获得 features 数据
#clf = DecisionTreeClassifier()
 
clf = DecisionTreeClassifier()  
clf = clf.fit(X_train, y_train)  
dot_data = StringIO()
tree.export_graphviz(clf, out_file = dot_data,                            #绘制决策树
                   
                    class_names = clf.classes_,
                    filled=True, rounded=True,
                    special_characters=True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
graph.write_pdf("D:\\MLiA_SourceCode\\machinelearninginaction\\Ch03\\tree2.pdf")
 
from sklearn.model_selection import cross_val_score#交叉验证模块
scores =cross_val_score(clf,X_test, y_test,cv=10)#验证评估  cv 迭代次数 
print(scores.mean())#平均精确度
 
# =============================================================================
# pre_labels=clf.predict(X_test)  
# print(pre_labels)
# =============================================================================
#手动计算正确率
import numpy  as np
CorrectNnumber = 0
 
for i in  range(len(X_test)):
    if clf.predict(np.array(X_test[i]).reshape((1,-1))) == y_test[i]:
# =============================================================================
#  此处predict()参数要求是数组，所系需要把列别predictions转换成数组，
#  然后把把一维数组通过reshape改造 ，否则会有报警     
# =============================================================================
        CorrectNnumber+=1
        
print("正确率为：",CorrectNnumber/len(X_test))
 
import numpy  as np
CorrectNnumberX = 0
for j in  range(len(lenses_data)):
    if clf.predict(np.array(lenses_data[j]).reshape((1,-1))) == lenses_target[j]:
        CorrectNnumberX+=1
print("正确率为：",CorrectNnumberX/len(lenses_data))
# =============================================================================
# recall_score
# 召回率 =提取出的正确信息条数 /样本中的信息条数。通俗地说，就是所有准确的条目有多少被检索出来了。
# 形式：
# klearn.metrics.recall_score(y_true, y_pred, labels=None, pos_label=1,average='binary', sample_weight=None)
# 参数average : string, [None, ‘micro’, ‘macro’(default), ‘samples’, ‘weighted’]
# 将一个二分类matrics拓展到多分类或多标签问题时，我们可以将数据看成多个二分类问题的集合，每个类都是一个二分类。接着，我们可以通过跨多个分类计算每个二分类metrics得分的均值，这在一些情况下很有用。你可以使用average参数来指定。
# macro：计算二分类metrics的均值，为每个类给出相同权重的分值。当小类很重要时会出问题，因为该macro-averging方法是对性能的平均。另一方面，该方法假设所有分类都是一样重要的，因此macro-averaging方法会对小类的性能影响很大。
# weighted:对于不均衡数量的类来说，计算二分类metrics的平均，通过在每个类的score上进行加权实现。
# micro：给出了每个样本类以及它对整个metrics的贡献的pair（sample-weight），而非对整个类的metrics求和，它会每个类的metrics上的权重及因子进行求和，来计算整个份额。Micro-averaging方法在多标签（multilabel）问题中设置，包含多分类，此时，大类将被忽略。
# samples：应用在multilabel问题上。它不会计算每个类，相反，它会在评估数据中，通过计算真实类和预测类的差异的metrics，来求平均（sample_weight-weighted）
# average：average=None将返回一个数组，它包含了每个类的得分. 
# =============================================================================
from sklearn.metrics import recall_score
recall_score(y_train, clf.predict(X_train),average='macro')  
# =============================================================================
# accuracy_score
# 分类准确率分数是指所有分类正确的百分比。分类准确率这一衡量分类器的标准比较容易理解，但是它不能告诉你响应值的潜在分布，并且它也不能告诉你分类器犯错的类型。
# 形式：
# sklearn.metrics.accuracy_score(y_true, y_pred, normalize=True, sample_weight=None)
# normalize：默认值为True，返回正确分类的比例；如果为False，返回正确分类的样本数
# =============================================================================
from sklearn import metrics
print(metrics.accuracy_score(y_test, clf.predict(X_test)))