分类算法-决策树 Decision Tree

决策树（Decision Tree）是一个非参数的监督式学习方法，决策树又称为判定树，是运用于分类的一种树结构，其中的每个内部节点代表对某一属性的一次测试，每条边代表一个测试结果，叶节点代表某个类或类的分布。

0x00决策树的判定流程

下图表示礼物选择地判定过程，首先根据颜的两个选择分支：当黑色的时候根据价格选择喜欢不喜欢；当选择白色的时候，可以再根据大小确定喜欢或者不喜欢。

决策树的决策过程一般是从决策树的根节点开始，将待测数据和决策树中的特征节点进行比较，再选择下一个比较分支，直到叶子节点作为最终的决策结果。

决策树除了可以用来分类外，还可以用来回归和预测。分类树对离散变量做决策树，回归树对连续变量做决策树。

0x01决策树的三种节点

从数据产生决策树的机器学习技术成为决策树学习，通俗的来说是决策树，一个决策树一般有三种节点

• 决策节点:是对几种可能方案的选择，即最后选择的最佳方案。如果决策属于多级决策，则决策树的中间可以有多个决策点，以决策树根部的决策点为最终决策方案。

• 状态节点:代表备选方案的经济效果(期望值)，通过各状态节点的经济效果对比，按照一定的决策标准就可以选出最佳方案。由状态节点引出的分支称为概率枝，概率枝的数目表示可能出现的自然状态数目每个分支上要注明该状态出现的概率。

• 终结点:每个方案在各种自然状态下取得的最终结果.即树的叶子。

0x02优缺点

*优点**

1. 简单易懂，原理清晰，决策树可以实现可 视化;
2. 决策树算法的时间复杂度(预测数据)是 用于训练决策树的数据点的对数;
3. 能够处理数值和分类数据;
4. 能够处理多路输出问题;
5. 可以通过统计学检验验证模型。这也使模 型的可靠性计算变得可能;
6. 即使模型假设违反产生数据的真实模型， 表现性能依旧很好

缺点

1. 决策树有时候是不稳定的，因为数据微小 的变动，可能生成完全不同的决策树
2. 有些问题学习起来非常难，因为决策树很难表达，如异或问题、奇偶校验或多路复用器问题
3. 如果有些因素占据支配地位，决策树是有偏差的。因此建议在拟合决策树之前先平衡数据的影响因子
4. 对连续性的字段比较难预测
5. 最优决策树的构建属于NP问题

👇摘抄自：百度百科

P问题

P问题是一个判定问题类，这些问题可以用一个确定性算法在多项式时间内判定或解出。如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。

确定一个问题是否是多项式问题，在计算机科学中非常重要。已经证明，多项式问题是可解问题，因为除了P问题之外的问题，其时间复杂度都很高，即求解需要大量时间。

理论上有解但其时间复杂度巨大的问题，科学家将其称为难解型问题。对计算机来说，这类问题是不可解的。因此，P问题成了区别问题是否可以被计算机求解的一个重要标志。

NP问题

NP问题是指可以在多项式时间内被非确定机解决的问题。通常它们的时间复杂度都是指数变量，如 等。

这里有一个著名的问题一千禧难题之首。是说P问题是否等于NP问题，也即是否所有在非确定机上多项式可解的问题都能在确定机上用多项式时间求解。这表明用NP问题寻找多项式时间表示的算法很困难，或许最后的结论是NP问题根本就不是P问题。
P=NP?问题

目前已经证明所有P问题都是NP问题，那么反之P—NP吗?这就是所谓的“NP问题”。目前P与NP是否等价是一个既没有证实也没有证伪的问题。但是大部分科学家猜想：找一个问题的解很困难，但验证一个解很容易(证比解易)，用公式表示就是P≠NP。问题较难求解(P)但容易验证(NP)，这与我们的日常生活经验是相符的。

【例1】对方程求解很难，但是验证很容易。
假设证明了P=NP，那么依据计算复杂性的密码技术就会没有前途，因为答案很容易得到验证的问题也同样可以轻松求解，这将对计算机安全构成巨大威胁。因为目前的加密技术是将一个整数分解为几个因数的乘积，正是因数分解过程烦琐，才保证了信息的安全 [1] 。

NPC(NP Complete，NP完全)问题

计算机科学家将NP问题中最困难的称为NPC问题。NPC问题有一个令人惊讶的性质，即如果一个NPC问题存在多项式时间算法，那么所有NP问题都可以在多项式时间内求解，即P=NP成立。

这是因为每一个NPC问题都可以在多项式时间内转化成任何一个NP问题。只要任意一个NPC问题找到了一个多项式算法，那么所有NP问题都能用这个算法解决，也就解决了NP=P问题。但是给NPC找一个多项式算法太不可想象了，而且也从未成功，因此科学家认为，正是NPC问题的存在，使得人们相信P=NP。

NPC问题目前没有多项式算法，只能用穷举法逐个检验，最终得到答案。但是穷举法的计算时间随问题的复杂程度呈指数增长，很快问题就会变得不可计算了。

围棋或象棋的博弈问题、国际象棋的n皇后问题、密码学中的大素数分解问题等，都属于NPC类问题。

0x03决策树得学习过程

决策树学习是数据挖掘中得经典算法，每个决策树都表述了一种树形结构，它由它的分支对该类型得对象依靠属性进行分类。每个决策树可以依靠对源数据库得分隔进行数据测试。这个过程可以递归式地对树进行修建。

其学习过程如下：

• 特征选择：从训练数据地特征中选择一个特征作为当前节点地分裂标准（特征选择地标准不同产生了不同地特征决策树算法）
• 决策树地产生：根据所选特征评估标准，从上而下递归地生成子节点，知道数据集不可分时再停止生成
• 剪枝：决策树容易过拟合，需要剪枝来缩小树地结构和规模（包括预剪枝和后剪枝）

0x04创建决策树进行分类

创建决策树进行分类的流程如下。

(1)创建数据集。

(2)计算数据集的信息熵。

(3 )遍历所有特征，选择信息熵最小的特征，即为最好的分类特征。

(4)根据上一步得到的分类特征分隔数据集， 并将该特征从列表中移除。

(5)执行递归函数，返回(3)，不断分隔数据集，直到分类结束。

( 6)使用决策树执行分类， 返回分类结果。

决策树学习算法的伪代码如下。

检测数据集中的每个子项是否属于同一类。
if每个子项属于同一类return类标签
else
    ( 1 )寻找划分数据集的最好特征。
    (2 )划分数据集。
    (3)创建分支节点。
        ①for每个划分的子集。
        ②调用分支创建函数并增加返回结果到分支节点中。
    ( 4) return分支节点。

从上面代码的实现过程可以发现，在构建决策树的过程中，要寻找划分数据集的最好
特征。

例如，如果一个训练数据中有 10个特征,那么每次选取哪个特征作为划分依据?

这 就必须采用量化的方法来判断，量化划分方法有多种,其中一项就是“信息论度量信息分类”， 即使无序的数据变得有序。

基于信息论的决策树算法包括ID3、C4.5、 CART 等。J. Ross Quinlan在1975年提 出将信息熵的概念弓|入决策树的构建，这就是鼎鼎有名的ID3算法，后续的C4.5、 C5.0、 CART等都是该方法的改进算法。下面是几种算法的大致情况，详细算法可以参考机器学 习有关书籍，这里不做重点介绍。

（学习由浅入深，我jio的这三个算法可以之前再了解，先往后看看关于信息熵的内容）

0x05信息熵

由于这些算法又涉及信息熵的概念，因此，下面就简要介绍一下信 息熵的基本知识。

信息熵:在概率论中，信息熵是一种度量随机变量不确定性的方式，熵就是信息的期
望值。假设S为所有事件集合，待分类的事物可能划分在C类中，分别是C，C2,
Cn,每一类的概率分别是P1，P2, . Pn, 那么s的熵就定义为:

信息熵是以二进制位的个数来度量编码长度的，因此熵的最大值是log2C。

• 举个栗子(　o=^•ェ•)o　┏━┓

熵值越高，则数据混合的种类越高，其蕴含的含义是一个受重可能的支化越多 (反而 与变量具体的取值没有任何关系，只和值的种类多少及发生概率有关)，它携带的信息量 就越大。熵在信息论中是一个非常重要的概念 ，很多机器学习的算法都会用到这个概念。

信息增益( Information Gain)是指信息划分前后熵的变化，即由于使用这个属性分 隔样例而导致的期望熵降低。也就是说，信息增益就是原有信息熵与属性划分后信息熵(需 要对划分后的信息熵取期望值)的差值，具体计算法为:

其由第二项为属性A对S划分的期望信息

• 再举个栗子(　o=^•ェ•)o　┏━┓

这个数据集有四个样本，两个基本属性，其中X1表示是否为红色，X2表示大小，Y表示是否为好苹果

由于只有两个属性，只可能有两个决策树，如下图所示：

尝试用代码来计算熵：

换一组测试数据：

from math import log
def calcshan(dataSet):
    lenData = len(dataSet)
    p = {}
    H = 0.0
    for data in dataSet:
        currentLabel = data[-1]#获取类别标签（也就是样本的yes或no，比如上面例子的苹果的好与坏）
        if currentLabel not in p.keys():
            p[currentLabel] = 0 #如果字典中没有该类别标签，则创建
        p[currentLabel]+=1 #递增类别标签的值
    for key in p:
        px = float(p[key])/float(lenData) #计算某标签的概率
        # 计算信息熵
        H -= px*log(px,2)
    return H

if __name__ == "__main__":
    dataSet=[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]
    print(calcshan(dataSet))

测试结果

(env_default) PS F:\workspace> python .\test.py
0.9709505944546686
(env_default) PS F:\workspace>

本作品采用《CC 协议》，转载必须注明作者和本文链接