数据库-决策树

《分布式数据库》课程报告分类算法功能及应用简介1.1分类技术的方法和意义数据挖掘(DataMinig,DM)来源于数据库中的知识发现，它可以说是数据库研究中的一个非常有应用价值的新领域，它融合了数据库、人工智能、机器学习、数理统计学、模糊数学等多个领域的理论和技术。从数据分析的观点来看，数据挖掘分为两类：描述性数据挖掘和预测性数据挖掘。描述性数据挖掘以概要方式描述数据，提供数据所具有的一般性质；预测性数据挖掘分析数据，建立一个或一组模型，产生关于数据的预测，包括分类和回归。分类可用于提取描述重要数据的模型或预测未来的数据趋势。分类技术是数据挖掘的重要分支，它能够对各个行业提供良好的决策支持，对整个社会的发展产生重要而深远的影响。分类的目的是构造一个分类函数或分类模型（分类器），该模型能把数据库中的数据映射到给定类别中的某一个。分类研究在国外发展很快，已有很多的算法和模型。因此，研究数据分类对数据挖掘技术有很大的意义。用于分类挖掘技术的方法有很多，如决策树方法、遗传算法、贝叶斯网络、粗糙集、k-最临近方法、关联规则方法等等。其中，决策树方法以其算法容易被人理解、易转换成IF-THEN分类规则、效率较高等优点被广泛研究与应用。目前决策树方法中比较流行的算法有ID3、C4.5、CART、SLIQ和SPRINT等。这些算法都是对训练数据样本集建立一棵决策树，利用建好的决策树，对数据进行预测。决策树的建立可以看成是分类规则的生成过程，因此可以认为，决策树实现了数据分类规则的可视化，其输出结果也容易理解。1.2分类挖掘的应用价值 目前，分类挖掘在实际应用中有着很重要的应用价值，在很多行业领域都取得了一定的成功。比如，在股票市场上对每只股票的历史数据进行分析，通过相应的技术进行预测，从而做出相对比较准确的判断；彩票的购买也可以利用数据挖掘的分类或预测技术进行分析；在金融领域中将贷款对象分为低贷款风险与高贷款风险两类。通过决策树，可以很容易地确定贷款申请者是属于高风险的还是低风险的。由于决策树方法在分类挖掘技术中有着独特的优势，因此对决策树分类算法的研究有着多层次的研究价值和很高的应用价值。

2ID3分类算法及其设计实现2.1ID3算法简介2.1.1ID3算法基本思想决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则的方法。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。基本算法：1.选择一个属性放置在根节点，为每个可能的属性值产生一个分支。2.将样本划分成多个子集，一个子集对应于一个分支。3.在每个分支上递归地重复这个过程，仅使用真正到达这个分支的样本。4.如果在一个节点上的所有样本拥有相同的类别，即停止该部分树的扩展。ID3算法思想：(1)初始化决策树T为只含一个树根(X,Q)，其中X是全体样本集，Q为全体属性集。(2)if(T中所有叶节点(X’,Q’)都满足X属于同一类或Q’为空)then算法停止；(3)else{任取一个不具有(2)中所述状态的叶节点(X’,Q’)；(4)foreachQ’中的属性Ado计算信息增益gain(A,X’)；(5)选择具有最高信息增益的属性B作为节点(X’,Q’)的测试属性；(6)foreachB的取值bido{从该节点(X’,Q’)伸出分支，代表测试输出B=bi；求得X中B值等于bi的子集Xi，并生成相应的叶节点(Xi’,Q’-{B})；}(7)转(2)；}ID3算法伪代码。寻找根节点寻找根节点将根节点压入栈中将根节点压入栈中更新根节点更新根节点清空候选表清空候选表找一个除测试点的找一个除测试点的属性作为候选属性计算熵值并更新计算熵值并更新包含所有属性包含所有属性否是在候选列表中查找最大信息增益的属性作为根节点是在候选列表中查找最大信息增益的属性作为根节点计算当前增益最大值计算当前增益最大值将节点插入结果表将节点插入结果表StackStack是否为空否结束是结束2.1.2ID3算法的基本概念信息熵熵是无序性（或不确定性）的度量指标，是用来度量一个属性的信息量。假如事件A的全概率划分是（A1,A2,...,An），每部分发生的概率是(p1,p2,...,pn)，那信息熵定义为：通常以2为底数，所以信息熵的单位是bit。补充两个对数去处公式：构造树的基本想法是随着树深度的增加，节点的熵迅速地降低。熵降低的速度越快越好，这样我们有望得到一棵高度最矮的决策树。2.1.3ID3实例详解先看看下面的数据表格：Table1我们统计了14天的气象数据(指标包括outlook，temperature，humidity，windy)，并已知这些天气是否打球(play)。如果给出新一天的气象指标数据：sunny,cool,high,TRUE，判断一下会不会去打球。在没有给定任何天气信息时，根据历史数据，我们只知道新的一天打球的概率是9/14，不打的概率是5/14。此时的熵为：属性有4个：outlook，temperature，humidity，windy。我们首先要决定哪个属性作树的根节点。对每项指标分别统计：在不同的取值下打球和不打球的次数。Table2下面我们计算当已知变量outlook的值时，信息熵为多少。outlook=sunny时，2/5的概率打球，3/5的概率不打球。entropy=0.971outlook=overcast时，entropy=0outlook=rainy时，entropy=0.971而根据历史统计数据，outlook取值为sunny、overcast、rainy的概率分别是5/14、4/14、5/14，所以当已知变量outlook的值时，信息熵为：5/14×0.971+4/14×0+5/14×0.971=0.693这样的话系统熵就从0.940下降到了0.693，信息增溢gain(outlook)为0.940-0.693=0.247同样可以计算出gain(temperature)=0.029，gain(humidity)=0.152，gain(windy)=0.048。gain(outlook)最大（即outlook在第一步使系统的信息熵下降得最快），所以决策树的根节点就取outlook。接下来要确定N1取temperature、humidity还是windy?在已知outlook=sunny的情况，根据历史数据，我们作出类似table2的一张表，分别计算gain(temperature)、gain(humidity)和gain(windy)，选最大者为N1。依此类推，构造决策树。当系统的信息熵降为0时，就没有必要再往下构造决策树了，此时叶子节点都是纯的--这是理想情况。最坏的情况下，决策树的高度为属性（决策变量）的个数，叶子节点不纯（这意味着我们要以一定的概率来作出决策）。用图形可以形象的表示成：2.2ID3算法仿真程序设计图2-2ID3仿真程序设计流程图Fig.2-2ID3simulationprogramdesignflowfigureID3算法程序分为三个存储过程，包括三部分：存储过程1构建决策树，存储过程2计算熵值，存储过程3产生输出结果。（1）存储过程1BuildTree(table_nameVARCHAR,classVARCHAR,res_nameVARCHARDEFAULT'BTRES,min_gainREALDEFAULT0,root_viewVARCHARDEFAULT'BTROOT',delBOOLEANDEFAULTTRUE)包含六个输入参数：table_name为创建的训练集表名，class为你要预测的属性名，res_name是结果集存放的表的表名，min_gain表示的是最小信息增益，root_view是结果集的视图，del为删除中间表。（2）存储过程2表的作用是计算熵值存储过程2Entropy(view_nameINVARCHAR,entOUTREAL,totpopOUTINTEGER)包含三个输入参数，view_name视图标的名称，ent为熵值，totpop是关联度。（3）存储过程3表的作用是产生输入输出结果。存储过程3产生输出结果。Result(numINTEGER,parentVARCHAR,ruleVARCHAR,view_nameVARCHAR)，本程序共有2处result调用分别的作用是：1.输出rule为空的时候时主属性的值。2.输出rule不为空的时候所有的结果。2.3ID3算法仿真程序实验结果1．创建BTCandidate表，并且定义了CNode、CNod