ID3算法思想以及实现
1. 决策树原理
数据挖掘中的分类主要包括基于决策树的分类、基于规则的分类、基于神经⽹络的分类、基于⽀持向量机的分类、基于朴素贝叶斯的分类等。机器学习中，决策树是⼀个预测模型，他代表的是对象属性与对象值之间的⼀种映射关系。树中每个节点表⽰某个对象，⽽每个分叉路径则代表的某个可能的属性值，⽽每个叶结点则对应从根节点到该叶节点所经历的路径所表⽰的对象的值。决策树仅有单⼀输出，若欲有复数输出，可以建⽴独⽴的决策树以处理不同输出。数据挖掘中决策树是⼀种经常要⽤到的技术，可以⽤于分析数据，同样也可以⽤来作预测。
[1]Hunt算法
Hunt算法是许多决策树算法的基础，包括ID3、C4.5和CART。
使用dom4j解析xml文件[2]ID3算法
ID3算法的核⼼是在决策树各级结点上选择属性时，⽤信息增益[information gain]作为属性的选择标准，以使得在每⼀个⾮叶结点进⾏测试时，能获得关于被测试记录最⼤的类别信息。
[3]C4.5算法
C4.5算法继承了ID3[Iterative Dichotomiser 3]算法的优点，并在以下⼏个⽅⾯对ID3算法进⾏了改进：
⽤信息增益率来选择属性，克服了⽤信息增益选择属性时偏向选择取值多的属性的不⾜。
在树构造过程中进⾏剪枝。
能够完成对连续属性的离散化处理。
能够对不完整数据进⾏处理。
[4]CART算法
CART[Classification And Regression Tree]算法采⽤⼀种⼆分递归分割的技术，将当前的样本集分为两个⼦样本集，使得⽣成的的每个⾮叶⼦节点都有两个分⽀。因此，CART算法⽣成的决策树是结构简洁的⼆叉树。采⽤⼀种⼆分递归分割的技术，将当前的样本集分为两个⼦样本集，使得⽣成的的每个⾮叶⼦节点都有两个分⽀。因此，CART算法⽣成的决策树是结构简洁的⼆叉树。
[5]SLIQ算法
SLIQ[super-vised learning in quest]算法对C4.5决策树分类算法的实现⽅法进⾏了改进，在决策树的构造过程中采⽤了“预排
序”和“⼴度优先策略”两种技术。
[6]SPRINT算法
为了减少驻留于内存的数据量，SPRINT算法[scalable parallelizable induction of decision trees]进⼀步改进了决策树算法的数据结构，去掉了在SLIQ中需要驻留于内存的类别列表，将它的类别列合并到每个属性列表中。这样，在遍历每个属性列表寻当前结点的最优分裂标准时，不必参照其他信息，将对结点的分裂表现在对属性列表的分裂，即将每个属性列表分成两个，分别存放属于各个结点的记录。
总结：除此之外，常见的决策树算法还有CHAID、Quest和C5.0等。ID3、C4.5和CART都采⽤贪⼼[即⾮回溯的]⽅法，其中决策树以⾃顶向下递归的分治⽅式构造。⼤多数决策树归纳算法都沿⽤这种⾃顶向下⽅法，从训练元组集和它们相关联的类标号开始构造决策树。随着树的构建，训练集递归地划分成较⼩的⼦集。
2. 实验数据inal.arff
@relation weather.symbolic
@attribute outlook {sunny, overcast, rainy} @attribute temperature {hot, mild, cool} @attribute humidi
ty {high, normal}
@attribute windy {TRUE, FALSE}
@attribute play {yes, no}
@data
sunny,hot,high,FALSE,no
sunny,hot,high,TRUE,no
overcast,hot,high,FALSE,yes
rainy,mild,high,FALSE,yes
rainy,cool,normal,FALSE,yes
rainy,cool,normal,TRUE,no
overcast,cool,normal,TRUE,yes sunny,mild,high,FALSE,no
sunny,cool,normal,FALSE,yes
rainy,mild,normal,FALSE,yes
sunny,mild,normal,TRUE,yes overcast,mild,high,TRUE,yes overcast,hot,normal,FALSE,yes
rainy,mild,high,TRUE,no
3. Weka实现
[1]Preprocess选项
[2]Classify选项
[3]Classifier output选项
=== Run information ===
Scheme:s.Id3
Relation:    weather.symbolic
Instances:    14
Attributes:  5
outlook
temperature
humidity
windy
play
Test mode:10-fold cross-validation
=== Classifier model (full training set) ===
Id3
outlook = sunny
|  humidity = high: no
|  humidity = normal: yes
outlook = overcast: yes
outlook = rainy
|  windy = TRUE: no
|  windy = FALSE: yes
Time taken to build model: 0.01 seconds
=== Stratified cross-validation ===
=== Summary ===
Correctly Classified Instances          12              85.7143 %
Incorrectly Classified Instances        2              14.2857 %
Kappa statistic                          0.6889
Mean absolute error                      0.1429
Root mean squared error                  0.378
Relative absolute error                30      %
Root relative squared error            76.6097 %
Total Number of Instances              14
=== Detailed Accuracy By Class ===
TP Rate  FP Rate  Precision  Recall  F-Measure  ROC Area  Class                  0.889    0.2        0.889    0.889    0.889      0.844    yes
0.8      0.111      0.8      0.8      0.8        0.844    no
Weighted Avg.    0.857    0.168      0.857    0.857    0.857      0.844
=== Confusion Matrix ===
a b  <-- classified as
8 1 | a = yes
1 4 | b = no
解析：
[1]统计量
Kappa statistic：Kappa统计
Mean absolute error：平均绝对误差
Root mean squared error：均⽅根误差
Relative absolute error：相对绝对误差
Root relative squared error：相对平⽅根误差
[2]相关术语
TP(true positive)：正确的肯定
TN(true negative)：正确的否定
FP(false positive)：错误的肯定
FN(false negative)：错误的否定
Precision：精确率
Recall：反馈率
ROC(receiver operating characteristic)：接受者操作特性
F-Measure(F-Score)：F值
Confusion Matrix：混淆矩阵
4. 信息熵概念
解析：信息熵⽅程，如下所⽰：
Entropy = 系统的凌乱程度，使⽤算法ID3，C4.5和C5.0⽣成树算法使⽤熵，这⼀度量是基于信息学理论中熵的概念。
5. ID3决策树算法伪代码

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。