本文共 5044 字，大约阅读时间需要 16 分钟。

---

本文内容为：基于python的Id3算法，实现，数据采用了西瓜书中，西瓜数据集2.0的部分数据测试，没有使用csv文件内容，代码可直接复制，改进，使用。代码仅实现了算法，测试数据包含在代码中，文件信息处理需要自己进行。

---

1. ID3决策树算法是什么？

提示：这里可以添加本文要记录的大概内容：

例如：随着人工智能的不断发展，机器学习这门技术也越来越重要，很多人研究学习机器学习的很多算法，本文就介绍了机器学习的基础内容之决策树的ID3算法实现。完成了核心的部分，决策树的剪枝等之后的博客会细说到。

2. ID3决策树算法的笼统理论

ID3算法是一种贪心算法,用来构造决策树,ID3算法起源于概念学习系统（CLS）。

在学习决策树之后，我们知道决策树的核算即划分选择，不同的算法往往有不同的划分选择标准，一般情况下，我们要求分支节点所包含的样本属于同一类别，即节点的纯度越高。信息熵一般是度量样本纯度最常用的指标，如下： 从其中我们不难得到，信息熵越大，则意味着越混乱，所以信息熵越小，则D的纯度越高。

而著名的ID3决策树算法是以信息增益为准则划分的，信息增益也是以信息熵为基础的一个数值。如下：

如上就是ID3主要的划分方式，也是整个划分算法的核心。 如下数据集为西瓜数据集2.0，我取1,3,5,7,9,11,13,15，行数据，并去除掉了敲声行。

2.代码实现（面向对象写法）

#三个过程：特征选择，决策树的生成，决策树的剪枝import numpy as npimport mathclass __ID3__():    #测试数据集     def __init__(self):        self.test_data=[[0,0,0,0,0,'yes'],[1,0,0,0,0,'no'],[2,0,0,0,0,'yes'],[1,1,1,1,1,'yes'],[1,1,1,1,2,'no'],[2,2,2,2,2,'no'],[0,1,1,1,2,'no'],[1,1,0,1,1,'no']]        self.test_label=['color','root','vein','region','touch']    #以下为划分选择的重点算法        #计算数据集D的信息熵 信息熵的计算公式位于西瓜书p75 4.1，由公式我们很容易得到需要的数据：数据数与样本所占比例    #这里是由于信息增益公式太复杂了。。因此先写出获取信息熵的方法。    #信息熵越小，纯度越高    def get_comentropy(self,data):        #获取数据数        nums=len(data)        #获取每个数据占有的比例，利用字典记录每个样本出现的次数        label={
   }        for ele in data:            if ele[-1] not in label.keys():                label[ele[-1]]=1            else :                label[ele[-1]]+=1        comentropy=0        for ele in label:            comentropy-=(label[ele]/nums*math.log(label[ele]/nums,2))        return comentropy    #计算信息增益 还需要子数据集，定义方法获取     #假设离散属性a有V种可能的取值，那么Dv即所有在属性a上，取值为av的样本，函数返回子集    def get_sub_data(self,data,attribute_index,value):        #设置返回值 这里注意我们还要想到，该数据集返回之后还是需要递归使用的，因此我们要抽离到该数值特征        sub_data=[]        for line in data:            if line[attribute_index] == value :                temp=[line[i] for i in range(len(line)) if i !=attribute_index]                sub_data.append(temp)        return sub_data    #选取最优的划分属性 这里需要数据的信息增益    def get_best_information_gain(self,data):        #首要需要数据集信息熵        comentropy=self.get_comentropy(data)        #获取分支节点数 解释：最后一列为标签，去掉算长度        branch_nums=len(data[0])-1        #信息增益越大，意味着纯度越大        best_information_gain=0        #返回要划分的属性索引        best_attribute=-1        for index in range(branch_nums):            #填入某一列全部的属性 利用列表生成式            every_col_ele=[temp[index] for temp in data]            temp=0            #通过集合去重 求累计和            for value in set(every_col_ele):                sub_data=self.get_sub_data(data,index,value)                temp+=(len(sub_data)/len(data)*self.get_comentropy(sub_data))            #求信息增益            temp=comentropy-temp            if temp>best_information_gain :                best_information_gain=temp                best_attribute=index        return best_attribute#以上为划分选择特征的重点算法    #用嵌套字典表示创建树 创建树整体应该是个递归的过程，因此必须要找到递归的出口    def creat_tree(self,data,input_label):        result=[temp[-1] for temp in data]        #出口1：本身的数据只有一个属性        if len(result) == result.count(result[0]):            return result[0]        #出口2：已经遍历完所有特征的情况下，需要一个函数，返回数量最多的类别        if len(data[0])==1:            return most_class(result)        #找出最优特征索引，用来划分数据集        best_feature_index=self.get_best_information_gain(data)        #找出最优的标签        best_label=input_label[best_feature_index]        #构建树，同时删除掉已经抽取的标签        tree={
   best_label:{
   }}        del(input_label[best_feature_index])        #抽取特征集合        best_values=[temp[best_feature_index] for temp in data]        for value in set(best_values):            #抽取子数据集合标签            sub_data=self.get_sub_data(data,best_feature_index,value)            sub_label=input_label[:]            #递归创建子树            tree[best_label][value] =self. creat_tree(sub_data,sub_label)        return tree    def most_class(data_class):        re_class={
   }        for line in data_class:            if line not in re_class.keys():                re_class[line]=0            re_class[line]+=1        #获取字典，按值排序        return sorted(re_class.values(),reverse=True)[0]    #完成分类任务    def predict(self,tree,label,data):        decision_dic=tree[list(tree.keys())[0]]        label_index=label.index(list(tree.keys())[0])        ret_label=''        for dict_key_name in decision_dic.keys():            if data[label_index] == dict_key_name:                if type(decision_dic[dict_key_name])is dict:                    ret_label=self.predict(decision_dic[dict_key_name],label,data)                else: ret_label=decision_dic[dict_key_name]        return ret_label    #测试用例    def test_pre(self):        data,label=self.test_data,self.test_label        te_label=label[:]        tree=self.creat_tree(data,label)        print(self.predict(tree,te_label,[1,1,1,1,1]))test=__ID3__()test.test_pre()

总结以及对于学习的感慨

本文简单实现了ID3算法

其实我们在学习中，已经发现有各种各样的框架，API可以直接调用，那么学这些底层还有什么意义呢，我知道这也是和我一样的机器学习新手所面临的的问题，为什么明明有框架还要学习这些东西，我想说的是，如果仅仅是调用框架，调用api，调参，那不论是前段，后台，安卓开发，服务器维护，算法师，这些人在有经验的情况下，可以在两三甚至三天内掌握所谓的"机器学习"，我们学习这个领域，所学的不仅仅是那个API，而是机器是如何学习的，为什么我们能让机器学习起来，到底怎么样去构建一个完整的AI，框架本身只是为我们提供了更方便的方法罢了，甚至我曾亲眼见到我一个学长自己实现的序列预测比pytorch的调参到极限的算法效率还要高，我们的目标终究是不断研究，创新，加油吧，ML人。

转载地址：http://bkcki.baihongyu.com/