第二章+关联规则挖掘-20140918

10三月20241/91第二章关联规则挖掘软件工程学院郑皎凌10三月20242/91基本概念Task设I

={i1,i2,...,im}是项的集合。设A是一个项集，事务T包含A当且仅当A

T

关联规则是形如A

B的蕴涵式，其中A

I，B

I，并且A

B=

规则A

B在事务集D中成立，具有支持度s，置信度c，s=包含A、B的元组数/元组总数c=包含A、B的元组数/包含A的元组数10三月20243/91TaskAB元组总数10三月20244/91AllElectronics某分店的事务数据TIDListofitem_ID’sT100T200T300T400T500T600T700T800T900I1,I2,I5I2,I4I2,I3I1,I2,I4I1,I3I2,I3I1,I3I1,I2,I3,I5I1,I2,I310三月20245/9110三月20246/91基本概念同时满足最小支持度阈值(min_sup)和最小置信度阈值(min_conf)的规则称作强规则。项的集合称为项集。包含k个项的项集称为k-项集。如果项集满足最小支持度，则称它为频繁项集10三月20247/91关联规则的挖掘过程找出所有频繁项集：根据定义，这些项集出现的频繁性至少和预定义的最小支持计数一样。由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和最小置信度。这两步中，第二步最容易。挖掘关联规则的总体性能由第一步决定。10三月20248/91关联规则如何用于决策？10三月20249/9110三月202410/9110三月202411/9110三月202412/91关联规则R1：烤鸭

面饼、面酱。支持度40%，置信度为66.6%R2：面饼

烤鸭、面酱。支持度40%，置信度为66.6%R3：面酱

面饼、烤鸭。支持度40%，置信度为50%10三月202413/91关联规则KDD结果不一定是因果关系。运用之妙成乎于人。

例如∶用R1，将烤鸭降价以促销面饼、面酱，很可能会破产用R2将面饼降价，以促销烤鸭，可能会发财；用R3，引不起顾客的热情。10三月202414/91挖掘单维布尔关联规则Apriori算法FP-树挖掘频繁闭相集挖掘10三月202415/91

Apriori算法：使用候选项集找频繁项集Apriori使用一种称作逐层搜索的迭代方法，k-项集用于探索(k+1)-项集。首先，找出频繁1-项集的集合。该集合记作L1。L1用于找频繁2-项集的集合L2，而L2用于找L3，如此下去直到不能找到频繁k-项集。找每个Lk需要一次数据库扫描。10三月202416/91Apriori性质频繁项集的所有非空子集都必须也是频繁的。Apriori性质基于如下观察：根据定义，如果项集I不满足最小支持度阈值s，则I不是频繁的，即P(I)<s。如果项A添加到I，则结果项集（即，I

A）不可能比I更频繁出现。因此，I

A也不是频繁的，即P(I

A)<s。该性质属于一种特殊的分类，称作反单调，意指如果一个集合不能通过测试，则它的所有超集也都不能通过相同的测试10三月202417/91连接步：为找Lk，通过Lk-1与自己连接产生候选k-项集的集合。该候选项集的集合记作Ck。设l1和l2是Lk-1中的项集。记号li[j]表示li的第j项执行连接Lk-1

Lk-1

；其中，Lk-1的元素是可连接的，如果它们前(k-2)个项相同；即，Lk-1的元素l1和l2是可连接的，如果(l1

[1]=l2[1])

(l1[2]=l2[2])

...

(l1[k-2]=l2[k-2])

(l1[k-1]<l2[k-1])。连接l1和l2产生的结果项集是l1[1]l1[2]...l1[k-1]l2[k-1]。10三月202418/91通过连接步得到的候选相集会不会漏掉频繁相集？不会l[1]l[2]...l[k-1]l[k]频繁则l[1]l[2]...l[k-1]

频繁则l[1]l[2]...l[k]

频繁必然会连接l[1]l[2]...l[k-1]

和l[1]l[2]...l[k-2]l[k]10三月202419/91剪枝步：Ck是Lk的超集；即，它的成员可以是，也可以不是频繁的，但所有的频繁k-项集都包含在Ck中。扫描数据库，确定Ck中每个候选的计数，从而确定Lk（即，根据定义，计数值不小于最小支持度计数的所有候选是频繁的，从而属于Lk）。然而，Ck可能很大，这样所涉及的计算量就很大。为压缩Ck，可以用以下办法使用Apriori性质：任何非频繁的(k-1)-项集都不是可能是频繁k-项集的子集。因此，如果一个候选k-项集的(k-1)-子集不在Lk-1中，则该候选也不可能是频繁的，从而可以由Ck中删除。10三月202420/91AllElectronics某分店的事务数据TIDListofitem_ID’sT100T200T300T400T500T600T700T800T900I1,I2,I5I2,I4I2,I3I1,I2,I4I1,I3I2,I3I1,I3I1,I2,I3,I5I1,I2,I310三月202421/9110三月202422/91Apriori算法

使用逐层迭代找出频繁项集输入：事务数据库D；最小支持度阈值。输出：D中的频繁项集L。方法：L1=find_frequent_1_itemsets(D);for(k=2;Lk-1

;k++){Ck=aproiri_gen(Lk-1,min_sup);foreachtransactiont

D{//scanDforcountCt=subset(Ck,t);//getsubsetsoftthatarecandidatesforeachcandidatec

Ctc.count++;}Lk={c

Ck|c.count

min_sup}}returnL=

kLk；10三月202423/91procedureapriori_gen(Lk-1:frequent(k-1)-itemset;min_sup:support)foreachitemsetl1

Lk-1foreachitemsetl2

Lk-1if(l1[1]=l2[1])

...

(l1[k-2]=l2[k-2])

(l1[k-1]<l2[k-2])//通过Lk-1与自己连接产生候选k-项集的集合

//Lk-1的元素是可连接的，如果它们前(k-2)个项相同

//条件(l1[k-1]<l2[k-1])是简单地保证不产生重复。//连接l1和l2产生的结果项集是l1[1]l1[2]...l1[k-1]l2[k-1]

then{c=l1l2;//joinstep:generatecandidatesifhas_infrequent_subset(c,Lk-1)thendeletec;//prunestep:removeunfrequentcadidateelseaddctoCk;}returnCk;10三月202424/91procedurehas_infrequent_subset(c:candidatek-itemset;Lk-1:frequent(k-1)-itemset)//useprioriknowledgeforeach(k-1)-subsetsofcifc

Lk-1thenreturnTRUE;returnFALSE;10三月202425/91由频繁项集产生关联规则对于每个频繁项集l，产生l的所有非空子集。对于l的每个非空子集s，如果，则输出规则“s

(l-s)”。其中，min_conf是最小置信度阈值。10三月202426/91例AllElectronics事务数据库。假定数据包含频繁项集l={I1,I2,I5}，可以由l产生下列关联规则？l的非空子集有{I1,I2},{I1,I5},{I2,I5},{I1},{I2}和{I5}。结果关联规则如下，每个都列出置信度。10三月202427/91I1

I2

I5,I1I5

I2,I2I5

I1,I1I2

I5,I2I1

I5,I5I1

I2,confidence=2/4=50%confidence=2/2=100%confidence=2/2=100%confidence=2/6=33%confidence=2/7=29%confidence=2/2=100%如果最小置信度阈值为70%，则只有2、3和最后一个规则可以输出，因为只有这些是强的。

10三月202428/91

提高Apriori的有效性基于散列的技术（散列项集计数）：一种基于散列的技术可以用于压缩候选k-项集Ck

(k>1)。例如，当扫描数据库中每个事务，由C1中的候选1-项集产生频繁1-项集L1时，我们可以对每个事务产生所有的2-项集，将它们散列（即，映射）到散列表结构的不同桶中，并增加对应的桶计数10三月202429/91提高Apriori的有效性事务压缩（压缩进一步迭代扫描的事务数）：不包含任何k-项集的事务不可能包含任何(k+1)-项集。这样，这种事务在其后的考虑时，可以加上标记或删除，因为为产生j-项集(j>k)，扫描数据库时不再需要它们。10三月202430/91提高Apriori的有效性划分（为找候选项集划分数据）：它包含两遍。在第I遍，算法将D中的事务划分成n个非重叠的部分。如果D中事务的最小支持度阈值为min_sup，则每个部分的最小支持度计数为min_sup

该部分中事务数。对每一部分，找出该部分内的频繁项集。这些称作局部频繁项集。局部频繁项集可能不是整个数据库D的频繁项集。D的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。这样，所有的局部频繁项集作为D的候选项集。所有部分的频繁项集的集合形成D的全局候选项集。在第II遍，第二次扫描D，评估每个候选的实际支持度，以确定全局频繁项集。10三月202431/91不产生候选挖掘频繁项集Apriori有两种开销可能并非微不足道：它可能需要产生大量候选项集。如果有104个频繁1-项集，则Apriori算法需要产生多达107个候选2-项集，累计并检查它们的频繁性。此外，为发现长度为100的频繁模式，如{a1,...,a100}，它必须产生多达2100

1030个候选。它可能需要重复地扫描数据库，通过模式匹配检查一个很大的候选集合。对于挖掘长模式尤其如此。10三月202432/91FP-增长(FP-growth)频繁模式增长(FP-增长):它采取如分治策略将提供频繁项集的数据库压缩到一棵频繁模式树（或FP-树），但仍保留项集关联信息；将这种压缩后的数据库分成一组条件数据库（一种特殊类型的投影数据库），每个关联一个频繁项，并分别挖掘每个数据库。10三月202433/91FP-树构造数据库的第一次扫描与Apriori相同，它导出频繁项（1-项集）的集合，并得到它们的支持度计数（频繁性）。设最小支持度计数为2。频繁项的集合按支持度计数的递减序排序。结果集或表记作L。AllElectronics某分店的事务数据的频繁项L=[I2:7,I1:6,I3:6,I4:2,I5:2]。10三月202434/91FP-树构造L=[I2:7,I1:6,I3:6,I4:2,I5:2]。TIDListofitem_ID’sT100T200T300T400T500T600T700T800T900I1,I2,I5I2,I4I2,I3I1,I2,I4I1,I3I2,I3I1,I3I1,I2,I3,I5I1,I2,I310三月202435/91FP-树构造将这种压缩后的数据库分成一组条件数据库（一种特殊类型的投影数据库），每个关联一个频繁项，并分别挖掘每个数据库。10三月202436/91FP-树挖掘由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基（一个“子数据库”，由FP-树中与后缀模式一起出现的前缀路径集组成）。然后，构造它的（条件）FP-树，并递归地在该树上进行挖掘。模式增长通过后缀模式与由条件FP-树产生的频繁模式连接实现。10三月202437/91FP-树挖掘算法算法：FP-增长。使用FP-树，通过模式段增长，挖掘频繁模式。输入：事务数据库D；最小支持度阈值min_sup。输出：频繁模式的完全集。方法：按以下步骤构造FP-树：扫描事务数据库D一次。收集频繁项的集合F和它们的支持度。对F按支持度降序排序，结果为频繁项表L。创建FP-树的根结点，以“null”标记它。对于D中每个事务Trans，执行：选择Trans中的频繁项，并按L中的次序排序。设排序后的频繁项表为[p|P]，其中，p是第一个元素，而P是剩余元素的表。调用insert_tree([p|P],T)。该过程执行情况如下。如果T有子女N使得N.item-name=p.item-name，则N的计数增加1；否则创建一个新结点N，将其计数设置为1，链接到它的父结点T，并且通过结点链结构将其链接到具有相同item-name的结点。如果P非空，递归地调用insert_tree(P,N)。FP-树的挖掘通过调用FP_growth(FP_tree,null)实现。该过程实现如下：10三月202438/91FP-树挖掘算法procedure

FP_growth(Tree,

)if

Tree

含单个路径P

then

for

路径P中结点的每个组合（记作

）产生模式

，其支持度support=

中结点的最小支持度;elseforeach

ai

在Tree的头部{产生一个模式

=ai

，其支持度support=ai.support；构造

的条件模式基，然后构造

的条件FP-树Tree

；ifTree

then调用FP_growth(Tree

,

)；}10三月202439/91FP-growth频繁模式增长挖掘全部频繁项集而不产生候选构造FP-树：扫描DB一次,找出1-itemset频繁项集按频数递减顺序把频繁项排序：f-list扫描DB再一次,构造FP-树10三月202440/91FP-growth步骤一：扫描DB一次,找出频繁1-项集{I2:7,I1:6,I3:6,I4:2,I5:2}步骤二：第2次扫描DB，构造FP-树。null{}I2:I1:I5:I3:I4:I3:I4:I5:I1:I3:TID项ID的列表T100I1,I2,I5T200I2,I4T300I2,I3T400I1,I2,I4T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I37412112221项IDsup节点链I27I16I36I42I5210三月202441/91FP-树挖掘算法I3的条件模式基是{(I2I1:2),(I2:2),(I1:2)}。它的条件FP-树有两个分枝<I2:4,I1:2>和<I1:2>，如图6.9所示，它产生模式集：{I2I3:4,I1I3:2,I2I1I3:2}。最后，I1的条件模式基是{(I2,4)}，它的FP-树只包含一个结点<I2:4>，产生一个频繁模式I2I1:4。挖掘过程总结在图6.10。

10三月202442/91FP-growth由FP-树产生频繁模式由长度为1的频繁模式开始，构造它的条件模式基，然后构造它的条件FP树，并递归地在该树上进行挖掘。null{}I2:I1:I5:I3:I4:I3:I4:I5:I1:I3:741211221项IDsup节点链I27I16I36I42I522I5<(I2,I1:1)>,<(I2,I1,I3:1)><I2:2,I1:2>I2I5:2,I1I5:2,I2I1I5:2I4<(I2,I1:1)>,<(I2:1)><I2:2>I2I4:2I3<(I2,I1:2)>,<(I2:2)>,<(I1:2)><I2:4,I1:2>,<I1:2>I2I3:4,I1I3:4,I2I1I3:2I1<(I2:4)><I2:4>I2I1:4Item条件模式基条件FP树产生的频繁模式10三月202443/91CompactnessofFP-tree10三月202444/91CompactnessofFP-treeAlphabeticalFP-tree.Itincludesthespaceofallthelinks.However,insuchanFP-tree,thealphabeticalorderofitemsareusedinsteadoffrequencydescendingorder.OrderedFP-tree.thesizecoversthatofalllinks.InsuchanFP-tree,theitemsaresortedaccordingtofrequencydescendingorder.Transactiondatabase.Eachiteminatransactionisstoredasaninteger.Itissimplythesumofoccurrencesofitemsintransactions.Frequenttransactiondatabase.Thatisthesub-databaseextractedfromtheoriginalonebyremovingallinfrequentitems.10三月202445/91Scalabilitystudy10三月202446/91FP-树挖掘算法的优点FP-增长方法将发现长频繁模式的问题转换成递归地发现一些短模式，然后与后缀连接。它使用最不频繁的项作后缀，提供了好的选择性。该方法大大降低了搜索开销。当数据库很大时，构造基于内存的FP-树是不现实的。一种有趣的替换是首先将数据库划分成投影数据库的集合（上一张），然后在每个投影数据库上构造FP-树并挖掘它。该过程可以递归地用于投影数据库，如果它的FP-树还不能放进内存。10三月202447/91最大的频繁模式最大的频繁模式是频繁模式p，使得p的任何真超模式都不是频繁的。I2I5:2,I1I5:2,I2I1I5:2，I2I4:2，I2I3:4,I1I3:4,I2I1I3:2，I2I1:410三月202448/91最大的频繁模式最大的频繁模式是频繁模式p，使得p的任何真超模式都不是频繁的。I2I5:2,I1I5:2,I2I1I5:2，I2I4:2，I2I3:4,I1I3:4,I2I1I3:2，I2I1:410三月202449/91频繁闭项集频繁闭项集是一个频繁的、闭的项集；其中，项集c是闭的，如果不存在c的真超集c’，使得每个包含c的事务也包含c’使用最大模式和频繁闭项集可以显著地压缩挖掘所产生的频繁项集数。I2I5:2,I1I5:2,I2I1I5:2，I2I4:2，I2I3:4,

I1I3:4,I2I1I3:2，I2I1:410三月202450/91由关联挖掘到相关分析强关联规则关联分析vs相关分析兴趣度10三月202451/91由关联挖掘到相关分析数据挖掘系统如何筛选出用户感兴趣的关联规则？支持度和置信度阈值强关联规则一定有趣吗？相关分析相关性度量10