众文网决策树算法毕业论文
1.毕业设计题目是（选用决策树算法的数据挖掘实例分析与设计）
应用遗传算法和决策树算法在数据挖掘中的比较 贾修一 MG0533024 （南京大学 计算机科学与技术系， 江苏省南京市 210093） A Comparision between the Genetic Algorithms and Decision Tree For Data Mining Abstract: This chapter introduces the application with the genetic algorithms and ID3 for the data mining, choose the better algorithm to classifier the given data sets through.the comparision between the two algorithms. And analyzing the results of the experiment as well as reasons. Key words: genetic algrithms; data ming; decision Tree 摘 要： 对训练数据分别采用遗传算法和决策树算法进行数据挖掘，通过比较两者实验得出的结果，来选择更适合本数据集的算法进行分类，并分析实验结果及原因. 关键词： 遗传算法；数据挖掘；决策树算法 1. 数据的描述 数据属性有139351维，每个属性的取值为0或1，分类标识只有两类：A和I.数据的维数太高，在数据预处理阶段最好做属性的约简，进行降维的处理. （1）数据维数太高，易造成一定的维数灾难，使得分类挖掘时间过长. （2）数据庞大，肯定有些噪音数据. 2.算法的设计 为了提高最后分类的精确度，特设计了两种方法进行比较，从中选出一种精确度高的方法.第一种是根据数据的特点，每个属性只取值0和1，所以进行属性约简的时候采用遗传算法.遗传算法的优点是可以对大规模的数据进行一定的属性约简. 2.1 遗传算法描述： （1） 遗传算法的步骤是编码，选择，交叉，变异.通过模仿自然界中的遗传进化原理，来对数据进行处理.而遗传算法的好坏取决于适应度函数的选择，进化的次数，和交叉变异的合理性和概率性等，所以要想设计一个合适的遗传算法必须经过大量的实验. （2） 就训练数据而言，对每一维属性的取值，在类标识一定的条件下，取1和取0的概率之间有个绝对值差α1，α2，该差越大，说明该属性的重要程度越高.同时还要考虑对同一维属性，不论最终类标识是什么，取值都相同的话，则该属性可以被认为是无效的属性，对最后的分类没有影响，所以适应度函数取对每一维属性的α1，α2的熵，熵越大，则属性的重要程度就越低. （3） 编码阶段，就把每一位属性做为一个长度为139351的染色体的一个基因，1表示选择该属性，0表示不选择该属性.随机初始化8个种群，按照适应度函数的定义，从中选取4个适应度函数最小的染色体做为父代. （4） 将选出的父代进行交叉操作，因为是降维操作，所以交叉就是取两个染色体之间隔位进行AND（与）操作，变异就是按照一定的概率，在139351维上随机的100位进行非操作，即：0变为1,1变为0.依次又产生4个后代，结合原来的4个父代组成新的8个初始种群.进化50次. 然后利用贝叶斯方法进行分类.得到的是一个弱的学习器h，然后利用AdaBoost方法进行强化学习分类器. 2.2 AdaBoost算法描述： （1） 给定训练集（x1,y1）,(x2,y2)，…，（xm,ym）m个. （2） yi∈{-1,+1}，实例xi∈X的正确标识. （3） for t=1，…，T 2 { 构造{1，…，m}上的分布Dt，找出弱分类器 ht:X->{-1,+1}， 同时在Dt产生很小的错误εt： εt=PrDt[ht(xi)≠yi] } (4)构造 Dt,D1(i)=1/m Dt+1(i)= Dt/Zt*exp（-αt*yi*ht(xi)）//（注：yi和ht(xi)只能取值于{-1,+1}） 其中Zt是归一化因子（使Dt+1为分布） αt=1/2*㏑（（1-εt）/ εt)>0 (5)输出最终分类器：Hfinal(x)=sign（∑αt*ht(x)）. 第二种方法就是直接使用决策树方法（ID3算法）进行分类.求出每一维属性的的信息增益，建立一棵决策树，利用决策树来进行分类. 2.3 决策树算法（ID3） (1)创建节点N; (2)if samples都在同一个类C then { 返回N作为叶结点，以类C标识； } （3）if attribut_list为空 then { 返回N作为叶结点，标记为samples中最普通的类； } （4） 选择attribute_list中具有最高信息增益的属性test_attribute；标记节点N为test_attribute; (5) for each test_attribute中的已知值a 由节点N长出一个条件为test_attribute=a的分枝； （6） 设s是samples中test_attribute=a的样本的集合； （7） if s为空 then 加上一个树叶，标记weisamples中最普通的类； else 加上一个由ID3(s,attribute_list-test_attribute)返回的节点； 3. 实验分析 就第一种方法：通过实验，在进化次数上选取50次，使得维数约简到1500维左右时得到的分类效果最好，但由于种群是随机产生的，所以在未进行boosting强化时正确率在60~85%之间，不是很稳定，但是符合弱分类器的要求，即只要正确率超过50%就行，在进行boosting后，正确率能超过80%，但可能是数据进行约简的不好或进行迭代的次数选取不太合适，正确率却没有ID3的高.就本数据集而言，由于最终标识只有2个，所以比较适合使用遗传算法和Adaboost进行训练.正确率不高主要问题应该在： （1）遗传算法的适应度函数没有选好，不同的编码方式对应不同的适应度函数取法，就本例而言，二进制编码方式应该是可以的，就是在对适应度函数取的时候没有一个合适的数据表示，只好利用了熵的概念，但在实际意义上感觉效果并不是很好.属性约简后正确率不高，这应该是最主要的原因. （2）交叉变异的方式或许有问题，但是不是主要问题，只要适应度函数选好，也就是选择操作正确。
2.决策树的算法
C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：
1） 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；
2） 在树构造过程中进行剪枝；
3） 能够完成对连续属性的离散化处理；
4） 能够对不完整数据进行处理。
C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。
具体算法步骤如下；
1创建节点N
2如果训练集为空，在返回节点N标记为Failure
3如果训练集中的所有记录都属于同一个类别，则以该类别标记节点N
4如果候选属性为空，则返回N作为叶节点，标记为训练集中最普通的类；
5for each 候选属性 attribute_list
6if 候选属性是连续的then
7对该属性进行离散化
8选择候选属性attribute_list中具有最高信息增益率的属性D
9标记节点N为属性D
10for each 属性D的一致值d
11由节点N长出一个条件为D=d的分支
12设s是训练集中D=d的训练样本的集合
13if s为空
14加上一个树叶，标记为训练集中最普通的类
15else加上一个有C4.5(R - {D},C,s)返回的点 背景：
分类与回归树（CART——Classification And Regression Tree）） 是一种非常有趣并且十分有效的非参数分类和回归方法。它通过构建二叉树达到预测目的。
分类与回归树CART 模型最早由Breiman 等人提出，已经在统计领域和数据挖掘技术中普遍使用。它采用与传统统计学完全不同的方式构建预测准则，它是以二叉树的形式给出，易于理解、使用和解释。由CART 模型构建的预测树在很多情况下比常用的统计方法构建的代数学预测准则更加准确，且数据越复杂、变量越多，算法的优越性就越显著。模型的关键是预测准则的构建，准确的。
定义：
分类和回归首先利用已知的多变量数据构建预测准则， 进而根据其它变量值对一个变量进行预测。在分类中， 人们往往先对某一客体进行各种测量， 然后利用一定的分类准则确定该客体归属那一类。例如， 给定某一化石的鉴定特征， 预测该化石属那一科、那一属， 甚至那一种。另外一个例子是， 已知某一地区的地质和物化探信息， 预测该区是否有矿。回归则与分类不同， 它被用来预测客体的某一数值， 而不是客体的归类。例如， 给定某一地区的矿产资源特征， 预测该区的资源量。
3.如何理解什么是决策树算法
具体算法步骤如下；1创建节点N2如果训练集为空，在返回节点N标记为Failure3如果训练集中的所有记录都属于同一个类别，则以该类别标记节点N4如果候选属性为空，则返回N作为叶节点，标记为训练集中最普通的类；5foreach候选属性attribute_list6if候选属性是连续的then7对该属性进行离散化8选择候选属性attribute_list中具有最高信息增益率的属性D9标记节点N为属性D10foreach属性D的一致值d11由节点N长出一个条件为Dd的分支12设s是训练集中Dd的训练样本的集合13ifs为空14加上一个树叶，标记为训练集中最普通的类15else加上一个有C4.5(R-{D},C,s)返回的点决策树CART背景：分类与回归树（））是一种非常有趣并且十分有效的非参数分类和回归方法。
4.决策树的计算方法是什么
应用决策树进行决策的方案是从右向左逐步后退，根据损益期望值分层进行决策。
具体步骤如下： （1）整理、分析资料，把决策要解决的问题整理绘制成表格。 （2）绘制决策树，按从左向右的顺序绘制。
（3）计算出各方案在每种自然状态下的收益或损益值。因为它只是在考虑到各种自然状态可能出现的概率情况下的损益值，这并非是真正的、实际的数值，是期望能得到的数值，故称为期望值，计算时应从决策树最右端的结果点开始。
期望值=EMV=∑（各种自然状态下的概率*损益或收益值） （4）在各个决策点上比较各方案的期望收益值，取其中最大值的最优方案，剪掉其他被舍弃的方案。
5.求算法相关的论文
史丰收计算法
演练实例一
速 算 法 演 练 实 例
Example of Rapid Calculation in Practice
○史丰收速算法易学易用，算法是从高位数算起，记着史教授总结了的26句口诀（这些口诀不需死背，而是合乎科学规律，相互连系），用来表示一位数乘多位数的进位规律，掌握了这些口诀和一些具体法则，就能快速进行加、减、乘、除、乘方、开方、分数、函数、对数…等运算。
□本文针对乘法举例说明
○速算法和传统乘法一样，均需逐位地处理乘数的每位数字，我们把被乘数中正在处理的那个数位称为「本位」，而从本位右侧第一位到最末位所表示的数称「后位数」。本位被乘以后，只取乘积的个位数，此即「本个」，而本位的后位数与乘数相乘后要进位的数就是「后进」。
○乘积的每位数是由「本个加后进」和的个位数即--
□本位积=（本个十后进）之和的个位数
○那么我们演算时要由左而右地逐位求本个与后进，然后相加再取其个位数。现在，就以右例具体说明演算时的思维活动。
（例题） 被乘数首位前补0，列出算式：
0847536*2=1695072
乘数为2的进位规律是「2满5进1」
0*2本个0，后位8，后进1，得1
8*2本个6，后位4，不进，得6
4*2本个8，后位7，满5进1,
8十1得9
7*2本个4，后位5，满5进1,
4十1得5
5*2本个0，后位3不进，得0
3*2本个6，后位6，满5进1,
6十1得7
6*2本个2，无后位，得2
在此我们只举最简单的例子供读者参考，至于乘3、4……至乘9也均有一定的进位规律，限于篇幅，在此未能一一罗列。
「史丰收速算法」即以这些进位规律为基础，逐步发展而成，只要运用熟练，举凡加减乘除四则多位数运算，均可达到快速准确的目的。
6.如何运用决策树进行决策分析
决策树分析法是通过决策树图形展示临床重要结局，明确思路，比较各种备选方案预期结果进行决策的方法。
决策树分析法通常有6个步骤。 第一步：明确决策问题，确定备选方案。
对要解决的问题应该有清楚的界定，应该列出所有可能的备选方案。 第二步：绘出决策树图形。
决策树用3种不同的符号分别表示决策结、机会结、结局结。决策结用图形符号如方框表示，放在决策树的左端，每个备选方案用从该结引出的]个臂（线条）表示；实施每一个备选方案时都司能发生一系列受机遇控制的机会事件，用图形符号圆圈表示，称为机会结，每一个机会结司以有多个直接结局，例如某种治疗方案有3个结局（治愈、改善、药物毒性致死），则机会结有3个臂。
最终结局用图形符号如小三角形表示，称为结局结，总是放在决策树最右端。从左至右机会结的顺序应该依照事件的时间先后关系而定。
但不管机会结有多少个结局，从每个机会结引出的结局必须是互相排斥的状态，不能互相包容或交叉。 第三步：明确各种结局可能出现的概率。
可以从文献中类似的病人去查找相关的概率，也可以从临床经验进行推测。所有这些概率都要在决策树上标示出来。
在为每一个机会结发出的直接结局臂标记发生概率时，必须注意各概率相加之和必须为1。0。
第四步：对最终结局用适宜的效用值赋值。 效用值是病人对健康状态偏好程度的测量，通常应用0-1的数字表示，一般最好的健康状态为1，死亡为0。
有时可以用寿命年、质量调整寿命年表示。 第五步：计算每一种备远方案的期望值。
计算期望值的方法是从"树尖"开始向"树根"的方向进行计算，将每一个机会结所有的结局效用值与其发生概率分别相乘，其总和为该机会结的期望效用值。 在每一个决策臂中，各机会结的期望效用值分别与其发生概率相乘，其总和为该决策方案的期望效用值，选择期望值最高的备选方案为决策方案。
第六步：应用敏感性试验对决策分析的结论进行测试。敏感分析的目的是测试决策分析结论的真实性。
敏感分析要回答的问题是当概率及结局效用值等在一个合理的范围内变动时，决策分析的结论会不会改变。
7.写一篇《论算法设计中的分治与增量》的学术论文1500字1500字 爱问
一、动态规划的基本思想 在比较基本的算法设计思想里，动态规划是比较难于理解，难于抽象的一种，但是却又十分重要。
动态规划的实质是分治思想和解决冗余，因此它与分治法和贪心法类似，它们都是将问题的实例分解为更小的、相似的子问题，但是动态规划又有自己的特点。 贪心法的当前选择可能要依赖于已经作出的选择，但不依赖于还未做出的选择和子问题，因此它的特征是由顶向下，一步一步地做出贪心选择，但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解。
相比而言，动态规划则可以处理不具有贪心实质的问题。 在用分治法解决问题时，由于子问题的数目往往是问题规模的指数函数，因此对时间的消耗太大。
动态规划的思想在于，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。 由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。
比较感性的说，其实动态规划的思想是对贪心算法和分治法的一种折衷，它所解决的问题往往不具有可爱的贪心实质，但是各个子问题又不是完全零散的，这时候我们用一定的空间来换取时间，就可以提高解题的效率。 二、动态规划的基本步骤 动态规划算法通常用于求解具有某种最优性质的问题。
在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。
设计一个动态规划算法，通常可以按以下几个步骤进行： （1）找出最优解的性质，并刻画其结构特征。 （2）递归地定义最优值。
（3）以自底向上的方式计算出最优值。 （4）根据计算最优值时得到的信息，构造一个最优解。
其中（1）——（3）步是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（4）可以省去。
若需要求出问题的一个最优解，则必须执行步骤（4）。 此时，在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速构造出一个最优解。
三、典型的动态规划举例——矩阵连乘问题 作为经典的动态规划算法举例，矩阵连乘问题很好地展现了动态规划的特点和实用价值。 给定n个矩阵{A1,A2,。
,An}，其中Ai与Ai 1是可乘的，i=1,2,。
n-1。
现在要计算这n个矩阵的连乘积。由于矩阵的乘法满足结合律，所以通过加括号可以使得计算矩阵的连乘积有许多不同的计算次序。
然而采用不同的加扩号方式，所需要的总计算量是不一样的。 若A是一个p*q矩阵，B是一个q*r矩阵，则其乘积C=AB是一个p*r矩阵。
如果用标准算法计算C，总共需要pqr次数乘。 现在来看一个例子。
A1,A2,A3分别是10*100,100*5和5*50的矩阵。 如果按照（（A1A2）A3）来计算，则计算所需的总数乘次数是10*100*5 10*5*50=7500。
如果按照（A1(A2A3)）来计算，则需要的数乘次数是100*5*50 10*100*50=75000，整整是前者的10倍。由此可见，在计算矩阵连乘积时，不同的加括号方式所导致的不同的计算对计算量有很大的影响。
如何确定计算矩阵连乘积A1A2,。
,An的一个计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少便成为一个问题。
对于这个问题，穷举法虽然易于入手，但是经过计算，它所需要的计算次数是n的指数函数，因此在效率上显得过于低下。 现在我们按照动态规划的基本步骤来分析解决这个问题，并比较它与穷举法在时间消耗上的差异。
（1）分析最优解的结构。 现在，将矩阵连乘积AiAi 1。
Aj简记为A[i:j]。对于A[1:n]的一个最优次序，设这个计算次序在矩阵Ak和Ak 1之间将矩阵链断开（1 *max） *max= A; if(A } } 上面这个算法需比较2(n-1)次。
能否找到更好的算法呢？我们用分治策略来讨论。 把n个元素分成两组： A1={A[1],。
,A[int(n/2)]}和A2={A[INT(N/2) 1],。
,A[N]} 分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。
如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。
例如有下面一组元素：-13,13,9,-5,7,23,0,15。用分治策略比较的过程如下： 图中每个方框中，左边是最小值，右边是最大值。
从图中看出，用这种方法一共比较了10次，比直接比较法的14次减少4次，即约减少了1/3。算法如下： void maxmin2(int A[],int i,int j,int *max,int *min) /*A存放输入的数据，i,j存放数据的范围，初值为0,n-1,*max,int *min 存放最大和最小值*/ { int mid,max1,max2,min1,min2; if (j==i) {最大和最小值为同一个数；return;} if (j-1==i) {将两个数直接比较，求得最大会最小值；return;} mid=(i j)/2； 求i~mid之间的最大最小值分别为max1,min1； 求mid 1~j之间的最大最小值分别为max2,min2； 比较max1和max2，大的就是最大值； 比较min1和min2，小的就是最小值； } 利用分治策略求解时，所需时间取决于分解后子问题的个数、子问题的规模大小等因素，而二分法，由于。
转载请注明出处众文网 » 决策树分类算法