17.-关联分析

数据挖掘:关联分析王成（副教授）华侨大学计算机科学与技术学院主要内容关联分析Apriori算法FP-Growth算法啤酒与尿布关联分析关联分析：发现隐藏在大型数据集中的有趣的联系所发现的有趣的联系通常用关联规则或频繁项集的形式表示关联规则:{Diaper}→{Beer}TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,CokeTID:事务(transaction)记录的惟一标识Diaper:尿布频繁项集项(Item)例:Milk,Bread,Diaper为项项集(Itemset)包含0个或多个项的集合k-项集:包含k个项的集合例:{Milk,Bread,Diaper}为3-项集支持度计数(Supportcount)包含特定项集的事务个数例如：({Bread,Milk,Diaper})=2支持度(Support)包含项集的事务数与总事务数的比值例：s({Milk,Bread,Diaper})=({Bread,Milk,Diaper})/|T|=2/5|T|为数据库中事务总数频繁项集(FrequentItemset)满足最小支持度阈值(minsup)的所有项集TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,Coke直观理解支持度：你说你是频繁项集，有多少数据支持你的这个结论？关联规则关联规则(Associationrules)形如XY的蕴含表达式其中X和Y是不相交的项集例:{Milk,Diaper}{Beer}支持度(Support)和置信度(Confidence)TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,Coke)()()(,XYXYXcConfidence(),()TXYSupportsXY|T|为数据库中事务总数X、Y为项集为项集的集合并操作支持度：有多少交易同时购买了X和Y中的商品置信度：购买了X中商品的交易中，有多少同时也购买了Y中的商品XY关联规则关联规则(Associationrules)形如XY的蕴含表达式其中X和Y是不相交的项集例:{Milk,Diaper}{Beer}支持度(Support)和置信度(Confidence)TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,Coke)()()(,XYXYXcConfidenceT)()(,YXYXsSupport|T|为数据库中事务总数X、Y为项集例子:Beer}Diaper,Milk{(Milk,Diaper,Beer)20.4|T|5s(Milk,Diaper,Beer)20.67(Milk,Diaper)3c支持度和置信度的意义低支持度购买了牛奶和面包的顾客100%会同时购买篮球(高置信度)，但是只有一位顾客同时购买了牛奶、面包和篮球(低支持度)。不是有意义的关联规则低置信度同时购买牛奶面包的顾客中只有10%还会同时购买篮球(低置信度)。不是有意义的关联规则满足了最小支持度和最小置信度阈值的关联规则才是有趣的(强关联规则)阈值可由领域专家设定多维关联规则单维关联规则购买({电脑})=购买({打印机,杀毒软件})多维关联规则购买({电脑})=年龄={20-40}and收入={5K+}天气=晴and温度=适中and湿度=高=外出=yes外出=yesand天气=晴=温度=适中and湿度=高多维关联规则外出=yesand天气=晴=温度=适中and湿度=高看成项(Item)外出=yesand天气=晴=温度=适中and湿度=高牛奶尿布啤酒可乐support=count(外出=yes&天气=晴&温度=适中&湿度=高)/|T|confidence=sup(外出=yes&天气=晴&温度=适中&湿度=高)/sup(外出=yes&天气=晴)|T|为数据集大小关联规则挖掘给定交易数据集T,关找出支持度大于等于minsup且置信度大于等于minconf的所有规则,minsup和minconf是对应的支持度和置信度阈值计算所有可能的规则计算各个规则的支持度和置信度暴力法包含d个项的数据集可产生3d-2d+1+1条规则若d=6，可产生602条规则计算代价太大关联规则挖掘规则的支持度依赖于对应的项集{Beer,Diapers,Milk}{Beer,Diapers}→{Milk}{Beer,Milk}→{Diapers}{Diapers,Milk}→{Beer}{Beer}→{Diapers,Milk}{Milk}→{Beer,Diapers}{Diapers}→{Beer,Milk}以上六条规则支持度相同若{Beer,Diapers,Milk}不是频繁项集，则其生成的六条候选规则一定不会满足最小支持度的要求，可全部剔除关联规则挖掘因此，将关联规则挖掘任务划分为两个子任务：任务1.生成频繁项集发现满足最小支持度阈值的所有项集(频繁项集)任务2.生成规则在任务1的基础上，从频繁项集中提取满足最小置信度阈值的规则(强规则)极大地减少了候选规则的数量若有n个项，则可生成Cn1+Cn2+...Cnn=2n-1个频繁项集的候选项集若n=100，则大约可生成1.27×1030个频繁项集的候选项为确定频繁项集，要为所有候选项集计算支持度优化方向：减少候选项集的数量计算量仍然太大关联规则挖掘由a,b,c,d,e生成的所有项集主要内容关联分析Apriori算法FP-Growth算法Apriori算法十大数据挖掘算法之一C4.5k-MeansSVMAprioriEMPageRankAdaBoostkNNNaïveBayesCARTApriori算法(生成频繁项集)Apriori原理：如果一个项集是频繁的，那它的所有子集一定也是频繁的反之，如果一个项集是非频繁的，那它的所有超集一定也是非频繁的(Apriori原理的逆否命题)生成所有候选项集计算各项集的支持度，确定频繁项集逐步生成候选项集，并计算支持度，若一个项集是非频繁的，根据Apriori原理，其所有超集一定也是非频繁的，因此无需再为其超集计算支持度得到所有频繁项集基于支持度的后剪枝基于Apriori原理的预剪枝Apriori算法(生成频繁项集)若{c,d,e}是频繁的，则其所有子集也是频繁的Apriori算法(生成频繁项集)若{a,b}是非频繁的，则其所有超集也一定是非频繁的Apriori算法(生成频繁项集)为每个项产生候选1项集C1,计算支持度并后剪枝，确定频繁1-项集F1在频繁1-项集F1基础上产生候选2项集C2，计算支持度并后剪枝，确定频繁2-项集F2在频繁(k-1)-项集Fk-1的基础上产生候选k-项集Ck，计算支持度并后剪枝，确定频繁k-项集Fk直到Fk为空集Apriori的两个重要特征：1.是一个逐层算法，每次迭代只扩展一个项；2.采用“产生-测试”策略来发现频繁项集。每次迭代，由上一次迭代发现的频繁项集Fk-1产生新的候选项集Ck，再计算候选的支持度并进行后剪枝Apriori算法(生成频繁项集)假定交易或项集中的项按字母序排序若两频繁项集Fk-1的前k-2项相同，则将它们进行连接，形成候选k项集Ck如频繁项集{面包，尿布}和{面包，牛奶}合并，形成了候选3-项集{面包，尿布，牛奶}。算法不会合并项集{啤酒，尿布}和{尿布，牛奶}，因为它们的第一个项不相同。•{啤酒，尿布}和{尿布，牛奶}合并可得到{啤酒，尿布，牛奶}•但{啤酒，尿布，牛奶}同样可以通过合并{啤酒，尿布}和{啤酒，牛奶}得到•若频繁2项集中不存在{啤酒，牛奶}，•则{啤酒，尿布，牛奶}一定是非频繁的•此时若合并{啤酒，尿布}和{尿布，牛奶}，则得到的3-项集一定是非频繁的，因此没有必要合并频繁项集Fk的K个子集都是频繁的，因此任何一个子集Fk-1不是频繁的，则其一定不是频繁的Apriori算法(生成频繁项集)示例1项支持度Bread4Cola2Milk4Beer3Diaper4Eggs1项集支持度{Bread,Milk}3{Bread,Beer}2{Bread,Diaper}3{Milk,Beer}2{Milk,Diaper}3{Beer,Diaper}3项集支持度{Bread,Milk,Diaper}31-项集2-项集3-项集暴力法:枚举所有项集(直到3-项集)，将产生C61+C62+C63=41个候选Apriori原理:仅产生6+6+1=13个候选TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,Coke指定支持度阈值=60%(最小支持度计数=3)Apriori算法(生成频繁项集)示例2交易号项集合T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3交易数据库Apriori算法(生成频繁项集)示例2项集支持度｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2扫描D，对每个候选计数交易号项集合T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3指定最小支持度为2所有候选支持度都=2，因此没有项需要剪去(后剪枝)C1F1Apriori算法(生成频繁项集)示例2项集支持度｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2F1项集｛I1，I2｝｛I1，I3｝｛I1，I4｝｛I1，I5｝｛I2，I3｝｛I2，I4｝｛I2，I5｝｛I3，I4｝｛I3，I5｝｛I4，I5｝由F1产生候选C2C2Apriori算法(生成频繁项集)示例2项集支持度｛I1，I2｝4｛I1，I3｝4｛I1，I4｝1｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2｛I3，I4｝0｛I3，I5｝1｛I4，I5｝0项集支持度｛I1，I2｝4｛I1，I3｝4｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2C2F2比较候选支持度计数与最小支持度计数扫描D，对每个候选计数Apriori算法(生成频繁项集)示例2项集支持度｛I1，I2｝4｛I1，I3｝4｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2F2项集{I1,I2,I3}{I1,I2,I5}{I1,I3,I5}{I2,I3,I4}{I2,I3,I5}{I2,I4,I5}C3由F2产生候选C3根据Apriori原理进行预剪枝：{I3,I5}不在F2中，因此{I1,I3,I5}一定是非频繁的，剪去{I3,I4}不在F2中，因此剪去{I2,I3,I4}{I3,I5}不在F2中，因此剪去{I2,I3,I5}{I4,I5}不在F2中，因此剪去{I2,I4,I5}Apriori算法(生成频繁项集)示例2项集支持度{I1,I2,I3}2{I1,I2,I5}2C3扫描D，对每个候选计数比较候选支持度计数与最小支持度计数项集支持度{I1,I2,I3}2{I1,I2,I5}2F3项集{I1,I2,I