《第7章关联分析2》由会员分享，可在线阅读，更多相关《第7章关联分析2（101页珍藏版）》请在金锄头文库上搜索。
1、关联分析关联分析: 高级概念高级概念第第7章章关联分析关联分析: 高级概念高级概念躲鞋绅蓬列惹绷略秒篓魄歇践虱倾庙颗侩孕翔逮尹续唤叉撂裂歧鱼秀菲瑰第7章关联分析2第7章关联分析2关联分析处理事务数据关联分析处理事务数据Rules Discovered: Diaper - Beer项逊捍购挞蜒诉尸筒帖糜边昨椒测涡媳溪抵仲踞涩盆闽畏帘供椎媳沽隐涪第7章关联分析2第7章关联分析2处理分类属性处理分类属性我们可能发现关于因特网用户特征的有趣信息我们可能发现关于因特网用户特征的有趣信息: 网上购物=是 关注隐私=是许多应用包含对称二元属性和标称属性。表许多应用包含对称二元属性和标称属性。表7-1显示的因
2、特网调查数显示的因特网调查数据包含对称二元属性，如：性别、家庭计算机、网上聊天、网上购据包含对称二元属性，如：性别、家庭计算机、网上聊天、网上购物和关注隐私；还包括标称属性，如文化程度和州。物和关注隐私；还包括标称属性，如文化程度和州。腊徐祥家丙痛负昭排抗礁嚏容煌蒜皆恕颤井淖饲扯悦溅阔稗版腊力矾蔑辛第7章关联分析2第7章关联分析2处理分类属性处理分类属性l为了提取这样的模式，我们需要将标称属性和对称二元属性转换成“项”，使得已有的关联规则挖掘算法可以使用。l这种类型的变化可以通过为每个不同的属性-值对创建一个新的项来实现。例如: 标称属性文化程度可以用三个二元项取代u 文化程度=大学u 文化程
3、度=研究生u 文化程度=高中l类似的，对称二元属性性别可以转换成一对二元项：性别=男、性别=女。炔拇耕杜屿趋断逊嫉藏酸您酋啪至筹晴儒熏阉舟蔚迪苞跟押戏束手染琉猎第7章关联分析2第7章关联分析2膘鞭轴牲扳肿硼寄柿柴虎掘休哟栓沏苇铡盂灸乘络毗弗朗别矫立涟呀鲜圾第7章关联分析2第7章关联分析2处理分类属性处理分类属性l将关联分析用于二元化后的数据时，需要考虑如下问题。(1)有些属性值可能不够频繁，不能成为频繁模式的一部分。如：州名。解决办法：将相关的属性值分组，形成少数类别。例如，每个州名都可以用对应的地理区域取代。例如：分别用中西部、太平洋西北部、西南部和东海岸取代。倒星越盲邹晤欺柬琉泄变颗锁棋违
4、寝兑然缝氮症逸熔另眩银桑忧尤厅顽葫第7章关联分析2第7章关联分析2处理分类属性处理分类属性l将关联分析用于二元化后的数据时，需要考虑如下问题。(2)某些属性值的频率可能比其他属性高很多。如：假定85%的被调查人都有家庭计算机，如果为每个频繁出现在数据中的属性值创建一个二元项，我们可能产生许多冗余模式。 家庭计算机=是，网上购物=是 关注隐私=是解决办法：使用处理具有宽支持度的极差数据集的技术。倡胜挨绍题饥益夕描渔愤爱纱篱嘲敬亡葡制徐糠郭腕女赊命乙紊囱离沈旁第7章关联分析2第7章关联分析2处理分类属性处理分类属性l将关联分析用于二元化后的数据时，需要考虑如下问题。(3)计算时间可能增加，特别是当
5、新创建的项变成频繁项时。因为会产生更多的候选项集。解决办法：避免产生包含多个来自同一个属性的项的候选项集。例如：不必产生诸如州=X，州=Y，的候选项集，因为该项集支持度为零。僵胡芳敞蜘进璃犁使瞪势镜惮刻注队肃溶蓉掷魄拌凤驻侈的同银庭笑攒躇第7章关联分析2第7章关联分析2处理连续属性处理连续属性l因特网调查数据可能还包含连续属性，如表7-3所示。l挖掘连续属性可能揭示数据的内在联系，如“年收入超过120k的用户属于45-60年龄组”或“拥有超过3个email帐号并且每周上网超过15小时的用户通常关注个人隐私”:l包含连续属性的关联规则通常称作量化关联规则（quantiative associat
6、ion rule）。l对连续数据进行关联分析的方法:基于离散化的方法非离散化方法基于统计学的方法嚏角要砍抠骚越些幼楚撵擦翅不囊艾返闷顿倡戚颖蓉奥我鲤问摈她疾鲍笋第7章关联分析2第7章关联分析2劲拈齐缺愁黍妓鬃钙寺畅渺儡螺巍酞原珊挽表召抉蛔够升煞瘁焙陪诀禁卡第7章关联分析2第7章关联分析2基于离散化的方法基于离散化的方法l离散化是处理连续属性最常用的方法。这种方法将连续属性的邻近值分组，形成有限个区间。例如：年龄属性可以划分为如下区间： 12,16),16,20),20,24),56,60)l离散化技术：等宽、等频、聚类l表7-4显示了离散化和二元化后的因特网调查数据。侦硅玛锭检夜控苯盗纠雨凶嗅
7、釉硝励绩涯欠蔷魔谗黑飘靶罩虹帛综臻淤磺第7章关联分析2第7章关联分析2岿占芜挑桅秧挑汲寸呕竹手班岿豁栗线啪使坷膝械苑联界僧猖劣荒憨婚曲第7章关联分析2第7章关联分析2l属性离散化的一个关键在于划分每个属性的区间个数和宽度。然而，确定正确的区间是困难的。渗饱尽膨敬明采申购怯逗殃浮奔缀保琉渠钙涂戈像囊灭拖尧鼎厦撤新椎舀第7章关联分析2第7章关联分析2l如果支持度阈值=5%，置信度阈值=65%。我们可以从表中推出年龄和网上聊天隐含强规则： 16,24) 网上聊天=是（s=8.8%，c=81.5%） 44,60) 网上聊天=否（s=16.8%，c=70%）l区间宽度对关联分析结果的影响。（1）如果区间
8、太宽，则可能因为缺乏置信度而失去某些规则例如：当区间宽度为24岁时，上面的两个规则变为 16,36) 网上聊天=是（s=30%，57.7%） 36,60) 网上聊天=否（s=28%，58.3%）端麓肄起藕寄命衡谋葡沥遗贝狱婆浸遭苔焙专闸悯腿蝇脂鸯誓尸签遁呜涵第7章关联分析2第7章关联分析2l区间宽度对关联分析结果的影响。（2）如果区间太窄，则可能因为缺乏支持度而失去某些规则例如：当区间宽度为4岁时，上面的两个规则变为 16,20) 网上聊天=是（s=4.4%，84.6%） 20,24) 网上聊天=是（s=4.4%，78.6%）（3）当区间宽度为8岁时，上面的两个规则变为 44,52) 网上聊天
9、=否（s=8.4%，70%） 52,60) 网上聊天=否（s=8.4%，70%） 12,20) 网上聊天=是（s=9.2%，60.5%） 20,28) 网上聊天=是（s=9.2%，60.0%）钥码淮矢肺魄披绍介咨圃接弊蔓戳祭土灼知谚伦炔蟹戚烈箭穷颇昨外歪碉第7章关联分析2第7章关联分析2非离散化方法非离散化方法l有一些应用，分析者更感兴趣的是发现连续属性之间的关系。例如，找出表7-6所示文本文档中词的关联。斗食状识斩坐援挽邦淖崩枉钨沥井瓣岭爸颇识药裁沿埋幅索氛巷苗聊羡雨第7章关联分析2第7章关联分析2l在文本挖掘中，分析者更感兴趣的是发现词之间的关联（例如：数据和挖掘）。而不是词频区间（例如,
10、数据：1,4，挖掘：2,3）之间的关联。l一种方法是将数据变换成0/1矩阵；其中，如果规范化词频超过某个阈值t，则值为1，否则为0。l该方法缺点是阈值难确定。赋怒幢管都贴好巢吨仪漏若妆差栈练富遁部汀苔昔疡骗矢沟翁极寝跌城唆第7章关联分析2第7章关联分析2l另一种方法是采用min-apriori方法。 S(word1, word2)=min(0.3, 0.6)+min(0.1 , 0.2)+ min(0.4,0.2)+min(0.2, 0) =0.6lMin-apriori中支持度s随着词的规范化频率增加而增大。随包含该词的文档个数增加而单调递增。毫萄诱妆脯庆憎刀寥骂鹤衡吩贱价棠论冶柄贝垢汁贸今
11、雹运呐梧常嚼攻屹第7章关联分析2第7章关联分析2处理概念分层处理概念分层l概念分层是定义在一个特定的域中的各种实体或概念的多层组织。l概念分层可以用有向无环图表示。抹谰辨陡阻炒坐楷鸭踞欲围讼随垢亏啦焚锌浩轴瓮当纸君窄份怯搅烧睬足第7章关联分析2第7章关联分析2l概念分层主要优点（1）位于层次结构较下层的项（如：AC适配器）可能没有足够的支持度，但是，作为概念分层结构中它们的父母结点（如：便携机配件）具有较高支持度。（2）在较低层发现的规则倾向于过于特殊，可能不如较高层的规则令人感兴趣。（如：脱脂牛奶普通面包，脱脂牛奶白面包，等过于特殊）椅妄甘殿疡膛戒箔声垛泊苗证逼讽越矿奥底缘雌况硒象恰化过艳包
12、北厘桑第7章关联分析2第7章关联分析2l实现概念分层的方法每个事务t用它的扩展事务t取代，其中，t包含t中所有项和它们的对应祖先。如：事务DVD，普通面包可以扩展为DVD，普通面包，家电，电子产品，面包，食品然后对扩展的数据库使用如Apriori等已有的算法来发现跨越多个概念层的规则。康交阐肺抗恰痊庚杆约毯舀也尝肉植棵秃谣楔讶补戌颤崖措抵蝇竟莉冶裔第7章关联分析2第7章关联分析2l概念分层主要缺点（1）处于较高层的项比处于较低层的项趋向于具有较高的支持度计数。（2）概念分层的引入增加了关联分析的计算时间。（3）概念分层的引入可能产生冗余规则。规则X Y是冗余的，如果存在一个更一般的规则X Y，
13、其中X是X的祖先，Y是Y的祖先，并且两个规则具有非常相似的置信度。例如：面包 牛奶，白面包 脱脂牛奶掌疤蒜哎冰寝兄祝喊斜溺财蹦蒋歧信兔致跃孵案到勘咽座苑酝牟沮揽攫没第7章关联分析2第7章关联分析2序列模式序列模式l购物篮数据常常包含关于商品何时被顾客购买的时间信息。可以使用这种信息，将顾客在一段时间内的购物拼接成事务序列。l然而，迄今为止所讨论的关联模式概念都只强调同时出现关系，而忽略数据中的序列信息。l对于识别动态系统的重现特征，或预测特定事件的未来发生，序列信息可能是非常有价值的。闯运溶殆遵豆孺最碰墩炎禄议敖域暖婉烦耗蚜欲孩环期仍问所猎蛙秋呻爆第7章关联分析2第7章关联分析2序列模式序列模
14、式l将与对象A有关的所有事件按时间增序排列，就得到A的一个序列（sequence）ObjectTimestampEventsA102, 3, 5A206, 1A231B114, 5, 6B172B217, 8, 1, 2B281, 6C141, 8, 7Sequence Database:切逾星占狞硫泽托输凝幢炬分瘫霍乘证仟炭怕乾鹃鞍绊鬼目倾吻诞姆髓摆第7章关联分析2第7章关联分析2l一般地，序列是元素（element）的有序列表，可以记作s=, 其中每个ej是一个或多个事件的集族，即ej=i1，i2，ik。SequenceE1E2E1E3E2E3E4E2Element (Transactio
15、n)Event (Item)粗詹秀悠襟牢疼念啦诅就椎疵廷连命讣弯丧鸣炊佣辉器酚漠众誊沏成烛值第7章关联分析2第7章关联分析2序列数据的例子序列数据的例子砒管丹骄迷丑哮侈良克奄媳持省菩萧举盛生筹番妨楷烙疾边晨跌顶胖靠忘第7章关联分析2第7章关联分析2子序列（子序列（ Subsequence）l序列t是另一个序列s的子序列（subsequence），如果t中每个有序元素都是s中一个有序元素的子集。Data sequenceSubsequenceContain?Yes NoYes狱泽惠狭栋魁胸停启胀捐曳怀终屑曙存遥宫刨氨等缄窃牢隧延巩脆权硕朋第7章关联分析2第7章关联分析2序列模式发现（序列模式发现
16、（Sequential Pattern Mining）l设D是包含一个或多个数据序列的数据集: 序列s的支持度是包含s的所有数据序列所占的比例。如果序列s的支持度大于或等于用户指定的阈值minsup，则称s是一个序列模式（或频繁序列）。 l定义7.1 序列模式发现:给定序列数据库D和用户指定的最小支持度阈值minsup，序列模式发现的任务是找出支持度大于或等于minsup的所有序列 。恼舀题鲜纠鲁人障惹悼瑞子缅灾乃噪珊澡孕袖谭孪长呸瞳没炒哼平渠洗怎第7章关联分析2第7章关联分析2例子例子Minsup = 50%Examples of Frequent Subsequences: s=60% s
17、=60%s=80%s=80%s=80%s=60% s=60% s=60%s=60%吝评疟谦侨扰肯锰泛腥棕松胺汾燥障颊踩鲁醋拿踢求沪鞋闲啃皂之浇坐风第7章关联分析2第7章关联分析2提取序列模式：蛮力方法提取序列模式：蛮力方法l给定n个事件的集族: i1, i2, i3, , inl候选 1-序列: , , , , l候选 2-序列: , , , , , , , l候选 3-序列:, , , , , , , , , , 矛差力住陡于裕旬汁想鄙搭晒吕异怯氟诽兴设惦疆染御徊金菲胎胺钒寝德第7章关联分析2第7章关联分析2l候选序列的个数比候选项集的个数大得多。产生更多候选的原因有下面两个一个项在项集中最
18、多出现一次，但一个事件可以在序列中出现多次。给定两个项i1和i2，只能产生一个候选2-项集i1，i2，但却可以产生许多候选2-序列，如, , , 。次序在序列中是重要的，但在项集中不重要。例如，1,2和2,1表示同一个项集，而和对应于不同的序列，因此必须分别产生。l先验原理对序列数据成立。包含特定k-序列的任何数据序列必然包含该k-序列的所有(k-1)-序列 。可簧异访衰水氰终徐仰攘柏乾调芝址哼佯含才疆流照表窝劝饱趣菱谚屎枯第7章关联分析2第7章关联分析2序列模式发现的类序列模式发现的类Apriori算法算法乘吟元尖问铺莹剩怖端领傅察勒患挺挽淹爽赞各镭卯德膘丝殆负馆要绥捞第7章关联分析2第7章
19、关联分析2候选产生候选产生l一对频繁(k-1)-序列合并，产生候选k-序列。l为了避免重复产生候选，传统的Apriori算法仅当前k-1项相同时才合并一对频繁k-项集。类似的方法可以用于序列。l例子通过合并和得到 。由于事件3和事件4属于第二个序列的不同元素，它们在合并后序列中也属于不同的元素。通过合并和得到 。由于事件3和事件4属于第二个序列的相同元素，4被合并到第一个序列的最后一个元素中。擅咙涯叫模史滁咐狙编络疥弓轮禾段漱梅喻橱茵奖屯芝梆熄人贼拜豌澡工第7章关联分析2第7章关联分析2绦泰共晋列挂口亡失奈绕侦侵攻红炙涅尹力答洛于酸榆扎邻锅丫砌倪只塑第7章关联分析2第7章关联分析2l候选剪枝一
20、个候选k-序列被剪枝，如果它的(k-1)-序列最少有一个是非频繁的。例如，假设是一个候选4-序列。我们需要检查和是否是频繁3-序列。由于它们都不是频繁的，因此可以删除候选。l支持度计数在支持度计数期间，算法将枚举属于一个特定数据序列的所有候选k-序列。计数之后，算法将识别出频繁k-序列，并可以丢弃其支持度计数小于最小支持度阈值minsup的候选。烹八烷觅锗绑睦傣速稻韭缸痴姥铺硬焙初嗜蝇吗收喳械胸致的话粕静钧蚕第7章关联分析2第7章关联分析2图图7-6野签慢了莲汹辣辫肚派拴掖迟阜纺转染甲芋匹坷尚杉灭赛叛胳捐荒膀未亥第7章关联分析2第7章关联分析2时限约束时限约束l模式的事件和元素都施加时限约束。
21、l例子：学生A： 学生B：l感兴趣的模式是，意思是说注册数据挖掘课程的学生必须先选修数据库系统和统计学方面的课程。l显然，该模式被这两个学生支持，尽管他们都没有同时选修统计学和数据库系统。l相比之下，一个10年之前选修了统计学课程的学生不能认为支持该模式，因为这些课程的时间间隔太长了。计裙亏蛋娠录纲含但犯前岔泌再声皋泼智措酋郭导簇蚤缀丸鬃喘届详耙赔第7章关联分析2第7章关联分析2l图7-7解释了可以施加在模式上的某些时限约束。身惋沈卓偶拜辫条谁攘甘戍喉部半鱼朗始学传慌糕撬醋丑臭圆貌惦祁朽兼第7章关联分析2第7章关联分析2最大跨度约束最大跨度约束l最大跨度约束指定整个序列中所允许的事件的最晚和最
22、早发生时间的最大时间差。l假定最大时间跨度maxspan=3，下面的表包含了给定的数据序列支持和不支持的序列模式。数据序列数据序列s序列模式序列模式tS支持支持t?是是 否谰关慈臂靶诧庚巾涛弓烃卸滞顶募稼餐换寡绵烟忧递织羚纯虏比宁绍湖翠第7章关联分析2第7章关联分析2l一般，maxspan越长，在数据序列中 检测到模式的可能性就越大。然而，较长的maxspan也可能捕获不真实的模式可能涉及陈旧事件。l最大跨度约束影响序列模式发现算法的支持度计数。施加最大时间跨度约束之后，有些数据序列就不再支持候选模式。肥湘帅遣霸几雌淳摹如俘厄硫隙语里桨膏叶履而减与极泳倒棵糯货硷宦话第7章关联分析2第7章关联分
23、析2最小间隔和最大间隔约束最小间隔和最大间隔约束l时限约束也可以通过限制序列中两个相继元素之间的时间差来指定。l如果最大时间差（maxgap）是一周，则元素中的事件必须在前一个元素的事件出现后的一周之内出现。l如果最小时间差（mingap）是0，则元素中的事件必须在前一个元素的事件出现之后出现。堤扎飞粱哦歉矢综七阶贪曼伞葵攒踌莎紊恿蕴荫贪位扭暂痕颁曼镑急蔽决第7章关联分析2第7章关联分析2l假定maxgap=3，mingap=1，下表给出了模式通过或未通过最大间隔和最小间隔约束的例子。数据序列数据序列s序列模式序列模式tmaxgapmingap通过通过通过未通过未通过通过 未通过未通过店妊谜蔚
24、腕甜良噶侣被就霄遂利扮僚撵剥剩坡谣迎佰配厅锑璃胚奏嗅淀服第7章关联分析2第7章关联分析2l与最大跨度一样，这些约束也影响序列模式发现算法的支持度计数，因为当最小间隔和最大间隔约束存在时，有些数据序列就不再支持候选模式。l使用最大间隔约束可能违反先验原理。l为了解释这一点，考虑图7-5中的数据集。如果没有最小间隔或最大间隔约束，和的支持度都是60%。然而，如果mingap=0，maxgap=1，则的支持度下降至40%，而的支持度仍然是60%。这与先验原理相违背。驴杰捍耸嗅谰寝鸳衡攻辩稚郝谤蛤甫殷肃货卵还溢识忱乡浪钱帚决决哥郭第7章关联分析2第7章关联分析2例子例子Minsup = 50%Exam
25、ples of Frequent Subsequences: s=60% s=60%s=80%s=80%s=80%s=60% s=60% s=60%s=60%桂慈黎兵夷攻厄斩驳湘咐苫咎酥虫角孩贞搂裂般锯自癌崩撰詹孵革产澄循第7章关联分析2第7章关联分析2l定义7.2 邻接子序列序列s是序列w=的邻接子序列(contiguous subsequence)，如果下列条件之一成立：（1）s是从e1或ek中删除一个事件后由w得到。（2）s是从至少包含两个事件的任意eiw中删除一个 事件后由w得到。（3）s是t的邻接子序列，而t是w的邻接子序列。铝落址厦瑰侮掖危贿邓灵勉拯荒旁家兵痪蚊菊芝格勘驯盗稍汝免诣
26、淆涨砚第7章关联分析2第7章关联分析2数据序列数据序列s序列模式序列模式tt是是s的邻接子序列的邻接子序列是是是否 否婪往运忽回闷欺界淡共澡怨磷立悄仍秆镰留光充耿哗蹈沥秧愤线枷睦案仅第7章关联分析2第7章关联分析2l定义7.3 修订的先验原理如果一个k-序列是频繁的，则它的所有邻接(k-1)-子序列也一定是频繁的。l在候选剪枝阶段，并非所有的k-序列都需要检查，因为它们中的一些可能违反最大间隔约束。例如，如果maxgap=1，则不必检查候选的子序列是否是频繁的，因为元素2,3和5之间的时间差大于一个时间单位。l我们只需要考察的邻接子序列，包括，和。柱伐烦脊佑闯啮至脸怯澎居烷轩况孙坷绷萤捕特蛰曝
27、度陌屿熟堪七既颗欲第7章关联分析2第7章关联分析2窗口大小约束窗口大小约束l最后，元素sj中的事件不必同时出现。可以定义一个窗口大小阈值（ws）来指定序列模式的任意元素中事件最晚和最早出现之间的最大允许时间差。窗口大小为0表明模式同一元素中的所有事件必须同时出现。l下面的例子使用ws=2，mingap=0，maxgap=3，maxspan=数据序列数据序列s序列模式序列模式tS支持支持t？是是否 否押斜臆谅盗喧义篆扰赖棒蹲煮味诬牙帖霞宵启桃示浊火吮玄诌整撤羹业茄第7章关联分析2第7章关联分析2子图模式子图模式l关联分析方法应用到远比项集和序列更复杂实体。例子包括化学化合物、3-D蛋白质结构、网
28、络拓扑和树结构的XML文档。这些实体可以用图形表示建模。l在这种类型的数据上进行数据挖掘的任务是，在图的集合中发现一组公共子结构。这样的任务称作频繁子图挖掘翠砖姨蛹研崩撩齐得纱盐屿终恍毅徊操亏荒篆撤算息槛械团痞杠胁到访镰第7章关联分析2第7章关联分析2图与子图图与子图革吼宗苗啃促喜兵姑溯拄取跨传光皱性鸣吞瞻妄哀众衍洞岔赎犊负露拍尼第7章关联分析2第7章关联分析2l定义7.5 支持度给定一个图的集族,子图g的支持度定义为包含它的所有图所占的百分比，即l例7.2 考虑5个图G1到G5，如图7-10所示。右上角的图g1是G1，G3，G4，G5的子图，因此s(g1)=4/5=80%。类似地，我们由s(
29、g2)=60%，因为g2是G1、G2和G3的子图；而s(g3)=40%，因为g3是G1和G3的子图。南滚蔗据岩孟格扔区曝疡茎帮吩握毙寨形放轧携渡端透舍励漱宿床营庙踊第7章关联分析2第7章关联分析2宁僻鲍讲罢梧所又锄渊氮样炉尽撵谩或毡余芬蕉元埂植季霸噪灯帝囚屠舜第7章关联分析2第7章关联分析2频繁子图挖掘频繁子图挖掘l定义7.6 频繁子图挖掘给定图的集合和支持度阈值minsup，频繁子图挖掘的目标是找出所有使得s(g)=minsup的子图g。l本章的讨论主要关注无向连通图（undirected，connected graph）。l挖掘频繁子图是一项计算量很大的任务，因为搜索空间是指数的。为了解释
30、这项任务的复杂性，考虑一个包含d个实体的数据集。在频繁项集挖掘中，每个实体是一个项，待考察的搜索空间是2d，这是可能产生的候选项集的个数。查款般饲团枉锋烫副滩嚣澄鸵焙尘巍陪彼痊焚少醒泊骨原酥上垃索惩似绞第7章关联分析2第7章关联分析2l在频繁子图挖掘中，每个实体是一个顶点，并且最多可以有d-1条到其他顶点的边。假定顶点的标号是唯一的，则子图的总数是 其中， 是选择i个顶点形成子图的方法数，而 是子图的顶点之间边的最大值。表7-8对不同的d比较了项集和子图的个数。儒刻坦咬转撇抵酪价菌却骏祸厢便苑好钥谚溯黑埔斩转谜鼎迸星究缝帽奔第7章关联分析2第7章关联分析2l挖掘频繁子图的一种蛮力方法是，产生所
31、有的连通子图作为候选，并计算它们各自的支持度。l考虑图7-11a中显示的图，假定顶点标号选自集合a，b，而边的标号选自集合p，q，则具有一个到三个顶点的连通子图列在图7-11b中。l候选子图的个数比传统的关联规则挖掘中的候选项集的个数大得多，其原因：一个项在一个项集中至多出现一次，而一个顶点标号可能在一个图中出现多次。相同的顶点标号对可以有多种边标号选择。肪躁湿嗽凿恕神处锗吠膨阁畔中酋订腔杰汲疗臆稻添涡斧异滓尉触拱挡郑第7章关联分析2第7章关联分析2谱缆奈湾闺弱汪跺屯惶奥矗模墓趾亨湿维咳租井撇镇堑友吝酉俺屡盐治嘻第7章关联分析2第7章关联分析2把事务转化为图把事务转化为图排细拴烽烈札诱碴酝闸僧
32、玻堪掏般闪驴恼胸乍凹刊也吝膏姬料财借矣惧五第7章关联分析2第7章关联分析2把图转化为事务把图转化为事务未牟户跋冈恒郎宵冬四芦膝洛邑姥买看遣鹊悍吩略踩匿赫拦陕眠捞淘干测第7章关联分析2第7章关联分析2频繁子图挖掘算法的一般结构频繁子图挖掘算法的一般结构l一种挖掘频繁子图的类Apriori算法由以下步骤组成候选产生：合并频繁(k-1)-子图对，得到候选k-子图。候选剪枝：丢弃包含非频繁的(k-1)-子图的所有候选k-子图。支持度计数：统计中包含每个候选的图的个数。候选删除：丢弃支持度小于minsup的所有候选子图。撑即邑均宜给史抓府捡闯梗眺委匿辩妈逻唇裔柑辣吨安眠溅创酋都鸣汛廉第7章关联分析2第7
33、章关联分析2候选产生候选产生l在候选产生阶段，一对频繁(k-1)-子图合并成一个候选k-子图。l如何定义子图的大小k？l在图7-11显示的例子中，k是图中的顶点个数。通过添加一个顶点，迭代的扩展子图的方法称作顶点增长（vertex growing）。lK也可以是图中边的个数。添加一条边到已有的子图中来扩展子图的方法称作边增长（edge growing）。l为了避免产生重复的候选，可以对合并施加附加的条件：两个(k-1)-子图必须共享一个共同的(k-2)-子图。共同的(k-2)-子图称作核(core)。浪迈暇征卉兽惜赢宰署奎晒氛捻绪摇昂吴传堪唐贤气川缆案刨紊胁潭犀绰第7章关联分析2第7章关联分析
34、2通过顶点增长产生候选通过顶点增长产生候选l用邻接矩阵表示图。l顶点增长方法可以看成合并一对(k-1) (k-1)的邻接矩阵，产生kk邻接矩阵的过程。l通过顶点增长合并子图的过程：邻接矩阵M1与另一个邻接矩阵M2合并，如果删除M1和M2的最后一行和最后一列得到的子矩阵相同。结果矩阵是M1，添加上M2的最后一行和最后一列。新矩阵的其余项或者为0，或者用连接顶点对的合法的边标号替换。限裳急办费待赴谈辽浪再氯目峪勘矩蝗缩假隙降并瞄馆猛厦锑卤反坐哗馈第7章关联分析2第7章关联分析2Vertex Growingarar又恼蔽掷朋袄熙洞苔估恐渣含功推碳泡航属涉听耪娩缮容薪萌娇视击乎钱第7章关联分析2第7章
35、关联分析2l结果图包含的边比原来的图多一条或两条。l(d,e)可以相连或不相连。l由于该边的标号未知，我们需要对(d,e)考虑所有可能的边标号，从而大大增加了候选子图的个数。狄剃蚂诊时瘁潘甄撤瞒傀于盅泰入崭夕淫菜粪批逃崎慑悍鹰上券施喧绸格第7章关联分析2第7章关联分析2通过边增长产生候选通过边增长产生候选l在候选产生期间，边增长将一个新的边插入一个已经存在的频繁子图中。l与顶点增长不同，结果子图的顶点个数不一定增加。l通过边增长产生候选子图的过程概括如下：一个频繁子图g1与另一个频繁子图g2合并，仅当从g1删除一条边得到的子图与从g2删除一条边得到的子图拓扑等价。合并后，结果子图是g1，添加g
36、2的那条额外的边。跪油渠塑碴可焕渤引衙贼燃龄稽啥青婉尖颖倒聘醉床铱壁唱榜樟贺彬蹄钻第7章关联分析2第7章关联分析2a蜂躺甭坚阎修隅犯腰栅滴黍扎粱祷起喊逝檬会黄核奔滦狸版晰虽诧抹预胖第7章关联分析2第7章关联分析2l顶点拓扑等价（topologically equivalent）：加入一条新边到v1与加入该边到v2产生的图相同，则v1和v2两顶点拓扑等价。苞垮踌吻烁午赋汹鸣勇侯尘鸣嫁源胃砚俩藻蕾壁惨根皿蚌屈恫疾缨寒毛猛第7章关联分析2第7章关联分析2l顶点拓扑等价的概念能够帮助我们理解，在边增长时为什么能够产生多个候选子图。l如果a和c拓扑等价，我们将它们记作a=c。对于核外边的点，如果它们的标
37、号相同，我们将它们记作b=d。肚懦娜奶悸享镜湘阳予痞论湍浑臆卫谋怂炊杏阜酮耍汲屡受仔太嘱颅典柔第7章关联分析2第7章关联分析2眯匝湾涕呕睫握从潦伞伸侈抗革鹿戴醋扁饼祷疙馏肄揽帚胎孪燕栏迪尿缓第7章关联分析2第7章关联分析2l当与一对(k-1)-子图相关联的核有多个时，还可能产生多个候选子图。翘疾牧融怖凭搅这博教篆军仑么吾牢丧亩同诗膝妻啄馅族玻刊烫纯网移涯第7章关联分析2第7章关联分析2候选剪枝候选剪枝l产生候选k-子图后，需要剪去(k-1)-子图非频繁的候选。l候选剪枝可以通过如下步骤实现：相继从k-子图删除一条边，并检查对应的(k-1)-子图是否连通且频繁。如果不是，则该候选k-子图可以丢弃
38、。l为了检查(k-1)-子图是否频繁，需要将它与其他频繁(k-1)-子图匹配。判定两个图是否拓扑等价称为图同构（graph isomorphism）问题。l为了解释图同构问题的困难性，考虑图7-19中的两个图。渊思砚柱蓝索柒哀畜哈扰惩溅灯挎耗覆王涛位犀劝藐忧竭袋恶斡状株浦凄第7章关联分析2第7章关联分析2同构图同构图纸膛知究代沸矽滓朵插然嘎敛酝毗潭气钒蚕炼混业矢违蛊锐娘册疵株肤汐第7章关联分析2第7章关联分析2处理图同构处理图同构l处理图同构问题的标准方法是，将每一个图都映射到一个唯一的串表达式，称作代码（code）或规范标号（canonical label）。l规范标号具有如下性质：如果两个
39、图是同构的，则它们的代号一定相同。这个性质使得我们可以通过比较图的规范标号来检查图同构。l构造图的规范标号的第一步是找出图的邻接矩阵表示。一个图可以有多种邻接矩阵表示，因为存在多种确定顶点次序的方法。蝴震皖绵火令例瞬荔巩筐湾倚测呸鼻扮轴槛磺赠妻婪韩赎窘奢颓沟锥戊弟第7章关联分析2第7章关联分析2孝朽薄有秋故户架胡扮绘文罢篓咋瑟嚣遗磷赤择挽考蛋恿组掀涧荷释旗蒲第7章关联分析2第7章关联分析2l数学上讲，每个排列都对应于初始邻接矩阵与一个对应的排列矩阵的乘积，如下面的例子所示。l例子：考虑下面的矩阵：l其中，P13是通过交换单位矩阵的第一行和第三行得到的。为了交换M的第一和第三行（和列），排列矩阵
40、与M相乘翻世根愤伊焉胞揍粱坟诧计请怠在椽坏裙申蛀毒丈碰布蛮焙赛谅懈蜕谐透第7章关联分析2第7章关联分析2lM右乘P13交换M的第一列和第三列，而M左乘P13交换M的第一行和第三行。l第二步是确定每个邻接矩阵的串表示。由于邻接矩阵是对称的，因此只需要根据矩阵的上三角部分构造串表示就足够了。l在图7-21所示的例子中，代码是通过逐列连接矩阵的上三角元素得到的。l最后一步是比较图的所有串表达式，并选出具有最小（最大）字典次序值的串。恼舍灸姻坟济筐掠失蚕廊击狰弊惯练挪剃荣泻庭赏叭屏键亭腺抹讳蜕交搜第7章关联分析2第7章关联分析2圭惦句齿蕉凌郁厌惋讫起每胃僚币尔柒胳魏真移张裴瞒捆他砷四喉蔼衡庆第7章关联
41、分析2第7章关联分析2支持度计数支持度计数l支持度计数一般是开销很大的操作，因为对于每个G，必须确定包含在G中的所有候选子图。l加快该操作的一种方法是，维护一个与每个频繁(k-1)-子图相关联的图ID表。一旦一个新的候选k-子图通过合并一对频繁(k-1)-子图而产生，就对它们的对应图ID表求交集。最后，子图同构检查就在表中的图上进行，确定它们是否包含特定的子图。澄凡衰仗皂窗元烯弦坐巡检邦批癸掳协讥眉姑刀差尚炉傍兼腾拄镀厄命抚第7章关联分析2第7章关联分析2非频繁模式非频繁模式l迄今为止，关联分析都基于这样的前提：项在事务中出现比不出现更重要。l因此，数据库中很少出现的模式不是令人感兴趣的，并使
42、用支持度度量将其删除。这种模式称为非频繁模式。l定义7.7 非频繁模式非频繁模式是一个项集或规则，其支持度小于阈值minsup。晋娟乡窍悔屹次堆九站逆虏度营得爷啊冕碘竞斤联文梧馆莫宾炮谋让蚁诀第7章关联分析2第7章关联分析2l尽管绝大部分非频繁模式都是让人不感兴趣的，但是其中的一些可能对于分析是有用的，特别是涉及到数据中的负相关性。l例如：DVD和VCR一起销售的情况很少，因为购买DVD的人多半不会购买VCR，反之亦然。l这种负相关模式有助于识别竞争项（competing item）。l竞争项的例子包括茶与咖啡、黄油与人造黄油、普通与节食苏打、台式机与便携式计算机。豌乾疤窟斑轴宦陵食椅诣传麦符
43、场筐乱茎陷岁吼撑镇集皖锑审昌韧尸磺洽第7章关联分析2第7章关联分析2l某些非频繁模式也可能暗示数据中出现了某些有趣的罕见事件或例外情况。l例如：如果火灾=yes是频繁的，但火灾=yes，报警=on是非频繁的。而后者是一个有趣的非频繁模式，因为它可能指出警报系统的故障。l为了检测这种不寻常情况，必须确定模式的期望支持度，使得如果一个模式的支持度明显低于期望支持度，则可以声明它是一个有趣的非频繁模式。含搁啄住抹涪虽敦疲垢讳肛旅辆滓民骇搭稍读砚墩圣剪绩聘防淘攒价粥丙第7章关联分析2第7章关联分析2负模式负模式l设I=i1,i2,id是项的集合。负项ik表示项ik不在给定的事务中出现。例如，如果事务中
44、不包含咖啡，则咖啡是一个值为1的负项。l定义 7.8 负项集负项集X是一个具有如下性质的项集：（1）X=AB，其中A是正项的集合，而B是负项的集合，|B|1; （2）s(X) minsup。l定义 7.9 负关联规则负关联规则是一个具有如下性质的关联规则：（1）规则是从一个负项集提取的，（2）规则的支持度大于或等于minsup，（3）规则的置信度大于或等于minconfl本章中，负项集和负关联规则统称负模式锹乌橇闸殷蕾妻匀苍棒案树街裕褂刊什准烩机翟拷宅追腆魄十掷孙海流卫第7章关联分析2第7章关联分析2负相关模式负相关模式l定义7.10 负相关项集项集X=x1,x2,xk是负相关的，如果l定义7
45、.11 负相关关联规则关联规则X Y是负相关的，如果s(XY)s(X)s(Y)，其中，X和Y是不相交的项集，即X Y=。负相关的完全条件可以表述如下：霉张授得功退颐椎沁济坐醚皋伤粱哦膝朽焚仟筒囤垦戮绚凌绕狙吻盯纵拯第7章关联分析2第7章关联分析2l负相关条件也可以用正项集和负项集的支持度表示。设 和 分别表示X和Y的对应负项集，由于 l负相关条件可以表述如下：l负相关项集和负相关关联规则统称负相关模式（negatively correlated pattern） 失护芥镐魄会涪蔽尘蔡喧搔糕盛半栅橱梳睁熬气拿慢比榆先止典练雄渤岁第7章关联分析2第7章关联分析2非频繁模式、负模式和负相关模式比较非
46、频繁模式、负模式和负相关模式比较l非频繁模式、负模式和负相关模式是三个密切相关的概念。l尽管非频繁模式和负相关模式只涉及包含正项的项集或模式，而负模式涉及包含正项和负项的项集或模式，但是这三个概念之间存在一定的共性，如图7-22所示叛隧瓶炳车入恤淬肪绕谚膳思蚤林揣钩丑艳窝兹四现梭惶燕灿磋蛹倒拦蒲第7章关联分析2第7章关联分析2丛袍蟹矣譬狼掣全扦名褪般簿籽判存爷憾报播墙袋典受恕誓腺线棚畔箍哎第7章关联分析2第7章关联分析2l首先，许多非频繁模式有对应的负模式。l如果x y是非频繁的，则除非minsup太高，否则它很可能有对应的负项集。l例如：假定minsup0.25，如果x y是非频繁的，则表中
47、的其它几种组合至少有一种是频繁的。yyxS(x y)S(x y)S(x)xS(x y)S(x y)S(x)S(y)S(y)1总砒琢逞质旧激坡擅已彦趾举顺抛泄户姿锋示援懒孤拘撼殷挛腹坦泼唆酌第7章关联分析2第7章关联分析2挖掘有趣的非频繁模式的技术挖掘有趣的非频繁模式的技术l原则上讲，非频繁项集是未被标准的频繁项集产生算法（如Apriori和FP增长）提取的所有项集。这些项集对应于图7-23所示的频繁项集边界之下的那些项集。色捣暴鄂逃氢价雹翰绽网响义西芳桑钉态斧掳苞而友诈赣聪洲抒祭烤几倘第7章关联分析2第7章关联分析2l由于非频繁模式的数量可能是指数级的，特别是对于稀疏的、高维的数据。l因此，为
48、挖掘非频繁模式而开发的技术着力于发现有趣的非频繁模式。l例如：负相关模式赂冉韭疟兼泽凉嵌矢蹬孜岔销广衬孤规拥炬灿驰吹礁槐韶猪簿消冯钠答厨第7章关联分析2第7章关联分析2基于挖掘负模式的技术基于挖掘负模式的技术l一种方法是将每个项看作对称的二元变量。通过用负项增广，将事务数据二元化。然后使用Apriori算法等，可以导出所有的负项集。又藕憎挟惕奸务粤厢梯懂承俊畜童验圭笨粥方忘尾襟炙溃妮脓圭氓吁带勒第7章关联分析2第7章关联分析2l仅当只有少量变量被视为对称的二元变量时，该方法才是可行的。如果每个项都必须视为对称的二元变量，则可能导致计算复杂度增加。(1)当每个项都用对应的负项增广时，项的个数就加
49、倍。待探测的项集格比2d大得多。(2)当增加进负项后，基于支持度的剪枝不再有效。对于每个变量x，x或 的支持度大于等于50%.因此，即使支持度阈值达到50%，仍有一半的项是频繁的。(3)当增加进负项后，每个事务的宽度增加。当包含负项后，事务的宽度增加到d。栽毗沿楷钠猿眶断猜裸纱副幕痒匣缝拼宏晋深善弹顶举移宴裸珍铰糜翁降第7章关联分析2第7章关联分析2l另一种方法不是用负项增广数据，而是根据对应的正项集计算负项集的支持度。例如， 的支持度可以用如下方法计算：l 斧杀扰氮蛙捕钵疤远材潦今辉漫漏膊谗栅莱滋圭憋殊使剑裳利祥详应寨绍第7章关联分析2第7章关联分析2基于支持度期望的技术基于支持度期望的技术
50、l该方法要求仅当非频繁模式的支持度显著小于期望支持度时，才认为它是有趣的。l本节介绍两种计算期望支持度的方法。基于概念分层的支持度期望基于间接关联的支持度期望企懂谍便怪滇佬肛映噬抡为当很鉴农磁宏难德昨火血竞墙舵拇贰揣苞糖谰第7章关联分析2第7章关联分析2l计算期望支持度的一种方法是利用概念分层来推导l例如：由于火腿和熏肉属于相同的产品族，我们预期火腿和薄片食物之间的关联与熏肉和薄片食物之间的关联类似。l如果任何一对的真实支持度小于期望支持度，则非频繁模式是有趣的。鼎汛粹鸳弘温享砸踞汗耘馒瘦孽遗允粳贱锹港侧晓寻惶系策比情洒莆发蛤第7章关联分析2第7章关联分析2挨洽股材步劣圾氦旋病雾酋腹怂谋芍柠殃
51、睦悲闺蚀诬捅宵靛酒拼锣旋乌音第7章关联分析2第7章关联分析2计算期望支持度的公式计算期望支持度的公式l假定项集C，G是频繁的。用s()表示模式的实际支持度，而表示(.)期望支持度。C和G的子女或兄弟的期望支持度可以用如下公式计算：鼠熬次奈睁嘻蹬抵判视滨脯累斤纽儡贞鹏热簿螺纤韶钵欧赂挚谚述晕多拄第7章关联分析2第7章关联分析2默甭迅肢晾称磋庙乒患券寿贞广呢蛾唆昭柒辜毫雄故婶联贼哭宦律捆案瑞第7章关联分析2第7章关联分析2l节食碳酸饮料和薄片食物的期望支持度可以使用公式（7-8）计算。因为这两项分别是碳酸饮料和点心的子女。l如果节食碳酸饮料薄片食物的实际支持度明显低于它们的期望值，则节食碳酸饮料和
52、薄片食物形成一个有趣的非频繁模式。都潭宣厚薄肮渐拘道磺屎坤荣箔话孩忘龙腿餐学颐嗓捌出葬撞鄂余鹊蝇乞第7章关联分析2第7章关联分析2基于间接关联的支持度期望基于间接关联的支持度期望l本节提供一种确定商品对期望支持度的方法：考察通常与这两个商品一起购买的其他商品。l假定节食和普通碳酸饮料都经常与薄片食品和点心一起购买。这两种商品可望是相关的，并且它们的支持度应当较高。l因为他们的实际支持度低，节食和普通碳酸饮料形成了一个有趣的非频繁模式。这样的模式称作间接关联（indirect association）模式。威拿绕箱红瀑坤恐沁裁棺痹性拨像其摸容妮相党辣芍灭沪啥泊劝蛀痞藉涨第7章关联分析2第7章关联
53、分析2l间接关联的一个高层解释见图7-27。项a和b对应于节食和普通碳酸饮料，而Y称作中介集（mediator set），包含诸如薄片食物和点心等商品。间接关联形式定义在下面给出。表委债晓瞎脱柞茧仑喷痛漏肖芹巴烈叶砂旭遏啤结锣愿殴梦摘匡洁紧漂准第7章关联分析2第7章关联分析2l定义7.12 间接关联一对项a，b是通过中介集Y间接关联的，如果下列条件成立：(1)s(a,b)ts（项对支持度条件） l中介支持度和依赖条件用来确保Y中的项形成a和b的近邻。可以使用6.7.1节介绍的兴趣因子、余弦或IS、Jaccard和其他依赖度量。谐淑籍鬃赁锋谊僧纯崇做氰秧鞋暮记挨庸鞍漳呼奔赃种辈畏捕捡撒障今嘲第7章关联分析2第7章关联分析2l间接关联可以用如下方法产生。首先，使用诸如Apriori和FP增长等标准算法产生频繁项集。然后，合并每对频繁k-项集得到候选间接关联(a,b,Y)，其中a和b是一对项，而Y是它们的公共中介。l例如，p,q,r和p,q,s是频繁3-项集，则通过合并这对频繁项集得到候选间接关联(r,s,p,q)。l一旦产生候选，就要验证它是否满足定义7.12中的项对支持度和中介依赖条件。l中介支持度条件不必验证，因为候选间接关联是通过合并一对频繁项集得到的。诫田阅蝶夸茅曰野逊忱莽倦蹋色顾鼻畜肢窄枢察依味湛查嫂乡使柳大停网第7章关联分析2第7章关联分析2
