哈尔滨医科大学《数据挖掘》第7章 关联分析2.pptVIP

可以用若干优化策略来进一步提高挖掘算法的性能。首先，可以限制被视为对称二元变量的变量数。更具体地说，仅当y频繁时才认为y的负项是有趣的。 该策略的理由是，稀有项趋向于产生大量的非频繁模式，并且其中许多都不是令人感兴趣的。 另一种策略是限制负模式的类型。例如，算法考虑负模式 , 如果它至少包含一个正项（即|X|=1）。 该策略的理由是，如果数据集包含少量支持度大于50%的正项，则大部分形如 的负模式都将是频繁的。这样就会降低挖掘算法的性能。 基于支持度期望的技术 该方法要求仅当非频繁模式的支持度显著小于期望支持度时，才认为它是有趣的。 本节介绍两种计算期望支持度的方法。 基于概念分层的支持度期望 基于间接关联的支持度期望 基于概念分层的支持度期望 仅用客观度量还不足以删除不感兴趣的非频繁模式。 例如，假设面包和台式计算机是频繁项。即使项集{面包，台式机}是非频繁的，并且可能是负相关，它也不是有趣的。因为在领域专家看来，它们的支持度低是显然的，因为它们属于两个完全不同的产品类（期望支持度低）。 因此，需要确定期望支持度，并用它来避免产生上面那种非频繁模式。 计算期望支持度的一种方法是利用概念分层来推导 例如：由于火腿和熏肉属于相同的产品族，我们预期火腿和薄片食物之间的关联与熏肉和薄片食物之间的关联类似。 如果任何一对的真实支持度小于期望支持度，则非频繁模式是有趣的。 计算期望支持度的公式 假定项集{C，G}是频繁的。用s(．)表示模式的实际支持度，而表示ε(.)期望支持度。C和G的子女或兄弟的期望支持度可以用如下公式计算： 节食碳酸饮料和薄片食物的期望支持度可以使用公式（7-8）计算。因为这两项分别是碳酸饮料和点心的子女。 如果节食碳酸饮料薄片食物的实际支持度明显低于它们的期望值，则节食碳酸饮料和薄片食物形成一个有趣的非频繁模式。 基于间接关联的支持度期望 本节提供一种确定商品对期望支持度的方法：考察通常与这两个商品一起购买的其他商品。 假定节食和普通碳酸饮料都经常与薄片食品和点心一起购买。这两种商品可望是相关的，并且它们的支持度应当较高。 因为他们的实际支持度低，节食和普通碳酸饮料形成了一个有趣的非频繁模式。这样的模式称作间接关联（indirect association）模式。 间接关联的一个高层解释见图7-27。项a和b对应于节食和普通碳酸饮料，而Y称作中介集（mediator set），包含诸如薄片食物和点心等商品。间接关联形式定义在下面给出。 定义7.12 间接关联 一对项a，b是通过中介集Y间接关联的，如果下列条件成立： (1)s({a,b})ts（项对支持度条件） 中介支持度和依赖条件用来确保Y中的项形成a和b的近邻。可以使用6.7.1节介绍的兴趣因子、余弦或IS、Jaccard和其他依赖度量。 间接关联可以用如下方法产生。首先，使用诸如Apriori和FP增长等标准算法产生频繁项集。然后，合并每对频繁k-项集得到候选间接关联(a,b,Y)，其中a和b是一对项，而Y是它们的公共中介。 例如，{p,q,r}和{p,q,s}是频繁3-项集，则通过合并这对频繁项集得到候选间接关联(r,s,{p,q})。 一旦产生候选，就要验证它是否满足定义7.12中的项对支持度和中介依赖条件。 中介支持度条件不必验证，因为候选间接关联是通过合并一对频繁项集得到的。 习题 考虑下表所示的数据集。第一个属性是连续的，而其余两个属性是非对称二元的。一个规则是强规则，如果它的支持度超过15%且置信度超过60%。表中数据支持如下两个强规则： (i) {(1 ≤ A ≤ 2),B = 1} → {C = 1} (ii) {(5 ≤ A ≤ 8),B = 1} → {C = 1} 习题 (a)计算这两个规则的支持度和置信度。 (b)为了使用传统的Apriori算法找出这些规则，我们需要离散化连续属性A。假定我们使用等宽分箱方法离散化该数据，其中bin-width=2，3，4.对于每个bin-width，上面两个规则是否能够被Apriori算法发现？对于每个与前面规则对应的规则，计算其支持度和置信度。 习题 对于下面给定的每个序列w=e1, e2, …ei, ei+1,… elast，确定它们是否是序列{1,2,3}{2,4}{2,4,5}{3,5}{6}的子序列，时限约束为：mingap=0; maxgap=3; maxspan=5; ws=1; w={1}{2}{3} w={1,2,3,4}{5,6} w={2,4}{2,4}{6} w={1}{2,4}{6} w={1,2}{3,4}{5,6} 习题 确定上面每个子序列w是否是下面序列s的邻接