数据挖掘第三版课后题答案 | 您所在的位置:网站首页 › 数据分析与数据挖掘喻梅课后答案 › 数据挖掘第三版课后题答案 |
写在前面
该文为数据挖掘概念与技术第三版课后习题的答案,部分参考了第二版的英文答案,由于个人水平有限,如若存在纰漏,请在评论区批评指正。另外,由于本次编辑格式较乱,可在资源下载区下载PDF版本以便参考。 第一章 引论什么是数据挖掘?在你的回答中,强调以下问题: 1) 它是又一种噱头吗? 2) 它是一种从数据库、统计学、机器学习和模式识别发展而来的技术的简单转换或应用吗? 3) 我们提出了一种观点,说数据挖掘是数据库技术进化的结果。你认为数据挖掘也是机器学习研究进化的结果吗?你能基于该学科的发展历史提出这一观点吗?针对统计学和模式识别领域,做相同的事情。 4) 当把数据挖掘当做知识发现过程时,描述数据挖掘所涉及的步骤。 数据挖掘指从大量数据中挖掘出有趣模式和知识的过程或方法。 数据挖掘不是另一种噱头,数据挖掘的兴起是由于海量数据及其转化为有效信息和知识的需求。因此,数据挖掘作为信息技术的自然革命的一个结果。 数据挖掘比从数据库、统计学等简单转换或应用更复杂。数据挖掘是数据库、神经网络、机器学习、高性能计算、模式识别、数据可视化等的集成和综合。 机器学习与数据挖掘高度相关,机器学习模型通常非常强调准确性,而数据挖掘则强调挖掘方法在大型数据集上的有效性和可收缩性,以及处理复杂数据类型的方法,开发新的非传统方法;统计学研究数据的收集、分析、解释和表示,与数据挖掘具有天然联系;统计学方法可以用来验证数据挖掘结果等。因此可以说数据挖掘是统计学技术进步的结果;模式识别重在认识事物,数据挖掘重在发现知识,因此可以说数据挖掘是一种方法,用于模式识别。 数据挖掘作为知识发现过程时,步骤有:1)数据清理;2)数据集成;3)数据选择;4)数据转换;5)数据挖掘;6)模式评估;7)知识表示。 数据仓库与数据库有何不同?它们有哪些相似之处? 数据库是由一组内部相关的数据和一组管理和存取数据的软件程序组成;数据仓库是一个从多个数据源手机的信息存储库。不同点是数据库由表组成,数据仓库是由数据立方体的多维数据结构建模。相似点在于数据库和数据仓库都可以存储数据,都是数据分析和挖掘的信息源。 定义以下数据挖掘功能:特征化、区分、关联和相关性分析、分类、回归、聚类、离群点分析。使用你熟悉的现实生活中的数据库,给出每种数据挖掘功能的例子。 数据特征化是目标类数据的一般特性或者特征的汇总。例如可以通过收集销量在前10%的物品的信息,再进行特征汇总。 数据区分是将目标类数据对象的一般特性与一个或多个对比类对象的一般特性进行比较。例如将销量增加10%和销量减少30%的物品放在一起进行比较。 数据分类是找出描述和区分数据类或概念的模型,以便能够使用模型预测类标号位置的对象的类标号。例如找出描述销量增加30%和销量减少30%的物品,通过对其特征进行描述和建模,再对一个新的物品根据其特征将其分类。 回归建立连续值函数模型,用于预测缺失的难以确定的数据值。例如补全未采样的数据。 聚类根据最大化类内相似性、最小化类间相似性的原则分析数据对象,但不进行类标号。例如可以对客户数据进行分析,以簇形式表示每个购物目标群。 离群点分析指研究那些与数据的一般行为或模型不一致的数据离散点,可以从中挖掘某种模式。例如使用离群点分析发现信用卡诈骗使用活动。 给出一个例子,其中数据挖掘对于工商企业的成功是至关重要的。该工商企业需要什么数据挖掘功能?这种模式能够通过简单的查询处理或统计分析得到吗? 以百货商店为例,可以使用数据挖掘去开展商业目标邮件活动,可以使用聚类方法去找出商品的特定消费人群的特征,进而给与该类人群相似的顾客发送该商品促销邮件。此时简单的查询处理不能找出特定人群特征,同样,统计分析不能处理该百货商店里大量的顾客数据记录。 解释区分和分类、特征化和聚类、分类和回归之间的区别和相似之处。 区分指的是将目标类数据的一般特性和一个或多个对比类对象的一般特性进行比较,即找出两者之间的特征区别;分类指的是找出一种模型来描述和区分数据类型或概念,并预测类标号未知的对象的类标号。两者的相似性在于他们都要对目标类数据对象进行处理和分析,输出结果都是类别特征,这些类别是预先指定的。 特征化是对目标类数据的的一般特性或特征的汇总;聚类是指对数据对象在不考虑明确标签分类下的情况下进行分析。两者的相似处在于他们都刻画目标的总体特征。 分类用于找出一种模型来描述和区分数据类型或概念,并预测类标号未知的对象的类标号;而回归则是建立一个连续值函数模型,而不是离散、无序的标号。相似点在于两者都是用函数进行预测。 根据你的观察,描述一个可能的知识类型,它需要由数据挖掘方法发现,但未在本章中列出,他需要一种不同于本章列举的数据挖掘技术吗? 建立一个周期性的知识类型,在不同时间段内数据会更新和修改,但是会发生重复性动作。此时要从时间出发,使用一种新的数据挖掘技术。 以欺诈检测为例,提出两种可以用来检测离群点的方法,并讨论哪种方法更可靠。 1) 使用聚类方法,在进行聚类分析之后,不同的簇代表着不同的数据类型,离散点不在簇的范围内。聚类分析是最有效的检测离群点的方法。 2) 使用回归方法,基于全体数据建立一个可能的数据预测模型,如果一个值极大偏离回归值,可以认为该数据是一个离散点。 描述三个关于数据挖掘方法和用户交互问题的数据挖掘挑战。 1) 处理不同的知识类型:不同的用户对不同的知识类型感兴趣,可能以不同的方式使用同一个数据库,并且需要不同的数据挖掘技术。 2) 挖掘多维空间中的知识:我们需要通过返回的结果给出和定义数据挖掘的要求,并在多维数据立方体中从不同角度和组合搜索有趣的知识模式。 3) 跨学科的背景知识:背景知识能能够有助于帮助人们去分析、发现和表达发现的模式对于多学科的作用。 与挖掘少量数据相比,挖掘海量数据的主要挑战是什么? 一方面是数据挖掘算法的有效性和可伸缩性,即数据挖掘算法的运行时间必须是可预计的、短的和可以被应用接受的。 另一方面是并行、分布式和增量挖掘算法,即海量数据引起的计算复杂性促进了并行和分布式数据密集型挖掘算法。 概述在诸如流/传感器数据分析、时空数据分析或生物信息学某个特定引用领域中的数据挖掘的主要挑战? 在生物信息学中,由于对某些生物对象、染色体序列、生物学网络和染色体的数据结构可能同时存在,对数据的清理和集成、一种数据的多个数据源之间的复杂相互作用给数据挖掘带来了巨大挑战。 第二章 认识数据 再给三个用于数据散布的常用特征度量(即未在本章讨论的),并讨论如何在大型数据库中有效的计算它们。 异众比率(variation ratio):主要用于衡量众数对一组数据的代表程度。异众比率越大,说明非众数组的频数占频数的比重越大,众数的代表性就越差;反之说明众数的代表性越好。异众比率主要适合测度分类数据的离散程度。 12其中∑▒f_i 表示变量值的总频数,∑▒f_m 表示众数组的频数。 标准分数:变量值与其平均数的差除以标准差后的值。给出了一组数据中各数值的相对位置。实际上,z分数只是将原始数据进行了线性变换,并没有改变一个数据在该组数据中的位置,也没有改变该组数据的分布形状。 离散系数:一组数据的标准差与其相应的平均数之比称为离散系数,也称变异系数。为了消除变量水平高低(即两个相同类型的属性其值分布差别特别大,比如一个为几百万,而另一个为几万或几十万)和计量单位不同对离散程度测量值的影响,需要计算离散系数。离散系数越小,说明数据离散程度越小;反之则说明数据离散程度越大。其计算公式为:假设所分析的数据包括属性age,它在数据元组中的值(以递增序)为13,15,16,16,19,20,20,21,22,22,25,25,25,25,30,33,33,35,35,35,35,36,40,45,46,52,70. 该数据的均值是多少?中位数是什么? 12345该组数据均值是29.963,中位数是25。 该数据的众数是什么?讨论数据的模态(即二模、三模等)。 该数据的众数是25和35,是一个双峰的分布,即二模。 该数据的中列数是多少? 该数据的中列数是(70+13)/2=41.5。 你能粗略地找出该数据的第一个四分位数(Q1)和第三个四分位数(Q3)吗? 第一个四分位数为[27/4]=7处,Q1=20,;第三个四分位数为21处,Q3=35。 给出该数据的五数概括。 五数概括即中位数25,四分位数Q120,第三个四分位数Q335,最大观测值70和最小观测值13。 绘制该数据的盒图。
age的均值为46.44,中位数为(50+52)/2=51,标准差为12.85; %fat的均值为28.78,中位数为(31.2+34.6)/2=32.9,标准差为8.99。 绘制age和%fat的盒图。 其中p为刻画对象的属性总数,m是匹配的数目。 非对称的二元属性。 使用二元属性的列联表进行计算,计算公式如下: 其中,r为在对象i中取1、在对象j中取0的属性数;s为在对象i中取0、对象j中取1的属性数;q为在对象i和j中都去1的属性数,即两个值都取1的正匹配更有意义的情况下。 数值属性。 使用闵可夫斯基 距离进行计算,即欧几里得距离和曼哈顿距离的推广。 其中,h是实数,h≥1。 词频向量。 使用余弦相似度进行计算,其计算公式如下: 给定两个元祖(22,1,42,10)和(20,0,36,8)表示的对象。 计算这两个对象之间的欧几里得距离。 12d=√(2&〖(22-20)〗2+〖(1-0)〗2+〖(42-36)〗2+〖(10-8)〗2 )≈6.7 计算这两个对象之间的曼哈顿距离。 d=|22-20|+|1-0|+|42-36|+|10-8|=11 使用q=3,计算这两个对象之间的闵可夫斯基距离。 d=∛(〖(22-20)〗3+〖(1-0)〗3+〖(42-36)〗3+〖(10-8)〗3 )≈6.15 计算这两个对象之间的上确界距离。 中位数是数据分析中最重要的整体度量之一。提出几种中位数近似计算方法。在不同的参数设置下,分析它们各自的复杂度,并确定它们的实际相似程度。此外,提出一种启发式策略,平衡准确性与复杂性,然后把它用于你给出的所有方法。 1通过查阅资料,很难查找到有效信息,对比原英文书的问题进行比较,发现应该是再找出几种方法描述数据分散程度。原书答案中使用的是平均偏差、偏态(skewness)和离散系数(the coefficient of variation)进行描述。 在数据分析中,最重要的是选择相似性度量。然而,不存在广泛接受的主观相似性度量,结果可能因所用的相似性度量而已。尽管如此,在进行某种变换后,看来似乎不同的相似性度量可能等价。假设我们有如下二维数据集: 1
准确性:由于技术的限制或人为的失误,有些需要准确投入营销比如生日折扣等的商品可能会失去作用。 完整性:由于故意隐瞒和设置、转移数据时没有加入,有些需要完整信息的例如快递行业会在业务经营中遇到障碍。 一致性问题:由于某些不可抗因素导致的数据不一致,例如多个数据源命名不一致时会影响数据集成等。 其他两个尺度是可信性和时效性。 在现实世界是数据中,某些属性上缺失值得到元组是是比较常见的。讨论处理这一问题的方法。 忽略元组。 人工填写缺失值。 使用一个全局常量填充缺失值。 使用属性的中心度量(如均值或中位数)填充缺失值。 使用与给定元组属同一类的所有样本的属性均值或中位数。 使用最可能的值填充缺失值。在习题2中,属性age包括如下值(以递增序):13,15,16,16,19,20,20,21,22,22,25,25,25,25,30,33,33,35,35,35,35,35,35,36,40,45,46,52,70。 以深度为3的箱,用箱均值光滑以上数据。说明你的步骤,讨论这种技术对给定数据的效果。 将以上数据分为三个一组的箱为: 1234567891011(13,15,16) (16,19,20) (20,21,22) (22,25,25) (25,25,30) (33,33,35) (35,35,35,) (36,40,45) (46,52,70) 计算各个箱的平均值,给出以下结果。 (142/3,142/3, 142/3) (181/3,181/3,181/3) (21,21,21) (24, 24, 24,) (262/3,262/3,262/3) (332/3, 332/3,332/3) (35, 35, 35) (401/3, 401/3, 401/3) (56, 56, 56) 该方法在一定程度上光滑了噪声数据,但是在一定程度上还是会受到离群点的影响。 如何确定该数据中的离群点? 可以使用聚类检测,有相似特征的数据会聚集成一个簇,离簇较远的点可能是离群点。另外,还可以采用人机结合的方式,计算机将会给出疑似离群点,由人工进行复查确认是否需为离群点。 还有什么其他方法来光滑数据? 在分箱方法中,还可以通过箱中位数光滑、箱边界光滑等。或者使用回归技术和离群点分析技术。 讨论数据集成需要考虑的问题。 模式集成:涉及到实体识别问题,例如如何确认一个数据库中的customer_id和另一个数据库中的cust_number指的是同一个属性。 冗余数据:使用相关分析来解决数据库中的数据冗余问题。 数据值冲突的检测与处理:对于同一实体可能因为表示、尺度或编码不同导致属性值不同。如下规范化方法的值域是什么? 最小-最大规范化。 1234567[〖new_min〗_A,〖new_max〗_A] Z分数规范化。 [(v_min-A ̅)/σ_A ,(v_max-A ̅)/σ_A ] Z分数规范化,使用均值绝对偏差而不是标准差。 [(v_min-A ̅)/s_A ,(v_max-A ̅)/s_A ] 小数定标规范化。 (-1,1) 使用如下方法规范化如下数据组: 200, 300, 400, 600, 1000 令min=0,max=1,最小-最大规范化。 0.386 使用z分数规范化变换age35,其中age的标准差为12.70。 0.386 使用小数定标规范化变换age值35。 0.35 指出对于给定的数据,你愿意使用哪种方法。陈述你的理由。 在最大值和最小值确定的情况下,我更愿意使用最大-最小值规范,这样计算比较简单快速,且原来的数据不会改变太多。在数据的最大值和最小值不太明确的情况下使用均值绝对偏差的z分数规范,其鲁棒性更强。 使用习题4中给出的age和%fat数据,回答如下问题: 基于z分数规范化,规范化这两个属性。 5,10,11,13,15,35,50,55,72,92,204,215 使用如下各方法将它们划分为三个箱: 等频(等深)划分。 即划分为三个元素一样多的箱,即:
需要检查的个数为C_k^(k-1),暂时没有想到一个改进版本,猜测应该是做一个更加有效的剪枝或者检查手段。 6.2.2节介绍了由频繁项集产生关联规则的方法。提出一个更有效的方法。解释它为什么更有效。(考虑将习题3中的2和3的性质结合到你的设计中。) 1
首先找出频繁的1-项集,然后进行组合再找出频繁的2-项集,以此类推,有如下图(其中L表示频繁项集): 有效性比较:Apriori算法需要对数据库做多次扫描而FP-growth算法只需要一次扫描。Apriori的候选集产生代价较高(需要做多次自身连接),而FP-growth不需要生成任何候选集。 列举所有与下面的原规则匹配的强关联规则(给出支持度s和置信度c),其中X是代表顾客的变量,item是表示项的变量(如“A”,“B”等); ∀x∈transaction,buys(X,〖item〗_1 )∧buys(X,〖item〗_2 )⇒buys(X,item_3 ) [s,c] 数据库有4个事务。设min_sup=60%,min_conf=80%。 123
∀x∈transaction,buys(X,〖item〗_1 )∧buys(X,〖item〗_2 )⇒buys(X,item_3 ) [s,c] 列出最大k的频繁k项集(但不输出任何规则)。 k=3,且频繁3项集为{Wonder-Bread, Dairyland-Milk, Tasty-Pie},{Wonder-Bread, Sunset-Milk, Dairyland-Cheese}。 假定一个大型商店有一个事务数据库,分布在4个站点,每个成员数据库中的事务具有相同的格式T_j:{i_1,i_2,…,i_m};其中T_j是事务标识符,而i_k (1≤k≤m)是事务中购买的商品标识符。提出一种有效的算法,挖掘全局关联规则。可以给出你算法的要点。你的算法不必将所有的数据都转移到一个站点,并且不造成过度的网络通信开销。 1以下描述了一个简单算法: 在每个成员数据库中找到本地的频繁项集,用CF作为四个成员数据库中各自本地的频繁项集的集合。 在每个成员数据库中,计算出CF中本地频繁项集的支持度。 接下来在CF中计算全部的频繁项集的支持度,可以将四个成员数据库中项集支持度相加得到总的支持度,从而计算出支持度超过最小支持度阈值的频繁项集。 从频繁项集中推导出强关联规则。 假定大型事务数据库DB的频繁项集已经存储。讨论:如果新的事务集∆DB(增量地)加进,在相同的最小支持度阈值下,如何有效地挖掘(全局)关联规则? 1我们可以将∆DB和DB作为两部分进行考虑: 对于DB中的频繁项集,在∆DB扫描一次并增加计数以判断它们在更新后的数据库是否仍然频繁; 对于在∆DB中但不在DB中的频繁项集,扫描一次DB并增加计数以判断他们是否在更新后的数据库仍然频繁。 大部分频繁模式挖掘算法只考虑事务中的不同项。然而,一种商品在一个购物篮中多次出现,例如4块蛋糕3桶牛奶的情况,在销售数据分析中可能是重要的。考虑项的多次出现,如何有效地挖掘频繁项集?对著名的算法如Apriori算法、FP-growth算法,提出修改方案,以适应这种情况。 1考虑将一个项以及其出现的次数作为第一次处理中联合的一项,例如将{milk,3}作为一个项集。在第一次扫描单个频繁项集i时,如果i的最高次数超过了最小频繁阈值,例如(milk, 3)可能是一个频繁项集。对于(i, max_count)尝试找出k项集从1到max_count的计数(可以使用Apriori算法或者FP-growth算法)。例如在FP-growth算法中,一个(I, count)项可以使用一个节点表示,然而如果想要更高的效率,这样的一个节点可以再结合计数器存储更多的信息。 (实现项目)给出一个小例子表明强关联规则中的项实际上可能是负相关的。 123
树从单个根节点开始,该节点包含所有的训练元组。 如果元组中都为同一类,则该节点变成一个叶子节点,并以该类标记它。 否则,调用算法确定分裂准则。分裂准则使用启发或统计标准(如信息增益或基尼系数)来确定将元组划分成各自的类的最好方法。即分裂准则指定分裂属性,并给出分裂点或分裂子集。 节点N使用分裂准则进行标记并进行测试。对分裂准则的每个输出,由节点N生长一个分支,该节点的元组因此分类,有以下三种分类方法:(1)属性值是离散的,则分支对应的是A的取值;(2)属性值是连续的,取两个分支,对应于条件A≤split_point和A>split_point;(3)属性值是离散的且必须产生二叉分枝,测试形如“A∈S_A?”,其中S_A是A的分裂子集,是A中已知值的子集。 对于每个节点上的元组使用同样的算法进行递归形成决策树。 递归划分步骤终止条件是:(1)该节点所有元组都属于同一个类;(2)没有剩余的属性可以用来进一步划分元组,此时采用多数表决,将节点N转换成叶节点并使用元组中的大多数标记它;(3)给定的分支没有元组,此时用元组中的多数类创建一个叶节点。 在决策树归纳中,为什么树剪枝是有用的?使用独立的元组集评估剪枝有什么缺点? 1决策树可能出现过拟合的情况,即分支的产生会受到训练数据中的噪声和离群点等异常的影响,剪枝技术可以通过使用统计度量删除最不可靠的分支来里面这种过拟合。这样能够产生可靠、简洁的决策树以更快、更精确对数据进行分类。 使用独立的元组集进行剪枝的缺点是剪枝后的决策树可能不如原决策树具有代表性。如果独立的数据元组集是倾斜的,则形成的决策树在分类上将不是准确的。此外,使用独立元组集剪枝意味着更少的元组用于产生和测试该树,对于机器学习而言这是一个巨大缺点,对于大数据集的数据挖掘下也是如此。 给定决策树,选项有:(a)将决策树转换成规则,然后对结果规则剪枝;(b)对决策树剪枝,然后将剪枝后的树转换成规则。相比于(b),(a)的优点是什么? 1如果剪去一个子树,使用方法b可以完整删去一个子树;然而使用方法a如果剪去一个规则,我们可以删除它的所有前提条件,这更加严格。 计算决策树算法在最坏情况下的计算复杂度是重要的。给定数据集D,属性数n和训练元组数|D|,根据n和D来分析计算复杂度最多是n×|D|×log〖|D|〗。 1最差的情况就是我们需要使用尽可能多的元组来分出每个元组,对于一棵树来说最大深度是log〖|D|〗;在每一层我们需要使用所有的属性计算attribute_selection算法(每个属性计算一次),每一层所有的元组数是|D|,因此树中的每一层计算复杂度是O(n×|D|)。因此,整个流程需要的复杂度是O(n×|D|×log|D|)。 给定一个具有50个属性(每个属性包含100个不同值)的5GB的数据集,而你的台式机有512MB内存。简述对这种大型数据集构造决策树的一种有效算法。通过粗略地计算主存的使用说明你的答案是正确的。 1使用雨林算法,此时内存中需要存储的是以avc_set为根的树,计算avc_set的根节点,扫描一次数据库,构建avc_list的50个属性,每个属性具有100个不同的值,则需要的总大小是10050|C|(|C|表示每个值占据的空间大小),则对于一个合理的|C|能够使适应512M的大小。使用这种每个节点存储一部分avc-集的方法,我们或许可以适应内存的水平。 为什么朴素贝叶斯分类称为“朴素”的?简述朴素贝叶斯分类的主要思想。 1朴素贝叶斯被称为“朴素”是因为它假设条件独立分布,这个假设用于减少计算代价,因此称为“朴素”,其主要原理是通过后概率的贝叶斯定理使用P(X|C_i)P(C_i)得到最大值来对数据进行分类。 其主要步骤通过原书第三版P227描述。 下表由雇员数据库的训练数据组成。数据已泛化。例如,age“31…35”表示年龄在31~35之间。对于给定的行,count表示department、status、age和salary在该行上具有给定值的元组数。 1
RainForest是一种可伸缩的决策树归纳算法。开发一种可伸缩的朴素贝叶斯分类算法。对于大多数数据库,它只需要扫描整个数据集一次。讨论这种算法是否可以进一步求精,结合提升进一步调高分类的准确率。 在一次对数据库的扫描中,对于每个属性的值我们可以采用下面的表进行计数: 设计一种方法,对无限的数据流进行有效的朴素贝叶斯分类(即只能扫描数据流一次)。如果想发现这种分类模式的演变(例如,将当前的分类模式与较早的模式进行比较,如与一周以前的模式相比),你有何修改建议? 这种设计方法和上题类似,我们使用一个属性值计数表并在每个数据流输入的时候进行更新。 为了发现分类模式的演变,我们可以保持一个基于所有历史数据的分类器,一个基于过去一星期数据的分类器,一个基于过去一天的分类器。对于以周计算的分类器,我们保持过去七天每项的独立技术;在每天结束后,我们抛弃掉最老天数的数据并且使用刚过去的一天的数据替换。对于以天计算的分类器,类似的使用过去的一个小时的数据替代最早的一个小时的数据。 证明准确率是灵敏性和特效性度量的函数,即证明accuracy=sensitivity P/((P+N))+specificity N/((P+N))成立。
根据计算,可以得到如上图所示对应的TPR和FPR,绘制出来的表格如下: 我们可以使用假设检验去看平均错误率是否有明显不同。假设我们使用同样的测试数据做配对观察去比较平均误差: H_0: (x_1 ) ̅-(x_2 ) ̅=0 H_1: (x_1 ) ̅-(x_2 ) ̅≠0 其中,(x_1 ) ̅是M1的平均误差,(x_2 ) ̅是M2的平均误差。 我们使用下面公式进行计算: t=d ̅/(s_d/√n) 其中,d ̅是错误率差值的平均误差,s_d是标准误差,n是观察的样本数。在该题中可得d ̅=6.45,s_d=8.25,n=10,故得到t=2.47.使用t-分布表,我们查到probability为0.005且自由度为9的t_(α/2)为3.25,由于-3.25 |
CopyRight 2018-2019 实验室设备网 版权所有 |