文档章节

ID3算法

东方神剑
 东方神剑
发布于 2014/11/12 17:55
字数 1913
阅读 8907
收藏 6

先上问题吧,我们统计了14天的气象数据(指标包括outlook,temperature,humidity,windy),并已知这些天气是否打球(play)。如果给出新一天的气象指标数据:sunny,cool,high,TRUE,判断一下会不会去打球。

outlook temperature humidity windy play
sunny hot high false no
sunny hot high true no
overcast hot high false yes
rainy mild high false yes
rainy cool normal false yes
rainy cool normal true no
overcast cool normal true yes
sunny mild high false no
sunny cool normal false yes
rainy mild normal false yes
sunny mild normal true yes
overcast mild high true yes
overcast hot normal false yes
rainy mild high true no

 

这个问题当然可以用朴素贝叶斯法求解,分别计算在给定天气条件下打球和不打球的概率,选概率大者作为推测结果。

现在我们使用ID3归纳决策树的方法来求解该问题。

预备知识:信息熵

熵是无序性(或不确定性)的度量指标。假如事件A的全概率划分是(A1,A2,...,An),每部分发生的概率是(p1,p2,...,pn),那信息熵定义为:

通常以2为底数,所以信息熵的单位是bit。

补充两个对数去处公式:

ID3算法

构造树的基本想法是随着树深度的增加,节点的熵迅速地降低。熵降低的速度越快越好,这样我们有望得到一棵高度最矮的决策树。

在没有给定任何天气信息时,根据历史数据,我们只知道新的一天打球的概率是9/14,不打的概率是5/14。此时的熵为:

属性有4个:outlook,temperature,humidity,windy。我们首先要决定哪个属性作树的根节点。

对每项指标分别统计:在不同的取值下打球和不打球的次数。

下面我们计算当已知变量outlook的值时,信息熵为多少。

outlook=sunny时,2/5的概率打球,3/5的概率不打球。entropy=0.971

outlook=overcast时,entropy=0

outlook=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的情况,根据历史数据,我们作出类似table 2的一张表,分别计算gain(temperature)、gain(humidity)和gain(windy),选最大者为N1。

依此类推,构造决策树。当系统的信息熵降为0时,就没有必要再往下构造决策树了,此时叶子节点都是纯的--这是理想情况。最坏的情况下,决策树的高度为属性(决策变量)的个数,叶子节点不纯(这意味着我们要以一定的概率来作出决策)。

Java实现

最终的决策树保存在了XML中,使用了Dom4J,注意如果要让Dom4J支持按XPath选择节点,还得引入包jaxen.jar。程序代码要求输入文件满足ARFF格式,并且属性都是标称变量。

实验用的数据文件:

@relation weather.symbolic 
@attribute outlook {sunny, overcast, rainy} 
@attribute temperature {hot, mild, cool} 
@attribute humidity {high, normal} 
@attribute windy {TRUE, FALSE} 
@attribute play {yes, no} 
  
@data 
sunny,hot,high,FALSE,no 
sunny,hot,high,TRUE,no 
overcast,hot,high,FALSE,yes 
rainy,mild,high,FALSE,yes 
rainy,cool,normal,FALSE,yes 
rainy,cool,normal,TRUE,no 
overcast,cool,normal,TRUE,yes 
sunny,mild,high,FALSE,no 
sunny,cool,normal,FALSE,yes 
rainy,mild,normal,FALSE,yes 
sunny,mild,normal,TRUE,yes 
overcast,mild,high,TRUE,yes 
overcast,hot,normal,FALSE,yes 
rainy,mild,high,TRUE,no

程序代码:

package com.dfsj;
import java.io.BufferedReader; 
import java.io.File; 
import java.io.FileReader; 
import java.io.FileWriter; 
import java.io.IOException; 
import java.util.ArrayList; 
import java.util.Iterator; 
import java.util.LinkedList; 
import java.util.List; 
import java.util.regex.Matcher; 
import java.util.regex.Pattern; 
  
import org.dom4j.Document; 
import org.dom4j.DocumentHelper; 
import org.dom4j.Element; 
import org.dom4j.io.OutputFormat; 
import org.dom4j.io.XMLWriter; 
  
public class ID3 { 
    private ArrayList<String> attribute = new ArrayList<String>(); // 存储属性的名称 
    private ArrayList<ArrayList<String>> attributevalue = new ArrayList<ArrayList<String>>(); // 存储每个属性的取值 
    private ArrayList<String[]> data = new ArrayList<String[]>();; // 原始数据 
    int decatt; // 决策变量在属性集中的索引 
    public static final String patternString = "@attribute(.*)[{](.*?)[}]"; 
  
    Document xmldoc; 
    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("/home/orisun/test/weather.nominal.arff")); 
        inst.setDec("play"); 
        LinkedList<Integer> ll=new LinkedList<Integer>(); 
        for(int i=0;i<inst.attribute.size();i++){ 
            if(i!=inst.decatt) 
                ll.add(i); 
        } 
        ArrayList<Integer> al=new ArrayList<Integer>(); 
        for(int i=0;i<inst.data.size();i++){ 
            al.add(i); 
        } 
        inst.buildDT("DecisionTree", "null", al, ll); 
        inst.writeXML("/home/orisun/test/dt.xml"); 
        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 = Pattern.compile(patternString); 
            while ((line = br.readLine()) != null) { 
                Matcher matcher = pattern.matcher(line); 
                if (matcher.find()) { 
                    attribute.add(matcher.group(1).trim()); 
                    String[] values = matcher.group(2).split(","); 
                    ArrayList<String> al = new ArrayList<String>(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; 
                        String[] row = line.split(","); 
                        data.add(row); 
                    } 
                } else { 
                    continue; 
                } 
            } 
            br.close(); 
        } catch (IOException e1) { 
            e1.printStackTrace(); 
        } 
    } 
  
    //设置决策变量 
    public void setDec(int n) { 
        if (n < 0 || n >= attribute.size()) { 
            System.err.println("决策变量指定错误。"); 
            System.exit(2); 
        } 
        decatt = n; 
    } 
    public void setDec(String name) { 
        int n = attribute.indexOf(name); 
        setDec(n); 
    } 
  
    //给一个样本(数组中是各种情况的计数),计算它的熵 
    public double getEntropy(int[] arr) { 
        double entropy = 0.0; 
        int sum = 0; 
        for (int i = 0; i < arr.length; i++) { 
            entropy -= arr[i] * Math.log(arr[i]+Double.MIN_VALUE)/Math.log(2); 
            sum += arr[i]; 
        } 
        entropy += sum * Math.log(sum+Double.MIN_VALUE)/Math.log(2); 
        entropy /= sum; 
        return entropy; 
    } 
  
    //给一个样本数组及样本的算术和,计算它的熵 
    public double getEntropy(int[] arr, int sum) { 
        double entropy = 0.0; 
        for (int i = 0; i < arr.length; i++) { 
            entropy -= arr[i] * Math.log(arr[i]+Double.MIN_VALUE)/Math.log(2); 
        } 
        entropy += sum * Math.log(sum+Double.MIN_VALUE)/Math.log(2); 
        entropy /= sum; 
        return entropy; 
    } 
  
    public boolean infoPure(ArrayList<Integer> 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 double calNodeEntropy(ArrayList<Integer> subset, int index) { 
        int sum = subset.size(); 
        double entropy = 0.0; 
        int[][] info = new int[attributevalue.get(index).size()][]; 
        for (int i = 0; i < info.length; i++) 
            info[i] = new int[attributevalue.get(decatt).size()]; 
        int[] count = new int[attributevalue.get(index).size()]; 
        for (int i = 0; i < sum; i++) { 
            int n = subset.get(i); 
            String nodevalue = data.get(n)[index]; 
            int nodeind = attributevalue.get(index).indexOf(nodevalue); 
            count[nodeind]++; 
            String decvalue = data.get(n)[decatt]; 
            int decind = attributevalue.get(decatt).indexOf(decvalue); 
            info[nodeind][decind]++; 
        } 
        for (int i = 0; i < info.length; i++) { 
            entropy += getEntropy(info[i]) * count[i] / sum; 
        } 
        return entropy; 
    } 
  
    // 构建决策树 
    public void buildDT(String name, String value, ArrayList<Integer> subset, 
            LinkedList<Integer> selatt) { 
        Element ele = null; 
        @SuppressWarnings("unchecked") 
        List<Element> list = root.selectNodes("//"+name); 
        Iterator<Element> iter=list.iterator(); 
        while(iter.hasNext()){ 
            ele=iter.next(); 
            if(ele.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 < minEntropy) { 
                minIndex = selatt.get(i); 
                minEntropy = entropy; 
            } 
        } 
        String nodeName = attribute.get(minIndex); 
        selatt.remove(new Integer(minIndex)); 
        ArrayList<String> attvalues = attributevalue.get(minIndex); 
        for (String val : attvalues) { 
            ele.addElement(nodeName).addAttribute("value", val); 
            ArrayList<Integer> al = new ArrayList<Integer>(); 
            for (int 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()); 
        } 
    } 
}

 

最终生成的文件如下:

<?xml version="1.0" encoding="UTF-8"?> 
  
<root> 
  <DecisionTree value="null"> 
    <outlook value="sunny"> 
      <humidity value="high">no</humidity> 
      <humidity value="normal">yes</humidity> 
    </outlook> 
    <outlook value="overcast">yes</outlook> 
    <outlook value="rainy"> 
      <windy value="TRUE">no</windy> 
      <windy value="FALSE">yes</windy> 
    </outlook> 
  </DecisionTree> 
</root>

 

用图形象地表示就是:

 

 

 

 

本文转载自:http://www.cnblogs.com/zhangchaoyang/articles/2196631.html

共有 人打赏支持
东方神剑

东方神剑

粉丝 64
博文 126
码字总数 93166
作品 0
朝阳
程序员
加载中

评论(8)

niuxiao
niuxiao
你好,我用这个算法套在了另外一个决策案例中,发现如果测试数据中的决策结果不一样就会报数组越界错误,这是我的arff文件的部分内容,现在给出的数据用程序跑就会出现这个错误,请教一下是什么原因
@attribute adress {重庆,宜昌,武汉,厦门,中山,广州,深圳,南京,苏州,成都,杭州,上海,西藏,新疆}
@attribute store {CL餐厅,DL餐厅,OP餐厅,OC餐厅,DO餐厅,MC餐厅,MQ餐厅}
@attribute dish {薯条,可乐,鸡肉汉堡,牛肉汉堡,鱼肉汉堡,蟹肉汉堡,冰淇淋,沙拉}
@attribute remark {大薯,大杯,中杯,买二送一,单买,巧克力味,香芋味,香蕉味,蓝莓味,草莓味,中薯,多加酱}
@attribute month {1,2,3,4,5,6,7,8,9,10,11,12}

@data
重庆,CL餐厅,薯条,大薯,2
宜昌,CL餐厅,可乐,大杯,2
深圳,OP餐厅,冰淇淋,巧克力味,1
深圳,CL餐厅,冰淇淋,巧克力味,1
亚洲超人小俊俊
亚洲超人小俊俊
神剑你好,我们在集成学习中,常用的训练基分类器的方法有那些啊?我仅知道用决策树算法训练基分类器,并且已经实现了算法。但目前集成学习中主流的训练基分类器的算法是那些,还望赐教
东方神剑
东方神剑

引用来自“可爱的小芸12”的评论

你好,我第一次使用arff文件与Xml文件。我在Eclipse里建立了一个file,然后将其命名为test.arrf。38行的inst.readARFF()时,使用了绝对路径,但是运行Java文件,显示数组越界:-1。50行的inst.writeXM(),我写了一个xml文件,但是运行完程序后,在我所写路径下并未生成xml文件,你可以帮帮我吗?谢谢。
请确认你复制的arff文件每行末尾是否多了一个空格,把每行最好多余的空格删除掉即可
可爱的小芸12
可爱的小芸12
你好,我第一次使用arff文件与Xml文件。我在Eclipse里建立了一个file,然后将其命名为test.arrf。38行的inst.readARFF()时,使用了绝对路径,但是运行Java文件,显示数组越界:-1。50行的inst.writeXM(),我写了一个xml文件,但是运行完程序后,在我所写路径下并未生成xml文件,你可以帮帮我吗?谢谢。
东方神剑
东方神剑

引用来自“亚洲超人小俊俊”的评论

文章很好,给了我们初学者很大的帮助。但是决策树在面临叶子节点不纯的时候是怎么处理的呢,请问老师您怎么解决?

引用来自“东方神剑”的评论

你好,首先说明我不是什么老师啊,我是刚毕业没多久的学生而已,不用客气。关于叶子节点不纯的处理,最直接的办法就是看看叶子节点中占比重最多的类是什么,直白的说就是少数服从多数。也建议你再看一看C4.5算法,关于过拟合的优化等,比如剪枝

引用来自“亚洲超人小俊俊”的评论

东方神剑你好,我最近在研究adaboost算法。算法里用的单层决策树的弱分类器,不知道你有没有研究。单层决策树具体是什么样的,网上没看到什么资料。望指点!
你好,我不太清楚你到底想问什么,你是对单层决策树这个概念不清楚还是对于单层决策树的构建过程或者说为什么要构建单层决策树不清楚。对于单层决策树的样子就是一个根节点下面两个叶子节点,仅此而已,单层决策树也叫决策树桩,它仅基于单个特征做决策。而关于adaboost的原理就是三个臭皮匠赛过诸葛亮,就是通过多个弱分类器组合,而弱分类器你可以使用单层决策树,当然其他分类算法如SVM也是可以的。比如一个数据利用5种不同的分类算法,其中4种说它是正例,那它就是正例,而这5种分类算法都叫弱分类器。如果你是对单层决策树的构建过程不清楚可以参考《机器学习实战Python版》第七章内容,如果有问题,可随时再联系我,希望对你有用
亚洲超人小俊俊
亚洲超人小俊俊

引用来自“亚洲超人小俊俊”的评论

文章很好,给了我们初学者很大的帮助。但是决策树在面临叶子节点不纯的时候是怎么处理的呢,请问老师您怎么解决?

引用来自“东方神剑”的评论

你好,首先说明我不是什么老师啊,我是刚毕业没多久的学生而已,不用客气。关于叶子节点不纯的处理,最直接的办法就是看看叶子节点中占比重最多的类是什么,直白的说就是少数服从多数。也建议你再看一看C4.5算法,关于过拟合的优化等,比如剪枝
东方神剑你好,我最近在研究adaboost算法。算法里用的单层决策树的弱分类器,不知道你有没有研究。单层决策树具体是什么样的,网上没看到什么资料。望指点!
东方神剑
东方神剑

引用来自“亚洲超人小俊俊”的评论

文章很好,给了我们初学者很大的帮助。但是决策树在面临叶子节点不纯的时候是怎么处理的呢,请问老师您怎么解决?
你好,首先说明我不是什么老师啊,我是刚毕业没多久的学生而已,不用客气。关于叶子节点不纯的处理,最直接的办法就是看看叶子节点中占比重最多的类是什么,直白的说就是少数服从多数。也建议你再看一看C4.5算法,关于过拟合的优化等,比如剪枝
亚洲超人小俊俊
亚洲超人小俊俊
文章很好,给了我们初学者很大的帮助。但是决策树在面临叶子节点不纯的时候是怎么处理的呢,请问老师您怎么解决?
决策树 学习笔记

基本概念 算法杂货铺的这篇介绍说的比较生动详细 决策树算法原理(上) 对ID3、C4.5 的算法思想做了总结。介绍了两种算法的过程,以及优缺点。 ID3 构造决策树是基于信息增益最大的情况进行。...

喵_十八
2017/12/04
0
0
明故为知/DataMining

数据挖掘 English 数据挖掘算法软件。 开发环境 Eclipse 4.2.2 (Juno) JDK 1.8 代码结构 algorithm -- 算法集,可自由加入算法 ID3 -- ID3 实现 Kmeans -- K-means 实现 data -- 数据结构 Da...

明故为知
2017/07/31
0
0
机器学习之决策树(Decision Tree)及其Python代码实现

  决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象,而每个分叉路径则代表的某个可能的属性值,而每个叶结点则对应从根节点到该叶节点所经...

大黄有故事
2017/02/10
0
0
ID3算法编程怎么得到决策树

@一只小桃子 你好,想跟你请教个问题:你好,我想问下文章《R语言实现决策树ID3算法》里面的ID3算法最后R语言编程是怎么整理得到树结构的?

spinning
2015/04/12
119
1
决策树的python实现

本文结构: 是什么? 有什么算法? 数学原理? 编码实现算法? 1. 是什么? 简单地理解,就是根据一些 feature 进行分类,每个节点提一个问题,通过判断,将数据分为几类,再继续提问。这些问...

aliceyangxi1987
2017/05/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

聊聊redisson的DelayedQueue

序 本文主要研究一下redisson的DelayedQueue maven <dependency><groupId>org.redisson</groupId><artifactId>redisson</artifactId><version>3.8.1</version></dependenc......

go4it
23分钟前
1
0
一张图看懂JVM

JVM结构示意图 JVM总体概述 JVM总体上是由类装载子系统(ClassLoader)、运行时数据区、执行引擎、内存回收这四个部分组成。其中我们最为关注的运行时数据区,也就是JVM的内存部分则是由方法...

小致dad
24分钟前
0
0
安全管理标准

安全生产严重等级分类: 故障频次: 风险等级矩阵:

乔老哥
55分钟前
2
0
数据结构“树”的相关微视频

今天在腾讯视频上闲逛,然後发现一个叫“岚人”的用户上传了几段小视频,基本上都在5分钟以内,讲解了关于树的一些结构和算法。零代码,非常适合初学者入门。不过,对于老鸟来说,这也是非常...

Iridium
今天
1
0
10-利用思维导图梳理JavaSE-Java 集合

10-利用思维导图梳理JavaSE-Java 集合 主要内容 1.Collection接口 2.Set接口 2.1.Set接口概述 2.2.HashSet类 2.3.TreeSet类 2.4.SortedSet接口 3.List接口 3.1.List接口概述 3.2.ArrayList类...

飞鱼说编程
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部