数据挖掘课后题答案(3)

3

3 3 OKE 3 C3 KEY 2 4 3

L 3 OKE 3

FP-growth：数据库的第一次扫描与 Aprio ri 算法相同，得到 L 1。再按支持度 计数的递减序排序，得到：L={(K:5), (E:4), (M:3), (O:3), (Y:3)}。扫描没个事 务，按以上 L 的排序，从根节点开始，得到 FP-树。

Root

E:4

M:1

Y:1

Y:1

题 5.3 图 FP 增长算法

效率比较：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 在该行具有给定值的元组数。

department sales sales sales systems systems systems systems marketing marketing secretary secretary

status senior junior junior junior senio r junior senio r senior junior senior junior

age 31 3526 30 31 35 21 25 31 35 26 30 41 45 36 40 31 35 46 50 26 30

salary 46K 50K26K 30K 31K 35K 46K 50K 66K 70K 46K 50K 66K 70K 46K 50K 41K 45K 36K 40K 26K 30K

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 ； ∵ 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 ；