决策树之ID3算法（转）

今天，我来讲解的是决策树。对于决策树来说，主要有两种算法：ID3算法和C4.5算法。C4.5算法是

对ID3算法的改进。今天主要先讲ID3算法，之后会讲C4.5算法和随机森林等。

Contents

1. 决策树的基本认识

2. ID3算法介绍

3. 信息熵与信息增益

4. Java实现

1. 决策树的基本认识

决策树是一种依托决策而建立起来的一种树。在机器学习中，决策树是一种预测模型，代表的是一种对

象属性与对象值之间的一种映射关系，每一个节点代表某个对象，树中的每一个分叉路径代表某个可能

的属性值，而每一个叶子节点则对应从根节点到该叶子节点所经历的路径所表示的对象的值。决策树仅

有单一输出，如果有多个输出，可以分别建立独立的决策树以处理不同的输出。接下来讲解ID3算法。

2. ID3算法介绍

ID3算法是决策树的一种，它是基于奥卡姆剃刀原理的，即用尽量用较少的东西做更多的事。ID3算法，

即Iterative Dichotomiser 3，迭代二叉树3代，是Ross Quinlan发明的一种决策树算法，这个

算法的基础就是上面提到的奥卡姆剃刀原理，越是小型的决策树越优于大的决策树，尽管如此，也不总

是生成最小的树型结构，而是一个启发式算法。

在信息论中，期望信息越小，那么信息增益就越大，从而纯度就越高。ID3算法的核心思想就是以信息

增益来度量属性的选择，选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍

历可能的决策空间。

3. 信息熵与信息增益

在信息增益中，重要性的衡量标准就是看特征能够为分类系统带来多少信息，带来的信息越多，该特征越

重要。在认识信息增益之前，先来看看信息熵的定义

熵这个概念最早起源于物理学，在物理学中是用来度量一个热力学系统的无序程度，而在信息学里面，熵

是对不确定性的度量。在1948年，香农引入了信息熵，将其定义为离散随机事件出现的概率，一个系统越

是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。所以信息熵可以被认为是系统有序

化程度的一个度量。

假如一个随机变量决策树之ID3算法（转）的取值为，每一种取到的概率分别是，那么

决策树之ID3算法（转）的熵定义为

决策树之ID3算法（转）

意思是一个变量的变化情况可能越多，那么它携带的信息量就越大。

对于分类系统来说，类别决策树之ID3算法（转）是变量，它的取值是，而每一个类别出现的概率分别是

决策树之ID3算法（转）

而这里的决策树之ID3算法（转）就是类别的总数，此时分类系统的熵就可以表示为

决策树之ID3算法（转）

以上就是信息熵的定义，接下来介绍信息增益。

信息增益是针对一个一个特征而言的，就是看一个特征决策树之ID3算法（转），系统有它和没有它时的信息量各是多少，两者

的差值就是这个特征给系统带来的信息量，即信息增益。

接下来以天气预报的例子来说明。下面是描述天气数据表，学习目标是play或者not play。

决策树之ID3算法（转）

可以看出，一共14个样例，包括9个正例和5个负例。那么当前信息的熵计算如下

决策树之ID3算法（转）

在决策树分类问题中，信息增益就是决策树在进行属性选择划分前和划分后信息的差值。假设利用

属性Outlook来分类，那么如下图

决策树之ID3算法（转）

划分后，数据被分为三部分了，那么各个分支的信息熵计算如下

决策树之ID3算法（转）

那么划分后的信息熵为

决策树之ID3算法（转）

决策树之ID3算法（转）代表在特征属性的条件下样本的条件熵。那么最终得到特征属性带来的信息增益为

决策树之ID3算法（转）

信息增益的计算公式如下

决策树之ID3算法（转）

其中决策树之ID3算法（转）为全部样本集合，是属性所有取值的集合，是的其中一个属性值，是中属性的

值为决策树之ID3算法（转）的样例集合，为中所含样例数。

在决策树的每一个非叶子结点划分之前，先计算每一个属性所带来的信息增益，选择最大信息增益的属性来划

分，因为信息增益越大，区分样本的能力就越强，越具有代表性，很显然这是一种自顶向下的贪心策略。以上

就是ID3算法的核心思想。

4.ID3 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

程序代码：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

package 
dt;
 

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>

用图形象地表示就是：

决策树之ID3算法（转）

决策树之ID3算法（转）

相关推荐