数据仓库与数据挖掘习题

1、数据仓库与数据挖掘习题什么是数据挖掘？在你的回答中，强调以下问题：（a）它是又一个骗局吗？（b）它是一种从数据库，统计学和机器学习发展的技术的简单转换吗？（c）解释数据库技术发展如何导致数据挖掘（d）当把数据挖掘看作知识发现过程时，描述数据挖掘所涉及的步骤。给出一个例子，其中数据挖掘对于一种商务的成功至关重要的。这种商务需要什么数据挖掘功能？他们能够由数据查询处理或简单的统计分析来实现吗？假定你是Big-University的软件工程师，任务是设计一个数据挖掘系统，分析学校课程数据库。该数据库包括如下信息：每个学生的姓名，地址和状态（例如，本科生或研究生），所修课程，以及他们累积的GPA（学分

2、平均）。描述你要选取的结构。该结构的每个成分的作用是什么？数据仓库和数据库有何不同？它们有那些相似之处？15简述以下高级数据库系统和应用：面向对象数据库，空间数据库，文本数据库，多媒体数据库和WWW。16定义以下数据挖掘功能：特征化，区分，关联，分类，预测，聚类和演变分析。使用你熟悉的现实生活中的数据库，给出每种数据挖掘的例子。17区分和分类的差别是什么？特征化和聚类的差别是什么？分类和预测呢？对于每一对任务，它们有何相似之处？18根据你的观察，描述一种可能的知识类型，它需要由数据挖掘方法发现，但未在本章中列出。它需要一种不同于本章列举的数据挖掘技术吗？1.9描述关于数据挖掘方法和用户交互问题

3、的三个数据挖掘的挑战。1.10描述关于性能问题的两个数据挖掘的挑战。试述对于多个异种信息源的集成，为什么许多公司宁愿使用更新驱动的方法（构造使用数据仓库），而不愿使用查询驱动的方法（使用包装程序和集成程序）。描述一些情况，其中查询驱动方法比更新驱动方法更受欢迎。简略比较以下概念，可以用例子解释你的观点（a）雪花模式、事实星座、星型网查询模型（b）数据清理、数据变换、刷新（c）发现驱动数据立方体、多特征方、虚拟仓库2.3假定数据仓库包含三个维time，doctor和patient，两个度量count和charge，其中charge是医生对一位病人的一次诊治的收费。（a）列举三种流行的数据仓库建模

4、模式。（b）使用（a）列举的模式之一，画出上面数据仓库的模式图。（c）由基本方体day,doctor，patient开始，为列出2000年每位医生的收费总数，应当执行哪些OLAP操作？（d）为得到同样的结果，写一个SQL查询。假定数据存放在关系数据库中，其模式如下：fee（day，month，year，doctor，hospital，patient，count，charge）假定Big_University的数据仓库包含如下4个维student,course,semester和instructor，2个度量count和avg_grade。在最低的概念层（例如对于给定的学生、课程、学期和教师的组

5、合），度量avg_grade存放学生的实际成绩。在较高的概念层，avg_grade存放给定组合的平均成绩。为数据仓库画出雪花模式图；由基本方体student,course,semester,instructor开始，为列出Big_University每个学生的CS课程的平均成绩，应当使用哪些OLAP操作(如由semester上卷到year)；如果每维有5层(包括all)，如studentMAJORSTATUSUNIVERSITY2.5假定数据仓库包含4个维date，spectator,location和game，2个度量count和charge。其中charge是观众在给定的日期观看节目的付费

6、。观众可以是学生、成年人或老人，每类观众有不同的收费标准。(a)画出该数据仓库的星型模式图；由基本方体date,spectator,location，game开始，为列出2000年学生观众在GM-Place的总付费，应当执行哪些OLAP操作？对于数据仓库，位图索引是有用的。以该数据立方体为例，简略讨论使用位图索引结构的优点和问题。为地区气象局设计一个数据仓库。气象局大约有1000观察点，散步在该地区的陆地、海洋，收集基本气象数据，包括每小时的气压、温度、降雨量。所有的数据都送到中心站，那里已收集了这种数据长达十年。你的设计应当有利于有效的查询和联机分析处理，有利于有效地导出多维空间的一般天气模

7、式。关于数据立方体中的度量计算：根据计算数据立方体所用的聚集函数，列出度量的三种分类；对于具有三个维time,location和product的数据立方体，函数variance属于哪一类？如果立方体被分割成一些块，描述如何计算它；假定函数是最高的10个销售额。讨论如何在数据立方体里有效的计算该度量。2.8假定需要在数据立方体中记录三种度量：min，average和median。给定的数据立方体允许递增的删除(即每次一小部分)，为每种度量设计有效的计算和存储方法。数据仓库实现的流行方法是构造一个称为数据立方体的多维数据库。不幸的是，这常常产生大的、稀疏的多维矩阵。给出一个例子，解释这种大的、稀疏

8、的数据立方体；设计一种实现方法，可以很好的克服这种稀疏矩阵问题。注意，需要详细解释你的数据结构，讨论空间需求量，以及如何由你的结构中检索数据；修改你在(b)的设计，处理递增的数据更新。给出你的新设计的理由。假定数据仓库包含20个维，每个维有5级粒度。用户感兴趣的主要是4个特定的维，每维有3个上卷、下钻频繁访问的级。你如何设计数据立方结构，有效地对此予以支持？用户时常想由一两个特定的维钻透数据立方体，到原始数据。你如何支持这一特征？2.11假定基本立方体有三个维A，B，C，其单元数如下：|A|=1000000，|B|=100,|C|=1000。假定分块将每维分成10部分。假定每维只有一层，画出完

9、整的立方体的格。如果每个立方单元存放一个4字节的度量，若方是稠密的，所计算的立方体有多大？指出立方体中空间需求量最小的块计算次序，并对计算2维平面所需要的内存空间计算空间量。31数据的质量可以用精确性，完整性和一致性来评估。提出两种数据质量的其他尺度。32在现实世界的数据中，元组在某些属性上缺少值是常有的。描述处理该问题的各种方法。3.3假定用于分析的数据包含属性age。数据元组中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使用按箱平均值平滑对以上数据

10、进行平滑，箱的深度是3。解释你的步骤。评论对于给定的数据，该技术的效果你怎样确定数据中的孤立点？对于数据平滑，还有那些其他方法？34讨论数据集成需要考虑的问题。模式识别：这主要是实体识别问题冗余：一个属性是冗余的，即它能由另一个表导出，如果属性或唯的命名不一致，也可能导致冗余，可以用相关分析来检测数据值冲突的检测与处理：有些属性因表示比例或编码不同，会导致属性不同3.5使用习题3。3给出的age数据，回答以下问题：使用最小-最大规范化，将age值35转换到0。0,1。0区间使用z-score规范化转换age值35,其中age的标准差为12。94年使用小数定标规范化转换age值35。指出对于给定

11、的数据，你愿意使用哪种方法。陈述你的理由。3.6使用流程图概述如下属性子集选择过程逐步向前选择逐步向后删除逐步向前选择和逐步向后删除的结合3.7使用习题3.3给出的age数据画一个宽度为10的等宽直方图。为如下每种选样技术勾画例子:SRSWOR,SRSWR,聚类选择，分层选择。使用长度为5的样本和层young,middle_aged和senior。对如下问题，使用伪代码或你喜欢用的程序设计语言，给出算法：对于分类数据，基于给定模式中属性的不同值得个数，自动产生概念分层。对于数值数据，基于等宽划分规则，自动产生概念分层。对于数值数据，基于等深划分规则，自动产生概念分层。列出和描述说明数据挖掘任务

12、的五种原语。说明为什么概念分层在数据挖掘中是有用的。概念分层的四种主要类型是：模式分层，集合分组分层，操作导出的分层和基于规则的分层。简略定义每种类型的分层。对于每种类型的分层，给出一个不在本章中出现的例子。考虑下面的由Big-University的学生数据库挖掘的关联规则major(X,science)=status(X,undergrad)(4.8)假定学校的学生人数(即任务相关的元组数)为5000，其中56%的在校本科生的专业是科学，64%的学生注册本科学位课程，70%的学生主修科学。计算规则(4.8)的支持度和置信度。考虑下面的规则(4.9)：major(X,biology)=stat

13、us(X,undergrad)17%,80%(4.9)假定主攻科学的学生30%专业为biology。与规则(4.8)对比，你认为规则(4.9)新颖吗？解释你的结论。语句可以用于挖掘特征化，区分，关联和分类规则。为聚类的挖掘提出一个语法定义。论建立标准化的数据挖掘查询语言的重要性。涉及这一任务的一些潜在好处和挑战是什么？列举一些该领域的最近提议。4.7下面的练习涉及定义概念分层的DMQL语法。典型情况，对于模式date(day,month,quarter,year)数据挖掘系统有一个预定义的概念分层。使用DMQL提供该概念分层的定义。概念分层定义可能涉及多个关系。例如，iterm_hierach

14、y可以涉及两个关系item和supplier，由如下模式定义：item(item_ID,brand,type,place_made,supplier)supplier(name,type,headquarter_location,owner,size,assets,revenue)5.1对于类特征化，基于数据立方体的实现与诸如面向属性归纳的关系实现之间的主要不同是什么？讨论哪种方法最有效，在什么条件下最有效。假定下面的表从面向属性的归纳导出classprogrammerbirth-placeCannadaothersCannadaDbaotherscount18012020;80将该表转换成现

15、实相关t-权和d-权的交叉表(b)将类Programmer转换成(双向的)量化描述规则。例如(birth_place(X)=CanadaA.)t:x%,d:y%.V(.)(t:w%,d:z%。？X,Programmer(X)5.3讨论为什么需要解析特征化和如何进行。比较两种归纳方法的结果：(I)包含相关分析和(ii)不包含相关分析。对于数据离散的特征化，另外给出三个常用统计度量(未在本章说明)，并讨论如何在大型数据库中有效地计算它们。5.5假定分析数据包含属性age.数据元组的age值(以递增次序)是：13,15,16,16,19，20，20，21，22，22，25，25，25，25，30，3

16、3，33，35，35，35，35，36，40，45，46，52，70A该数据的平均值是多少？中位数是多少？B该数据的模是多少？评论数据的模态性(即双模态,三模态等).C数据的中列数是什么D你能找出(粗略地)数据的第一个四分位数(q1)和第三个四分位数(Q3)吗？E给出数据的五数概括F画出数据的盒图G分位数-分位数图与分位数图的不同之处是什么？给定由数据库DB导出的概化关系R,假定元组的集合厶DB需要从DB中删除，简要给出用于R的必要删除的增量更新过程。简要给出挖掘解析类比较的基于数据立方体的增量算法。5.8简要给出数据立方体环境下数据离散统计度量的(i)并行和(ii)分布式挖掘方法。61Apr

17、iori算法使用子集支持度性质的先验知识证明频繁项集的所有非空子集必须也是频繁的。证明项集s的任意非空子集s的支持度至少和s的支持度一样大。给定频繁项集丨和丨的子集s,证明规则,s=(l-s)啲置信度不可能大于s=(l-s)的置信度。其中，s是s的子集。d)Apriori的一种变形将事务数据库D中的事务划分成n个不重叠的部分。证明在D中是频繁的任何项集至少在D的一个部分中是频繁的。62数据库有4个事务。设min_sup=60%，min_conf=80%。TIDDATEITEMS_BOUGHTT10010/15/99K,A,D,BT20010/15/99D,A,C,E,BT30010/19/99

18、C,A,B,ET40010/22/99B,A,DA)分别使用Apriori和FP-增长算法找出频繁项集。比较两种挖掘过程的有效性。B)列出所有强关联规则，他们与下面的元规则匹配，其中，X是代表顾客的变量，item时表示项的变量：xWtransaction,buys(X,item1)Abuys(X,item2)=buys(X,item3)s,c6.3在挖掘层交叉关联规则时，假定发现项集IBMdesktopcomputer,printer不满足最小支持度。这一信息可以用来剪去诸如IBMdesktopcomputer,b/wprinter1的后代项集的挖掘吗？给出一个一般规则，解释这一信息如何用于对

19、搜索空间剪枝。6.4给出一个短例子，表明强关联规则中的项可能实际上是负相关的。6.5下面的相依表汇总了超级市场的事务数据，其中，hotdogs表示包含热狗的事务，hotdogs表示不包含热狗的事务，hamburgers表示包含汉堡包的事务，hamburgers表示不包含汉堡包的事务。HotdogshotdogsHamburgers20005002500hamburgers100015002500工col300020005000假定发现关联规则hotdogs=hamburgers。给定最小支持度阈值25%，最小置信度阈值50%，该关联规则是强的吗？根据给定的数据，买hotdog独立于买hambu

20、rgers吗？如果不是，二者之间存在何种相关联系？6.6数据库有4个事务，设min_sup=60%，min_conf=80%。Cust_IDTIDItems_bought(以brand-item_category形式)01T100Kings-Carb,Sunset-Milk,Dairyland-Cheese,best-Bread02T200Best-Cheese,Dairyland-Milk,Goldenfarm-Apple,Tasty-Pie,Wonder-Bread01T300Westcoast-Apple,Dairyland-Milk,Wonder-Bread,Tasty-Pie03T4

21、00Wonder-Bread,Sunset-Milk,Dairyland-Cheese在item_category粒度(例如，itemi可以是milk),对于下面规则模板xWtransaction,buys(X,item1)Abuys(X,item2)=buys(X,item3)s,c对于最大的k,列出频繁k-项集和包含最大的k的频繁k-项集的所有强关联规则。在brand-item_category粒度(例如：item可以是sunset-milk)，对于下面的规则模板：xWcustomer,buys(X,item1)Abuys(X,item2)=buys(X,item3)对最大的k,列出频繁k

22、-项集。注意：不打印任何规则。假定一个大型存储具有分布在4个站点的事务数据库。每个成员数据库中的事务具有相同的格式Tj:i1,.,im；其中，Tj是事务标示符，而ik(1=k=m)是事务中购买的商品标识符。提出一个有效的算法，挖掘全局关联规则(不考虑多层关联规则)。可以给出你的算法的要点。你的算法不必将所有的数据移到一个站点，并且不造成过度的网络通信开销。6.8假定大型事务数据库DB的频繁项集已经存储。讨论：如果新的事务集ADB(增量地)加进，在相同的最小支持度阈值下，如何有效地挖掘(全局)关联规则？提出并给出挖掘多层关联规则的层共享挖掘方法的要点。其中，每个项用它的层位置编码，一次初始数据库

23、扫描收集每个概念层的每个项的计数，识别频繁和子频繁项集。将用该方法挖掘多层关联规则与挖掘单层关联规则的花费进行比较。6.10证明：包含项h和其祖先h的项集H的支持度与项集H-h的支持度相同。解释如何将它用于层交叉关联规则挖掘。提出一种挖掘混合维关联规则(多维关联规则带有重复谓词)的方法。序列模式可以用类似于关联规则挖掘的方法挖掘。设计一个有效的算法，由事务数据库挖掘多层序列模式。这种模式的一个例子如下：买PC的顾客在三个月内将买Microsoft软件，在其上，可以下钻，发现该模式的更详细的版本，如买PentiumPC的顾客在三个月内将买MicrosoftOffice。商店里每种商品的价格是非负

24、的。商店经理只关心如下形式的规则：一件免费商品可能触发在同一事务中$200的总购物。陈述如何有效地挖掘这种规则。商店里每种商品的价格是非负的。对于以下每种情况，识别它们提供的约束类型，并简略讨论如何有效地挖掘这种关联规则。至少包含一件Nintendo游戏。包含一些商品，它们的单价和小于$150。包含一件免费商品，并且其它商品的单价和至少是$200。所有商品的平均价格在$100和$500之间。简述判定树分类的主要步骤。在判定树归纳中，为什么树剪枝是有用的？用一个单独的样本集计值剪枝的缺点是什么？为什么朴素贝叶斯分类称为朴素的？简述朴素贝叶斯分类的主要思想。7.4比较急切分类(如判定树、贝叶斯、神

25、经网络)相对于懒散分类(如，k-最临近、基于案例的推理)的优缺点。通过对预测变量的变换，有些非线性回归模型可以转换成线性的。指出如何将非线性回归方程Y=aXb转换成可以用最小平方法求解的线性回归方程。什么是推进？陈述它为何能提高判定树归纳的准确性。的表决，这里每个分类法的表决是其准确率的函数。推进算法也可以扩充到连续值预测。证明准确率是灵敏性和特效性度量的函数，即证明(7.31)式。当一个数据对象可以同时属于多个类时，很难评估分类的准确率。陈述在这种情况下，你将使用何种标准比较在相同数据上的建模的不同分类方法。7.9给定判定树，你有选择：(a)将判定树转换成规则，然后对结果规则剪枝，或(b)对

26、判定树剪枝，然后将剪枝后的树转换成规则。相对于(b),(a)的优点是什么？7.10给定k和描述每个样本的属性数n,写一个k-最临近分类算法。7.11下表给出课程数据库中学生的期中和期末考试成绩。X其中考试Y期末考试728450638177747894908675594983796577335288748190绘数据图。X和Y看上去具有线性联系吗？使用最小二乘法，求由学生的期中成绩预测学生的期末成绩的方程式。预测期中成绩为86分的学生的期末成绩。7.12下表有雇员数据库的训练数据组成。数据已概化。对于给定的行，count表示department,status,age和salary在该行上具有给定

27、值的元组数。departmentStatusAgeSalarycountsalessenior31.3546K.50K30salesjunior26.3026K.30K40salesjunior31.3531K.35K40systemsjunior21.2546K.50K20systemssenior31.3566K.70K5systemsjunior26.3046K.50K3systemssenior41.4566K.70K3marketingsenior36.4046K.50K10marketingjunior31.3541K.45K4secretarysenior46.5036K.40K

28、4secretaryjunior26.3026K.30K6设salary是类标号属性。你将如何修改ID3算法，以便考虑每个概化数据元组(即每一行)的count？使用你修改过的ID3算法，构造给定数据的判定树。给定一个数据样本，它在属性department,status和age上的值分别为systemsTjunior和20.24。该样本的salary的朴素贝叶斯分类是什么？为给定的数据设计一个多层前馈神经网络。标记输入和输出层节点。使用上面得到的多层前馈神经网络，给定训练实例(sales,senior,31.35,46K.50K)给出后向传播算法一次迭代后的权值。指出你使用的初始权值和偏置以及学

29、习率。给定年龄age的变量的如下度量值：18，22，25，42，28，43，33，35，56，28通过如下的方法进行变量标准化：计算age的平均绝对误差。计算头四个值的zscore。给定两个对象，分别用元组(22，1，42，10)和(20，0，36，8)表示计算两个对象之间的欧几里的距离计算两个对象之间的曼哈坦距离计算两个对象间的明考斯基距离，q=3。什么是聚类？简单描述下列聚类方法：划分方法，层次方法，基于密度的方法，基于网格的方法，以及基于模型的方法。为每种方法给出例子。假设数据挖掘的任务是将如下8个点（用（x,y）代表位置）聚类为3个簇：A1（2，10），A2（2，5），A3（8，4），

30、B1（5,8）,B2（7,5）,B3（6,4）,C1（1,2）,C2（4,9）距离函数是欧几里的距离。假设初始选择A1，B1，C1分别为每个聚类的中心。请用K平均算法给出a）第一次循环执行后的三个聚类中心；b）最后的三个簇。人眼在判断聚类方法对二位数据的聚类质量上是快速而有效的。你能否设计出一个数据可视的方法类似数据聚类可视化和帮助人们判断三维数据的聚类质量。对更高维的数据如何？给出如何集成特定聚类算法的例子,例如,什么情况下一个聚类算法被用作另一个算法的预处理。异构数据库系统由多个数据库系统组成,这些数据库的定义是相互独立的,但彼此间需要一定的信息交换,能够处理局部和全局查询。试述在这种系统

31、中如何使用基于概化的方法处理描述性挖掘查询。对象立方体的建立,可以在执行多维概化之前通过把面向对象的数据库概化为结构化数据来完成。试述如何在对象立方体中处理集合值数据。9.3空间关联挖掘可以至少按如下两种方式加以实现：（i）基于挖掘查询的要求，可以动态计算不同空间对象之间的空间关联关系；（ii）预先计算出空间对象间的空间距离，使得关联挖掘可以基于这些预计算结果求得。试述（i）如何高效实现上述方法；（ii）各方法的适用条件。9.4假设某城市的交通部门需要规划高速公路的建设，为此希望根据每天不同时刻收集到的交通数据进行有关高速公路大通方面的数据分析。（a）设计一存储高速公路交通信息的空间数据仓库，

32、可以方便地支持人们按高速公路、按一天的时间和按工作日查看平均的和高峰时间的交通流量，以及在发生重大交通事故时的交通状况。（b）可以从该空间数据仓库中挖掘什么样的信息用于支持城市规划人员？（c）该数据仓库既包含了空间数据，也包含了时态数据。设计一种挖掘技术，可以高效地从该空间时态数据仓库挖掘有意义的模式。多媒体中的相似检索已经成为多媒体数据检索系统开发中的主要内容。然而，许多多媒体数据挖掘方法只是基于孤立的简单多媒体特征分析，如颜色、形状、描述、关键字，等等。（a）请指出将数据挖掘与基于相似性的检索结合,可以给多媒体数据挖掘带来重要的进步。可以用任一数据挖掘技术为例，如多维分析、分类、关联或聚类等。（b）请概述应用基于相似性的搜索方法增强多媒体数据中聚类质量的实现技术。假设一供电站保存了按时间和按地区的能源消耗量，和每一地区每一用户的能源使用信息。讨论在这一时序数据库中，如何解决如下问题：（a）找出星期五某一给定地区的相似的能源消耗曲线；（b）当能源消耗曲线急剧上升时，20分钟内会发生什么情况？（c）如何找出可以区分稳定能源消耗地区与不稳定能源消耗地区的最突出特征？9.7假设某连锁餐厅想挖掘出与主要体育事件相关的顾客行为，如每当电视播出法裔加拿大人的曲棍球比赛时，肯德鸡的销量会在比赛前一小时上升20。(a)给出一种找出这种模式的有效方法。(b)大部分与时间相关的关联挖