数据仓库与数据挖掘 习题
1.1什么是数据挖掘？在你的回答中，强调以下问题： (a) 它是又一个骗局吗？
(b) 它是一种从数据库，统计学和机器学习发展的技术的简单转换吗？ (c) 解释数据库技术发展如何导致数据挖掘
(d) 当把数据挖掘看作知识发现过程时，描述数据挖掘所涉及的步骤。
1.2 给出一个例子，其中数据挖掘对于一种商务的成功至关重要的。这种商务需要什么数据挖掘功能？他们能够由数据查询处理或简单的统计分析来实现吗？
1.3 假定你是Big-University的软件工程师，任务是设计一个数据挖掘系统，分析学校课程数据库。该数据库包括如下信息：每个学生的姓名，地址和状态（例如，本科生或研究生），所修课程，以及他们累积的GPA（学分平均）。描述你要选取的结构。该结构的每个成分的作用是什么？
1.4 数据仓库和数据库有何不同？它们有那些相似之处？
1．5简述以下高级数据库系统和应用：面向对象数据库，空间数据库，文本数据库，多媒体数据库和WWW。
1．6 定义以下数据挖掘功能：特征化，区分，关联，分类，预测，聚类和演变分析。使用你熟悉的现实生活中的数据库，给出每种数据挖掘的例子。
1．7 区分和分类的差别是什么？特征化和聚类的差别是什么？分类和预测呢？对于每一对任务，它们有何相似之处？
1．8 根据你的观察，描述一种可能的知识类型，它需要由数据挖掘方法发现，但未在本章中列出。它需要一种不同于本章列举的数据挖掘技术吗？
1. 9 描述关于数据挖掘方法和用户交互问题的三个数据挖掘的挑战。 1. 10 描述关于性能问题的两个数据挖掘的挑战。
2.1 试述对于多个异种信息源的集成，为什么许多公司宁愿使用更新驱动的方法（构造使用数据仓库），而不愿使用查询驱动的方法（使用包装程序和集成程序）。描述一些情况，其中查询驱动方法比更新驱动方法更受欢迎。
2.2 简略比较以下概念，可以用例子解释你的观点 （a） 雪花模式、事实星座、星型网查询模型 （b） 数据清理、数据变换、刷新
（c） 发现驱动数据立方体、多特征方、虚拟仓库 2.3 假定数据仓库包含三个维time，doctor和patient，两个度量count 和charge，其中charge是医生对一位病人的一次诊治的收费。 （a） 列举三种流行的数据仓库建模模式。
（b） 使用（a）列举的模式之一，画出上面数据仓库的模式图。
（c） 由基本方体[day，doctor，patient]开始，为列出2000年每位医生的收费总数，应当执行哪些 OLAP操作？
（d） 为得到同样的结果，写一个SQL查询。假定数据存放在关系数据库中，其模式如下： fee（day，month，year， doctor，hospital，patient，count，charge）
2.4 假定Big_University的数据仓库包含如下4个维student, course, semester和instructor，2个度量count和avg_grade。在最低的概念层（例如对于给定的学生、课程、学期和教师的组合），度量avg_grade存放学生的实际成绩。在较高的概念层，avg_grade存放给定组合的
平均成绩。
（a） 为数据仓库画出雪花模式图；
（b） 由基本方体 [student, course, semester, instructor]开始，为列出Big_University每个学生的CS课程的平均成绩，应当使用哪些OLAP操作（如由 semester上卷到year）； （c） 如果每维有5层（包括all），如student
（a ） 画出该数据仓库的星型模式图； （b） 由基本方体[date，spectator，location，game]开始，为列出2000年学生观众在GM-Place的总付费，应当执行哪些OLAP操作？
（c） 对于数据仓库，位图索引是有用的。以该数据立方体为例，简略讨论使用位图索引结构的优点和问题。
2.6 为地区气象局设计一个数据仓库。气象局大约有1000观察点，散步在该地区的陆地、海洋，收集基本气象数据，包括每小时的气压、温度、降雨量。所有的数据都送到中心站，那里已收集了这种数据长达十年。你的设计应当有利于有效的查询和联机分析处理，有利于有效地导出多维空间的一般天气模式。 2.7 关于数据立方体中的度量计算：
（a） 根据计算数据立方体所用的聚集函数，列出度量的三种分类； （b） 对于具有三个维time，location和product的数据立方体，函数variance属于哪一类？如果立方体被分割成一些块，描述如何计算它；
（c） 假定函数是\最高的10个销售额\。讨论如何在数据立方体里有效的计算该度量。 2.8 假定需要在数据立方体中记录三种度量：min，average和median。给定的数据立方体允许递增的删除（即每次一小部分），为每种度量设计有效的计算和存储方法。
2.9 数据仓库实现的流行方法是构造一个称为数据立方体的多维数据库。不幸的是，这常常产生大的、稀疏的多维矩阵。
（a） 给出一个例子，解释这种大的、稀疏的数据立方体；
（b） 设计一种实现方法，可以很好的克服这种稀疏矩阵问题。注意，需要详细解释你的数据结构，讨论空间需求量，以及如何由你的结构中检索数据；
（c） 修改你在（b）的设计，处理递增的数据更新。给出你的新设计的理由。 2.10 假定数据仓库包含20个维，每个维有5级粒度。
（a）用户感兴趣的主要是4个特定的维，每维有3个上卷、下钻频繁访问的级。你如何设计数据立方结构，有效地对此予以支持？
（b）用户时常想由一两个特定的维钻透数据立方体，到原始数据。你如何支持这一特征？ 2.11 假定基本立方体有三个维A，B，C，其单元数如下：|A|=1000000， |B|=100，|C|=1000。假定分块将每维分成10部分。
（a）假定每维只有一层，画出完整的立方体的格。
（b）如果每个立方单元存放一个4字节的度量，若方是稠密的，所计算的立方体有多大？ （c）指出立方体中空间需求量最小的块计算次序，并对计算２－维平面所需要的内存空间计算空间量。
3．1 数据的质量可以用精确性，完整性和一致性来评估。提出两种数据质量的其他尺度。 3．2 在现实世界的数据中，元组在某些属性上缺少值是常有的。描述处理该问题的各种方法。
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
(a) 使用按箱平均值平滑对以上数据进行平滑，箱的深度是3。解释你的步骤。评论对于给定的数据，该技术的效果
(b) 你怎样确定数据中的孤立点？
(c) 对于数据平滑，还有那些其他方法？ 3．4 讨论数据集成需要考虑的问题。
(1) 模式识别：这主要是实体识别问题
(2) 冗余：一个属性是冗余的，即它能由另一个表导出，如果属性或唯的命名不一致，也可能导致冗余，可以用相关分析来检测
(3) 数据值冲突的检测与处理：有些属性因表示比例或编码不同，会导致属性不同 3．5 使用习题3。3给出的age数据，回答以下问题：
(a) 使用最小-最大规范化，将age值35转换到[0。0，1。0]区间
(b) 使用z-score规范化转换age 值35，其中age的标准差为12。94年 (c) 使用小数定标规范化转换age值35。
(d) 指出对于给定的数据，你愿意使用哪种方法。陈述你的理由。 3．6 使用流程图概述如下属性子集选择过程 (a) 逐步向前选择 (b) 逐步向后删除
(c) 逐步向前选择和逐步向后删除的结合 3.7 使用习题3.3给出的age数据
(a)画一个宽度为10的等宽直方图。
(b)为如下每种选样技术勾画例子: SRSWOR, SRSWR, 聚类选择，分层选择。使用长度为5的样本和层\，\和\。
3.8 对如下问题，使用伪代码或你喜欢用的程序设计语言，给出算法：
(a)对于分类数据，基于给定模式中属性的不同值得个数，自动产生概念分层。 (b)对于数值数据，基于等宽划分规则，自动产生概念分层。 (c)对于数值数据，基于等深划分规则，自动产生概念分层。 4.1列出和描述说明数据挖掘任务的五种原语。 4.2 说明为什么概念分层在数据挖掘中是有用的。
4.3 概念分层的四种主要类型是：模式分层，集合分组分层，操作导出的分层和基于规则的分层。
a)简略定义每种类型的分层。
b)对于每种类型的分层，给出一个不在本章中出现的例子。
4.4 考虑下面的由Big-University 的学生数据库挖掘的关联规则major (X,\ (4.8)
假定学校的学生人数（即任务相关的元组数）为5000，其中56%的在校本科生的专业是科学，64%的学生注册本科学位课程，70%的学生主修科学。 a) 计算规则(4.8)的支持度和置信度。 b)考虑下面的规则(4.9)：
major(X,\ [17%,80%] (4.9)
假定主攻科学的学生30%专业为biology。与规则(4.8)对比，你认为规则(4.9)新颖吗？ 解释你的结论。
4.5 语句可以用于挖掘特征化，区分，关联和分类规则。为聚类的挖掘提出一个语法定义。
4.6 论建立标准化的数据挖掘查询语言的重要性。涉及这一任务的一些潜在好处和挑战是什么？列举一些该领域的最近提议。
4.7 下面的练习涉及定义概念分层的DMQL语法。
(a) 典型情况，对于模式date(day,month,quarter,year)，数据挖掘系统有一个预定义的概念分层。使用DMQL提供该概念分层的定义。
(b) 概念分层定义可能涉及多个关系。例如，iterm_hierachy可以涉及两个关系item和supplier，由如下模式定义：
item(item_ID, brand, type, place_made, supplier)
supplier(name, type, headquarter_location, owner, size, assets, revenue)
5.1．对于类特征化， 基于数据立方体的实现与诸如面向属性归纳的关系实现之间的主要不同是什么？讨论哪种方法最有效，在什么条件下最有效。 5.2 假定下面的表从面向属性的归纳导出
class &n bsp; birth--- place count &n bsp; Cannada &nbs p; 180 programmer others ; 120
&nbs p; Cannada &nbs p; 20 Dba &n bsp; others ; 80
（a） 将该表转换成现实相关t-权和d-权的交叉表
（b） 将类Programmer转换成（双向的）量化描述规则。例如 (birth_place(X)=\∧...)[t:x%,d:y%]...∨(...)([t:w%,d:z%]。?X,Programmer(X)
5.3 讨论为什么需要解析特征化和如何进行。比较两种归纳方法的结果：（I）包含相关分析和（ii）不包含相关分析。
5.4 对于数据离散的特征化，另外给出三个常用统计度量（未在本章说明），并讨论如何在大型数据库中有效地计算它们。
5.5 假定分析数据包含属性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
A 该数据的平均值是多少？中位数是多少?
B 该数据的模是多少?评论数据的模态性(即双模态,三模态等). C 数据的中列数是什么
D 你能找出(粗略地)数据的第一个四分位数(q1)和第三个四分位数(Q3)吗? E 给出数据的五数概括 F 画出数据的盒图
G 分位数-分位数图与分位数图的不同之处是什么?
5.6 给定由数据库DB导出的概化关系R,假定元组的集合△ DB需要从DB中删除，简要给出用于R的必要删除的增量更新过程。
5.7 简要给出挖掘解析类比较的基于数据立方体的增量算法。
5.8 简要给出数据立方体环境下数据离散统计度量的(ⅰ)并行和( ⅱ)分布式挖掘方法。
6．1 Apriori 算法使用子集支持度性质的先验知识 a) 证明频繁项集的所有非空子集必须也是频繁的。
b) 证明项集s的任意非空子集s`的支持度至少和s的支持度一样大。 c) 给定频繁项集l和l的子集s，证明规则\的置信度不可能大于\的置信度。其中，s'是s的子集。
d) Apriori的一种变形将事务数据库D中的事务划分成n个不重叠的部分。证明在D中是频繁的任何项集至少在D的一个部分中是频繁的。
6．2 数据库有4个事务。设min_sup = 60%，min_conf = 80%。 TID DATE ITEMS_BOUGHT T100 10/15/99 {K, A, D, B} T200 10/15/99 {D, A, C, E, B} T300 10/19/99 {C, A, B, E} T400 10/22/99 {B, A, D}
A） 分别使用Apriori 和FP- 增长算法找出频繁项集。比较两种挖掘过程的有效性。
B） 列出所有强关联规则，他们与下面的元规则匹配，其中，X 是代表顾客的变量，item 时表示项的变量： \∈transaction, buys(X, item1)∧buys(X, item2) => buys(X, item3) [s, c] 6．3 在挖掘层交叉关联规则时，假定发现项集\不满足最小支持度。这一信息可以用来剪去诸如\的\后代\项集的挖掘吗？给出一个一般规则，解释这一信息如何用于对搜索空间剪枝。
6．4 给出一个短例子，表明强关联规则中的项可能实际上是负相关的。
6．5 下面的相依表汇总了超级市场的事务数据，其中，hot dogs 表示包含热狗的事务，~hotdogs 表示不包含热狗的事务，hamburgers 表示包含汉堡包的事务，~hamburgers 表示不包含汉堡包的事务。 Hotdogs ~hotdogs Hamburgers 2000 500 2500 ~hamburgers 1000 1500 2500 ∑ col 3000 2000 5000
A） 假定发现关联规则\。给定最小支持度阈值25% ，最小置信度阈值 50% ，该关联规则是强的吗？
B） 根据给定的数据，买hotdog 独立于买hamburgers 吗？如果不是，二者之间存在何种相关联系？
6．6 数据库有4 个事务，设 min_sup = 60% ， min_conf = 80% 。 Cust_ID TID Items_bought（以brand- item_category形式） 01 T100 {King's-Carb, Sunset-Milk, Dairyland-Cheese, best-Bread}
02 T200 {Best-Cheese, Dairyland-Milk, Goldenfarm-Apple, Tasty-Pie, Wonder-Bread} 01 T300 {Westcoast-Apple, Dairyland- Milk, Wonder-Bread, Tasty-Pie} 03 T400 {Wonder-Bread, Sunset-Milk, Dairyland-Cheese}
a) 在 item_category 粒度（例如，itemi 可以是\），对于下面规则模板 \ x∈transaction, buys(X, item1)∧buys(X, item2) => buys(X, item3) [s, c]
对于最大的k，列出频繁k-项集和包含最大的k的频繁k-项集的所有强关联规则。 b) 在brand-item_category 粒度（例如：item 可以是\），对于下面的规则模板：
\ x∈customer, buys(X, item1)∧buys(X, item2) => buys(X, item3) 对最大的k，列出频繁k-项集。注意：不打印任何规则。 6.7 假定一个大型存储具有分布在4个站点的事务数据库。每个成员数据库中的事务具有相同的格式Tj:{i1,...,im}；其中，Tj是事务标示符，而ik(1<=k<=m)是事务中购买的商品标识符。提出一个有效的算法，挖掘全局关联规则（不考虑多层关联规则）。可以给出你的算法的要点。你的算法不必将所有的数据移到一个站点，并且不造成过度的网络通信开销。