数据挖掘概念与技术 - 课后题答案汇总

数据挖掘——概念概念与技术 Data Mining

Concepts and Techniques

习题解答

Jiawei Han

Micheline Kamber 范明 孟晓峰 译

著

目录

第 1 章 引言

1.1 什么是数据挖掘？在你的回答中，针对以下问题：

1.2 1.6 定义下列数据挖掘功能：特征化、区分、关联和相关分析、预测聚 类和演变分析。使用你熟悉的现实生活的数据库，给出每种数据挖掘功 能的例子。 解答：

? 特征化是一个目标类数据的一般特性或特性的汇总。例如，学生的特征 可被提出，形成所有大学的计算机科学专业一年级学生的轮廓，这些特 征包括作为一种高的年级平均成绩(GPA：Grade point aversge) 的信息， 还有所修的课程的最大数量。

? 区分是将目标类数据对象的一般特性与一个或多个对比类对象的一般 特性进行比较。例如，具有高 GPA 的学生的一般特性可被用来与具有 低 GPA 的一般特性比较。最终的描述可能是学生的一个一般可比较的 轮廓，就像具有高 GPA 的学生的 75%是四年级计算机科学专业的学生， 而具有低 GPA 的学生的 65%不是。

? 关联是指发现关联规则，这些规则表示一起频繁发生在给定数据集的特 征 值的 条 件。 例 如， 一 个数 据 挖掘 系 统可 能 发现 的

关联 规 则为 ： major(X,

“ computing

science”) ?

owns(X, “personal computer” )

confid

[support=12%, ence=98%]

其中，X 是一个表示学生的变量。这个规则指出正在学习的学生，12%

（支持度）主修计算机科学并且拥有一台个人计算机。这个组一个学生 拥有一台个人电脑的概率是 98%（置信度，或确定度）。 ? 分类与预测不同，因为前者的作用是构造一系列能描述和区分数据类型 或概念的模型（或功能），而后者是建立一个模型去预测缺失的或无效 的、并且通常是数字的数据值。它们的相似性是他们都是预测的工具： 分类被用作预测目标数据的类的标签，而预测典型的应用是预测缺失的 数字型数据的值。

? 聚类分析的数据对象不考虑已知的类标号。对象根据最大花蕾内部的相 似性、最小化类之间的相似性的原则进行聚类或分组。形成的每一簇可 以被看作一个对象类。聚类也便于分类法组织形式，将观测组织成类分 层结构，把类似的事件组织在一起。

? 数据延边分析描述和模型化随时间变化的对象的规律或趋势，尽管这可 能包括时间相关数据的特征化、区分、关联和相关分析、分类、或预测， 这种分析的明确特征包括时间序列数据分析、序列或周期模式匹配、和 基于相似性的数据分析

1.3 1.9 列举并描述说明数据挖掘任务的五种原语。 解答：

用于指定数据挖掘任务的五种原语是： ? 任务相关数据：这种原语指明给定挖掘所处理的数据。它包括指明数据 库、数据库表、或数据仓库，其中包括包含关系数据、选择关系数据的 条件、用于探索的关系数据的属性或维、关于修复的数据排序和分组。 ? 挖掘的数据类型：这种原语指明了所要执行的特定数据挖掘功能，如特 征化、区分、关联、分类、聚类、或演化分析。同样，用户的要求可能 更特殊，并可能提供所发现的模式必须匹配的模版。这些模版或超模式 （也被称为超规则）能被用来指导发现过程。 ? 背景知识：这种原语允许用户指定已有的关于挖掘领域的知识。这样的 知识能被用来指

(a) 使用 min-max 规范化将 age 值 35 变换到[0.0，1.0]区间。

(b) 使用 z-score 规范化变换 age 值 35，其中 age 的标准差为 12.94 岁。

(c) 使用小数定标规范化变换 age 值 35。

(d) 对于给定的数据，你愿意使用哪种方法？陈述你的理由。 解答：

(a) 使用 min-max 规范化将 age 值 35 变换到[0.0，间。 ∵_max minA=1.0 A=13，而，maxA=70，new _min A=0.0，new v?' ?v ? v=35， ?new _ A

? new A

A

min

max _ min ? ? new _ minA

max A ? min A ? 70 35 ?? 13 13

?1.0 ? 0.0 ? ? 0.0 ? 0.3860 1.0]区

(b) 使用 z-score 规范化变换 age 值 35，其中 age 的标准差为 12.94 岁。

? 19 ? 2 ? 20 ? 21 ? 2 ? 22 ? 4 ? 25 A ? 13 ? 15 ? 2 ? 16 27

? 30 ? 2 ? 33 ? 4 ? 35 ? 36 ? 40

? 45 ? 46 ? 52 ? 70

27

? 809 ? 29 .963 27 ?

?? ?Ai ?2 ? 12.7002 A ??? σ 2 σ i?1 161.2949 ，

N ??

σ A ??

? ?? ?Ai ?

2 ? 12.9421 或 s A ??? s 167 .4986 2 ??i?1N ， sA ??

v=35 v ? A 35 5.0? 0.3966 ? 0.400 v ' ? ? ? 29.963 ??37

12.7002 σ A

12.70 02

v ? A 35 或 v ' ? ? 5.0? 0.3892 ? 0.39 ? 29.963 ??37

sA 12.9421

12.94 21

(c) 使用小数定标规范?

化变换 age 值 35。 ?

v ? ? 0.35

35 由于最大的绝对值为 10 j 10 2

70，所以 j=2 。 v' ??

(d) 对于给定的数据，你愿意使用哪种方法？陈述你的理由。

略。

N

A

A

N

A

A

σ

s

2.6 2.14 假设 12 个销售价格记录组已经排序如下：5，10，11，13，15，35，

50，55，72，92，204，215。使用如下每种方法将其划分成三个箱。

(a) 等频（等深）划分。 (b) 等宽划分。 (c) 聚类。 解答：

(a) 等频（等深）划分。

bin5,10,11,bin15,35,50

(b) 等宽划分。

每个区间的宽度是：(215-5)/3=70

bin5,10,11,13,15,35bin9bin204,2bin1 72,91,204,215

(c) 聚类。

我们可以使用一种简单的聚类技术：用 2 个最大的间隙将数据分成 3 个箱。

bin5,10,11,1bin35,50,55,bin204,212.7 2.15 使用习题 2.4 给出的 age 数据， (a) 画出一个等宽为 10 的等宽直方图； (b) 为如下每种抽样技术勾画例子：SRSWOR，

SRSWR ，聚类抽样，分层 抽样。使用大小为 5 的样本和层“青年”，“中年”和“老年”。 解答：

(a) 画出一个等宽为 10 的等宽直方图；

8 7 6 5 4 3 2 1 0 15 25 35

45 55 65 (b) 为如下每种抽样技术勾画例子：SRSWOR，SRSWR ，聚类抽样，分层 抽样。使用大小为 5 的样本和层“青年”，“中年”和“老年”。

元组：

T 1T 2T 3T 1T 2T 3T 1T 2T 3T 1T 2T 3T 1T 2T 4T 2T 3T 4T 2T 3T 4T 2T 3T 5T 2T 3T 7 SRSWOR 和 SRSWR：不是同次的随机抽样结果可以不同，但前者因无放回

所以不能有相同的元组。

SRSW(n=SRS(n=16 T 2T 20 T 2T 22 T 3T 25 T 3T52 T 4T 聚类抽样：设起始聚类共有 6 类，可抽其中的 m 类。 SampleT 1 13 T 2 15 T 3 16 T 4 16 T 5 19 SampleT20 T 20 T21 T22 T 22 SampleT 25 T 25 T 25 T 25 T 30 SampleT 33 T 33 T 35 T 35 T 35 SampleSampleT 35 T 52 T 36 T 70 T 40 T 45 T 46

Sample2 Sample5

∵ P(senio r)=52/165=0.32； ∴ P(X|junior)P(junior)=0.01796×0.68=0.0122128>0=0=P(X|senior)P(senio r)； 所以：朴素贝叶斯分类器将 X 分到 junio r 类。 解二：设元组的各属性之间不独立，其联合概率不能写成份量相乘的形式。 所以已知：X=(department=system,age=26?30,salary=46K?50K)，元组总数 为：30+40+40+20+5+3+3+10+4+4+6=165。 先验概率：

当 status=senio r 时，元组总数为：30+5+3+10+4=52，P(senior)=52/165=0.32 ；

当 status=junio r 时 ， 元 组 总 数 为 ： 40+40+20+3+4+6=113 ， P(junio r)=113/165=0.68 ；

因为 status=senio r 状态没有对应的 age=2 6?30 区间，所以：P(X|senior)=0； 因为 status=junio r 状态对应的 partment=systems 、age=26?30 区间的总元组 数为：3，所以：P(X|junior)=3/113； 因为：P(X|junior)P(junior)=3/113×113/165＝0.018>0=P(X|senior)P(senior)； 所以：朴素贝叶斯分类器将 X 分到 junio r 类。

(d) 为给定的数据设计一个多层前馈神经网络。标记输入和输出层节点。

(e) 使用上面得到的多层前馈神经网络，给定训练实例（sales，senior，31?

35，46K?50K），给出后向传播算法一次迭代后的权重值。指出你使用的 初始权重和偏倚以及学习率。

6.3 2008-12-01 6.4 2008-12-01

T 20 T235 T 20 T236 T 21 T240 T 22 T245 T 22 T246 分层抽样：按照年龄分层抽样时，不同的随机试验结果不同。

TTTTTTT T T111112222youyouyouyouyouyouyouyouyouT T T T T T T T T 222223333young T young T young T young T young T middle T middle T middle T middle T 1young 2young 3middle 4middle 7Senio 333344457middle middle middle middle middle middle middle middle senior

TT T T T 2.8 55555555555555555555555555

第 3 章 数据仓库与 OLAP 技术概述

3.1 3.4 假定 BigUniversity 的数据仓库包含如下 4 个维：student(student_name,

area_id , major, status, university) ， course(course_name, department) ， semester(semester, year) 和 instructor(dept, rank)；2 个度量：count 和 avg_grade。 在最低概念层， 度量 avg_grade 存放学生的实际 课程成绩。在较高概念层， avg_grade 存放给定组合的平均成绩。 (a) 为该数据仓库画出雪花形模式图。

(b) 由 基 本 方 体 [student, course, semester, instructor] 开 始 ， 为 列 出 BigUniversity 每个学生的 CS 课程的平均成绩，应当使用哪些特殊 的 OLAP 操作。

(c) 如果每维有 5 层（包括 all），如“studenta) 为该数据仓库画出雪花形模式图。雪花模式如图所示。

b) 由 基 本 方 体 [student, course, semester, instructor] 开 始 ， 为 列 出 BigUniversity 每个学生的 CS 课程的平均成绩，应当使用哪些特殊的 OLAP 操作。

这些特殊的联机分析处理（OLAP ）操作有：

i. 沿课程（course）维从 course_id

“上卷”到 department。

ii. 沿学生（student）维从 student_id “上卷”到

第 3 章 数据仓库与 OLAP 技术概述

university 。

iii. 取 department= “CS ”和 university= “Big

University ”，沿课程

（course）维和学生（student）维切片。 iv. 沿学生（student）维从 university 下钻到 student_name。

c) 如果每维有 5 层（包括 all），如“student

course 维表 course_id course_name department semester 维表 semester_id semester year

instructor 维表 Instructor_id dept

rank

univ 事实student_id表 course_id semester_id instructor_id count avg_grade student

维表 student_id student name area_id major status university

area 维表 area_id city provi nce country

题 3.4 图 题 3.4 中数据仓库的雪花形模式

3.2 2222222 3.3 3333333

第 4 章 数据立方体计算与数据泛化

4.1 2008-11-29

4.2 有几种典型的立方体计算方法，

4.3 题 4.12 考虑下面的多特征立方体查询：按{item ，regio n，month} 的所有 子集分组，对每组找出 2004 年的最小货架寿命，并对价格低于 100 美元、货架 寿命在最小货架寿命的 1.25~1.5 倍之间的元组找出总销售额部分。

d) 画出该查询的多特征立方体图。 e) 用扩充的 SQL 表示该查询。 f) 这是一个分布式多特征立方体吗？为什么？ 解答： (a) 画出该查询的多特征立方体图。 R 0→R1(≥1.25*min(shelf)and≤1.5*min(shelf)) (b) 用扩充的 SQL 表示该查询。

select item, region, month, Min(shelf), SUM(R1) from

Purcha

se where 004

cube by item, region, month: R1 such that R1.shelf≥1.25*MIN(Shelf) and

year=2

第 4 章 数据立方体计算与数据泛化

(R1.Shelf≤1.5*MIN(Shelf) and R1.Price<100

(c) 这是一个分布式多特征立方体吗？为什么？ 这不是一个分布多特征立方体，因为在“such that”语句中采用了“≤”条 件。 4.4 2008-11-29 4.5 2008-11-29

第 5 章 挖掘频繁模式、关联和相关

5.1 Aprio ri 算法使用子集支持度性质的先验知识。 5.2 5.2.2 节介绍了由频繁项集产生关联规则的方法。提出了一个更有效的方 法。解释它为什么比 5.2.2 节的方法更有效。（提示：考虑将习题 5.1(b)和习题 5.1(c) 的性质结合到你的设计中。） ■

5.3 数据库有 5 个事物。设 min_sup=60%，min_conf=80 。 TID 购买的商品 T100 {M, O, N, K, E, Y}

T200 {D, O, N, K,

E, Y} T300

{M, A, K, E}

T400 {M, U, C, K, Y} T500 {C, O, O, K, I, E}

g) 分别使用 Aprio ri 和 FP 增长算法找出所有的频繁项集。比较两种挖 掘过程的效率。 h) 列举所有与下面的的元规则匹配的强关联规则（给出支持度 s 和置 信度 c），其中，X 是代表顾客的变量，item 是表示项的变量（如“A”、 “B ”等）：

?x?transaction, buys(X, item 1)∧buys(X, item 2)?buys(X, item 3) [s, c] 解答：

(a) 分别使用 Aprio ri 和 FP 增长算法找出所有的频繁项集。比较两种挖掘过 程的效率。

Aprio ri 算法：由于只有 5 次购买事件，所以绝对支持度是

第 5 章 挖掘频繁模式、关联和相关

5×min_sup=3。

?M? 3?????O 3 ? ???3???M ??O 3 ????? N??

?MO ??1 ??

?MK3 ??????

?MK

3????

? OK3 ?????ME

?

???????

OKE 3????C3 ?KEY 2

??

?2 ??

??

?? ??

2 ?L1 ??5 ? ? K??? K? ??5???2 L?

MYOE2 ? ? ?? 3? E 4

? E??????OK ? 3 ? KE4 ?4??? C???? C ?????2 ? ??

?

???Y1 ? ?

? OE ???3??3 ??? OY 2 D?1? ???? A ?

1?? Y 3 ???????U 1????KE ?KY 3 ?? ?? C 2?? I 1 ???

?KY ??4 ??

?3 L ??3

? ?OKE 3??

EY 2 ????

?

?FP-growthL 1。再按支持度：数据库的第一次扫描与

Aprio ri 算法相同，得到计数的递减序排序，得到：L={(K:5), (E:4),

(M:3), (O:3), (Y:3)}。扫描没个事 务，按以上 L 的排序，从根节点开始，得到 FP-树。

Root K:5 E:4 M:1 O:1 MO:2 :2

Y:

1 Y:1

Y:1

题 5.3 图 FP 增长算法

条件 项 Y{{K,E,M,O:1} ，{K,E,O:1}， {K,M:1}} {{K,E,M:1} O 条件 K:3 K:3 ，产生的频繁{K,Y:3} {K,O:3}，{E,O:3} ，

效率比较：Aprio ri 算法的计算过程必须对数据库作多次扫描，而 FP-增长算 法在构造过程中只需扫描一次数据库，再加上初始时为确定支持度递减排序 的一次扫描，共计只需两次扫描。由于在 Aprio ri 算法中的自身连接过程产 生候选项集，候选项集产生的计算代价非常高，而 FP-增长算法不需产生任 何候选项。

(b) 列举所有与下面的的元规则匹配的强关联规则（给出支持度 s 和置信度 c），其中，X 是代表顾客的变量，item 是表示项的变量（如“A”、“B ” 等）：

?x?transaction, buys(X, “K”) ∧buys(X, “O”)?buys(X, “E ”) [s=0.6, c=1]

?x?transaction, buys(X, “E ”)∧buys(X, “E”) ?buys(X, “K”) [s=0.6, c=1]

或也可表示为

K,O→E[s(support)=0.6 或 60%,c(confid ence)=1 或 100%] E,O→K[s(support)=0.6 或 60%,c(confid ence)=1 或 100%] ■

5.4 （实现项目）使用你熟悉的程序设计语言（如 C++或 Java），实现本章介 绍的三种频繁项集挖掘算法：

5.5 2008-12-01

5.6 2009-01-09

第 6 章 分类和预测

6.1 简述决策树分类的主要步骤。

6.2 6.11 下表由雇员数据库的训练数据组成。数据已泛化。例如，age “31?

35”表示年龄在 31~35 之间。对于给定的行，count 表示 department，status，ag e

和 salary 在该行具有给定值的元组数。

departmsalsalsalsystems systems systems systems marketinmarketinsecretary secretary status senior junior junior junior senio r junior senio r senior junior senior junior ag31?26? 3031?3521?31?25 35?263041 ? 45?3640?3146?35 50?2630 salary 46K?26K? 30K31K?35K46K?66K?50K

70K?46K50K66K ? 70K?46K50K?41K36K?45K

40K?26K30K count 30 40 40 20 5 3 3 10 4 4 6

i) 如何修改基本决策树算法，以便考虑每个广义数据元组（即每一行） 的 count？ j) 使用修改过的算法，构造给定数据的决策树。 k) 给定一个数据元组，它的属性 department，age 和 salary 的值分别为 “systems”，“26?30”，和“46K?50K”。该元组 status 的朴素贝叶 斯分类是什么？

l) 为给定的数据设计一个多层前馈神经网络。标记输入和输出层节点。

m) 使用上面得到的多层前馈神经网络，给定训练实例

（sales，senior ，

31?35，46K?50K），给出后向传播算法一次迭代后的权重值。指出

你使用的初始权重和偏倚以及学习率。 解答：

(a) 如何修改基本决策树算法，以便考虑每个广义数据元组（即每一行） 的 count？

(b) 使用修改过的算法，构造给定数据的决策树。 (c) 给 定一 个数 据元 组， 它的 属性 department ，age 和 salary 的 值分 别为 “systems”，“26?30”，和“46K?50K”。该元组 status 的朴素贝叶斯分 类是什么？

解一：设元组的各个属性之间相互独立，所以先求每个属性的类条件概率：

P(systems|junior)=(20+3)/(40+40+20+3+4+6)=23/113; P(26-30|junior)=(40+3+6)/113=49/113；

P(46K-50K|junior)=(20+3)/113=23/113；

∵ X=(department=system, age=26 ?30,salary=46K?50K)； ∴ P(X|junior)=P(systems|junior)P(26-30|junior)P(46K-50K|junio r)

=23×49×23/1133=25921/1442897=0.01796 ； P(systems|senior)=(5+3)/(30+5+3+10+4)=23/52; P(26-30|senior)=(0)/53=0;

P(46K-50K|senior)=(30+10)/52=40/52 ；

∵ X=(department=system, age=26 ?30,salary=46K?50K)； ∴ P(X|senior)=P(systems|senio r)P(26-30|senior)P(46K-50K|senior)=0;

∵ P(junio r)=113/165=0.68 ；

本文来源：https://www.bwwdw.com/article/227v.html