数据挖掘课后答案

《数据挖掘课后答案》由会员分享，可在线阅读，更多相关《数据挖掘课后答案（18页珍藏版）》请在装配图网上搜索。

1、AA- *弟一章1 . 6(1) 数据特征化是目标类数据的一般特性或特征的汇总。例如，在某商店花费1000元以上的顾客特征的汇总描述是：年龄在40-50岁、有工作和很好的信誉 等级。(2) 数据区分是将目标类数据对象的一般特性与一个或多个对比类对象的一般特性进行比较。例如，高平均分数的学生的一般特点，可与低平均分数的学生的一般特点进行比较.由此产生的可能是一个 相当普遍的描述，如平均分高达75%的学生是大四的计算机科学专业的学生，而平均分低于65%的学生则 不是.(3) 关联和相关分析是指在给定的频繁项集中寻找相关联的规则.例如，一个数据挖掘系统可能会发现这样的规则：专业(X,计算机科学)二拥

2、有(X,个人电脑“) supports 12%, confidence = 98%,其中X是一个变量，代表一个学生，该规则表明，98%的置 信度或可信性表示，如果一个学生是属于计算机科学专业的，则拥有个人电脑的可能性是98%。12%的支持 度意味着所研究的所有事务的12%显示属于计算机科学专业的学生都会拥有个人电脑。(4) 分类和预测的不同之处在于前者是构建了一个模型(或函数)，描述和区分数据类或概念，而后者则建立 了一个模型来预测一些丢失或不可用的数据，而且往往是数值，数据集的预测。它们的相似之处是它们都是 为预测工具：分类是用于预测的数据和预测对象的类标签，预测通常用于预测缺失值的数值数据

3、。例如：某银行需要根据顾客的基本特征将顾客的信誉度区分为优良中差几个类别，此时用到的则是分类; 当研究某只股票的价格走势时，会根据股票的历史价格来预测股票的未来价格，此时用到的则是预测。(5) 聚类分析数据对象是根据最大化类内部的相似性、最小化类之间的相似性的原则进行聚类和分组。聚 类还便于分类法组织形式，将观测组织成类分层结构，把类似的事件组织在一起。例如：世界上有很多种鸟，我们可以根据鸟之间的相似性，聚集成门类，其中n可以认为规定.(6) 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。这可能包括时间相关数据的特征 化、区分、关联和相关分、分类、预测和聚类，这类分析的不同特点

4、包括时间序列数据分析、序列或周期模（完整word版）数据挖掘课后答案 式匹配和基于相似性的数据分析。例如：假设你有纽约股票交易所过去几年的主要股票市场（时间序列）数据，并希望投资高科技产业公司 的股票。股票交易数据挖掘研究可以识别整个股票市场和特定的公司的股票的演变规律。这种规律可以帮助 预测股票市场价格的未来走向，帮助你对股票投资做决策。1.11 一种是聚类的方法，另一种是预测或回归的方法。（1）聚类方法：聚类后，不同的聚类代表着不同的集群数据。这些数据的离群点，是不属于任何集群。在 各种各样的聚类方法当中，基于密度的聚类可能是最有效的。（2）使用预测或回归技术：构建一个基于所有数据的概率（

5、回归）模型，如果一个数据点的预测值有很大的不 同给定值，然后给定值可考虑是异常的.用聚类的方法来检查离群点更为可靠，因为聚类后，不同的聚类代表着不同的集群数据，离群点是不属于 任何集群的，这是根据原来的真实数据所检查出来的离群点。而用预测或回归方法，是通过构建一个基于所 有数据的（回归）模型，然后根据预测值与原始数据的值比较，当二者相差很大时,就将改点作为离群点处理， 这对所建立的模型有很大的依赖性，另外所建立的模型并不一定可以很好地拟合原来的数据，因此一个点在 可能某个模型下可能被当作离群点来处理，而在另外一个模型下就是正常点.所以用聚类的方法来检查离群点 更为可靠1.15挖掘海量数据的主要

6、挑战是：1）第一个挑战是关于数据挖掘算法的有效性、可伸缩性问题，即数据挖掘算法在大型数据库中运行时间必须 是可预计的和可接受的，且算法必须是高效率和可扩展的。2）另一个挑战是并行处理的问题，数据库的巨大规模、数据的广泛分布、数据挖掘过程的高开销和一些数据 挖掘算法的计算复杂性要求数据挖掘算法必须具有并行处理的能力，即算法可以将数据划分成若干部分，并行处理，然后合并每一个部分的结果。第二章2 . 11三种规范化方法:（1）最小一最大规范化（min-max规范化）：对原始数据进行线性变换，将原始数据映射到一个指定的区间。V，v min /(new _ max- new _ min) + new _

7、 min max- min（2）z-score规范化（零均值规范化）：将某组数据的值基于它的均值和标准差规范化，是其规范化后的均值为0方差为1。v，= 二殳，其中H是均值，b是标准差 b（3）小数定标规范化:通过移动属性A的小数点位置进行规范化。） 1的最小整数其中，j是使得Max 10 j（a）minmax 规范化v 一 min / (new max一 minmax一 newmin) + new _ min其中v是原始数据，min和max是原始数据的最小和最大值,new_max和new_min是要规范化到的区原始数据20030040060010000,1规范化00。1250.250.51间的

8、上下限（b）zscore 规范化v，= v - p，其中p是均值，b是标准差 b200 + 300 + 400 + 600 +1000 ecpi = 5001000在初始设置中是否 还有更多的属性？所选属性是否超出停止界限？开始.(200-500)2 + (300-500)2 + (400-500)2 + (500-500)2 + (1000-500)2 。b | 282.842752.13(1)逐步向前选择结束是是否否把选中的属性添加到归 约集中以减少属性设置初始化属性集，设置初始归约集为空集确定原属性集中最好的属性原始数据2003004006001000zscore-1.060.7-0.3

9、50。351.78（2）逐步向后删除所选属性是否 超出停止界限？在初始设置中有 更多的属性设置？是否是否删除选中的最差属性，以减少 属性的设置初始化属性设置为整 个属性集确定原属性集中最差的属性（3）向前选择和向后删除的结合第三章3。2简略比较以下概念，可以用例子解释你的观点（a ）雪花形模式，事实皇座形、星形网查询模型.答：雪花形和事实星形模式都是变形的星形模式，都是由事实表和维表组成雪花形模式的维表都是规范 化的;而事实星座形的某几个事实表可能会共享一些维表;星形网查询模型是一个查询模型而不是模式模型, 它是由中心点发出的涉嫌组成其中每一条射线代表一个维的概念分层。（皿数据清理、数据变换，

10、刷新答：数据清理是指检测数据中的错误，可能时订正它们;数据变换是将数据由遗产或宿主格式转换成数据仓库格式；刷新是指传播由数据源到数据仓库的更新。（a）雪花形模式图如下:（见74页）course维表univ fact tablestudent 维表area维表course_idcoursenamedepartmentarea_idstudentidcourseidsemesteridstudentidstudentnameareaidmajorcityprovincecountrysemester_idsemesterInstructoridstatuscountuniversityyearav

11、g_gradeInstructor 维表Instructor_iddeptrank（b）特殊的QLAP操作如下所示:（见79页）1) 在课程维表中，从course_id到department进行上卷操作；2) 在学生维表中，从student_id到university进行上卷操作；3) 根据以下标准进行切片和切块操作：department二CS and university二Big University;4 )在学生维表中，从university到student_id进行下钻操作。(c )这个立方体将包含5 = 625个长方体。(见课本88与89页)第五章5.1(a)假设s是频繁项集，min_

12、sup表示项集的最低支持度，D表示事务数据库。由于s是一个频繁项集，所以有=suppcount(s) z min sup D假设s,是s 的一 非空子集，由于support_count ( s) support_sup(s ),故有sup port(s) = sup p_count(s) min sup D所以原题得证，即频繁项集的所有非空子集必须也是频繁的。(b )由定义知，sup port(s) = support_count(s)令s是s的任何一个非空子集，则有 sup port(s) = sup prot _count(s)由(a)可知，support(s ) sup prot(s),

13、这就证明了项集s的任意非空子集s的支持度至少和s的支 持度一样大。(c)因为 confidence(s = l - s)=P(), confidence(s = l - s) = )P( s)p (s)根据(6)有 p( s ) =p(s)所以confidences = 1 - s) confidences，= l - s)即s = (l- s)”的置信度不可能大于s = (1 s)”(d)反证法：即是D中的任意一个频繁项集在D的任一划分中都不是频繁的假设D划分成d , d , d ,设Id I = C , d = C,.，|d = C ，min_sup表示最小支持度，12n 11221 nn

14、-C=D = C1 + C2 + CNF是某一个频繁项集，A = |F|， A C x min_ sup ，D = d设F的项集在d , d ,d中分别出现a ,a ,a次 12 n12 n所以 A= a + a + . + an(*)故A C x min_ sup =(C + C + . + Cx min_ sup)n a + a + a (C + C + C ) x min_ sup12几 12NF在D的任意一个划分都不是频繁的a C x min_sup, a C x min_sup，a C x min_sup 1122n n:.(a + a + a ) (C + C + C ) x mi

15、n_ supn A i i ：山 ( TUJ， z( T : o 7 a 7 1 7 1：OUJP 1)Conditional pattern base7KK3K.e 43 ,33Conditional treekb3kkofeW，亍4自丁切kep3Frequent pattern- APz.orM甫&淄 xsesffisM令粗%3mffi、aFPfi木M甫制吁ffl-B%mffi的FP树上。在Aprior算法中生成的候选项集是昂贵的（需要自身的自连接），而FP-growth不会产生任何 的候选项集。所以FP算法的效率比先验算法的效率要高。（b）k，。* e0.6,1e, o k0. 6,15

16、.6个全局的关联规则算法如下：1）找出每一家商店自身的频繁项集。然后把四个商店自身的频繁项集合并CF项集；2）通过计算四个商店的频繁项集的支持度，然后再相加来确定CF项集中每个频繁项集的总支持度即全局的 支持度。其支持度超过全局支持度的项集就是全局频繁项集.3）据此可能从全局频繁项集发现强关联规则。5。14support(hotdogs n humbergers)(a) =(hotdogs c hamburgers) = 2000 =4% 25% 500050002000 = 67% 50% 3000p(hotdogs, hamburgers)confidence =p(hotdogs)所以该

17、关联规则是强规则.corr(hotdogs, hamburgers)=(b)2000 5000p(hotdogs, hamburgers) p(hotdogs)p(hamburgers) 0.441= 1 3000 5000 x 2500 50000. 6 x 2.53所以给定的数据，买hot dogs并不独立于hamburgers,二者之间是正相关。5.191）挖掘免费的频繁1项集，记为S12 ）生成频繁项集S2，条件是商品价值不少于$200 （使用FP增长算法）3 ）从S1S2找出频繁项集（完整word版）数据挖掘课后答案4 ）根据上面得到的满足最小支持度和置信度的频繁项集，建立规则S1二

18、S2弟六章6。1简述决策树的主要步骤答：假设数据划分D是训练元组和对应类标号的集合1）树开始时作为一个根节点N包含所有的训练元组；2）如果D中元组都为同一类，则节点N成为树叶，并用该类标记它；3）否则，使用属性选择方法确定分裂准则。分裂准则只当分裂属性和分裂点或分裂子集。4）节点N用分裂准则标记作为节点上的测试。对分裂准则的每个输出，由节点N生长一个分枝。D中元组厥词进行划分.（1）如果A是离散值，节点N的测试输出直接对应于A的每个已知值。（2）如果A是连续值的，则节点N的测试有两个可能的输出，分别对应于A split _ point .（3）如果A是离散值并且必须产生二叉树，则在节点N的测试

19、形如“ A e七”， 七是A的分裂子集。如果给定元组有A的值%，并且a, e Sa，则节点N的测试条件满足，从 N生长出两个分枝。5）对于D的每个结果划分。，使用同样的过程递归地形成决策树。6）递归划分步骤仅当下列条件之一成立时停止：（1）划分D的所有元组都属于同一类；（2）没有剩余的属性可以进一步划分元组；（3 ）给定分枝没有元组。6。4计算决策树算法在最坏情况下的计算复杂度是重要的.给定数据集D,具有n个属性和| D|个训练元 组，证明决策树生长的计算时间最多为n x D xlog“|）证明：最坏的可能是我们要用尽可能多的属性才能将每个元组分类，树的最大深度为log（|D|）在 每一层，必

20、须计算属性选择O（n）次，而在每一层上的所有元组总数为|D|,所以每一层的计算时 间为O（nx | D I），因此所有层的计算时间总和为(完整word版)数据挖掘课后答案O(n x D x log P(C I X)1 j m, j。i，因此12miij我们要最大化P(C I X) = P(X CPC)，由于P(X)对于所有类为常数，因此只需要P(X I C )P(C )最大iP( X)ii即可。如果类的先验概率未知，则通过假定这些类是等概率的，即P(C ) = P(C2) = .(C )，并据此对P(X I C )最大化，否则，最大化P(X I C )P(C )，类的先验概率可以用P(C )

21、= iC汁1估计。其中IC I是D中ii ii I D Ii, DC 类的训练元组数。(c)假定属性值有条件地相互独立，则iP( X I C )=计 P( x I C ) = P (x I C ) x P( x I C ) x x P( x I C )，如果 A 是分类属性，则 P( x I C )是D 中ik i1 i2 in ikk ik=1属性A的值为x的C类的元组数除以D中C类的元组数I C I;如果A是连续值属性，则P(x I C )由高斯kk iii, Dkk i分布函数决定.6.13给定k和描述每个元组的属性数n,写一个k最近邻分类算法.算法：输入：(1)设U是待分配类的元组；(

22、2)T 是一个训练元组集，包括 T = (t ，t，t )，T = (t , t ,t ), T = (t , t ，,t )11,1 1,21,n22,1 2,22,nmm,1 m,2m,n(3) 假设属性tin是T的类标签；(4) m为训练元组的个数；(5) n为每个元组的描述属性的个数；(6)k是我们要找的最邻近数。输出：U的分类标签算法过程：(1) 定义矩阵am2o/(m行是存储与m个训练元组有关的数据，第一列是存储待分类元组U与训练元组的欧几里得距离，第二列是存储训练元组的序号)(2) for i = 1 to m do fai1 = Euclidean distance ( U;

23、Ti);ai2 = i;g / save the index, because rows will be sorted later(3) 将ai1 按升序排列。(4 )定义矩阵bk 2L /第一列包含的K 近邻不同的类别，而第二列保存的是它们各自频数(5 ) for i = 1 to k do fif类标签tai 2;n已经存在于矩阵b中then矩阵b中找出这个类标签所在的行，并使其对应的频数增加1eles将类标签添加到矩阵b可能的行中，并使其对应的频数增加1(6) 将矩阵b按类的计数降序排列(7) 返回b(1)。/返回频数最大的类标签作为U的类标签.第七章7.1简单地描述如何计算由如下类型的

24、变量描述的对象间的相异度：(a) 数值(区间标度)变量答：区间标度变量描述的对象间的相异度通常基于每对对象间的距离计算的，常用的距离度量有欧几里得距离和曼哈顿距离以及闵可夫基距离。欧几里得距离的定义如下：d (i, j) = (I. 丁.)+ (. X. ) H (.卜.)其中i = (x ,X ,X )和j = (X ,X，,X )是两个n维数据对象。 i1 i 2 inj1 j 2 jn曼哈顿距离的定义:d(i, j) = x - x + x - x + X - Xi1 j1 x 2j 2in jn闵可夫基距离的定义：d (i, j) = (x - x + x - x p +i1j1x 2

25、j 2(b) 非对称的二元变量答:如果二元变量具有相同的权值，则一个二元变量的相依表如下:10和1qrq + r0sts+t和q+sr+tP对象j对象i在计算非对称二元变量的相异度时，认为负匹配的情况不那么重要,因此计算相异度时可以忽略，所以二元变 量的相异度的计算公式为：d (i, j) = r + q + r + s(c) 分类变量 答：分类变量是二元变量的推广，它可以取多于两个状态值。两个对象i和j之间的相异度可以根据不匹配率来计算：d(i, j) = p-m，其中m是匹配的数目(即对i和j取值相同状态的变量的数目)，而p是全部变量 P的数目。另外，通过为M个状态的每一个创建一个二元变量

26、，可以用非对称二元变量对分类变量编码。对于一个具有给定状态值的对象，对应于该状态值的二元变量置为1，而其余的二元变量置为0。(d) 比例标度变量答：有以下三种方法：(1) 将比例标度变量当成是区间标度标量，则可以用闽可夫基距离、欧几里得距离和曼哈顿距离来计算 对象间的相异度。(2) 对比例标度变量进行对数变换，例如对象i的变量f的值x变换为v =log(x )，变换得到的v可ifififif以看作区间值。(3) 将xf看作连续的序数数据，将其秩作为区间值来对待。(e )非数值向量对象答：为了测量复杂对象间的距离，通常放弃传统的度量距离计算，而引入非度量的相似度函数。例如，两个向量x和y，可以将

27、相似度函数定义为如下所示的余弦度量：心,J)=苔其中，X是向量x的转置，X是向量x的欧几里得范数|y|是向量y的欧几里得范数，s本质上是向量x和y 之间夹角的余弦值。7.5简略描述如下的聚类方法：划分方法、层次方法、基于密度的方法、基于网格的方法、基于模型的方法、 针对高维数据的方法和基于约束的方法。为每类方法给出例子。(1)划分方法：给定个对象或数据元组的数据可，划分方法构建数据的k个划分，每个划分表示一个簇， k = n.给定要构建的划分数目k,划分方法创建一个初始画风.然后采用迭代重定位技术，尝试通过对象在组 间移动来改进划分。好的划分的一般准则是：在同一个簇的对象间互相接近和相关，而不

28、同簇中的对象 之间远离”或不同。k均值算法和k中心点算法是两种常用的划分方法。(2 )层次方法:层次方法创建给定数据对象集的层次分解。根据层次的分解的形成方式，层次的方法可以分 类为凝聚的或分裂的方法。凝聚法，也称自底向上方法，开始将每个对象形成单独的组，然后逐次合并相近的 对象或组，直到所有的组合并为一个，或者满足某个终止条件。分裂法，也称自顶向下方法，开始将所有的对 象置于一个簇中。每次迭代，簇分裂为更小的簇，直到最终每个对象在一个簇中，或者满足某个终止条件.(3)基于密度的方法：主要是想是：只要邻域”中的密度(对象或数据点的数目)超过某个阈值，就继续聚 类。也就是说，对给定簇中的每个数据

29、点，在给定半径的邻域中必须至少包含最少数目的点。这样的方法可 以用来过滤噪声数据(离群点)，发现任意形状的簇。DBSCAN和OPTICS方法是典型的基于密度的聚类方法.(4 )基于网格的方法:基于网格的方法把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类 操作都在这个网格结构上进行。这种方法的主要优点是处理速度很快，其处理时间通常独立于数据对象的数 目，仅依赖于量化空间中每一维的单元数目。STING是基于网格方法的典型例子。(5)基于模型的方法:基于模型的方法为每簇坚定一个模型，并寻找数据对给定模型的最佳拟合。基于模型（完整word版）数据挖掘课后答案 的算法通过构建反映数据点空间

30、分布的密度函数来定位簇.它也导致基于标准统计量自动地确定簇的数目，考虑噪声”数据和离群点的影响，从而产生鲁棒的聚类方法。COBWEB和SOM是基于模型方法的示例。7.7 k均值和k中心点算法都可以进行有效的聚类。概述k均值和k中心点算法的优缺点。并概述两种方法 与层次聚类方法（如AGBES）相比的优缺点。答：（1）:k均值和k中心点算法的优缺点：k中心点算法比k均值算法更鲁棒性，这是因为中线点不想均值 那样容易受离群点或其他极端值影响。然而，k中心点方法执行代价比k均值算法高.（2）k均值和k中心点算法与层次聚类方法（如AGBES）相比的优缺点:寸匀值和k中心点算法都是划分的聚类 方法，它们的优点是在聚类是它们前面的步骤可以撤销，而不像层次聚类方法那样，一旦合并或分裂执行 就不能修正，这将影响到聚类的质量。k均值和k中心点方法对小数据集非常有效，但是对大数据集没有良好 的可伸缩性，另外的一个缺点是在聚类前必须知道类的数目。而层次聚类方法能够自动地确定类的数量，但 是层次方法在缩放时会遇到困难，那是因为每次决定合并或分裂时，可能需要一定数量的对象或簇来审核与评 价。改善层次聚类方法有：BIRCH , ROCK和 Chameleon算法