机器学习基础-决策树&随机森林

• 利用特征生成子节点，进行判断实例属性

1 ID3算法

• ID3算法是在每个节点处选取能获得最高信息增益的分支属性进行分裂，就是每一次找到最重要的属性进行分类
• 在每个决策节点处划分分支、选取分支属性的目的，是将整个决策树的样本纯度提升，就是保证每个分支节点下下对应的分类都是唯一的。
• 衡量样本集合纯度的指标是熵

1.1 熵和信息增益

熵和信息增益是生成节点的主要依据。

1.1.1 熵

熵在物理学中表示分子运动的不确定性的状态，pi表示状态的概率
熵的定义：
$\large Entropy(S) = -\sum_{i=1}^k{p_i\log_2(p_i)},\space p_i = \frac{|C_i|}{n}$Entropy(S)=−i=1∑k​pi​log2​(pi​), pi​=n∣Ci​∣​

• $k$k是可能出现的k种状态
• $C_i$Ci​表示状态$\large i$i的出现的次数
• 计算熵时，约定若$p=0$p=0，则
  $\large p\log_2p=0$plog2​p=0
• 有一个大小为10的布尔值样本集$S_k$Sk​，其中6个为假，因为共有0、1两种状态，所以k=2.则该样本的熵
  $\large Entropy(S_2) = -(\dfrac{6}{10})\log_2(\frac{6}{10})-(\dfrac{4}{10})\log_2(\dfrac{4}{10})=0.9710$Entropy(S2​)=−(106​)log2​(106​)−(104​)log2​(104​)=0.9710
• 熵在这里是衡量样本集合纯度的一种指标，熵值越小，则样本纯度越高。

1.1.2 信息增益

信息增益就是两个熵值的差。
决策树是通过特征来进行判断分类，对样本S来说，会有a个属性，每个属性可能有v种特征，会导致产生v个分支。

• 样本S的分类结果的熵：就是不考虑任何特征，只考虑分类结果的熵。
• 每个属性的熵：根据每个节点对应的分类结果可以计算出此节点的熵。而由于样本中属性$a_i$ai​对应的v种特征，每种特征取值$S^v$Sv的数量不同。每个属性的熵就是计算该属性下每个特征的熵进行带权相加。
• 信息增益就是样本S分类结果的熵，减去属性a的熵。
  信息增益的值越高，则说明以属性a进行分类产生的结果接近样本自有的分类情况，则以属性a进行分类的效果越好，我们称之为分类后的样本纯度高。
• 公式如下:
  $Entropy(S^v) = -\sum^k_{i=1}\log_2p_i,\space p_i=\frac{n_i^v}{S^v}$Entropy(Sv)=−i=1∑k​log2​pi​, pi​=Svniv​​
  $n^v_i$niv​表示属性a中，特征v对应的分类i的数量。
  $Gain(S,a) = Entropy(S)-\sum_{i=1}^{v}\dfrac{|S^v|}{|S|}Entropy(S^v)$Gain(S,a)=Entropy(S)−i=1∑v​∣S∣∣Sv∣​Entropy(Sv)

1.2 ID3算法实例

ID3算法原理就是对每一个特征求信息增益，选择信息增益最大的属性作为根节点进行划分



根据西瓜书的步骤，首先选择信息增益最大的纹理，作为根节点来对样本进行分类，分类的结果，我们知道每个节点对应的结果并不唯一，所以需要继续进行分类。
所以我们将每个节点下的样本作为样本集继续分类，对除纹理外的特征计算信息增益，选择值最大的作为根节点进行分类，直到每个节点对应的分类结果唯一，递归停止。由此产生的树，就是ID3算法产生的分类树。

2 C4.5算法

C4.5算法是对ID3算法的改进。使用增益率来确定根节点。

2.1 改进原因

在ID3算法中，如果一个属性对应的特征有很多，那么这个属性的信息增益会相对的大，这是因为对应的特征多，在样本数量相同时，每一个值对应的分类结果会相对较少，这就存在值对应的分类结果的纯度较大，这样对其他特征就不够公平，这就是信息增益对可取特征数目较多的属性有所偏好。
为减少这种偏好，引进了增益率。

2.2 增益率

增益率定义如下：
$Gain\_ratio(S,a)=\dfrac{Gain(S,a)}{IV(a)}$Gain_ratio(S,a)=IV(a)Gain(S,a)​

• IV(a)称作属性a的“固有值”（intrinsic value）,定义如下：
  $IV(a) = -\sum_{i=1}^{v}\dfrac{S_v}{S}\log_2\dfrac{S_v}{S}$IV(a)=−i=1∑v​SSv​​log2​SSv​​
  由定义我们知道，属性a的特征值数目越多，IV(a)的值越大，从而可以消除对可取值数目较多的属性的偏好

2.3 缺点

采用增益率虽然消除了对可取值数目较多的特征的偏好，但同时却偏好了可取值数目较少的特征。所以C4.5算法不使用增益率最大的属性用来划分，而是使用了一个启发式，从候选属性中选择信息增益率高于平均水平的属性，再从中选择增益率最高的。

3 CART算法

CART(Classification and Regression Tree)算法，采用基尼指数(Gini index)来选择根节点。

3.1 基尼指数

• 使用基尼值来表示样本的纯度
• 基尼值定义如下：
  $Gini(S)=\sum_{k=1}^{v}\sum_{k^*!=k}p_kp_{k^*}=1-\sum_{k=1}^{v}p_k^2$Gini(S)=k=1∑v​k∗!=k∑​pk​pk∗​=1−k=1∑v​pk2​
  基尼值反映了从数据集S中随机抽取两个样本，其取值不同的的概率，即类别标记不同的概率。
  因此，基尼值越小，则样本纯度越高。
• 基尼指数定义如下：
  $Gini\_index(S,a)=\sum_{i=1}^{v}\frac{S_v}{S}Gini(S_v )$Gini_index(S,a)=i=1∑v​SSv​​Gini(Sv​)
• CART算法就是选择基尼指数最小的特征，作为决策树的根节点。

4 剪枝处理

剪枝是决策树处理“过拟合”的主要手段。在决策树学习过程中，为了尽可能正确的分类训练样本，往往会不断地进行分支，而这却有可能导致测试准确度时，准确度并不高，甚至可能会降低，这就是过拟合。
决策树的剪枝处理主要方法有“预剪枝”和“后剪枝”。

4.1 预剪枝

预剪枝是在节点生成过程中进行的，若当前节点不能带来决策树泛化性能的提升，则停止划分，将当前节点标记为叶节点。步骤如下：

• 1.使用训练集判断一特征作为叶节点时的分类结果，因为没有完全分类，所以该特征下的分类情况可能由多种，我们以数量最多的分类情况作为分类结果。
• 2.用测试集计算使用上现有树分类的准确度，记为$P_0$P0​。
• 3.对第一步生成的叶节点继续进行分类，计算此次分类后使用测试集计算出的准确度，记为$P_1$P1​.
• 4.若$P_0<P_1$P0​<P1​,则在树中添加第3步中生成的节点，否则，不生成。
• 5.重复上述步骤，至特征全部遍历且准确度达到最大值。

4.2 后剪枝

后剪枝是先使用训练集生成一个完整的树，在自底向上，使用测试集计算删除节点后的准确度，若准确度提升，则删除节点，否则保留。
西瓜书上的剪枝实例如下图：

4.3 方法比较

后剪枝决策树可以保留更多的节点，欠拟合风险小。但是后剪枝在决策树生成后进行，训练时间比预剪枝长。

5 连续与缺失

5.1 连续值的处理

在前面提到的例子中，特征对应的值是离散的比如0，1.但在实际应用中，可能会出现连续的值，比如年轻，密度，此时我们需要对连续的值进行离散化，最简单的就是分段。

• 比如年龄这个特征，对应的值可能为1到80的连续整数，而在应用中，对每一个年龄的样本进行计算、分类是不理想的，因此我们可以对年龄进行分段20-30，30-40，每个年龄段为一个值，以此来进行计算分类，效果会更好。
• 密度的离散化方法也是一样的。

5.2 缺失值的处理

实际问题中，收集到的数据往往是不完全的，而若删除有缺失值的数据，可能会导致数据集中大量数据被删除，对此情况，西瓜书中给出的解决方法如下(前文中，对样本用到的符号为S，此处改为D)。
给定训练集D和属性a

• $\widetilde{D}$D表示属性a上没有缺失值的样本子集。
• 假定属性a有V个特征，用$\{a^1,a^2,...a^V\}${a1,a2,...aV}表示，用$\widetilde{D}^v$Dv表示属性a内的特征v所包含的$\widetilde{D}$D的样本子集，
• $\widetilde{D}_k$Dk​表示$\widetilde{D}$D的第k种分类结果的子集。
• $\widetilde{D}=\bigcup_{k=1}^{\mathcal{Y}}\widetilde{D}_k,\widetilde{D}=\bigcup_{v=1}^{V}\widetilde{D}^v$D=⋃k=1Y​Dk​,D=⋃v=1V​Dv
• 为每个样本$x$x赋予一个权重$w_x$wx​（可以默认为1）。
  由以上初始条件，给出定义：
  $\large \rho = \frac{\sum_{x\in \widetilde{D}}w_x}{\sum_{x\in D}w_x}$ρ=∑x∈D​wx​∑x∈D​wx​​
  $\large \widetilde{\rho}_k= \frac{\sum_{x\in\widetilde D_k}w_x}{\sum_{x\in\widetilde D}w_x},\space (1\leq k \leq \mathcal Y)$ρ​k​=∑x∈D​wx​∑x∈Dk​​wx​​, (1≤k≤Y)
  $\large \widetilde r_v = \frac{\sum_{x \in \widetilde D^v}w_x}{\sum_{x \in \widetilde D}w_x},\space (1 \leq v \leq V)$rv​=∑x∈D​wx​∑x∈Dv​wx​​, (1≤v≤V)
• $\large \rho$ρ表示无缺失样本所占比例
• $\large \widetilde p_k$p​k​表示无缺失样本中分类为第k类的样本所占的比例
• $\large \widetilde r_v$rv​表示无缺失样本中属性a中的特征v的样本所占的比例。
  西瓜书中处理缺失值的办法，就是在计算熵和增益率的时候，将无缺失值样本数量$\rho$ρ考虑在内，同时，对存在缺失值的样本处理办法是将该样本分配至每一个属性特征的分支中，因为在计算时考虑了各无缺失值特征所占比例$\large \widetilde r_v$rv​，所以可理解为将缺失值样本按比例分配到了每一个分支中。
  修改后的信息熵为：
  $\large Ent(\widetilde D) = -\sum_{k=1}^{\mathcal{Y}}\widetilde p_k\log_2\widetilde p_k$Ent(D)=−k=1∑Y​p​k​log2​p​k​
  修改后的信息增益为：
  $\large Gain(D,a)=\rho×(Ent(\widetilde D)-\sum_{v=1}^V\widetilde r_vEnt(\widetilde D^v))$Gain(D,a)=ρ×(Ent(D)−v=1∑V​rv​Ent(Dv))

6 随机森林(Random Forest)

随机森林是对决策树的改进，是集成学习的经典方法之一。

6.1 集成学习(ensemble learning)

集成学习是使用多个学习器来完成学习任务，示意图如下

对简单的二分类问题，有分类$y\in \{-1,+1\}$y∈{−1,+1}，真是函数$f$f,假定基分类器的错误率为$\large\epsilon$ϵ，即对每个基分类器有
$\large P(h_i(x)\neq f(x))=\epsilon$P(hi​(x)​=f(x))=ϵ
以简单的投票法结合T个基分类器，若有超过半数的基分类器正确，则集成分类就正确：
$\large H(x)=sign(\sum^T_{i=1}h_i(x))$H(x)=sign(i=1∑T​hi​(x))
若每个基分类器相互独立，则集成的错误率为
$\large P(H(x)\neq f(x))=\sum_{k = 0}^{\lfloor T/2 \rfloor}(^T_k)(1-\epsilon)^k\epsilon ^{T-k} \leq \exp(-\frac{1}{2}T(1-2\epsilon)^2)$P(H(x)​=f(x))=k=0∑⌊T/2⌋​(kT​)(1−ϵ)kϵT−k≤exp(−21​T(1−2ϵ)2)
由上式可知，随着T的数目增大，集成的错误率将成指数下降趋势，直至趋近于零。
上述结论有一个关键假设，就是基学习器的相互独立。在实际任务中，个体学习器是为了解决同一个问题训练出来的，他们不可能相互独立。为解决这一问题，提出了两种集成学习方法，一种是个体学习器之间存在强依赖关系，必须串行生成序列化方法（Boosting），另一种是个体学习器不存在强依赖关系，可同时生成的并行化方法（Bagging和Random Forest）。

6.2 随机森林

随机森林简称BF，在构建个体学习器也就是随机森林时，引入了随机属性选择。传统决策树在生成节点时，从当前的属性集合d中选择一个最优属性，而随机森林中，在生成基决策树的每个节点时，先从该节点的属性集合中，随机选择一个包含k个属性的子集，然后从这个子集中选取最优属性用于划分。这里的参数k控制了随机性的引入程度：若k=d,则基决策树的构建与传统决策树相同；若令k=1，则随机选择一个属性用于划分；一般情况下，推荐$k = \log_2d$k=log2​d.
随机森林的其实性能往往相对较差，特别是集成中只包含一个基学习器是，这是因为通过引入属性扰动，随机森林中个体学习器的性能往往有所降低，然而，随着个体学习器数目的增加，随机森林通常会收敛到更低的泛化误差。

7 决策树代码实现

这一部分的实现，来源于《机器学习实战》,笔者在这里添加了详细的注释，有不对的地方希望有人能指出来。

import os
from math import log
import operator
import matplotlib.pyplot as plt

• 计算给定数据集的熵
  $Ent = -\sum_{i=1}^np(x_i)\log_2p(x_i)$Ent=−i=1∑n​p(xi​)log2​p(xi​)

def calcShannonEnt(dataSet):
    numEntries = len(dataSet)
    labelCounts = {}
    for featVec in dataSet:
        currentLabel = featVec[-1]
        # 数据集中最后一列存放标签
        if currentLabel not in labelCounts.keys():
        # 标签在字典键值中不存在，则赋初值0
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
        # 统计标签出现的次数
    shannonEnt = 0.0
    # 熵赋初值
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        # 计算p_i
        shannonEnt -=prob * log(prob,2)
    return shannonEnt

• 自建一数据集进行测试

def creatDataSet():
    dataSet = [[1,1,'yes'],
              [1,1,'yes'],
              [1,0,'no'],
              [0,1,'no'],
              [0,1,'no']]
    labels = ['no surfacing','flippers']
    return dataSet,labels
myDat, labels = creatDataSet()
print(myDat,'\n',labels)

>>> [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']] 
>>> ['no surfacing', 'flippers']

calcShannonEnt(myDat)

>>> 0.9709505944546686

• 划分特征

根据特征的值来划分属性(即划分数据集)

def splitDataSet(dataSet, axis, value):
# axis代表属性在数据集中的位置，value是属性的特征值
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            # extend()用于增加另一个列表中的多个值
            retDataSet.append(reducedFeatVec)
    return retDataSet

print(splitDataSet(myDat,0,1))
print(splitDataSet(myDat,0,0))

>>> [[1, 'yes'], [1, 'yes'], [0, 'no']]
>>> [[1, 'no'], [1, 'no']]

def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1
    # 得到属性数目
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1
    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]
        # 记录属性i下的特征值
        uniqueVals = set(featList)
        # 获取唯一的特征值
        newEntropy = 0.0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            # 提取属性i的特征vlue的数据
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet)
        infoGain = baseEntropy - newEntropy
        # 得到信息增益
        if (infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature
    # 返回可使信息增益最大的属性

• 测试

chooseBestFeatureToSplit(myDat)

>>> 0

返回结果为0，表明数据集中，属性0作为当前的节点，对子集的提纯效果最好

• 构建决策树往往不止需要一个节点，这里使用递归的方法来创建决策树。

递归结束的条件是：程序遍历完所有划分数据集的属性，或者每个分支下的所有*都具有相同的分类。

def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.iteritems(),
                             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])
    # 删除已经用过的属性，此处labels发生改变
    featVlues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featVlues)
    # 存储用来划分的属性下的特征值
    for value in uniqueVals:
        subLabels = labels[:]
        # 存储当前剩余属性
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
        # 给新生成的节点赋值
    return myTree

• 测试

myTree = createTree(myDat,labels)
myTree

{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

• 通过决策树创建分类函数

def classify(inputTree, featLabels,testVec):
    firstStr = inputTree.keys()[0]
    # 获取树的根节点
    secondDict = inputTree[firstStr]
    # 获取子树
    featIndex = featLabels.index(firstStr)
    # 获取根节点在属性列表中的位置
    for key in secondDict.keys():
    # 遍历子树
        if testVec[featIndex] == key:
            if type(secondDict[key]).__name__=='dict':
                classLabel = classify(secondDict[key],featLabels,testVec)
            else:
                classLabel = secondDict[key]
    return classLabel