数据挖掘概念与技术（第三版）课后答案

您所在的位置：网站首页 › 数据库10章课后答案 › 数据挖掘概念与技术（第三版）课后答案

数据挖掘概念与技术（第三版）课后答案

2024-07-12 11:00| 来源: 网络整理| 查看: 265

未完待续。。。

5.1 假定10维基本方体只包含3个基本单元: (1) (a1,d2,d3,d4,...,d9,d10), (2) (d1,b2,d3,d4,...,d9,d10), 和(3) (d1,d2,c3,d4,...,d9,d10),其中a1≠d1, b2≠d2并且c3≠dz。该立方体的度量是count ()。 (a)完全数据立方体中包含多少个非空方体? (b)完全立方体中包含多少个非空聚集(即非基本)单元? (c) 如果冰山立方体的条件是“count≥2”,那么冰山立方体包含多少个非空聚集单元? (d)单元c是闭单元，如果不存在单元d使得d是单元c的特殊化(即d通过用非“*”值替换c中的“*”得到)，并且d与c具有相同的度量值。闭立方体是仅由闭单元组成的数据立方体。该立方体中有多少个闭单元?

（a）n维数据立方体包含 $2^{n}$ 个方体， $\Rightarrow$ 10维数据立方体包含 $2^{10}$ 个非空方体。

（b）（1）每一个单元生成 $2^{10}-1$ 个非空聚集单元，因此3个基本单元总共有 $3*(2^{10}-1)$ 个非空聚集单元（包含重复记录的）；

（2）1×27（即（*，∗，∗，d4，...，d10））重叠两次（因此计数3），3×27（即（d1，∗，∗，d4，...，d10）、（*，d2，∗，d4，...，d10）、（*，∗，d3，d4，...，d10））个像元重叠一次（因此计数2），因此多记录了 $5*2^{7}$ 个单元；

（3）因此包含 $3*(2^{10}-1)-5*2^{7}$ = $19*2^{7}-3$ 个。

（c）（1）（d1，∗，∗，d4，...，d9，d10）的计数为2，因为它由单元格2和单元格3生成，

类似地，（2）（∗，d2，∗，d4，...，d9，d10）：2，

（3）（∗，∗，d3，d4，...，d9，d10）：2;

（4）（∗，∗，∗，d4，...，d9，d10）：3

因此该冰山立方体包含 $4*2^{7}=2^{9}$ 个非空聚集单元

（d）总共有7个闭单元，如下：

(1) (a1,d2,d3,d4,...,d9,d10) : 1,

(2) (d1,b2,d3,d4,...,d9,d10) : 1,

(3) (d1,d2,c3,d4,...,d9,d10) : 1,

(4) (∗,∗,d3,d4,...,d9,d10) : 2,

(5) (∗,d2,∗,d4,...,d9,d10) : 2,

(6) (d1,∗,∗,d4,...,d9,d10) : 2,

(7) (∗,∗,∗,d4,...,d9,d10) : 3。

5.2 有几种典型的立方体计算方法，如MultiWay[ ZDN97]、 BUC[ BR99] 和Star- Cubing[ XHLW03 ]。简单地描述这三种方法(即用一两行列出要点)，并在以下条件下比较它们的灵活性和性能:

(a)计算低维(例如，小于8维)、稠密的完全立方体。 (b)计算具有高度倾斜数据分布的大约10维的冰山立方体。 (c)计算高维(例如，超过100维)、稀疏的冰山立方体。

MultiWay、 BUC 和Star- Cubing总结：

Star- Cubing：

一种集成自顶向下和自底向上的立方体计算方法，结合了多路数组聚集中的同时聚集和BUC中的Apriori剪枝策略。利用星型树数据结构进行存储，其中核心的部分就是引入共享维的概念。如果共享维的聚集值不满足冰山条件，则共享维向下的所有单元都不满足冰山条件。

（a）MultiWay和Star-Cubing均比BUC的灵活性和性能好。

（b）MultiWay确实适用于冰山立方体。对于高度倾斜的数据集，Star-Cubing比BUC更好。

（c）MultiWay确实适用于冰山立方体。MultiWay确实适用于冰山立方体。 BUC和Star-Cubing都无法有效地处理高维数据。应该探索封闭立方体和壳碎片的方法。

5.3假设数据立方体C有d 个维，并且基本方体包含 k个不同元组。 (a)给出一个公式，计算立方体C可能包含的单元的最小个数。 (b)给出一个公式，计算立方体C可能包含的单元的最大个数。 (e)如果每个立方体单元中的计数不能小于阂值v，回答(a)和(b)。 (d)如果只考虑闭单元(使用最小计数阅值v），回答(a) 和(b)。

（a）为了实现最小的个数，我们需要尽可能地“合并”这k个不相同的元组，只有这样在较高层才会有更少的单元（但是在基本方体中总是有k个单元）。我们首先观察两种极端情况：

1、如果当我们删除一个维（记为A），k个元组可以“融合”成一个单元时，这k个元组的形式为：t1=(a1,t'), t2=(a2,t'),..., tk=(ak,t')（其中t'为一个d-1维的元组）。然而，当我们保持属性A，忽略其它属性时却是低效的，因为这时仍然需要维持k个元组，因为k个元组之间无法进行任何合并操作。

2、在第一种情况中，只有忽略维A时才会发生“数量约减”。我们可以设想一下另一种情况：“约减”是以一种分布式的和“平均”式的方式发生。对于这两种情况的处理，我们看一个例子：

假设我们有一个8（A）*8（B）*8（C）的三维立方体，并且k=8。在第一种情况中，有8个基本单元，1（roll up to all on A）+8+8=17个 2-D单元，1+1+8（(roll up to all on two dimensions other than A)=10 1-D单元，1个0-D单元。考虑第二种情况，在整个立方体的角落中取一个2*2*2的3维子方体，用8个元组对其填充，我们将得到8个基本单元，4+4+4=12个2-D单元（任一维度上的累积会产生4个单元），2+2+2=6个1-D单元，1个0-D单元。因为36=8+17+10+1>8+12+6+1=27，所以情形2比情形1更好。

情形2总是较好的。假如K=4，这时情形1有4个基本单元，1+4+4=9个2-D单元，1+1+4=6个1-D单元，1个0-D单元，所以共有4+9+6+1=20个单元。对于情形2，我们可以建立一个2（B）*2（C）的2维子方体：4个基本单元，2+2+4（roll up to all on A）=8个2-D单元，1（roll up to all on B and C）+2+2=5个1-D单元，1个0-D单元，共4+8+5+1=18个单元。

对于这一问题的理解，可以按照一种启发式的思路考虑：我们想把k个不同的元组放入一个a*b*c的子方体中，在情形1中是以1*1*k的方式，情形2中是很明显，a+b+c是1-D单元的数量，求1-D方体的最小数量，我们可以将其转化为给定条件abc=k时，求a+b+c的最小值。

综上所述，当我们把所有的k个元组放入一个x1*x2*....*xD的子方体，并且x1x2...xD=k（或者放宽条件将“=”改为“>=”）时，方体包含的单元的个数最小。单元的总数为：

（b）单元个数最大的情况是：k个元组是完全“不相关的”或者“随机的”，即任意两个元组（t11,t12,...,t1D）和（t21,t22,...,t2D）只有忽略所有项才能合并，即：t1i≠t2i,i=1,2,...,D。这时，不管我们如何选择忽略的维，都会产生k个元组，除非忽略所有的维。所以包含单元的最大个数为：

（c）1.最少情况：将k个元组放在在一个完全相同的基本单元中。因此，当所有k个元组都在一个基本单元时，共产生 $2^{D}$ 个单元。

2.最大情况：我们如果用 $\left \lfloor k/c \right \rfloor$ （因为我们最多可以得到个基本方体），按照（b）的方法可得到最终结果

（d）通过（c）的分析，因为在这里只要调整k使k满足:k>=v，那么阈值v可以不用考虑。因此，为方便起见，我们将不考虑阈值v。

1.最少情况：如果我们把所有k个元组都放入一个基本单元中，那么闭单元的个数最少为1。

2.最大情况：给定一个p元组{t1,t2,...,tp}，那么最多有一个闭单元。这样,我们可以得到上界

思路：假设有一个2*2*....*2的k维方体，则k个元组基于如下坐标系分布：t1=(1,0,...,0),t2=(0,1,0,...,0),...,tk=(0,0,0,...,0,1)。则（*1,*2,...,*p,0,...,0）是一个闭方体单元（因为把任意一个*变为0或1会导致计数变为p-1或1）。所以一共有2^k-1个闭方体单元。注意到这种情况下k k，则当达到不满足该条件的上限时，可以停止递归。

5.8 假设计算维A、 B、C、D的冰山立方体，其中希望物化满足最小支持度计数v的所有单元，并且维的基数满足cardinality(A) < cardinality(B) < cardinality(C) < cardinality(D)。显示构造以上冰山立方体的BUC处理树(该树显示BUC算法从all开始考察数据立方体格的次序)。

我们知道应该按基数递减的顺序处理维，即首先使用最有区别的维，以期希望我们能够尽快修剪搜索空间。在这种情况下，我们应该以D，C，B，A的顺序计算立方体，遍历顺序下图所示。

5.9 讨论如何扩展Star-Cbing算法计算冰山立方体、其中冰山条件测试avg不大于某个值v。

代替使用平均值，我们可以使用每个单元的底部k平均值，它是反单调的。如果一个单元格的最低k平均值大于v，则可以确定没有后代单元格（尺寸较小的单元格）的最低k平均值可以小于v。为了减少检查底k平均条件所需的空间量，我们可以存储一些统计信息，例如落在一定范围v之间的基本元组的计数和总和（例如，小于v，[1.0-1.2)乘以v，[1.2-1.4）乘以v等），然后使用这几个值进行修剪。

5.10 旅行代理的航班数据仓库包含6个维: traveler、departure(city)、departure_time、arrival、arrival_time和flight,两个度量: count()和 avg_fare(),其中avg_fare()在最低层存放具体费用，而在其他层存放平均费用。 (a)假设该立方体是完全物化的。从基本方体[traveler、departure、departure_time、arrival、arrival_time]开始，为了列出2009年每个从洛杉矶乘坐美国航空公司(AA) 的商务旅客的月平均费用，应该执行哪些OLAP操作(例如，上卷flight到airline)? (b)假设想计算数据立方体，其中条件是记录的个数最少为10,并且平均费用超过500美元。勾画一种有效的立方体计算方法(基于航班数据分布的常识)。

（a）The OLAP operations are:

i. roll-up on traveller to the level of category and dice on “business”ii. roll-up on departure to the level of city and dice on “L.A.”iii. roll-up on departure_time to the level of “ANY” (∗)iv. roll-up on arrival to the level of “ANY” (∗)v. roll-up on arrival_time to the level of “ANY” (∗)vi. roll-up on ﬂight to the level of company and dice on “AA”vii. drill-down on traveller to the level of individualviii. drill-down on departure_time to the level of month.

（b）有两个约束：min_sup = 10和avg_fare>500。使用冰山立方体算法，例如BUC。由于avg_fare> 500不是反单调的，因此应将其转换为top-k-avg，即 $avg^{10}(fare) 500$ 。使用分箱+min_sup修剪立方体的计算量。

5.11 (实现项目)有四种典型的数据立方体计算方法: MuliWey[ ZDN97]、BUC BR99、H ouing[ HP. DW01]和Star- cubing[ XHLW03]。

(a)从这些立方体计算算法中任选一种加以实现，并介绍你的实现、实验和性能。找另外一个在相同平台(如Limux 上C+ +)实现不同算法的学生，比较你们的算法性能。输人: i.一个n维基本方体表(n

【本文地址】

公司简介

联系我们