申请会员ID:秋初-晓尘
1、申 请 I D：秋初-晓尘
2、个人邮箱：1134050036@qq.com
3、原创技术文章：机器学习决策树之ID3算法
注：该文章为原创，之前发布在博客园你与CSDN，现更新版本后（加入源码），作论坛申请用。
原文：
https://static.52pojie.cn/static/image/hrline/4.gif
1、什么是决策树
决策树，就是一种把决策节点画成树的辅助决策工具，一种寻找最优方案的画图法。 如下图所示，从左图到右图就是一个简单的，利用决策树，辅助决策的过程。
https://img-blog.csdnimg.cn/20190801144418603.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29nbmFN,size_16,color_FFFFFF,t_70#pic_center
https://static.52pojie.cn/static/image/hrline/4.gif
2、如何构造一棵决策树？
2.1、基本方法
通过对不同特征的优先级区分判断后，优先选择优先级高的特征作为划分的特征。（如上图所示，假设优先级：学历>院校>工作经验。因此我们优先选择了学历作为分类依据，次而选择了院校作为分类依据，最后才选择了项目经验作为分类依据）。那么，下一个问题来了，我们是怎样判断一个特征的优先级的？具体来说，就是我们在评价一个特征优先级时候的评价标准是什么。这个评价标准，在决策树中非常重要，一个合适评价标准，可以将不同的特征按照非常合理的方式进行优先级排序，从而能够构建出一颗比较完美的决策树。而一个不合适的评价标准则会导致最终构造的决策树出现种种问题。
2.2、评价标准是什么/如何量化评价一个特征的好坏？
在不同的决策树算法中，这个特征好坏的评价标准略有不同。比如，在问哦们今天讲的ID3算法中，评价标准是一个叫做 信息增益(Information Gain) 的东西。而在另一个决策树算法C4.5中，评判标准则进一步变为信息增益比(Information Gain Ration或Gain Ratio)。另外一个比较主流的决策树算法CART算法则是采用 基尼系数(Gini Index) 作为评判标准。这些东西，我们会在后面的几篇文章中一一涉及到，在本文中，我们将关注的重点放在信息增益上。
在进入正题之前，我们需要先了解一些简单的概念。第一个需要我们了解的概念叫做熵/entropy。学过中学物理的朋友们可能会有一些印象：熵，热力学中表征物质状态的参量之一，用符号S表示，其物理意义是体系混乱程度的度量。熵这个概念最初源自于热力学中，1948年，香农引入了信息熵，将其定义为离散随机事件出现的概率。在信息学里面，熵是对不确定性的度量。 一个系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。 所以信息熵可以被认为是系统有序化程度的一个度量。其本质与热力学中的熵的概念是相同的。
可这又和我们今天要讲的信息增益这个评判标准有什么关系呢？我们不妨这样想，当我们得到一组信息，一组类似于上图左半部分的信息。该组信息有多个特征(如学历、学校等)，同时有一组综合每一个特征得到的结论。上图展示的这组信息只有A、B、C、D四个实例，倘若我们有成千上万个实例，但看这成千上万实例构成的表格，我们的第一感受可能是混乱。没错，如此多的实例，粗鲁地被凭借在同一个表格中，实在是太混乱了。将混乱换成我们刚刚提到过的说法：这组信息的信息熵太高了。
这样的场景，尤其是当我们想要通过这张表去查询某些东西，更是非常不便。我们希望可以有某种方法，在降低系统混乱程度/降低系统熵值的同时，不损害信息的完整性。那么有没有这么一种方法呢？当然有的，就是我们今天讲到的决策树算法。从上图的左边，到上图右边的转变，我们可以非常直观感受到，这组信息不仅变得不那么混乱，而且这种树形的表示方式，比较符合我们人类的思维习惯。
为什么会出现这样感受上的差异呢？其实很简单，因为我们从右图的根节点开始，每做一次特征的划分，整个系统的熵值就得到了一次降低。 这个信息系统给我们的感受也就越来越规范。进而，我们很容易地引出信息增益地概念：信息增益就是我们以某一个特征划分某个信息系统后，这个系统整体信息熵降的数值。接下来，我们很容易可以回答如何去判断一个特征的好坏：如果一个特征，相较于其他所有特征，在将一个信息系统按照该特征划分前后，可以将整个数据系统的信息熵降到最低（信息增益最大），这个特征就是一个好的特征。我们应该优先使用该特征进行系统的划分。
2.3、信息熵、信息增益的计算在此，我们先给出信息熵的计算公式：
https://img-blog.csdnimg.cn/20190801154047417.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29nbmFN,size_16,color_FFFFFF,t_70#pic_center
知道了信息熵的计算公式后，信息增益的计算公式也很容易理解，就是当前系统的信息熵S，减去按照某个特征划分整个系统后，每个子系统的信息熵乘以每个子系统在整个系统所占比例(Si X Pi)，最后相加得到的值。也即：信息增益 InfoGain = S-Σ(SixPi)。举个例子，我们得到如下图所示的一个信息系统(该系统前四列为不同的四个特征，最后一列为结果。)，那么要如何计算整个系统的信息熵，以及该系统对应某个特征的信息增益呢？
https://img-blog.csdnimg.cn/20190801153054108.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29nbmFN,size_16,color_FFFFFF,t_70#pic_center
首先，可以看出，结果列中一共有14个样例，其中包括9个正例和5个负例。那么当前信息的熵计算
https://img-blog.csdnimg.cn/20190801152513377.png#pic_center
上面，我们计算出了整个系统的信息熵，也就是未对数据进行划分时的信息熵。那么下面我们计算使用某个特征对系统进行划分后，整个系统的信息熵，以及划分前后系统信息熵的差值(信息增益)比如，我们根据第一个特征Outlook进行划分：
https://img-blog.csdnimg.cn/20190801152949706.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29nbmFN,size_16,color_FFFFFF,t_70#pic_center
划分后，数据被分为三部分了，那么各个分支的信息熵（子系统信息熵）计算如下:
https://img-blog.csdnimg.cn/20190801153419446.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29nbmFN,size_16,color_FFFFFF,t_70#pic_center
我们将每个子系统的信息熵，乘以该子系统在整个系统中所占比例，依次相加后，得到划分后系统的整体信息熵。如下图所示：
https://img-blog.csdnimg.cn/20190801153655781.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29nbmFN,size_16,color_FFFFFF,t_70#pic_center
最后，终于来到我们最激动人心的一步了，计算信息增益，如下图所示：
https://img-blog.csdnimg.cn/20190801153848560.png
2.4、决策树构建方法
在上一步中，我们计算出每个特征所对应地信息增益，选取信息增益最大的特征优先划分整个系统（将系统划分为一个个子数据集/子树/子系统）。
在每个子系统中，我们再 重新计算 未被使用过的特征的优先级，并选择优先级最大的特征继续划分数据集构造子树。知道，该递归构造子树的过程因为某些原因终止为止。2.4、构造终止的条件/何时停止构造子树？1、当我们发现一个子树中，结果完全相同，如结果全部为YES的时候，就没有在该子树中继续构造下去的必要了(其他子树中的构造过程未必终止)。此时我们得到该子树最终的结果为YES。2、当我们发现一个子树中，虽然其结果没有完全相同，但已经没有可以支撑我们继续构造子树的特征了(简而言之就是所有特征都已经用过了)，这个时候就可以停止在该子树中继续构造了。此时，该子树的最终结果为该子树集合的结果列中，出现次数最多的哪个属性值。
https://static.52pojie.cn/static/image/hrline/4.gif
3、算法总结
1、判断每一个子树中的每个例子结果是否一致或是否特征已用尽
是：该子树构造完成，返回该子树对应的最终结果。
否：继续递归构造子树
若1中结果为否，则：
1.1、计算当前子系统信息熵
1.2、计算未被使用过的特征的信息增益
1.3、选取最大的信息增益的特征进行划分，并从特征集合中删除该特征
1.4、根据3中划分构造子树，并转向步骤1。
https://static.52pojie.cn/static/image/hrline/4.gif
4、源码
纯文本查看 复制代码
?
001002003004005006007008009010011012013014015016017018019020021022023024025026027028029030031032033034035036037038039040041042043044045046047048049050051052053054055056057058059060061062063064065066067068069070071072073074075076077078079080081082083084085086087088089090091092093094095096097098099100101102103104105106107108109110# coding=utf-8from math import logimport copy# --------------------------------------------------------# 信息初始化 -# --------------------------------------------------------def InputData():initData = [ , , , , , , , , , , , ]dataLables = ['feature_A','feature_B','feature_C']return initData,dataLablesinitData,dataLables = InputData() # --------------------------------------------------------# 计算当前数据集的信息熵 -# --------------------------------------------------------def CalcEntropy(initData):newDataLen = len(initData)resultList = for row in initData]resultType = set(resultList)entropy = 0for x in resultType:pi = float(resultList.count(x)) / newDataLenentropy -= pi*log(pi,2)return entropy# print(CalcEntropy(initData)) # --------------------------------------------------------# 分割后，初始数据集不应该被改变 -# --------------------------------------------------------def SplitData(initData,featureNum,featureValue):newData = []dataCopy = copy.deepcopy(initData)for row in dataCopy:if row == featureValue: del row newData.append(row)return newData# print(initData)# print(SplitData(initData,1,0))# print(initData) # --------------------------------------------------------# 选取最佳标志 -# 选取信息增益最大，即条件熵最小的属性作为分裂属性 -# --------------------------------------------------------def ChooseFeature(initData):dataLen = len(initData) - 1elemNum = len(initData)entropy = 0biggestEntropy = 10000bestFeatureNum = 0for i in range(0,dataLen):featureSet = set( for row in initData])for j in featureSet: subData = SplitData(initData,i,j) subEntropy = CalcEntropy(subData) entropy += float(len(subData)) / elemNum * subEntropyif entropy < biggestEntropy: bestFeatureNum = i biggestEntropy = entropyreturn bestFeatureNum # --------------------------------------------------------# 获取list中出现最多次的元素 -# --------------------------------------------------------def MaxList(lt): temp = 0 for i in lt: if lt.count(i) > temp: max_str = i temp = lt.count(i) return max_str # ------------------------------------------------------------# 递归方式构建dict树。终止条件有两种：1、当前数据集中所有结果一致 -# 2、当前数据集虽然结果不一致，但已无继续判断的条件/lable，此时返-# 回当前数据集最后一列出现最多次的元素。另外，lables也要做深拷贝-# 因为当for循环遍历当前数据集子集时，lable的初始值应该是相同的 -# -----------------------------------------------------------def CreateTree(data,lables):# print(data)resultList = for x in data]if resultList.count(resultList[-1]) == len(resultList):return resultList[-1]elif len(data) == 1:return MaxList(resultList)bestFeatureNum = ChooseFeature(data)bestFeatureName = lablestree = {bestFeatureName:{}}lables.remove(bestFeatureName)featureSet = set( for row in data])for value in featureSet:subLables = copy.deepcopy(lables)# value作为树枝，将前后两次迭代的两个tree连接起来tree = CreateTree(SplitData(data,bestFeatureNum,value),subLables)return treeprint(CreateTree(initData,dataLables))
运行结果：file:///C:/Users/Zzzz/AppData/Roaming/Typora/typora-user-images/1570675296961.png?lastModify=1570676154
Tree:
{'feature_A': {0: {'feature_B': {0: {'feature_C': {0: 'no', 1: 'yes'}}, 1: 'yes'}}, 1: 'yes'}}
抱歉，未能达到申请要求，申请不通过，可以关注论坛官方微信（吾爱破解论坛），等待开放注册通知。
页:
[1]