《模式识别——决策树算法.doc》由会员分享，可在线阅读，更多相关《模式识别——决策树算法.doc（18页珍藏版）》请在三一办公上搜索。
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);OutputForm
29、at format = OutputFormat.createPrettyPrint(); / 美化格式XMLWriter output = new XMLWriter(fw, format);output.write(xmldoc);output.close(); catch (IOException e) System.out.println(e.getMessage();四 ID3算法性能分析1 优势搜索空间是完全的假设空间，目标函数必在搜索空间中，不存在无解的危险；全盘使用训练数据，而不是像候选剪除算法一个一个地考虑训练例。这样做的优点是，可以利用全部训练例的统计性质进行决策，从而抵抗
30、噪音。2 弊端以上介绍的基本算法对于树的每一层，需要扫描一遍D中的元组。在处理大型数据库时，这可能导致很长的训练时间和内存的不足。对于非增量式学习任务，ID3算法常常是建立决策树的很好的选择。但对于增量式学习任务来说，由于ID3不能增量地接受训练例，这就使得每增加一次实例都必须抛弃原有决策树，重新构造新的决策树，造成了极大的开销。C4.5能够避免这个问题。搜索中只维持一个解，不能像候选剪除算法那样返回所有可能的与训练例集一致的假设，并优化地查询新例以获得收敛于目标函数的解；其搜索无回溯。它可能收敛于局部最优解而丢失全局最优解，因为一个一个地考虑训练例，不容易像剪除算法那样使用新例步进式地改进决
31、策树。五 ID3算法改进传统的ID3算法选择属件A作为测试属性的原则是使得其信息增益最大。研究表明这种方法存在一个弊端：算法往往偏向于选择取值较多的属性，因为加权和的方法使得实例集的分类趋向于抛弃小数据量的数据元组，然而取值较多的属性却不总是最优的属性，即按照使熵值最小和信息增益最大的原则被ID3算法列为应该首先选取的属性在现实情况中却并不那么重要，也就是说对这些属性进行测试不会提供太多的信息。针|对ID3算法偏向于选择取值较多但实际中并不总是最优的属件作为测试属件的缺点，这里引人用户兴趣度：给定01，称为用户对不确定知识的兴趣度，其太小由决策者根据先验知识或领域知识来确定。它是个模糊的概念，
32、通常指关于某一事务的先验知识，包括领域知识和专家建议，具体到决策树学习中则是指在决策树训练过程中除了用于生成和修改决策树的实例集之外的所有影响决策树规则生成和选择的因素。改进的ID3算法是针对规则生成方法即属性选择标准算法进行了改进，通过对式(2)中加权和增加用户兴趣度，加强了属性的标注，降低了非重要属性的标注，把加权和转换为加权和加用户兴趣度，使生成决策树时数量少的数据元组不会被淹没，最终使决策树减少了对取值较多的属性的依赖性，从而尽可能地减少大数据掩盖小数据的现象发生。利用用户兴趣度把（2）修改为：六、 附录核心算法的主要源代码参考文献1 张学工. 模式识别. 第三版. 北京：清华大学出版社，2010-8.2 ID3决策树
