计本1502决策树分类算法

本学院_信息与电_专业_计算机科学与技术班级计本1502 学号专密封学生须将本学院_信息与电_专业_计算机科学与技术班级计本1502 学号专密封学生须将文字写在此 任课教 成题目：（可指定题目，也可说明题目范围。要求：（ 题目、内容、行文、字数等作出判分规定。1、结合自己感的实际应用领域，自拟题目，并使用本学数据挖掘课程中所学习的基本数据分析和处理方法，包括数据预探索性分析数据仓库相似度计算决策树分类最近邻分类朴素分类、逻辑回归、支持向量机、神经网络、关联规则、means聚类层次聚类和密度聚类等知识对所解决的实际问题从本理论数学原理算法设计数据描述和实验结果与分析等角度开描述2、要 结构清晰、语言通顺、图文并茂，字数不少于正文首行缩进2个汉字多倍行距设置为1.25，字体要求汉字宋体，英文为TimesNewRoman，大小为小四。 写自己动手设计算法和编写程序如发 来自网上或他人， 处理，本门课程考核总成绩计0分 版和程序文件夹；文件夹 名格式统一为“学号-名-班级 题目”。此外，必须上 的打印稿，并要与电子的内容一致，不规范者将酌情扣分教师评教师签 日决策树分类算ID3C4.5一、对于决策树的介

二、对于分类的介分类任务就是确定对象属于哪个预定义的目标类。其本质就是当给定一个数据集后，要求我们训练出（或建立）ff我们预测（或判断）拥有这样一组特征向量的对象应当属于哪个类别。预测：预测是指对连续数据的分类，比如预测明天8点天气的湿度情况，天气的湿度在随时变化，8比如我们可以根据比较的某个特征值判断，如果值大于0.5就认定为，小于等于0.5就认为是女性，这样就转化为连续处理方式；将天气湿度值分段处理也就转三、决策树的分类及结地实例的某一特征进试根据测试结构将实例分配到其子节（也就是选择适当决策点：是对几种可能方案的选择，即最后选择的最佳方案。如果决策属于多决策，则决的中间可以有多个决策点，以决根部的决策点为最终决策方案，四、决的分析与算1、 的学习过

特征选择：从训练数据的特征中选择一个特征作为当前节点的标（征选择的标准不同产生了不同的特征决算法）决生成：根据所选特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决停止声场。剪枝：决容易过拟合，需要剪枝来缩小树的结构和规模（包括预剪枝2、决的构，要构造决就需要根据样本数据集的数据特征对数据集进行划分直到针对所有特征都划分过或者划分的数据子集的所有数据的类别相同然而要构造决，构造决的一般流程使用算法：此步骤可以适用于任何监督学习算法，而使用决可以更好3、递归构建决数据的每个特征都进行了划分，或者每个分支下的所有数据都具有相同的类别。 如果程序已经处理了数据集的所有特征但是数据的类别依然不是唯一的，定该叶子节点的类别即数据中那种类型的数据多叶子结点就采用这个类别标4、决的算决算法是非常常用的分类算法是近离散目标函数的方法学习得到的函数以决的形式表示其基本思路是不断选取产生信息增益最大的属性来划分样例集和，构造决。决算法根据数据的属性采用树状结构建立决策模型，决策AndRegressionTree，CART），ID3(I tiveDichotomiser3)，C4.5，Chi-squaredAutomaticIn ctionDetection(CHAID),DecisionStump，随机森（Random 等。这里主要介绍ID3算法和C4.5算法。来度量数据的内容组织杂乱无章数据的法就是使用信息论度量信息信息论集合信息的度量方式成为熵信息熵或者简称为熵熵在信息科学中可看成是信息程度的度量，熵越大，信息越。况也就越多。其计算是：

其中，S为所有集合，pi表示第i个类别在整个训练元组中出现的概率，可D中元组的类标号所需要的平均信息量。注意：熵是以2进制位的个数来度量编码长log2C。V(A)ASSvSAv5、决的算ID3算ID3算法是由Rossan决的一种算法实现以信息论为基础以信息熵和信息增益为衡量标准从而实现对数据的归纳分类ID3算法的思想是以信息增益度量属性选择选择后信息增益最大的属性进行该算法采自顶向下的贪婪搜索遍历可能的决空间。基本思自顶向下的贪婪搜索遍历可能的决空间构造决这形成了对合格 的贪婪搜索，也就是算法从不回溯重新考虑以前的选择C4.5算C4.5ID3C4.5①用信息增益率来选择属性ID3选择属性用的是的信息增益这里可ID3(entropyC4.5是信息增益率。②在树构造过程中进行剪枝在构造决的时候那些挂着几个元素的节点，overfitting。③④五、具体实例分。

1、决策分将是否yTennis的决策转换成树的形式，如下2、代码分3、主要代

for(j=0;j<{if(kinds[0][j]!=0&&kinds[1][j]!=0&&kinds[2][j]!={p1=p2=以广义表的形式输出voidtreelists(tree{treep;

}}

gain_kind[j]=-p1*log(p1)/log2-gain=gain-(1.0*kinds[0][j]/(positive+gain_kind[j]=if(p)

return}{while(p){

程序输出 如下p=p->nextsibling;if(p)cout<<',';}}}计算信息增double*gain_kind=newdouble[atrr_kinds];intpositive_kind=0,negative_kind=0;对于决，数据的准备往往是简单或者是不必要的，而且能够同时处理个观察的模型，那么根据所产生的决很容易推出相应的逻辑表达式。既可以处理离散值也可以处理连续值，还可以处 度输出的分类相比于神经网络之类的黑盒分类模型，决在逻辑上可以得到很好的2、缺4、性能良好的决的选择标准是什么性能良好的决的选择标准是一个与训练数据较小的决，同时具有很好的泛化能力。言外之意就是说，好的决不仅对训练样本有着很好的分类效六、决优缺1、优点决列出了决策问题的全部可行方案和可能出现的各种自然状态，以及

决算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少