一种决策树ID3算法及其优化的实现

　　决策树（ Decision Tree ）又称为判定树，是运用于分类的一种树结构。其中的每个内部结点（ internal node ）代表对某个属性的测试，每条边代表一个测试结果，叶结点（ leaf ）代表某个类（ class ）或者类的分布（ class distribution ），上面的结点是根结点。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。构造决策树是采用自上而下的递归构造方法。决策树构造的结果是一棵二叉或多叉树，它的输入是一组带有类别标记的训练数据。二叉树的内部结点（非叶结点）一般表示为一个逻辑判断，如形式为 （a = b） 的逻辑判断，其中 a 是属性，b 是该属性的某个属性值；树的边是逻辑判断的分支结果。多叉树（ ID3 ）的内部结点是属性，边是该属性的所有取值，有几个属性值，就有几条边。树的叶结点都是类别标记。

　　1 决策树分类过程

　　决策树的分类过程也就是决策树分类模型（简称决策树）的生成过程，如图1所示。从图中可知决策树分类的建立过程与用决策树分类模型进行预测的过程实际上是一种归纳-演绎过程。其中，由已分类数据得到决策树分类模型的过程称归纳过程，用决策树分类模型对未分类数据进行分类的过程称为演绎过程。需要强调的是：由训练集得到分类模型必须经过测试集测试达到一定要求才能用于预测。

  

　　信息增益是不确定性的消除，也就是接收端所获得的信息量。

　　2.2 ID3算法多值偏向性分析

　　ID3算法是由Quinlan首先提出的。该算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。在梳理ID3改善，添加了特征选择的启发。ID3搜索通过属性的训练资料中，分离出的属性，在给定的例子。如果属性的完全分类的训练集然后ID3停止的，否则它递归的运作就n（n =可能出现的数量在一个属性的值划分子集）去得到他们的""的属性。ID3算法计算每个属性的信息增益，并选取具有增益的属性作为给定集合的测试属性。对被选取的测试属性创建一个节点，并以该节点的属性标记，对该属性的每个值创建一个分支据此划分样本。

　　首先，设A是某训练样本集的一个属性，它的取值为A1,A2,…，An,创建另外一个新属性A′，它与属性A的区别：其中一个已知值An分解为两个值A′n和A′n+1,其余值和A中的完全一样，假设原来n个值已经提供足够的信息使分类正确进行，很明显，则属性A′相对于A没有任何作用。但如果按照Qulnina的标准，属性A′应当优先于属性A选取。

　　综上所知，把ID3算法分别作用在属性A和属性A′上，如果属性选取标准在属性A′上的取值恒大于在属性A上的取值，则说明该算法在建树过程中具有多值偏向；如果属性选取标准在属性A′上的取值与在属性A上的取值没有确定的大小关系，则说明该决策树算法在建树过程中不具有多值偏向性。

　　2.3 ID3算法的缺点

　　（1）ID3算法往往偏向于选择取值较多的属性，而在很多情况下取值较多的属性并不总是重要的属性，即按照使熵值的原则被ID3算法列为应该首先判断的属性在现实情况中却并不一定非常重要。例如：在银行客户分析中，姓名属性取值多，却不能从中得到任何信息。

　　（2）ID3算法不能处理具有连续值的属性，也不能处理具有缺失数据的属性。

　　（3）用互信息作为选择属性的标准存在一个假设，即训练子集中的正、反例的比例应与实际问题领域中正、反例的比例一致。一般情况很难保证这两者的比例一致，这样计算训练集的互信息就会存在偏差。

　　（4）在建造决策树时，每个结点仅含一个属性，是一种单变元的算法，致使生成的决策树结点之间的相关性不够强。虽然在一棵树上连在一起，但联系还是松散的。

　　（5）ID3算法虽然理论清晰，但计算比较复杂，在学习和训练数据集的过程中机器内存占用率比较大，耗费资源。

　　决策树ID3算法是一个很有实用价值的示例学习算法，它的基础理论清晰，算法比较简单，学习能力较强，适于处理大规模的学习问题，是数据挖掘和知识发现领域中的一个很好的范例，为后来各学者提出优化算法奠定了理论基础。表1是一个经典的训练集。

　　由ID3算法递归建树得到一棵决策树如图2所示。

　　3 ID3算法优化的探讨

　　ID3算法在选择分裂属性时，往往偏向于选择取值较多的属性，然而在很多情况下取值较多的属性并不总是重要的属性，这会造成生成的决策树的预测结果与实际偏离较大，针对这一弊端，本文提出以下改进思路：

　　（1）引入分支信息熵的概念。对于所有属性，任取属性A,计算A属性的各分支子集的信息熵，在每个分支子集中找出信息熵，并计算其和，比较大小，选择其值作为待选择的属性。

　　（2）引入属性优先的概念。不同的属性对于分类或决策有着不同的重要程度，这种重要程度可在辅助知识的基础上事先加以假设，给每个属性都赋予一个权值，其大小为（0,1）中的某个值。通过属性优先法，降低非重要属性的标注，提高重要属性的标注。

　　4 实例分析

　　仍以表1为例，分别计算其H（A）的值。在此通过反复测试，天气的属性优先权值为0.95,风的属性优先权值为0.35,其余两个的属性优先权值都为0.

　　（1）确定根结点

　　选取天气属性作为测试属性，天气为多云时，信息熵为：

 

　　根据算法步骤（6），选择值H（A）为的作为候选属性，所以此时应选择湿度作为根结点。在24个训练集中对湿度的2个取值进行分枝，2个分枝对应2个子集，分别为：

　　通过比较ID3算法和本文所提出的组合优化算法所生成的决策树可知，组合优化算法的改进为：

　　（1）从本实例所生成的决策树的形态来看，改进后的算法生成的是一棵二叉树，而ID3算法生成的是多叉树，简化了决策问题处理的复杂度。

　　（2）引入了分支信息熵和属性优先的概念，用条件熵、分支信息熵与属性优先三者相结合来选择分裂属性。从本实例来看，根结点选择湿度而未选择属性值多的天气，所以本优化算法确实能克服传统ID3算法的多值偏向性。