ID3数据挖掘算法

ID3数据挖掘算法（精选8篇）

ID3数据挖掘算法 第1篇

随着信息技术的发展, 数据量以惊人的速度增长, “数据丰富, 知识贫乏”的矛盾日益突出, 各个领域迫切需要有一种能够从存储海量数据的数据集、数据库、数据仓库中寻求有用信息的工具, 数据挖掘技术应运而生。ID3 (Iterative Dichotomiser versions3, 迭代二叉树第三版本) 算法由John Ross Quinlan于1986年提出, 是数据挖掘中影响较大的经典决策树技术之一[1], 采用信息增益 (即信息论中的互信息) 来选择属性作为决策树的节点。由于决策树的建树算法思想简单, 识别样本效率高的特点, 使ID3算法广泛应用于故障诊断、数据分析、评估、森林火警预报、信用评级等领域。

通常运用ID3算法对海量数据的对象进行挖掘时, 存储的数据或记录都有确切的数值, 挖掘的结果与数据源样本分布有着密切的关系。但是, 许多实际应用中的数据没有明确的大小, 或者根本无法取确切数值, 比如天气预报中温度高低、湿度大小, 以及信用等级、安全程度、高考志愿的理想程度、中医辨症中病的轻重等, 记录的填写都是模糊的, 数据没有分明的数量界限, 不可以简单地用是非真假或数字来表示的, 因不需要精确信息而导致无法运用ID3算法进行数据挖掘。

因此, 笔者提出模糊ID3数据挖掘算法, 扩大ID3算法的适用范围, 从而可以对存储模糊数据的数据集、数据库、数据仓库的海量数据记录进行挖掘, 挖掘结果的决策树更加科学, 利于寻找数据中隐藏的规律。

1 ID3算法

ID3算法以信息论为基础, 以信息熵和信息增益度为衡量标准度量数据样本特征的判别能力。它将建立决策树的丰富嵌入在迭代过程中, 采用自顶向下不回溯的策略搜索全部的属性空间, 从而实现对数据的归纳与分类。J.R.Quinlan提出的ID3算法可以归纳为主算法和建树算法两种[1,2]。

主算法的步骤为:

(1) 从数据源中随机提取一个含有正例和反例的样本集;

(2) 用“建树算法”对该样本集进行训练, 生成一棵决策树;

(3) 将数据源中的样本集以为的数据用所建立的决策树进行类别判定, 找出错例;

(4) 如果存在错误的例子, 则将其放入样本集中, 重复步骤 (2) , 否则结束。

建树算法的步骤为:

(1) 计算从数据源提取的样本集的各特征的互信息;

(2) 选择互信息最大的特征Ak;

(3) 将在Ak处取相同值的例子分为同一样本子集。Ak取值个数与子集个数相同。

(4) 对含有正例和反例的样本子集递归调用建树算法;

(5) 若子集仅含有正、反例, 对生成的决策树相应分枝作P、N标记真假, 返回。

ID3算法特点可以归纳为:

(1) 使用所有没有使用的属性并计算与之相关的样本熵值。

(2) 选取其中熵值最小的属性。

(3) 生成包含该属性的节点。

(4) 得到结点最少的决策树。

2 模糊ID3算法

ID3算法模糊化后, 主算法基本保持不变, 但建树算法在样本数据提取、训练数据、生成决策树叶子结点数据都用模糊数据来表示。模糊ID3建树算法为:

(1) 提取数据源的模糊样本, 根据模糊数值计算各特征的互信息, 得到精确数值;

(2) 选择最大互信息特征Ak;

(3) 将在Ak处取相同值例子分为相同样本子集, 样本子集的类别结果为模糊的。

(4) 对含有多个模糊样本子集递归调用建树算法;

(5) 若子集仅含有限模糊类别的样例, 对生成的决策树对应分枝作C1、C2、C3等标记, 返回调用处。

模糊ID3算法建树的计算过程为:

(1) 计算信息熵H (U) 。

其中, 表示训练样本子集S的总个数, 表示样本模糊值为类别为的例子数。

(2) 计算条件熵

属性A1取值vj时, 类别ui的条件概率为:

(3) 计算互信息。

选择较大I (A1) , 递归建立决策树。

3 实例研究

实例的数据源为我校学生评优部分信息, 如表1所示。

基于ID3算法进行数据挖掘后得到的决策树如图1所示。其中P表示获得评优资格, N则不具备评优资格。

从数据挖掘的结果可以看出, 叶子结点的结论基本与评优实际相符, 模糊ID3算法能从一组无次序、无规则的实例中推理出决策树表示形式的规则, 样本以外是训练数据可以通过该树来判定类别, 而且ID3具有以下一些特点:

(1) 对于挖掘对象为模糊事物时, 数据源或样本中的数据可以使用一些模糊的词句来形容、描述;比如评优, 用模糊数据表达更符合常理。

(2) 数据挖掘结果也可以是模糊的。生成的决策树中由根结点到叶子结点的每一条分枝对应一条if A then B的规则, 其中A和B都可以用模糊数据来表示;而模糊关联规则的生成, 有利于在计算机上实现。

(3) 能实现模糊化分类, 而不是非此即彼的简单判定, 可以根据隶属函数的模糊取值来确定类别。

(4) 训练数据的样本集类别往往客观地根据人们的生活、工作的经验给定, 与现实的模糊世界相符, 而模糊运算可以省略。

4 结束语

模糊ID3算法思路情形, 计算简单, 适用范围广, 学习能力强, 分类速度快, 分类结论更接近实际, 适合处理存储海量模糊信息的对象, 是一种获取模糊知识的有效工具, 为提供各种决策支持有着现实的意义。

摘要：针对ID3算法难以对存储模糊记录的大规模数据集、数据库、数据仓库等对象进行数据挖掘的问题, 基于模糊数学理论提出了模糊ID3算法。它扩大了ID3算法的适用范围, 更加容易生成合理的决策树, 加快了分类速度, 以及能为各领域提供决策支持。

关键词：数据挖掘,ID3算法,决策树,模糊

参考文献

[1]QUINLAN J R.Induction of decision tree[J].Machine learning, 1986 (1) :81-106.

[2]陈文伟, 黄金才.数据仓库与数据挖掘教程[M].北京:清华大学出版社, 2006.

[3]杨纶标.模糊数学原理及应用[M].广州:华南理工大学出版社, 2006.

[4]Shekhar R.Gaddam, Vir V.Phoha and Kiran S.Balagani.K-Means+ID3:A Novel Method for Supervised Anomaly Detection by Cascading K-Means Clustering and ID3Decision Tree Learning Methods[J].IEEE Transactions on Knowledge and Data Engineering.2007, 19 (3) :345-354.

数据压缩算法研究 第2篇

关键词 数据压缩 预测编码 压缩感知 小波变换

中图分类号：TP393 文献标识码：A

0引言

数据压缩技术一直是一个热门研究领域，其作用是去除数据中存在的冗余信息，以不影响数据内容为前提，尽量减小数据存储大小。

1预测编码技术

预测编码技术根据信源存在的时空相关性这一特点去预测信源数据，然后用预测数据减去真实信源数据得到预测值，最后将差值进行存储，利用这种方法去除信源中的冗余信息，实现数据压缩的目的。

预测是根据前n个测量参数，估计当前的测量值。x0表示当前测量值，表示估计值，同时{€%Zi|i=1，2，…，N}是预测系数，其中N是预测的阶数。

预测估计值：

（1.1）

预测误差：

（1.2）

测量的预测误差记作MSE：

MSE=e2i （1.3）

预测多项式阶数越高，预测准确性越高，计算复杂性也急剧增加。

2时间序列线性拟合技术

数据在一段时间内保持相对稳定的某种趋势，使得采样数据构成时间序列，可以通过构建合适的时间序列数学模型得到近似的数据，使数据量少于原时间序列，达到数据压缩的目的。

时间序列为：

s=（（t1，d1），（t2，d2），…，（tn，dn）） （1.4）

其中（ti，di）表示在ti时的采样值为di，n为采样次数。时间序列的拟合回归线为就是以时间t为自变量，以采样数值d为因变量的函数。令

d=€%Z+€%[t+€%g，€%g∈（0，€%]2） （1.5）

对上式参数采用最小二乘法进行线性拟合，得到€%Z，€%[的估计值分别为：

（1.6）

得到回归方程：

（1.7）

3小波变换

小波变换在时域频域都具有表征信号局部特征的能力和多分辨率分析的特点，它将原始信号伸缩和平移，分解为一系列频率不同的子带信号， 这些子带信号具有良好的时域、频域等局部特征。这些特征可用来表示原始信号的局部特征，进而实现对信号时间、频率的局部化分析，压缩后数据失真更小，压缩效率也更高。

小波变换将信号表示成基函数的线性组合，其基函数是具有紧支集的母函数，对母函数伸缩和平移可以得到小波序列。

（2.1）

其中a为伸缩因子，b为平移因子。

对于任意函数F（t）属于L2（R）的连续小波变换为：

Wf（€%Z，b）=fflF，€%q€%Z，bffl=|€%Z|1/2RF（t）€%q*·（）dt （2.2）

其逆变换为：

F（t）=Wf（€%Z，b）€%q（）d€%Zdb （2.3）

基本小波函数的选择取决于实际应用，小波函数在几何形状必须是振荡函数和迅速收敛的函数。尺度因子和平移因子的不同会给小波函数的几何形状带来很大的变化。

4压缩感知

对某一信号 f 进行采样实际上就是将该信号同一系列波形进行内积运算。例如：奈奎斯特采样就是信号 f 与一组频率大于2 f 的脉冲信号的内积。

yk，k=1，……，m （3.1）

压缩感知采用波形数目远小于信号维数的采样信号对信号 f 进行欠采样。得到的信号采样值的数目m远小于原始信号 f 的维数n。因此压缩感知在采样的同时实现了对信号的压缩。

压缩感知将n维可压缩信号x∈k通过采样矩阵€%O∈Cm，n（m<

y=€%Ox （3.2）

如果信号 f 在域是稀疏的，那么式（5）就可以写为

y=€%Ox=€%O€%ox=Ax （3.3）

其中x为信号 f 在€%o域的系数，A=€%O€%o是一个m€譶阶的矩阵，称之为感知矩阵。

Candes和Tao指出采样矩阵€%O需要满足一定的约束等距条件，如果测量矩阵€%O的约束等距常数满足€HQ2k+€HQ3k<1，则能够从k·log（n /k）个测量值中精确恢复出原始信号。

定义：对于矩阵€%O∈Cm，n（m<

（3.4）

的最小数值€HQk定义为矩阵€%O的约束等距常数。如果€HQk∈（0，1），就说矩阵€%O满足k阶约束等距性。

压缩感知恢复算法的做法是对信号或其变换系数的非零元素个数进行约束，通过l0范数最小化求解：

s.t.y=€%Of=€%O€%ox （3.5）

其中||x||0，是l0范数。

Donoho等利用l0范数代替l0范数，将（9）的非凸组合优化问题转化为凸松弛问题求解：

s.t.y=€%Of=€%O€%ox （3.6）

其中||x||0，是l1范数。基追踪 （BasisPursuit，BP）方法将（10）中有约束的l1范数最小化问题转换为线性规划问题进行求解。如果信号足够稀疏，l1范数最小化方法能够比较精确的恢复出原始信号。

5总结

数据压缩算法还有很多，文中只列出了最常见、目前切实可行的、比较成熟的压缩算法，还有很多算法处于各种原因，未能真正的走进人们的生活，下一步将对这些算法进行深入研究。

参考文献

[1] Hao Yong-zhi，Chen Jun-jie. Based data compression energy saving method for wireless sensor networks [J]. Huazhong University of Science and Technology （Natural Science edition） ， 2008， 36 （ S1） ： 232-234.

[2] Liu Xiang-yu，Wang Ya-zhe，Yang Xiao-chun，et al. Facing the wireless sensor network streaming data compression technology [J]. Computer Science， 2007，34（ 2） ： 141-143.

[3] 赵洁， 汤宝平， 姚金宝， 卢得芳. 一种自适应最优化小波变换算法及应用[J]. 重庆大学学报.第31卷第9期.2008，09：1028-1033.

[4] 戴琼海，付长军，季向阳.压缩感知研究[J].计算机学报.第34卷第3期. 2011，03：425-434.

ID3数据挖掘算法 第3篇

关键词：分类,决策树,信息论,ID3

1 决策树的定义

在决策树方法中, 有两个基本的步骤:构建树和将树应用于数据库。大多数研究都集中在如何有效地构建树, 而应用过程是很简单的。

定义1给出了决策树分类方法的定义。

定义1给定一个数据库D={t1, ..., tn}, 其中ti= (ti1, ..., tih) , 数据库模式包含下列属性{A1, A2, ..., Ah}。同时给定类别集合C={C1, ..., Cm}。对于数据库D, 决策树 (或分类树) 是指具有下列性质的树:

每个内部结点都被标记一个属性Ai;

每条弧都被标记一个谓词, 这个谓词可应用于相应父结点的属性;

每个叶结点都被标记一个类Cj。

利用决策树求解分类问题包括两个步骤: (1) 决策树归纳利用训练数据集构建一棵决策树; (2) 对每个元素, 应用决策树确定元素的类别。

2 ID3算法的信息论基础

信息论是C.E.Shannon为解决信息传递 (通信) 过程问题建立的一系列理论。一个传递信息的体统是由发送端 (信源) 和接收端 (信宿) , 以及连接两者的通道 (信道) 组成。信息论把通信过程看作是在随机干扰的环境中传递信息的过程。在这个通信模型中, 信息源和干扰 (噪声) 都被理解为某种随机过程或随机序列。因此, 在进行实际的通信之前, 收信者不可能确切了解信源究竟会发出什么样的具体信息, 不可能判断信源会处于怎样的状态, 这种情形就称为信宿对于信源状态具有不确定性。由于这种不确定性存在于通信之前, 因而又叫做先验不确定性。

在进行了通信之后, 信宿收到了信源发来的信息, 这种先验不确定性才会被消除或者被减少。如果干扰很小, 不会对传递的信息产生任何可察觉的影响, 信源发出的信息能够被完全收到, 在这种情况下, 信宿的先验不确定性就会被完全消除。但是, 在一般情况下, 干扰总会对信源发出的信息造成某种破坏, 使信宿收到的信息不完全。因此, 先验不确定性不能全部被清除。即通信结束后, 信宿还仍然具有一定程度的不确定性。这就是后验不确定性。

显然, 后验不确定性总要小于先验不确定性, 不可能大于先验不确定性。如果后验不确定性的大小正好等于先验不确定性的大小, 这就表示信宿根本没有收到信息。如果后验不确定性的大小等于零, 这就表示信宿收到了全部信息。

可见, 信息是用来消除不确定的东西。信息量的到小, 由所消除的不确定性的大小来计量。

3 基于互信息的ID3算法

3.1 ID3算法的基本思想

在实体世界中, 每个实体用多个特征来描述。每个特征限制在一个离散集中取互斥的值。例如, 设实体是某天早晨的气候, 分类任务是得到关于气候的类型有如下特征和取值:

outlook={sunny, overcast, rain}

temperature={cool, mild, hot}

humidity={high, normal}

windy={true, false}

某天早晨的气候描述为:

outlook:overcast

temperature:cool

humidity:normal

windy:false

它属于哪类气候呢?要解决这个问题, 需要用某个原则来判定, 这个原则来自于大量的实际例子, 从例子中总结出原则, 有了原则就可以判定任何一天的天气属于哪类气候了。

每个实体在世界中属于不同的类别, 为简单起见, 假定仅两个类别, 跟别为P、N。在这两种类别的归纳任务中, P类和N类的实体分别称为概念的正例和反例。将一些已知的正例和反例放在一起便得到了训练集。

由ID3算法的出一棵正确分类训练集中每个实体的决策树, 如图2所示:

决策树叶子为类名, 即P或N。其他结点由实体的特征组成, 每个特征的不同取值对应一分枝。若要对一实体分类, 从树根开始进行测试, 按特征的取值分枝向下进入新结点, 对新结点进行测试, 过程一直进行到叶结点, 实体被判为属于该叶结点所标记的类别。现用图2判本节开始处的例子, 得该实体的类别为P类。ID3就是要训练构成像图2这样的决策树。

实际上, 能正确分类训练集的决策树不止一棵。Quinlan的ID3算法能得出结点最少的决策是树。

3.2 ID3算法描述

(1) 主算法

(1) 从训练集中随机选择一个既含正例又含反例的子集 (称为“窗口”) ; (2) 用建树算法对当前窗口形成一棵决策树; (3) 对训练集 (窗口除外) 中的例子用决策树进行类别判定, 找出错判的例子; (4) 若存在错判的例子, 把它们插入窗口, 转入b) , 否则结束。

主算法中每迭代循环一次, 生成的决策树将会不同。

(2) 建树算法

(1) 对当前例子集合, 计算各特征的互信息; (2) 选择互信息最大的特征Ak; (3) 把在Ak处取值相同的例子归于同一子集, Ak取几个值就得几个子集; (4) 对既含正例又含反例的子集, 递归调用建树算法; (5) 若子集仅含正例或反例, 对应分枝标上P或N, 返回调用处。

(3) 实例计算

对于气候分类问题进行具体计算, 有以下五步。

(1) 信息熵的计算

对9个正例和5个反例, 有:

(2) 条件熵计算

A=outlook, 取值v1=sunny, v2=overcast, v3=rain。

在A1处取值sunny的例子5个, 取值overcast的例子4个, 取值rain的例子5个, 故:

而取sunny的5个例子中2个正例, 3个反例, 取overcas的4个例子中4个均为正例, 取rain的例子5个, 其中正例为3个, 反例为2个, 故:

(3) 互信息计算

对A1=outlook处, 有

类似可得:

(4) 构建决策树的树根和分枝

ID3算法将选择互信息最大的特征outlook作为树根, 在14个例子中对outlook的3个取值进行分枝, 3个分枝对应3个子集, 分别是:

其中F2中的例子全属于P类, 因此对应分枝标记为P, 其余两个子集既含有正例又含有反例, 将递归调用建树算法。

(5) 递归建树

分别对F1和F2子集利用ID3算法, 在每个子集中对各个特征 (仍为四个特征) 求互信息。

F1中的outlook全取sunny值, 则H (U) =H (U│V) , 即I (U, V) =0, 在余下3个特征中求出humidity的互信息量最大, 以它为该分枝的根结点, 再向下分枝。humidity取high全为N类, 该分枝标记N;取值normal全为P类, 该分枝标记为P。

在中, 对四个特征求互信息, 得到windy特征互信息最大, 则以它为该分枝根结点, 再向下分枝。它取ture时全为N类, 该分枝标记N;取false时全为P类, 该分枝标记为P。

这样就得到图2所示的决策树。

3.4 对ID3算法的讨论

(1) 优点

ID3在选择重要特征时利用了互信息的概念, 算法的基础理论清晰, 得算法较简单, 是一个具有使用价值的示例学习算法。

(2) 缺点

互信息的计算具有依赖于特征取值的数目较多的特征, 这样不太合理。一种简单的办法是对特征进行分解, 如气候问题中的例子, 特征取值不一样, 可以把它们统统化为二值特征。如outlook取值sunny, overcast, rain, 可以分解为三个特征:outlook_sunny, outlook_overcast, outlook_rain。取值都为“是”或“否”, 对temperature也可做类似的工作。这样就不存在偏向问题了。

用互信息作为特征选择量存在一个假设, 即训练例子集中能够的正、反例的比例应与实际问题领域里正、反例比例相同。一般情况不能保证相同, 这样计算训练集的互信息就有偏差。

ID3在建树时, 每个结点仅含一个特征, 是一种单变元的是算法, 特征间的相关性强调不够。虽然它将多个特征用一棵树连在一起, 但联系还是松散的。

ID3对噪声较为敏感。关于什么是噪声, Quinlan的定义是训练例子中的错误就是噪声。

它包括两方面:一是特征值取错;二是类别给错。

当训练集增加时, ID3的决策树会随之变化。在建树过程中, 各特征的互信息会例子的增加而改变, 从而使决策树也变化。这对于渐进学习 (即训练例子不断增加) 是不方便的。

4 结束语

ID3由于其理论清晰, 方法简单, 学习能力较强, 适于处理大规模学习问题, 得到了广泛使用, 是数据挖掘和机器学习领域的一个极好范例, 也不失为一种知识获取的有用工具。但其也存在一些不足之处。

参考文献

[1]陈文伟, 黄金才.数据仓库与数据挖掘[M].北京:人民邮电出版社.

[2]IAN H.Witten Eibe Frank.数据挖掘——实用机器学习技术[M].北京:机械工业出版社, 2006.

[3]Jiawei Han Micheline Kamber.数据挖掘:概念与技术[M].北京:机械工业出版社, 2007.

[4]Margaret H.Dunbam.数据挖掘教程[M].北京:清华大学出版社, 2010.

[5]J.R.QUINLAN.Induction of Decision Trees.Machine Learning 1:81-106, 1986.

[6]TJEN SIEN LIM and WEI YIN LOH and YU SHAN SHIH.A Com-parison of prediction accuracy, complexity, and training time of thir-ty-three old and new classification algorithms[J].Machine Learn-ing, 40, 203-228, 2000.

决策树ID3算法及其改进 第4篇

ID3算法属于决策树算法当中的一种,它是通过把实例从根结点排列到某个叶子结点来对实例进行分析,叶子结点即为实例所属的分类[1]。决策树上的每一个结点就是对该实例某一个属性的测试,并且该结点的每一个后继分支对应着该属性的一个可能值。分类从根节点开始,对所有的实例通过所选属性进行分割,属性的选择采用最高信息增益法。停止分割的条件是:没有属性可以再对实例进行分割,或者结点上的实例都属于同一目标属性类别。ID3算法主要针对属性选择问题,是决策树学习方法中最为典型的算法,该方法使用信息增益度选择测试属性。

MIND算法可以作为ID3算法的一种改进算法,其算法思想更方便考虑每一个概化数据元组。MIND算法是一种典型的决策树构造方法的构造分类器,是采用数据库中用户定义的函数UDF发现分类规则的算法,也就是在决策树的每一层,为每个属性建立一张维度表,用来存放各个属性的取值属于哪个类别及结点编号,其优点是通过采用UDF实现决策树的构造过程使得分类算法易于与数据库系统集成。

1 数据挖掘

数据挖掘这个概念于1989年提出[2],指从大量模糊的、有噪声的、不完全的、随机的数据中挖掘出有价值的信息。随着信息技术的发展,大数据技术广泛应用,数据挖掘发挥着越来越重要的作用。在数据挖掘中人们对“啤酒与尿布”的经典案例津津乐道:在美国超市,研究人员发现啤酒和尿布的销量总成某种特殊的关联关系,原来当父亲来到超市给孩子买尿布时,总会捎带啤酒。根据这个发现,超市工作人员特意将啤酒和尿布这两个看似毫不相干的商品摆放在一起,于是这两种商品的销量增大,为超市带来可观收益。这个小小例子足以说明数据挖掘的重要性。

数据挖掘遵循一定步骤:首先要确定业务对象,然后是数据准备工作,在数据准备工作中有数据选择、数据预处理、数据转换、数据挖掘、结果分析和知识同化这些步骤,如图1所示。

2 决策树ID3算法基本原理

2.1 信息增益与信息熵概念

信息增益和信息熵是ID3算法中最重要的两个概念,简单来说,在ID3算法中,信息增益最大的节点属性作为划分标准,信息熵是当获取信息时,将不确定的内容转为确定内容,因此信息伴着不确定性,分别有以下数学定义:

信息增益:假设{b1,b2,...,bn}是属性B的n个不相同的值,则可以将集合T划分为n个子集{a1,a2,...,an}。假设选择属性B为决策树的测试属性,那么以上子集与由结点生成的分支相对应,属性B对集合划分的数学期望为:

其中,是子集aj的权值,即它的值可以用属性B的样本除a得到。最终的信息增益为:

其中,Gain值越大,说明选择测试属性对分类提供的信息越多。

信息熵:已知随机样本的集合T中的样本个数为a,有n个互不相同的值为类别属性,即可得到n个类别Mi(i=1,2,…,n)。假设Mi的样本个数为ai,则某一样本分类需要的数学期望为:

在上述公式中,pi为样本集合中Mi的概率值,可以用计算得出,对数底数可以为任何数,不同的取值对应了熵的不同单位,通常取2。

2.2 ID3算法实现

下面给出一个实例。表1是不同年龄、收入、性别的人群对于买车或者不买车的一个训练数据集。

对于给定的行,类标号属性为买车,计数表示年龄、收入、性别在该行上具有给定值的元组数。首先计算决策属性的熵,根据信息增益与信息熵的公式可知,设买车的人数为S1,不买车的人数为S2,P1为样本中买车的概率值,P2为样本中不买车的概率值,总人数为148,可知

条件属性一共有3个,年龄、收入、性别,分别计算这3个条件属性的信息增益,以计算年龄的信息熵与信息增益为例。年龄分青年、中年、老年3个组。青年买的人数为22,所占比例为22/38,不买的人数为16,所占比例为16/38,则青年的信息熵为-0.58log20.58-0.42log20.42=0.9832。同理可得中年的信息熵为0.971,老年的信息熵为0.242。

青年所占整体人数比重为38/148=0.26,中年所占整体人数的比重为60/148=0.41,老年所占整体人数的比重为50/148=0.33。

则年龄的平均期望为:

年龄的信息增益为:

同理可算出收入的信息增益为0.6628,性别的信息增益为0.3858,可知收入的信息增益是最大的,因此选择性别为决策树的根结点,如图2所示。

找到了根结点后,其它叶子结点的寻找过程与根结点的寻找过程一样。

3 决策树ID3算法的改进算法

3.1 ID3算法的不足

虽然ID3算法理解简单,使用方便,适用于处理大规模的学习问题,但是ID3算法并不适应所有的数据挖掘和机器学习问题,ID3算法效率较低。下面归纳出ID3算法的不足之处:

(1)因为ID3算法为一种贪心算法,即在对问题求解时,总是做出目前状况下的最好选择。换句话说,在算法过程中,不从整体最优上加以考虑,算法选择只是某种意义上的局部最优解。因此,ID3算法的决策树搜索是无回溯的,很有可能在得到局部最优解后丢失了全局最优解。

(2)ID3算法只能处理离散属性,对于连续值的属性,必须首先对其进行离散化处理才能投入使用。比如年龄属性就是一个连续值属性,在ID3算法中对这种连续值属性是无法进行计算的,必须先将年龄属性离散化才能进行下一步计算。

(3)ID3的决策树计算中,每个叶子节点都必须要有属性值才能进行计算,但是并不是每个节点都必须拥有属性值,如果样本的某个属性缺少对应的属性值,那么ID3算法计算将无法继续,只能对缺省值进行赋值才能继续计算。

3.2 ID3改进算法实现

由ID3算法可知,生成决策树的关键是找到根结点,ID3算法是计算各个属性的信息熵和信息增益来寻找根结点的。下面介绍ID3算法的一种改进算法———MIND算法,通过计算各个属性的基尼系数来寻找到根结点以及叶子结点。

基尼系数或译坚尼系数,是20世纪初由意大利经济学家基尼根据劳伦斯曲线所定义的判断收入分配公平程度的指标。基尼系数是一个比例数值,在0和1之间,是国际上用来综合考察居民内部收入分配差异状况的一个重要指标。我们可以利用基尼系数的思想来计算属性的分配程度,从而选择决策树的根结点。

MIND算法具体操作:将各个属性按类别分成不同的小树。

因为买/不买为类标号属性,因此令S1(买)=94,S2(不买)=54。

计算年龄属性的基尼系数,已知青年中买的人数为22,不买的人数为16,因此记为青(22,16),中年中买的人数为24,不买的人数为36,因此记为中(24,36),老年中买的人数为48,不买的人数为2,因此记为老(48,2)。

由上式可知,年龄属性的基尼系数为

计算收入属性的基尼系数:已知低收入中买的人数为2,不买的人数为34,因此记为低(2,34);中收入中买的人数为12,不买的人数为20,因此记为中(12,20);高收入中买的人数为80,不买的人数为0,因此记为高(80,0)。计算得:Gini(低)=0.105,Gini(中)=0.469,Gini(高)=0,Gini(收入)=0.127。

计算性别属性的基尼系数:已知男性中买的人数为50,不买的人数为34,因此记为男(50,34);女性中买的人数为44,不买的人数为20,因此记为女(44,20)。计算得:Gini(男)=0.482,Gini(女)=0.43,Gini(性别)=0.46。

由上述计算可知,收入的基尼系数是最小的,因此选择收入作为决策树的根结点,这个结论与ID3算法一样。根结点决策树与图2一致。

4 结语

本文利用一种新的MIND算法对ID3算法进行改进,从而实现寻找到决策树根结点的简便计算方法。新算法引入基尼系数概念,可以适当减少非重要属性的信息量,相应减少ID3算法对取值较多的属性依赖性,使整个运算更加独立,从而改善分类规则和结果。

摘要：介绍了数据挖掘的相关概念,数据挖掘中决策树ID3算法的相关概念以及信息增益和信息熵概念。通过实例介绍了ID3算法的主要内容,指出了ID3算法的不足及改进之处。针对该实例提出ID3算法的一种改进算法——MIND算法,并通过MIND算法重新计算实例内容。最后通过实例分析将改进算法与ID3算法进行对比,证明了改进算法的有效性。

关键词：数据挖掘,决策树,ID3算法,MIND算法

参考文献

[1]谭建豪,章兢,黄耀,等.数据挖掘技术[M].北京:中国水利水电出版社,2009:16-148.

[2]DAVIDSON IAN,TAYI GIRI.Data preparation using data quality matrices for classification mining[J].European Journal of Operational Research,2009,197(2):764-772.

[3]朱付宝,霍晓齐,徐显景.基于粗糙集的ID3决策树算法改进[J].郑州轻工业学院学报:自然科学版,2015,30(1):50-54.

ID3算法的改进和优化 第5篇

决策树过程为：通过分析已有的数据训练集形成一系列规则，并运用规则对未知的数据进行分类预测的决策。

构造决策树的过程为：

(1) 寻找最初的分裂属性。将整个训练集作为产生决策树的集合，训练集每个记录已分类。在决定哪个属性是目前最好的分类属性时，一般的做法是穷尽现有的全部属性，对每个属性分裂的好坏进行量化，计算出最好的一个分裂。

(2) 重复步骤 (1) ，直至每个叶节点内的记录都属于同一类，并增长到一棵完整的树。

ID3[1,2]算法是基于信息熵的决策树分类算法，其核心思想是在决策树各级结点上选择属性，用信息增益作为属性选择标准，使得在对每一非叶结点进行测试时，能获得关于被测试例子最大的类别信息，期望该非叶结点到达各后代叶结点的平均路径最短，使生成的决策树平均深度较小，提高分类速速和准确率。

2、基本概念

(1) 信息熵：不纯度的最佳评估方法是平均信息量，信息熵为

(2) 信息增益：属性的信息增益度是按该属性分割后熵的消减期望值，即

其中，S为样本集；A为样本中的某一属性；|Sv|是属性A=v时样本的个数；Sv是属性A=v时样本对应的训练集；v属于A的某一个值；|S|表示样本集元素的个数。

ID3选择属性A作为新的属性的原则是：在现有的属性中选择一个属性A，使属性A的信益增益最大。

3、E-ID3决策树算法

ID3算法偏向选择属性取值较多的属性，而实际上属性值较多的属性却不总是最优的属性。该文引入“加权熵”的概念，根据A属性的分支子集所占A实例的比重赋予一个权值，然后根据各个分支子集vi的正负例子计算各个vi的熵值，计算加权熵，通过比较加权熵的大小来选择最优的属性。

(3) 加权熵：若A为候选的属性，A有v个属性值，对应的概率分别为p1, p2, …, pv，属性A的v个子结点选择的属性值为{B1, B2, …, Bv}，对应的信息熵为E (B1) , E (B2) , …, E (Bv) ，则

算法选择属性A*的标准是：在现有的属性中选择一个属性A*，使加权熵E′ (A*) 相对于现有的其他属性的加权熵而言是最小的。

E-ID3决策树算法描述如下：

(1) 在现有的属性中选择任意的一个属性Ai，假设Ai有vi个属性值，对应的概率分别为p1, p2, …, pvi，设属性Ai有vi个属性值{B1, B2, …Bvi}，Bs是属性Ai取第s个值时属性值，Ai的vi个属性值根据利用式 (1计算出各自属性值所对应的信息熵为E (B1) , E (B2) , …, E (Bvi) 。

(2) 根据式 (3) ，计算加权熵E′ (Ai) 。

(3) 继续选择属性Ai+1, Ai+2, …，根据步骤 (1) 、步骤 (2) 计算出相对应的E′ (Ai+1) , E′ (Ai+2) , …；然后在现有的全部属性加权熵E′ (Ai) E′ (Ai+1) , E′ (Ai+2) , …中，通过比较计算出最小的加权熵E′ (Ak*) ，使E′ (A*) 最小，将Ak*作为新选的属性结点，同时扩展其属性值的vk个子结点。此外，如果Ak1和Ak2计算出来的加权熵均相等且都是最小值，此时可以从Ak1和Ak2两个属性中选择一个属性作为新选的属性结点。

(4) 利用步骤 (1) 的计算结果，建立结点Ak的其后继子结点为{B1, B2, …, Bvk}。

(5) 对所有的Bi，若为叶结点，则停止扩展此结点，否则以新建立的后继子结点{B1, B2, …, Bvk}作为父结点，对除属性Ak以外现有的全部属性{…, Ak-1, Ak+1, …}，计算其信息熵及加权熵，然后进行比较，选择加权熵最小的属性作为新的属性结点，即递归执行步骤 (1) ～步骤 (5) 。

该算法步骤 (1) ～步骤 (4) 选定A*作为新的属性，与ID3相比，不是直接计算选择后带来的信息增益，而是选择的后继属性计算属性的熵值。也就是说，该算法改进了选择新属性的启发式函数，达到了更好的分类效果。

4、ID3与E-ID3算法的实验数据的比较

以机器学习书[3]关于决策树算法打高尔夫球为例，对ID3和E-ID3做一个定性和定量的比较。如表1所示，属性天气 (outlook的属性值 (overcast阴天、sunny晴天、rain雨天) ，属性气温 (temperature) 的属性值 (hot天热、mild气温适中、cool天凉) ，属性湿度 (humidity) 的属性值 (high湿度高、normal湿度正常) 以及属性风力 (wind) 的属性值 (weak风力小、strong风力大) 作出打高尔夫球 (play tennis) 的决策判断 (yes是、no否) 。

针对同一数据源，ID3算法与E-ID3算法产生的决策树如图1、图2所示。

E-ID3产生的决策树要比ID3产生的决策树简单，不但可以加快决策树的生长，而且可以得到结构比较好的决策树，便于从中挖掘出较好的规则信息。

5、结束语

通过算法的介绍及实验的对比，ID3算法使用了一种对属性进行逐层的搜索和比较的贪婪算法，而E-ID3算法使用一种基于"统计出局部最优"方法，来获得比较好的启发式函数的算法。如果把这种E-ID3运用于C4.5算法中，能进一步简化、精确构建决策树的步骤。

参考文献

[1]Quinlan J R.Induction of Decision Trees[J].Machine Learning, 1986, 1 (1) :81-106.

[2]Quinlan J R.Simplifying Decision Trees[J].International Journal of-Man-machine Studies, 1987, 27 (3) :221-234.

[3]Mitchell T M.机器学习[M].张银奎, 曾华军, 译.北京:机械工业出版社, 2006.

[4]Durkinl J, 蔡竞峰, 蔡自兴.决策树技术及其当前研究方向[J].控制工程, 2005, 12 (1) .

[5]刘小虎, 李生.决策树的优化算法[J].软件学报, 1998, 9 (10) .

[6]毕建东, 杨桂芳.基于熵的决策树分枝合并算法[J].哈尔滨工业大学学报, 1997, 29 (2) .

[7]洪家荣, 丁明峰, 李星原, 等.一种新的决策树归纳学习算法[J].计算机学报, 1995, 18 (6) .

[8]杨善林, 倪志伟.机器学习与智能决策支持系统[M].北京:科学出版社, 2004-05.

决策树算法ID3的应用研究 第6篇

关键词：决策树算法,ID3算法,传球决策

0 引言

Robo Cup即机器人世界杯足球锦标赛, 是机器人足球的一个国际盛会, 涉及到人工智能, 机器视觉, 机器控制, 智能决策等广泛领域。含有包括仿真组在内的多大40多个比赛项目。Robo Cup对于促进人工智能领域的研究, 提高民族的创新精神, 以及对于教学都有很大作用和成效。目前国内大多数高校都积极参与, 极大的提高了大学生的动手和独创的实践能力。

仿真球队的设计是一个非常复杂的问题, 每个球员是一个Agent, 如只考虑22名Agent在场上的位置、速度以及身体朝向等三个因素, 场上的状态就有10198种之多, 再加上球的位置、速度以及过去的状态, 场上的状态数就会更多。对于如此庞大的一个状态空间, 仅仅依靠人的经验进行手工编码来处理Agent的所有行为是不可能的。因此, 很多研究者都尝试应用机器学习的方法来解决这个复杂的问题。

传球是一个非常重要的策略, 也是进攻对方的一个不可缺少的动作。因此传球的成功率的大小很大程度上决定了进攻的强弱, 也决定我方进球数量。如何提高传球成功率, 以及如何决策传球都是极端重要的。本文基于决策树的学习算法ID3, 给出一种判断传球与否的依据。这使得Agent能够根据场上动态的变化决策下个周期的行为。

1 决策树学习

决策树算法是目前分类方法中应用最广泛的归纳推理算法之一, 它是以实例为基础, 从无次序、无规则的样本数据集中推理出决策树表示形式、逼近离散值目标函数的分类规则方法。它采用自顶向下的递归方式, 在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分支, 在决策树的叶结点得到结论, 因此从根结点到叶结点的一条路径就对应着一条规则, 整棵决策树就对应着一组表达式规则。常用的决策树学习算法有以下几类:

1.1 CLS算法

CLS (Concept Learning System) 学习算法是Hunt.E.B等人在1966年提出的, 后来的许多决策树学习算法都可以看作是CLS算法的改进与更新。CLS的主要思想是从一个空的决策树出发通过添加新的判定结点来改善原来的决策树, 直到该决策树能够正确地将训练实例分类为止。它对决策树的构造过程也就是假设特化的过程, 所以CLS可以看作是只带一个操作符的学习算法, 此操作符可以表示为:通过添加一个新的判定结点特化当前假设, CLS算法递归调用这个操作符作用在每个叶结点来构造决策树。

1.2 CART算法

CART (Classification and Regression Trees分类回归树) 是由Leo Breiman、Jerome Friedman、Richard Olshen和Charles Stone于1984年提出的一种数据勘测和预测算法。这种算法选择具有最小基尼指数值的属性作为测试属性, 并采用一种二分递归分割的技术, 将当前样本集分为两个子样本集, 使得生成的决策树的每一个非叶节点都有两个分枝, 最后生成的决策树是结构简洁的二叉树。由于CART算法得到的决策树每个节点有两个分支, 这种树也称为二叉树。

1.3 CHAID

CHA ID (Chi-Square Automatic Interaction Detector, 卡方自动交互检测) 是一种快速多维树型统计算法。CHA ID的目的主要是在每次分割时利用卡方检验 (Chi-Square Test) 来计算节点中类别的属性值, 以属性值大小来决定决策树是否继续生长, 不必作修剪树的动作。CHA ID自动地把数据分成互斥的、无遗漏的组群, 但只适用于类别型资料。

1.4 ID3算法

相比于前几种算法, ID3算法是一种更有影响力的决策树生成算法。ID3 (Iterative Dichotomizer 3) 算法是Quinlan在1986年提出的, 它基于信息熵的理论, 采用从上到下分而治之的贪心算法策略。ID3是一个典型的决策树学习系统, 其核心是在决策树的各级节点上选择属性, 用信息增益作为属性选择标准, 使得在每个非叶节点上进行测试时, 能获得关于被测试例子最大的类别信息。使用该属性将实例集分成子集后, 系统的熵值最小, 期望该非叶节点到达各后代叶节点的平均路径最短, 使生成的决策树平均深度较小, 提高分类速度和准确率。ID3算法的基本算法是贪婪算法, 采用自顶向下的递归方式构造决策树。其原理是对大量的数据进行归纳、概括、提炼出带有普遍性、概括性的描述 (即事物的属性规律) , 并将这些规律以决策树的方式表示出来。

2 ID3算法

由于ID3采用信息的增益作为属性决策的标准, 算法速度快, 适应于大型的数据集应用, 因此本文选择ID3算法对球场上与传球有关的数据属性进行归类。ID3算法简介如下:

设E=D1×D2×…×Dn是n维有穷向量空间, 其中Dj是有穷离散符号集, E中的元素e=<v1, v2, …, vn>, 叫做例子, 其中vj∈Dj, j=1, 2, …, n.设PE和N E是E的两个子集, 分别叫作正例集和反例集.假设向量空间E中的正例集PE和反例集N E的大小分别为p和n, ID3基于下列两个假设:

1) 在向量空间E上的一棵正确决策树对任意例子的分类概率同E中正反例的概率一致;

2) 一棵决策树能对一个例子作出正确类别判断所需的信息量为:I (p, n) =p/ (p+n) ln (p/ (p+n) ) +n/ (p+n) ln (n/ (p+n) )

如果以属性A作为树的根, A具有v个值{v1, v2, …, vv}, 它将E分为V个子集{E1, E2, …, Ev}, 假设Ei中含有pi个正例和ni个反例, 那么子集Ei所需的信息期望是I (pi, ni) , 以属性A为根所需的期望信息是:

因此, 以A为根的信息增益是:

gain (A) =I (p, n) -E (A) ;

ID3选择使gain (A) 最大的属性A3作为根节点, 对A3的不同取值对应的E的V个子集E递归上述过程生成A3的子结点B1, B2, …Bn, ID3是一个典型的决策树学习系统, 其核心是在决策树的各级节点上, 用信息增益作为属性选择标准, 使得在每个非叶节点上进行测试时, 能获得关于被测试例子最大的类别信息, 使用该属性将例子集分成子集后, 系统的熵值最小, 期望该非叶节点到达各后代叶节点的平均深度较小, 准确率较高, ID3采用这种自顶向下的策略, 搜索全部空间的一部分, 它确保所做的测试次数较少, 因而分类速度也较快。

ID3是通过自顶向下构造决策树来进行学习的, 在搜索的每一步都使用当前的所有训练样本。由于使用所有样本的统计属性, 大大降低了对个别训练样本错误的敏感性, 因此该算法适合于训练样本中含有错误的学习。

3 ID3在Robo Cup中的应用

Robo Cup仿真比赛是由22名队员组成, 双方各11名, 是典型的多智能体协作问题, 队友及敌人的站位, 速度, 角度, 球的速度, 球员的视觉信息等等都会对球场上的每个决策产生影响。另外, 由于比赛是实时的, 而且仿真环境存在噪声干扰, 所以采集的信息可能是不精确的, 甚至机器的速度都会对比赛产生大的影响。基于以上, ID3算法能有效的消弱不确定的影响, 使比赛的决策趋于稳定。下面主要针对传球策略, 给出影响的属性集。

若要考虑场上所有因素, 则状态空间很大, 是目前的机器所不能支持的。下面根据主要和次要的矛盾, 简化状态空间, 考虑影响传球的主要干扰, 忽略次要方面。当然, 这可能会造成判断不准确, 但是相比较运行时间而言, 在误差允许范围内, 可以提高传球成功决策率, 有实际的应用价值的。

假设传球者为A, 接球者为B, 离B最近的两名对方球员为C, D, 球为E, 下面将属性因素总结如下:

1) A与B的距离为dist AB, C与E的距离为dist CE, D与E的距离为dist DE, A与E的距离为dist AE;

2) A与C的角度为Ang AC, A与B的角度为Ang AB, A与D的角度为Ang AD, A与E的角度为Ang AE;

3) 球速度为Espeed, 传球者速度为Aspeed, B速度为Bspeed, D速度为Dspeed, C速度为Cspeed。

学习目标是:A能传给B为T, 否则F;属性集合大小13;

根据属性集, 采集一定的训练样本, 进行基于ID3的决策树构造;具体的构造方法如下:

1) 把所有属性作为节点放入树的集合中;

2) 如果所有的属性均在T中或者F中则决策树构造结束;否则转3;

3) 选择莫个属性A根据训练样本值V1, V2, …Vn将训练集分成子集T1, T2, …Tn, 计算属性A的信息增益, 遍历所有属性, 比较信息增益取最大值即为根节点;

4) 循环3, 迭代计算子结点等。

为了验证本文带球算法的可行性和有效性, 我们将此方法应用于ROBOCUP仿真平台中球员的传球训练中。从统计数据中可以看出, 随着训练次数的增加, 我方球员的传球成功率逐渐提高, 在趋于700次以后, 我方的平均传球决策成功率趋于稳定。结果表明此方法是收敛并且有效的提高了我方的传球成功率。

4 不足与总结

本文根据ID3算法, 给出了在Robo Cup仿真比赛中训练学习传球策略的思路, 但是由于考虑问题的局限性, 并且算法本身也存在诸如不连续性、优先选取取值较多的属性的倾向等缺陷, 要想将ID3算法运用于传球策略中并达到百分之百的成功率还有很多需要改进的地方。

参考文献

[1]Tom M.Mitchell.机器学习[M].机械工业出版社, 2003, 1.

[2]云健, 张旭, 魏晓呜.Robo Cup中截球、控球/带球、传球/跑位的策略[J].内蒙古科技大学学报, 2009, 28 (2) .

[3]麻春, 韩有韬.决策树学习研究[J].科技咨询导报, 2007.

[4]马瑜, 王有刚.ID3算法应用研究[J].信息技术:2006, 12:84-86.

[5]满桂云, 林家骏.ID3决策树算法的改进研究[J].中国科技信息, 2007, 13:8-9.

[6]陶维马, 吉明.决策树算法分析及应用[J].电脑知识与技术, 2009, 5:3352-3354.

ID3算法在分析学生成绩中的应用 第7篇

关键词：数据挖掘,ID3算法,成绩

1 ID3算法

ID3算法是决策树分类算法之一。该算法选择信息增益最高的属性作为当前结点的测试属性。它使数据分类在结果划分中所需要的信息量最小, 体现了划分的最小随机性。最终生成决策树中, 每一个非叶子结点对应着一个非类别属性, 树枝表示该属性的值。从树根到叶结点之间的路径对应着一条规则。

(1) 计算样本分类所需的期望信息。设X是x个数据样本的集合。假定目标类属性具有m个不同的值, 将X划分为{C1, C2Cm}。设xi是类Ci中的样本数。则期望信息I为:

其中pi是任意样本属于Ci的概率, 并用xi/x估计, 由于信息用二进制编码, 所以对数以2为底。

(2) %计算其他各属性的信息熵。设属性A具有n个值, 属性A将X划分为{x1, x2, , xn}, 将xj中属于类Ci的样本数记为xij, 则根据属性A划分子集的信息熵计算公式为:

(3) %计算属性A的信息增益为:

依据 (1) 、 (2) 、 (3) 公式计算出每个属性的信息增益, 选择信息增益的最大的属性作为X样本集的测试属性, 构造一个结点, 为该属性的每一个值创建一个分支, 继续进行划分, 最终构造出决策树。

2 分析学生成绩的影响因素

2.1 样本采集

《计算机文化基础》是全校学生的必修课, 涉及范围广、数量多。利用ID3算法从众多影响学生成绩的因素中挖掘出对学生成绩影响最大的因素, 寻求导致学生成绩优劣的原因。20名学生的学习情况如见表1所示。

2.2 分析

(1) 计算样本的信息熵。在表1中, 目标属性“是否及格”有“是”和“否”两个取值。所以样本集将划分为两个类:C1为“是”, C2为“否”。根据表中数据可得x1=16, x2=4, 由公式 (1) 得:

(2) 计算其他各属性信息熵。例如:“学前情况”属性有三个值“优” (其中3个及格, 1个未及格) , “中” (其中11个及格, 2个未及格) , 和“差” (其中2个及格, 1个未及格) 由公式 (1) (2) 计算得出:

(3) 计算信息增益, 由公式 (2) 得出:

从上面的计算结果中得出, “上机效果”的信息增益度最大, 所以选择其作为决策树的根结点, 该属性有三个值, 得到三个分支。重复上述步骤, 继续进行分裂, 生成决策树。如图1所示。

2.3 结论

通过ID3算法分析得出, 在影响学生成绩的因素中, 上机效果和课堂效果尤为重要, 学生的基础好坏并不直接影响学生的成绩。在决策树中也反映了一个容易被忽视的问题, 有一定基础的学生不一定最终能取得好的成绩, 关键还在于他的学习态度。因此, 计算机文化基础这门课在教学过程中关键是提高学生的课堂和上机的效果, 同时要帮助学生端正学习态度。这样才能有效地提高学生的成绩, 让他们真正掌握计算机的应用能力。

3 结束语

ID3算法是基于信息熵决策树分类算法, 其核心是确定决策树中各个结点的测试属性, 它在搜索的每一步都使用当前的所有训练样例, 降低了对个别训练样例错误的敏感性, 同时增长树的每一个分支的深度, 使训练样例完美地分类。ID3算法只能处理离散值的属性, 当某个属性有大量取值, 被选作树的根结点时, 形成一颗非常宽的树, 虽然理想地分类训练数据, 但是分类性能可能会相当差。因此, 当某个属性取值较多时, 不适合使用ID3算法生成决策树。

参考文献

[1]JIAWEI HAN, MICHELINE KANMBER.数据挖掘概念与技术[M].范明, 孟小峰, 译.北京:机械工业出版社, 2003.

[2]毛国君, 段立娟.数据挖掘原理与算法[M].北京:清华大学出版社, 2005.

[3]张桂杰.数据挖掘决策树分类算法的研究与应用[J].长春理工大学学报, 2005 (10) .

[4]李苗在.决策树技术在学生考试成绩数据库中的应用[J].教育信息化, 2005 (6) .

ID3数据挖掘算法 第8篇

最近几年, 部分国内的教育专家、学者及高校工作者开始对高校毕业生就业进行分析和研究, 应用数据挖掘、统计分析等相关理论对大学生就业进行分析和研究, 提出了相应的预测就业及促进就业、提高就业质量方面的应用。例如: 基于信息增益比的决策树应用于毕业生就业预测分析的方法[1]中提出了针对目前大学毕业生就业预测中存在的不可靠性因素, 提出一种基于信息增益比的决策树算法, 构造出基于信息增益比的决策树来准确预测毕业生的就业情况。应用决策树方法对大学生就业信息进行分析挖掘[2]中提出应用决策树方法对大学生就业信息进行了分析挖掘, 并抽取规则知识, 指出专业成绩、外语成绩、实践能力等是影响学生就业层次的主要因素。应用决策树分析影响高校学生就业的因素[3]中利用决策树分类算法对高校学生的就业信息进行分析, 发现影响学生就业的因素等等。

以上这些研究都提供了较好的研究思路和很多有参考价值的资料[4,5,6,7], 经过研读和分析, 充分考虑到高职学生就业情况 ,采用基于决策树分类算法对高职生就业进行分析与预测。

2 基于决策树分类算法的数据分析

高职学生的信息量大而复杂, 而且各属性之间趋向离散,为使更好地把握分析方向, 挖掘到有用的信息, 必须对原始数据进行统计和预处理。原始数据的部分记录如: 高职院校招生入学信息 (表1)、学籍管理 (表2)。

2.1 数据统计

2.2 数据预处理

为了提高分类的有效性、准确性和可伸缩性, 在分类之前, 就对高职生基础数据进行了预处理。为准确评价学生的就业质量, 引入就业专业相关度这一属性。就业专业相关度用于描述招聘企业的岗位和学生所学专业的对口程度对就业的影响程度。专业相关度的计算是通过专业和就业岗位进行比对得到, 由于专业存在相关性, 进行了人工辨别。转换后的值如表3所示。

3 就业预测决策树模型构建

根据训练集的预测属性, 对学生的能否顺利就业进行分类及预测。

(1) 计算分支 节点处每 个属性的 信息增益 , 选择当前样本集中具有最大信息增益值的属性作为测试属性, 各属性取值如表4所示。

训练集中以毕业生306人作为样本, 其类Y有288个样本, 类N有18个样本, Y为“是”, N为“否”。

利用求解信息增益的公式:

逐一计算样本分类的信息增益, 通过公式可以得到:

下一步, 计算每个属性的信息增益。

首先计算“入学总分”(是否达到最低分数控制线) 属性, 该属性有2个属性值 (0: “达到录取线”, 1: “未达到录取线”), 需对每个属性值所划分的子集计算信息增益:

对于“入学总分 (Rxcj)” >= “录取线”, 类0有131个样本, 用公式

对于“入学总分 (Rxcj)” < “录取线”, 类1有175个样本, 用公式

使用公式, 可计算出按“入学总分” (Rxcj) 划分给定的样本所需的期望信息为:

其他测试属性信息增益计算结果如下:

1) Gain (Zhsz) =0.721

2) Gain (Gklb) =0.468

3) Gain (Ywj) =0.472

4) Gain (Xsdy) =0.078

由于“Zhsz”属性具有最高信息增益, 故成为决策的测试属性。创建一个节点, 用“Zhsz”标记, 引出一个分支, 样本以此划分, 其他分支节点的选择也按此方法。

(2) 生成就业 预测决策树 模型

根据对就业预测各测试属性信息增益的计算, 生成的就业预测决策树模型如图1所示, 内部节点用矩形表示, 叶子节点用椭圆表示。其中,“就业有效率”描述“学生就业预测有效程度”的概念, 其预测分类属性分为两类: Y: 顺利就业; N: 待业。

至此, 应用ID3算法生成了“高职学生就业预测”的决策树模型, 可以通过“就业预测”的决策树来判断学生能否顺利就业, 并进行就业情况的预测。

4 实验分析

本次实验训练集中, 共有306个样本, 其就业预测属性:正例 (顺利就业、Y) 有288个样本, 反例 (待业、N) 有18个样本。就业单位类型预测属性288个样本分3类: 类A (国企事业单位) 有61个样本, 类B (个体私营公司) 有173个样本, 类C (创业或自由职业) 有54个样本。

经过验证, TP样本174例, FP样本39例, FN样本16例。由此 可知 , 精确度 =TP /(TP+FP) =0.8169, 召回率 =TP/(TP+FN) =0.9157。计算Measure值 : F-Measure=2RP /(R+P) =2*0.8169/(0.8169+0.9157) =0.9429, 这表明模 型分类的 质量较好。还进行了就业预测分类信息处理的性能趋势分析, 如图2所示。