数据挖掘大作业

深圳大学研究生课程论文题目数据挖掘作业成绩专业软件工程课程名称、代码161023050015年级2015级姓名文成学号2150230509时间2015年12月任课教师黄哲学、王熙照一、期末课程试题针对一个离散属性二分类问题，表1给出了包含15个样本的训练集，其输入特征为A1，A2，A3，A4，A5，类标签为{1,2}。表2给出了包含2个测试样本的测试集，其分类未知。请回答下述问题：表1.训练样本SamplesA1A2A3A4A5Class113222222122123132111421223151312226212111712222282111119122232101321321111223112222111132321111412122215232131表2.测试样本SmaplesA1A2A3A4A5Class122111?211121?问题1.基于表1中给出的训练集，给出分别使用极小熵和极大熵选择扩展属性所生成的两棵决策树。然后给出你对树的大小的理解，并比较两种方法生成的决策树那个小，那个大。问题2.分别将两个决策树转换成两组IF-THEN规则。问题3.分别给出此两组规则对表2给出的两个测试样本的预测类别。问题4.那组结果你认为更可信？阐述你的理由。问题5.利用极小熵生成的决策树是否是“最小决策树”？给出你的证明或反例问题6.如果第一个属性A1为数值属性，其取值为[0,1]区间的实数，如表3、表4所示。此时如何处理？进一步请按你的方法基于表3给出的训练集产生一棵决策树（用极小熵选择扩展属性），并给出表4中的测试样本的预测类别。表3.训练样本SamplesA1A2A3A4A5Class10.603222220.901221230.353211140.151223150.503122260.951211170.202222280.121111190.6822232100.9532132110.0512231120.0222111130.0832111140.4521222150.1432131表4.测试样本SmaplesA1A2A3A4A5Class10.102111?20.981121?二、解答问题1基于表1中给出的训练集，给出分别使用极小熵和极大熵选择扩展属性所生成的两棵决策树。然后给出你对树的大小的理解，并比较两种方法生成的决策树那个小，那个大。答几个概念和求熵的方法：熵是数据中的不确定性、突发性或随机性的程度的度量。决策树是一个树结构。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。设数据集为D，类标号属性”Class”有两个属性：1和2,因此有不同的两类，令C1对应“1”，C2对应“2”，那么C1有8个样本，C2有7个样本，所以数据集D的熵为：下面分别计算按各个属性分裂后所得的诸子集的熵。1.若以“A1”作为分裂属值，则产生两个子集(因为该属性有两个不同的取值)，所以D按照属性“A1”划分的2个子集的熵的加权和为0.4327+0.2139=0.64662.如果用“A2”为分裂属性类似的：如果用“A2”为分裂属性0.2406+0.2163+0.4=0.85693.如果用“A3”为分裂属性0.1057+0.7839=0.88964.如果用“A4”为分裂属性0.4339+0.4652=0.89915.如果用“A5”为分裂属性0.2600+0+0.3237=0.5837根据以上结果得到使用极小熵生成的决策树：那么用A5作为分裂属性，所得信息增益最大。使用极大熵生成的决策树：那么用A4作为分裂属性，所得信息增益最小15个训练集465A5=1A5=2A5=351A4=1A4=2Class1Class2Class2212A2=1A2=2A2=3Class1Class211A1=1A1=2Class2Class115个训练集78A4=1A4=22A1=15A1=211A5=3Class1Class2Class126A3=1A3=2Class2312A2=2Class2Class2A2=112A1=1Class1A1=211A5=1Class2A5=3A5=1A2=3Class1从信息论知识中我们知道，期望信息越小，信息增益越大，从而纯度越高。构造决策树的核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。所以树的大小跟期望信息和信息增益有关。另一方面，构造决策树的关键步骤是分裂属性。分裂次数越多，树深度会变大，从而树就会更大。所以极大熵生成的决策树明显要比极小熵生成的决策树要高，树枝也比极小熵生成的决策树要多，但生成过程也更繁琐。问题2.分别将两个决策树转换成两组IF-THEN规则答使用极小熵生成的决策树转换成IF-THEN规则：规则1：IFA5=1andA4=1THENClass为1；规则2：IFA5=1andA4=2THENClass为2；规则3：IFA5=2THENClass为2；规则4：IFA5=3andA2=1THENClass为1；规则5：IFA5=3andA2=2THENClass为2；规则6：IFA5=3andA2=3andA1=2THENClass为1；规则7：IFA5=3andA2=3andA1=1THENClass为2；使用极大熵生成的决策树转换成IF-THEN规则：规则1：IFA4=1andA1=2THENClass为1；规则2：IFA4=1andA1=1andA5=1THENClass为1；规则3：IFA4=1andA1=1andA5=3THENClass为2；规则4：IFA4=2andA3=1THENClass为2；规则5：IFA4=2andA3=2andA2=2THENClass为2；规则6：IFA4=2andA3=2andA2=3THENClass为2；规则7：IFA4=2andA3=2andA2=1andA1=1THENClass为1；规则8：IFA4=2andA3=2andA2=1andA1=2andA5=1THENClass为2；规则9：IFA4=2andA3=2andA2=1andA1=2andA5=3THENClass为1；问题3.分别给出此两组规则对表2给出的两个测试样本的预测类别答极小熵构造的决策树对表2预测类别：SmaplesA1A2A3A4A5Class12211112111212极大熵构造的决策树对表2预测类别：SmaplesA1A2A3A4A5Class12211112111212问题4.那组结果你认为更可信？阐述你的理由。答当然，两组结果都一样的话最可信。极小熵生成的决策树更可信。因为变量的不确定性越大，熵也就越大，一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高，所以每次采用极小熵进行划分等同于按照不确定性最小划分，划分的过程更加准确，可靠。反之，采用极大熵划分所得到的决策树会比较高，不够直观。问题5.利用极小熵生成的决策树是否是“最小决策树”？给出你的证明或反例答猜想：利用极小熵生成的决策树是“最小决策树”。反证法：假设利用极小熵生成的不是最小决策树，那么一定存在一个更小的决策树，如果存在，那么极小熵生成的就不是最小决策树。反之，找不出比这个更小的树，那么利用极小熵生成的决策树就是“最小决策树”。证不出来。如果属性比较少可以用穷举法列举决策树，可以观察一下极小熵生成的是不是最小决策树。但属性多的话是一个NPhard问题，暂时不确定问题6.如果第一个属性A1为数值属性，其取值为[0,1]区间的实数，如表3、表4所示。此时如何处理？进一步请按你的方法基于表3给出的训练集产生一棵决策树（用极小熵选择扩展属性），并给出表4中的测试样本的预测类别。表3.训练样本SamplesA1A2A3A4A5Class10.603222220.901221230.353211140.151223150.503122260.951211170.202222280.121111190.6822232100.9532132110.0512231120.0222111130.0832111140.4521222150.1432131表4.测试样本SmaplesA1A2A3A4A5Class10.102111?20.981121?答将A1的概率值化成为在两个区间范围内[0-0.5]和[0.5-1]，也就是在[0-0.5]为1，(0.5-1]为2，则训练样本就化为了表(1)表(1)SamplesA1A2A3A4A5Class123222222122123132111411223151312226212111712222281111119222232102321321111223112122111131321111412122215132131接下来就是和上述一样的画出决策树了0.5875+0.2406=0.8281参考上面的结果得：0.85690.88960.89910.5837用极小熵选择扩展属性得到决策树：初始一用15个训练集。决策树转换成IF-THEN规则：规则1：IFA5=1andA1=1THENClass为1；规则2：IFA5=1andA1=2andA4=1THENClass为1；规则3：IFA5=1andA1=2andA4=2THENClass为2；规则4：IFA5=2THENClass为2；规则5：IFA5=3andA1=1THENClass为1；规则6：IFA5=3andA1=2THENClass为2；根据决策树表4的测试样本的预测类别为：SmaplesA1A2A3A4A5Class10.102111120.981121215个训练样本645A5=1A5=2A5=3Class223A1=1A1=2Class2Class142Class1A1=1A1=211A4=1A4=2Class1Class2