id3 使用java实现id3算法建立决策树，建成 后可以测 例， 对用例分类。 Develop 240万源代码下载-
&文件名称: id3& & [
& & & & &&]
&&所属分类:
&&开发工具: Java
&&文件大小: 13 KB
&&上传时间:
&&下载次数: 127
&&提 供 者:
&详细说明：使用java实现id3算法建立决策树，建成决策树后可以测试用例，使用决策树对用例分类。主类是ID3List，花了3天时间写完调试通过的。
ID3算法的实现 包括：建树，测试用例， 选根， 建立叶子节点, 求熵， 求信息期望，求信息增益 等方法以及相应的测试
* 测试：目前全部方法都无异常。makeTree方法有两处逻辑错误待修正 工具类 ListUtil MathUtil ClassUtil StringUtil
* DecisionTree 等工具类 实体类 Person(--&person_id3) VO类 PersonVO
* 针对：一个具体的例子:根据历史数据建立一棵决策树，判定某个具有某些属性的人是否会购买电脑 进步：重构后结构清晰 分工明确 缺陷：打印信息偏少无法反映出计算过程的复杂性。不易得到跟踪消息-ID3 Decision Tree
文件列表(点击判断是否您需要的文件，如果是垃圾请在下面评价投诉):
&&id3\ID3List.java&&...\vo\PersonVO.java&&...\util\ClassUtil.java&&...\....\ListUtil.java&&...\....\MathUtil.java&&...\....\QueryUtil.java&&...\....\StringUtil.java&&...\pojo\DecisionTree.java&&...\....\insert-data.sql&&...\....\Person.hbm.xml&&...\....\Person.java&&...\dao\PersonDAO.java&&...\...\PersonDAOImpl.java&&...\vo&&...\util&&...\pojo&&...\dao&&id3
&[]:很好，推荐下载&[]:纯粹是垃圾&[]:dm.aproiri.dao.HibernateSessionFactory这个文件没有，可以分享分享吗？
&近期下载过的用户:
&&&&&&&&&&&&[]
&相关搜索:
&输入关键字，在本站240万海量源码库中尽情搜索：
&[] - ID3决策树算法的JAVA实现：ID3算法是机器学习中的一种分类方法，本例子用java构建多叉树来实现id3算法。
&[] - ID3算法，对随机生成的15组数据进行最佳分类，得到最佳决策树
&[] - 数据挖掘中的ID3算法源码
决策树的经典算法之一。
&[] - 一个计算信息熵的完整功能类。设计互信息，熵，信息增益，条件熵等等功能。
&[] - 决策树进行分类。ID3算法，通过输入数据，输出决策规则。
&[] - 商业只能中数据挖掘的决策树算法 用于数据分类
&[] - ID3 Decision Tree Algorithm JAVA realize: ID3 machine learning algorithm is a classification method, the example of using java to build a multi-tree a
&[] - 此编码是一个数据挖掘的决策树各种算法。以作为入门提示-this code is a decision tree data mining algorithms. As a portal to suggest
&[] - ID3算法的另一种用java实现的代码，利用向量。
&[] - c++实现的ID3产生决策树的源程序!请放心使用！　　摘要：ID3算法是决策树学习里面很重要的算法之一。ID3算法采用自顶向下贪婪搜索遍历可能的决策树空间[1]54，由于该" />
免费阅读期刊
论文发表、论文指导
周一至周五
9：00&22：00
ID3算法的改进
2013年7期目录
&&&&&&本期共收录文章20篇
　　摘要：ID3算法是决策树学习里面很重要的算法之一。ID3算法采用自顶向下贪婪搜索遍历可能的决策树空间[1]54，由于该算法存在两个大的缺点：一、属性取值偏向；二、抛弃较小数据。针对这两个缺点本文给出了两个改进方法：一、增加属性权值；二：增加信息增益度。通过实验结果表明使用这两种方法的综合应用的结果比没有使用这两种方法的效果更好。 中国论文网 /8/view-4288817.htm　　关键词：决策树 ID3 算法 属性权值 信息增益 　　1 引言 　　决策树学习是应用最广的归纳推理算法之一。决策树的结果是实例属性值的合取的析取式的结果。合取是从每条树根到树叶的属性测试的结果，对所有合取进行析取的结果就是整个决策树的结果。因为在决策树学习中ID3算法很有用，所以很多人都进行了研究和探索。决策树学习起源于概念学习系统，最早是由Quinlan[2]81提出来的， 通过应用分治策略，对一个训练集进行学习最后生成一棵决策树。当训练数据集变大的时候ID3算法由于之前的决策树已经确定，所以再次加入其它样本的时候就要重新进行树的构建，就会花费较多的时间，这会使算法的效率变得很低。由于ID3算法以最高信息增益作为选择属性的标准[1]54，这就会导致最后的结果偏向于选取属性取值更多的那个属性。针对这两个问题本文采取了从两个方面进行改进：一、属性权值；二、信息增益度。从这两个方面进行改进的好处就是可以提高决策树的准确性和决策树的实时性，减少了决策树依赖于取值较多的属性，通过实验验证这种改进的方法比以前的方法更有效率。 　　2 ID3 算法的原理 　　ID3 是基于信息熵的决策树分类算法，其核心思想是在决策树中各层分枝节点上选择属性， 用信息增益作为属性选择标准，使得在每一非叶子节点进行测试时，能获得关于被测试例子最大的类别信息，使用该属性将样本集划分成子集后，系统的信息熵值最小[3]3073。 　　2.1 ID3算法思想 　　现假设一个训练集仅有两种分类：正例和反例，并且所有的属性都是离散型数据[4]63。在生成决策树的过程中，通过计算每个结点的信息增益来确定它们的位置，根据信息增益的高低来对每个属性进行排列，树的每个结点的确定都是从信息增益的从高到低的顺序来进行排列。 　　2.2 ID3算法的理论基础如下 　　1948 年，香农提出了信息论[5]57。其中对信息量和熵的定义[5]57为： 　　（1） 　　（2） 　　2.2.1 数据集S划分前的熵 　　设数据集S有 ， C共有n + l个属性。其中分类属性C有m个不同的离散属性值 。即数据集S中的记录要分成m个类别。设数据集S中全部的记录数为s，分类属性值为 的记录数分别为 。那么划分之前，数据集S的总熵为： 　　（2.1） 其中Pi是任意一个记录属于类别的概率，用Si/S估计。 　　2.2.2 数据集S划分后的熵 　　一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低[11]。其中，属性A有v个值，并且把S分割成了v个不同的子集 。设子集Sj中全部的记录数为Sj，其中分类属性值为C1，C2，…Cm的记录数分别为S1j，S2j，…Svj。子集Sij的熵为： 　　（2.2） 　　其中Pij是Sj中任意一个记录属于类别Ci的概率，用Sij/Sj估计。S的总熵是v个子集的熵的加权平均。数据集S划分后的熵为： 　　2.2.3 数据集S划分前与划分后的熵差 　　信息增益：表示系统由于分类获得的信息量。由系统熵的减少值定量描述。数据集S用属性A划分后的信息增益为数据集S划分前后的熵差： 　　（2. 4） 　　在结点划分方面，选择属性应该具有最高信息增益。熵刻画了任意样例集的纯度，就可以使用熵减少量最大的作为划分方案中最好的那张方法，所以就把信息增益最大的属性作为当前结点。 　　3 ID3算法改进 　　3.1属性加权 　　从上面的算法我们可以看出ID3算法存在两个大的缺点：一、属性取值偏向；二、只对较小数据有效。针对以上两个缺点本文进行了下面的改进。通过对2.2.3中的公式（2. 4）中的属性进行加权，以此来增加属性的权值，减小不重要的属性的权值，通过增加权值的方法使得最后生成的决策树的结点的时候数量少的数据元组也会得到重视，而属性值较多但是并不重要的属性就会得不到重视，这样的结果就会使得决策树不会对取值较多的属性存在依赖，从根本上减少由于数据多而属性并不重要但是得到重视，数据少而属性重要的属性得不到重视的情况。经过加权，原式（2. 4）将修改为下式： 　　其中 是属性j的加权后的值，从上面的公式我们可以看出重要性高的属性，他的权值参数的取值就会越大，但是不管他有多大最终都要满足 。 　　3.2信息增益度 　　在公式（3. 1）改进的基础之上，增加信息增益度的概念。将（3. 1）变为下式： 　　其中，N为属性A的取值个数，这样计算之后就原来的信息增益度就会被替换掉。理论上来说，这种方法通过引入分支数N，在ID3算法的取值存在偏向缺陷的基础上得到了克服。 　　4 实例验证 　　下表给出了测试数据样本集，其中属于Y的实例有9个，属于N的实例有6个。 　　此时可以看出湿度的信息增益最大，而风的信息增益最小。所以在构建决策树的时候，湿度就会作为第一个节点，风最为最后一个结点，最后的决策树形如图1所示。 　　图 1改进前决策树 　　现假设各属性的取值的重要程度依次为：温度、风、湿度，那么对他们的权值的赋值为为0. 2、0. 4、0. 4，结合公式（3. 1）与公式（3. 2） ，得到新的决策树如图2所示。 　　图 2改进后决策树 　　通过图1和图2的比较，可以发现图1的决策树分支比图2多了很多，而且结构很稀疏，在进行树的搜索的时候扫描次数也更多，所以图2的决策树的算法相对于图1的算法来说更实用， 用200个样本进行测试发现，没有改进之前的ID3算法的错误率为9.3%，改进后的ID3算法的错误率为5.7%，由此我们可以看出在ID3算法的基础上给通过增加属性权值和改变信息增益这两个方面的改进能使得决策树更加符合实际情况，同时也达到了我们的预期目标。 　　5 结束语 　　通过对ID3算法中所存在的属性取值偏向和抛弃较小数据的缺点进行改进，即在ID3算法的原有的基础上增加属性权值和信息增益度，一定程度上克服了上面的两个缺点，这样在可以加快决策树的生长的同时，还可以使树的结构性更好，这就提高了ID3算法的效率，并且结果表明，改进后的算法比传统算法更好，更加实用。 　　参考文献： 　　[1]张保华.改进的ID3算法[J].中国校外教育，2009（8）：49-54. 　　[2]J.R.QUINLAN.Induction of Decision Trees[J].Kluwer Academic Publishers，）：81-106. 　　[3]王小巍，蒋玉明.决策树ID3算法的分析与改进[J].计算机工程与设计，2011（9）：76. 　　[4]段玉春，朱晓艳，孙玉强.一种改进的ID3算法[J].南阳师范学院学报（社会科学版），2006（9）：63-65. 　　[5]王勇.香农信息定义分析与改进[J].情报杂志，2008（8）：57-60.
转载请注明来源。原文地址：
【xzbu】郑重声明：本网站资源、信息来源于网络，完全免费共享，仅供学习和研究使用，版权和著作权归原作者所有，如有不愿意被转载的情况，请通知我们删除已转载的信息。
xzbu发布此信息目的在于传播更多信息，与本网站立场无关。xzbu不保证该信息（包括但不限于文字、数据及图表）准确性、真实性、完整性等。工具类服务
编辑部专用服务
作者专用服务
决策树ID3算法的一种改进
ID3算法是决策树分类挖掘方法的核心算法，其思想是通过计算训练属性集的信息增益值，选取增益值最大的属性作为分类依据。文中针对ID3算法在大数据量下计算信息增益时运行效率低下，利用数学运算对计算信息增益的公式进行了改进，提出了新的改进算法，同时针对ID3算法在选择属性时偏向于选择较多的属性，引入了加权属性值的概念。通过实验结果分析，新的算法在运行时间效率上有很大的提高。
作者单位：
福州大学至诚学院计算机工程系
年，卷(期)：
机标分类号：
在线出版日期：
本文读者也读过
相关检索词
万方数据知识服务平台--国家科技支撑计划资助项目（编号：2006BAH03B01）(C)北京万方数据股份有限公司
万方数据电子出版社捷配欢迎您!
微信扫一扫关注我们
当前位置：&>>&&>>&&>>&一种决策树ID3算法及其优化的实现
　　决策树（ Decision Tree ）又称为判定树，是运用于分类的一种树结构。其中的每个内部结点（ inrnal node ）代表对某个属性的一次，每条边代表一个测试结果，叶结点（ leaf ）代表某个类（ class ）或者类的分布（ class distribution ），最上面的结点是根结点。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。构造决策树是采用自上而下的递归构造方法。决策树构造的结果是一棵二叉或多叉树，它的输入是一组带有类别标记的训练数据。二叉树的内部结点（非叶结点）一般表示为一个逻辑判断，如形式为 （a = b） 的逻辑判断，其中 a 是属性，b 是该属性的某个属性值；树的边是逻辑判断的分支结果。多叉树（ ID3 ）的内部结点是属性，边是该属性的所有取值，有几个属性值，就有几条边。树的叶结点都是类别标记。
　　1 决策树分类过程
　　决策树的分类过程也就是决策树分类模型（简称决策树）的生成过程，如图1所示。从图中可知决策树分类的建立过程与用决策树分类模型进行预测的过程实际上是一种归纳-演绎过程。其中，由已分类数据得到决策树分类模型的过程称归纳过程，用决策树分类模型对未分类数据进行分类的过程称为演绎过程。需要强调的是：由训练集得到分类模型必须经过测试集测试达到一定要求才能用于预测。
　　信息增益是不确定性的消除，也就是接收端所获得的信息量。
　　2.2 ID3算法多值偏向性分析
　　ID3算法是由Quinlan首先提出的。该算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。在梳理ID3改善，添加了特征选择的启发。ID3搜索通过属性的训练资料中，分离出的属性，在给定的例子最好。如果属性的完全分类的训练集然后ID3停止的，否则它递归的运作就n（n =可能出现的数量在一个属性的值划分子集）去得到他们的"最好"的属性。ID3算法计算每个属性的信息增益，并选取具有最高增益的属性作为给定集合的测试属性。对被选取的测试属性创建一个节点，并以该节点的属性标记，对该属性的每个值创建一个分支据此划分样本。
　　首先，设A是某训练样本集的一个属性，它的取值为A1,A2,…，An,创建另外一个新属性A′，它与属性A唯一的区别：其中一个已知值An分解为两个值A′n和A′n+1,其余值和A中的完全一样，假设原来n个值已经提供足够的信息使分类正确进行，很明显，则属性A′相对于A没有任何作用。但如果按照Qulnina的标准，属性A′应当优先于属性A选取。
　　综上所知，把ID3算法分别作用在属性A和属性A′上，如果属性选取标准在属性A′上的取值恒大于在属性A上的取值，则说明该算法在建树过程中具有多值偏向；如果属性选取标准在属性A′上的取值与在属性A上的取值没有确定的大小关系，则说明该决策树算法在建树过程中不具有多值偏向性。
　　2.3 ID3算法的缺点
　　（1）ID3算法往往偏向于选择取值较多的属性，而在很多情况下取值较多的属性并不总是最重要的属性，即按照使熵值最小的原则被ID3算法列为应该首先判断的属性在现实情况中却并不一定非常重要。例如：在银行客户分析中，姓名属性取值多，却不能从中得到任何信息。
　　（2）ID3算法不能处理具有连续值的属性，也不能处理具有缺失数据的属性。
　　（3）用互信息作为选择属性的标准存在一个假设，即训练子集中的正、反例的比例应与实际问题领域中正、反例的比例一致。一般情况很难保证这两者的比例一致，这样计算训练集的互信息就会存在偏差。
　　（4）在建造决策树时，每个结点仅含一个属性，是一种单变元的算法，致使生成的决策树结点之间的相关性不够强。虽然在一棵树上连在一起，但联系还是松散的。
　　（5）ID3算法虽然理论清晰，但计算比较复杂，在学习和训练数据集的过程中机器占用率比较大，耗费资源。
　　决策树ID3算法是一个很有实用价值的示例学习算法，它的基础理论清晰，算法比较简单，学习能力较强，适于处理大规模的学习问题，是数据挖掘和知识发现领域中的一个很好的范例，为后来各学者提出优化算法奠定了理论基础。表1是一个经典的训练集。
　　由ID3算法递归建树得到一棵决策树如图2所示。
技术资料出处:武献宇1，王建芬2，谢金龙1
该文章仅供学习参考使用，版权归作者所有。
因本网站内容较多，未能及时联系上的作者，请按本网站显示的方式与我们联系。
【】【】【】【】
上一篇：下一篇：
本文已有(0)篇评论
发表技术资料评论，请使用文明用语
字符数不能超过255
暂且没有评论!
12345678910
12345678910
12345678910
12345678910
电机瞬态测试的核心关键“同步性”
[][][][][][][][][][]
IC热门型号
IC现货型号
推荐电子百科转：决策树算法ID3算法源代码&数据文件
算法：。由给定的训练数据产生一棵判定树。
输入：训练样本，由离散值属性表示；候选属性的集合。
输出：一棵判定树。
创建结点；
都在同一个类类标号属性的值均为，其候选属性值不考虑
作为叶结点，以类标记；
作为叶结点，标记为中最普通的类；类标号属性值数量最大的那个
选择中具有最高信息增益的属性；找出最好的划分属性
标记结点为；
中的未知值将样本按照进行划分
由结点长出一个条件为的分枝；
设是中的样本的集合；
加上一个树叶，标记为中最普通的类；从样本中找出类标号数量最多的，作为此节点的标记
加上一个由&返回的结点；对数据子集递归调用，此时候选属性已删除
//////////////////////////////////////////////////////////////////////////
* 文件名称：ID3.cpp
* 摘 要：ID3算法实现
* 当前版本：1.0
* 作 者：郭运凯
* 完成日期：
* QQ:(海风)
*////////////////////////////////////////////////////////////////////////
#include &stdio.h&
#include &iostream&
#include &vector&
#include &math.h&
#include &string.h&
using namespace&
typedef struct tnode
&char tdata[100];
typedef struct Tree_Node
&char name[100];
&bool isL&//标记是否叶子节点
&vector&tnode&
att_//属性名称列表
&vector&Tree_Node *
}Tree_Node,* pTreeN
typedef struct dnode
&vector&tnode&
typedef struct D_Node
&vector&dnode&DB;
&vector&tnode&
&tnode class_
D_Node G_DB;
pTreeNpde Root = NULL;
typedef struct FreeQNode
&char name[100];
&vector&int&
typedef struct FreeQNodeDouble
&char name[100];
&vector&int&
&vector&FreeQNode&
//存放分类属性列表及相应的出现次数
}FreeQNodeD
typedef struct attr_node
&int attr_
&vector&tnode&
&vector&int&
vector&attr_node& G_Attr_L
typedef struct binNode
&char name[100];
&vector&int&
&struct binNode *
&struct binNode *
typedef struct binNodeDouble
&char name[100];
&vector&int&
&struct binNodeDouble *
&struct binNodeDouble *
&vector&FreeQNode&&
void insert_tree(binNode& * &
r, char str[100])
&if (NULL == r)
&&binNode * node = new
&&strcpy(node-&name,str);
&&node-&count =
&&//printf("[%s,%d]\n",node-&name,node-&count);
&&node-&lchild =
node-&rchild = NULL;
(strcmp(r-&name,str) == 0)
&&&r-&count
(strcmp(r-&name,str) & 0)
&&&insert_tree(r-&lchild,str);
&&&insert_tree(r-&rchild,str);
void delete_bin_tree(binNode *& r)
&if (r != NULL)
&&delete_bin_tree(r-&lchild);
&&delete_bin_tree(r-&rchild);
&&delete(r);
&&r = NULL;
void Bin_tree_inorder(binNode *
r,vector&FreeQNode& &
&if (r != NULL)
&&Bin_tree_inorder(r-&lchild,Fq);
&&//printf("%s,%d\n",r-&name,r-&count);
&&strcpy(ft.name,r-&name);
&&ft.count =
&&for (int i= 0;i
& r-&Set_ID.size();i++)
&&&ft.Set_ID.push_back(r-&Set_ID[i]);&//保存子集对应的ID号
&&Fq.push_back(ft);
//此处少了这条语句，造成结果无法返回
&&Bin_tree_inorder(r-&rchild,Fq);
void Get_attr(binNode * r,attr_node & attr)
&if (r != NULL)
&&Get_attr(r-&lchild,attr);
&&strcpy(t.tdata,r-&name);
&&//printf("%s,%d\n",r-&name,r-&count);
&&attr.attr_name.push_back(t);
&&attr.count_list.push_back(r-&count);//保存出现次数
&&Get_attr(r-&rchild,attr);
void insert_tree_double(binNodeDouble *& r, int
DB_ID,char attr_name[100],char class_name[100])
&if (NULL == r)
&&binNodeDouble * node = new
&&strcpy(node-&name,attr_name);
&&node-&count =
&&node-&row_id.push_back(DB_ID);
&&node-&lchild
= node-&rchild =
&&strcpy(fq.name,class_name);
&&fq.count = 1;
&&fq.Set_ID.push_back(DB_ID);&//保存子集所对应的ID号
&&node-&classes.push_back(fq);
(strcmp(r-&name,attr_name) == 0)
&&&r-&count
&&&r-&row_id.push_back(DB_ID);//这里也需要保存相应的ID号
&&&bool found
&&&for (int i
= 0; i& r-&classes.size();i++)
(strcmp(r-&classes[i].name,class_name) == 0)
&&&&&r-&classes[i].count
&&&&&r-&classes[i].Set_ID.push_back(DB_ID);//保存子集对应的ID号
&&&&&found
= //发现相同的变量名，计数器增1,
&&&&&&&&&&&&
//并退出循环
&&&&FreeQNode
&&&&strcpy(fq.name,class_name);
&&&&fq.count
&&&&fq.Set_ID.push_back(DB_ID);//保存子集所对应的ID号
&&&&r-&classes.push_back(fq);
(strcmp(r-&name,attr_name) & 0)
&&&insert_tree_double(r-&lchild,DB_ID,attr_name,class_name);
&&&insert_tree_double(r-&rchild,DB_ID,attr_name,class_name);
void delete_bin_tree_double(binNodeDouble *&
&if (r != NULL)
&&delete_bin_tree_double(r-&lchild);
&&delete_bin_tree_double(r-&rchild);
&&delete(r);
&&r = NULL;
void Bin_tree_inorder_double(binNodeDouble *&
r,vector&FreeQNodeDouble&
&if (r != NULL)
&&Bin_tree_inorder_double(r-&lchild,Fq);
&&FreeQNodeD
&&strcpy(ft.name,r-&name);
//保存候属性的名称
&&ft.count =
&&for (int k =
0;k& r-&row_id.size();k++)
&&&ft.row_id.push_back(r-&row_id[k]);
&&//printf("doubleTree.
%s,%d\n",r-&name,r-&count);
&&for (int i =
0;i& r-&classes.size();i++)
&&&FreeQNode
&&&strcpy(fq.name,r-&classes[i].name);
&&&fq.count =
r-&classes[i].
&&&for (int j =
r-&classes[i].Set_ID.size();j++)
&&&&fq.Set_ID.push_back(
r-&classes[i].Set_ID[j]);&//保存子集对应的ID号
&&&ft.classes.push_back(fq);
&&Fq.push_back(ft);
&&ft.classes.erase(ft.classes.begin(),ft.classes.end());//使用完，必须清空
&&Bin_tree_inorder_double(r-&rchild,Fq);
void getFqI(vector&int& S,int
class_id,vector&FreeQNode&
&binNode * root = NULL;
&for (int i = 0;i&
S.size();i++)
&&insert_tree(root,G_DB.DB[S[i]].row[class_id].tdata);
&Bin_tree_inorder(root,Fq);
&delete_bin_tree(root);
void getFqIA(vector&int& S,int
attr_id,int
class_id,vector&FreeQNodeDouble&
&binNodeDouble * root = NULL;
&printf("call getFqIA\n");
&for (int i = 0;i&
S.size();i++)
&&insert_tree_double(root,S[i],G_DB.DB[S[i]].row[attr_id].tdata,G_DB.DB[S[i]].row[class_id].tdata);
&Bin_tree_inorder_double(root,Fq);
&delete_bin_tree_double(root);
void readdata(char *filename)
&char str[1000];
&fp = fopen(filename,"r");
&fgets(str,1000,fp);
&int len = strlen(str);
&int attr_no = 0;&//属性个数
&int row_num = 0;
&if (str != NULL)
&&row_num = 1;
&for (int i = 0;i&
&&if (str[i] == '\t')
&&&attr_no
&attr_no ++;//最后一个是回车，整个属性值+1
&printf("%d\n",attr_no);
&while(fgets(str,1000,fp) != NULL)
++;&//统计行数
&fclose(fp);
&fopen(filename,"r");
&for (i = 0;i&attr_i++)
&&fscanf(fp,"%s",t.tdata);
&&G_DB.attr_name.push_back(t);
&&printf("%s\n",t.tdata);
&strcpy(G_DB.class_name.tdata,G_DB.attr_name[attr_no-1].tdata);
&for (int j = 1;j&
&&for (int i =
0;i&attr_i++)
&&&fscanf(fp,"%s",temp.tdata);
&&&dt.row.push_back(temp);
&&G_DB.DB.push_back(dt);
&&dt.row.erase(dt.row.begin(),dt.row.end());
&printf("%d\n",G_DB.DB.size());
&for (i = 0;i&
G_DB.DB.size();i++)
&&for (int j =
0;j& G_DB.DB[i].row.size();j++)
&&&printf("%s\t",G_DB.DB[i].row[j].tdata);
&&printf("\n");
double Fnc_I(vector&int& S,int
&//给定一个子集，计算其按照class_id所对应的分类属性进行分类时的期望I
//&printf("called Fnc_I(%d)\n ",class_id);
&vector&FreeQNode&
&getFqI(S,class_id,Fq);&
&//调用getFqI获取按照Class_id为分类标准的分类结果,当Fq中为一条数据时，则子集S都属于一个分类
&//否则，从中找到出现此时最大的，作为返回结果
& //& printf("begin to compute I
&double total = 0;
&for (int i = 0;i&
Fq.size();i++)
&&total += Fq[i].
&//&printf("%s,%d\n",Fq[i].name,Fq[i].count);
&double result = 0;
&if (0 == total)
&&return 0;
&for (i = 0;i&
Fq.size();i++)
&&double p =
Fq[i].count/
&&result += -1*(p *
log(p)/log(2));
&& // printf("FNC_I
return\n\n");
double Fnc_IA(vector&int& S,int
attr_id,int
class_id,vector&FreeQNodeDouble&
&//给定一个子集，计算其按照class_id所对应的分类属性进行分类时的期望I
&printf("给定一个子集，计算其按照class_id所对应的分类属性进行分类时的期望I\n");
&getFqIA(S,attr_id,class_id,Fq);
&double total = 0;
&for (int i = 0;i&
Fq.size();i++)
&&total += Fq[i].
&double result = 0;
&if (0 == total)
&&return 0;
&for (i = 0;i& Fq.size();i++)
&&double stotal =
&&double sresult = 0;
(pr)&printf("[%s,%d]\n",Fq[i].name,Fq[i].count);
&&for (int j = 0;j
& Fq[i].classes.size();j++)
(pr)&printf("%s,%d\n",Fq[i].classes[j].name,Fq[i].classes[j].count);
&&&for (int k =
0;k & Fq[i].classes[j].k++)
&&&//&printf("%d\t",Fq[i].classes[j].Set_ID[k]+1);
//printf("\n");
&&&double sp =
Fq[i].classes[j].count/ //计算子集的频率
&&&sresult +=
-1*(sp*log(sp)/log(2));
&&result += (stotal/total) *
(pr)&printf("\n");
SelectBestAttribute(vector&int&
Samples,vector&int&
attribute_list,int class_id)
&//输入训练数据集Samples，候选属性列表attribute_list
&//分类属性标记class_id
&//返回best_attribute
&double fi = Fnc_I(Samples,5);
//&printf("%lf\n",fi);&
&double IA = ;
&int best_attrib = -1;
&for (int i = 0;i &
attribute_list.size();i++)
&&vector&FreeQNodeDouble&
double tfa = Fnc_IA(Samples,attribute_list[i],class_id,fqd);
&//&printf("%d, FIA =
%lf\n",i,tfa);
if (IA & tfa)
&&& best_attrib
&//printf("%lf\n",IA);
&printf("gain(%d) = %lf - %lf =
%lf\n",best_attrib,fi,IA,fi - IA);
attribute_list[best_attrib];&&
void fnc_getattr(vector&int&
Samples,int att_id,attr_node &at)
&binNode * root = NULL;
&for (int i = 0;i&
Samples.size();i++)
&&insert_tree(root,G_DB.DB[Samples[i]].row[att_id].tdata);
&Get_attr(root,at);
&delete_bin_tree(root);
get_class_num_and_name(vector&int&
Samples,int class_id,int & class_num,tnode
& class_name)
&binNode * root = NULL;
&for (int i = 0;i&
Samples.size();i++)
&&insert_tree(root,G_DB.DB[Samples[i]].row[class_id].tdata);
&Get_attr(root,at);&
&delete_bin_tree(root);
&//printf("att_size =
%d\n",at.attr_name.size());
&class_num = at.attr_name.size();
&int num = 0;
&int id = 0;
&if (1 == class_num)
&&strcpy(class_name.tdata,at.attr_name[0].tdata);
&&for (int j = 0;j
& at.attr_name.size();j++ )
(at.count_list[j] & num)
= at.count_list[j];
&strcpy(class_name.tdata,at.attr_name[id].tdata);//保存最普通的类名
getAllTheAttribute(vector&int&
Samples,vector&int&
attribute_list,int class_id)
&printf("all the attribute are:\n");
&for (int i = 0;i &
attribute_list.size();i++)
&&at.attr_id =
attribute_list[i];
&&fnc_getattr(Samples,attribute_list[i],at);&
&&G_Attr_List.push_back(at);
&for (i = 0;i
&G_Attr_List.size();i++)
&&printf("%d\n",G_Attr_List[i].attr_id);
&&for (int j =
0;j& G_Attr_List[i].attr_name.size();j++)
&&&printf("%s\t",G_Attr_List[i].attr_name[j].tdata);
&&printf("\n");
void Generate_decision_tree(Tree_Node * &
root,vector&int& Samples,
vector&int& attribute_list,int
&printf("begin to call
Generate_decision_tree.\n");
&printf("the samples are:\n");
&for (int ts = 0;ts &
Samples.size();ts++)
&&printf("%d\t",Samples[ts]);
&printf("\nend\n");
&int class_num = 0;
&tnode class_
&get_class_num_and_name(Samples,class_id,class_num,class_name);
//判断是否属于同一类
&//如果是同一类，则class_num =1，class_name就是类名
&//否则，class_num &1 ,class_name就是
最普通的类名
&//printf("class_num = %d\n",class_num);
& root = new Tree_N//(1) 创建结点 N；
& root-&isLeaf =
//这里显式初始化为False，以免程序出错
&if (1 == class_num)
&&printf("samples 都在同一个类【%s】
,返回\n",class_name.tdata);
&&//(2) if samples 都在同一个类C
//类标号属性的值均为C，其候选属性值不考虑
&&//(3) return N 作为叶结点，以类C
&&strcpy(root-&name,class_name.tdata);
&&root-&isLeaf =
&if (attribute_list.size() == 0)
&&printf("attribute_list.size()
&&//(4) if attribut_list 为空
then&&&&&&&
&&//(5) return N 作为叶结点，标记为
samples 中最普通的类； //类标号属性值数量最大的那个
&&//上面已经计算了，这里直接引用了
&&strcpy(root-&name,class_name.tdata);
&&root-&isLeaf =
&//开始找最佳划分
&int best_arrtib =
SelectBestAttribute(Samples,attribute_list,class_id);
&printf("the best attrib_id is %d,attribute_name
is [%s]\n",best_arrtib,G_DB.attr_name[best_arrtib].tdata);
&vector&FreeQNodeDouble&
&double tfa =
Fnc_IA(Samples,best_arrtib,class_id,Fq);
&vector&int&
&for (int tt =
0;tt&attribute_list.size();tt++ )
&&if (attribute_list[tt] !=
best_arrtib)
&&&att_list.push_back(attribute_list[tt]);
///////////////////////////直接选择里面最普通的类///////////////////////////////////////////////
&int id = 0;
&int num = Fq[id].
&for (int i = 1;i &
Fq.size();i++)
&&if (num &
Fq[i].count)
&printf("最普通的类名:%s\n",Fq[id].name);
///////////////////////////直接选择里面最普通的类///////////////////////////////////////////////
&printf("开始处理，将Sample按照%d,%s进行划分\n",best_arrtib,G_DB.attr_name[best_arrtib].tdata);
&strcpy(root-&name,G_DB.attr_name[best_arrtib].tdata);&//这里已经是最好的划分了
&//(6) 选择attribute_list
中具有最高信息增益的属性best_attribute；//找出最好的划分属性
&//(7) 标记结点 N 为best_attribute；
&printf("划分共有%d个子集\n",Fq.size());
printf("G_Attr_List[best_arrtib].attr_name.size() =
%d\n",G_Attr_List[best_arrtib].attr_name.size());
&&& for (int k =
G_Attr_List[best_arrtib].attr_name.size();k++)
&&//root-&att_list.push_back(G_Attr_List[best_arrtib].attr_name[k]);//保存相应的属性值
bool has_attr = //判断实际数据集中是否有该属性值，无没有，则跳过 郭运凯
&&for (int nn = 0;nn
& Fq.size();nn ++)
(strcmp(G_Attr_List[best_arrtib].attr_name[k].tdata,Fq[nn].name) ==
&&&&has_attr
&&if ( ! has_attr)
&&&//如果没有该属性值，则跳过,不然就会出现错误的规则(假设该子集中就一种情况，
&&&&&&&&&&&
// G_Attr_List[best_arrtib].attr_name
里面却有3中属性，这样，就会生成3条规则，而不是一条规则，并且后面两条规则是错误的)
&&root-&att_list.push_back(G_Attr_List[best_arrtib].attr_name[k]);//保存相应的属性值
&&// (8) for each
best_attribute 中的已知值a i //将样本samples按照best_attribute进行划分
&&printf("\n开始获取第[%d]个划分\n",k);
&&//printf("[%d],name =
%s\n",k,G_Attr_List[best_arrtib-1].attr_name[k].tdata);
这里出了问题，应该直接访问best_arrtib
&&printf("[%d],属性名 =
%s\n",k,G_Attr_List[best_arrtib].attr_name[k].tdata);
&&bool found =
&&for (int n = 0;n
& Fq.size();n++)
&&&printf("Fq[%d].name=%s\n",n,Fq[n].name);
(strcmp(G_Attr_List[best_arrtib].attr_name[k].tdata,Fq[n].name) ==
&&&&printf("k=%d,n=%d\n",k,n);
&&&&printf("%s\t%s\n",G_Attr_List[best_arrtib].attr_name[k].tdata,Fq[n].name);
&&&&//(13)
else 加上一个由 Generate_decision_tree(si,attribute_list -
best_attribute)
&&&&//返回的结点；//对数据子集si,递归调用，此时候选属性已删除best_attribute
&&&&pTreeNpde
trnode = new Tree_N//(1) 创建结点 N；
&&&&//Generate_decision_tree(trnode,Fq[k].row_id,att_list,class_id);
//这里Fq的下标应该取n,而不是k, 郭运凯
&&&&Generate_decision_tree(trnode,Fq[n].row_id,att_list,class_id);
&&&&root-&child_list.push_back(trnode);
&&if (!found)
&&&// (9) 由结点 N
长出一个条件为 best_attribute = a i 的分枝；
&&&//(10) 设si
是samples 中best_attribute = a i 的样本的集合；//a partition
&&&//(11) if si
(12) 加上一个树叶，标记为 samples 中最普通的类；//从样本中找出类标号数量最多的，作为此节点的标记
&&&&pTreeNpde
trnode = new Tree_N//(1) 创建结点 N；
&&&&strcpy(trnode-&name,Fq[id].name);
trnode-&isLeaf =
&&&&root-&child_list.push_back(trnode);
void generage_decision_rules(Tree_Node * r,char rules[1000],int
&//printf("%d,%s\n",level,r-&name);
&if (1 == level)
&&for (int i = 0;i
& r-&child_list.size();i++)
str[1000];
&&&strcpy(str,rules);
&&&strcat(str,"IF
&&&strcat(str,r-&name);
&&&strcat(str,"
&&&strcat(str,r-&att_list[i].tdata);
&&&strcat(str,"\"");
&&&generage_decision_rules(r-&child_list[i],str,level
r-&isLeaf)
&&&for (int i =
0;i & r-&child_list.size();i++)
str[1000];
&&&&strcpy(str,rules);
&&&&strcat(str,"
&&&&strcat(str,r-&name);
&&&&strcat(str,"
&&&&strcat(str,r-&att_list[i].tdata);
&&&&strcat(str,"
&&&&//printf("
AND %s = \"%s\"
",r-&name,r-&att_list[i].tdata);
&&&&generage_decision_rules(r-&child_list[i],str,level
&&&printf("%s",rules);
&&&printf(" THEN
%s = \"%s\"\n",G_DB.class_name.tdata,r-&name);
void test()
&vector&int&
&for (int i = 0;i&
G_DB.DB.size();i++)
&&s.push_back(i);
&vector&int&
&int class_id = G_DB.attr_name.size()-1;
&for ( i =0;i&
G_DB.attr_name.size()-1;i++)
&&arrt_list.push_back(i);
&getAllTheAttribute(s,arrt_list,class_id);
&Generate_decision_tree(Root,s,arrt_list,class_id);
&char rules[1000] ="";
&generage_decision_rules(Root,rules,1);
void main()
&readdata("data.txt");
已投稿到：