关联分析基本概念与算法VIP免费

关联分析:基本概念和算法第6章关联分析:基本概念和算法定义:关联分析（associationanalysis）关联分析用于发现隐藏在大型数据集中的令人感兴趣的联系，所发现的模式通常用关联规则或频繁项集的形式表示。关联分析可以应用于生物信息学、医疗诊断、网页挖掘、科学数据分析等RulesDiscovered:{Diaper}-->{Beer}RulesDiscovered:{Diaper}-->{Beer}TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,Coke定义:频繁项集（FrequentItemset）项集（Itemset）–包含0个或多个项的集合例子:{Milk,Bread,Diaper}–k-项集如果一个项集包含k个项支持度计数（Supportcount）()–包含特定项集的事务个数–例如：({Milk,Bread,Diaper})=2支持度（Support）–包含项集的事务数与总事务数的比值–例如：s({Milk,Bread,Diaper})=2/5频繁项集（FrequentItemset）–满足最小支持度阈值（minsup）的所有项集TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,Coke定义:关联规则（AssociationRule）Example:Beer}Diaper,Milk{4.052|T|)BeerDiaper,,Milk(s67.032)Diaper,Milk()BeerDiaper,Milk,(c关联规则–关联规则是形如XY的蕴含表达式,其中X和Y是不相交的项集–例子:{Milk,Diaper}{Beer}关联规则的强度–支持度Support(s)确定项集的频繁程度–置信度Confidence(c)确定Y在包含X的事务中出现的频繁程度TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,Coke关联规则挖掘问题关联规则挖掘问题：给定事务的集合T,关联规则发现是指找出支持度大于等于minsup并且置信度大于等于minconf的所有规则,minsup和minconf是对应的支持度和置信度阈值挖掘关联规则的一种原始方法是：Brute-forceapproach:–计算每个可能规则的支持度和置信度–这种方法计算代价过高，因为可以从数据集提取的规则的数量达指数级–从包含d个项的数据集提取的可能规则的总数R=3d-2d+1+1，如果d等于6，则R=602挖掘关联规则（MiningAssociationRules）大多数关联规则挖掘算法通常采用的一种策略是，将关联规则挖掘任务分解为如下两个主要的子任务:1.频繁项集产生（FrequentItemsetGeneration）–其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集。2.规则的产生（RuleGeneration）–其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则（strongrule）。频繁项集产生（FrequentItemsetGeneration）nullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDE格结构（latticestructure）频繁项集产生（FrequentItemsetGeneration）Brute-force方法:–把格结构中每个项集作为候选项集–将每个候选项集和每个事务进行比较，确定每个候选项集的支持度计数。–时间复杂度~O(NMw)，这种方法的开销可能非常大。TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,CokeNTransactionsListofCandidatesMw降低产生频繁项集计算复杂度的方法减少候选项集的数量(M)–先验(apriori)原理减少比较的次数(NM)–替代将每个候选项集与每个事务相匹配，可以使用更高级的数据结构，或存储候选项集或压缩数据集，来减少比较次数先验原理（Aprioriprinciple）先验原理:–如果一个项集是频繁的，则它的所有子集一定也是频繁的相反，如果一个项集是非频繁的，则它的所有超集也一定是非频繁的:–这种基于支持度度量修剪指数搜索空间的策略称为基于支持度的剪枝（support-basedpruning）–这种剪枝策略依赖于支持度度量的一个关键性质，即一个项集的支持度决不会超过它的子集的支持度。这个性质也称为支持度度量的反单调性（anti-monotone）。非频繁项集nullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDE例子nullABACADAEBCBDBECDCEDEAB...