




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、数学与计算机学院课程名称: 模式识别 题 目: 决策树 任课老师: 王类 年级专业: 2014级应用数学 姓 名: 闫辉 时 间: 2014 年 12 月 10 日目 录一 决策树算法介绍3二 id3算法描述3三 id3算法java实现51 实例52 算法的java实现7四 id3算法性能分析141 优势142 弊端14五 id3算法改进14六、 附录核心算法的主要源代码15161617参考文献18决策树算法一 决策树算法介绍决策树是数据挖掘分类算法的一个重要方法。在各种分类算法中,决策树是最直观的一种。决策树(decision tree)是在已知各种情况发生概率的基础上,通过构成决策树来求取
2、净现值的期望值大于等于零的概率,评价项目风险,判断其可行性的决策分析方法,是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干,故称决策树。在机器学习中,决策树是一个预测模型,他代表的是对象属性与对象值之间的一种映射关系。entropy = 系统的凌乱程度,使用算法id3,c4.5和c5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。决策树是由一系列节点组成的,每一个节点代表一个特征和相应的决策规则。最上部的节点是根节点(这里的“树”通常是倒置过来画的,即根在顶端),此时所有的样本都在一起,经过该节点后被划分到各个子节点中。每个子节点再用新的特征来进一步决策,直到
3、最后的叶节点。在叶节点上,每一个节点只包含纯一类的样本,不需要再划分。决策树构造可以分两步进行。第一步,决策树的生成:由训练样本集生成决策树的过程。一般情况下,训练样本数据集是根据实际需要有历史的、有一定综合程度的,用于数据分析处理的数据集。第二步,决策树的剪技:决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修下的过程,主要是用新的样本数扼集(称为测试数据集)中的数据校验决策树生成过程中产生的初步规则,将那些影响预衡准确性的分枝剪除。二 id3算法描述id3算法是由quinlan首先提出的。该算法是以信息论为基础,以信息熵和信息增益度为衡量标准,从而实现对数据的归纳分类。 id3算法主要
4、针对属性选择问题,是决策树学习方法中最具影响和最为典型的算法。id3采用贪心方法,其中决策树以自顶向下递归的分治方式构造。大多数决策树归纳算法都沿用这种自顶向下的方法,从训练元组集和它们的相关联的类标号开始构造决策树。随着树的构建,训练集递归地划分成较小的子集。id3算法中关键的一步是属性选择度量,即选择分裂准则。其中的三种度量方法分别是信息增益、增益率和gini指标。(示例算法选择了第一种方法)。当获取信息时,将不确定的内容转为确定的内容,因此信息伴着不确定性。算法的基本策略如下:算法:generate_decision_tree。由数据划分d的训练元组产生决策树。输入:1.数据划分d是训练
5、元组和对应类标号的集合2.attribute_list,候选属性的集合3.attribute_selection_method,一个确定“最好”地划分数据元组为个体类的分裂准则的过程。这个准则由分裂属性和分裂点或分裂子集组成。输出:一棵决策树方法:创建一个节点n;if d中的元组都是同一类c,then返回n作为叶节点,以类c标记;if attribute_list 为空then返回n作为叶节点,标记为d中的多数类; /多数表决使用attribute_selection_method(d,attribute_list),找出“最好”的splitting_criterion;7用splitting
6、_criterion标记节点n;if splitting_ attribute是离散值的并且允许多路划分then /不限于二叉树attribute_list attribute_list - splitting_ attribute ; /删除划分属性for splitting_criterion的每个输出j / 划分元组并对每个划分产生子树设dj是d中满足输出j的数据元组的集合;/一个划分if dj为空then加一个树叶到节点n,标记为d中的多数类;else 加一个由generate_decision_tree(dj,attribute_list)返回的节点到节点n;end for返回n;上
7、述算法基本策略中,用到三个参数d、attribute_list和attribute_selection_method调用该算法。其中,d为数据划分;attribute_list是描述元组的属性列表;attribute_selection_method指定选择属性的启发式过程,所选择的属性按类“最好”地区分元组。该过程使用一种属性选择度量,如信息增益和gini指标。属性选择度量是一种选择分裂准则,将给定的类标记的训练元组的数据划分d“最好”地分成个体类的启发式方法。如果我们要根据分裂准则的输出将d划分成较小的划分,理想地,每个划分是“纯”的,即,落在给定划分的所有元组都属于相同的类。从概念上讲,
8、最好的划分准则是导致最接近这种情况的划分。本文主要介绍一种流行的属性选择度量信息增益。信息增益度量基于claude shannon在研究消息的值或“信息内容”的信息论方面的先驱工作。设节点n代表或存放划分d的元组。选择具有最高信息增益的属性作为节点n的分裂属性。该属性使结果划分中的元组分类所需的信息量最小,并反映这些划分中的最小随机性或“不纯性”。这种方法使对给定元组分类所需的期望测试数目最小,并确保找到一棵简单的树。对于d中的元组分类所需的期望信息由下式给出:(1)其中,pi是d中任意元组属于类ci的概率,并用|ci,d|/|d|估计。使用以2为底的对数函数,因为信息用二进位编码。info(
9、d)是识别d中的元组的类标号所需的平均信息量。这里,我们所具有的信息只是每个类的元组所占的百分比。info(d)又称d的熵。假设按属性a划分d中的元组,其中属性a根据训练数据的观测具有v个不同值a1,a2,av。可以用属性a将d划分为v个子集d1d2,dv ,其中dj包含d中的元组,它们在a上具有值aj。这些划分将对应于从节点n生长出来的分枝。理想地,我们希望该划分产生元组的准确分类,即,每个划分都是纯的。为了得到准确的分类我们还需要多少信息?这个量由下式度量: (2)项充当第j个划分的权重。是基于按a划分对d的元组分类所需要的期望信息。所需要的信息越小,划分的纯度越高。信息增益定义为原来的信
10、息需求(即仅基于类比例)与新的需求(即对a划分之后得到的)之间的差。即是: (3)gain(a)告诉我们通过a的划分我们得到了多少。选择具有最高信息增益的属性作为节点n的分裂属性。这等价于按能做“最佳划分”的属性a划分,使得完成元组分类还需要的信息最少。三 id3算法java实现1 实例假定某推销员根据经验得知,学生是否会由家长接送,与学生的年龄、性别和家庭收入关系最大。于是,她收集了某一学校学生由家长接送的信息,得到了表如下的数据,这就是她的训练样本集,她的目标是建立能够估学生是否会由家长接送的决策树。这可以看作一个两类的分类问题。顾客编号年龄性别月收入是否购买19男4000否211女500
11、0否312女3800否414女2000否58男7000否612女2500否79女2000否88女9000是914男5000是109男7000否1112女4800否126男2800否1312女4500否1412男2800是1514男4000是1615女2500否面对这些数据,她无从下手分析。有经验的同事告诉她,应该先把年龄和收入情况分成几个等级。于是她查阅了有关资料,决定把年龄以10岁为门槛分成两档,把收入按照每月3000元以下、3000-6000元和6000元以上分为低、中、高三档,这样,她的数据就变成了表如下的形式。接下来的事情就是如何根据这样的样本数据构造决策树。顾客编号年龄性别月收入是否
12、购买110女中否310女中否410女低否510女低否710女低否810男中是1010女中否1210男低否1310男低是1510男中是1610女低否这个例子中,每个属性都是离散值的,连续的属性已经被离散化。对于表中数据,在不考虑任何特征时,16人中有4人需要家长接送,12人不需要家长接送,计算出此时的熵不纯度为其中,info(d)表示总共16个样本中4个为一类,12个为另一类时的熵不纯度。现在希望找到一个能够最有效地划分买车与不买车两类的特征,也就是希望引入该特征后,能够使不纯度最有效地减少。于是,相关人员逐一考查各个特征,分别计算如果采用年龄、性别或月收入为特征把样本划分,划分后的熵不纯度是否
13、会减少,比较哪个特征能够使不纯度减少幅度最大。对年龄特征的计算方法和结果是:如果采用年龄作为根节点,则把所有样本分为两组,30岁以下组有6人,1人需要家长接送;30岁以上组有10人,3人需要家长接送。总的熵不纯度是这两组样本上计算的不纯度按照样本比例的加权求和,即这样,采用年龄作为根节点后,在下一级的熵不纯度比上一级减少的量是称作不纯度减少量,或信息增益(information gain)。用同样的方法,相关人员又分别计算了采用性别特征、月收入特征作为根节点所能够带来的信息增益相关人员发现,用性别作为第一个特征能够带来不纯度最大的减小,于是决定用性别特征作为决策树的根节点,如图(1)所示:所有
14、16个样本被按照性别特征分成了两组,女性组有9个样本,其中1人需要家长接送;男性组有7个样本,其中3个人不。下面需要构建决策树的下一层节点。对于女性组合男性组,用上面的相同的方法,分别考查两组样本上如果再采用年龄或月收入作为特征所得的不纯度减少。结果发现,对于男性组,采用年龄特征后不纯度减少最大,为0.9852;对于女性组,则是采用月收入作为特征后不纯度减少最多,为0.688。这样就可以分别用这两个特征构建下一级的决策树节点。事实上,在这个简单的例子里,这时各个节点上已经都是纯的样本了,因此这一级节点就是叶节点。决策树构建完成,如图(2)所示。 2 算法的java实现import java包;
15、public class id3 private arraylist attribute = new arraylist(); / 存储属性的名称private arraylistarraylist attributevalue = new arraylistarraylist(); / 存储每个属性的取值private arraylist data = new arraylist(); / 原始数据int decatt; / 决策变量在属性集中的索引public static final string patternstring = attribute(.*)(.*?);document x
16、mldoc;element root;public id3() xmldoc = documenthelper.createdocument();root = xmldoc.addelement(root);root.addelement(decisiontree).addattribute(value, null);public static void main(string args) id3 inst = new id3();inst.readarff(new file(d:newprojectweka-3-7-1weka-3-7-1weka-3-7-1dataweather.nomin
17、al.arff);inst.setdec(play);linkedlist ll = new linkedlist();for (int i = 0; i inst.attribute.size(); i+) if (i != inst.decatt)ll.add(i);arraylist al = new arraylist();for (int i = 0; i inst.data.size(); i+) al.add(i);inst.builddt(decisiontree, null, al, ll);inst.writexml(d:newprojecttestweather.xml)
18、;return;/ 读取arff文件,给attribute、attributevalue、data赋值public void readarff(file file) try filereader fr = new filereader(file);bufferedreader br = new bufferedreader(fr);string line;pattern pattern = ppile(patternstring);while (line = br.readline() != null) matcher matcher = pattern.matcher(line);if (m
19、atcher.find() attribute.add(matcher.group(1).trim();string values = matcher.group(2).split(,);arraylist al = new arraylist(values.length);for (string value : values) al.add(value.trim();attributevalue.add(al); else if (line.startswith(data) while (line = br.readline() != null) if (line = )continue;s
20、tring row = line.split(,);data.add(row); else continue;br.close(); catch (ioexception e1) e1.printstacktrace();/ 设置决策变量public void setdec(int n) if (n = attribute.size() system.err.println(决策变量指定错误。);system.exit(2);decatt = n;public void setdec(string name) int n = attribute.indexof(name);setdec(n);
21、/ 给一个样本(数组中是各种情况的计数),计算它的熵public double getentropy(int arr) double entropy = 0.0;int sum = 0;for (int i = 0; i arr.length; i+) entropy -= arri * math.log(arri + double.min_value)/ math.log(2);sum += arri;entropy += sum * math.log(sum + double.min_value) / math.log(2);entropy /= sum;return entropy;pu
22、blic boolean infopure(arraylist subset) string value = data.get(subset.get(0)decatt;for (int i = 1; i subset.size(); i+) string next = data.get(subset.get(i)decatt;/ equals表示对象内容相同,=表示两个对象指向的是同一片内存if (!value.equals(next)return false;return true;/ 给定原始数据的子集(subset中存储行号),当以第index个属性为节点时计算它的信息熵public d
23、ouble calnodeentropy(arraylist subset, int index) int sum = subset.size();double entropy = 0.0;int info = new intattributevalue.get(index).size();for (int i = 0; i info.length; i+)infoi = new intattributevalue.get(decatt).size();int count = new intattributevalue.get(index).size();for (int i = 0; i s
24、um; i+) int n = subset.get(i);string nodevalue = data.get(n)index;int nodeind = attributevalue.get(index).indexof(nodevalue);countnodeind+;string decvalue = data.get(n)decatt;int decind = attributevalue.get(decatt).indexof(decvalue);infonodeinddecind+;for (int i = 0; i info.length; i+) entropy += ge
25、tentropy(infoi) * counti / sum;return entropy;/ 构建决策树public void builddt(string name, string value, arraylist subset,linkedlist selatt) element ele = null;suppresswarnings(unchecked)list list = root.selectnodes(/ + name);iterator iter = list.iterator();while (iter.hasnext() ele = iter.next();if (ele
26、.attributevalue(value).equals(value)break;if (infopure(subset) ele.settext(data.get(subset.get(0)decatt);return;int minindex = -1;double minentropy = double.max_value;for (int i = 0; i selatt.size(); i+) if (i = decatt)continue;double entropy = calnodeentropy(subset, selatt.get(i);if (entropy minent
27、ropy) minindex = selatt.get(i);minentropy = entropy;string nodename = attribute.get(minindex);selatt.remove(new integer(minindex);arraylist attvalues = attributevalue.get(minindex);for (string val : attvalues) ele.addelement(nodename).addattribute(value, val);arraylist al = new arraylist();for (int
28、i = 0; i subset.size(); i+) if (data.get(subset.get(i)minindex.equals(val) al.add(subset.get(i);builddt(nodename, val, al, selatt);/ 把xml写入文件public void writexml(string filename) try file file = new file(filename);if (!file.exists()file.createnewfile();filewriter fw = new filewriter(file);outputformat format = outputformat.createprettyprint(); / 美化格式xmlwriter output = new xmlwriter(fw, format);output.write(xmldoc);output.close(); catch (ioexception e) system.out.println(e.getmessage();四 id3算法性能分析1 优势搜索空间是完全的假设空间,目标函数必在搜索空间中,不存在无解的危险;全盘使用训练数据,而不是像候选剪除
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年江西烟草招聘考试真题及答案
- 考点解析人教版八年级上册物理光现象《平面镜成像》定向攻克试题(解析版)
- 2025年道路运输企业主要负责人和安全生产管理人员考试(安全生产管理人员)练习题及答案
- 2025年建筑结构设计与技术施工综合测评试题及答案
- 难点解析人教版八年级物理上册第5章透镜及其应用-5.5显微镜和望远镜专题训练试题(含详解)
- 2025年煤矿企业主要负责人安管能力考试考前模拟试题及答案
- 综合解析人教版八年级上册物理机械运动《运动的描述》综合练习练习题(含答案解析)
- 2025高中从句试题及答案解析
- 考点解析人教版八年级物理上册第5章透镜及其应用-凸透镜成像的规律专项训练练习题
- 综合解析人教版八年级物理《压强》单元测试练习题(含答案详解)
- 新闻记者职业资格《新闻采编实务》考试题库(含答案)
- 图解自然资源部《自然资源领域数据安全管理办法》
- 2024年四川省绵阳市中考英语试题卷(标准含答案)
- 股东之间股权转让合同协议书(2篇)
- PLC入门课程课件
- 港口液体危化品装卸管理人员理论考试题库(浓缩500题)
- 2024年深圳市龙华建设发展集团有限公司招聘笔试冲刺题(带答案解析)
- 药师竞聘正高述职报告
- 昇兴(安徽)包装有限公司年产 18 亿只铝制两片罐项目环境影响评价报告书
- 企业电气安全事故案例分析
- 2023学年完整公开课版液压方枕器
评论
0/150
提交评论