2011年数据挖掘与数据仓库考试题a

2011 年数据挖掘与数据仓库考试题 1 （10 分）讨论:：下列每项活动是否是数据挖掘任务 ?简单陈述你的理由。 (a) 根据性别划分公司的顾客。 不是。数据挖掘是在大型数据存储库中，自动地发现有用信息的过程。数据挖掘 技术服务用来探查大型数据库，发现先前未知的有用模式。还可以预测未来观测 结果，例如，预测一位新的顾客是否会在一家百货公司消费 100 美元以上。但并 非所有的信息发现任务都被视为数据挖掘，数据挖掘与信息检索不同，使用数据 库管理系统查找个别的记录，或通过因特网的搜索引擎查找特定的 Web 页面，则 是信息检索领域的任务，它们主要依赖传统的计算机科学技术和数据的明显特征 来创建索引结构，从而有效地组织和检索信息。数据挖掘的任务可分为两大类： 预测任务和描述任务。主要任务有四种：聚类分析，关联分析，异常检测，和预 测建模。其目的是根据其它属性的值，预测特定属性的值，或导出概括数据中潜 在联系的模式，主要是预测某些信息。而根据性别划分公司的顾客，只是一种简 单的数据库查询操作，并没有涉及预测分析。 (b) 根据可赢利性划分公司的顾客。 不是。根据可赢利性划分公司的顾客是使用阈值进行的一种统计计算。它仅仅是 根据消费结果统计将原有顾客进行划分，只是一种统计的结果，而没有根据这些 结果的特点预测一个新的顾客的赢利性，这种预测才是数据挖掘。 (c) 预测投一对骰子的结果。 不是。因为骰子的六个数值出现的可能性是相同的，这是一种概率计算，如果结 果出现的可能性是不确定的，不相同的，则更像是数据挖掘的任务，但在很早以 前利用数学已经能够很好的解决这个问题了。所以预测投一对骰子的结果不属于 数据挖掘的任务，不带有发现新信息的预测特点。 (d) 使用历史记录预测某公司未来的股票价格。 这是数据挖掘的任务。可以通过对历史记录特点的分析来创建一种模型预测未来 的公司的股票价格，这是数据挖掘任务中预测建模的一个例子，预测建模涉及以 说明变量函数的方式为目标变量建立模型，有两类预测建模任务：分类，用于预 测离散的目标变量；回归，用于预测连续的目标变量 dmj 预测某公司未来的股票 价格则是回归任务，因为价格具有连续值属性。 2 （10 分）列举 3 种数据挖掘功能，对每种举 2 个实际应用的例子。 （1）支持商务智能应用。借助 POS（销售点）数据收集技术，零售商可以在其商店 的收银台收集顾客购物的最新数据。零售商可以利用这些信息，加上电子商务网站的 日志、电购中心的顾客服务记录等其他的重要商务数据，更好地理解顾客的需求，做 出明智的商务决策。数据挖掘技术可以用来支持广泛的商务智能应用，如顾客分析、 定向营销、工作流管理、商店分布和欺诈检测等。商店可以根据顾客的购物习惯来安 排端口的摆放位置，这是日常生活中数据挖掘最常见的一种应用。数据挖掘还能帮助 零售商回答一些重要的商务问题，如“谁是最有价值的顾客？” “什么产品可以交叉销 售或提升销售？” “公司明年的收入前景如何？”这些是数据挖掘任务中的关联分析。 通过商品销售情况，来分析购买商品的顾客特点，根据这些特点重要发掘最可能的消 费者，这是关联分析在日常生活中的一种应用。 （2）在医学、科学与工程中的应用。医学、科学与工程技术界的研究者正在快速积累大 量数据，这些数据对获得有价值的新发现至关重要。例如，为了更深入地理解地球的气候 系统，NASA 已经部署了一系列的地球轨道卫星，不停地收集地表、海洋和大气的全球观 测数据。然而，由于这些数据的规模和时空特性，传统的方法常常不适合分析这些数据集。 数据挖掘开发的技术可以帮助地球科学家回答如下问题：“干旱和飓风等生态系统扰动的 频度和强度与全球变暖之间有何联系？” “海洋表面温度对地表降水量和温度有何影响？” “如何准确地预测一个地区的生长季节的开始和结束？” 。我国神舟七号载人航天飞船的发 射也是数据挖掘的一个应用，传统的技术通常不能处理太大量数据，而利用数据挖掘技术 可以将卫星收集到的太空中的大量数据信息进行分析，这样才能保证飞船在太空中的顺利 航行。 3 （10 分）比较急切分类（如，判定树、贝叶斯、神经网络）相对于懒散分类（如，k - 最临近、基于案例的推理）的优缺点。 决策树归纳的特点：（1）决策树归纳是一种构建分类模型的非参数方法，它不要求 任何先验假设，不假定类和其他属性服从一定的概念分布。（2）找到最佳的决策树是 NP 完全问题，可以采用一种贪心的、自顶向下的递归划分策略建立决策树。（3）已 构台构建决策树技术不需要昂贵的计算代价，决策边界是直线（平面）。（4）决策树 算法对于噪声的干扰具有相当好的鲁棒性，采用避免过分拟合的方法之后尤其如此。 （5）冗余属性不会对决策树的准确率造成不利的影响。（6）决策树方法会存在数据 碎片问题。（7）子树可能在决策树中重复多次。（8）当决策树很小时，训练和检验 误差都很大，称为模型拟合不足；当规模变得太大时，即使训练误差还在继续降低， 但是检验误差开始增大，称为模型过分拟合。 贝叶斯网络（BBN）的特点：（1）BNN 提供了一种用图形模型来捕获特定领域的先 验知识的方法，网络还可以用来对变量间的因果依赖关系进行编码。（2）构造网格可 能既费时又费力，但一旦网格结构确定下来，添加新变量就十分容易。（3）贝叶斯网 络很适合处理不完整的数据。（4）因为数据和先验知识以概率方式结合起来了，所以 该方法对模型的过分拟合问题是非常鲁棒的。 人工神经网络（ANN）的特点：（1）至少含有一个隐藏层的多层神经网络是一种普适 近似。（2）ANN 可以处理冗余特征，对训练数据中的噪声非常敏感。（3）ANN 权值 学习使用的梯度下降方法经常会收敛到局部极小值。训练 ANN 是一个很耗时的过程， 而测试样例分类时非常快。 基于密度的聚类（DBSCAN）优缺点：（1）它是相对抗噪声的，并且能够处理任意形 状和大小的簇。当近邻计算需要计算所有的点对邻近度时，DBSCAN 的开销可能很大。 K 均值的优缺点：K 均值并不适合所有的数据类型。它不能处理非球形簇、不同尺寸 和不同密度的簇，尽管指定足够大的簇个数时它通常可以发现纯子簇。 通过以上急切分类和懒散分类各种方法的特点对比可知，急切分类仅仅对于某些类型 的数据进入分类，而懒散分类则对于不同大小和不同类型的数据都可以进行处理。急 切分类对噪声较敏感而懒散分类而不是，急切分类方法较为简单，花费的时间和空间 代价都较懒散分类少。 4 （10 分）假定你作为一个数据分析人员，受雇于一家移动通讯公司。通过一个例子说 明打算如何使用数据挖掘技术为公司提供帮助。你的例子应包含问题描述，使用何种 数据挖掘方法解决该问题，理由和预期效果（不需要定量分析）。 例子如下：首先，移动通信公司数据分析人员的主要工作是收集移动通信用户使用 通信的方式，业务流量，并且收集用户的类型来分析各种用户使用信息的主要方式 及销售情况，以此可以出台更加适合不同用户需求的业务套餐类型。使用数据挖掘 中的聚类分析方法可以以一种较相似的主题来对结果进行分类，并且以一种更为简 洁的方式呈现给用户，例如：报告聚类中最频繁出现的10个词语，来收集最多使用 各种类型业务的用户特点。可以按照预先定义的分类，例如漫游类，本地外地类等 等用户使用通信的方法来进行分类。利用数据挖掘中顺序关联分析可以检测出某些 按照一定的高概率来查询到其他分类，并且允许更为高效的缓存，通过这种方法， 可以得出具有相互关联的用户使用通信方式和业务套餐的关系，进而通过查询一种 类型推导出其他相关类型的分类用户特点。通过异常检测技术可以发现不寻常的用 户通信方式，例如一个新方式的更加流行。总的来说，通过数据挖掘的聚类分析可 以将通信用户进行分类，然后发掘出各种类型用户使用通信的需求和最普通具用的 特点，通过对以往历史信息业务的分析，聚类，可能会发现新的需求，最后所用的 广告策略就可以根据这些发掘出来的新特性采取相应的调整策略以满足大多数用户 的需求，吸引更多的潜在客户，出台符合这些用户需求的业务产品类型，进而使公 司拥有更多的客户，有更大的发展前景。 5 （10 分）假设数据挖掘的任务是将如下的八个点（用(x,y)代表位置）聚类为三个类。 A1(2,10),A2(2,5),A3(8,4),B1(5,8),B2(7,5),B3(6,4),C1(1,2),C2(4,9) 距离函数是 Euclidean（欧几里得）函数。假设初始我们选择 A1,B1,和 C1 为每个簇的中心， 用 k-means 算法来给出 （a） 在第一次循环执行后的三个簇中心 （b） 最后的三个簇 K 均值算法的过程为：1： 选择 K 个点作为初始质点。 2： repeat 3: 每个点指派到最近的质心，形成 K 个簇。 4. 重新计算每个簇的质心、 5. until 质心不发生变化。 A1,B1,C 作为初始质点，距离函数是 Euclidean 函数，指派点到最近的质心，方法 为计算其他点到质点的欧几里得距离。计算距离如下：A1-A2 ：dist=(2-2) 2 +(5-10)2=25; A1-A3:dist=(8-2)2+(4-10)2=72; A1-B2:dist=(7-2)2+(5-10)2 =50; A1-B3:dist=(6-2)2+(4-10) 2=52; A1-C2:dist=(4-2)2+(9-10)2=5; B1-A2:dist=(2-5)2+(5-8)2=18; B1-A3:dist=(8-5)2+(4-8)2=25; B1-B2:dist=(7-5)2+(5-8)2=13 B1-B3:dist=(6-5)2+(4-8)2=17 B1-C2:dist=(4-5)2+(9-8)2=2 C1-A2:dist=(2-1)2+(5-2)2=10 C1-A3:dist=(8-1)2+(4-2)2=53 C1- B2:dist=(7-1)2+(5-2)2=45 C1-B3:dist=(6-1)2+(4-2)2=29 C1-C2:dist=(4-1)2+(9-2)2=58 其他五个结点选择与其最近的质心，三个簇分别为：B1,C2,B3,B2,A3C1,A2A1 计算这三个簇的质心：B1,C2,B3,B2,A3 的质心为：( （ 8+5+7+6+4）/5,(4+8+5+4+9)/5) 即 （6，6） ；C1,A2的质心为：（2+1）/2 ， （5+2）/2）即为（1.5,3.5）;A1的质心为 （2，10） 。 （a） 在第一次循环执行后的三个簇中心分别为（6，6） ， （1.5,3.5） ， （2，10） 重新指派各个对象到离其最近的质心，与上面方面相同，形成的三个簇为 A3,B1,B2,B3 ， C1，A2 ， A1,C2三个簇的质心分别为（6.5，5.25） ， （1.5，3.5） ， （3，9.5）;重新指派各个对象到离其最近的质心 , 形成的三个簇为: A3,B2,B3C1,A2 A1,B1,C2 三个簇的质心分别为：（7，4.3） ， （1.5，3.5） ， （3.67，9） ；重新指派各个对象到离其最 近的质心, 形成的三个簇为: A3,B2,B3C1,A2 A1,B1,C2三个簇的质心分别为： （7，4.3） ， （1.5，3.5） ， （3.67，9） ；至此质心不发生变化； （b） 最后三个簇即为A3,B2,B3C1,A2 A1,B1,C2; 6 （10 分）考虑下面的由 Big-University 的学生数据库挖掘的关联规则 major(X,”science”) status(X,”undergrad”) （1） 假定学校的学生人数（即，任务相关的元组数）为 5000，其中 56%的在校本科生的专 业是科学，64%的学生注册本科学位课程， 70%的学生主修科学 (science)。 (a) 计算规则(1)的支持度和置信度。 (b) 考虑下面的规则 major(X,”biology”) status(X,”undergrad”) 17%,80% （2） 假定主攻科学的学生 30%专业为 biology。与规则(1)对比，你认为规则(2)新颖吗？解释 你的结论。 （1）对于形如“A B”的关联规则，支持度定义为 support(A B) = 包含 A 和 B 的元 组数/元组总数; 规则（1）的支持度计算如下： 主修科学(science) 且未注册本科学位课程的学生人数为：5000*70%- 5000*64%*56%=1708；元组总数为 5000； 支持度为：1708/5000=34.16% 对于形如“A B”的关联规则，置信度定义为：confidence(A B)= 包含 A 和 B 的元组数/包含的 A 元组数 规则（1）的置信度计算如下： 主修科学(science) 且未注册本科学位课程的学生人数为：5000*70%- 5000*64%*56%=1708；主修科学的人数为： 5000*70%=3500 置信度为：1708/3500=48.8% （2）假定主攻科学的学生 30%专业为 biology：我们可以猜测下面的规则 major(X,”biology”) status(X,”undergrad”)的支持度和置信度应为 34.16%*30%=10.238%，48.8%，而题目中给出的 major(X,”biology”) status(X,” undergrad”)的支持度和置信度应为 17%，80%，与我们由规则（ 1）推测出来的相差较 大，所以规则（2）并不是冗余的，是新颖的。 7 （15 分）考虑为产品销售问题建立数据仓库。关注的主题是销售，用销售量、销售价 和成本度量（由此可以计算销售金额和利润） 。销售涉及销售的产品、时间、客户和销 售代理。其中，产品用产品名称、产品类别、产品品牌等描述，时间用日、月、季、 年描述，客户信息包括客户 ID、客户名、送货地址（省、市、街道、门牌号） 、帐号等 信息，销售代理包括销售代理姓名、地区、省、市等信息 (a) 给出每个维的概念分层。 (b) 画出该数据仓库的星型模式图。 (c) 由基本方体开始，为列出河南省客户购买的、由国美家电 2004 年销售的、小天鹅 洗衣机，应当执行哪些 OLAP 操作？下钻，上卷，切片 8 （15 分）下表由雇员数据库的训练数据组成。数据已泛化。例如，年龄“3135”表 示 31 到 35 的之间。对于给定的行，count 表示 department, status, age 和 salary 在该行 上具有给定值的元组数。 department status age salary count sales sales sales systems systems systems systems marketing marketing secretary secretary senior junior junior junior senior junior senior senior junior senior junior 31.35 26.30 31.35 21.25 31.35 26.30 41.45 36.40 31.35 46.50 26.30 46K.50K 26K.30K 31K.35K 46K.50K 66K.70K 46K.50K 66K.70K 46K.50K 41K.45K 36K.40K 26K.30K 30 40 40 20 5 3 3 10 4 4 6 设 status 是类标号属性。 (a) 你将如何修改基本决策树算法，以便考虑每个广义数据元组 (即，每一行) 的 count？ 基本的决策树算法应作如下修改，以考虑到每个广义数据元组(即，每一行) 的 count: 每个元组的 count 必须综合考虑属性的选择测量计算 (假如信息获取)： 考虑 count 来决定元组中最普遍的分类。 (b) 使用你修改过的算法，构造给定数据的决策树。 (c) 给定一个数据元组，它在属性 department, age 和 salary 上的值分别为 “systems”, “2630 ”和 “4650K”。该元组 status 的朴素贝叶斯分类结果 是什么？ 依题意，希望分类的元组为X=(department=systems,age=26-30,salary=46k-50k)，我们需要最 大化P X|Ci P Ci ,i=1,2。每个类的先验概率P Ci 可以根据训练元组计算： P(status=senior)=52/165=0.315 P(status=junior)=113/165=0.685 为了计算P X|Ci P Ci ,i=1,2，计算下面的条件概率 P(department=systems|status=senior)=8/52=0.154 P(department=systems|status=junior)=23/113=0.204 P(age=26-30|status=senior)=1/(52+6)=0.017 /使用拉普拉斯校准 P(status=26-30|status=junior