i) 在两个对象a和b中，只要其中一个对象在另一个对象的最近另列表中，我们就设置Mba = Mab = 1（Mab是指邻近度矩阵中a行和b列交叉项的值）；
ii) 当某个对象a不在另一对象b的k最近邻中时，不管另一对象b是否在该对象a的最近邻中，我们设置Mba = Mab = 0。
4.13给出一个簇集合的例子，其中基于簇的接近性的合并得到的簇集合比基于簇的连接强度
(互连性)的合并得到的簇集合更自然。 答：簇集合例子如下图所示：
图 (a) 图 (b)
图(a)两个簇合并后的接近性显然较图(b)要差，因此，如果是基于簇的接近性来合并图中的簇，则会合并图(b)的两个簇，合并得到的簇结构几乎与原来的每个簇一样。
第5章关联分析
5.1 列举关联规则在不同领域中应用的实例。
答：在医学领域：发现某些症状与某种疾病之间的关联，为医生进行疾病诊断和治疗提供线
索；
在商业领域：发现商品间的联系，为商场进行商品促销及摆放货架提供辅助决策信息； 在地球科学领域：揭示海洋、陆地和大气过程之间的关系。
5.2 给出如下几种类型的关联规则的例子，并说明它们是否是有价值的。
(a)高支持度和高置信度的规则； (b)高支持度和低置信度的规则；
(c)低支持度和低置信度的规则； (d)低支持度和高置信度的规则。
答：(a)如牛奶 -> 面包，由于这个规则很明显，所以不具有价值。
(b)如牛奶->大米，由于牛奶、大米销售量都比较高，所以有高支持度。但是很多事务不同时包括牛奶和大米，所以置信度很低，不具有价值。
(c)如可乐->洗衣粉，由于置信度低，所以不具有价值。 (d)如尿布->啤酒，虽然支持度低，不过置信度高，具有价值。
5.3 数据集如表5-14所示：
表5-14 习题5.3数据集
Customer ID 1 1 2 Transaction ID 0001 0024 0012 第 21 页 共 27 页
Items Bought {a, d, e} {a, b, c, e} {a, b, d, e} 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的支持度
第 22 页 共 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划分为d1 d2…dn个子数据集，包含的事务数分别为a1 a2…an。如果D中的某一个频繁项集s在D的所有子数据集中是非频繁的，在每个子数据集中包含s的事务数为c1 c2…cn，则
c1≤a1 * min_support，c2≤a2 * min_support，…，
cn/≤an * min_support。(c1+c2+…+cn) ≤(a1+a2+?an) * min_support。
由于(c1+c2+…+cn)为数据集D中包含s的事务数，a1+a2+?an为数据集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 购买的商品 {M, O, N, K, E, Y} {D, O, N, K, E, Y} {M, A, K, E} {M, U, C, K, Y} T500 {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}
第 23 页 共 27 页
(2)穷举法：
M=2-1=2-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相依表
Hamburgers hamburgers ?col hot dogs 2,000 1,000 3,000 hot dogs 500 1,500 2,000 ?row 2,500 2,500 5,000 k
11
假设挖掘出的关联规则是“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%
故这个关联规则是强规则。
第 24 页 共 27 页