搜索
机器学习期末报告（一）决策树一、决策树简介决策树是一种用来表示人们为了做出某个决策而进行的一系列判断过程的树形图。决策树方法的基本思想是：利用训练集数据自动地构造决策树，然后根据这个决策树对任意实例进行判定。决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。决策树方法最早产生于上世纪60年代，到70年代末。由JRossQuinlan提出了ID3算法，此算法的目的在于减少树的深度。但是忽略了叶子数目的研究。C4.5算法在ID3算法的基础上进行了改进，对于预测变量的缺值处理、剪枝技术、派生规则等方面作了较大改进，既适合于分类问题，又适合于回归问题。决策树算法构造决策树来发现数据中蕴涵的分类规则．如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树构造可以分两步进行。第一步，决策树的生成：由训练样本集生成决策树的过程。一般情况下，训练样本数据集是根据实际需要有历史的、有一定综合程度的，用于数据分析处理的数据集。第二步，决策树的剪技：决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修下的过程，主要是用新的样本数扼集（称为测试数据集）中的数据校验决策树生成过程中产生的初步规则，将那些影响预衡准确性的分枝剪除二、决策树的工作原理决策树一般都是自上而下的来生成的。选择分割的方法有多种，但是目的都是一致的，即对目标类尝试进行最佳的分割。从根节点到叶子节点都有一条路径，这条路径就是一条“规则”。决策树可以是二叉的，也可以是多叉的。对每个节点的衡量：1)通过该节点的记录数；2)如果是叶子节点的话，分类的路径；3)对叶子节点正确分类的比例。有些规则的效果可以比其他的一些规则要好。YYYYNNNNw1Tx≥0w4Tx≥0w3Tx≥0w2Tx≥0二叉决策树框图三、决策树算法决策树的典型算法有ID3，C4.5，CART等。国际权威的学术组织，数据挖掘国际会议ICDM（theIEEEInternationalConferenceonDataMining）在2006年12月评选出了数据挖掘领域的十大经典算法中，C4.5算法排名第一。C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法。C4.5算法产生的分类规则易于理解，准确率较高。不过在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，在实际应用中因而会导致算法的低效。决策树算法的优点如下：（1）分类精度高；（2）生成的模式简单；（3）对噪声数据有很好的健壮性。因而是目前应用最为广泛的归纳推理算法之一，在数据挖掘中受到研究者的广泛关注。1.ID3算法ID3算法是一个众所周之的决策树算法，该算法是澳大利亚悉尼大学的RossQuinlan于1986年提出，也是国际上最早、最有影响力的决策树算法，其他的许多算法如C4.5、CART算法等都是在ID3算法基础上的改进。在ID3算法中，决策节点属性的选择运用了信息论中的熵概念作为启发式函数。在这种属性选择方法中，选择具有最大信息增益（informationgain）的属性作为当前划分节点。通过这种方式选择的节点属性可以保证决策树具有最小的分枝数量，使得到的决策树冗余最小。公式1：设数据划分D为类标记的元组的训练集。假定类标号属性具有M个不同值，定义m个不同的类Ci（I＝1，2，…，m），Ci,D是Ci类的元组的集合。和分别表示D和Ci,D中元组的个数。对D中的元组分类所需的期望信息由下式给出：21()log()miiiInfoDpp公式2：假设属性A具有v个不同的离散属性值，可使用属性A把数据集D划分成v个子集{D1,D2，…Dv}。设子集Dj中全部的记录数在A上具有相同的值aj。基于按A划分对D的元组分类所需要的期望信息由下式给出：1Dj()()vjAjDInfoDDInfo公式3：信息增益定义为原来的信息需求（基于类比例）与新的信息需求（对A划分之后得到的）之间的差，即Gain(A)=Info（D）-InfoA（D）ID3算法大概的流程就是在属性集A中寻找信息增益值最大的属性，作为根节点，按照根节点属性的取值将样本集合分成几个子集，将此属性从属性集中去掉，在每个子集中选择信息增益值最大的属性，作为当前子集的根节点，上层集合的根节点的子节点，如此循环递归，如果得到的子集中所有的样本属于一个类别，则递归停止。ID3算法对数据的要求：○1所有属性必须为离散量；○2所有的训练例的所有属性必须有一个明确的值；○3相同的因素必须得到相同的结论且训练例必须唯一。实例：假如有一个网球爱好者，天气状况（天气、温度、湿度、风力）是决定他是否去打球的重要因素，利用ID3算法构筑决策树。以往部分打球数据库类标记的训练元组统计如表所示：类标号打球有两个取值（即{是，否}），因此有两个不同的类，即m=2，设C1类对应与是，C2类对应于否。C1有9个元组，C2有5个元组。我们根据公式1可以计算D中元组分类所需要的期望信息：229955()loglog0.94014141414InfoD位如果根据天气属性划分，根据公式2则对D的元组进行分类所需要的期望信息为：222225223344453322()*(loglog)*(log)*(loglog)14555514441455550.694InfoD天气位根据公式3这种划分的信息增益是：Gain（天气）=info（D）-info天气（D）=0.940-0.694=0.246位类似地，可以计算：Gain(温度)=0.029Gain(湿度)=0.151Gain(风力)=0.048由于天气在属性中具有最高信息增益，它被选作测试属性。创建一个节点，用天气标记，并根据每个属性值，引出一个分枝。注意，落在分区天气=多云”的样本都属于同一类，根据算法，要在该分支的端点创建一个树叶，并用“是”标记。同理，在“晴朗”和“雨天”这两个分支上，分别对“温度”、“湿度”、“风力”属性计算其信息增益，分别选取下一个测试属性。依算法全部计算后返回的最终决策树如图所示2.C4.5算法由于ID3算法在实际应用中存在一些问题，于是Quilan提出了C4.5算法，严格上说C4.5只能是ID3的一个改进算法。C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：○1用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；○2在树构造过程中进行剪枝；○3能够完成对连续属性的离散化处理；○4能够对不完整数据进行处理。C4.5算法的优点：产生的分类规则易于理解，准确率较高。C4.5算法的缺点：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。分类决策树算法：C4.5算法是机器学习算法中的一种分类决策树算法，其核心算法是ID3算法。分类决策树算法是从大量事例中进行提取分类规则的自上而下的决策树。四、实现在VisualStudio2013中C++语言ID3算法实现决策树：代码：#includeiostream#includelist#includecstring#includestring#includevector#includemap#includesstream#includeiomanip#includecmath#includefstream#includealgorithm#includeset#includequeueusingnamespacestd;classID3{classNode{public:stringvalue;boolisLeaf;mapstring,Node*map;public:Node():value(),isLeaf(false){}};private:vectorstringattribute;//vectorvectorstringattributevalue;vectorvectorstringdata;intdecatt;Node*root;public:ID3(){//从文件中加载数据ifstreamfin(C:\\Users\\Administrator\\Desktop\\playData.txt);stringline,str;getline(fin,line);//readalinefromtheinputfintolineistringstreamistring(line);//bindtoistringtothelinewereadwhile(!istring.eof()){istringstr;//readawordfromlineattribute.push_back(str);}while(!fin.eof()){getline(fin,line);vectorstringvecStr;istringstreamistring(line);while(!istring.eof()){istringstr;vecStr.push_back(str);}data.push_back(vecStr);}fin.close();}voidrun(){setDec(4);vectorintsubSet;for(inti=0;idata.size();i++){subSet.push_back(i);}vectorintcandidateAtt;for(inti=0;iattribute.size();i++){if(i!=decatt){candidateAtt.push_back(i);}}Node*tree=buildDT(subSet,candidateAtt);//输出树结构root=tree;vectorstrings;printTreeDepth(root,s);}voidsetDec(intn){if(n0||n=attribute.size()){cout指定决策树变量错误!endl;exit(0);}decatt=n;}doublegetEntropy(vectorintsubSet)//获得子集信息熵{doubleentropy=0;doublep,n;p=n=0;vectorstringvec;for(inti=0;isubSet.size();i++){if(data[subSet[i]][decatt]==yes)p++;elsen++;}//判断属于同一类，熵为零的情况if(0==p||0==n)return0;doublepR=p/(p+n),nR=n/(p+n);entropy=-pR*(log(pR)/log(2.0))-nR*(log(nR)/log(2.0));returnentropy;}boolisPure(vectorintsubset){stringvalue=data[subset[0]][decatt];for(inti=1;isubset.size();i++){if(data[subset[i]][decatt]!=value){returnfalse;}}returntrue;}doublegain(vectorintsubset,intindex)//返回以index为节点的信息增益{//统计正例个数和范例个数doubleentropy=getEntropy(subset);doublesum=0;//求可能的所有属性值mapstring,vectorintmapSub;for(inti=0;isubset.size();i++){mapSub[data[subset[i]][index]].push_back(subset[i]);}for(