机器学习算法-决策树C4.5练习

决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。 数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据，同样也可以用来作预测（就像上面的银行官员用他来预测贷款风险）。从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。

　　1986年Quinlan提出了著名的ID3算法。在ID3算法的基础上，1993年Quinlan又提出了C4.5算法。为了适应处理大规模数据集的需要，后来又提出了若干改进的算法，其中SLIQ (super-vised learning in quest)和SPRINT (scalable parallelizableinduction of decision trees)是比较有代表性的两个算法，此处暂且略过。

　　本文实现了C4.5的算法，在ID3的基础上计算信息增益，从而更加准确的反应信息量。其实通俗的说就是构建一棵加权的最短路径Haffman树，让权值最大的节点为父节点。

　　下面简要介绍一下ID3算法：

　　ID3算法的核心是：在决策树各级结点上选择属性时，用信息增益（information gain）作为属性的选择标准，以使得在每一个非叶结点进行测试时，能获得关于被测试记录最大的类别信息。

　　其具体方法是：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。

　　某属性的信息增益按下列方法计算：

　　信息熵是香农提出的，用于描述信息不纯度(不稳定性)，其计算公式是Info(D)。

　　其中：Pi为子集合中不同性(而二元分类即正样例和负样例)的样例的比例；j是属性A中的索引，D是集合样本，Dj是D中属性A上值等于j的样本集合。

这样信息收益可以定义为样本按照某属性划分时造成熵减少的期望，可以区分训练样本中正负样本的能力。信息增益定义为结点与其子结点的信息熵之差，公式为Gain(A)。

　　ID3算法的优点是：算法的理论清晰，方法简单，学习能力较强。其缺点是：只对比较小的数据集有效，且对噪声比较敏感，当训练数据集加大时，决策树可能会随之改变。

　　C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：

　　1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足，公式为GainRatio(A)；

　　2) 在树构造过程中进行剪枝；

　　3) 能够完成对连续属性的离散化处理；

　　4) 能够对不完整数据进行处理。

　　C4.5算法与其它分类算法如统计方法、神经网络等比较起来有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

　　实现的C4.5数据集合如下：

　　它记录了再不同的天气状况下，是否出去觅食的数据。

　　程序引入状态树作为统计和计算属性的数据结构，它记录了每次计算后，各个属性的统计数据，其定义如下：

1 struct attrItem
2 {
3    std::vector<int>  itemNum;  //itemNum[0] = itemLine.size()
4                                //itemNum[1] = decision num
5    set<int>          itemLine;
6 };
7
8 struct attributes
9 {
10    string attriName;
11    vector<double> statResult;
12    map<string, attrItem*> attriItem;
13 };
14
15 vector<attributes*> statTree;

程序输出结果为：

以图形表示为：

小结：

　　1、在设计程序时，对程序逻辑有时会发生混乱，后者在纸上仔细画了些草图才解决这些问题，画一个好图可以有效的帮助你理解程序的流程以及逻辑脉络，是需求分析时最为关键的基本功。

　　2、在编写程序之初，一直在纠结用什么样的数据结构，后来经过几次在编程实现推敲，才确定最佳的数据结构，可见数据结构在程序中的重要性。

　　3、决策树的编写，其实就是理论与实践的相结合，虽然理论上比较简单，但是实践中却会遇到这样那样的问题，而这些问题就是考验一个程序员对最基本的数据结构、算法的理解和熟练程度，所以，勤学勤练基本功依然是关键。