决策树实验
一、实验原理
决策树是一个类似于流程图的树结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输入，而每个树叶结点代表类或类分布。
数的最顶层结点是根结点。
一棵典型的决策树如图1所示。
它表示概念buys_computer，它预测顾客是否可能购买计算机。
内部结点用矩形表示，而树叶结点用椭圆表示。
为了对未知的样本分类，样本的属性值在决策树上测试。
决策树从根到叶结点的一条路径就对应着一条合取规则，因此决策树容易转化成分类规则。
图1
ID3算法：
■决策树中每一个非叶结点对应着一个非类别属性，树枝代表这个属性的值。
一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。
■每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。
■采用信息增益来选择能够最好地将样本分类的属性。
信息增益基于信息论中熵的概念。
ID3总是选择具有最高信息增益（或最大熵压缩）的属性作为当前结点的测试属性。
该属性使得对结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性或“不纯性”。
二、算法伪代码
算法Decision_Tree(data,AttributeName)
输入由离散值属性描述的训练样本集data;
候选属性集合AttributeName。
输出一棵决策树。
（1）创建节点N；
（2）If samples 都在同一类C中then
（3）返回N作为叶节点，以类C标记；
（4）If attribute_list为空then
（5）返回N作为叶节点，以samples 中最普遍的类标记；//多数表决
（6）选择attribute_list 中具有最高信息增益的属性test_attribute;
（7）以test_attribute 标记节点N；
（8）For each test_attribute 的已知值v //划分samples
（9）由节点N分出一个对应test_attribute=v的分支；
（10令S v为samples中test_attribute=v 的样本集合；//一个划分块
（11）If S v为空then
（12）加上一个叶节点，以samples中最普遍的类标记；
（13）Else 加入一个由Decision_Tree(Sv,attribute_list-test_attribute)返回节点值。
三、实验数据预处理
Age:30岁以下标记为“1”；30岁以上50岁以下标记为“2”；50岁以上标记为“3”。
Sex：FEMAL----“1”；MALE----“2”
Region：INNER CITY----“1”；TOWN----“2”；RURAL----“3”；SUBURBAN----“4”Income：5000~2万----“1”；2万~4万----“2”；4万以上----“3”
Married
Children
Car
Mortgage
Pep：以上五个条件，若为“是”标记为“1”，若为“否”标记为“2”。
Age sex region income married children car mortgage pep
1 2 1 1 2 1 1 2 2
1 2 1 1 2 2 2 2 1
2 1 4 1 2 1 2 2 1
2 1 1 1 1 2 2 2 2
1 2 1 1 1 2 2 2 2
1 2 1 1 2 1 2 1 1
2 1 2 1 1 2 1 1 2
2 1 1 1 2 1 1 2 1
2 1
3 1 2 2 1 2 1
2 1 2 2 2 1 2 2 2
2 2 1 2 2 2 2 1 1
2 1 2 2 1 1 2 1 1
2 2 1 2 1 2 2 1 2
1 1 1
2 1 2 2 2 1
3 2 1 2 1 1 1 2 2
1 1 1
2 1 1 1 2 1
1 1 3
2 2 2 1 2 1
3 1 2 2 1 2 2 2 1
3 2 3 3 1 1 1 2 1
3 2 2 3 1 2 1 1 2
3 1 3 3 1 1 2 2 1
3 2 1 3 1 2 1 2 2
3 2 1 3 1 1 1 1 1
3 1 1 3 1 2 1 1 2
3 1 3 3 1 2 2 2 2
3 2
4 3 1 2 2 1 1
3 1 3 3 2 2 1 1 2
四、实验主函数
function main
clc;
DataSet=[1 2 1 1 2 1 1 2 2
1 2 1 1 2 2 2 2 1
2 1 4 1 2 1 2 2 1
2 1 1 1 1 2 2 2 2
1 2 1 1 1 2 2 2 2
1 2 1 1 2 1 2 1 1
2 1 2 1 1 2 1 1 2
2 1 1 1 2 1 1 2 1
2 1
3 1 2 2 1 2 1
2 1 2 2 2 1 2 2 2
2 2 1 2 2 2 2 1 1
2 1 2 2 1 1 2 1 1
2 2 1 2 1 2 2 1 2
1 1 1
2 1 2 2 2 1
3 2 1 2 1 1 1 2 2
1 1 1
2 1 1 1 2 1
1 1 3
2 2 2 1 2 1
3 1 2 2 1 2 2 2 1
3 2 3 3 1 1 1 2 1
3 2 2 3 1 2 1 1 2
3 1 3 3 1 1 2 2 1
3 2 1 3 1 2 1 2 2
3 2 1 3 1 1 1 1 1
3 1 1 3 1 2 1 1 2
3 1 3 3 1 2 2 2 2
3 2
4 3 1 2 2 1 1
3 1 3 3 2 2 1 1 2
];
AttributName=[11 12 13 14 15 16 17 18 19];
[Tree RulesMatrix]=DecisionTree(DataSet,AttributName) End
五、实验结果
The Decision Tree:
(The Root):Attribut
|_____1______Attribut
| |_____1______Attribut
| | |_____1______Attribut
| | | |_____1______leaf 1
| | | |_____2______leaf 2
| | |_____2______leaf 2
| | |_____3______Attribut
| | |_____1______Attribut
| | | |_____1______leaf 1
| | | |_____2______leaf 2
| | | |_____3______leaf 1
| | |_____2______leaf 2
| |_____2______Attribut
| |_____1______Attribut
| | |_____1______leaf 2
| | |_____2______leaf 1
| |_____2______leaf 1
|_____2______Attribut
| |_____1______leaf 2
| |_____2______Attribut
| | |_____1______leaf 1
| | |_____2______leaf 2
| |_____3______leaf 2
|_____3______Attribut
| |_____1______leaf 2
| |_____2______Attribut
| |_____1______leaf 1
| |_____2______Attribut
| |_____1______leaf 1
| |_____2______leaf 2
|_____4______leaf 1
Tree =
Attribut: 3
Child: [1x4 struct]
RulesMatrix =
1 1 1 0 1 0 0 0 1
1 2 1 0 1 0 0 0 2
2 0 1 0 1 0 0 0 2
3 0 1 1 1 1 0 0 1
3 0 1 2 1 1 0 0 2
3 0 1 3 1 1 0 0 1
3 0 1 0 1 2 0 0 2
1 0 1 0
2 0 1 0 2
2 0 1 0 2 0 1 0 1
0 0 1 0 2 0 2 0 1
0 0 2 1 0 0 0 0 2
0 0 2 2 1 0 0 0 1
0 0 2 2 2 0 0 0 2
0 0 2 3 0 0 0 0 2
0 0 3 0 0 0 0 1 2
0 0 3 0 0 0 1 2 1
0 0 3 0 0 1 2 2 1
0 0 3 0 0 2 2 2 2
0 0 4 0 0 0 0 0 1
六、实验小结：
通过本次试验，我学习了决策树分类方法，并了解了其他ID3等其它分类方法，应用Ｍａｔｌａｂ软件，学会导入数据文件，并对数据文件进行预处理。