《数据挖掘基础及其应用》课件第7章

第7章关联规则Ⅰ:频繁模式挖掘7.1引言7.2基本概念7.3频繁项集挖掘7.4频繁模式树算法本章小结

7.1引言

关联规则最初是针对购物篮分析(MarketBasketAnalysis)问题提出的。在店铺中,分店经理想更多地了解顾客的购物习惯,特别是哪些商品容易被顾客同时购买。为回答该问题,需要对商店的事物零售数量进行购物篮分析。该过程通过挖掘顾客放入“购物篮”中的不同商品之间的关联,分析顾客的购物习惯,帮助零售商了解哪些商品频繁地被顾客同时购买,从而辅助他们开发更好的营销策略,如图7-1所示。图7-1购物篮行为分析

在描述有关关联规则的一些细节之前,先来看一个有趣的“尿布与啤酒”的故事。在一家超市里,有一个有趣的现象:尿布和啤酒赫然摆在一起出售,但是这个奇怪的举措却使

尿布和啤酒的销量双双增加了。这个故事一直为商家所津津乐道。实际上这不是一个单纯的故事,而是一个真实发生的事件,主角是大名鼎鼎的沃尔玛。沃尔玛拥有世界上最大的

数据仓库系统,为了能够准确了解顾客在其门店的购买习惯,沃尔玛对其顾客的购物行为进行了购物篮分析,想知道顾客经常一起购买的商品有哪些。

沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上,沃尔玛利用数据挖掘技术对数据进行分析和挖掘。一个意外的发现是:跟尿布一起购买最多的商品竟是啤酒!经过大量的调查和分析,科学家们揭示了一个隐藏在“尿布与啤酒”背后的美国人的一种行为模式:在美国,一些年轻的父亲下班后经常要到超市去买婴儿尿布,而他们中有30%~40%的人同时也为自己买一些啤酒,如图7-2所示。图7-2交易数据与关联规则

同时,一些知名的电子商务站点也从强关联规则的挖掘中受益。这些电子购物网站对关联规则进行挖掘,然后设置用户有意要一起购买的捆绑包。也有一些购物网站使用它们

设置相应的交叉销售,即购买某种商品的顾客会看到相关的另一种商品的广告。

在我国,“数据海量,信息缺乏”是商业银行在数据大集中之后普遍所面临的尴尬状况。金融业实施的大多数数据库只能实现数据的录入、查询、统计等较低层次的功能,却无法发现数据中存在的各种有用信息。关联规则挖掘技术在我国的研究与应用并不是很深入。

7.2基本概念

关联(Associations)分析的目的是挖掘隐藏在数据间的相互关系,即对于给定的一组项目和一个记录集,通过对记录集的分析,得出项目集中项目之间的相关性。项目之间的相关性用关联规则来描述,关联规则反映了一组数据项之间的密切程度或关系。相关定义如下:

定义7.9(强关联规则)给定项集I={I1,I2,…,In},D={T1,T2,…,Td}是全体事务数据集,规则X→Y是关联规则,当且仅当如下两个条件得到满足时X→Y是强关联规则:

(1)规则支持度大于事先设定的阈值,即s(X→Y)≥minsup;

(2)规则置信度大于事先设定的阈值,即c(X→Y)≥minsup。

根据关联规则的定义,关联规则与频繁项集的关系是:频繁项集是关联规则的前提。因此,关联规则的挖掘主要被分解为下面两步:

第一步,频繁项集提取。找出所有的频繁项集,即找出支持度大于或等于给定的最小支持度阈值的所有项集。可以从1~k递归查找k-频繁项集。

第二步,关联规则提取,即找出满足最小支持度和最小置信度的关联规则。对给定的L,如果其非空子集A⊂L,sup(L)为L的支持度,sup(A)为A的支持度,则产生形式为A→L-A的规则。

7.3频繁项集挖掘

给定总项集I={I1,I2,…,In},要挖掘出所有的频繁模式涉及两大关键步骤:(1)创建所有的候选项集。(2)判断一个候选项集是否是频繁项集。最常用的方法有枚举法(暴力破解)、剪枝算法(Apriori算法)、Apriori加速算法、FP算法等。

7.3.1暴力破解方法

暴力破解是最常用的方法,可以利用树状结构枚举所有的候选项集,创建完候选项集树之后,依次判断每个候选项集是否满足频繁项集的要求。给定交易数据项集I={a,b,c,d,e},暴力破解算法枚举所有子集合,如图7-3所示。图7-3暴力破解示例

其特点是:

①共k+1层;

②第一层是空集;

③第k层都是(k-1)-项集;

④每层只与上一层和下一层有关系。

暴力破解算法的优点是:简单、易懂;

暴力破解算法的缺点是:时间复杂度极高,为指数级(M=2d),其结构如图7-3所示。基于暴力破解算法的频繁模式挖掘如图7-4所示。图7-4基于暴力破解算法的频繁模式挖掘

7.3.2Apriori算法

Apriori算法是一种挖掘关联规则的频繁项集算法,它开创性地使用基于支持度的剪枝技术,系统地控制候选项集指数增长。Apriori利用如下两个基本性质:①频繁项集的所

有非空子集都是频繁的。如果项集I不满足最小支持度阈值minsup,则I不是频繁的,即sup(I)<minsup。②如果将项集A添加到I,则结果项集(I∪A)不可能比I更频繁出现。因此,I∪A也不是频繁的,sup(I∪A)<minsup,即存在反单调模式:

基于频繁项集的反单调性,Apriori算法的核心思想总结如下:

频繁项集的Apriori性质用于压缩搜索空间(剪枝),以提高逐层产生频繁项集的效率,如图7-5所示。其中2-项集{AB}是非频繁的,则以{AB}为子集的所有超集都是非频繁的,包括{ABC}、{ABD}、{ABE}、{ABCD}、{ABCE}、{ABDE}、{ABCDE}。为了避免无效计算,可以对以{AB}为根节点的子树进行剪枝操作,如图7-5所示虚线所包围的项集集合(子树)图7-5Apriori算法剪枝示意图(虚线所包围部分为剪枝部分)

以图7-4中的数据为例,Apriori算法的计算过程如图7-6所示。图7-6Apriori算法的计算过程

具体描述如下

(1)初始通过单边扫描数据集,确定每个项集的支持度,并得到所有频繁1-项集的集合F1(步骤1和2)。

(2)之后使用上一次迭代产生的频繁(k-1)-项集,产生新的候选k-项集(步骤5),其中apriori-gen函数将在下节进行细节介绍。

(3)再次扫描数据集获得候选项集的支持度计数(步骤6~10),使用subset函数确定包含在每一个事物t中的Ck中的所有候选k-项集。subset函数的实现在后文中会介绍。

(4)删去支持度计数小于minsup的所有候选项集(步骤12)。

(5)当没有新的频繁项集产生,即Fk=⌀时,算法结束(步骤13)。

Apriori算法是在早期成功处理频繁项集产生的组合爆炸问题的算法之一,它通过使用先验原理对指数搜索空间进行剪枝,成功地处理了组合爆炸问题。尽管显著地提高了挖掘关联关系的性能,但是该算法还是会导致不可低估的I/O开销,因为它需要多次扫描事务数据集。此外,对于稠密数据集,由于事务数据宽度的增加,Apriori算法的性能会显著降低。为了克服这些局限性和提高Apriori算法的效率,人们开发了一些替代方法。下面是这些方法的简略描述。

1)项集格遍历

概念上,可以把频繁项集的搜索看作遍历图7-5中的项集格。算法使用的搜索策略指明了频繁项集产生过程中是如何遍历格结构的。根据频繁项集在格中的布局,某些搜索策略优于其他策略。这些策略包括:

(1)一般到特殊与特殊到一般。Apriori算法使用了“一般到特殊”的搜索策略,合并两个频繁(k-1)-项集得到候选k-项集。只要频繁项集的最大长度不是太长,这种“一般到特

殊”的搜索策略是有效的。

图7-7(a)中显示使用这种策略效果最好的频繁项集的分布,其中黑色的节点代表非频繁项集。相反,“特殊到一般”的搜索策略在发现更一般的频繁项集之前,先寻找更特殊的频繁项集。这种策略对于发现稠密事务中的极大频繁项集是有用的。稠密事务中频繁项集的边界靠近格的底部,如图7-7(b)所示。可以使用先验原理剪掉极大频繁项集的所有子集。具体来说,如果候选k-项集是极大频繁项集,则不必考察它的

任意k-1项子集。然而,如果候选k-项集是非频繁的,则必须在下一迭代考察它所有的k-1项子集。另外一种策略是结合“一般到特殊”和“特殊到一般”的搜索策略,尽管这种双

向搜索方法需要更多的空间存储候选项集,但是对于图7-7(c)所示的布局,该方法有助于加快确定频繁项集边界。图7-7-一般到特殊、特殊到一般和双向搜索

(2)等价类。另外一种遍历的方法是先将格划分为两个不相交的节点组(或等价类),频繁项集产生算法依次在每个等价类内搜索频繁项集。例如,Apriori算法采用的逐层策略可以看作根据项集的大小划分格,即在处理较大项集之前,首先找出所有的频繁1-项集。等价类也可以根据项集的前缀或后缀来定义。在这种情况下,如果它们共享长度为K的相同前缀或后缀,则两个项集属于同一个等价类。在基于前缀的方法中,算法首先搜索以前缀a开始的频繁项集,然后是以前缀b开始的频繁项集,然后是c,如此下去。基于前缀和基于后缀的等价类都可以使用图7-8所示的类似于树的结构来演示。图7-8基于项集前缀和后缀的等价类

(3)宽度优先与深度优先。Apriori算法采用宽度优先的方法遍历格,如图7-9(a)所示。它首先发现所有的频繁1-项集,接下来是频繁2-项集,如此下去直到没有新的频繁项集产生为止。也可以以深度优先的方式遍历项集格,如图7-9(b)和图7-10所示。例如,算法可以从图中的节点a开始,计算其支持度计数并判断它是否频繁。如果是,则算法渐增地扩展下层节点,即ab、abc等,直到到达一个非频繁节点,如abcd。然后回溯到下一个分支,如abce,并且继续搜索。图7-9宽度优先和深度优先遍历

通常,深度优先搜索方法用于发现极大频繁项集的算法。与宽度优先方法相比,这种方法可以更快地检测到频繁项集边界。一旦发现一个极大频繁项集,就可以在它的子集上进行剪枝。例如,如果图7-10中的节点bcde是极大频繁项集,则算法就不必访问以bd、be、c、d和e为根的子树,因为它们不可能包含任何极大频繁项集。然而,如果abc是极大频繁项集,则只有ae和be这样的节点不是极大频繁项集,但以它们为根的子树还可能包含极大频繁项集。深度优先方法还允许使用不同的基于项集支持度的剪枝方法。例如,假定项集{a,b,c}和{a,b}具有相同的支持度,则可以跳过以abd和abe为根的子树,因为可以确保它们不包含任何极大频繁项集。图7-10使用深度优先的方法产生的候选项集

2)事务数据集的表示

事务数据集的表示方法有多种。表示方法的选择可能影响计算候选项集支持度的I/O开销。图7-11显示了两种表示购物篮事务的不同方法。图7-11(a)的表示法称作水平数据布局,许多关联规则挖掘算法(包括Apriori)都采用这种表示法;另一种可能的方法是存储与每一个项集相关联的事务标识符(TransactionIdentifer,TID),这种表示法称作垂直(Vertical)数据布局。图7-11水平与垂直数据形式

假设有15个3-项集:{145},{124},{457},{125},{458},{159},{136},{234},

{567},{345},{356},{357},{689},{367},{368},那么如何构建Hash函数,可以有效地存储15个3-项集?如图7-12所示,可以构建Hash函数取模3操作(具体过程参看数据结构部分,Hash函数与Hash树),构建Hash树的基本思想是:将事务中每个项前缀的项集构建出来,采用递归的方式创建所有的项集。图7-12Hash树的构建

7.3.3加速技术

1.二次加速技术

Apriori算法通过反单调性质对候选项集进行剪枝操作,这在很大程度上降低了时间复杂性,在挖掘频繁项集时每个候选项集都需要对数据库进行扫描操作,能否通过其他方式加速这一过程?人们发现可采用哈希树(Hash树)的方式来降低时间复杂性。

构建Hash树的前提是需要知道所有的k-项集,给定一个事务,通过枚举的方式构建所有的k-项集,如图7-13所示。图7-13Hash树构建

2.其他加速技术

Apriori算法需要重复地扫描数据库,通过模式匹配方法对一个大的候选集合进行筛。为了提高Apriori算法的效率,目前已产生了许多Apriori算法的变形:

(1)散列技术:用于压缩候选k-项集Ck。

(2)基于事务压缩方法:目标是减少用于未来扫描的事务集的大小。

(3)基于划分方法:Savasere设计了一个基于划分(Partition)的算法,这个算法先把数据库从逻辑上分成几个互不相交的块,每次单独考虑一个分块并对它生成所有的频繁项集;然后把产生的频繁项集合并,用来生成所有可能的频繁项集;最后计算这些频繁项集的支持度。

(4)基于采样方法:采样是发现规则的一个有效途径。

(5)动态项集计数:将给定事务集D划分为标记开始点的块,可以在任何开始点添加新的候选项集。

Apriori算法的缺点:

(1)在每一步产生候选项集时,循环产生的组合过多,没有排除不应该参与组合的元素;

(2)每次计算项集的支持度时,对数据库中的全部记录进行了一次扫描比较,因此需要很大的I/O负载;

(3)当数据量过大时,需要采取页面调入与调出算法,极其费时。

7.4频繁模式树算法

7.4.1FP树表示法FP(FrequentPattern)树是一种输入数据的压缩表示,它通过逐个读入事务,并把每个事务映射到FP树中的一条路径来构造。由于不同的事务可能会有若干个相同的项,因此它们的路径可能部分重叠。路径相互重叠得越多,使用FP树结构获得的压缩效果越好。如果FP树足够小,能够存放在内存中,则可以直接从这个内存的结构中提取频繁项集,而不必重复地扫描存放在硬盘上的数据。

图7-14显示了一个数据集,它包含10个事务和5个项。

随后,用如下方法扩充FP树:

(1)扫描一次数据集,确定每个项的支持度计数。

(2)第二次扫描数据集,构建FP树。

(3)读入第二个事务{b,c,d}后,为项b、c和d创建新的节点集,然后连接节点null→a→b,形成一条代表该事务的路径。

(4)第三个事务{a,c,d,e}与第一个事务共享一个共同前缀项a,所以第三个事务的路径null→a→c→d→e与第一个事务的路径null→a→b部分重叠。

5)继续该过程,直到每个事务都映射到FP树的一条路径。图7-14构建FP树

FP树的大小也取决于项的排序方式。如果颠倒前面例子中的序,即项按照支持度由小到大排列,则FP树表示如图7-15所示。图7-15支持度递增顺序方案的FP树表示

7.4.2FP算法的频繁项集的产生

FP增长是一种以自底向上方式探索树,由FP树产生频繁项集的算法。给定图7-14所示的树,FP算法首先查找以e结尾的频繁项集,接下来依次是d、c、b,最后是a。这种用于发现以某一个特定项结尾的频繁项集的自底向上的策略等价于基于后缀的方法。由于每一个事务都映射到FP树中的一条路径,因而通过仅考察包含特定节点(如e)的路径,就可以发现以e结尾的频繁项集。使用与节点e相关联的指针,可以快速访问这些路径,图7-16(a)显示了所提取的路径。稍后详细解释如何处理这些路径,以得到频繁项集。图7-16将项集分解为子问题

发现以e结尾的频繁项集之后,FP算法通过处理与节点d相关联的路径,进一步寻找以d结尾的频繁项集。图7-16(b)显示了对应的路径。继续该过程,直到处理了所有与节点c、b和a相关联的路径为止。图7-16(c)、图7-16(d)、图7-16(e)分别显示了这些项的路径,而它们对应的频繁项集汇总在表7-1中。

为了更具体地说明如何解决这些子问题,考虑发现所有以e结尾的频繁项集的任务。

具体如下:

(1)收集包含e节点的所有路径,这些初始的路径称为前缀路径,如图7-17(a)所示。

(2)由图7-17(a)中所显示的前缀路径,通过把与节点e相关联的支持度计数相加得到e的支持度计数。假定最小支持度为2,因为{e}的支持度是3,所以它是频繁项集。１图7-17-使用FP增长算法发现以e为结尾的频繁项集的例子

(3)由于{e}是频繁的,因此算法必须解决发现以de、ce、be和ae结尾的频繁项集的子