数据挖掘实验2.

数据挖掘实验2——决策树分类数据挖掘实验2（30’）•实验目的：了解关联规则在数据挖掘中的应用，理解和掌握分类经典算法ID3ORC4.5算法的算法的基本原理和执行过程并完成程序设计。•实验内容：对给定数据集用ID3算法进行挖掘，生成相应的决策树并生成规则。对下面数据集进行挖掘：数据挖掘实验2（30’）•实验要求：可以用JAVA、C++或C语言实现。实验背景知识样本数据8决策树表示与例子•决策树（DecisionTree）的每个内部结点表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶结点代表类或类分布。树的最顶层结点是根结点。•buys_computer的决策树示意为什么以年龄作为根节点来划分？HowtoFindtheBestSplitB?YesNoNodeN3NodeN4A?YesNoNodeN1NodeN2BeforeSplitting:C0N10C1N11C0N20C1N21C0N30C1N31C0N40C1N41C0N00C1N01M0M1M2M3M4M12M34Gain=M0–M12vsM0–M34AlternativeSplittingCriteriabasedonINFO•Entropy(熵)atagivennodet:(NOTE:p(j|t)istherelativefrequencyofclassjatnodet).–Measureshomogeneityofanode.•Maximum(lognc)whenrecordsareequallydistributedamongallclassesimplyingleastinformation•Minimum(0.0)whenallrecordsbelongtooneclass,implyingmostinformationjtjptjptEntropy)|(log)|()(2ExamplesforcomputingEntropyC10C26C12C24C11C25P(C1)=0/6=0P(C2)=6/6=1Entropy=–0log20–1log21=–0–0=0P(C1)=1/6P(C2)=5/6Entropy=–(1/6)log2(1/6)–(5/6)log2(1/6)=0.65P(C1)=2/6P(C2)=4/6Entropy=–(2/6)log2(2/6)–(4/6)log2(4/6)=0.92jtjptjptEntropy)|(log)|()(2SplittingBasedonINFO...•InformationGain:•ParentNode,pissplitintokpartitions;•niisnumberofrecordsinpartitionikiisplitiEntropynnpEntropyGAIN1)()(SplittingBasedonINFO...–MeasuresReductioninEntropyachievedbecauseofthesplit.Choosethesplitthatachievesmostreduction(maximizesGAIN)–UsedinID3andC4.5–Disadvantage:Tendstoprefersplitsthatresultinlargenumberofpartitions,eachbeingsmallbutpure.kiisplitiEntropynnpEntropyGAIN1)()(小结•在决策树归纳方法中，通常使用信息增益方法来帮助确定生成每个结点时所应采用的合适属性。•这样就可以选择具有最高信息增益（熵减少的程度最大）的属性作为当前结点的测试属性，以便使对之后所划分获得的训练样本子集进行分类所需要信息最小。•注：对于人的理解来说，越是具体的信息（信息增加了），而熵越小。小结•也就是说，如果该属性导致具有最高的信息增益，那么对该属性进行当前（结点所含）样本集合划分，将会使得所产生的各样本子集中的“不同类别混合程度”降为最低（换句话说，就是越相互区分的开！）。•因此采用这样一种信息论方法将帮助有效减少对象分类所需要的次数，从而确保所产生的决策树最为简单，尽管不一定是最简单的。举例说明假设按年龄来划分Thisisthereasonwhychoose“age”asthesplitforpartitionthetrainingset!23ID3算法•ID3是Quinlan提出的一个著名决策树生成方法：–决策树中每一个非叶结点对应着一个非类别属性，树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。–每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。–采用信息增益来选择能够最好地将样本分类的属性。24ID3决策树生成算法描述ID3算法Generate_decision_tree(samples,attribute_list)/*决策树生成算法*/输入：训练样本samples，由离散值属性表示；候选属性的集合attribute_list。输出：一棵决策树。（1）创建结点N；（2）IFsamples都在同一个类CTHEN返回N作为叶结点，以类C标记；（3）IFattribute_list为空THEN返回N作为叶结点，标记为samples中最普通的类；//多数表决（4）选择attribute_list中具有最高信息增益的属性test_attribute；（5）标记结点N为test_attribute；（6）FOReachtest_attribute中的已知值ai由结点N长出一个条件为test_attribute=ai的分枝；（7）设si是samples中test_attribute=ai的样本的集合；//一个划分（8）IFsi为空THEN加上一个树叶，标记为samples中最普通的类；（9）ELSE加上一个由Generate_decision_tree(si，attribute_list-test_attribute)返回的结点；•决策树所表示的分类知识可以被抽取出来并可用”IF-THEN”分类规则形式加以表示。从决策树的根结点到任一个叶结点所形成的一条路径就构成了一条分类规则。•沿着决策树的一条路径所形成的属性-值对就构成了分类规则条件部分（”IF”部分）中的一个合取项，叶结点所标记的类别就构成了规则的结论内容（TEHN部分）。由判定树提取分类规则由判定树提取分类规则•”IF-THEN”分类规则表达方式易于被人理解，且当决策树较大时，IF-THEN规则表示形式的优势就更加突出。•示例：从决策树中抽取出分类规则。如图-所示的一个决策树，需要将其所表示的分类知识用IF-THEN分类规则形式描述出来，通过记录图-所示决策树中的每条从根结点到叶结点所形成的一条路径，可以得到以下分类规则，它们是：