ID3分类算法（精选8篇）
ID3分类算法 第1篇
关键词：分类,决策树,信息论,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.
音频分类总结(算法综述) 第2篇
刚开始对音频分割还有特征提取有些自己的想法，感觉应该能够分清楚，但是当开始查阅文献的时候，发现对他们两个的概念越来越模糊。很多时候他们是重叠的。后来我在一篇文献里找到这句话。觉得应该是这个道理：
音频数据的分类是一个模式识别的问题，它包括两个基本方面：特征选择和分类。
音频分割是在音频分类的基础上从音频流中提取出不同的音频类别，也就是说在时间轴上对音频流按类别进行划分。分类是分割的前提和基础。对音频流的准确分割是最终的目的。
于是我找了一下比较典型的分类算法
比较典型的音频分类算法包括最小距离方法、支持向量机、神经网络、决策树方法和隐马尔可夫模型方法等。
1．最小距离法。(典型的音频分类算法)最小距离分类法的优点是概念直观，方法简单，有利于建立多维空间分类方法的几何概念。在音频分类中应用的最小距离分类法有k近邻(k—Nearest Neighbor，简称K—NN)方法和最近特征线方法(Nearest Feature，简称NFL))等。
k近邻方法的思想是根据未知样本X最近邻的k个样本点的类别来确定X的类别。为此，需要计算X与所有样本x。的距离d(x，x。)，并且从中选出最小的k个样本作为近邻样本集合KNN，计算其中所有属于类别Wj的距离之和，并且按照以下判别规则进行分类：C(x)argminC{W1,...,Wn}
d(x,xi),其中，C为类别集合由于k近邻方法利用了更多的样本信息确定它的类别，k取大一些有利于减少噪声的影响。但是由于k近邻方法中需要计算所有样本的距离，因此当样本数目非常大的时候，计算量就相当可观。取k=l时，k近邻方法就退化为最近邻方法。
最近特征线方法是从每一类的样本子空间中选取一些原型(Prototype)特征点，这些特征点的两两连线称为特征线(Feature Line)，这些特征线的集合用来表示原先每一类的样本子空间。
设类C的原型特征点集合:,其中Nc为类C的原型特征点数目，则对应的特征线的数目为Sc，而类C的特征线集合
{|XicXjc|1i,jNc，ij} i≠jl构成类C的特征线空间，它是类C的特征子空间。—般所选取的原型特征点的数目比较少，因此特征线的数目也比较少。未知样本X与特征线XicXjc的距离定义为x在XicXjc上的投影距离，如图4所示，而X与类别C的距离为X与类C的特征线空间中的所有特征线的最短距离。
2．神经网络(Neural Network)。
在使用神经网络进行音频分类时，可以令输入层的节点与音频的特征向量相对应，而输出层的节点对应于类别Ci。，如图5所示。在训练时，通过对训练样本集中的样本进行反复学习来调节网络，从而使全局误差函数取得最小值。这样，就可以期望该网络能够对新输入的待分类样本T输出正确的分类Ci。
3．支持向量机(support Vector Machine，简称为SVM)。
支持向量机是Vapnik等人提出的以结构风险最小化原理(Stuctural Risk Minimization Principle)为基础的分类方法。该方法最初来自于对二值分类问题的处理，其机理是在样本空间中寻找—个将训练集中的正例和反例两类样本点分割开来的分类超平面，并取得最大边缘(正样本与负样本到超平面的最小距离)，如图6所示。该方法根据核空间理论将低维的输入空间数据通过某种非线性函数(即核函数)映射到—个高维空间中，并且线性判决只需要在高维空间中进行内积运算，从而解决了线性不可分的分类问题。
根据不同的分类问题，可以选用不同的核函数，常用的核函数有三种：
① 项式核函数:
② 径向基核函数:
③ Sigmoid核函数：
SVM训练算法主要有三类：二次规划算法，分解算法，增量算法。
4．决策树方法
决策树是一种结构简单、搜索效率高的分类器。这类方法以信息论为基础，对大量的实例选择重要的特征建立决策树，如图7所示。
最优决策树的构造是一个NP完全(NPComepleteness)问题，其设计原则可以形式化地表示为
其中T为特定的决策树结构，F和d分别为分枝结,为在数据集合点的特征子集和决策规则，D为所有的训练数据，D上选取特征集合F和决策规则d训练得到的结构为T的决策树的分类错误的条件概率。因此，决策树的构造过程可以分为三个问题：选取合适的结构，为分枝结点选取合适的特征子集和决策规则。常用的决策树构造方法有非回溯的贪心(Greedy)算法和梯度上升算法。
5.隐马尔可夫模型(Hidden Markov Model，简HMM)方法。
隐马尔可夫模型(HMM)的音频分类性能较好，它的分类对象是语音(speech)、音乐(music)以及语音和音乐的混合(speech+music)共3类数据，根据极大似然准则判定它们的类别，最优分类精度可达90.28％。
ID3算法的改进和简化 第3篇
在ID3算法取值偏向问题的改进中，许多学者提出在子集权重因子中加入“用户兴趣度”[1]等方法，这些方法中权重的确定多数是由专家打分法和决策者的先验知识确定，主观因素的影响较大。而通过数据集本身反映出的客观存在的属性重要性是对客观规律的最大体现。基于这样的想法, 结合粗集理论, 在ID3算法中引入属性重要性, 以改进算法取值偏向的问题, 更具客观性。另一方面, 在简化ID3算法计算复杂度方面, 在类别表示属性取值只有两个的基础之上, 推导了属性取值有多个的计算公式, 使得ID3算法更具有扩展性。
1 ID3算法的改进
1.1 基于属性重要性的ID3算法
属性A的重要性IF (A) 表明了把属性A从R中去掉后对分类决策的影响程度，即不能把正确分类样本所占的比例。将属性重要性IF (A) 引入到信息增益计算公式中子集权重因子，得到改进的公式：
因为属性重要性，所以可得：
在文献[3]中给出的商场顾客训练样本集，使用原始的ID3算法和改进的ID3算法分别计算属性信息增益，结果发现使用原始的ID3算法测得属性：age的信息增益最大，而改进的ID3算测得属性：student的信息增益最大。这样解决了大数据掩盖小数据的问题，还降低了趋向于取值较多而不重要的属性，有效地解决了ID3算法趋向于选择取值较多属性的缺点。
2 ID3算法的简化
2.1 降低ID3算法计算复杂度的理论基础
本文利用Maclaurin公式，来简化信息熵，Maclaurin公式如下：
其近似公式为
当f (x) =ln (1+x) 时，
当x的值非常小时，得到如下结论：ln (1+x) ≈x，本文采用这个结论简化ID3算法的计算复杂度。
2.2 ID3算法的简化过程
属性A作为决策分类属性的信息增益如下式所示：
式中I r 1, r2, …, rm对每个属性信息增益的计算来说，都是一个定值，所以把属性A的信息熵E (A) 作为节点选择的标准，信息熵E (A) 值越小，则信息增益Gain (A) 值越大。
把式（2）代入式（1）得：
由于|S|ln2是个常数，则假设E (A) 满足以下方程：
对于相同属性来说，由2.1的结论可知：当x的值非常小时，ln (1+x) ≈x, Inp1j=In (1- (p2j+…+pmj) ) ≈- (p2j+…+pmj)
……
将以上公式代入到E (A) 中，得到以下结论：
则简化后的ID3算法为：
上式中的常数2，也可以简化掉，得到下式：
其中，v为属性A的取值个数；m为类别标识属性取值的个数。
3 实验例证
验证改进和简化的ID3算法准确率和计算速度以及在构造决策树上的叶子节点的数目（表1）。对于经典的“天气表”[4]，通过天气来决定是否适合打高尔夫球，使用ID3算法和IF-ID3算法分别进行验证。得到结果如表所示：
决策树的节点个数代表了树的规模，树高体现了树的深度相对应着决策树的预测速度[5]。
通过表中的数据结果可以看出：改进的算法节点数少了，但是树高降低了。IF-ID3算法在构建决策树的时候，降低了计算复杂度和节点数目，要比原算法优越。
4 结论
本章针对ID3算法分类时偏向于“取值较多的属性”和循环计算对数log2的缺点，分别利用粗集理论中属性重要性的概念和Maclaurin公式进行改进和简化。通过对比叶子数、节点数和树高，证明了IF-ID3算法的优越性。
参考文献
[1]曲开社, 成文丽, 王俊红.ID3算法的一种改进算法.计算机工程与应用, 2003, 25:104-107.
[2]朱颢东.ID3算法的改进和简化.上海交通大学学报, 2010, 44 (7) :883-886.
[3]朱明.数据挖掘第2版.合肥:中国科学技术大学出版社, 2008.
[4]黄爱辉等.决策树ID3算法的改进.计算机工程与科学, 2009, 31 (6) :109-111.
ID3算法的改进和优化 第4篇
决策树过程为：通过分析已有的数据训练集形成一系列规则，并运用规则对未知的数据进行分类预测的决策。
构造决策树的过程为：
(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分类算法 第5篇
ID3算法属于数据挖掘技术, 所谓的数据挖掘 (Data Mining, 简称DM) 技术是一种进行大量数据深度挖掘、剖析的一种技术。它能够在事先收集好的或是已经积累多年的大量的可以是不完整或是模糊的不确定的具有噪声的数据内部, 研究并深度找出人们经常忽略的及隐含的但很可能是非常重要的数据信息的过程。
数据挖掘的方法和技术可以包括公式发现、模糊数学方法、归纳学习法和数据分类等多种方法[1], 而在数据分类技术中最常用和经典的方法就是决策树分类方法, 该方法的早期算法产生在上个世纪的60年代, 之后经过不断的发展到现在已经研究出好多种常用的决策树算法了, 例如典型的决策树ID3算法、分类与回归树CART算法以及将ID3算法进行改进的决策树学习算法C4.5等等, 而在本文中主要研究的是ID3算法及改进后的应用研究。
2 ID3算法的基本思想
在数据挖掘技术中的ID3算法主要是建立用来建立决策树, 并能通过建立的决策树来分析判断隐藏在数据后面的能对信息结果起到决定作用的重要因素, 它是由CLS发展而来的。ID3算法在建立决策树时首先要进行树的根节点和子节点的选取, 主要选取方法是根据计算每个给定属性的信息熵[2]的值按照它们的下降程度进行选取, 此方法在很多实际分类的应用上进行了广泛的应用, 包括对学生成绩的分析中。
ID3算法的核心点主要在如何选择要建立的决策树的所有的分裂节点上。首先要计算出每个给定属性的信息增益值, 在得出的信息增益值中最大的属性先选作分裂节点属性的备选项, 这样除了根节点对其他节点进行测试的时候得到对于训练样本来说类别信息是最大的。然后, 使用刚刚确定的分列属性中的备选项属性进行训练样本集合划分, 将其划分成相应的子集合系统, 这样得到的熵的值是最小的, 最后通过求得每个属性的信息增益进行比较, 找出最大的信息增益属性。
3 ID3算法的优缺点
在整个建立决策树的过程中, ID3算法的特点很突出具备它自己的优缺点下面分别详细的介绍。
3.1 算法优点
在众多的分类算法中, 决策树算法已经深入的被研究并且被广泛的应用到各个领域中。该算法被作为较为通用的分类函数逼近算法应用, 它本身存在很多的优点, 分别为:
3.1.1 生成的规则容易理解
ID3算法是通过树形结构中的每个分支代表一个分类来查看最终的分类结果的, 在分类的时候才用判断的形式进行分类, 所以能形成用IF-Then的形式表示出来的规则。这种“如果就”规则很容易让人们接受, 对现实世界描述的表示形式非常接近自然语言。而在算法的实际应用中, 这种特点是非常重要的。
3.1.2 容易确定属性之间的重要程度
在建树的过程中要根据熵值和信息增益值来确定根节点和每个叶子节点, 通过熵计算的结果对属性进行分类。通过整个分类的决策树形结构图中就会很容易的观察出哪个属性比较重要, 就是容易区分出属性的重要性了。因为, 在建立的决策树中从根节点开始一直到最后的叶子节点都是按照属性的重要性进行选取的, 节点越高越重要如果同一层属性的重要程度是一样的。
3.1.3 计算量少运算速度高
ID3算法采用的是自上而下的方法进行搜索, 在进行空间搜索时确保搜索该部分所用的测试次数是最少的, 分类速度也是最快的。大大的提高了工作效率, 速度也提高了很多。
3.2 算法的缺点
(1) 通过信息熵的办法来选择所有属性中的最优属性, 可能会产生出取值很大但是属性并不一定是最重要的, 例如学生的性别属性。
(2) 建立的决策树的节点之间联系比较松散, 这是由属性特征值决定决策树节点的原因。
(3) ID3不容易去除噪声, 该算法对噪声比较敏感, 有时取错特征值或给错类别。
(4) ID3算法会随着训练集的改变建立的决策树发生改变, 对于一些可变的数据集合建树是不太合适的。
(5) 算法复杂也是缺点中最大的, 计算每个属性的信息增益值的计算量是非常大的, 通过计算的值进行分裂点选取不只耗费了大量的时间、资源而且还很占用机器内存, 重要的选取出的属性未必是最优的。
4 改进ID3算法的研究及应用
本文将粗糙集理论中的决策协调度引入到ID3算法中, 进行选定分裂点过程的改进不仅能够得到简单的决策树, 而且是整个建树过程简化大大降低了原有算法的复杂度。过程是在整个决策系统中随机选取出某些规则, 通过选出规则的前驱和后继条件相同的几率判断它们的相互协调的几率。这样可以看出起到决策作用的那些属性对可以作为条件属性到底有多少依赖程度, 完全可以通过决策协调度表示出来。所以, 可以通过决策协调度度量在构造决策树时选取的属性。
4.1 决策协调度的概念
设定一个系统S= (U, CU D, V, f) 将其用作决策中, 式子中的D代表决策的属性, X⊆C用来表示某一个属性的子集, 用IDX (X) ⊆UU来表示条件属性或者也称作为用于预测的属性[3]。则, X→D的决策协调度可以表示为:
其中, X=IND (X) , 表示IND (X) ⊆UU的基数。而X UD/X表示在决策系统中, 任意取出两条它们的前件和后继都相同的规则计算可能性大小, 通过X UD/X可以反映出数据D对X的依赖程度。因此, CON (X→D) 就表示集合C中任意一子集的协调度, 也可说用X来度量D的优劣性, CON (X→D) 越大, D对X的依赖性越大, X属性集就越能预测D的优良。
4.2 基于决策协调度的决策树生成算法
将上面描述的协调度概念引入到决策树的建立中, 能够快速并准确的找出所有属性中的好与坏。整个过程可以描述为:计算所有样本集中的属性的决策协调度, 如果决策协调度相近的再计算其信息增益值;值大的会被选作决策的分裂点, 如果无需计算信息增益值那么协调度大的会被选作决策分裂点以该分裂节点进行划分后的每个属性中含有的训练元组都是同类的, 并可将其作为叶子节点;利用递归调用直到条件属性为空值结束, 最后生成决策树。
5 结语
综合上面对ID3算法及改进算法的分析, 利用ID3算法进行属性信息增益计算时用的是对数运算计算量非常大。而改进的算法是在决策协调度相近的情况下才计算信息增益值, 所以在计算量上降低计算的复杂度。
摘要：本文对数据挖掘算法中的决策树算法进行了深入的分析和研究, 在研究ID3算法的过程中总结了该算法的优缺点, 同时针对原算法计算量大计算复杂的缺点进行改进, 同时对改进的算法过程进行描述阐述其优于原算法的特点。
关键词：ID3算法,原算法
参考文献
[1]杜聪.数据挖掘技术在科研评价系统中应用研究.济南:山东大学, 2009
[2]牛文颖.改进的ID3决策树分类算法在成绩分析中的应用研究.大连:大连交通大学, 2008.
模糊ID3数据挖掘算法的研究 第6篇
随着信息技术的发展, 数据量以惊人的速度增长, “数据丰富, 知识贫乏”的矛盾日益突出, 各个领域迫切需要有一种能够从存储海量数据的数据集、数据库、数据仓库中寻求有用信息的工具, 数据挖掘技术应运而生。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.
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所示。
