决策树算法原理(分类树)及实现

简单介绍

  机器学习主要分为俩大类：分类问题和回归问题。决策树是常用的分类学习算法，当然也能用于处理回归问题，同时也适合集成学习比如随机森林，作为机器学习的入门算法今天简单介绍一下决策树算法的原理和实现(python)

决策树的特点：

• 优点
• 1. 决策树易于理解和实现。
• 2. 对于决策树，数据的准备往往是简单或者是不必要的，而且能够同时处理数据型和常规型>属性，在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
• 3. 易于通过静态测试来对模型进行评测，可以测定模型可信度;如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。
• 缺点
• 1. 对连续性的字段比较难预测，需要对连续数据做分段处理。
• 2. 对有时间顺序的数据，需要很多预处理的工作。
• 3. 当类别太多时，错误可能就会增加的比较快。
• 4. 一般的算法分类的时候，只是根据一个字段来分类。

常用的算法:

信息熵(Entropy)

就是一组数据包含的信息，概率的度量。一个信息越是确定那他的信息熵就越低，列如信息：今天中午在你家吃饭。这条信息基本可以确定了今天中午在你家吃饭只一种可能，则信息熵的值低。另一个信息：过几天在你家或者我加吃饭。这条消息过几天是几天，在你家还是在我家，不确定性高，者他的信息熵越高。也就是说：在信息论中，变量的不确定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大。信息熵是信息论中用于度量信息量的一个概念。一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。所以，信息熵也可以说是系统有序化程度的一个度量。

定义：假设随机变量X的可能取值有x1，x2， ... , xn
对于每一个可能的取值xi，其概率 P(X=xi) = pi , ( i = 1,2, ... , n)
因此随机变量X的熵：

H(x) = \sum_{i=1}^n-p(x)log_2P(x)
信息熵(entroy)公式
对上面样本集合D来说，随机变量X是样本的类别，即，假设样本有K个类别，每个类别的概率是，其中|Dk|表示类别k的样本个数，|D|表示样本总数则对于样本集合D来说熵（条件熵）为：

H(D) = -\sum_{k=1}^K\frac{|D_k|}{|D|}log_2\frac{|D_k|}{|D|}

但是光有熵还不够通常在算法中要找到一个用来衡量一个属性对熵的影响，这就出现了信息增益。

ID3算法——信息增益（Information gain)

信息增益（information gain）这个概念，用Gain(D)表示，该概念是指信息熵的有效减少量，该量越高，表明目标属性在该参考属性那失去的信息熵越多。

定义：以某特征划分数据集前后的熵的差值。

划分前样本集合D的熵是一定的，entroy(前)，使用某个特征A划分数据集D，计算划分后的数据子集的熵 entroy(后)：
信息增益 = entroy(前) - entroy(后)

G(D,A) = H(D)-H(D/A)
用法：计算使用所有特征划分数据集D，得到多个特征划分数据集D的信息增益，从这些信息增益中选择最大的，因而当前结点的划分特征便是使信息增益最大的划分所使用的特征。
信息增益的理解：对于待划分的数据集D，其 entroy(前)是一定的，但是划分之后的熵 entroy(后)是不定的，entroy(后)越小说明使用此特征划分得到的子集的不确定性越小（也就是纯度越高），因此 entroy(前)-entroy(后)差异越大，说明使用当前特征划分数据集D的话，其纯度上升的更快。而我们在构建最优的决策树的时候总希望能更快速到达纯度更高的集合，这一点可以参考优化算法中的梯度下降算法，每一步沿着负梯度方法最小化损失函数的原因就是负梯度方向是函数值减小最快的方向。同理：在决策树构建的过程中我们总是希望集合往最快到达纯度更高的子集合方向发展，因此我们总是选择使得信息增益最大的特征来划分当前数据集D。

缺点

• ID3不能处理连续数据的属性
• ID3不能处理有属性缺失的样本
• 容易产生过度拟合
• 算法一般会优先选择较多属性值的特征，因为属性多的特征会有相对较大的信息增益

4.5算法——信息增益比

信息增益比= 惩罚参数*信息增益

G_r(D,A)=\frac{G_r(D,A)}{H_A(D)}
其中的HA(D)，对于样本集合D，将当前特征A作为随机变量（取值是特征A的各个特征值），求得的条件熵。
信息增益比的本质：是在信息增益的基础上乘上一个惩罚参数。特征个数较多是，惩罚参数较小；特征个数较少时，惩罚参数较多。从上面的公式可以看出：

\text{惩罚参数}=\frac{1}{H_A(D)}
优点

• 解决了ID3偏向特征较多的属性值的特征。

CART算法——基尼指数

经济学中基尼（GINI）指数：

1. 是一种不等性的度量
2. 通常用来度量收入不平等，也可以用来度量任何不均匀分布
3. 是介于0~1之间的书，0-完全相等，1-完成不等
4. 总体内包含的类别越杂乱，GINI指数就越大

基尼指数
在CRAT算法中，基尼不纯度指数表示一个随机选中的样本在子集中被分错的可能性。基尼不纯度为这个样本被选中的概率乘以被分错的概率。当一个节点的所有样本都是一个类是，基尼不纯度为0。
基尼指数 = 样本被选中的概率*样本被分错的概率

Gini(p) = \sum_{k=1}^kp_k(1-p_k)=1-\sum_{k=1}^kp_k^2
说明：

1. Pk表示选中的样本中属于K的类别的概率，则这个样本被分错的概率是1-Pk
2. 样本集合中有K个类别，一个随机选中的样本可以属于K个类别中的一个，因而可以对类别求和
   样本集合D的Gini指数：假设集合中有K个类别，则：

Gini(D)=1-\sum_{k=1}^k(\frac{|C_k|}{|D|})^2
基于特征A划分样本集合D之后的基尼指数：

CART是个二叉树，也就是说基于某个特征划分集合只有2个子集：

1. 等于给定特征的样本集合D1
2. 不等于给定的特征值 的样本集合D2

Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)
因而对于一个具有多个取值（超过2个）的特征，需要计算以每一个取值作为划分点，对样本D划分之后子集的纯度Gini(D,Ai)，(其中Ai 表示特征A的可能取值)
然后从所有的可能划分的Gini(D,Ai)中找出Gini指数最小的划分，这个划分的划分点，便是使用特征A对样本集合D进行划分的最佳划分点。

优点

• 分类规则清晰，结果容易理解
• 计算量小，实现速度快
• 不需要预选变量，可以处理异常值，缺失值，不同量纲的值

算法实现

这里只介绍ID3算法的代码封装，C4.5和CART算法自己翻翻书基本过程和ID3类似只是选择划分标准不同而已。

案列介绍：此例子来自Tom M.Mitchell著的机器学习一书： 小王的目的是通过下周天气预报寻找什么时候人们会打高尔夫，他了解到人们决定是否打球的原因最主要取决于天气情况。而天气状况有晴，云和雨；气温用华氏温度表示；相对湿度用百分比；还有有无风。如此，我们便可以构造一棵决策树，如下（根据天气这个分类决策这天是否合适打网球）：

Outlook	Temperature	Humidity	Windy	PlayGoIf?
sunny	85	85	FALSE	no
sunny	80	90	TRUE	no
overcast	83	86	FALSE	yes
rainy	70	96	FALSE	yes
rainy	68	80	FALSE	yes
rainy	65	70	TRUE	no
overcast	64	65	TRUE	yes
sunny	72	95	FALSE	no
sunny	69	70	FALSE	yes
rainy	75	80	FALSE	yes
sunny	75	70	TRUE	yes
overcast	72	90	TRUE	yes
overcast	81	75	FALSE	yes
rainy	71	95	TRUE	no

树形结构

算法过程：

1. 搜集数据
2. 准备数据
3. 分析数据
4. 训了算法
5. 测试算法
6. 使用算法

代码如下

#! usr/bin/env
#coding=utf-8
from math import log
import numpy as np
import operator
import pandas as pd

# 数据准备
filename = 'data.csv'
def creatDataSet(filename):
    df = pd.DataFrame(pd.read_csv(filename))
    # 数据转换将属性转化为0,1标称数据类型
    outLook_mapping = {label: idx for idx, label in enumerate(set(df['Outlook']))}
    windy_mapping = {label: idx for idx, label in enumerate(set(df['Windy']))}
    play_mapping = {label: idx for idx, label in enumerate(set(df['PlayGoIf?']))}
    df['Outlook'] = df['Outlook'].map(outLook_mapping)
    df['Windy'] = df['Windy'].map(windy_mapping)
    df['PlayGoIf?'] = df['PlayGoIf?'].map(play_mapping)
    numberOfLines = len(df)
    # 数据矩阵初始化
    dataSet = np.zeros((numberOfLines, 5))
    # 类别数组初始化
    classLabelVector = []
    classLabelVector.extend(df.columns[0:4])
    index = 0
    for row in df.values:
        dataSet[index, :] = row[0:5]
        index += 1
    return list(dataSet),classLabelVector

# 计算给定数据集合的香农熵
def calcShannonEnt(dataset):
    numEntries = len(dataset)
    # 空字典用于统计类别
    labelCounts = {}
    for featVec in dataset:
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key]) / numEntries #使用频率pi
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt

#按照给定特征划分数据集
def splitDataSet(dataSet, axis, value):
    retDataSet = []
    for featVecn in dataSet:
        featVec = list(featVecn)
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

#选择最好的数据集划分方式
def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1
    basicEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0; bestFeature = -1
    for i in range(numFeatures):        #计算每一个特征的熵增益
        featlist = [example[i] for example in dataSet]
        uniqueVals = set(featlist)
        newEntropy = 0.0
        for value in uniqueVals:        #计算每一个特征的不同取值的熵增益
            subDataSet = splitDataSet(dataSet, i, value)
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet) #不同取值的熵增加起来就是整个特征的熵增益
        infoGain = basicEntropy - newEntropy
        if (infoGain > bestInfoGain):   #选择最高的熵增益作为划分方式
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

#选择出类别出现最多的分类
def majorityCnt(classList):
    classCount={}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

def createTree(dataSet, labels):
    classList = [example[-1] for example in dataSet]
    if classList.count(classList[0]) == len(classList): #停止条件一：判断所有类别标签是否相同，完全相同则停止继续划分
        return classList[0]
    if len(dataSet[0]) == 1:    #停止条件二：遍历完所有特征时返回出现次数最多的
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)    #得到列表包含的最佳属性值
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree


dataSet, labels = creatDataSet(filename)
myTree = createTree(dataSet, labels)
print(myTree)

可以使用Matplotlib对其进行可视化处理，pickle对生产的树进行存储