数据挖掘课后答案.doc

第一章16（1）数据特征化是目标类数据的一般特性或特征的汇总。例如，在某商店花费1000元以上的顾客特征的汇总描述是：年龄在4050岁、有工作和很好的信誉等级。（2）数据区分是将目标类数据对象的一般特性与一个或多个对比类对象的一般特性进行比较。例如，高平均分数的学生的一般特点，可与低平均分数的学生的一般特点进行比较。由此产生的可能是一个相当普遍的描述，如平均分高达75的学生是大四的计算机科学专业的学生，而平均分低于65%的学生则不是。（3）关联和相关分析是指在给定的频繁项集中寻找相关联的规则。例如，一个数据挖掘系统可能会发现这样的规则：专业（X，“计算机科学”）=拥有（X，”个人电脑“）support= 12，confidence = 98，其中X是一个变量，代表一个学生，该规则表明，98%的置信度或可信性表示，如果一个学生是属于计算机科学专业的，则拥有个人电脑的可能性是98%。12%的支持度意味着所研究的所有事务的12%显示属于计算机科学专业的学生都会拥有个人电脑。（4）分类和预测的不同之处在于前者是构建了一个模型（或函数），描述和区分数据类或概念，而后者则建立了一个模型来预测一些丢失或不可用的数据，而且往往是数值，数据集的预测。它们的相似之处是它们都是为预测工具：分类是用于预测的数据和预测对象的类标签，预测通常用于预测缺失值的数值数据。 例如：某银行需要根据顾客的基本特征将顾客的信誉度区分为优良中差几个类别，此时用到的则是分类；当研究某只股票的价格走势时，会根据股票的历史价格来预测股票的未来价格，此时用到的则是预测。（5）聚类分析数据对象是根据最大化类内部的相似性、最小化类之间的相似性的原则进行聚类和分组。聚类还便于分类法组织形式，将观测组织成类分层结构，把类似的事件组织在一起。 例如：世界上有很多种鸟，我们可以根据鸟之间的相似性，聚集成n类，其中n可以认为规定。（6）数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。这可能包括时间相关数据的特征化、区分、关联和相关分、分类、预测和聚类，这类分析的不同特点包括时间序列数据分析、序列或周期模式匹配和基于相似性的数据分析。 例如：假设你有纽约股票交易所过去几年的主要股票市场（时间序列）数据，并希望投资高科技产业公司的股票。股票交易数据挖掘研究可以识别整个股票市场和特定的公司的股票的演变规律。这种规律可以帮助预测股票市场价格的未来走向，帮助你对股票投资做决策。111 一种是聚类的方法，另一种是预测或回归的方法。（1）聚类方法：聚类后，不同的聚类代表着不同的集群数据。这些数据的离群点，是不属于任何集群。在各种各样的聚类方法当中，基于密度的聚类可能是最有效的。（2）使用预测或回归技术：构建一个基于所有数据的概率（回归）模型，如果一个数据点的预测值有很大的不同给定值，然后给定值可考虑是异常的。 用聚类的方法来检查离群点更为可靠，因为聚类后，不同的聚类代表着不同的集群数据，离群点是不属于任何集群的，这是根据原来的真实数据所检查出来的离群点。而用预测或回归方法，是通过构建一个基于所有数据的（回归）模型，然后根据预测值与原始数据的值比较，当二者相差很大时，就将改点作为离群点处理，这对所建立的模型有很大的依赖性，另外所建立的模型并不一定可以很好地拟合原来的数据，因此一个点在可能某个模型下可能被当作离群点来处理，而在另外一个模型下就是正常点。所以用聚类的方法来检查离群点更为可靠115挖掘海量数据的主要挑战是：1） 第一个挑战是关于数据挖掘算法的有效性、可伸缩性问题，即数据挖掘算法在大型数据库中运行时间必须是可预计的和可接受的，且算法必须是高效率和可扩展的。2） 另一个挑战是并行处理的问题，数据库的巨大规模、数据的广泛分布、数据挖掘过程的高开销和一些数据挖掘算法的计算复杂性要求数据挖掘算法必须具有并行处理的能力，即算法可以将数据划分成若干部分，并行处理，然后合并每一个部分的结果。第二章211 三种规范化方法：（1）最小最大规范化（min-max规范化）：对原始数据进行线性变换，将原始数据映射到一个指定的区间。（2）z-score规范化（零均值规范化）：将某组数据的值基于它的均值和标准差规范化，是其规范化后的均值为0方差为1。,其中是均值，是标准差（3）小数定标规范化：通过移动属性A的小数点位置进行规范化。 (a)min-max规范化其中v是原始数据，min和max是原始数据的最小和最大值，new_max和new_min是要规范化到的区间的上下限原始数据200 30040060010000,1 规范化00.1250.250.51(b)z-score规范化,其中是均值，是标准差原始数据2003004006001000z-score-1.06-0.7-0.350.351.782.13(1)逐步向前选择开 始初始化属性集，设置初始归约集为空集确定原属性集中最好的属性所选属性是否超出停止界限?把选中的属性添加到归约集中以减少属性设置否在初始设置中是否还有更多的属性?是是否结 束(2)逐步向后删除开 始初始化属性设置为整个属性集确定原属性集中最差的属性所选属性是否超出停止界限?否删除选中的最差属性,以减少属性的设置在初始设置中有更多的属性设置?是否是结束(3)向前选择和向后删除的结合选择最好的属性加入到归约集中，并在剩余的属性中删除一个最差的属性开 始初始化属性设置为空集确定原属性集中最好和最差的属性所选的最好的属性是否超出停止界限?否所选的最差的属性是否超出停止界限？合并设置为减少属性所设置的初始工作的所有剩余的属性是否从最初的工作集属性中删除选定属性在初始设置中是否有更多的属性设置?是否结 束是第三章3.2 简略比较以下概念，可以用例子解释你的观点（a）雪花形模式、事实星座形、星形网查询模型。答：雪花形和事实星形模式都是变形的星形模式，都是由事实表和维表组成，雪花形模式的维表都是规范化的；而事实星座形的某几个事实表可能会共享一些维表；星形网查询模型是一个查询模型而不是模式模型，它是由中心点发出的涉嫌组成，其中每一条射线代表一个维的概念分层。（b）数据清理、数据变换、刷新 答：数据清理是指检测数据中的错误，可能时订正它们；数据变换是将数据由遗产或宿主格式转换成数据仓库格式；刷新是指传播由数据源到数据仓库的更新。3.4(a)雪花形模式图如下：（见74页）course维表 univ fact table student维表 area维表 course_idcourse_namedepartmentarea_idcityprovincecountrystudent_idstudent_namearea_idmajorstatusuniversitystudent_idcourse_idsemester_idInstructor_idcountavg_grade Semester维表semester_idsemesteryear Instructor维表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)这个立方体将包含个长方体。（见课本88与89页）第五章5.1（a）假设s是频繁项集，min_sup表示项集的最低支持度，D表示事务数据库。由于s是一个频繁项集，所以有假设是s的一个非空子集，由于support_count()support_sup(s)，故有所以原题得证，即频繁项集的所有非空子集必须也是频繁的。（b）由定义知，令是s的任何一个非空子集，则有由（a）可知，support(),这就证明了项集s的任意非空子集的支持度至少和s的支持度一样大。（c）因为根据（b）有p()=p(s)所以 即“=(l- )”的置信度不可能大于“”（d）反证法：即是D中的任意一个频繁项集在D的任一划分中都不是频繁的假设D划分成，min_sup表示最小支持度，C=F是某一个频繁项集， ，设F的项集在中分别出现次所以A= 故 （*）这与（*）式矛盾从而证明在D中频繁的任何项集，至少在D的一个部分中是频繁。5.3最小支持度为3（a）Apriori方法 ：C1 L1 C2 L2 C3 L3oke3key2mk3ok3oe3ke4ky3mo1mk3me2my2ok3oe3oy2ke4ky3ey2m3o3k5e4y3m3o3n2k5e4y3d1a1u1c2i1okey3 FP-growth: RootK:5 E:4 M:1 M:2 O:2 Y:1 O:1 Y:1Y:1itemConditional pattern baseConditional treeFrequent patternyomek,e,m,o:1，k,e,o:1，k,m:1k,e,m:1，k,e:2k,e:2，k:1k:4K:3K:3，e:3K:3K:4k,y:3k,o:3，e,o:3，k,e,o:3k,m:3k,e:4这两种挖掘过程的效率比较：Aprior算法必须对数据库进行多次的扫描，而FP增长算法是建立在单次扫描的FP树上。在Aprior算法中生成的候选项集是昂贵的（需要自身的自连接），而FP-growth不会产生任何的候选项集。所以FP算法的效率比先验算法的效率要高。（b）5.6一个全局的关联规则算法如下：1） 找出每一家商店自身的频繁项集。然后把四个商店自身的频繁项集合并为CF项集；2） 通过计算四个商店的频繁项集的支持度，然后再相加来确定CF项集中每个频繁项集的总支持度即全局的支持度。其支持度超过全局支持度的项集就是全局频繁项集。3） 据此可能从全局频繁项集发现强关联规则。5.14（a）所以该关联规则是强规则。（b）所以给定的数据，买hot dogs并不独立于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的测试有两个可能的输出，分别对应于和。（3）如果A是离散值并且必须产生二叉树，则在节点N的测试形如“”，是A的分裂子集。如果给定元组有A的值，并且，则节点N的测试条件满足，从N生长出两个分枝。 5）对于D的每个结果划分，使用同样的过程递归地形成决策树。 6）递归划分步骤仅当下列条件之一成立时停止： （1）划分D的所有元组都属于同一类； （2）没有剩余的属性可以进一步划分元组； （3）给定分枝没有元组。6.4 计算决策树算法在最坏情况下的计算复杂度是重要的。给定数据集D，具有n个属性和|D|个训练元组，证明决策树生长的计算时间最多为证明：最坏的可能是我们要用尽可能多的属性才能将每个元组分类，树的最大深度为log(|D|),在每一层，必须计算属性选择O(n)次，而在每一层上的所有元组总数为|D|,所以每一层的计算时间为,因此所有层的计算时间总和为 ，即证明决策树生长的计算时间最多为6.5 为什么朴素贝叶斯分类称为“朴素”？简述朴素贝叶斯分类的主要思想。答：（1）朴素贝叶斯分类称为“朴素”是因为它假定一个属性值对给定类的影响独立于其他属性值。做此假定是为了简化所需要的计算，并在此意义下称为“朴素”。 （2）主要思想：（a）设D是训练元组和相关联的类标号的集合。每个元组用一个n维属性向量表示，描述由n个属性对元组的n个测量。另外，假定有m个类（b）朴素贝叶斯分类法预测X属于类C，当且仅当 ，因此我们要最大化，由于P（X）对于所有类为常数，因此只需要最大即可。如果类的先验概率未知，则通过假定这些类是等概率的，即，并据此对最大化，否则，最大化，类的先验概率可以用估计。其中是D中C类的训练元组数。（c）假定属性值有条件地相互独立，则，如果是分类属性，则是D中属性的值为的C类的元组数除以D中C类的元组数；如果是连续值属性，则由高斯分布函数决定。6.13 给定k和描述每个元组的属性数n,写一个k最近邻分类算法。算法：输入：（1）设U是待分配类的元组； （2）T是一个训练元组集，包括， （3）假设属性是的类标签； （4）m为训练元组的个数； （5）n为每个元组的描述属性的个数； （6）k是我们要找的最邻近数。输出：U的分类标签算法过程：（1）定义矩阵am2。/（m行是存储与m个训练元组有关的数据，第一列是存储待分类元组U与训练元组的欧几里得距离，第二列是存储训练元组的序号）（2）for i = 1 to m do fai1 = Euclidean distance(U; Ti); ai2 = i;g / save the index, because rows will be sorted later（3）将ai1按升序排列。（4）定义矩阵bk2。/第一列包含的K -近邻不同的类别，而第二列保存的是它们各自频数（5）for i = 1 to k do f if 类标签tai2;n 已经存在于矩阵b中 then矩阵b中找出这个类标签所在的行，并使其对应的频数增加1eles 将类标签添加到矩阵b可能的行中，并使其对应的频数增加1 （6）将矩阵b按类的计数降序排列 （7）返回b(1)./返回频数最大的类标签作为U的类标签。第七章7.1 简单地描述如何计算由如下类型的变量描述的对象间的相异度：（a）数值（区间标度）变量 答：区间标度变量描述的对象间的相异度通常基于每对对象间的距离计算的，常用的距离度量有欧几里得距离和曼哈顿距离以及闵可夫基距离。欧几里得距离的定义如下：其中和是两个n维数据对象。曼哈顿距离的定义：闵可夫基距离的定义：（b）非对称的二元变量 答：如果二元变量具有相同的权值，则一个二元变量的相依表如下： 对象 j10和1qrq+r0sts+t和q+sr+tp对象 i在计算非对称二元变量的相异度时，认为负匹配的情况不那么重要，因此计算相异度时可以忽略，所以二元变量的相异度的计算公式为：（c）分类变量答：分类变量是二元变量的推广，它可以取多于两个状态值。两个对象i和j之间的相异度可以根据不匹配率来计算：，其中m是匹配的数目（即对i和j取值相同状态的变量的数目），而p是全部变量的数目。另外，通过为M个状态的每一个创建一个二元变量，可以用非对称二元变量对分类变量编码。对于一个具有给定状态值的对象，对应于该状态值的二元变量置为1，而其余的二元变量置为0.（d）比例标度变量答：有以下三种方法： （1）将比例标度变量当成是区间标度标量，则可以用闽可夫基距离、欧几里得距离和曼哈顿距离来计算对象间的相异度。 （2）对比例标度变量进行对数变换，例如对象i的变量f的值变换为，变换得到的可以看作区间值。 （3）将看作连续的序数数据，将其秩作为区间值来对待。（e）非数值向量对象答：为了测量复杂对象间的距离，通常放弃传统的度量距离计算，而引入非度量的相似度函数。例如，两个向量x和y，可以将相似度函数定义为如下所示的余弦度量： 其中，是向量x的转置，是向量x的欧几里得范数，是向量y的欧几里得范数，s本质上是向量x和y之间夹角的余弦值。7.5 简略描述如下的聚类方法：划分方法、层次方法、基于密度的方法、基于网格的方法、基于模型的方法、针对高维数据的方法和基于约束的方法。为每类方法给出例子。（1）划分方法：给定n个对象或数据元组的数据可，划分方法构建数据的k个划分，每个划分表示一个簇，k=n。给定要构建的划分数目k，划分方法创建一个初始画风。然后采用迭代重定位技术，尝试通过对象在组间移动来改进划分。好的划分的一般准则是：在同一个簇的对象间互相“接近”和相关，而不同簇中的对象之间“远离”或不同。k均值算法和k中心点算法是两种常用的划分方法。（2）层次方法：层次方法创建给定数据对象集的层次分解。根据层次的分解的形成方式，层次的方法可以分类为凝聚的或分裂的方法。凝聚法，也称自底向上方法，开始将每个对象形成单独的组，然后逐次合并相近的对象或组，直到所有的组合并为一个，或者满足某个终止条件。分裂法，也称自顶向下方法，开始将所有的对象置于一个簇中。每次迭代，簇分裂为更小的簇，直到最终每个对象在一个簇中，或者满足某个终止条件。（3）基于密度的方法：主要是想是：只要“邻域”中的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对给定簇中的每个数据点，在