侯勋 方刚

(重庆三峡学院，重庆 404020)

1 概述

随着科技的飞速发展，人类积累的数据也越来越多，以数字化储存的数据信息量达到了一个十分庞大的地步，这些数据中也存在着大量有用的信息和知识。同时为了获得这些信息和知识，数据挖掘技术被人们发现并应用，在短时间内就应用于各行各业[1]。

决策树算法是应用最为广泛的数据挖掘算法之一[2]，它易于理解和解释。而在决策树算法中，ID3[3]算法是最具影响力和独特地位的算法，之后的许多决策树算法都是由之延伸而来。但是作为基础的决策树算法，ID3算法也存在许多不足之处。ID3算法在分类过程中存在多值倾向问题，且它是贪心算法，存在着局部最优问题。因此本文提出一种ID3的改进，在计算信息增益时引入修正函数以达到属性的信息增益修正的目的，解决多值偏向问题[4]。并利用遗传算法对决策树算法进行优化[5]，能有效的解决ID3算法面对的问题。

2 ID3 算法概念及改进原理

2.1 ID3算法概念

ID3算法的核心思想是以信息增益值作为属性选择度量，将具有最大增益值的属性作为最优分裂属性，对属性进行分类[6]。

信息增益指的是划分前后熵的变化，可以用下面的公式表示：

其中，A表示样本的属性，Value(A)是属性A所有的取值集合。V是A的其中一个属性值，SV是S中A的值为V的样例集合。

熵的公式可以表示为：

2.2 肯德尔等级相关系数

肯德尔等级相关系数的定义为：设X、Y两个集合的元素个数均为N，两个随即变量取的第i（1<=i<=N）个值分别用Xi、Yi表示。X与Y中的对应元素组成一个元素对集合XY，其包含的元素为(Xi,Yi)（1<=i<=N）。当集合XY中任意两个元素(Xi,Yi)与(Xj,Yj)满足Xi>Xj且Yi>Yj或XiXj且YiYj时这两个元素被认为是逆序对。当……