机器学习算法Code Show——决策树

阿里云2000元红包!本站用户参与享受九折优惠!

上一篇文章机器学习算法复习手册——决策树在复习完基本概念之后,我给自己挖了一个坑:用python写一个决策树出来(注意,不是sklearn调包)。虽然说这个东西在几年前我写过一次,但又写一次,发现很多地方还有挺折磨我的。今天,就来填这个坑,分享一下我写的很垃圾的ID3决策树算法。

注:

  • 这里展示的是ID3算法的大致思想
  • 没有写树的剪枝算法,只有“特征选择”和“树的生成”
  • 没有经过细致的优化,没有对照网上的其他写法

一、数据集

这里为了方便,我搞了一份十分简陋的“西瓜分类数据集”:


简易西瓜分类数据集

总共就17个样本,配得上“简陋”二字。
所以,我们的实验中就不涉及训练集测试集划分了,只要能根据这个数据集,生成一个符合它的规则的决策树,就算是成功了。
数据集文件可以通过公众号后台回复【简陋西瓜数据集】获取。

二、特征选择算法

ID3算法,使用的是“信息增益”的标准来选择特征,这个主要分两步:

  1. 熵的计算
  2. 条件熵的计算

算法可以回顾一下上一篇文章,这里不赘述,直接上代码:

import math
# 熵的计算
def entropy(p_list):
    E = 0
    for p in p_list:
        if p == 0:
            E += 0
        else:
            E += -p*math.log2(p)
    return E
def cal_info_gain(dataset,feature):
    # 先计算dataset的熵:
    N = len(dataset)
    n1 = len(dataset[dataset["好"]=="是"])
    E = entropy([n1/N,(N-n1)/N])
    # 再计算条件熵:
    # 需要知道:feature的每一个值在dataset中的个数,以及其中各类别的个数
    feature_count = {}
    for fv,c in zip(list(dataset[feature]),list(dataset["好"])):
        if fv not in feature_count:
            feature_count[fv] = [0,0] # 创建一个list,存放各类别的个数
        if c == "是":
            feature_count[fv][1] += 1
        else:
            feature_count[fv][0] += 1
    conditional_E = 0
    for v in feature_count:
        N_v = sum(feature_count[v]) # N_v:当前feature value的个数
        p_list = []
        for N_vc in feature_count[v]: # N_vc:feature value中各个类别的个数
            p_list.append(N_vc/N_v)
        conditional_E += N_v/N * entropy(p_list)
    return E - conditional_E

上面的注释部分应该写的比较清楚了,反正主要思想就是“数数”,把数字数清楚了,就都好算了。

具体思想就是:
给定了一个feature(比如“触感”),我希望统计出这个feature的各个值(“硬滑”和“软粘”)各自占数据集的多少,以及每一个值中,数据各个类别的多少。
上面代码里面有一个关键性的数据统计字典:feature_count,我们对feature=”触感”进行统计之后,得到的结果是:
feature_count = {'硬滑': [6, 6], '软粘': [3, 2]}
意思就是在“硬滑”这个特征值下,有6个坏瓜6个好瓜,“软粘”这个值下,有3个坏瓜2个好瓜。那么条件熵就用公式一套即可。

三、树的生成

很明显,我们需要用一个递归函数来生成一棵树。
一个重要的问题是:用什么数据结构存储这个树呢?
思来想去,发现字典这种非线性结构比较好。线性的数据结构是无法存储树这种东西的。

思路是这样的:

  1. 一个选择了某feature来划分,该feature就作为字典的一个key;
  2. 一个feature会有多个feature values,所以这个feature后面还得接一个字典,每一个feature value都是一个key;
  3. 一个feature value下面,可能唯一确定了一个叶节点了,所以可以接一个标签值label,终止;
    也有可能还要继续划分,所以就要确定新的划分feature,这个新的feature就作为key,继续回到步骤1。

所以想象中,我们希望得到这样的一个层次字典:

{'纹理': {'模糊': '否',
        '清晰': {'根蒂': {'硬挺': '否',
                      '稍蜷': {'色泽': {'乌黑': '否', '青绿': '是'}},
                      '蜷缩': '是'}},
        '稍糊': {'触感': {'硬滑': '否', '软粘': '是'}}}}

当然,我们事先不必画出这么一个字典,太费劲了(这个字典是我程序写完之后生成的)。我们只用脑补一下这个结构就行了。

有了这样的数据结构,程序就不难写了,上代码:

def tree_generation(dataset,features):
    # 终止条件:
    if len(set(dataset["好"])) == 1: # 数据集里所有样本都属于同一类
        return list(dataset["好"])[0] # 返回类别
    if len(features) == 0: # 没有剩余的特征了
        if len(dataset[dataset["好"]=="是"])>len(dataset[dataset["好"]=="否"]):
            return "是"
        else:
            return "否"
    # 其他情况:
    info_gains = []
    for feature in features:
        info_gains.append(cal_info_gain(dataset,feature))
    best_index = info_gains.index(max(info_gains))
    best_feature = features[best_index]
    features.remove(best_feature)
    remaining_features = features[:] # 不能使用features,要复制一份
    if max(info_gains)<=0:# 说明所有的特征都没有区分度
        if len(dataset[dataset["好"]=="是"])>len(dataset[dataset["好"]=="否"]):
            return "是"
        else:
            return "否"
    else: 
        my_tree = {best_feature:{}}
        feature_values = set(dataset[best_feature])
        for fv in feature_values:
            sub_dataset = dataset[dataset[best_feature]==fv]
            my_tree[best_feature][fv] = tree_generation(sub_dataset,remaining_features)
        return my_tree

上面的程序,先讨论了三种特殊情况:

  1. 样本都同一类了
  2. 没有剩下的特征了
  3. 有特征,但没有区分度了
    这些都是直接返回label,是递归程序的终止条件。

然后,就是正常的特征选择、划分的流程了:

  1. 每个特征算个info gain,大家一起碰一碰
  2. 最好的特征,每个特征值对数据集进行分割,产生子数据集,丢入递归程序中

验证一下:

feature_names = ['色泽','根蒂','敲声','纹理','脐部','触感']
t = tree_generation(df,feature_names)
pprint(t)

得到的输出就是上面给的字典:

{'纹理': {'模糊': '否',
        '清晰': {'根蒂': {'硬挺': '否',
                      '稍蜷': {'色泽': {'乌黑': '否', '青绿': '是'}},
                      '蜷缩': '是'}},
        '稍糊': {'触感': {'硬滑': '否', '软粘': '是'}}}}

四、如何画出来?

字典形式总归是难看的,我们希望能用一个生动形象的真正的树给它描绘一下。
这里尝试使用matplotlib这个我觉得很难用,每次用都要到处查文档的包。。。

画决策树主要需要哪些部分呢:

  1. 树的各个节点(决策点,即特征):直接用plt.plot(x,y,…)画点
  2. 树枝(特征值):用plt.annotate(”,(end),(start),…)来画
  3. 叶节点(标签):用plt.plot(x,y,…)来画

明显,这也是一个递归程序:
终止条件:当得到的tree就是label时,画叶节点,终止。
正常:先把tree中顶部的划分特征拿出来,画一个节点,然后取出它的各个特征值,画出各个分支,下面的子树继续丢进递归程序中。

代码:

plt.figure(figsize=(10,5))
def plot_tree(tree,x,y):
    shift = 0.2
    if isinstance(tree,str):
        plt.plot(x,y,'go')
        plt.text(x,y-shift,tree)
        return 0
    # 先判断是特征还是特征值
    feature = list(tree.keys())[0]
    assert feature in feature_names,"%s is not a feature!"%feature
    plt.plot(x,y,'ro',markersize=10)
    plt.text(x,y+shift,feature)
    for i,v in enumerate(list(tree[feature].keys())): # 取出每一个特征值
        next_x = x/3 + i
        next_y = y - 1
        plt.annotate('',(next_x,next_y),(x,y),arrowprops=dict(width=1,shrink=0.05))
        plt.text((next_x+x)/2,(next_y+y)/2,v)
        sub_tree = tree[feature][v]
        plot_tree(sub_tree,next_x,next_y)
        
feature_names = ['色泽','根蒂','敲声','纹理','脐部','触感']
plot_tree(t,1,-1)
plt.show()

上面的代码得到的结果是这样的:

诚然,它很丑。甚至树枝都交叉了,但我不想再调了,matplotlib这玩意儿我实在用着别扭。
一个合格的决策树的画法,应该首先计算一下树的基本属性,节点数、深度等等,再好好布局,我没心思继续扣这些细节了,所以虽然我画的决策树丑,但我看着顺眼,看的清楚,就OK!毕竟,写这些代码,主要是为了体验一下其中的思想,真正实战,还是用别人千锤百炼写出来的工具包吧!

五、如何预测?

有了决策树,怎么去预测?
这个实际上是最简单的了。
给定一个样本,用我们得到的tree字典依次去检查:
先取出tree的第一个划分特征,找到样本对于的特征值,去查询这个特征值对应的子树即可。
代码如下:

def predict(tree,feature_df):
    feature = list(tree.keys())[0]
    fv = list(feature_df[feature])[0]
    sub_tree = tree[feature][fv]
    if isinstance(sub_tree,str):
        print(feature+':'+fv,'-->',sub_tree,end='')
        return sub_tree
    else:
        print(feature+':'+fv,'--> ',end='')
        predict(sub_tree,feature_df)

我们拿数据集中的样本一个个检验一下:

for i in range(1,18):
    result = predict(t,df[df["编号"]==i])
    print()

输出结果:

纹理:清晰 --> 根蒂:蜷缩 --> 是
纹理:清晰 --> 根蒂:蜷缩 --> 是
纹理:清晰 --> 根蒂:蜷缩 --> 是
纹理:清晰 --> 根蒂:蜷缩 --> 是
纹理:清晰 --> 根蒂:蜷缩 --> 是
纹理:清晰 --> 根蒂:稍蜷 --> 色泽:青绿 --> 是
纹理:稍糊 --> 触感:软粘 --> 是
纹理:清晰 --> 根蒂:稍蜷 --> 色泽:乌黑 --> 否
纹理:稍糊 --> 触感:硬滑 --> 否
纹理:清晰 --> 根蒂:硬挺 --> 否
纹理:模糊 --> 否
纹理:模糊 --> 否
纹理:稍糊 --> 触感:硬滑 --> 否
纹理:稍糊 --> 触感:硬滑 --> 否
纹理:清晰 --> 根蒂:稍蜷 --> 色泽:乌黑 --> 否
纹理:模糊 --> 否
纹理:稍糊 --> 触感:硬滑 --> 否

发现,除了8号,都预测对了。

那么,我们终于写就了一个简陋的决策树算法啦!终于从坑里爬出来了!

https://www.jianshu.com/p/16c7acded764

Python量化投资网携手4326手游为资深游戏玩家推荐:《玄秋一战,八强诞生!《影之诗》SNC2019海选终轮战况回顾

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
Python
pandas
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论