数据仓库与数据挖掘习题课2

computer.dqpi.edu.cn数据仓库与数据挖掘主讲教师：王浩畅E-mail:[e-mail]&InformationTechnologyofNEPU习题课2习题5.3习题5.14习题6.1习题6.5习题6.14习题5.35.3.数据库有5个事物。设min_sup=60%，min_conf=80%.(a)分别使用Apriori和FP增长算法找出所有的频繁项集。比较两种挖掘过程的效率。(b)列举所有与下面的的元规则匹配的强关联规则（给出支持度s和置信度c），其中，X是代表顾客的变量，item是表示项的变量（如“A”、“B”等）：xtransaction,buys(X,item1)∧buys(X,item2)buys(X,item3)[s,c]TID购买的商品T100{M,O,N,K,E,Y}T200{D,O,N,K,E,Y}T300{M,A,K,E}T400{M,U,C,K,Y}T500{C,O,O,K,I,E}解答5.3(a)解答5.3(续)(a)项头表Itemfrequencyheadk5e4m3o3y3解答5.3(续)(a)效率比较：Apriori算法的计算过程必须对数据库作多次扫描，而FP-增长算法在构造过程中只需扫描一次数据库，再加上初始时为确定支持度递减排序的一次扫描，共计只需两次扫描。由于在Apriori算法中的自身连接过程产生候选项集，候选项集产生的计算代价非常高，而FP-增长算法不需产生任何候选项。解答5.3(续)(b)列举所有与下面的的元规则匹配的强关联规则（给出支持度s和置信度c），其中，X是代表顾客的变量，item是表示项的变量（如“A”、“B”等）：xtransaction,buys(X,“K”)∧buys(X,“O”)buys(X,“E”)[s=0.6,c=1]xtransaction,buys(X,“E”)∧buys(X,“O”)buys(X,“K”)[s=0.6,c=1]或也可表示为K,O→E[s(support)=0.6或60%,c(confidence)=1或100%]E,O→K[s(support)=0.6或60%,c(confidence)=1或100%]5.14.下面的相依表汇总了超级市场的事务数据。其中，hotdog表示包含热狗的事务，表示不包含热狗的事务，humburgers表示包含汉堡包的事务，表示不包含汉堡包的事务。(a)假定发现关联规则”hotdoghumburgers”。给定最小支持度阈值25%，最小置信度阈值50%，该关联规则是强的吗？(b)根据给定的数据，买hotdog独立于买humburgers吗？如果不是，二者之间存在何种相关联系？hotdogrowhumburgers2,0005002,5001,0001,5002,500col3,0002,0005,000习题5.14hotdoghotdoghumburgershotdoghumburgershotdoghotdoghumburgers解答5.14(续)(a)假定发现关联规则”hotdoghumburgers”。给定最小支持度阈值25%，最小置信度阈值50%，该关联规则是强的吗？支持度=P(hotdog,humburgers)=2000/5000=40%25%,置信度=P(hotdog,humburgers)/P(hotdog)=2000/3000=66.7%50%.关联规则是强的(b)根据给定的数据，买hotdog独立于买humburgers吗？如果不是，二者之间存在何种相关联系？Corr{hotdog,hamburger}=P({hotdog,hamburger})/(P({hotdog})P({hamburger}))=0.4/(0.5×0.6)=1.331.因此，购买hotdogs和hamburgers不独立。并且两者是正相关的关系6.1简述决策树分类的主要步骤。1.树以代表训练样本的单个节点开始2.如果样本都在同一个类，则该节点成为树叶，并用该类标记3.否则，算法使用基于熵的度量——信息增益作为指导信息，选择能够最好的将样本分类的属性；该属性成为节点的“测试”或“判定”属性。（使用分类属性）4.对测试属性每个已知的值，创建一个分支，并以此划分样本5.算法使用同样的过程，递归的形成每个划分上的样本决策树。一旦一个属性出现在一个节点上，就不在该节点的任何子节点上出现6.递归划分步骤停止的条件给定节点的所有样本属于同一类没有剩余属性可以用来进一步划分样本——使用多数表决没有剩余的样本习题6.1hotdoghotdoghumburgershotdog6.5为什么朴素贝叶斯分类称为“朴素”的？简述朴素贝叶斯分类的主要思想.朴素贝叶斯分类称为“朴素”是因为：朴素贝叶斯分类器基于一个简单的假定：在给定目标值时属性值之间相互条件独立。换言之，该假定说明给定实例的目标值情况下，观察到联合的a1,a2…am的概率正好是对每个单独属性的概率乘积习题6.5hotdoghotdoghumburgershotdog解答6.5设x=a1,a2…am，为一个有m个属性的样例=maxP(a1,a2…am|cj)P(cj)P(a1,a2…am)=maxP(a1,a2…am|cj)P(cj)(1)P(cMAP|x)=maxP(cj|x)j∈(1,|C|)=maxP(cj|a1,a2…am)朴素贝叶斯分类器是一种基于贝叶斯理论的分类器。它的特点是以概率形式表达所有形式的不确定，学习和推理都由概率规则实现，学习的结果可以解释为对不同可能的信任程度朴素贝叶斯分类器基于一个简单的假定：在给定目标值时属性值之间相互条件独立。换言之，该假定说明给定实例的目标值情况下，观察到联合的a1,a2…am的概率正好是对每个单独属性的概率乘积解答6.5(续)12mjij1P(a,a,...,a|c)=P(a|c)mi(2)将(2)式其代入(1)式中，可得到朴素贝叶斯分类器，如下ijP(a|c)1miCNB=argmaxP(cj)jcC（3）argmax表示寻找具有最大评分的参量解答6.5(续)概括地讲，朴素贝叶斯学习方法需要估计不同的P(cj)和P(ai|cj)项，也就是它们在训练数据上的频率。然后使用公式(3)来分类新实例。其中CNB表示朴素贝叶斯分类器输出的目标值。注意在朴素贝叶斯分类器中，须从训练数据中估计的不同P(ai|cj)项的数量只是不同的属性值数量乘以不同目标值数量——这比要估计P(a1,a2…am|cj)项所需的量小得多||()||jjcPcD||(|)||iijijjAaCcPacCc6.14下表给出课程数据库中学生的期中和期末考试成绩。a)绘制数据图。X和Y看上去具有线性联系吗？b)使用最小二乘法，求由学生的期中成绩预测学生的期末成绩的方程式。c)预测期中成绩为86分的学生的期末成绩。习题6.14hotdoghotdoghumburgershotdogX期中考试Y期末考试725081749486598365338881846377789075497977527490解答6.14(a)绘制数据图。X和Y看上去具有线性联系吗？从散布图看有线性关系(b)使用最小二乘法，求由学生的期中成绩预测学生的期末成绩的方程式。从数据中可以得到|D|=12;=866/12=72.167;=888/12=74.使用公式(6.50)和(6.51),得到w1=0.5816,w0=32.028.因此,得到方程y=32.028+0.5816x,由学生的期中成绩就可以预测学生的期末成绩(c)预测期中成绩为86分的学生的期末成绩。使用(b)中得到的方程y=32.028+0.5816x,代入x=86得到y=32.028+(0.5816)(86)=82.045.因此预测期中成绩为86分的学生的期末成绩为82.045.xycomputer.dqpi.edu.cn