数据挖掘复习题和答案

1、考虑表中二元分类问题的训练样本集表4-8练习3的数据集实例小th目标类1TTLQ+2TT6.0+13TF£04FF4Q4-5FT7.06FT3.07FF8.08TF7.0+9FT5gMM-1.整个训练样本集关于类属性的嫡是多少？2.关于这些训练集中a1,a2的信息增益是多少？3.对于连续属性a3,计算所有可能的划分的信息增益。4.根据信息增益，a1,a2,a3哪个是最佳划分？5.根据分类错误率，a1,a2哪具最佳？6.根据gini指标，a1,a2哪个最佳？答1.ExamplesforcomputingEntropyEntropyt=一工(j|f)1。"p(j/)010C26

2、J.餐P(C1)=0/6=0P(C2)=6/6=1Entropy=-0log0-1Iog1=-0-0=0P(C1)=1/6P(C2)=5/6Entropy=-(1/6)log2(1/6)-(5/6)log2(56)=0.65P(C1»=2/6P(C2)=4/6Entropy=-6)1。的(2/6)-(4/6)loq?(46)=0.92P(+)=4/9andP(-)=5/9-4/9log2(4/9)-5/910g2(5/9)=0.9911.答2:SplittingBasedonINFO.InformationGainGAIN=Entmpy(p)-XEnfropv(i)<1YlPa

3、rentNodepissplitintokpartitions;nisnumberofrecordsinpartitioni- M巳asu巳sReductioninEntropyachievedbecauseofthesplit.Choosethesplitthatachievesmostreduction(maximizesGAIN)- UsedinID3andC4.5- Disadvantage:Tendstoprefersplitsthatresultinlargenumberofpartitions,eachbeingsmallbutpure,（估计不考）Foraltributeai.

4、thvcurrvspotidingtxn山出andproLabililkriart:<11十-TF3114Tlicentroj)yforaiis41-(3/1)l喉田4)(1")1唯11/4)+-(4/5)g(4/5)=07616.>>Tbrrpforp.thrinformationgainforisQ9911-0,7616=0,2294.ForAttributea2-.th也corrrsotidingcountsundprobfihilid<sarc:di十-JF922Tlirrutropyfbra*is7J-(2/5)1%S)-3/b)1%(3/3+:-(

5、2/4)log3(2/4)-(2/4)fog2(2/4)=U.皎9.Thrrrfbrr.thrinformati-ongainfor做嗯。期-().9839=0W72.ContinuousAttributes:ComputingGiniIndex.Forefficientcomputation:foreachattribute,- Sorttheattributeonvalues- Linearlyscanthesevalues,eachtimeupdatingthecountmatrixandcomputingginiindex- Choosethesplitpositionthathast

6、heleastginiindexCheatSortedValuesYesNo地p|Nn|Ho|YesY&s丫腌|No|H01HoiNoTaxableIncome60|70|75|85I|95|100|120|126|2200.4200.4000.3750.3430.4170.400。迎0,343137504000.420GiniS'Tan.SleinbachXtJinarIntroductiontoDataMining4/18/20Q437agClassLibelSplitpointEntropyInfoGiinL0十2.0仇84M0.14273.03.50.98850.002

7、64X14-4.5o.gisjOXT7285.03。-5.50.98300.00726.0+6.50.972S0.01837.(17.(1+工5088即0.1022aiproducesthebestsplit.答4:Accordingtoinformationgain,答5:ExamplesforComputingErrorCl0C26Forattributeai:errorrate=2/9.Forattributea2：errorrate=4/9.Therefore,accordingtoerrorrate,Error(f)=1maxP(it)P(C1)s0/6S0P(C2)=6/B=1Er

8、rors1-max(0,1)=1-1=0P(C1)=1/6P(C2)=5/6Error=1-max(1/6,5/6)=1-5/6=1/6P(C1)=2/6F(C2)=4/6Error=1-max(2/6,4J6)=1-4/6=1/3a1producesthebestsplit.答6:BinaryAttributes:ComputingGINIIndexSplitsintotwopartitionsEffectofWeighingpartitions:Gini(Children)=7/12*0408+5/12*0.32=0371-LargerandPuerPartitionsaresoughtf

9、or.Gini(N1)=1-(5/7)2-(2/7)2=0.408Gini(N2)=1一(1百尸一(4f5)?=0.32STan.SlenbachKLimarIntrodU3tianteDataMiniraForattribute硝'the疝niindexisJprrr，1-(3/4产一(1/4/+31-(1/5尸一(I*)?=03414.，L向IForartribiitrdi.theginiindrxis54-1-(2/5/-(3/5)241-(2/4产-(2/4)2=0.488&.LiISincetheginiindexfor%is-mailer,itproducesthe

10、bettersplit.二、考虑如下二元分类问题的数据集AB类标号TTTTTFFF1TTFTTFTFPFTF十-4-+1.计算a.b信息增益，决策树归纳算法会选用哪个属性HhocontingcncptablesAftersplittingonatrribntpsAand13are:4-3115B=TB=FTheoverallentropytx?ioresplittingis;E口ng=G.4log0.4-0-GlogO.C=0.9710Theinformation：ainafter口口Ais:E&=f313-3Lofi3-31Qg-7/10£Ihrin(orniatien：a

11、inaftersplitting0口Ris:E*t=一,1门g一:I%;=E81134444Kr=f=：】促',1但二通6500=Em."10E人T一6/10Eh尸二力.如倘Thrfor*,attribute.4wilXhospnt<isplitthenode.2.计算a.bgini指标，决策树归纳会用哪个属性?Th<?overaJIxt口resplittin旦is1Gsy=1-0.12一。6,=0.48ThegaininginiaftersplittingouAis:-A=TY)1G)Gb©-7/10Ga=t-3/IOGf=0.1371Thegaini

12、nginiaftersplittingonRis:_(1)一G)=037502NG旧二F1=(I)-(0=0277SGig4/10G£j=tG/lUGi(=r=0.1G33'Therefore,attributeBwillbechosentosplitthenode.这个答案没问题3.从图4-13可以看出嫡和gini指标在0,0.5都是单调递增，而0.5,1之间单调递减。有没有可能信息增益和gini指标增益支持不同的属性？解释你的理由Yes,eventhoughthesemeasureshavesimilarrangeandmonotonousbehavior,theirre

13、spectivegains,A,whicharescaleddifferencesofthemeasures,donotnecessarilybehaveinthesameway,asillustratedbytheresultsinparts(a)and(b).贝叶斯分类ExampleofNaiveBayesClassifierGiv&naTestRecord:X=(Refond=No,Married,Income=12OK)naiveBayesClasBifier:pReruna=Yes|No)=3/7Petund=Jo|oj=4'?：¥&|¥t

14、b-CPWStaius-SinaNo)=27PiAlarilaISlalut-DivorcedNop1J7PNiamaistams=waTn|No)=4/7P(MaMaisialus=singie|Yes)=2f7P(VIarttaiStalus=Dlvorceq¥es)=1/7P(MariiajStah£=Mamed|Yes)=0Fa吐1幅incomeif0simplermi印一口samplevari3nce=?g75ifciass=Yes-samplemean=sosamplevanance=25FX|CIass-Noj=P(Refund=No|Class=No)kP(

15、Mlarried|Class=No)<P(lnccine-1?0K|Class=No)=4/7h4/7上0.0072=0,0024P(X|Cl8ss=Yes)=P(Refund=ND|Class=Yes)xLiamedClass=Yes)*P(ricome=120K|Class=Yes)二1xQx12x10*=0SiresP(X|No；PNq)>P(X|¥es)PYss)ThereforeP(No|X)>PfYes|X)=>Class=No吕Tmn.5明门1曲二如讨丽心口3怕Minin。6$工考虑表5-10中的数据集.亲门再睡7的数据悠记录ABc类10001+

16、200L1301La0I«1500+610171D1IS110I一911+1010i十(a)估计条件概率尸+),尸(0+),严(+)，r(A|-)尸烟一)和尸(牛力根据6)中的条件概率，使用朴素贝叶斯方法预测测试样本供=Q,B=1,C=0)的类标号.©使用m相计方法5=1/2且a=4)估计条件概率0d)同心)，使用(c)中的条件概率Ce)比较估计概率的两种方法，哪一种更好？为什么？1.P(A=1|-)=2/5=0.4,P(B=1|-)=2/5=0.4,P(C=1|-)=1,P(A=0|-)=3/5=0.6,P(B=0|-)=3/5=0.6,P(C=0|-)=0;P(A=1|

17、+)=3/5=0.6,P(B=1|+)=1/5=0.2,P(C=1|+)=2/5=0.4,P(A=0|+)=2/5=0.4,P(B=0|+)=4/5=0.8,P(C=0|+)=3/5=0.6.Let"=o.B=l.rf=AH+H=z?=i,r-G)_PA=0,Z?=1,C=XF(+)_rA=o,r?=()_-0|+)JT(£?-1|+)F(C=0|+x?(十)一7?=0.-1xCh2x0i6x0.5/CA=(F,A?=EC'=0)r(A=U.白=l.C=0|-)x7?(-)P(A=(I.=T,C=()r(.i=o|-)xp(b=i|-)xr(c=o|-)xr(K=0

18、/AF2.TheclassbibcEdiauldbe4-3. P(A=0|+)=(2+2)/(5+4)=4/9,P(A=0|-)=(3+2)/(5+4)=5/9,P(B=11+)=(1+2)/(5+4)=3/9,P(B=11-)=(2+2)/(5+4)=4/9,P(C=0|+)=(3+2)/(5+4)=5/9,P(C=0|-)=(0+2)/(5+4)=2/9.4. LetP(A=0,B=1,C=0)=K=0.B=17<7=C)_P(_A=1曰=Q=xP(-l-)r(A=o,/?=i,c=o)p(a="+>尸(C=乂尸(+)(4/Q)x(3/9)x(S/9)x0,5=K=0

19、.0412/KA=U,臼=I,=U=0,/?=1.=n|)x)=P(A-U；£J-1,C-0)PA=U|-Jx尸(归=l|-Jx/J(C=(J|-)x尸(一)K：(5/()x(4/Q)x(2/Q)x0.5二K=O.O2T4-KTheclasslabelshouldbe5.当的条件概率之一是零，则估计为使用m-估计概率的方法的条件概率是更好的，因为我们不希望整个表达式变为零。8.考虑表5-11中的数据集.315-11习题8的数据集实例A8c1类110Q1-2101*3010一14100w|5101;|6001十7110,s-80I009010十101114估计条件概率P(A=1R),产

20、(B=小)，P(C=lk%P伍=1卜)，P(B=1|-P(C=1H*(b)根据中的条件概率，使用朴素贝叶斯方法预测测试样本5=1,的类标号。(c)比较/(月=1),P(B=I)和/An1,8=1),陈述A.3之间的关系。(d)对尸俵=】)，P(fl=0)和?(A=LB=0)重复9)的分析。<c)比较尸(4=1,占=】|类=+)与P(A=1|类=十)和P(B=1|英三十)给定英)，受盘人.B条件独立吗？1. P(A=11+)=0.6,P(B=11+)=0.4,P(C=11+)=0.8,P(A=1|-)=0.4,P(B=1|-)=0.4,andP(C=1|-)=0.22.LetR:(A=1,

21、B=1,C=1)bethetestrecord.Todetermineitsclass,weneedtocomputeP(+|R)andP(-|R).UsingBayestheorem,P(+|R)=P(R|+)P(+)/P(R)andP(-|R)=P(R|-)P(-)/P(R).SinceP(+)=P(-)=0.5andP(R)isconstant,RcanbeclassifiedbycomparingP(+|R)andP(-|R).Forthisquestion,P(R|+)=P(A=1|+)XRB=1|+)*F(C=11+)=0.192P(R|-)=P(A=1|-)XRB=1|-)XIC

22、=11-)=0.032SinceP(R|+)islarger,therecordisassignedto(+)class.3.P(A=1)=0.5,P(B=1)=0.4andP(A=1,B=1)=P(A)xP(B)=0.2.Therefore,AandBareindependent.4.P(A=1)=0.5,P(B=0)=0.6,andP(A=1,B=0)=P(A=1)xRB=0)=0.3.AandBarestillindependent.5.CompareP(A=1,B=11+)=0.2againstP(A=11+)=0.6andP(B=1|Class=+)=0.4.Sincetheprod

23、uctbetweenP(A=11+)andP(A=11-)arenotthesameasP(A=1,B=11+),AandBarenotconditionallyindependentgiventheclass.三、使用下表中的相似度矩阵进行单链和全链层次聚类。绘制树状况显示结果，树状图应该清楚地显示合并的次序。Table8.1.SimilaritymatrixforExercise16.(a)Singlelink.Ib)C'oinpleielink.822*.0oo-=-8-10210210cbd-f)=*bd=0,2"02(18=1。%=25%2.考虑表a22中显示的数据

24、集s裹622购物该事劣的例子r成琴a事务ID烟奖项-iQOOL位/禺TO242(MJ12口内ME210031国中间3W1530022他“14CO291<44(KM阿融510033Md同51MK38忸由.将每个事务I视为一个购物篮乱明他却书也d©!计算项案和他4或的支持度.（W使用g）的计算结果，计算美联规则他df£利伍一伽刈的置信度，置信度是对称的度量吗？（C）将每个原客TD作为一个购物簸，重复值）.应当将每个项看作一个二元变量（如果一个项在欣客的购买事务中至少出现了一次，则为h古则，为G.（d）使用代）的计算结果，计算美联规则比用一色相1打一（也旬的置信度,（fi）

25、假定酊和是将每个事务ID作为一个购物篮时关联规则，的支持度和置信度，而歙利办是将每个顾客ID作为一个购物18时关联提则r的支持度和置信度*讨论物和J,或白和G之间是否存在某种关系？N(xronHdriircinnorasvmTnrtricniraurc5(H)3M)Therearenoapparentrelationshipsbetweensi,s2,ci,andc2.6.考虑表6-23中显示的购物篮事务.表6城3购物篮事务1浮购买项i234567B910（牛初，M酒,尿布）i面包，货油,牛奶）（牛奶，尿布，加干回包.黄浦,蝌干f理酒.伊干，尿布牛奶.球布.m包，黄浊）i面包.黄袖，尿布】啤泅

26、展布1牛奶，尿布，面包.黄油）晔工饼干Ca）从这基数据中,能够提取出的关联规则的最大数量是多少（包括零支持度的规则）？（b）能够提取的频繁项集的最大长度是多少（假定最小支持度0）?（0写出从该数据集中能够梃取的务项集的最大数量的表达式“（d）找出一个具有最大支持度的项集（长度为2或更大）.（e）找出一对项日和也使得规则。一与和可一内具有相同的置信度中(a) What,isthrniaxinmmnunitxrofaxsociarionrulesrhatcanIk1extracted6romthisdata(IncludingrillesthathavezerorapportJ?Answer:Th

27、rparpsixitpnisinthedataset.Ttierrforpth-ptotalnirmbci'ofrulesis仪理.(b) Whatisthemaximumsizeoffrequentitemsetethatcanbeextracted；3i<riLiiiiiriininsup>011Answer:Bocaiisrthe口口transacrioncontains1items,tlicmaxi-niuiEtiiAcuEfreqlientitetnsttif4.(c) Writeancxprcsnidii£orthvinaximuiuncuiiibcr

28、ofsine-3itcnisrtstliatcanbederivedfromtinsdat.aset,Aitswcr:(；)=肛(d) Findanitemwt(of哥a2orlargrTrhntliasthelargfFtsupport.Answer:(Bread.Buittr).(e) Findapairofiteuis.uand6.suulithatdierulesa-*叶and|b1ajntiavoth*1saTjirmnfidenraAnswer:：Bccr.Coulics3(Breail：Buller8. 论理算法使用产生一计数的策略找出赧繁项集,通过合并一对大小为无的频繁项集得到一个大小为阱1的候选项集1称作候选产生