数据挖掘实验.ppt

《数据挖掘实验.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、数据挖掘实验2——决策树分类数据挖掘实验2（30’）实验目的：了解关联规则在数据挖掘中的应用，理解和掌握分类经典算法ID3ORC4.5算法的算法的基本原理和执行过程并完成程序设计。实验内容：对给定数据集用ID3算法进行挖掘，生成相应的决策树并生成规则。对下面数据集进行挖掘：数据挖掘实验2（30’）实验要求：可以用JAVA、C++或C语言实现。实验背景知识样本数据决策树表示与例子决策树（DecisionTree）的每个内部结点表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶结点代表类或类分布。树的最顶层结点是根结点。buys_computer的决策树示意为什么以年龄作为根

2、节点来划分？8HowtoFindtheBestSplitB?YesNoNodeN3NodeN4A?YesNoNodeN1NodeN2BeforeSplitting:M0M1M2M3M4M12M34Gain=M0–M12vsM0–M34AlternativeSplittingCriteriabasedonINFOEntropy(熵)atagivennodet:(NOTE:p(j

3、t)istherelativefrequencyofclassjatnodet).Measureshomogeneityofanode.Maximum(lognc)whenrecordsareequallyd

4、istributedamongallclassesimplyingleastinformationMinimum(0.0)whenallrecordsbelongtooneclass,implyingmostinformationExamplesforcomputingEntropyP(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

5、)–(4/6)log2(4/6)=0.92SplittingBasedonINFO...InformationGain:ParentNode,pissplitintokpartitions;niisnumberofrecordsinpartitioniSplittingBasedonINFO...MeasuresReductioninEntropyachievedbecauseofthesplit.Choosethesplitthatachievesmostreduction(maximizesGAIN)UsedinID3andC4.5Disadvantage:Tendstopre

6、fersplitsthatresultinlargenumberofpartitions,eachbeingsmallbutpure.小结在决策树归纳方法中，通常使用信息增益方法来帮助确定生成每个结点时所应采用的合适属性。这样就可以选择具有最高信息增益（熵减少的程度最大）的属性作为当前结点的测试属性，以便使对之后所划分获得的训练样本子集进行分类所需要信息最小。注：对于人的理解来说，越是具体的信息（信息增加了），而熵越小。小结也就是说，如果该属性导致具有最高的信息增益，那么对该属性进行当前（结点所含）样本集合划分，将会使得所产生的各样本子集中的“不同类别混合程度”降为最低（换句话说，

7、就是越相互区分的开！）。因此采用这样一种信息论方法将帮助有效减少对象分类所需要的次数，从而确保所产生的决策树最为简单，尽管不一定是最简单的。举例说明假设按年龄来划分Thisisthereasonwhychoose“age”asthesplitforpartitionthetrainingset!ID3算法ID3是Quinlan提出的一个著名决策树生成方法：决策树中每一个非叶结点对应着一个非类别属性，树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。采用信息增益来选择能够最好地将样本分类

8、的属性。23ID3决策树生成算法描述ID3算法Generate_decision_tree(samples,attribute_list)/*决策树生成算法*/输入：训练样本samples，由离散值属性表示；候选属性的集合attribute_list。输出：一棵决策树。（1）创建结点N；（2）IFsamples都在同一个类CTHEN返回N作为叶结点，以类C标记；（3）IFattribute_list为空THEN返回N作为叶结点，标记为samples中最普通的类；//多