《分类挖掘算法》由会员分享，可在线阅读，更多相关《分类挖掘算法（3页珍藏版）》请在金锄头文库上搜索。
1、实验三 分类挖掘算法（C4.5）、实验目的1、理解分类2、掌握分类挖掘算法C4.53、为改进C4.5打下基础二、实验内容1、选定一个数据集（可以参考教学中使用的数据集）2、选择合适的实现环境和工具实现算法 C4.53、给出分类规则三、实验原理C4.5是机器学习算法中的另一个分类决策树算法，它是基于ID3算法进行改进后的一 种重要算法，相比于 ID3 算法，改进有如下几个要点：1）用信息增益率来选择属性。ID3选择属性用的是子树的信息增益，这里可以用很多方 法来定义信息，ID3使用的是熵（entropy,熵是一种不纯度度量准则），也就是熵的变化值， 而 C4.5 用的是信息增益率。2）在决策树构
2、造过程中进行剪枝，因为某些具有很少元素的结点可能会使构造的决策树 过适应（Overfitting）,如果不考虑这些结点可能会更好。3）对非离散数据也能处理。4）能够对不完整数据进行处理。信息增益计算公式：心归空需色心丄別讥 阴询血g）h）ut?42lu.ES（a）I I信息熵计算公式：minfo(D = - PilogAPi) i=l信息增益率公式：IGR(Exg) = IG/IV其中，IG就是前面的信息增益，IV计算公式如下：IVEx a）=-刀 1王 $ E刎他加就王卫）=讨|讨略2 （x G Exvalue（x,a）=百|UEt?fZ/UES（Z）简化公式如下：H（V）= 戸他如?仙）其
3、中，V表示属性集合A中的一个属性的全部取值。四、实验要求1、数据集具有一定的代表性，可以使用数据库技术管理2、实现界面友好3、提交实验报告：实验题目、目的、数据集描述、实验环境、过程、结果和分析等五、实验步骤1、毕业生就业信息数据集，如图1 所示：学号性别学主干部综合城绩堆业论文it业愫况200004113170-7?优已2000041135是中已2000041201黑60-9不圧需未2QOQ04 202男量mo良已3000041303中已200004)204黒不是未2000041205立良已2QOQO4HD&是(5 叶50克已IQOQD4131D立是7(WS甲200QD412U不是已2000
4、04121530-39巫格已200004)216是T29良己20000412237G-7P及洛来200004131960-69已2000041320男星70-70灵已1C00041331不是7(W9未2000041322男良1000041313文70-74)良已200004 B24禺不是丁0不及2000MB2S7(W920QQD4I326立忧已2000041317是6(WS已图 1 毕业生就业信息数据集 图中数据是经过预处理的数据集，从表中我们可以得到类标号属性“就业情况”有 2 个不同的值（“已”，“未”），因此有2 个不同的类。其中对应于类值“已”有14 个样本 类值“未”有 8 个样本。
5、2、算法流程假设用S代表当前样本集，当前候选属性集用A表示，则C4.5算法的伪代码如下： 算法：Generate_decision_tree由给定的训练数据产生一棵决策树 输入：训练样本samples；候选属性的集合attributelist 输出：一棵决策树（1）创建根节点N；（2）IF S都属于同一类C,则返回N为叶节点，标记为类C；（3）IF attributelist为空或S中所剩的样本数少于某给定值（4）则返回N为叶节点，标记N为S中出现最多的类；（5）FOR each attributelist 中的属性（6）计算信息增益率 information gain ratio；（7）N的
6、测试属性test.attribute = attributelist具有最高信息增益率的属性；(8) IF测试属性为连续型(9) 则找到该属性的分割阈值；(10) For each由节点N 个新的叶子节点(11) If该叶子节点对应的样本子集S为空(12) 则分裂此叶子节点生成新叶节点，将其标记为S中出现最多的类(13) Else在该叶子节点上执行C4.5f0rmtree(S, S.attributelist),继续对它分裂；(14) 计算每个节点的分类错误，进行剪枝。3、程序实现PrintTree(T);/Display entire decision tree TShow(T, Sh);/
7、 Display the tree T with offset ShShowBranch(Sh, T, v);/ Print a node T with offset Sh, branch value v, and continue short MaxLine(St);/ Find the maximum single line size for non-leaf subtree St. ndent(Sh, Mark);/ Indent Sh columnsSaveTree(T, Extension);/ Save entire decision tree T in file with ext
8、ension ExtensionOutTree(T);/ Save tree T as charactersTree GetTree(Extension);/ Retrieve entire decision tree with extension ExtensionTree InTree();/Retrieve tree from saved charactersStreamOut(s, n);/ Stream characters to/from file TRf from/to an address ReleaseTree(Node);/ Free up space taken up b
9、y tree NodeTree Leaf(ClassFreq, NodeClass, Cases, Errors);/ Construct a leaf in a given node Sprout(Node, Branches);/ Insert branches in a nodeTreeSize(Node);/ Count the nodes in a treeTree CopyTree(T);/ Return a copy of tree TSaveDiscreteNames();/Save attribute values read with discrete N RecoverDiscreteNames();/Recover attribute values read with discrete N六、实验结果如图 2 所示：图 2 毕业生就业情况判定树最终得到的决策树，
