机器学习--决策树和随机森林简介

基本介绍

    决策树是在数据挖掘中一种比较有效的算法。简单理解就是根据数据集中的特征值信息逐步分支，其每一个非叶子节点分支类似if-else结构，叶子节点对应分支结果，逐步分支直到不可分的节点或自定义的节点，整个决策过程最后形成了一棵倒立的树冠。

       决策树是一种监督学习算法，有分类和回归两种方法，本文主要以分类过程做介绍。决策树可适用的数据类型有数值型和标称型，通常是样本使用数值型，决策结果可以是数值或标称型。

 

名词解说

    信息熵(Entropy)    熵定义为信息的期望值，信息熵是样本集合纯度的指标，即信息熵值越小，其样本集合的纯度越高

    信息增益         样本在划分前后信息熵之差

    信息增益率     以特征  作为分隔节点时的信息增益除以 特征 的“固有值”

    基尼值 (Gini)   类似信息熵,也是样本集合纯度的度量指标,即基尼值 越小,则样本集合的纯度越高

    决策树剪枝    决策树容易形成过拟合，因而需要对树进行剪枝，通常剪枝有向前或向后剪枝 

    更多详细解释及相关公式参考 http://blog.****.net/cxmscb/article/details/53541224

 

算法分类

    目前主要有这几个版本ID3, C4.5/C5.0 和CART,  其中C4.5是继承ID3，C5.0是C4.5的升级版，CART和C4.5类似，主要不同是在回归方法中支持数值标称变量。在sklearn的DecisionTreeClassifier使用的是优化的CART算法。

  

建造一棵树的基本过程

      数据集准备      将准备的数据做好预处理，需要将样本数据转换为数值型

      数据集分析      特征选择，从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，

                 如何选择特征根据数据集有着很多不同量化评估标准标准，比如

                              ID3： 使用信息增益g(D,A)进行特征选择 
                              C4.5：使用信息增益率,公式为 信息增益率=g(D,A)/H(A) 
                              CART：使用基尼系数 

                             根据不同评估标准从而衍生出不同的决策树算法。

      构造决策树    根据选择的特征评估标准，从上至下递归地生成子节点，

               直到数据集不可分则停止决策树停止生长。

      对树进行测试   测试前通常需要对树进行剪枝，由于决策树容易过拟合，一般需要进行剪枝操作，

                 缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种

      树模型使用     将训练测试好的树模型保存以用于数据分析

 

树模型优缺点和应用

    优点  

       计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关的特征数据。

       效率高,决策树只需要一次构建,就可以反复使用,每一次预测的最大计算次数不超过决策树的深度。

    缺点  

    准确度不高，方差过大，另外容易产生过度拟合(Over fitting )

    应用 

    如邮件分类，银行贷款决策，根据天气预测活动等等

  

随机森林

    随机森林可以简单理解为bagging 策略 + 决策树

       Bagging( bootstrap aggregation)的策略：从样本集中进行有放回地选出n个样本；在样本的所有特征上，对这n个样本建立分类器；重复上述两步m次，获得m个样本分类器； 最后将测试数据都放在这m个样本分类器上，最终得到m个分类结果，再从这m个分类结果中决定数据属于哪一类。

    随机森林在一定程序上提高了泛化能力，而且可以并行地生成单棵树，与bagging策略相比，他做了些调整， 如下：

      1. 从训练样本集中使用Bootstrap采样（随机有放回）选出n个样本。

      2. 假如样本共有b个特征，从这b个特征中只随机选择k个特征来分割样本，通过计算选择最优划分特征作为节点来划分样本集合来建立决策树。（与Bagging的不同之处：没有使用全部的特征，这样可以避免一些过拟合的特征，不再对决策树进行任何剪枝）

     3. 重复以上两步m次，可建立m棵决策树 这m棵决策树形成了森林，可通过简单多数投票法（或其他投票机制）来决定森林的输出，决定属于哪一类型。（针对解决回归问   题，可以采用单棵树输出结果总和的平均值）

 

     建立决策树模型有两种方法，一种是根据其原理自己造*，另外一种是直接调用 klearn库中的DecisionTreeClassifier。关于自己造*过程代码比较多，主要来自于《机器学习实战》，具体代码可以参考Github链接：建立决策树模型代码

 

    造*代码建模过程有这几部分，一是建树，二是利用Matplotlib画图，三是测试模型，四是保存模型

      建树部分的过程包括以下几个函数：

      1. 建立数据集

      2. 计算数据集的信息熵

      3. 按照给定特征划分数据集     

      4. 选择最好的数据集划分方式

      5. 采用递归创建决策树

      6. 对创建好树进行分类

      Matplotlib画图包括函数：

      1. 使用文本注解绘制数节点

      2. 获取叶节点的数目和树层数

      3. 画树的结构图

以下介绍是直接调用sklearn库中的DecisionTreeClassifier和RandomForestClassifier模型来测试

使用数据集 黄色标识部分作为测试数据集：

ID	Refund	MaritalStatus	TaxableIncomeK	Cheat
1	Yes	Single	125	No
2	No	Single	100	No
3	No	Single	70	No
4	Yes	Married	120	No
5	No	Divorced	95	Yes
6	No	Married	60	No
7	Yes	Divorced	220	No
8	No	Single	85	Yes
9	No	Married	75	No
10	No	Single	90	Yes
11	No	Married	110	No
12	Yes	Married	90	Yes
13	No	Single	95	No
14	Yes	Divorced	80	Yes
15	No	Single	80	No
16	Yes	Married	105	No

程序代码如下：

#_*_coding:utf-8_*_
'''
Version: 0.1.0
Date: 2017-11-10
@Author: Cheney
'''


# Decision Tree and Random Forest Classifier model
# Part I
import time
import graphviz
import numpy as np
import pandas as pd

from sklearn import tree
from sklearn.tree import DecisionTreeClassifier,export_graphviz
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import train_test_split
from sklearn.model_selection import cross_val_score


#Read data from "m02_tree_data.csv" and transfer them as array type
csvData = pd.read_csv("m02_tree_data.csv")
dataTrans = csvData[['Refund','MaritalStatus','TaxableIncomeK']]
dataTrans  = [csvData.ix[idx,:] for idx in csvData.index]

#Create a dict to use for converting dataTrans' string to integer
covDict = {'Yes':1, 'No':0,'Married':2,'Single':1,'Divorced':0}
x = []
for idx in range(len(dataTrans)):
    s = list(dataTrans[idx])
    # Get the integer value from dataTrans's string through covDict
    value = [covDict.get(arr) for arr in s[1:3]]
    tax = np.array(csvData['TaxableIncomeK'][idx])
    value.append(int(tax))
    # Get the datasets x list
    x.append(value)

y  = [csvData.ix[idx,-1] for idx in csvData.index]
#Due to only 16samples sets, it will use the first 12 samples for training data and the last four for testing
# x_train, x_test, y_train, y_test = train_test_split(x,y, test_size=0.4,random_state=1)
x_train, x_test, y_train, y_test = x[:12], x[-4:], y[:12],y[-4:]

#Part II Built the tree and fix it
modelDict = {'DTC':DecisionTreeClassifier(criterion='entropy',random_state=3),
             'RFC':RandomForestClassifier(n_estimators=10,criterion='entropy',

                   bootstrap=True,n_jobs=2,random_state=3)}
for k, model in modelDict.items():
    mod = model.fit(x_train, y_train)
    score = mod.score(x_train, y_train)
    prob = mod.predict(x_test)
    croScore = cross_val_score(mod, x_train, y_train,scoring='accuracy', cv=4)

    if k == 'DTC':
        dt_mod = mod
    print('%s Model train score %s' %(k,score))
    print('%s Model cross validation train score %s' %(k,croScore))
    print('%s Model predict probability %s' %(k, prob))


#Part III Use graphviz to plot the tree of DecisionTreeClassifier model
feaName = 'Refund','MaritalStatus','TaxableIncomeK'
className = 'Yes', 'No'
treeData = export_graphviz(dt_mod, out_file=None, feature_names=feaName, class_names=className,
                                filled=True, rounded=True, special_characters=False)
grap = graphviz.Source(treeData)
grap.save('dt_tree')
grap.view('dt_tree')

运行程序输出结果：

DTC Model train score 1.0
DTC Model cross validation train score [ 0.66666667  1.          1.          1.        ]
DTC Model predict probability ['Yes' 'No' 'No' 'No']

RFC Model train score 1.0
RFC Model cross validation train score [ 0.66666667  1.          1.          0.66666667]
RFC Model predict probability ['Yes' 'No' 'No' 'No']

输出的决策树图形

温馨提示:  画图需要安装graphviz包,咱用Winds10+Anaconda,安装只需在运行界面输入conda install graphviz 

安装好后 将C:\Anaconda\Library\bin\graphviz 配置到环境变量中即可

声明：

本文参考了一些资料和博客，引用原著中内容比较少的则没有列出原著，还请原著作者海涵。