基于信息熵的ID3算法

基于信息熵的ID3算法ID3算法是一个典型的决策树学习算法，其核心是在决策树的各级节点上，使用信息增益方法作为属性的选择标准，来帮助确定生成每个节点时所应采用的合适属性。这样就可以选择具有最高信息增益属性作为当前节点的测试属性，以便使用该属性所划分获得的训练样本子集进行分类所需信息最小。定义1设U是论域，nXX,...,1是U的一个划分，其上有概率分布)(iiXPp，则称：niiippXH1log)(为信源X的信息熵，其中对数取以2为底，而当某个ip为零时，则可以理解为00log0。定义2设nn　　q　　　　qq　　Y　　　　YYY2121是一个信息源，即nYY　Y,,,21是U的另一个划分，jjqYP)(，njjq11，则已知信息源X是信息源Y的条件熵H(Y|X)定义为：niiiXYHXPXYH1)|()()|(其中njijijiXYPXYPXYH1)|(log)|()|(为事件iX发生时信息源Y的条件熵。在ID3算法分类问题中，每个实体用多个特征来描述，每个特征限于在一个离散集中取互斥的值。ID3算法的基本原理如下：设nFFFE21是n维有穷向量空间，其中iF是有穷离散符号集。E中的元素nVVVe,,,21称为样本空间的例子，其中ijFV，),,2,1(nj。为简单起见，假定样本例子在真实世界中仅有两个类别，在这种两个类别的归纳任务中，PE和NE的实体分别称为概念的正例和反例。假设向量空间E中的正、反例集的大小分别为P、N，由决策树的基本思想，ID3算法是基于如下2种假设：（1）在向量空间E上的一棵正确的决策树对任意样本集的分类概率同E中的正、反例的概率一致。（2）根据定义1，一棵决策树对一样本集做出正确分类，所需要的信息熵为：NPNNPNNPPNPPNPIloglog),(如果选择属性A作为决策树的根，A取V个不同的值VAAA,,,21，利用属性A可以将E划分为V个子集VEEE,,,21，其中)1(ViEi包含了E中属性A取iA值的样本数据，假设iE中含有ip个正例和in个反例，那么子集iE所需要的期望信息是),(iinpI，以属性A为根所需要的期望熵为：ViiiiinpINPnpAE1),()(其中，iiiiiiiiiiiiiinpnnpnnppnppnpIloglog),(以A为根的信息增益是：)(),()(AENPIAGainID3算法选择)(AGain最大的属性*A作为根节点，对*A的不同取值对应的E的V个子集iE递归调用上述过程生成的*A的子节点VBBB,,,21。ID3算法的基本原理是基于两类问题的，但是它很容易被扩展到多类问题。设样本集S共有C类样本，每类的样本数为),,2,1(CiPi。如果以属性A作为决策树的根，A具有V个值VAAA,,,21，它将E划分为V个子集VEEE,,,21。假设iE中含有的第j类样本个数为),,2,1(CiPij，那么子集iE的信息量，即熵为：||log||)(1iijCjiijEPEPEH以A为根分类后的信息熵为：)(||||)|(1iViiEHEEAEH选择属性*A，使)|(AEH最小，信息增益将最大。实际上，能正确分类训练集的决策树不止一棵。ID3算法能得出节点最小的决策树。在ID3算法的每一个循环过程中，都对训练集进行查询以确定属性的信息增益，然而此时的工作只是查询样本的子集而没有对其分类。为了避免访问全部数据集，ID3算法采用了称为窗口（Windows）的方法，窗口随机性是从数据集中选择一个子集。采用该方法会大大加快构建决策树的速度。ID3算法的主算法非常简单，首先从训练集中随机选择一个窗口（既含正例又含反例的样本子集），对当前的窗口形成一棵决策树；其次，对训练集（窗口除外）中例子用所得到的决策树进行类别判定，找出错判的例子。若存在错判的例子，把他们插入窗口，转到建树过程，否则停止。算法每迭代循环一次，生成的决策树将会不同。ID3算法以一种从简单到复杂的爬山策略遍历这个假设空间，从空的树开始，然后逐步考虑更加复杂的假设。通过观察搜索空间和搜索策略，我们可以发现，它同样存在着一些优势和不足。ID3算法的优点：（1）ID3算法的假设空间包含所有的决策树，搜索空间也是完整的假设空间。因为每个有限离散值函数可以被表示为某个决策树，所以它避免了假设空间可能不包含目标函数的风险。（2）ID3算法在搜索的每一步都使用当前的所有训练样本，以信息增益的标准为基础决定怎样简化当前的假设。使用信息增益这一统计属性的一个优点是大大降低了对个别训练样例错误的敏感性，因此，通过修改算法可以很容易地扩展到处理含有噪声的训练样本。（3）ID3算法采用自顶向下的搜索策略，搜索全部空间的一部分，确保所作的测试次数较少，分类速度较快。算法的计算时间与样本例子个数、特征个数、节点个数三者的乘积呈线性关系。（4）ID3算法与最基础的决策树算法一样，非常适合处理离散值样本数据，并且利用树型结构的分层的效果，可以轻而易举地提取到容易理解的If-Then分类规则。（5）由于引进了信息熵的概念，ID3算法能得出节点数最少的决策树。ID3算法存在的不足之处（1）当遍历决策树空间时，ID3算法仅维护单一的当前假设，它失去了表示所有一致假设带来的优势。比如，它不能判断有多少其他的决策树也是与现有的训练数据一致的，或者使用新的实例查询来最优地区分这些竞争的假设。（2）ID3算法在搜索中不进行回溯，每当在树的某一层选择了一个属性进行测试，它不会再回溯重新考虑这个选择。这样，算法容易收敛到局部最优的答案，而不是全局最优的。（3）ID3算法使用的基于互信息的计算方法依赖于属性值数目较多的属性，但是属性值较多的属性不一定是分类最优的属性。（4）ID3算法是一种贪心算法，对于增量式学习任务来说，由于它不能增量地接受训练样例，使得每增加一次实例都必须抛弃原有的决策树，重新构造新的决策树，造成极大的开销。所以，ID3算法不适合于渐进学习。（5）ID3算法啊对噪声较为敏感。Quinlan定义噪声未训练样本数据中的属性值错误和分类类别错误。（6）ID3算法将注意力集中在属性的选择上，而这种方式已受到一些学者的怀疑，属性选择对决策树的精度是否影响很大，至今仍无定论。总的来说，ID3算法由于理论清晰、方法简单、学习能力较强，适于处理大规模的学习问题，是数据挖掘和机器学习领域中的一个极好范例，也不失为一种知识获取的有用工具。