《数据模型与决策论文数据模型与决策 论文.doc》由会员分享，可在线阅读，更多相关《数据模型与决策论文数据模型与决策 论文.doc（8页珍藏版）》请在三一文库上搜索。
1、 数据模型与决策论文数据模型与决策 论文ID3算法创建的数据模型的存储结构探讨摘要：利用ID3算法创建的模型是一个不规则的多叉树，这棵树可以用来预测某一事物的发展，从而为决策者提供数据支持。为了能够使用计算机根据模型进行决策，需要设计合理的数据结构来存储树中的各个结点，为算法设计提供支持。该文根据训练集的数据样本创建了数据模型，并根据模型的特点和查找要求，探讨了多叉树的存储方法，以保证算法的运行效率。 关键词：ID3算法；信息增益；决策树；数据结构；结点 The ID3 Algorithm Create Storage Structure of the Data Model are Discu
2、ssed YANG Long-ping (Liuzhou Railway Vocational Technical College, Liuzhou 545007, China) Abstract: ID3 algorithm is used to create the model is a more irregular tree, the tree can be used to predict the development of certain things, so as to provide data to support decision-makers. To be able to m
3、ake decisions based on the model using a computer requires a data structure designed to store all nodes in the tree, the algorithm is designed to provide support. Based on the training set of data samples to create a data model, and find the model characteristics and requirements of the multi-tree s
4、torage method, in order to ensure the efficiency of the algorithm. Key words: ID3 algorithm; information gain; decision tree; data structure; node 对于同一个问题，可能会有多个算法可以解决，但是，执行时间短的算法效率高，而算法的效率与存储量的需求有很大的关系。数据在计算机中的存储方式，是影响算法的执行效率重要因素。 1 ID3算法创建模型的基本思路 ID3是基于信息熵的决策树分类算法，算法核心是在决策树中各级结点上选择属性，用信息增益作为属性选择标准
5、1，使得在每一个非叶子结点进行测试时，能够获得关于被测试例子最大的类别信息，利用该属性将例子分成子集后，系统的熵值最小。期望该非叶子结点到达各后代叶结点的平均路径最短，生成的决策树平均深度较小，从而能够提高分类速度和准确率。 ID3算法计算每一个属性的信息增益，并选取具有最高增益的属性作为给定集合的测试属性2。对被选取的测试属性创建一个结点，并以属性标记，对该属性的每个值创建一个分支，依次类推。创建决策树的方法主要由几个公式构成，分别是计算样本分类的期望信息、计算子集的熵、计算子集的期望信息和计算信息增益。 1.1 计算样本分类的期望信息 设S是s个数据样本的集合，假定类标号属性具有n个不同的
6、值，定义n个不同的类Ci（i=1,2,3,n）。设si是类Ci中的样本数，则对一个给定的样本分类所需的期望信息，可以由公式 3计算出来。其中pi是任意样本属于Ci的概率，一般可用si/s来估计；对数函数以2为底，因为信息用二进制编码。 1.2 计算子集的熵 设属性A具有m个不同值a1 ,a2 , am。可以用属性A将S划分为m个子集S1, S2, , Sm。如果A作为测试属性，则这些子集对应于由包含集合S的结点生长出来的分支。假设sij是子集Sj中类Ci的样本数1。则由A划分成子集的熵的计算可以由公式计算获得，其中充当第j个子集的权，并且等于子集中的样本个数除以S中的样本总数1。熵值越小，子集
7、划分的纯度越高。 1.3 计算子集的期望信息 对于给定的子集Sj，期望信息可以根据计算出来，其中是Sj中的样本属于类Ci的概率1。 1.4 计算信息增益 根据期望信息和熵值，可以得到对应的信息增益值。对于在A上分支将获得的信息增益可以由公式Gain(A)=I(s1, s2, , sn)E(A)计算出来4。 Gain(A)是由于获得属性A的值而导致的熵的期望压缩，决策树算法就是计算每个属性的信息增益，将具有最高信息增益的属性选作给定集合S的测试属性，创建一个节点，并以该属性标记，根据属性的每个值来创建树的分枝，并且据此划分样本。 2 ID3算法创建数据模型的结构 根据采集到的数据样本，可以将数据
8、分成训练集和测试集，其中训练集用于创建决策树，测试集用来对创建的模型进行验证，检验模型分类的精度。 现有收集到的数据共1467条，将其中的三分之二作为训练集，三分之一作为测试集，假设训练集的结构如表1所示。 根据计算公式，可以计算出每个子集的期望信息和熵值，利用期望信息和熵值，计算信息增益。计算的结果分别为：Gain(专业) =0.0252，Gain(成绩) =0.0312，Gain(班干否) =0.0035，Gain(英语水平) =0.0967，Gain(计算机水平) =0.1077，Gain(综合能力) =0.2557，Gain(工资待遇) =0.0475，Gain(专业对口否) =0.0
9、395，Gain(主观意愿) =0.0783，Gain(行业发展)=0.0482。 由决策树的创建方法可知，选择信息增益值最大的“综合能力”作为树的根结点，因为“综合能力”的取值有3个，所以树的分枝有3个，经过第一次选择以后，创建的树的初步模型如图1所示。 再次进行计算时的数据，应当是有条件的。比如，选择“综合能力”值为1的分支，则参与该分支计算的数据是所有“综合能力”=1的数据记录的集合。依次类推。经过剪枝以后的决策树结构如图2所示。 3 决策树模型的存储 根据图2所示，这是一棵不规则的树，得到的决策树模型的深度为4，树的度为4，树的叶子总数为9。为了便于利用计算机进行查询，需要对这棵树进行
10、存储。为了能够很好地表示数据的存储结构，对决策树的结点进行编码，结点的名称分别用AM表示，编号分别用112表示，连接父子2个结点之间的权，用父结点名称加上阿拉伯数字构成，改造后的树的如图3所示。 图2 决策树模型 图3 转换后的决策树 多叉树的存储数据结构一般有三种：双亲表示法、孩子表示法、孩子兄弟表示法5。这三种表示方法各有优缺点，为了能够提高查询的效率，可以使用“双亲表示法+孩子表示法”的组合方式。也就是使用一组连续的存储空间存储各个结点名称，再创建二个链表，分别指向结点的双亲和该结点的子树，如果是叶子结点，则结点的子树集为空指针，如果是树的根，则该结点的双亲为空指针。例如，根结点A的编号
11、为1，其双亲结点指针为空，它有3个分支，权重分别为a1、a2、a3，其孩子结点的名称分别为B、C、D，所以，B的数据域为a1，它指向的兄弟结点为C，C的数据域为a2，它指向的兄弟结点为D，D的数据域为a3，它的兄弟结点为空，最后获得的数据存储结构如图3所示。 根据上表可以定义的数据结构： 1) 定义学生记录 struct recorder int i; /属性的数量 int valuei; /第i个属性的值 student; 2) 定义双亲结构 struct TreeNode intparentNode; /双亲结点 charnumber; /数据域 ChildTreeNode *brothe
12、r; /指向子树集的指针 nodesize; 3) 定义子树集 struct ChildTreeNode int brothername;/兄弟结点名称 char number; /数据域 ChildTreeNode *next;/指向下一个兄弟结点的指针 LNode; 4 结束语 ID3算法在数据挖掘技术中应用非常广泛，根据其创建的数学模型，在很多情况下是不规则的树，利用“双亲孩子”的数据结构，其结构清晰，算法的设计比较容易理解。 参考文献： 1 Han Jiawei, Kamber M.数据挖掘概念与技术M.范明,孟小峰,译.北京:机械工业出版社,2001:15-304. 2 张云涛,龚玲.数据挖掘原理与技术M.北京:电子工业出版社,2004:38-44. 3 Inmon W H.数据仓库M.王志海,林友芳,等,译.北京:机械工业出版社,2003:36-75. 4 毛国君.段立娟,等.数据挖掘原理与算法M.北京:清华大学出版社,2005:11-119. 5 严蔚敏,吴伟民.数据结构M.北京:清华大学出版社,1992:134-135.