数据挖掘原理与应用教师用书精简版

给定如表3-4所示事务数据库画出FP-treeTOC\o"1-5"\h\zItemSCP/—fc5:*cb土e3—妒a2决策树容易转换成分类规则，试把图4-1转化为分类规则Ifage<=30andstudent=noThenbuys_computer=noIfage<=30andstudent=yesThenbuys_computer=yesIfage>30andage<=40Thenbuys_computer=yesIfage>40andcredit_rating=excellentThenbuys_computer=noIfage>40andcredit_rating=fairThenbuys_computer=yes下面的例子被分为3类{short,tall,Medium}(0,1.6)(1.6,1.7)..(2.0,无穷)P(Output="Short”)=4/14=0.267；P(Output="Medium”)=8/15=0.533P(Output=“Tall”)=3/15=0.200P(Gender="M”|Output=”Medium”)=2/8=0.25P(Gender="M”|Output=”Tall”)=3/3=1P(Height=(1.9,2.0]|Output=”Short”)=0/4=0P(Height=(1.9,2.0]|Output=”Medium=1/8=0.125P(Height=(1.9,2.0]|Output=”Short”)=1/3=0.33P(X|Output=”Short”)=0.24x0=0P(X|Output=”Medium”)=0.25x0.125=0.0313P(X|Output=”Tall”)=1x0.33=0.33P(X|Output=”Short”)P(Output=”Short”)=0x0.267=0P(X|Output=”Medium”)=0.25x0.125=0.0313x0.533=0.0167P(X|Output=”Tall”)=0.33x0.2=0.066对于样本t=<Adam,M,1.95m),朴素贝叶斯分类预测Ouput="Tall"11.给定两个对象，分别用元组(22,1,42,10),(20,0,36,8)表示。(1)计算两个对象之间欧氏距离。(2)计算两个对象之间绝对距离。(1)根据两个对象之间的欧氏距离公式d(x,y)=得出：d(x,y)=[|22-20|2+|1-0|2+|42-36|+|10-8|2]1/2=(4+1+36+41)1/2=45/2=6.708⑵根据两个对象之间的绝对距离公式d(x,y)=得出：d(x,y)P(Gender="M”|Output=”Short”)=1/4=0.25(22-20)+(1-0)+(42-36)+(10-8)=d(x,y)2+1+6+2=11的簇数为3.达到终止条件。表5-6给出了整个过程中平均值计算和簇生成的过程和结果。2+1+6+2=1123.在表5-4中给定的样本上运行DIANA算法，假定算法的终止条件为三个簇，初始簇{1,2，3,4.5.6.7.8}.||■有通大直褓的震jpointerm叩piiTiyI■■j■■1卜*.|K"Li-d1J*i41pB!11iSh&F"11i.lnfiI1?!,"L日■4■n.|SI3J.轧6A岸却UHrlMH2序弓■性日Hfl21LDEZ5JH4.45B$7$4Q1-T1J|,4在表中给定的样本上运行AGNES算法，假定算法的终第一步，找到具有最大直径的簇，对簇中的每个点计算平均相异度的平均距离：(5.000+8.485+3.606+7.071+7.211+8.062+2.236>/7=5.953的平均距离：(5.000+6.082+4.243+5.000+4.123+3.162+4.472)/7=4.583的平均距(8.485+6.082+5.000+1.414+2.000+7.280+6.403)/7=5.238的平均距距:(3.606+4.243+5.000+3.606+4.123+7.211+1.414)/7=4.172的平均距距：(7.071+5.000+1.414+3.606+1.414+6.708+5.000/7=4.316的平均距距：(7.211+4.123+2.000+4.123+1.414+5.385+5.385)/7=4.234的平均距距：(8.062+3.162+7.280+7.211+6.708+5.385+7.616)/7=6.489的平均距距：(2.236+4.472+6.403+1.414+5.000+5.385+7.616>/7=4.647挑出平均相异度最大的点7放到splintergroup中，剩余点在oldparty中。第二步，在oldparty里找出到最近的splintergroup中的点的距离不大于到oldparty中最近的点的距离的点，将该点放入splintergroup中,该点是2。第三步，没有新的oldparty中的点被分配给splintergroup，分裂簇数为2.第四步，具有最大直径的簇为(1.3,4,5.6.8)(具体属性值见表5-5.对簇中的每个点计算平均相异度。tf-sAW1大宣控RHiiA的Jtf!唯

止条件为3个簇，初始簇{1},{2},{3},{4},{5},{6},{7},{8}步骤最近的簇距离最近两个簇合并的新簇12（根号）{3}，{5}{3,5}{1}{2}{4}{6}{7}{8}22（根号）⑷，{8}{3,5}{4,8}{2}{1}{6}{7}32（根号）{3,5}，{6}{3,5,6}{4,8}{2}{1}{7}45（根号）{4,8}，{1}{3,5,6}{1,4,8}{2}{7}510（根号{2},{7}{3,5,6}{1,4,8}{2,7}序明flit18ft1序与rfiqtti12g,*4，:::的平均距离：(8.485+3.606+7.071+7.211+2.236)/5=5.722的平均距离：(8.485+5.000+1.414+2.000+6.403)/5=4.660的平均距离：(3.606+5.000+3.606+4.123+1.414)/5=3.549的平均距离：(7.071+1.414+3.606+1.414+5.000)/5=3.701的平均距离：(7.211+2.000+4.123+1,414+5.385)/5-4.0278的平均距离：(2.236+6.403+1.414+5.000+5.385)/5=4.088挑平均相异度最大点1放splintergroup中，剩余点在oldparty中。

给定如表3-1写出Apriori算法生成频繁项目集的过程（假设Minsuport=50%）。TIDItemseta，c，d，e，fb，c，fa，d，fa，c，d，ea，b，d，e，fL1生成：C1={(a，4)(b，2)(c，3)(d，4)(e.3)(f.4)};L1=(a，c，d，e，f)第五步，没有新的oldparty的点被分配给splintergroup，此时分裂L2C2=((ac,2)(ad,4)(ae,3)(af.3)(cd,2)(ce,2)(cf,2)(de,3)(df,3)(ef.2);

Rule-generate来生成对应的关联规则(设L2={ad.ae,af,de,df}L3生成：C3={(ade,3)(adf,3)(def.2)};L3={ade,adf)L4生成：C4:{(adef,2)};L4=空集L5生成：C5=空集,L5=空集结束后，最大频繁项目集为{ade,adf}给定如表3-2写出Apriori算法生成频繁项目集的过程(假设Minsuport=40%)oTIDItemset1.3.4.2.3.4.51.3.5.72.51.2.4.6.72.4.6L1生成：C1={(1,3)2.4)(3,3)(4,4)(5.3)(6,2)};

minconfidence=80%)序号lkXm-1confidencesupport规则(是否是强规则)1adead75%60%ad—e否2adea75%60%a—de否3aded75%60%d—ae否4adeae100%60%ae—d是5adee100%60%e—ad是6adede100%60%de—a是7adfad75%60%ad—f否8adfa75%60%a—df否9adfd75%60%d—af否10adfaf100%60%af—d是11adff75%60%f—ad否12adfdf100%60%df—a是L1={1,2,3,4,5}L2生成：C2={(12.1)(13,2)(14,2)(23,1)(24,3)(25,2)(34,2)(35,2)(45,1);L2={2,4}

一个关于配眼镜的一个决策分类所需要的数据，数据及包括五个属性。⑴计算给定样本contact-lenses分类所需的期望。I(s1,s2,s3)=I(15,5,4)=-15/24log2(15/24)-5/24log2(5/24)-4/24log2(4/24)=0.424+0.471+0.431=1.326(2)计算每个属性的熵对上面的第13题所生成的最大频繁项目集,跟踪观察age的每个样本值的分布，如下表：对于age=young,S11=4,S21=2,S31=2，则I(s11,s21,s31)=I(4,2,2)=-4/8log2(4/8)-2/8log2(2/8)-2/8log2(2/8)=0.5+0.5+0.5=1.5对于age=pre-presbyopic,S12=5,S22=2,S32=1，贝UI(s12,s22,s32)=I(5,2,1)=-5/8log2(5/8)-2/8log2(2/8)-1/8o2(1/8)=0.424+0.5+0.375=1.299对于age=presbyopic,S13=6,S23=1,S3=1，则JI(s13,s23,s33)=I(6,1,1)=-6/8log2(6/8)-1/8log2(1/8)-1/8o2(1/8)=0.311+0.375+0.375=1.061所以，如果样本按观察age的每个样本值的分布，如下表：对于age=young,S11=4,S21=2,S31=2，则2、假设有一个训练集，其包含3个属性：at1,at2,at3。现在有正例反例样本分别如下所示，AQ算法对“+”的规则进行获取。(1)cover=()E(2、假设有一个训练集，其包含3个属性：at1,at2,at3。现在有正例反例样本分别如下所示，AQ算法对“+”的规则进行获取。(1)cover=()Gain(age)=I(s1,s2,s3)-E(age)=1.326-1.287=0.039(2)空cover不覆盖任何样本，进入循环(3)一开始cover并没有覆盖任何正例，假定从正例中选取的SEED为{at}=y，at2=n，at3=r(4)调用STARSEED，NEG产生一个覆盖SEED但不包含NEG的STAR集合(4-1)初始化STAR为空，即STAR={}(4-2)空的complex覆盖所有样例，STAR覆盖多个负样例，进入循环(4-2-1)选取一个被STAR中的复合覆盖的负样例ENEG，假定选取的是ENGE={at1=x，at2=m，at3=s}(4-2-2)使EXTENSION为所覆盖SEED但不覆盖ENEG的选择则EXTENION包括at1=yat2=n,at3=r,则又根据STAR={xny}xgSTAR,ygEXTENSION}因此STAR={at1=ynat2=nnat3=r}(4-2-3)在这里定义maxstar为3，可不对STAR进行精简(4-2-4)接着选取另一个被STAR中的复合覆盖的负样例ENEG，虽然已经没有这样的负样例，因此，STAR={at1=ynat2=nnat3=r}(4-3)从STAR(SEED,NEG)返回(5)BEST={at1=ynat2=nnat3=r},COVER={at1=ynat2=nnat3=r}(6)显然COVER不能覆盖所有的正例，从正例中选取另一个SEED={at1=xnat2=mnat3=r}(7)调用STARSEED,NEG产生一个覆盖SEED但不包含NEG的STAR集合(7-1)初始化STAR为空，即STAR={}(7-2)空的complex覆盖所有样例，所以STAR覆盖负样例，进入循环(7-2-1)假定选取的负ENEG={at1=x,at2=n,at3=s}(7-2-2)使EXTENSION为所有覆盖ESSD但不覆盖ENEG的选择，则EXTENSION，包括at2=m和at3=r,则又根据STAR=xyIxgSTAR,ygEXTENSION}因此，STAR={at2=mnat3=r}(7-2-3)接着选取另一个被STAR中的复合覆盖的负样例ENEG,显然已经没有这样的负样例，因此STAR={at=mnat3=r}(7-3)从STAR(SEED,ALEG)返回(8)BEST={at2=mnat3=r}将BEST添加到COVER中，COVER={at1=ynat2=nnat3=ruat2=mnat3=r}={at2=mnat3=ruat2=nnat3=r}(9)显然cover不能覆盖所有的正例，从正例中选取另一个SEED{at1=ynat2=nnat3=s}(10)调用STAR(SEED,NEG)产生一个覆盖SEED但不会包含NEG的STAR集合(10—1)初始化STAR为空，即STAR={}(10—2)空的complex覆盖所有样例，所以STAR覆盖负样例，进入循环(10-2-1暇定选取的是ENEG={at1=y,at2=m,at3=t}(10-2-2)使TESION为所有覆盖SEED但不覆盖ENEG的选择，则TESION中at2=n,和at3=s则又根据STAR{xny/x属于STAR,y属于EXTESION}因此STAR={at2=nnat3=s}(10-2-3)接着选取另一个被STAR中的复合覆盖的负样例ENEG，显然已经没有选样的负样例，因此STAR=(at2=nnat3=s)(10-3)从STAR(SEED,NEG)返回(11)BEST=(at2=nnat3=s)将BEST添加到COVER中，COVER={at2=mnat3=ruat2=nnat3=suat2=nnat3=r}(12)这时cover已经覆盖到全部的正例，则算法结束，输出规则+at2=mnat3=ruat2=nnat3=suat2=nnat3=rK平均迭代平均值(簇1)平均值(簇2)新簇新平均c1新平均c2(1,1)(1,2)(1,2)(3,4,5,6,7,8)(1.5,1)(3.5,3)(1.5,1)(3.5,3)(1,2,3,4)(5,6,7,8)(1.5,1.5)(4.5,3.5)(1.5,1.5)(4.5,3.5)(1,2,3,4)(5,6,7,8)(1.5,1.5)(4.5,3.5)OLTP:联机事务处理：推动和管理面向事务的应用程序的一类程序。典型针对数据输入和恢复事物处理OLAP联机分析处理:使分析人员，管理人员或执行人员能够从多角度对信息进行快速一致，交互地存取，从而获得对数据的更深入了解的一-类软件技术。ParallelAssociationRuleMining并行关联规则挖掘:是指利用并行处理机、使用挖掘算法或在并行计算的环境下完成数据的高效挖掘工作。Posteriorprobability后验概率Paritioningmethods划分法Artificialintelligence人工智能：研究开发用于模式延伸和拓展人的智能的理论、方法、技术、应用及应用系统的学科ClosedItemset关闭项目集:简单地说，对于-一个关闭项目集的任何元素，要么不被任何元素所包含，要么只被小于它的支持度的元素所包含Decisionsupport决策支持:为决策者提供分析问题，建立模型，模拟决策过程和方案的环境DBSCAN:是一个基于密度的聚类算法。它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的空间数据库中发现任意形态的聚类Distributeddatabase分布式数据库:是用计算机网络将物理上分散的多个数据库单元连接起来组成一个逻辑统的数据库DataMiningOLTP:联机事务处理：推动和管理面向事务的应用程序的一类程序。典型针对数据输入和恢复事物处理OLAP联机分析处理:使分析人员，管理人员或执行人员能够从多角度对信息进行快速一致，交互地存取，从而获得对数据的更深入了解的一-类软件技术。ParallelAssociationRuleMining并行关联规则挖掘:是指利用并行处理机、使用挖掘算法或在并行计算的环境下完成数据的高效挖掘工作。Po