id3算法，阐述ID3算法处理连续型变量必须离散化的原因
来源：整理 编辑：智能门户 2023-08-21 04:49:05
本文目录一览
1，阐述ID3算法处理连续型变量必须离散化的原因
使用所有没有使用的属性并计算与之相关的样本熵值选取其中熵值最小的属性,生成包含该属性的节点D3算法对数据的要求： 1) 所有属性必须为离散量； 2) 所有的训练例的所有属性必须有一个明确的值； 3) 相同的因素必须得到相同的结论且训练例必须唯一。
Iterative Dichotomiser 3 迭代二叉树3代1959年，widrow和hof提出的最小均方(lms )算法对自适应技术的发展起了极
大的作用。由于lms算法简单和易于实现，它至今仍被广泛应用。对lms算法的性能
和改进算法已经做了相当多的研究，并且至今仍是一个重要的研究课题。进一步的研究
工作涉及这种算法在非平稳、相关输入时的性能研究。当输入相关矩阵的特征值分散时，
lms算法的收敛性变差，研究的另一个方面在于如何解决步长大小与失调量之间的矛
盾。
全称 least mean square
3，什么是ID3算法
http://www.rulequest.com/download.html http://www.rulequest.com/See5-demo.zip 这里有些。 Diversity(整体)-diversity(左节点)-diversity(右节点)，值越大，分割就越好。 三种diversity的指标： 1. min(P(c1),P(c2)) 2. 2P(c1)P(c2) 3. [P(c1)logP(c1)]+[P(c2)logP(c2)] 这几个参数有相同的性质：当其中的类是均匀分布的时候，值最大；当有一个类的个数为0的时候，值为0。 选择分割的时候，对每个字段都考虑；对每个字段中的值先排序，然后再一一计算。最后选出最佳的分割。 树的生成： 错误率的衡量：最初生成的树中也是有错误率的！因为有些叶子节点并不是“Pure”的。 树的修剪：是不是当所以的叶子都很纯是，这棵树就能工作的很好呢? 修剪的要点是：应该回溯多少、如何从众多的子树总寻找最佳的。 1) 鉴别生成候选子树 ：使用一个调整的错误率。AE(T)=E(T)+aleaf_count(T)。一步步的生成一些候选子树。 2) 对子树的评估：通过test set找到最佳子树 3) 对最佳子树衅拦溃菏褂胑valuation set。 4) 考虑代价(cost)的问题
4，ID3算法的介绍
ID3算法是一种贪心算法，用来构造决策树。ID3算法起源于概念学习系统（CLS），以信息熵的下降速度为选取测试属性的标准，即在每个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准，然后继续这个过程，直到生成的决策树能完美分类训练样例。http://www.rulequest.com/download.html http://www.rulequest.com/see5-demo.zip 这里有些。 diversity(整体)-diversity(左节点)-diversity(右节点)，值越大，分割就越好。 三种diversity的指标： 1. min(p(c1),p(c2)) 2. 2p(c1)p(c2) 3. [p(c1)logp(c1)]+[p(c2)logp(c2)] 这几个参数有相同的性质：当其中的类是均匀分布的时候，值最大；当有一个类的个数为0的时候，值为0。 选择分割的时候，对每个字段都考虑；对每个字段中的值先排序，然后再一一计算。最后选出最佳的分割。 树的生成： 错误率的衡量：最初生成的树中也是有错误率的！因为有些叶子节点并不是“pure”的。 树的修剪：是不是当所以的叶子都很纯是，这棵树就能工作的很好呢? 修剪的要点是：应该回溯多少、如何从众多的子树总寻找最佳的。 1) 鉴别生成候选子树 ：使用一个调整的错误率。ae(t)=e(t)+aleaf_count(t)。一步步的生成一些候选子树。 2) 对子树的评估：通过test set找到最佳子树 3) 对最佳子树衅拦溃菏褂胑valuation set。 4) 考虑代价(cost)的问题
5，为什么id3树不能处理连续性属性
ID3算法是决策树的一个经典的构造算法，在一段时期内曾是同类研究工作的比较对象，但通过近些年国内外学者的研究，ID3算法也暴露出一些问题，具体如下：(1)信息增益的计算依赖于特征数目较多的特征，而属性取值最多的属性并不一定最优。(2)ID3是非递增算法。(3)ID3是单变量决策树(在分枝节点上只考虑单个属性)，许多复杂概念的表达困难，属性相互关系强调不够，容易导致决策树中子树的重复或有些属性在决策树的某一路径上被检验多次。(4)抗噪性差，训练例子中正例和反例的比例较难控制。于是Quilan改进了ID3，提出了C4.5算法。C4.5算法现在已经成为最经典的决策树构造算法，排名数据挖掘十大经典算法之首，下一篇文章将重点讨论。决策树的经典构造算法——C4.5（WEKA中称J48）由于ID3算法在实际应用中存在一些问题，于是Quilan提出了C4.5算法，严格上说C4.5只能是ID3的一个改进算法。C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；2) 在树构造过程中进行剪枝；3) 能够完成对连续属性的离散化处理；4) 能够对不完整数据进行处理。C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。另外，无论是ID3还是C4.5最好在小数据集上使用，决策树分类一般只试用于小数据。当属性取值很多时最好选择C4.5算法，ID3得出的效果会非常差。
6，vb实现id3算法
给你个例题看
Function ID3(R：一个非类别的属性集合，C：类别属性，S：一个训练集)
Begin
If S为空, 返回一个值为FAILURE的单个节点；
If S是由其值均为相同类别属性值的记录组成，
返回一个带有该值的单个节点；
If R为空,则返回一个单节点，其值为在S记录中找出的频率最高的类别属性值；
将R中属性之间具有最大gain(D，S)值的属性赋值给D；
将属性D的值赋值给{dj |j =1,2,3 …m}；
将分别由对应于D的值为dj的记录组成的S的子集赋给{sj|j=1,2,3 …,m}；
返回一颗树,其根标记为D,树枝标记为d1， d2，…，dm ；
在分别递归构造以下树：ID3(R-{D},C,S 1) , ID3(R-{D},C,S2) …, ID3(R-{D},C,Sm) ；
End ID3；
如图：
属性 天气 气温 湿度 风 适合打高尔夫
1 多云 热 高 无风 不适合
2 晴 热 高 无风 适合
3 多云 热 高 大风 不适合
4 晴 热 高 中风 适合
5 雨 适中 高 无风 不适合
6 多云 热 高 中风 不适合
7 雨 热 正常 无风 适合
8 雨 适中 高 中风 不适合
9 雨 冷 正常 中风 不适合
10 晴 冷 正常 大风 适合
11 雨 热 正常 大风 不适合
12 晴 冷 正常 中风 适合
13 多云 适中 高 中风 不适合
14 多云 冷 正常 无风 适合
15 多云 适中 高 无风 不适合
16 雨 适中 正常 无风 不适合
17 多云 冷 正常 中风 适合
18 雨 适中 正常 中风 不适合
19 多云 适中 正常 中风 适合
20 多云 适中 正常 大风 适合
21 晴 适中 高 大风 适合
22 晴 适中 高 中风 适合
23 晴 热 正常 无风 适合
24 雨 适中 高 大风 不适合
GAIN天气熵=7/24（-7/7LOG2（7/7）-0）+9/24（4/9LOG2（4/9）+5/9LOG2（5/9））+8/24（1/8LOG2（1/8）+7/8LOG2（7/8）=0.5529
同理：GAIN 气温熵=0.9173 湿度熵=0.9184 风熵=1 所以选最小的天气建树最后递归生成树：
天气
晴 多云 雨
适合） 湿度 气温
高 正常
（ 适合） （不适合） 热 冷 适中
（不适合）（不适合）
风
大风 无风
（适合） （ 不适合）
文章TAG：
id3算法 阐述ID3算法处理连续型变量必须离散化的原因
