第1页 / 共23页
第2页 / 共23页
第3页 / 共23页
第4页 / 共23页
第5页 / 共23页
第6页 / 共23页
第7页 / 共23页
第8页 / 共23页
决策树ID3算法实验报告广工（附源码java）.doc
一、实验内容
已知：UCI标准数据集Car-Evaluation，定义了汽车性价比的4 个类别；
求：用ID3算法建立Car-Evaluation的属性描述决策树
Car-Evaluation训练数据集文件：
二、实验设计（原理分析及流程）
实验课程名称：__人工智能_
实验项目名称
决策树 ID3 算法
实 验 者
毛毛
专业班级
实验日期
一、实验内容
实验成绩
学
号
已知：UCI 标准数据集 Car-Evaluation，定义了汽车性价比的 4 个类别；
求：用 ID3 算法建立 Car-Evaluation 的属性描述决策树
Car-Evaluation 训练数据集文件：
1.
2.
car_databases.pdf
car_evalution-databases.pdf
二、实验设计（原理分析及流程）
原理
ID3 算法采用一种自顶向下，贪婪的搜索算法。ID3 搜索的假设空间是可能的决策树的集
合，搜索目的是构造与训练数据一致的决策树，搜索策略是爬山法，在构造决策树时从简单到
复杂，用信息熵作为爬山法的评价函数。算法核心在于决策树各级节点属性的选择，用信息增
益作为属性选择的标准，使得在每个非叶子节点进行测试时能获得关于被测数据最大的类别信
息，使得该属性将数据集划分为子集后系统的熵值最小。
流程
数据集输入，属性列表
对子类条件熵
0 的 样 本 重 新
组合新的集合
属性条件熵计算
遍 历 所 有
属性，计算
每 一 个 属
性 的 条 件
熵
对 比 所 有
属 性 的 条
件 熵 ， 选
择 最 优 的
分类属性
用 所 选 属 性 对 样 本
进行分类，并从属性
列表中删除该属性
画出决策分支
否
最优条件熵=0
是
结束
三、实验代码及数据记录
1.代码
Util 类
package id3;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class Util
{
// 获得列号为index的属性取值和该取值下的数量
public static Map getSubMap(
ArrayList> dataSet, int index)
// key用于存放列号为index的属性取值，value用于存放对应取值的数量
Map subMap = new HashMap();
for (ArrayList data : dataSet)
{
// 取出列号为index的属性，可包括目标属性
String lable = data.get(index);
// 如果属性取值首次出现，将value置为1，否则覆盖原有key,值加1
if (subMap.get(lable) == null)
{
subMap.put(lable, 1);
// 获取数据集中的目标属性集合，即evaluation取值的集合
public static ArrayList getClassList(
ArrayList> dataSet)
ArrayList classList = new ArrayList();
int length = dataSet.get(0).size();
for (ArrayList data : dataSet)
{
String label = data.get(length - 1);
classList.add(label);
}
return classList;
{
}
{
}
else
{
}
}
return subMap;
subMap.put(lable, subMap.get(lable) + 1);
// 求信息熵
public static double getEntropy(ArrayList>
dataSet,
int index)
int total = dataSet.size();
double entropy = 0;
// 获得目标属性的取值及对应数量，此时index为evaluation的列号
Map subMap = getSubMap(dataSet, index);
for (Map.Entry entry : subMap.entrySet())
{
double temp = entry.getValue() * 1.0 / total;
entropy += temp * (Math.log(temp) / Math.log(2));
}
return -entropy;
}
{
}
{
息熵
// 获取信息增益最大的属性，返回该属性的列号
public static String
bestFeatureSplit(ArrayList> dataSet,
ArrayList featureList)
int length = dataSet.get(0).size();
double totalEntropy = getEntropy(dataSet, length - 1); // 信
int featureNum = length - 1; // 属性个数，不包括目标属性
int index = -1; // 最大信息增益的属性列号
double maxInfoGain = -1; // 最大信息增益
for (int i = 0; i < featureNum; i++)
{
Map map = getSubMap(dataSet, i); // 获得
该属性下的集合
double entropySum = 0;
for (Map.Entry entry : map.entrySet())
{
Map subMap = new HashMap();
/*
* 某属性不同取值下，目标属性的不同取值及对应数量。如属性safety
* 目标属性evaluation的取值为unacc ，acc，good，vgood的数
的取值分别为low，med，high时，
量
*/
for (ArrayList data : dataSet)
{
if (data.get(i).equals(entry.getKey()))
{
if (subMap.get(data.get(length - 1)) == null)
{
subMap.put(data.get(length - 1), 1);
}
else
{
}
}
}
subMap.put(data.get(length - 1),
subMap.get(data.get(length - 1)) + 1);
double x = 0; // 某属性下的信息熵
for (Map.Entry subEntry :
double temp = subEntry.getValue() * 1.0 /
x += temp * (Math.log(temp) / Math.log(2));
subMap.entrySet())
entry.getValue();
{
}
entropySum += -x * (entry.getValue()) / dataSet.size();
// 条件熵
}
entropySum = totalEntropy - entropySum; // 信息增益 = 信息
熵 - 条件熵
if (entropySum > maxInfoGain)
{
index = i;
maxInfoGain = entropySum;
}
}
return featureList.get(index);
}
// 获得属性为value的新的所有数据集
public static ArrayList> splitDataSet(
ArrayList> dataSet, int index, String
value)
{
ArrayList> subDataSet = new
ArrayList>();
for (ArrayList data : dataSet)
{
if (data.get(index).equals(value))
{
ArrayList temp = new ArrayList();
for (int i = 0; i < data.size(); i++)
{
// 去除value属性取值
if (i != index)
{
temp.add(data.get(i));
}
}
subDataSet.add(temp);
}
}
return subDataSet;
}
list)
{
// 用于判断目标属性是否是同一取值，即key是否只有一种情况
public static Map arrayToMap(ArrayList
Map map = new HashMap();
for (String word : list)
{
// 如果目标属性取值首次出现，将value置为1，否则覆盖原有key,值加1
if (map.get(word) == null)
{
map.put(word, 1);
}
else
{
}
}
return map;
map.put(word, map.get(word) + 1);
// 获得列号为index所有存在的属性取值
public static Set getValueFromDataSet(
ArrayList> dataSet, int index)
ArrayList values = new ArrayList();
for (ArrayList data : dataSet)
{
values.add(data.get(index));
}
Set set = new HashSet();
for (String value : values)
{
set.add(value); // 去除重复的属性取值
}
return set;
}
{
}
src)
{
}
}
// 拷贝ArrayList数组并返回
public static ArrayList copyArrayList(ArrayList
ArrayList dest = new ArrayList();
for (String s : src)
{
dest.add(s);
}
return dest;
ID3 类
package id3;
import id3.Util;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Set;
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 static ArrayList> dataSet; // 数据集
private static ArrayList featureList; // 属性集
public static void main(String[] args)
{
dataSet = loadDataFromFile("car_evalution-databases.txt");
featureList = initFeatureList();
Element root = DocumentHelper.createElement("DecisionTree");
Document document = DocumentHelper.createDocument(root);
createDTree(dataSet, featureList, root);
WriteDTreeToXML(document, "DTree.xml");
}
// ID3 算法构建决策树
private static void createDTree(ArrayList>
dataSet,
{
ArrayList featureList, Element e)
// 获取 dataSet 数据集中目标属性的集合
ArrayList labelList = Util.getClassList(dataSet);
if (Util.arrayToMap(labelList).size() == 1)
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
