关联规则

关联规则:基本概念和算法1定义:关联分析（associationanalysis）关联分析用于发现隐藏在大型数据集中有意义的联系，所发现的模式通常用关联规则或频繁项集的形式表示。除购物篮数据以外，关联分析可以应用于生物信息学、医疗诊断、网页挖掘、科学数据分析等TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,CokeRulesDiscovered:{Diaper}--{Beer}定义:频繁项集（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）TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,CokeExample: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的事务中出现的频繁程度MiningAssociationRulesObservations:都源于同一个项集:{Milk,Diaper,Beer}相同的支持度，不同的置信度TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,CokeExampleofRules:{Milk,Diaper}{Beer}(s=0.4,c=0.67){Milk,Beer}{Diaper}(s=0.4,c=1.0){Diaper,Beer}{Milk}(s=0.4,c=0.67){Beer}{Milk,Diaper}(s=0.4,c=0.67){Diaper}{Milk,Beer}(s=0.4,c=0.5){Milk}{Diaper,Beer}(s=0.4,c=0.5)关联规则挖掘问题关联规则挖掘问题：给定事务的集合T,关联规则发现是指找出支持度大于等于minsup，并且置信度大于等于minconf的所有规则（其中，minsup和minconf是对应的支持度和置信度阈值）挖掘关联规则的一种原始方法是：Brute-forceapproach:计算每个可能规则的支持度和置信度这种方法计算代价过高，因为可以从数据集提取的规则的数量达指数级从包含d个项的数据集提取的可能规则的总数R=3d-2d+1+1，如果d等于6，则R=602挖掘关联规则（MiningAssociationRules）大多数关联规则挖掘算法通常采用的一种策略是，将关联规则挖掘任务分解为如下两个主要的子任务:1.频繁项集产生（FrequentItemsetGeneration）–其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集。2.规则的产生（RuleGeneration）–其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则（strongrule）。2频繁项集产生（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)替代将每个候选项集与每个事务相匹配，可以使用更高级的数据结构，或存储候选项集或压缩数据集，来减少比较次数2.1先验原理（Aprioriprinciple）先验原理:如果一个项集是频繁的，则它的所有子集一定也是频繁的相反，如果一个项集是非频繁的，则它的所有超集也一定是非频繁的:这种基于支持度度量修剪指数搜索空间的策略称为基于支持度的剪枝（support-basedpruning）这种剪枝策略依赖于支持度度量的一个关键性质，即一个项集的支持度决不会超过它的子集的支持度。这个性质也称为支持度度量的反单调性（anti-monotone）。非频繁项集nullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDE例子：如果{A,B}是非频繁的nullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDE被剪枝的超集2.2Apriori算法的频繁项集产生TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,CokeApriori算法的频繁项集产生ItemCountBread4Coke2Milk4Beer3Diaper4Eggs1ItemsetCount{Bread,Milk}3{Bread,Beer}2{Bread,Diaper}3{Milk,Beer}2{Milk,Diaper}3{Beer,Diaper}3ItemsetCount{Bread,Milk,Diaper}3Items(1-itemsets)Pairs(2-itemsets)Triplets(3-itemsets)支持度阈值=60%最小支持度计数=3枚举所有项集将产生个候选而使用先验原理，将较少为6+6+1=1341362616CCCApriori算法Apriori算法Apriori算法的频繁项集产生的部分有两个重要的特点：它是一个逐层算法。即从频繁1-项集到最长的频繁项集，它每次遍历项集格中的一层它使用产生-测试策略来发现频繁项集。在每次迭代，新的候选项集由前一次迭代发现的频繁项集产生，然后对每个候选的支持度进行计数，并与最小支持度阈值进行比较。该算法需要的总迭代次数是kmax+1，其中kmax是频繁项集的最大长度2.3候选的产生与剪枝(构造apriori-gen函数)（1）蛮力方法蛮力方法把所有的k-项集都看作可能的候选，然后使用候选剪枝除去不必要的候选第k层产生的候选项集的数目为虽然候选产生是相当简单的，但是候选剪枝的开销极大，因为必须考察的项集数量太大。设每一个候选项集所需的计算量为O(k)，这种方法的总复杂度为dkdkddOkCO11)2()(kdC注意避免产生太多不必要的候选不必要的候选:至少有一个子集是非频繁的确保候选项集的集合是完全的不遗漏任何可能的频繁项集不重复产生候选项集{a,b,c,d}可能会通过多种方法产生:合并{a,b,c}和{d}，合并{b,d}和{a,c}，合并{c}和{a,b,d}1819蛮力方法:把所有的k-项集都看作可能的候选，然后使用候选剪枝除去不必要的候选项啤酒面包可乐尿布牛奶鸡蛋候选产生项集{啤酒，面包，可乐}{啤酒，面包，尿布}{啤酒，面包，牛奶}{啤酒，面包，鸡蛋}{啤酒，可乐，尿布}{啤酒，可乐，牛奶}{啤酒，可乐，鸡蛋}{啤酒，尿布，牛奶}{啤酒，尿布，鸡蛋}{啤酒，牛奶，鸡蛋}{面包，可乐，尿布}{面包，可乐，牛奶}{面包，可乐，鸡蛋}{面包，尿布，牛奶}{面包，尿布，鸡蛋}{面包，牛奶，鸡蛋}{可乐，尿布，牛奶}{可乐，尿布，鸡蛋}{可乐，牛奶，鸡蛋}{尿布，牛奶，鸡蛋}候选剪枝项集{面包，尿布，牛奶}3620C20候选产生(2)（2）Fk1F1方法用一个频繁(k1)-项集和一个频繁1-项集构造一个候选,然后剪枝除去不必要的候选频繁2-项集项集{啤酒，尿布}{面包，尿布}{面包，牛奶}{尿布，牛奶}频繁1-项集项啤酒面包尿布牛奶候选产生项集{啤酒，尿布，面包}{啤酒，尿布，牛奶}{面包，尿布，牛奶}{面包，牛奶，啤酒}候选剪枝项集{面包，尿布，牛奶}{啤酒,尿布}+{面包}{面包,尿布}+{啤酒}候选的产生与剪枝这种方法用其他频繁项来扩展每个频繁（k-1）-项集这种方法将产生个候选k-项集，其中|Fj|表示频繁j-项集的个数。这种方法总复杂度是这种方法是完备的，因为每一个频繁k-项集都是由一个频繁（k-1）-项集和一个频繁1-项集组成的。因此，所有的频繁k-项集是这种方法所产生的候选k-项集的一部分。然而，这种方法很难避免重复地产生候选项集。如：{面包，尿布，牛奶}不仅可以由合并项集{面包，尿布}和{牛奶}得到，而且还可以由合并{面包，牛奶}和{尿布}得到，或由合并{尿布，牛奶}和{面包}得到。|)||(|11FFOkkkFFkO|)|||(11方法11FFk候选的产生与剪枝避免产生重复的候选项集的一种方法是确保每个频繁项集中的项以字典序存储，每个频繁（k-1）-项集X只用字典序比X中所有的项都大的频繁项进行扩展如：项集{面包，尿布}可以用项集{牛奶}扩展，因为“牛奶”（milk）在字典序下比“面包”（Bread）和“尿布”（Diapers）都大。尽管这种方法比蛮力方法有明显改进，但是仍然产生大量不必要的候选。例如，通过合并{啤酒，尿布}和{牛奶}而得到的候选是不必要的。因为它的子集{啤酒，牛奶}是非频繁的。23候选产生(3)（3）Fk1Fk1方法令A={a1,a2,...,ak1}和B={b1,b2,...,bk1}是一对频繁(k1)-项集，合并A和B，如果它们满足如下条件：ai=bi(i=1,2,...,k2)并且ak1bk1频繁2-项集项集{啤酒，尿布}{面包，尿布}{面包，牛奶}{尿布，牛奶}频繁2-项集项集{啤酒，尿布}{面包，尿布}{面包，牛奶}{尿布，牛奶}候选产生项集{面包，尿布，牛奶}候选剪枝项集{面包，尿布，牛奶}候选的产生与剪枝这种方法