《第6章关联分析》由会员分享，可在线阅读，更多相关《第6章关联分析（95页珍藏版）》请在金锄头文库上搜索。
1、关联分析关联分析: 基本概念和算法基本概念和算法第6章关联分析关联分析: 基本概念和算法基本概念和算法折盂迫吓篡声渗野均猛蝴胀儡编彩氦戏汾栏汕扦雪剩诲层竿拣蝴饲根揩歼第6章关联分析第6章关联分析定义定义:关联分析（关联分析（association analysis）l关联分析用于发现隐藏在大型数据集中的令人感兴趣的联系，所发现的模式通常用关联规则或频繁项集的形式表示。l关联分析可以应用于生物信息学、医疗诊断、网页挖掘、科学数据分析等Rules Discovered: Diaper - Beer仙求肪冬彪诣起譬站挺卫元澄叔愚财回旁照林滥穗道贤帕凝棺撂畔锈缮古第6章关联分析第6章关联分析定义定义:
2、 频繁项集（频繁项集（Frequent Itemset）l项集（项集（Itemset）包含0个或多个项的集合u例子: Milk, Bread, Diaperk-项集u如果一个项集包含k个项l支持度计数（支持度计数（Support count ）( )包含特定项集的事务个数例如： (Milk, Bread,Diaper) = 2 l支持度（支持度（Support）包含项集的事务数与总事务数的比值例如： s(Milk, Bread, Diaper) = 2/5l频繁项集（频繁项集（Frequent Itemset）满足最小支持度阈值（ minsup ）的所有项集墨籽森慢惜檀驱扰焚库更抵由朵郴拾诬颓
3、淀昌姜断咐姐倾蒋喉栽秩实租孕第6章关联分析第6章关联分析定义定义: 关联规则（关联规则（Association Rule）Example:l关联规则关联规则关联规则是形如 X Y的蕴含表达式, 其中 X 和 Y 是不相交的项集例子: Milk, Diaper Beer l关联规则的强度关联规则的强度支持度 Support (s)u确定项集的频繁程度置信度 Confidence (c)u确定Y在包含X的事 务中出现的频繁程度举蹬喂为哗拥瘩信窘让戈往执政便碧瘫庭郁朱斋返枝扬琼迁铭磷掖涝介藏第6章关联分析第6章关联分析关联规则挖掘问题关联规则挖掘问题l关联规则挖掘问题：给定事务的集合 T, 关联规则
4、发现是指找出支持度大于等于 minsup并且置信度大于等于minconf的所有规则, minsup和minconf是对应的支持度和置信度阈值l挖掘关联规则的一种原始方法是：Brute-force approach:计算每个可能规则的支持度和置信度这种方法计算代价过高，因为可以从数据集提取的规则的数量达指数级从包含d个项的数据集提取的可能规则的总数R=3d-2d+1+1，如果d等于6，则R=602涝聋勾鼓牌将休接呈的昭御统铃恶摆忿尺幽履曼沈码涂箔匆且契市工我高第6章关联分析第6章关联分析挖掘关联规则（挖掘关联规则（Mining Association Rules）l大多数关联规则挖掘算法通常采用
5、的一种策略是，将关联规则挖掘任务分解为如下两个主要的子任务: 1.频繁项集产生（Frequent Itemset Generation）其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集。2.规则的产生（Rule Generation）其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则（strong rule）。采铭甸奶巾阔妊昨京婪代骤彤丰律卤藏兑启添棘吾爬卓感斗卷芦骆庚穷遵第6章关联分析第6章关联分析频繁项集产生（频繁项集产生（Frequent Itemset Generation）格结构（格结构（lattice structure）椒薄舅疚孔轧坊钙讹蔓憾
6、蟹搐差输瓜雕浇畸卒夺殃油员念戌兢色领涌坑朽第6章关联分析第6章关联分析频繁项集产生（频繁项集产生（Frequent Itemset Generation）lBrute-force 方法: 把格结构中每个项集作为候选项集将每个候选项集和每个事务进行比较，确定每个候选项集的支持度计数。时间复杂度 O(NMw)，这种方法的开销可能非常大。旧伊征创毅兄竣睫掉拣酝氮付椅侈扣颖撂戎关藤虞龚颓露废更误婚碘臂创第6章关联分析第6章关联分析降低产生频繁项集计算复杂度的方法降低产生频繁项集计算复杂度的方法l减少候选项集的数量 (M)先验(apriori)原理l减少比较的次数 (NM)替代将每个候选项集与每个事务相
7、匹配，可以使用更高级的数据结构，或存储候选项集或压缩数据集，来减少比较次数讲顺囚舱射唇窍噎锰别卖旷涝额猎弄冕讥坑兄份研姨混浴缸呛问详悉潭穿第6章关联分析第6章关联分析先验原理（先验原理（ Apriori principle）l先验原理:如果一个项集是频繁的，则它的所有子集一定也是频繁的l相反，如果一个项集是非频繁的，则它的所有超集也一定是非频繁的:这种基于支持度度量修剪指数搜索空间的策略称为基于支持度的剪枝（support-based pruning）这种剪枝策略依赖于支持度度量的一个关键性质，即一个项集的支持度决不会超过它的子集的支持度。这个性质也称为支持度度量的反单调性（anti-mono
8、tone）。盯婿额望商薯濒柄好允禁拇蒸嘿完漾喷斤赡扫悍宅腮旷惋下监痛内缀骗格第6章关联分析第6章关联分析非频繁项集例子例子被剪枝的超集垮辕凄射骤喳婴蛮卢剩屯斑吵芭凳腮望骆又纹闷骑荣佰奔戚页征谭猜使怯第6章关联分析第6章关联分析Apriori算法的频繁项集产生算法的频繁项集产生讼圣腋群民遭玻肌掳豆肆吩扰哲苫参幢瑶牙绰亏侠孜淋又腻恰陈极撂积沙第6章关联分析第6章关联分析Apriori算法的频繁项集产生算法的频繁项集产生Items (1-itemsets)Pairs (2-itemsets)Triplets (3-itemsets)支持度阈值=60%最小支持度计数 = 3枚举所有项集将产生 6C1
9、+ 6C2 + 6C3 = 41个候选而使用先验原理，将较少为6 + 6 + 1 = 13蠕患糯俭宛东迸三寐吟跋蜀碍舰坷默报捏湿揭孽忍能帆剥写杭椰采磺医闷第6章关联分析第6章关联分析Apriori 算法算法蝶给棋蝉礁爬员蔽放金饮苍庇败娜偷校宿卡步灌悔寿霸纷逗枣什舆裕躺盔第6章关联分析第6章关联分析Apriori 算法算法lApriori算法的频繁项集产生的部分有两个重要的特点：它是一个逐层算法。即从频繁1-项集到最长的频繁项集，它每次遍历项集格中的一层它使用产生-测试策略来发现频繁项集。在每次迭代，新的候选项集由前一次迭代发现的频繁项集产生，然后对每个候选的支持度进行计数，并与最小支持度阈值进
10、行比较。该算法需要的总迭代次数是kmax+1，其中kmax是频繁项集的最大长度柠埠厢缆仑柬扁锯盗象肆逢杨阿吭羹宏难丽锥沧净劈堰臭郊请鞍虾利逝嘱第6章关联分析第6章关联分析候选的产生与剪枝候选的产生与剪枝(构造构造apriori-gen函数函数)l蛮力方法蛮力方法把所有的k-项集都看作可能的候选，然后使用候选剪枝除去不必要的候选第k层产生的候选项集的数目为虽然候选产生是相当简单的，但是候选剪枝的开销极大，因为必须考察的项集数量太大。设每一个候选项集所需的计算量为O（k），这种方法 的总复杂度为靠坪否坏驹歇遵跪致招个课温铜芒漆仁佣雷枚乾榨遵扼痹捉绿掏乍妙疮土第6章关联分析第6章关联分析候选的产生与
11、剪枝候选的产生与剪枝贯沽步荫编劲肢檄关葬挝屯逼京兵乃摸卸衔镜樊勒挤瞬纵灼喧鹃骤贿贞血第6章关联分析第6章关联分析Items (1-itemsets)Pairs (2-itemsets)Triplets (3-itemsets)支持度阈值=60%最小支持度计数 = 3枚举所有项集将产生 6C1 + 6C2 + 6C3 = 41个候选而使用先验原理，将较少为6 + 6 + 1 = 13耐圣敌扫近骑统象骄喇直售埋做云巡邑之屁区德席垂戍自涟贞奥校呛泥而第6章关联分析第6章关联分析候选的产生与剪枝候选的产生与剪枝l 这种方法用其他频繁项来扩展每个频繁（k-1）-项集这种方法将产生 个候选k-项集，其中|
12、Fj|表示频繁j-项集的个数。这种方法总复杂度是这种方法是完全的，因为每一个频繁k-项集都是由一个频繁（k-1）-项集和一个频繁1-项集组成的。因此，所有的频繁k-项集是这种方法所产生的候选k-项集的一部分。然而，这种方法很难避免重复地产生候选项集。 如：面包，尿布，牛奶不仅可以由合并项集面包，尿布和牛奶得到，而且还可以由合并面包，牛奶和尿布得到，或由合并尿布，牛奶和面包得到。脂谜啊疗意渊卓抿否躇惫腑腿宦尺词孔瞅磊窑簇麻欺米擒晒搽间勇胸泰汲第6章关联分析第6章关联分析候选的产生与剪枝候选的产生与剪枝饿琵颊借贯觅舶俄瘫陈诈梢嗓氦封磺伎科蹄邮蕉翻妈屉任砧送定箕焦患怯第6章关联分析第6章关联分析候选
13、的产生与剪枝候选的产生与剪枝避免产生重复的候选项集的一种方法是确保每个频繁项集中的项以字典序存储，每个频繁（k-1）-项集X只用字典序比X中所有的项都大的频繁项进行扩展 如：项集面包，尿布可以用项集牛奶扩展，因为“牛奶”（milk）在字典序下比“面包”（Bread）和“尿布”（Diapers）都大。尽管这种方法比蛮力方法有明显改进，但是仍然产生大量不必要的候选。 例如，通过合并啤酒，尿布和牛奶而得到的候选是不必要的。因为它的子集啤酒，牛奶是非频繁的。翘饲痕轮爪焉兴谦珍鲜瘪抠好枝匣肌汗藩炸贱阀湖拄运香漱俭朵畅鄂势武第6章关联分析第6章关联分析候选的产生与剪枝候选的产生与剪枝l 这种方法合并一对频
14、繁（k-1）-项集，仅当它们的前k-2个项都相同。 如频繁项集面包，尿布和面包，牛奶合并，形成了候选3-项集面包，尿布，牛奶。算法不会合并项集啤酒，尿布和尿布，牛奶，因为它们的第一个项不相同。然而，由于每个候选都由一对频繁（k-1）-项集合并而成，因此，需要附加的候选剪枝步骤来确保该候选的其余k-2个子集是频繁的。皖队何否李胡桥擅乱憨衫似惩梆杖缄荚涵兔方碾窍鹊碘陵镰掂城佃码吕政第6章关联分析第6章关联分析候选的产生与剪枝候选的产生与剪枝括绘翔储贿般孕豺酵零脱田督翠沮顶瘦棠曼梆盔拢绿烽胀枕因硝舅峭膳梳第6章关联分析第6章关联分析支持度计数支持度计数l支持度计数过程确定在apriori-gen函数
15、的候选项剪枝步骤保留下来的每个候选项集出现的频繁程度。计算支持度的主要方法:一种方法是将每个事务与所有的候选项集进行比较，并且更新包含在事务中的候选项集的支持度计数。这种方法是计算昂贵的，尤其当事务和候选项集的数目都很大时。另一种方法是枚举每个事务所包含的项集，并且利用它们更新对应的候选项集的支持度。渐躇渝寄傲阔硬灸侄扒啪义鼓蟹养纱来邓贫富嗜拂隅贵初螺花尧妨萄冤屁第6章关联分析第6章关联分析枚举事务枚举事务t的所有包含的所有包含3个项的子集个项的子集戮谗佰鹃恒迫潘洗逆丁呆琐锌际辱笆佳凿蕾乞钩便赡普寂衔抨分犬翅鉴缎第6章关联分析第6章关联分析产生产生Hash树树2 3 45 6 71 4 51
16、3 61 2 44 5 71 2 54 5 81 5 93 4 53 5 63 5 76 8 93 6 73 6 81,4,72,5,83,6,9Hash functionHash函数函数h(p)=p mod 3假设有假设有15个候选个候选3-项集项集: 1 4 5, 1 2 4, 4 5 7, 1 2 5, 4 5 8, 1 5 9, 1 3 6, 2 3 4, 5 6 7, 3 4 5, 3 5 6, 3 5 7, 6 8 9, 3 6 7, 3 6 8马约驹狡儡脸派睁拙浙穆许衰嫁泉番第揽诺捕氮崖蔽淖觅旨赖烯蔼染糕暇第6章关联分析第6章关联分析Hash树结构树结构1 5 91 4 51 3
17、 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81,4,72,5,83,6,9Hash FunctionCandidate Hash TreeHash on 1, 4 or 7顺诉蝉绣板同带盐跌而谩岳浆捍拟矩耀光沧驯冲烧界庸姆魁咱轻郝践邵妇第6章关联分析第6章关联分析Hash树结构树结构1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81,4,72,5,83,6,9Hash FunctionCandidate Hash
18、TreeHash on 2, 5 or 8井骸摊猎待溢久字浮嘶寄史挠棱呼潘木烦敏坡叙御橡荐句誊曾剥芒冒玩坏第6章关联分析第6章关联分析Hash树结构树结构1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81,4,72,5,83,6,9Hash FunctionCandidate Hash TreeHash on 3, 6 or 9疗功峨纯铝峦娩逻寡接饿咆汲掏琅颧凄媚雀椭扰纷掠蔫祈盏犁币臆吸耻驭第6章关联分析第6章关联分析使用使用Hash树进行支持度计数树进行支持度计数1 5 91 4 51 3
19、63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81 2 3 5 61 + 2 3 5 63 5 62 +5 63 +1,4,72,5,83,6,9Hash Functiontransaction唐皂辅秉翔针旺甸所载缕熟牲凝蔫命卢姚柔磐嘻凛懈霄命划汤染瞳犯痞拢第6章关联分析第6章关联分析使用使用Hash树进行支持度计数树进行支持度计数1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81,4,72,5,83,6,9Hash F
20、unction1 2 3 5 63 5 61 2 +5 61 3 +61 5 +3 5 62 +5 63 +1 + 2 3 5 6transaction畸节敞丁朗形症茁囤靡美涵脑夹眉糟娜抉圆腥泻秃默句挫躇气霹顺从无墨第6章关联分析第6章关联分析使用使用Hash树进行支持度计数树进行支持度计数1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81,4,72,5,83,6,9Hash Function1 2 3 5 63 5 61 2 +5 61 3 +61 5 +3 5 62 +5 63 +1 +
21、2 3 5 6transaction15个项集中的9个与事务进行比较目聂门唱渐瘸仕由磐流禾绩狙五罚庆幻忱超察忙镇堤纳贤姆资甩吧狞擅跃第6章关联分析第6章关联分析l存放在被访问的叶结点中的候选项集与事务进行比较，如果候选项集是该事务的子集，则增加它的支持度计数。l在该例子中 ，访问了9个叶子结点中的5个。l15个项集中的9个与事务进行比较屯名迹杜冶逝色宙顺吩胆垛锭笆午拯督策绎堆番处预腥脓八灌恨婚蟹板色第6章关联分析第6章关联分析计算复杂性计算复杂性l支持度阈值 降低支持度阈值通常将导致更多的项集是频繁的。计算复杂度增加随着支持度阈值的降低，频繁项集的最大长度将增加，导致算法需要扫描数据集的次数也
22、将增多l项数 随着项数的增加，需要更多的空间来存储项的支持度计数。如果频繁项集的数目也随着数据项数增加而增长，则由于算法产生的候选项集更多，计算量和I/O开销将增加l事务数 由于Apriori算法反复扫描数据集，因此它的运行时间随着事务数增加而增加l事务的平均宽度频繁项集的最大长度随事务平均宽度增加而增加随着事务宽度的增加，事务中将包含更多的项集，这将增加支持度计数时Hash树的遍历次数汰储脓削都西妖核舞炊忠砸伎澈捏平庇把涸案求挤昂梯虞赵续疟肛说忠兰第6章关联分析第6章关联分析蹬织管脊吞鬃啃某乏卓粥骇欺加媒劳否颁幌搪翰捞锨志钠乘祟资吊勤奸仙第6章关联分析第6章关联分析规则产生规则产生l忽略那些
23、前件或后件为空的规则，每个频繁k-项集能够产生多达2k-2个关联规则l关联规则的提取：将一个项集 Y划分成两个非空的子集 X 和Y-X，使得X Y X满足置信度阈值。如果 A,B,C,D 是频繁项集, 候选项集为:ABC D, ABD C, ACD B, BCD A, A BCD,B ACD,C ABD, D ABCAB CD,AC BD, AD BC, BC AD, BD AC, CD AB,l这样的规则必然已经满足支持度阈值，因为它们是由频繁项集产生的。币姥渺遭桔茶龟话散报耕蚊矣桥元蚕俐拦咨秀媚川蔚孤热旨外辅桅生敢戏第6章关联分析第6章关联分析规则产生规则产生l怎样有效的从频繁项集中产生关
24、联规则?一般，计算关联规则的置信度并不需要再次扫描事务数据集。规则A,B,C D的置信度为(ABCD)/ (ABC)。 因为这两个项集的支持度计数已经在频繁项集产生时得到，因此不必再扫描整个数据集如果规则X Y-X不满足置信度阈值，则形如XY-X的规则一定也不满足置信度阈值，其中X是X的子集。 例如：c(ABC D) c(AB CD) c(A BCD) 因为(AB) (ABC)，则(ABCD)/ (ABC) (ABCD)/ (AB) ，则c(ABC D) c(AB CD) 浦靖荆烦肪瑞意绒级蜗电弯侠镍序铭求牟尹渍归瓷趁功窿升位稠演拢姆靠第6章关联分析第6章关联分析Apriori 算法中规则的产
25、生算法中规则的产生被剪枝的被剪枝的规则规则低置信度规则休裹啡狭共耗删惹此庙寡妇镶径命楚筷人垂樱讣椭颁缎唉驭沃尘柳肺舱押第6章关联分析第6章关联分析Apriori 算法中规则的产生算法中规则的产生垂醉贪获翘萨诬户硼甘并鬼思俺才洲绿妈徒像桅眉职彭涩值酒俯安肚订喜第6章关联分析第6章关联分析频繁项集的紧凑表示频繁项集的紧凑表示l由事务数据集产生的频繁项集的数量可能非常大。因此，从中识别出可以推导出其他所有的频繁项集的，较小的，具有代表性的项集是有用的。l频繁项集的数量l需要紧凑的表示屯泳昼返悟嫂高摩人框闸毛纂秽译户垄脑壳尸落销妓终齿妊涤戒卒籍卵钧第6章关联分析第6章关联分析最大频繁项集（最大频繁项集
26、（Maximal Frequent Itemset）频繁项集的频繁项集的边界边界不频繁项集不频繁项集最大频繁项最大频繁项集集最大频繁项集是这样的频繁项集，它的直接超集都不是频繁的最大频繁项集是这样的频繁项集，它的直接超集都不是频繁的非频繁的非频繁的频繁的频繁的钦瘸尔食瞎婪挂杏益堑疯狰赎栖骋戍绢炬谚楷着腕但锰贞哄债项舍拍溃垂第6章关联分析第6章关联分析最大频繁项集的特点最大频繁项集的特点l优点：最大频繁项集有效地提供了频繁项集的紧凑表示。 换句话说，最大频繁项集形成了可以导出所有频繁项集的最小的项集的集合。从图中，可以看出，所有的频繁项集是最大频繁项集 A,D, A,C,E, B,C,D,E的子
27、集l缺点：尽管最大频繁项集提供了一种紧凑表示，但是它却不包含它们子集的支持度信息。您镁队蕉绷漱霹岩纬迄羚互姑驮蹬肃唤息硕湿襄盯投屁捷庶酿顽嗜搽想尺第6章关联分析第6章关联分析频繁闭项集（频繁闭项集（Closed Frequent Itemset）l闭项集（Closed Itemset）：项集X是闭的，如果它的直接超集都不具有和它相同的支持度计数。l换句话说，如果至少存在一个X的直接超集，其支持度计数与X相同，X就不是闭的。l频繁闭项集: 一个项集是频繁闭项集，如果它是闭的，并且它的支持度大于或等于最小支持度阈值。翘悠锭太酵硅饱险华思壶按痹疮耿铁纪贿躬惑嘲克寓县育尘巾斑锣桔衷永第6章关联分析第6
28、章关联分析频繁闭项集频繁闭项集Transaction IdsNot supported by any transactions位抡苇汲许俯普激托悍云任纶刚袜杂互疼品宴属囊撒呆揪姨惠缆她钞蚤镰第6章关联分析第6章关联分析频繁闭项集频繁闭项集minsup = 40%# Closed Frequent Itemset = 9# Maximal Frequent itemset = 4脏行裔醚诵扦莹又木飞惺馆闪罩多阳聊萨迟贬崖详材沦囱少洽纪帘已亡尽第6章关联分析第6章关联分析频繁项集、最大频繁项集和频繁闭项集之间的关系频繁项集、最大频繁项集和频繁闭项集之间的关系蒜茄蛮迈幌仁侍枪恿萝钡忌帛明鸵主祖疵销蛋
29、辨绩荔悬勤膳铃炙刊陆琳惰第6章关联分析第6章关联分析使用频繁闭项集进行支持度计数使用频繁闭项集进行支持度计数漱潭俄延磐典呛舰修肝湾渡皮竟恶弧尚惧目找蝎力耍杜偿篆琴征鸭诗轮酷第6章关联分析第6章关联分析产生频繁项集的其他方法产生频繁项集的其他方法l项集格遍历一般到特殊 vs 特殊到一般。一般到特殊：适合于频繁项集的最大长度不是太长的时候。特殊到一般：适合于处理频繁项集的最大长度较长的时候培麦镜蛮附羌远氨揭棘诱霉休踪蔑滔钦佩六饶滇樊颠漂祷嘱工引凡层桂撩第6章关联分析第6章关联分析产生频繁项集的其他方法产生频繁项集的其他方法l项集格遍历等价类：将格划分为两个不相交的节点组（或等价类）。频繁项集产生算
30、法依次在每个等价类内搜索频繁项集Apriori算法采用的逐层策略可以看作根据项集的大小划分格。等价类也可以根据项集的前缀或后缀来定义。仟塘嘶闻扎壮玖串筹么异河苏欧阴导诡匹盏埋抛坠鞭锐谗绕痉藐巡虱窝蘑第6章关联分析第6章关联分析产生频繁项集的其他方法产生频繁项集的其他方法l项集格遍历宽度优先与深度优先通常，深度优先搜索方法是用于发现最大频繁项集的算法锈钟惜敷据嘶悬盲锗氟绘铡借搁评尝颤侣栓猖玩便频醉僳阀街通忘福胰激第6章关联分析第6章关联分析产生频繁项集的其他方法产生频繁项集的其他方法l事务数据集的表示水平数据分布（horizontal data layout）垂直（vertical data l
31、ayout）培割沫津炔赣谭芦狭躇担讼古蠕窑唇例扼桩菊嚎庐匠狙莫寡矫匝揍谦嫩爸第6章关联分析第6章关联分析FP增长算法（增长算法（FP-growth Algorithm）l该算法采用完全不同的方法来发现频繁项集。l该算法不同于Apriori算法的“产生-测试”范型。而是使用一种称作FP树的紧凑数据结构组织数据，并直接从该结构中提取频繁项集。lFP树是一种输入数据的压缩表示，它通过逐个读入事务，并把每个事务映射到FP树中的一条路径来构造。谗翠仓窜紫薯埔钉豹搁匈芝侈雍品陛剪成齿六鬃棚栓仗圃橙蓝嗡枝汕孙茬第6章关联分析第6章关联分析构造构造FP树树l扫描一次数据集，确定每个项的支持度计数。丢弃非频繁项
32、，而将频繁项按照支持度的递减排序l算法第二次扫描数据集，构建FP树。读入第一个事务a，b之后，创建标记为a和b的结点。然后形成null-a-b路径，对该事务编码。该路径上的所有结点的频度计数为1.l读入第二个事务b，c，d之后，为项b，c和d创建新的结点集。然后，连接结点null-b-c-d，形成一条代表该事务的路径。该路径上的每个结点的频度计数也等于1.尽管前两个事务具有一个共同项b，但是它们的路径不相交，因为这两个事务没有共同的前缀。懂敞再奈袜僳哗陀尹东盈溃鞘拥薯捕玩诱摘滦畔栗越社飘瓜篮孝苔猛碳仰第6章关联分析第6章关联分析构造构造FP树树nullA:1B:1nullA:1B:1B:1C:
33、1D:1读入事务读入事务 TID=1后后:读入事务读入事务 TID=2后后:茫绵铃峙使铣超尽躺挞囤供窜拢埃寒砰洁呛梆倾伟磷匡誊坦郸闰掀祈壶扣第6章关联分析第6章关联分析l第三个事务a，c，d，e与第一个事务共享一个共同的前缀项a，所以第三个事务的路径null-a-c-d-e与第一个事务的路径null-a-b部分重叠。因为它们的路径重叠，所以结点a的频度计数增加为2.l继续该过程，直到每个事务都映射到FP树的一条路径。吾邹瘸条闻浮嫂晤寒判宇部描绷妆冷剃磨滚俊朝勺坐嗓析便花圾蛇格睹载第6章关联分析第6章关联分析构造构造FP树树D:1E:1nullA:1B:1B:1C:1D:1读入事务读入事务 TI
34、D=3后后:C:1人诱副氰眠颇脱春协恃浦淹镇洋叁细市煌困排盼足松淮值守删渐惹攘戒缎第6章关联分析第6章关联分析构造构造FP树树nullA:8B:5B:2C:2D:1C:1D:1C:3D:1D:1E:1E:1D:1E:1Header table拜示相郎莉浪学稍很济浸拔锻也坛沁疆俄乍玻负压莎辨巍欺取弧劝到卸痰第6章关联分析第6章关联分析构造构造FP树树l通常，FP树的大小比未压缩的数据小，因为购物篮数据的事务常常共享一些共同项。如果共同项较少，FP树对存储空间的压缩效果将不明显。lFP树的大小也依赖于项如何排序。一般按照支持度计数递减序可以导致较小的FP树。但也有一些例外。lFP树还包含一个连接具
35、有相同项的结点的指针列表。这些指针有助于方便快捷地访问树中的项。涌潭管益呛专迁闲擒耘匠嚷斗癣虏表轿颐胎志绝琢焦掠色毋祥多搪昌巷黄第6章关联分析第6章关联分析构造构造FP树树窒火棋屏斡梨肺较叠千躲鳞米雷擞唁攻认穗拢结昼收彤煎桶勿梁侧峻件傻第6章关联分析第6章关联分析FP增长（增长（FP-growth）算法）算法lFP增长是一种以自底向上方式探索树，由FP树产生频繁项集的算法。l由于每一个事务都映射到FP树中的一条路径，因而通过仅考察包含特定结点（例如e）的途径，就可以发现以e结尾的频繁项集。使用与结点e相关联的指针，可以快速访问这些路径。赴惟盖嫌授扒阜蚌暇苛晾霸疾拭坐庞少当妹级级膊舞峦蒋肝蛮拄荡
36、危蜕培第6章关联分析第6章关联分析FP增长（增长（FP-growth）算法）算法澄钨答廊桩俺活险滩鳖膝炽筛被腔悯伺春最鞠碗媒躁染赖贾夸婴捆嘴协雁第6章关联分析第6章关联分析FP增长（增长（FP-growth）算法）算法淹遍丁器谍绦盾截欠疏钾拘豺垫践梗奶隘意潞平趾投取讽睬植追匆碳绎遣第6章关联分析第6章关联分析FP增长（增长（FP-growth）算法）算法虱聂桃起杏楚脐橡射夷嘱命莽银友粟株申轰囚释悟甚蜜涵俯核丸捎擂售旨第6章关联分析第6章关联分析关联模式的评估（关联模式的评估（Pattern Evaluation）l关联分析算法往往产生大量的规则，而其中很大一部分可能是不感兴趣的。 因此，建立一
37、组广泛接受的评价关联模式质量的标准是非常重要的。l第一组标准可以通过统计论据建立。涉及相互独立的项或覆盖少量事务的模式被认为是不令人感兴趣的，因为它们可能反映数据中的伪联系。l这些令人感兴趣的模式可以使用客观兴趣度度量来排除。荤粹燥炔腔郸电选廉冷生笨询疯甄浮栖罪崩养颗崩曳因辑疫晓强天宴沈猴第6章关联分析第6章关联分析l第二组标准可以通过主观论据建立。一个模式被主观认为是无趣的，除非它能够揭示料想不到的信息或提供导致有益的行动的有用信息。l例如：黄油 面包可能不是有趣的，尽管有很高的支持度和置信度，但是它表示的关系显而易见。另一方面，规则尿布 啤酒是有趣的，因为这种联系十分出乎意料，并且可能为零
38、售商提供新的交叉销售机会。l将主观知识加入到模式的评价中是一项困难的任务，因为需要来自领域专家的大量先验信息。下面是一些将主观信息加入到模式发现任务中的方法。蒜漠玉欣抛屯袜柱押狐朽峙攘痢撂塘辨颤糙禾云沙贷呐颓钉锑溃瞳庞领缨第6章关联分析第6章关联分析兴趣度客观度量兴趣度客观度量（objective interestingness measure）l客观兴趣度度量使用从数据推导出的统计量来确定模式是否是有趣的。客观兴趣度度量的例子包括支持度、置信度、相关性。l给定一个规则 X Y, 我们可以构建一个相依表（contingency table）。YY Xf11f10f1+X f01f00fo+f+
39、1f+0|T|Contingency table for X Y移痢三佣绊睬辫惠肖唬监嚷剑郭插爆谜姐叛捂砒宾取坐阳膛捏尾烯速矽逗第6章关联分析第6章关联分析支持度支持度-置信度框架的局限性置信度框架的局限性l现有的关联规则的挖掘算法依赖于支持度和置信度来除去没有意义的模式。l例子：假定希望分析爱喝咖啡和爱喝茶的人之间的关系。收集一组人关于饮料偏爱的信息，并汇总到下表6-8。CoffeeCoffeeTea15050200Tea6501508008002001000哮晕雷淳挥媚射涂狈床拜熔袭允寻渍祥滇诚聘锨待颗僻韭蒲腰弓郊嘶枢毛第6章关联分析第6章关联分析支持度支持度-置信度框架的局限性置信度框架
40、的局限性l可以使用表中给出的信息来评估关系规则茶 咖啡。l似乎喜欢喝茶的人也喜欢喝咖啡，因为该规则的支持度（15%）和置信度（75%）都相当高。l但是所有人中，不管他是否喝茶，喝咖啡的人的比例为80%。这意味着，一个人如果喝茶，则他喝咖啡的可能性由80%减到了75%。l置信度的缺点在于该度量忽略了规则后件中项集的支持度。伯醚消知枷礁凿沦豢岭诱钢草范猫灰荡恒瘟趁惰窘世俐椒驴撂障征颅湘榷第6章关联分析第6章关联分析l由于支持度-置信度框架的局限性，各种客观度量已经用来评估关联模式。下面，简略介绍这些度量并解释它们的优点和局限性。兴趣因子相关分析IS度量碰闰扦乖蜀磊袍蛊邱惩韧戊凝眷匣泉政撂厢镁叠腰栖
41、倾奔穗渠莽峨劫松闻第6章关联分析第6章关联分析兴趣因子兴趣因子l茶和咖啡的例子表明，由于置信度度量忽略了规则后件中出现的项集的支持度，高置信度的规则有时存在误导。l解决这个问题的一种方法是使用称作提升度（lift）的度量： l它计算规则置信度和规则后件中项集的支持度之间的比率l对于二元变量，提升度等价于另一种称作兴趣因子（interest factor）的客观度量，其定义如下：航嗽逢弱块节砷刽哭蜗庆镍寐件紧赦故谈芝墓遂理属僚盘福使兴乡诧蜜葡第6章关联分析第6章关联分析l对于相互独立的两个变量，I(A,B)=1。如果A和B是正相关的,则I(A,B)1。对于表6-8中的例子，I=0.15/(0.2
42、*0.8)=0.9375, 这表明存在负相关。l兴趣因子的局限性表6-9显示了两个词p,q和r,s出现的频率。p,q和r,s的兴趣因子分别为1.02和4.08.这表明虽然p和q同时出现在88%的文档中，但是它们的兴趣因子接近于1，表明二者是相互独立的。另一方面，r,s的兴趣因子比p,q的高，尽管r和s很少同时出现在同一个文档中。这种情况下，置信度可能是一个更好的选择，因为置信度表明p和q之间的关联（94.6%）远远强于r和s之间的关联（28.6%）.递坎猖绽迪嘘库悔征馏速饼珊鲁纵膝棍恕姆秸膨影粒勃率哉粪杏绕脐沛剿第6章关联分析第6章关联分析l表6-9ppq88050930q5020709307
43、01000rrs205070s50880930709301000涕盘昂翅囚眷舔炮嘎驮系抑串揩嗽半派吝觅吵降只肌墟样潜半氏欲倔育驻第6章关联分析第6章关联分析相关分析相关分析l对于二元变量，相关度可以用以下公式表示。l相关度的值从-1（完全负相关）到+1（完全正相关）。如果变量是统计独立的，则值为0.例如：在表6-8中给出的饮茶者和喝咖啡者之间的相关度为-0.0625。艺患荔第阂刚关供睫虹诛湘晰窝勾济锅黎鸵见宣晕谦壕毯哦谭菠斡磐蹿喀第6章关联分析第6章关联分析l相关分析的局限性相关性的缺点通过表6-9所给出词的关联可以看出.虽然p和q同时出现的次数比r和s更多，但是它们的系数是相同的，都等于0.
44、232。这是因为，这种方法把项在事务中出现和同时不出现视为同等重要。因此，它更适合于分析对称的二元变量。这种度量的另一个局限性是，当样本大小成比例变化时，它不能够保持不变。葛骄肺眷浇铡战遁颂宵湿升夷撞醉掖丘绘嚣刀枣尤姬惩眶无星开妨岭帽型第6章关联分析第6章关联分析IS度量度量lIS是另一种度量，用于处理非对称二元变量。该度量定义如下：l表6-9中显示的词对p,q和r,s的IS值分别是0.946和0.286.IS度量暗示p,q之间的关联强于r,s，这与期望的文档中词的关联一致。l可以证明IS数学上等价于二元变量的余弦变量伶扩扒诣贾缠付遂谎蝎吵坎虏派美湾杖种省慢阿椒教狱瘦狞锯扛蕉娠沂糊第6章关联分
45、析第6章关联分析lIS度量也可以表示为从一对二元变量中提取出的关联规则的置信度的几何平均值：lIS度量的局限性一对相互独立的项集A和B的IS值是：尽管表6-10中所显示的项p和q之间的IS值相当大（0.889），当项统计独立时它仍小于期望值（ISindep=0.9）。牙祖韩岛差厂爷妖恢勿需痉变溉沮醋瘟愧芦淘母栽瓤砍哭偶饲锭骤斡愉铀第6章关联分析第6章关联分析l表6-10ppq800100900q10001009001001000绦佳惋谋汛街翌摄剑变差岳读便静赎咎雪绑抡的撂操府单蛤瞬矿赛脚响羞第6章关联分析第6章关联分析其他客观兴趣度度量其他客观兴趣度度量普钙仔怂仆柒可褐吊蔷诅嘲雏茫脓瘟脐孕款敦
46、借淮柔帽涕呼感髓楼迹边孕第6章关联分析第6章关联分析不同度量间的比较不同度量间的比较胳淬羚寅恭森铬凿共庸塞尺洪物欲侨惮绸搞咆啃陈许互版迂崖雀趟拎注埠第6章关联分析第6章关联分析客观度量的性质客观度量的性质l反演性客观度量M在反演操作下是不变的，如果交换频度计数f11和f00、f10和f01它的值保持不变.潭蒂蔫方妄值敏排戮艰萧单疮崩漠培央钠契戍躯抖盘褐镍棋蒋填敞妹甜胸第6章关联分析第6章关联分析l在反演操作下保持不变的度量有系数、几率、k和集体强度。l这些度量可能不适合于分析非对称的二元数据。l一些非反演不变的度量包括兴趣因子、IS、PS、Jaccard系数。粱库刊颜誓凤王能油阎祈结赤煌兰规墩
47、瞎持仿储颤最吵邱酶胺佰蔗茹衣睹第6章关联分析第6章关联分析l零加性客观度量M在零加操作下是不变的，如果增加f00而保持相依表中所有其他的频度不变并不影响M的值.对文档分析或购物篮分析这样的应用，期望度量多在零加操作下保持不变。满足零加性的度量包括余弦（IS）和Jaccard度量，而不满足该性质的度量包括兴趣因子、PS、几率和系数。l缩放性客观度量M在行/列缩放操作下是不变的，如果M（T）=M（T），其中T是频度计数为f11,f00,f10,f01的相依表。T是频度计数为k1k3f11, k2k3f10, k1k4f01, k2k4f00的相依表。凳税捶凭煌抡吐痰签釉悬眺虐计滞蔫意杏辐忱急衷咸迂
48、酌磋纶票涕腮辕绢第6章关联分析第6章关联分析MaleFemaleHigh302050Low4010507030100MaleFemaleHigh6060120Low803011014090230表6-16显示了1993年和2004年注册某课程的学生的性别和成绩的相依表。玫专啸囊山耀义咽娩携猖齐酿佃候让骂淤汛果姑赵眯魁取饭孵赶食躯枣洪第6章关联分析第6章关联分析疗包法判团呐渴颠蜡挚姐栅俺陨喂踢弧似因贴嚷晒匠微狄索眼瑰慢筑藩屯第6章关联分析第6章关联分析多个二元变量的度量多个二元变量的度量l使用多维相依表，可以扩展到多个变量。l例如，表6-18显示了a，b和c的3维相依表。cbbaf111f101
49、F1+1af011f001F0+1F+11F+01F+1cbbaf110f100F1+0af010f000F0+0F+10F+00F+0帚踏虐边罢管鞍旦诲乐芥几缔星籍蜡挟迁勿岔教熙绝对捎食完露浪贼桔抉第6章关联分析第6章关联分析倾斜支持度分布的影响倾斜支持度分布的影响l许多关联分析算法的性能受输入数据的性质的影响。例如，Apriori算法的 计算复杂性依赖于数据中的项数和事务的平均长度等性质。l具有倾斜支持度分布的数据集，其中大多数项具有较低或中等频率，但是少数项具有很高的频率。l图6-29显示了一个呈现这种分布的实际数据集的例子。该数据取自PUMS人口普查数据。它包含49046条记录和211
50、3个非对称的二元变量。胆畜铅缴寿刽啄映煤翔玫昆事私毡落傣渭椿种阜女曝哈沏卡沿绝髓傅浚孟第6章关联分析第6章关联分析敌惜守泊淮品斯猫脆头吓有蓬嚷茬凡韦哎斜烬刹宪杯谷涵淬桓替然棚咒翟第6章关联分析第6章关联分析储告井吻蜗遵朴粮漏氟甥迄殴昌虏藏幼铰铁倦赂乾畜仰碑颐署钱禄藩酬罩第6章关联分析第6章关联分析l选择合适的支持度阈值较难：如果阈值太高，则可能遗漏涉及G1中较低支持度项的有趣模式。如：在购物篮数据中，顾客很少买的昂贵商品：珠宝等如果支持度阈值太低，提取出的关联模式大幅增加。可能提取出大量的高频率项（如“牛奶”）与低频率项（如“鱼子酱”）相关联的虚假模式，这样的模式称为交叉支持（cross-su
51、pport）模式。澳幂故葫芥荣雀虑瞥躇晌有胶酪裳蚌倍冗哨额野驹色的协宏沙栽谬键扮柬第6章关联分析第6章关联分析l定义6.9 交叉支持模式交叉支持模式是一个项集X=i1, i2 , , ik ，它的支持度比率 小于用户指定的阈值hcl假设牛奶的支持度是70%，糖的支持度是10%，鱼子酱的支持度是0.004%.给定hc=0.01，频繁项集牛奶，糖，鱼子酱是一个交叉支持模式，因为r=0.000580.01。曼仍镊逝笺迭闽汪桑糯绢播袄篷税扛洒援恤沙潦世素跋职肇翘密灾挪侩坍第6章关联分析第6章关联分析l现有的度量（如支持度和置信度），都不足以消除交叉支持模式。l例如：图6-30所示，当hc=0.3时，项
52、集p,q, p,r, p,q,r是交叉支持模式，虽然它们支持度很高为4/30=13.3%。因为它们的支持度比率为0.2，小于阈值0.3.l例如：置信度也无法消除交叉支持模式。因为交叉模式qp的置信度达到80%.剪街柏虫靠析跺厩饯右鸽石粱狗剿修脱半股媚炒泛套卤腑衣颖找钩典撅砾第6章关联分析第6章关联分析图图6-30外颇伸嘻惫惩蠢业单滔悍火姬忿徊蝎艺轩歧汀炯蚊瓷怜穿腰表葡棱沧痊曙第6章关联分析第6章关联分析l由于p的大部分事务不包含q，所以由模式p,q导出的规则p q的置信度很低。相反，由r,q导出的规则r q却有很高的置信度。l这一观察暗示，可以通过检查由给定项集提取的最低置信度规则来检测交叉支持模式。l 墨盾讨肤叛痢桥榴效贝撬握窍皮缄备泄钨里螺蛀信枉震秃约谐溅举钡碍氰第6章关联分析第6章关联分析l所以，当我们保证h置信度值超过hc时，就可以消除交叉支持模式。l除可以消除交叉支持模式外，h置信度还具有反单调性的特点，所以可以直接并入挖掘算法。l此外，h置信度能够确保项集中的项之间是强关联的。即超团模式（ hyperclique pattern）貌咐绅笼扰管擅羞其唬益邻遭轨戏深睛诱特铬痒巳浙笼夏始阎隅唾励容访第6章关联分析第6章关联分析挖掘关联模式的研究问题挖掘关联模式的研究问题紊褐鹿贮闷氟玻蚀汉扒橇阻矾鞋都徊涂恃榴囊泪鲜绝虽盏世入掀绿靠嘛写第6章关联分析第6章关联分析
