决策树算法

发表于 分类于 Waline：

决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表某个可能的属性值，而每个叶节点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。 数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据，同样也可以用来作预测，从数据产生决策树的机器学习技术叫做 决策树学习 ,通俗说就是决策树

一、什么是决策树算法

决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表某个可能的属性值，而每个叶节点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。 数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据，同样也可以用来作预测，从数据产生决策树的机器学习技术叫做 决策树学习 ,通俗说就是决策树

维基百科：https://zh.wikipedia.org/zh-cn/%E5%86%B3%E7%AD%96%E6%A0%91#%E7%AE%80%E4%BB%8B

不懂？那我们引用周志华老师西瓜书上的例子，立马就能有一个大概了解。

比如你带你表妹现在要去西瓜摊买西瓜，而作为卖西瓜老手的你总是能够一眼挑选出那个最好吃最甜的西瓜，而表妹总是选的不尽人意，表妹突发奇想向你请教怎么选出一个心满意足的西瓜。你说：得价钱！不对不对咱们在谈买西瓜，你说咱们啊，先看“它是什么颜色?”，如果是“青绿色”，则我们再看 “它的根蒂是什么形态?”，如果是“蜷缩 ”，我们再判断“它敲起来是什么声音?”，最后，我们得出最终决策：这个瓜很润，呸呸呸，是很甜！

我相信你现在应该有一个大概了解了，不就是选择一个目的（我们需要进行的分类的标签），然后根据一系列的特征从而满足我们的目的，以后我们就借用这个特征去挑选“好瓜”。但是！先泼一盆凉水给你，我们怎么开始第一步呢？这还不简单，直接选择”颜色“呀！但是我们为什么不从”根茎“下手呢？下面就是我们要将的如何进行划分，也就是划分标准。

二、划分标准

2.1 信息增益(ID3决策树算法划分标准)

必须先了解信息熵这个概念，信息熵，维基百科上的定义：是接收的每条消息中包含的信息的平均量。这里，“消息”代表来自分布或数据流中的事件、样本或特征。（熵最好理解为不确定性的量度而不是确定性的量度，因为越随机的信源的熵越大）来自信源的另一个特征是样本的概率分布。这里的想法是，比较不可能发生的事情，当它发生了，会提供更多的信息。由于一些其他的原因，把信息（熵）定义为概率分布的对数的相反数是有道理的。事件的概率分布和每个事件的信息量构成了一个随机变量，这个随机变量的均值（即期望）就是这个分布产生的信息量的平均值（即熵）。熵的概念最早起源于物理学，用于度量一个热力学系统的无序程度。在信息论里面，熵是对不确定性的测量。但是在信息世界，熵越高，则能传输越多的信息，熵越低，则意味着传输的信息越少。还是不懂？那你不妨记住：信息熵是对信息量的一种衡量

维基百科：https://zh.wikipedia.org/zh-cn/%E7%86%B5_(%E4%BF%A1%E6%81%AF%E8%AE%BA)
Shannon,C.E.(1948).A Mathematical Theory of Communication. Bell System Technical Journal,27(3),379–423.doi:10.1002/j.1538-7305.1948.tb01338.x

一般地，划分数据集的大原则是：将无序的数据变得更加有序。在划分数据集之前之后信息发生的变化称为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。也就是说我们可用信息增益来进行决策树的划分属性选择，他们公式如下：

$$
信息熵：Ent(D)=-\displaystyle\sum_{k=1}^{|y|}p_klog_2p_k \取负数：保证信息熵>0
$$

其中$Ent(D)$的值越小，则消息熵越小

$$
信息增益Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v) \V:离散属性a的可能取值的个数
$$

怎么使用？再次借用周志华老师书上例子，我们来区分好瓜坏瓜。

202306041908136
  • 注释：本文都是采用的ID3决策树算法

因为我们的目的是区分好瓜坏瓜所以先计算其信息熵：

$$
Ent(D)=-\sum_{k=1}^{2}p_klog_2p_k=-(\frac{8}{17}log_2(\frac{8}{17})+\frac{9}{17}log_2(\frac{9}{17}))=0.998
$$

同理可得假设我们以色泽进行分类，那么色泽有三种可能 {青绿、乌黑、浅白}，我们再计算每种色泽下所对应好坏瓜的概率（$p_1:好，p_2:坏$）：青绿：$p_1=0.5,p_2=0.5$；乌黑：$p_1=\frac{4}{6}，p_2=\frac{2}{6}$；浅白：$p_1=\frac{1}{5},p_2=\frac{4}{5}$；这样一来我们可以计算各种信息增益：

$$
Ent(青绿)=1，Ent(乌黑)=0.918，Ent(浅白)=0.722
$$

然后计算信息增益:

$$
Gain(D,色泽)=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)=0.998-(\frac{6}{17}\times1+\frac{6}{17}\times0.918+\frac{5}{17}\times0.722)=0.109
$$

$$
同理可得其他的信息增益：\Gain(D,根蒂)=0.143;\Gain(D,敲声)=0.141;\Gain(D,纹理)=0.381;\Gain(D,脐部)=0.289;\Gain(D,触感)=0.006;
$$

纹理的信息增益最大，所以我们取纹理作为我们的划分标准，同理从纹理出发再取计算其他属性，并且得到信息增益，以此类推只到所有标准都划分完毕。

2.2 基尼指数(CART决策树算法划分标准)

三、评价

决策树的优点
1、决策树易于理解和实现.人们在通过解释后都有能力去理解决策树所表达的意义
2、对于决策树，数据的准备往往是简单或者是不必要的.其他的技术往往要求先把数据一般化，比如去掉多余的或者空白的属性
3、能够同时处理数据型和常规型属性。其他的技术往往要求数据属性的单一
4、是一个白盒模型如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式
5、易于通过静态测试来对模型进行评测。表示有可能测量该模型的可信度
6、在相对短的时间内能够对大型数据源做出可行且效果良好的结果
决策树的缺点
对于那些各类别样本数量不一致的数据，在决策树当中信息增益的结果偏向于那些具有更多数值的特征

文章如若有错误，欢迎大佬们批评指正。💪💪

四、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#计算信息熵
from math import *

def ent(data):
    data_length = len(data)
    dic = {}
    #统计个数
    for i in data:
        data_leable = i[-1]
        if data_leable not in dic:
            dic[data_leable] = 0
        dic[data_leable] +=1
   #return dic
    #计算信息熵
    ent_number = 0.0
    for j in dic:
        num1 = float(dic[j])/data_length
        ent_number = ent_number - num1*log(num1,2)
    return ent_number
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#划分数据集合
def data_split(data, axis, value):
    data_list = []
    for i in data:
        if i[axis] == value:
            feat = i[:axis]
            feat.extend(i[axis+1:])
            data_list.append(feat)
    return data_list

#extend与append函数区别：a.extend(b):将b的值全部加到a中；a.append(b):将b列表加到a中
# a = [1,2]
# b = [3,4]
# c = [3,4]
# a.append(b)
# c.extend(b)
# print(a,c)
# [1, 2, [3, 4]] [3, 4, 3, 4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#计算信增益,并且挑选最佳特征
def gain_chose(data):
    """
    data_ent:信息熵
    feat_list:每一种标签的全部数据
    feat_value:每一种标签下的取值
    data_gain:信息增益
    ent_number:计算各自列下的信息熵
    prop:计算概率
    best_feature:最佳划分特征
    """
    data_base_length = len(data[0])-1
    ent_base = ent(data)
    gain_max = -1 #取任何小于0的值都可以
    #第一个for循环得到每一列，第二个for循环则是对每一列中取值
    for i in range(data_base_length):
        feat_list = [a[i] for a in data]
        feat_value = set(feat_list)
        ent_number = 0.0
        for j in feat_value:
            data_split_use = data_split(data, i, j)
            prop = len(data_split_use)/float(len(data_split_use))
            ent_number = ent_number + prop * ent(data_split_use)
        data_gain = ent_base - ent_number 
        if data_gain > gain_max:
            gain_max = data_gain
            best_feature = i
    return best_feature
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#绘制决策树
import operator

def majorityCnt(classList):
    classCount={}
    for vote in classList:
        if vote not in classCount.keys(): classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

def createTree(dataSet,labels):
    """
    classList:存储dataset中的标签
    bestFeatLabel:根节点
    myTree:存储树结构
    """
    classList = [example[-1] for example in dataSet]
    # 如果全是一个特征，直接返回
    if classList.count(classList[0]) == len(classList): 
        return classList[0]
    # 如果数组长度为1，则
    if len(dataSet[0]) == 1: 
        return majorityCnt(classList)

    bestFeat = gain_chose(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(data_split(dataSet, bestFeat, value),subLabels)
    return myTree

五、决策树算法流程

第一步：计算信息熵：利用哈希表得到分类标签的对应数量关系，而后感觉对应的数量关系计算信息熵。
第二步：计算信息增益并且挑选出最佳特征：分为两个步骤。第一步：划分数据集合，第二步计算

  • 第一步：以西瓜例子说明，我们在挑选好 ‘yes’or’no’ 之后，我们要回过头观察前面特征的集合（色泽：a），而后在色泽：a中分别计算满足’yes’or’no’的信息熵。依次类推分别得到纹理等特征的信息熵。
  • 第二步：在我们前一步所得到的信息熵中计算信息增益
  • 第三步：挑选信息增益最大的值
    第三步：挑选好最佳特征之后开始绘制决策树

参考

周志华 《西瓜书》

《机器学习实战》