实验二 分类挖掘算法

1、实验二 分类挖掘算法(ID3)一、实验目的1、理解分类2、掌握分类挖掘算法ID33、为改进ID3打下基础二、实验内容1、选定一个数据集(可以参考教学中使用的数据集)2、选择合适的实现环境和工具实现算法ID33、给出分类规则三、实验原理决策树是一种最常见的分类算法，它包含有很多不同的变种，ID3算法是其中最简单的 一种。ID3算法中最主要的部分就是信息熵和信息增益的计算。信息熵的计算公式如下。而玦的可)= -云F1理汽妇信息增益的计算公式为：Gai 威 S. J) = E* 叮(5)一 三 U&igpj其中P(ui)为类别ui在样本S中出现的概率，A是样本的属性，Value(A)是属性A所有 取

2、值的集合，v是A得其中一个属性值。Sv是S中A的值为v的样例集合。ID3算法的流程就是在属性集A中寻找信息增益值最大的属性，作为根节点，按照根节 点属性的取值将样本集合分成几个子集，将此属性从属性集中去掉，在每个子集中选择信息 增益值最大的属性，作为当前子集的根节点，上层集合的根节点的子节点，如此循环递归， 如果得到的子集中所有的样本属于一个类别，则递归停止。四、实验要求1、数据集具有一定的代表性，可以使用数据库技术管理2、实现界面友好3、提交实验报告：实验题目、目的、数据集描述、实验环境、过程、结果和分析等。五、实验步骤1、所采用的数据集，如图1所示：收入范围煌险促带信川曰呆隆q龄40-50

3、K否453040K是仲k404J-50K杏杏yj423O-4OK是w43506晾fik382CI-3OKfi有女5530-40K是EJJ*20-3OK否w27否43Ka杏44(1- 50K是4320-30k否女29M-WK是女39而一 5OK行55a是192、具体步骤构造决策树的方法是采用自上而下的递归构造，其思路是：1）以代表训练样本的单个结点开始建树（步骤1）。2）如果样本都在同一类，则该结点成为树叶，并用该类标记（步骤2和3）。3）否则，算法使用称为信息增益的机遇熵的度量为启发信息，选择能最好地将样本分类 的属性（步骤6）。该属性成为该结点的“测试”或“判定”属性（步骤7）。值得注意的是

4、，在 这类算法中，所有的属性都是分类的，即取离散值的。连续值的属性必须离散化。4）对测试属性的每个已知的值，创建一个分支，并据此划分样本（步骤810）。5）算法使用同样的过程，递归地形成每个划分上的样本决策树。一旦一个属性出现在一 个结点上，就不必考虑该结点的任何后代（步骤13）。6）递归划分步骤，当下列条件之一成立时停止：给定结点的所有样本属于同一类（步骤2和3）。没有剩余属性可以用来进一步划分样本（步骤4）。在此情况下，采用多数表决（步 骤5）。这涉及将给定的结点转换成树叶，并用samples中的多数所在类别标记它。换一种方 式，可以存放结点样本的类分布。分支test_attribute=

5、ai没有样本。在这种情况下，以samples中的多数类创建一个树叶 （步骤12）。Decision_Tree（samples,attribute_list）输入由离散值属性描述的训练样本集samples;候选属性集合attribute_list。输出一棵决策树。1）创建节点N；2）if samples 都在同一类 C 中 then3）返回N作为叶节点，以类C标记；4）if attribute_list 为空 then5）返回N作为叶节点，以samples中最普遍的类标记；多数表决6）选择attribute list中具有最高信息增益的属性test attribute;以 test_attrib

6、ute 标记节点 N；for each test_attribute 的已知值 v划分 samples由节点N分出一个对应test_attribute=v的分支；令Sv为samples中test_attribute=v的样本集合；一个划分块if Sv 为空 then加上一个叶节点，以samples中最普遍的类标记；else 加入一个由 Decision_Tree(Sv,attribute_list-test_attribute)返回节点值六、实验结果1、具体输出结果如图1、2所示：(termiitated TestDecisi onTree Java Appli cation C : Frc

7、请输入候选属性 age income stucient. crediating请输入训练数据 yout.li high no fair nc yout.li high no excellent. no inidd 1 e_aged high noyessenior inediiim no fair yea senior low yes fair yes senior low yes excel lent, no inidd 1 eaged low yes exceHeinz yes yout.h rtiedituti no fair no yout.li lotij yes fair yes

8、senior inediiim yes fair yes yo ut-li rned i tun ye a excel le nt. ye a inidd 1 e_aged rnediinn nc excel lent yes inidd 1 e_aged high yes fair yes senior inediiiiri no excel lent, no图1n；5iiie : agenude rules : youth iniddle_agecl senior siz已 of childr已n:3child 1 of no cl 已 目g已： n；3iri 已：st. nd 已 ntn

9、ude cules: ( no yes size of childrenschild 1 f nocie st.uclent: n；5Ltne : nonude rules : 已盘 node !child 2 of no de student: n；zune : yesnode rules: leaf node!child 2 of nocle age : n；3itie : yesnocl已 rul已 已盘 node !child 3 u f no de age : n；sitie : crecli t_rat i ngnode rules: ralr exce1 lent )size of childrenschild 1 f no cl 已 c