第 5 章关联分析
5.1 列举关联规则在不同领域中应用的实例。
答：在医学领域：发现某些症状与某种疾病之间的关联，为医生进行疾病诊断和治疗提供线 索；
在商业领域：发现商品间的联系，为商场进行商品促销及摆放货架提供辅助决策信息； 在地球科学领域：揭示海洋、陆地和大气过程之间的关系。
5.2 给出如下几种类型的关联规则的例子，并说明它们是否是有价值的。 (a) 高支持度和高置信度的规则； (b) 高支持度和低置信度的规则； (c) 低支持度和低置信度的规则； (d) 低支持度和高置信度的规则。
答： (a) 如牛奶 -> 面包，由于这个规则很明显，所以不具有价值。
(b) 如牛奶 -> 大米，由于牛奶、大米销售量都比较高，所以有高支持度。但是很多事务 不同时包括牛奶和大米，所以置信度很低，不具有价值。 (c) 如可乐 -> 洗衣粉，由于置信度低，所以不具有价值。
(d) 如尿布 -> 啤酒，虽然支持度低，不过置信度高，具有价值。 5.3 数据集如表 5-14 所示： 表 5-14 习题 5.3 数据集
Customer ID Transaction ID Items Bought 1 1 2 0001 0024 0012 {a, d, e} {a, b, c, e} {a, b, d, e}
第 22 页 共 27 页 2 3 3 4 4 5 5 0031 0015 0022 0029 0040 0033 0038 {a, c, d, e}
{b, c, e} {b, d, e} {c, d} {a, b, c} {a, d, e} {a, b, e}
(a) 把每一个事务作为一个购物篮，计算项集 {e}, {b, d} 和 {b, d, e} 的支持度。
(b) 利用 (a) 中结果计算关联规则 {b, d} → {e} 和 {e} → {b, d} 的置信度。置信度是一个对称 的度量吗？
(c) 把每一个用户购买的所有商品作为一个购物篮，计算项集 {e}, {b, d} 和 {b, d, e} 的支持 度。
(d) 利用 (b) 中结果计算关联规则 {b, d} → {e} 和 {e} → {b, d} 的置信度。置信度是一个对称 的度量吗？
答： (a) s({e}) = 8/10 =0.8 ; s({b,d}) = 2/10 = 0.2 ; s({b,d,e}) = 2/10 = 0.2.
(b) c({b,d}->{e}) = s({b,d,e})/s({b,d}) = 0.2/0.2 = 1; c({e}->{b,d}) =s({b,d,e})/s({e}) = 0.2/0.8 = 0.25.
由于 c({b,d}->{e}) ≠ c({e}->{b,d}) ，所以置信度不是一个对称的度量。 (c) 如果把每一个用户购买所有的所有商品作为一个购物篮，则 s({e}) = 4/5 =0.8 ; s({b,d}) = 5/5 = 1 ; s({b,d,e}) = 4/5 = 0.8.
(d) 利用 c 中结果计算关联规则 {b, d} → {e} 和 {e} → {b, d} 的置信度 , 则 c({b,d}->{e}) = 0.8/1 = 0.8 c({e}->{b,d}) = 0.8/0.8 = 1 置信度不是一个对称的度量
5.4 关联规则是否满足传递性和对称性的性质？举例说明。 答：关联规则不满足传递性和对称性！ 例如： s(A,B) = 50% s(A) = 70% s(A,C) = 20% s(B) = 90% s(B,C) = 70% s(C) = 60%
设最小置信度 minconf = 60% ，则 : c(A → B) = s(A,B) / s(A) =71% > minconf c(B → C) = s(B,C) / s(B)=66% > minconf
但是 c(A → C) = s(A,C) / S(A)=28% < minconf ，不满足传递性 c(B → A)= s(A,B) / s(B)=55% < minconf ， 不满足对称性 5.5 Apriori 算法使用先验性质剪枝，试讨论如下类似的性质 (a) 证明频繁项集的所有非空子集也是频繁的
(b) 证明项集 s 的任何非空子集 s ’的支持度不小于 s 的支持度 第 23 页 共 27 页
(c) 给定频繁项集 l 和它的子集 s ，证明规则“ s’ → (l – s’)” 的置信度不高于 s →
(l – s) 的置信
度，其中 s’ 是 s 的子集
(d) Apriori 算法的一个变形是采用划分方法将数据集 D 中的事务分为 n 个不相交的子数据
集。证明 D 中的任何一个频繁项集至少在 D 的某一个子数据集中是频繁的。
证明： (a) 设 s 为频繁项集， s’ 为 s 的子集， min_supp_count 为最小支持度计数。由于包含 s
的事务也一定包含 s’ ，所以 support_ count(s’) ≥ support_count(s) ≥ min_support_count ， s’ 也是频繁的。
(b) 设数据集为 D ， |D| 为数据集中的事务数。由于 support_ count(s’) ≥ support_count(s) ， 所以 support_count(s’)/|D| ≥ support_count(s)/|D| ，即 support (s’) ≥ support (s) 。 (c) 规则“ s → (l – s’)” 的置信度 confidence(s → (l – s)) = support(l)/support(s) ，规则
“ s’ → (l – s’)” 的置信度 confidence(s’ → (l – s’)) = support(l)/support(s’) 。 由于 support (s’) ≥ support (s) ，故“ s’ → (l – s’)” 的置信度不高于 s → (l – s) 的置信度。 (d) 反证法证明。
设 min_support 为最小支持度。 D 划分为 d 1 d 2 …d n 个子数据集，包含的事务数分别
为 a 1 a 2 …a n 。如果 D 中的某一个频繁项集 s 在 D 的所有子数据集中是非频繁的， 在每个子数据集中包含 s 的事务数为 c 1 c 2 …c n ，则
c 1 ≤ a 1 * min_support ， c 2 ≤ a 2 * min_support ， … ，
c n / ≤ a n * min_support 。 (c 1 +c 2 +…+c n ) ≤(a 1 +a 2 +?a n ) * mi n_support 。 由于 (c 1 +c 2 +…+c n ) 为数据集 D 中包含 s 的事务数，a 1 +a 2 +?a n 为数据集 D的事务 数，所以 s 是非频繁的，与 s 在 D中是频繁的矛盾。命题得证。
5.6 考虑如下的频繁 3- 项集： {1, 2, 3} ， {1, 2, 4} ， {1, 2, 5} ， {1, 3, 4} ， {1, 3, 5} ， {2, 3, 4} ，
{2, 3, 5} ， {3, 4, 5} 。
(a) 根据 Apriori 算法的候选项集生成方法，写出利用频繁 3- 项集生成的所有候选 4- 项集。 (b) 写出经过剪枝后的所有候选 4- 项集
答： (a) 利用频繁 3- 项集生成的所有候选 4- 项集： {1,2,3,4} {1,2,3,5} {1,2,4,5} {1,3,4,5} {2,3,4,5} (b) 经过剪枝后的所有候选 4- 项集： {1,2,3,4} {1,2,3,5}
5.7 一个数据库有 5 个事务，如表 5-15 所示。设 min_sup=60% ， min_conf = 80% 。 表 5-15 习题 5.7 数据集 事务 ID 购买的商品 T100 T200 T300 T400 T500
{M, O, N, K, E, Y}
{D, O, N, K, E, Y} {M, A, K, E} {M, U, C, K, Y} {C, O, O, K, I ,E}
(a) 分别用 Apriori 算法和 FP-growth 算法找出所有频繁项集。比较两种挖掘方法的效率。 (b) 比较穷举法和 Apriori 算法生成的候选项集的数量。
(c) 利用 (1) 所找出的频繁项集，生成所有的强关联规则和对应的支持度和置信度。 答： (1) 频繁 1- 项集： M,O,K,E,Y
频繁 2- 项集： {M,O} ， {O,K} ， {O,E} ， {K,Y} ， {K,E} 频繁 3- 项集： {O,K,E} 第 24 页 共 27 页 (2) 穷举法：
M=2 k -1=2 11 -1=2047
Apriori 算法： 23
(3) {O,K} — >{E} ，支持度 0.6 ，置信度 1 {O,E} — >{k} ，支持度 0.6 ，置信度 1
5.8 购物篮分析只针对所有属性为二元布尔类型的数据集。如果数据集中的某个属性为连续
型变量时，说明如何利用离散化的方法将连续属性转换为二元布尔属性。比较不同的离 散方法对购物篮分析的影响。
答： 首先利用等频、等宽等方法将连续属性离散化，然后将离散化后的每个区间映射为一 个二元属性。
离散化时，如果区间太宽，可能因为缺乏置信度而失去某些模式；如果区间太窄，则 可能因为缺乏支持度而失去某些模式。
5.9 分别说明利用支持度、置信度和提升度评价关联规则的优缺点。 答：支持度
优点：支持度高说明这条规则可能适用于数据集中的大部分事务。
缺点：若支持度阈值过高，则许多潜在的有意义的模式由于包含支持度小的项而被删去； 若支持度阈值过低，则计算代价很高而且产生大量的关联模式。 置信度
优点：置信度高说明如果满足了关联规则的前件，同时满足后件的可能性也非常大。 缺点：找到负相关的关联规则。 提升度：
优点：提升度可以评估项集 A 的出现是否能够促进项集 B 的出现 缺点：会产生出现伪相互独立的规则。
5.10 表 5-16 所示的相依表汇总了超级市场的事务数据。其中 hot dogs 指包含热狗的事务，
hot dogs 指不包含热狗的事务。 hamburgers 指包含汉堡的事务， hamburgers 指不包 含汉堡的事务。
表 5-16 习题 5.10 相依表 hot dogs hot dogs Σ row
Hamburgers 2,000 500 2,500 hamburgers 1,000 1,500 2,500 Σ col 3,000 2,000 5,000
假设挖掘出的关联规则是“ hot dogs ? hamburgers” 。给定最小支持度阈值 25% 和最小 置信度阈值 50% ，这个关联规则是强规则吗？
计算关联规则“ hot dogs ? hamburgers” 的提升度，能够说明什么问题？购买热狗和购买 汉堡是独立的吗？如果不是，两者间存在哪种相关关系？
答： s({hot dogs})=3000/5000=60%; s({hot dogs, hamburgers})=2000/5000=40% C({hot dogs} → {hamburgers})=40%/60%=66.7% 故这个关联规则是强规则。 第 25 页 共 27 页
S({hamburgers})=2500/5000=50%
提升度 lift({hot dogs} → {hamburgers})= C({hot dogs} → {hamburgers})/ S({hamburgers}) =1.334 提升度大于 1 ，表明 hot dogs 和 hamburgers 不是互相独立的，二者之间存在正相关 关系。
5.11 对于表 5-17 所示序列数据集，设最小支持度计数为 2 ，请找出所有的频繁模式。 表 5-17 习题 5.11 数据集 Sequence ID Sequence ID 1 2 3 4
<(ad)c(bc)(ae)> <(e f )(ab)(d f )cb>
答：频繁 1- 序列：
、 、
、 、 、 、 、
频繁 3- 序列：
、 、 、 、 、 、
第 6 章离群点挖掘
6. 1 为什么离群点挖掘是重要的？
