习题及参考答案 下载本文

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 页