【机器学习】二、决策树-CSDN博客

目录

一、决策树定义

二、决策树特征选择

2.1 特征选择问题

 2.2 信息增益

2.2.1 熵

2.2.2 信息增益

三、决策树的生成

 3.1 ID3算法

3.1.1理论推导

3.1.2代码实现

 3.2 C4.5 算法

3.2.1理论推导

​ 3.2.2代码实现

四、决策树的剪枝

4.1 原理

4.2 算法思路

五、CART算法

5.1 CART生成

5.1.1 回归树的生成

5.1.2 分类树的生成

 比较

5.1.3 CART生成算法

5.2 CART剪枝

 六、代码

6.1 代码

6.2 结果

---

一、决策树定义

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点node和有向边directed edge组成。

结点有两种类型内部结点internal node和叶结点leaf node。内部结点表示一个特征或属性叶结点表示一个类。

⚪内部结点

正方形叶结点

二、决策树特征选择

2.1 特征选择问题

特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果用一个特征去分类得到的结果与随机的分类没有很大差别那么这次分类是无意义的。因此我们要选取有意义的特征进行分类。

举个例子吧~

 如上述表格所示决定买房子要不要贷款的因素有年龄、有无工作、有无房子、信贷情况四个因素。那么如何选取合适的特征因素呢

特征选择就是决定用哪个特征来划分特征空间。

       直观上来讲如果一个特征具有更好的分类能力或者说按照各以特征将训练数据集分割成子集使得各个子集在当前条件下有最好的分类那么就应该选择这一特征。  

信息增益information gain就能够很好的表示这一直观准则。

 2.2 信息增益

2.2.1 熵

在统计学中熵是表示随机变量不确定性的度量。

设X是一个取有限个值的离散随机变量其概率分布为

 则随机变量X的熵定义为

其中如果pi =  0则0log0 = 0.

单位为bit或者nat。

上只依赖于X的分布而与X的取值无关所以也可将X的熵记作Hp。

熵越大随机变量的不确定性越大从定义可以验证

 

 信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

2.2.2 信息增益

 

 选择方法

 计算方法

输入训练数据集D和特征值A:

输出特征A队训练数据集D的信息增益g(D,A)

step1计算数据集D的经验熵H(D)

step2计算特征A对数据集D的经验条件熵H(D|A)

step3计算信息增益

 举个栗子吧~

用上面的表计算每个特征的信息增益

 所以A3的信息增益值最大选择A3做最优特征。

三、决策树的生成

 3.1 ID3算法

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

3.1.1理论推导

对上表用ID3算法建立决策树

 

3.1.2代码实现

https://blog.csdn.net/colourful_sky/article/details/82056125

 3.2 C4.5 算法

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

3.2.1理论推导

 3.2.2代码实现

https://www.cnblogs.com/wsine/p/5180315.html

四、决策树的剪枝

4.1 原理

      决策树生成算法递归地产生决策树直到不能继续下去为止。这样产生的结果容易出现过拟合现象。因为这样生成的决策树过于复杂所以我们需要对决策树进行简化——剪枝。

剪枝在决策树学习中将已生成的树进行简化的过程。

本次介绍损失函数最小原则进行剪枝即用正则化的极大似然估计进行模型选择。

公式这里参考李航老师的书

 

4.2 算法思路

五、CART算法

     分类与回归树模型CART, classification and regression tree)是应用广泛的决策树学习方法。

CART由特征选择、树的生成及剪枝组成既可以用于回归也可以用于分类。

5.1 CART生成

step1决策树生成基于训练数据集生成决策树生成的决策树要尽量大。

step2决策树剪枝用验证数据集对已生成的树进行剪枝并选择最优子树这时用损失函数最小作为剪枝的标准。

5.1.1 回归树的生成

回归树用平方误差最小化准则选择特征生成二叉树。

 

5.1.2 分类树的生成

分类树用基尼指数最小化准则选择特征生成二叉树。

 比较

5.1.3 CART生成算法

原理

 例子

还是用上面的的表格吧

step1计算各个特征的基尼指数选择最有特征以及其最优切分点。

step2选择基尼指数最小的特征及其对应的切分点 

5.2 CART剪枝

 六、代码

sklearn中决策树都在‘tree’这个模块中这个模块总共包含五类

tree.DecisionTreeClassifier 分类树
tree.DecisionTreeRegressor 回归树
tree.export_graphviz 画图专用
tree.ExtraTreeClassifier 高随机版本的分类树
tree.ExtraTreeRegressor 高随机版本的回归树

这里用分类树举例子

6.1 代码

   
   

     
     

      
      

     
     
     
     

      
      

       
       #数据准备
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       from sklearn.datasets 
       
       import load_breast_cancer
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       breast_cancer = load_breast_cancer()
      
      
     
     

     
     

      
      

     
     
     
     

      
      
 
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       #分离数据
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       breast_cancer
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       x=breast_cancer.data
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       y=breast_cancer.target
      
      
     
     

     
     

      
      

     
     
     
     

      
      
 
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       #训练数据
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       from sklearn.model_selection 
       
       import train_test_split
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       x_train,x_test,y_train,y_test = train_test_split(x,y,random_state=
       
       33,test_size=
       
       0.3)
      
      
     
     

     
     

      
      

     
     
     
     

      
      
 
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       #数据标准化
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       from sklearn.preprocessing 
       
       import StandardScaler
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       breast_cancer_ss = StandardScaler()
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       x_train = breast_cancer_ss.fit_transform(x_train)
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       x_test = breast_cancer_ss.transform(x_test)
      
      
     
     

     
     

      
      

     
     
     
     

      
      
 
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       #分类树
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       from sklearn.tree 
       
       import DecisionTreeClassifier
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       dtc = DecisionTreeClassifier()
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       dtc.fit(x_train,y_train)
      
      
     
     

     
     

      
      

     
     
     
     

      
      
 
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       dtc_y_predict = dtc.predict(x_test)
      
      
     
     

     
     

      
      

     
     
     
     

      
      
 
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       from sklearn.metrics 
       
       import classification_report
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       k=
       
       0
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       j=
       
       0
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       for i 
       
       in y_test:
      
      
     
     

     
     

      
      

     
     
     
     

      
      
    
       
       if i!=dtc_y_predict[j]:
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
               k=k+
       
       1
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
           j=j+
       
       1
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       print(k)
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       print(
       
       '预测结果:\n',dtc_y_predict)
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       print(
       
       '真是结果:\n:',y_test)
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       print(
       
       'Accuracy:',dtc.score(x_test,y_test))
      
      
     
     

     
     

      
      

     
     
     
     

      
      

       
       print(classification_report(y_test,dtc_y_predict,target_names=[
       
       'benign',
       
       'malignant']))
      
      
     
     
   
   

    
    
   
   
   
   

6.2 结果