完整版数据挖掘课后答案

第一章1.6(1)数据特征化是目标类数据的一般特性或特征的汇总.例如,在某商店花费1000元以上的顾客特征的汇总描述是：年龄在40—50岁、有工作和很好的信誉等级.(2)数据区分是将目标类数据对象的一般特性与一个或多个比照类对象的一般特性进行比较.例如,高平均分数的学生的一般特点,可与低平均分数的学生的一般特点进行比较.由此产生的可能是一个相当普遍的描述,如平均分高达75%的学生是大四的计算机科学专业的学生,而平均分低于65%的学生那么不是.(3)关联和相关分析是指在给定的频繁项集中寻找相关联的规那么.例如,一个数据挖掘系统可能会发现这样的规那么：专业(X,计算机科学〞)=＞拥有(X,〞个人电脑J[support=12%,confidence=98%],其中X是一个变量,代表一个学生,该规那么说明,98%的置信度或可信性表示,如果一个学生是属于计算机科学专业的,那么拥有个人电脑的可能性是98%.12%的支持度意味着所研究的所有事务的12%显示属于计算机科学专业的学生都会拥有个人电脑.(4)分类和预测的不同之处在于前者是构建了一个模型(或函数),描述和区分数据类或概念,而后者那么建立了一个模型来预测一些丧失或不可用的数据,而且往往是数值,数据集的预测.它们的相似之处是它们都是为预测工具：分类是用于预测的数据和预测对象的类标签,预测通常用于预测缺失值的数值数据.例如：某银行需要根据顾客的根本特征将顾客的信誉度区分为优良中差几个类别,此时用到的那么是分类；当研究某只股票的价格走势时,会根据股票的历史价格来预测股票的未来价格,此时用到的那么是预测.(5)聚类分析数据对象是根据最大化类内部的相似性、最小化类之间的相似性的原那么进行聚类和分组.聚类还便于分类法组织形式,将观测组织成类分层结构,把类似的事件组织在一起.例如：世界上有很多种鸟,我们可以根据鸟之间的相似性,聚集成n类,其中n可以认为规定.(6)数据演变分析描述行为随时间变化的对象的规律或趋势,并对其建模.这可能包括时间相关数据的特征化、区分、关联和相关分、分类、预测和聚类,这类分析的不同特点包括时间序列数据分析、序列或周期模式匹配和基于相似性的数据分析.例如：假设你有纽约股票交易所过去几年的主要股票市场(时间序列)数据,并希望投资高科技产业公司的股票.股票交易数据挖掘研究可以识别整个股票市场和特定的公司的股票的演变规律.这种规律可以帮助预测股票市场价格的未来走向,帮助你对股票投资做决策.1.11一种是聚类的方法,另一种是预测或回归的方法.(1)聚类方法：聚类后,不同的聚类代表着不同的集群数据.这些数据的离群点,是不属于任何集群.在各种各样的聚类方法当中,基于密度的聚类可能是最有效的.(2)使用预测或回归技术：构建一个基于所有数据的概率(回归)模型,如果一个数据点的预测值有很大的不同给定值,然后给定值可考虑是异常的.用聚类的方法来检查离群点更为可靠,由于聚类后,不同的聚类代表着不同的集群数据,离群点是不属于任何集群的,这是根据原来的真实数据所检查出来的离群点.而用预测或回归方法,是通过构建一个基于所有数据的(回归)模型,然后根据预测值与原始数据的值比较,当二者相差很大时,就将改点作为离群点处理,这对所建立的模型有很大的依赖性,另外所建立的模型并不一定可以很好地拟合原来的数据,因此一个点在可能某个模型下可能被当作离群点来处理,而在另外一个模型下就是正常点.所以用聚类的方法来检查离群点更为可靠15挖掘海量数据的主要挑战是:1)第一个挑战是关于数据挖掘算法的有效性、可伸缩性问题,即数据挖掘算法在大型数据库中运行时间必须是可预计的和可接受的,且算法必须是高效率和可扩展的.2)另一个挑战是并行处理的问题,数据库的巨大规模、数据的广泛分布、数据挖掘过程的高开销和一些数据挖掘算法的计算复杂性要求数据挖掘算法必须具有并行处理的水平,即算法可以将数据划分成假设干局部,并行处理,然后合并每一个局部的结果.第二章11三种标准化方法：(1)最小一最大标准化(min-max标准化)：对原始数据进行线性变换,将原始数据映射到一个指定的区间.,v_min/_一._v=(new_max-new_min)+new_minmax-min一一一(2)z-score标准化(零均值标准化)：将某组数据的值基于它的均值和标准差标准化,是其标准化后的均值为0方差为1.,vv=,其中N是均值,仃是标准差(3)小数定标标准化：通过移动属性A的小数点位置进行标准化.7=本其中,j是使得Maxfv|)<1的最小整数(a)min-max标准化v-minv=(new_max-new_min)+new_minmax-min一一一其中v是原始数据,min和max是原始数据的最小和最大值,new_max和new_min是要标准化到的区间的上下限原始数据2003004006001000[0,1]标准化00.1250.250.51(b)z-score标准化1v-v=,其中N是均值,仃是标准差,200300400600100010005001000_~zTT2TTTT2TTTT22(200—500)+(300—500)2+(400-500)2+(500—500)2+(1000-500)2ooo二2o2.o427原始数据2003004006001000z-score-1.06-0.7-0.350.351.782.13(1)逐步向前选择(2)逐步向后删除(3)向前选择和向后删除的结合第三章3.2简略比较以下概念,可以用例子解释你的观点(a)雪花形模式、事实星座形、星形网查询模型.答：雪花形和事实星形模式都是变形的星形模式,都是由事实表和维表组成,雪花形模式的维表都是标准化的；而事实星座形的某几个事实表可能会共享一些维表；星形网查询模型是一个查询模型而不是模式模型,它是由中央点发出的涉嫌组成,其中每一条射线代表一个维的概念分层.(b)数据清理、数据变换、刷新答：数据清理是指检测数据中的错误,可能时订正它们；数据变换是将数据由遗产或宿主格式转换成数据仓库格式；刷新是指传播由数据源到数据仓库的更新.(见74页)(见74页)student维表area维表univfacttable(a)雪花形模式图如下:course维表(b)特殊的QLAP操作如下所示：(见79页)在课程维表中,从course_id到department进行上卷操作；在学生维表中,从student_id到university进行上卷操作；根据以下标准进行切片和切块操作：department="C6anduniversity="BigUniversity";在学生维表中,从university到student_id进行下钻操作.(c)这个立方体将包含54=625个长方体.(见课本88与89页)第五章5.1(a)假设s是频繁项集,min_sup表示项集的最低支持度,D表示事务数据库.由于s是个频繁项集,所以有

supsupport(s)二support_count(s)之min_sup假设s是s的一个非空子集,由于support_count(s)>support_sup(s),故有至min_sup」,'supprotcount(s)support(s至min_sup所以原题得证,即频繁项集的所有非空子集必须也是频繁的.(b)由定(b)由定义知,support(s)=support_count(s)令s是s的任何一个非空子集,那么有support(s)='supprot_count(s)s的任意非空子集s的支持度p(l)

p(s)由(a)可知,support(s)-ss的任意非空子集s的支持度p(l)

p(s)至少和s的支持度一样大.(c)由于confidence(s=l-s)=血»,confidence(s=p(s)根据(b)有p(s)=>p(s)''所以confidence(s=>l-s)_confidence(s-三l-s)..''..........■.一即“s=>(l-s)〞的置信度不可能大于"s=A(l—s)〞(d)反证法：即是D中的任意一个频繁项集在D的任一划分中都不是频繁的假设D划分成d1,d2,…,dn,设d1=Ci,dz|=C2,…,dn=Cn,min_sup表示最小支持度,C=D=GC2-CnF是某一个频繁项集,A=F,A>CXmin_sup,D=d1=d25-udn设F的项集在d1,d2,…,dn中分别出现a1,a2,…,an次所以A=a1+a2+…+an*)故A之C父min_sup=(C1+C2+…+CN)父min_sup)*)=ai+a2++an之(Ci+C2+Cn)xmin_sup丁FftD的任意一个划分都不是频繁的:.a1<C1Mmin_sup,a2cC2Mmin_sup；",ancCn父min_sup(ai+a2+…+an)<(C[+C2+…+Cn)xmin_sup=A<Cmmin_sup这与(*)式矛盾从而证实在D中频繁的任何项集,至少在D的一个局部中是频繁.5.3最小支持度为3(a)Apriori方法：CiLiC2L2C3L3m3o3n2m3o3n2k5e4y3diaiuic2iim3o3k5e4y3moimk3me2my2ok3oe3oy2ke4ky3ey2mk3ok3oe3ke4ky31oke3keyokey3FFP-growth:Y:iitemCY:iitemConditionalpatternbaseConditionaltreeFrequentpatterny{{k,e,m,o:1},{k,e,o:1},{k,m:1}}K:3{k,y:3}o{{k,e,m:1},{k,e:2}}K:3,e:3{k,o:3},{e,o:3},{k,e,o:3}m{{k,e:2},{k:1}}K:3{k,m:3}e{{k:4}}K:4{k,e:4}这两种挖掘过程的效率比较：Aprior算法必须对数据库进行屡次的扫描,而FP增长算法是建立在单次扫描的FP树上.在Aprior算法中生成的候选项集是昂贵的〔需要自身的自连接〕而FP-growth不会产生任何的候选项集.所以FP算法的效率比先验算法的效率要高.(b)(b)k,o)e,o>e[0.6,1]k[0.6,1]5.6一个全局的关联规那么算法如下：1〕找出每一家商店自身的频繁项集.然后把四个商店自身的频繁项集合并为CF项集；2〕通过计算四个商店的频繁项集的支持度,然后再相加来确定CF项集中每个频繁项集的总支持度即全局的支持度.其支持度超过全局支持度的项集就是全局频繁项集.3〕据此可能从全局频繁项集发现强关联规那么.5.14support(hotdogs=humbergers)⑶=(h0td0gs「harmburge⑶=2000=40%>25%500055000confidence黑—%p(hotdogs,hamburger,

p(confidence黑—%所以该关联规那么是强规那么.、p〔hotdogs,hamburgers〕corr〔hotdogs,hamburgers〕=--〔b〕p〔hotdogs〕p〔hamburgers〕TOC\o"1-5"\h\z200050000.44,===—130005000250050000.62.53所以给定的数据,买hotdogs并不独立于hamburgers,二者之间是正相关.5.191〕挖掘免费的频繁1-项集,记为S12〕生成频繁项集S2,条件是商品价值不少于$200〔使用FP增长算法〕3〕从S1S2找出频繁项集4〕根据上面得到的满足最小支持度和置信度的频繁项集,建立规那么S1=>S2第六章6.1简述决策树的主要步骤答：假设数据划分D是练习元组和对应类标号的集合1)树开始时作为一个根节点N包含所有的练习元组；2)如果D中元组都为同一类,那么节点N成为树叶,并用该类标记它；3)否那么,使用属性选择方法确定分裂准那么.分裂准那么只当分裂属性和分裂点或分裂子集.4)节点N用分裂准那么标记作为节点上的测试.对分裂准那么的每个输出,由节点N生长一个分枝.D中元组厥词进行划分.(1)如果A是离散值,节点N的测试输出直接对应于A的每个值.(2)如果A是连续值的,那么节点N的测试有两个可能的输出,分别对应于A<split_point和A>split_point.(3)如果A是离散值并且必须产生二叉树,那么在节点N的测试形如“AWSa",Sa是A的分裂子集.如果给定元组有A的值aj,并且ajWSa,那么节点N的测试条件满足,从N生长出两个分枝.5)对于D的每个结果划分Dj,使用同样的过程递归地形成决策树.6)递归划分步骤仅当以下条件之一成立时停止：(1)划分D的所有元组都属于同一类；(2)没有剩余的属性可以进一步划分元组；(3)给定分枝没有元组.计算决策树算法在最坏情况下的计算复杂度是重要的.给定数据集D,具有n个属性和|D|个练习元组,证实决策树生长的计算时间最多为nM|D|xlogqD)证实：最坏的可能是我们要用尽可能多的属性才能将每个元组分类,树的最大深度为10g(|D|),在每一层,必须计算属性选择O(n)次,而在每一层上的所有元组总数为|D|,所以每一层的计算时间为O(nx|D|),因此所有层的计算时间总和为O(n父|D|父logD),即证实决策树生长的计算时间最多为n父D父10gqD|)为什么朴素贝叶斯分类称为“朴素〞简述朴素贝叶斯分类的主要思想.答：(1)朴素贝叶斯分类称为“朴素〞是由于它假定一个属性值对给定类的影响独立于其他属性值.做此假定是为了简化所需要的计算,并在此意义下称为“朴素〞.(2)主要思想：(a)设D是练习元组和相关联的类标号的集合.每个元组用一个n维属性向量X={x1,X2,…,Xn}表示,描述由n个属性Ai,A2,…,An对元组的n个测量.另外,假定有m个类Ci,C2,…,Cm(b)朴素贝叶斯分类法预测X属于类G,当且仅当P(Ci|X)>P(Cj|X)1WjWm,j#i,因此我们要最大化P(Ci|X)=P(X髭；(.",由于P(X)对于所有类为常数,因此只需要P(X|Ci)P(Ci)最大即可.如果类的先验概率未知,那么通过假定这些类是等概率的,即P(Ci)=P(C2)=…P(Cm),并据此对P(X|Ci)最大化,否那么,最大化P(X|Ci)P(Ci),类的先验概率可以用P(Ci)=巴也估计.其中|GD|是D中Ci类的练习元组数.(c)假IDI定属性值有条件地相互独立,那么nP(X|Ci)=nP(Xk|Ci)=P(X1|Ci)MP(X2|Ci)M…MP(Xn|G),如果Ak是分类属k4性,那么P(Xk|0)是口中属性Ak的值为Xk的Ci类的元组数除以D中Ci类的元组数|Ci,D|;如果Ak是连续值属性,那么P(Xk|Ci)由高斯分布函数决定.6.13给定k和描述每个元组的属性数n,写一个k最近邻分类算法.算法：输入：(1)设U是待分配类的元组；T是一个练习元组集,包括T1=(t1Gti,2,…,t1,n),T2-(t2,1,t2,2,,t2,n),,Tm-(tm,1)tm,21,tm,n)(3)假设属性ti,n是Ti的类标签；m为练习元组的个数；n为每个元组的描述属性的个数；k是我们要找的最邻近数.输出：U的分类标签算法过程：(1)定义矩阵a[m][2]0//(m行是存储与m个练习元组有关的数据,第一列是存储待分类元组U与练习元组的欧几里得距离,第二列是存储练习元组的序号)(2)fori=1tomdofa[i][1]=Euclideandistance(U;Ti);a[i][2]=i;g//savetheindeX,becauserowswillbesortedlater(3)将a[i][1]按升序排列.(4)定义矩阵b[k][2].〃第一列包含的K-近邻不同的类别,而第二列保存的是它们各自频数⑸fori=1tokdofif类标签ta[i][2];n已经存在于矩阵b中then矩阵b中找出这个类标签所在的行,并使其对应的频数增加1eles将类标签添加到矩阵b可能的行中,并使其对应的频数增加1(6)将矩阵b按类的计数降序排列(7)返回b(1).//返回频数最大的类标签作为U的类标签.第七章

简单地描述如何计算由如下类型的变量描述的对象间的相异度：(a)数值(区间标度)变量答：区间标度变量描述的对象间的相异度通常基于每对对象间的距离计算的,常用的距离度量有欧几里得距离和曼哈顿距离以及闵可夫基距离.欧几里得距离的定义如下：d(i,j)-xi1-xji,xi2-xj2;xin-X川其中i=(xii,xi2,,xin)和j=(xji,xj2,,xjn)是两个n维数据对象.曼哈顿距离的定义：d(i,j)=为1—x〞+xx2—xj2+…+*所一*而iijixjjuinjnPpp1n闵可夫基距离的定义：d(i,j)=(xi1-xj1+xx2-xj2+…+xin—xjny(b)非对称的二元变量答：如果二元变量具有相同的权值,那么一个二元变量的相依表如下:对象j10和1qrq+r0sts+t和q+sr+tp因此计算相异度时可以在计算非对称二元变量的相异度时,认为负匹配的情况不那么重要,忽略,所以二忽略,所以二元变量的相异度的计算公式为:d(i,j))qrs(c)分类变量i和j之间的相异度答：分类变量是二元变量的推广,它可以取多于两个i和j之间的相异度可以根据不匹配率来计算：d(i,j)=上二m,其中m是匹配的数目(即对i和j取值相同状P态的变量的数目),而p是全部变量的数目.另外,通过为M个状态的每一个创立一个二元变量,可以用非对称二元变量对分类变量编码.对于一个具有给定状态值的对象,对应于该状态值的二元变量置为1,而其余的二元变量置为0.(d)比例标度变量答：有以下三种方法：(1)将比例标度变量当成是区间标度标量,那么可以用闽可夫基距离、欧几里得距离和曼哈顿距离来计算对象间的相异度.(2)比照例标度变量进行对数变换,例如对象i的变量f的值％变换为yif=log(xif),变换得到的yif可以看作区间值.(3)将xif看作连续的序数数据,将其秩作为区间值来对待.(e)非数值向量对象答：为了测量复杂对象间的距离,通常放弃传统的度量距离计算,而引入非度量的相似度函数.例如,两个向量x和y,可以将相似度函数定义为如下所示的余弦度量:s(x,y)=其中,x,是向量x的转置,Hx|是向量x的欧几里得范数,|y|是向量y的欧几里得范数,s本质上是向量x和y之间夹角的余弦值.7.5简略描述如下的聚类方法：划分方法、层次方法、基于密度的方法、基于网格的方法、基于模型的方法、针,高维数据的方法和基于约束的方法.为每类方法给出例子.(1)划分方法：给定n个对象或数据元组的数据可,划分方法构建数据的k个划分,每个划分表示一个簇,k<=n.给定要构建的划分数目k,划分方法创立一个初始画风.然后采用迭代重定位技术,尝试通过对象在组间移动来改进划分.好的划分的一般准那么是：在同一个簇的对象间互相“接近〞和相关,而不同簇中的对象之间“远离〞或不同.k均值算法和k中央点算法是两种常用的划分方法.(2)层次方法：层次方法创立给定数据对象集的层次分解.根据层次的分解的形成方式,层次的方法可以分类为凝聚的或分裂的方法.凝聚法,也称自底向上方法,开始将每个对象形成单独的组,然后逐次合并相近的对象或组,直到所有的组合并