资源描述：
《第6章关联分析_(定稿)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、CVipinKumar,ParallelIssuesinDataMining,VECPAR2002CVipinKumar,ParallelIssuesinDataMining,VECPAR2002关联分析v/B＞:基本概念和算法定义:关联分析＜/B＞(associationanalysis)关联分析＜/B＞用于发现隐藏在大型数据集中的令人感兴趣的联系，所发现的模式通常用关联规则或频繁项集的形式农示。关联分析v/B＞可以应用于生物信息学、医疗诊断、网页挖掘、科学数据分析＜/B＞等定义：频繁项集(FrequentItemset)项集(Itemset)包含0个或多个项的集
2、合例子：Milk,Bread,Diaperk•项集如果一-个项集包含k个项支持度计数(Supportcount)?包含特定项集的事务个数例如：？Milk,Bread,Diaper2支持度(Support)包含项集的事务数与总事务数的比值例如：sMilk,Bread,Diaper2/5频繁项集(FrequentItemset)满足最小支持度阈值(minsup)的所有项集定义：关联规则(AssociationRule)关联规则挖掘问题关联规则挖掘问题：给定事务的集合T,关联规则发现是指找出支持度大于等于minsup并月.置信度大J：等minconf的所冇规则,minsu
3、p和minconf是对应的支持度和置信度阈值挖掘关联规则的一•种原始方法是：Brute-forceapproach:计算每个可能规则的支持度和置信度这种方法计算代价过高，因为可以从数据集提取的规则的数量达指数级从包含d个项的数据集提取的可能规则的总数R3d-2d+l+l,如果d等于6,则R602挖掘关联规则(MiningAssociationRules)大多数关联规则挖掘算法通常采用的一种策略是，将关联规则挖掘任务分解为如下两个主要的子任务：频繁项集产生(FrequentItemsetGeneration)其廿标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项
4、集。规则的产生(RuleGeneration)其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则(strongrule)。频繁项集产牛(FrequentItemsetGeneration)频繁项集产生(FrequentItemsetGeneration)Brute-force方法：把格结构屮每个项集作为候选项集将每个候选项集和每个事务进行比较，确定每个候选项集的支持度计数。时间复杂度-ONMw，这种方法的开销可能非常大。降低产生频繁项集计算复朵度的方法减少候选项集的数量M先验apriori原理减少比较的次数NM替代将每个候选项集与每个事务相匹
5、配，可以使用更高级的数据结构，或存储候选项集或压缩数据集，来减少比较次数先验原理(Aprioriprinciple)先验原理：如果一个项集是频繁的，则它的所有子集一定也是频繁的相反，如果一个项集是非频繁的，则它的所有超集也一定是非频繁的：这种基于支持度度量修剪指数搜索空间的策略称为基于支持度的剪枝(support-basedpruning)这种剪枝策略依赖于支持度度量的一个关键性质，即一个项集的支持度决不会超过它的子集的支持度。这个性质也称为支持度度量的反单调性(anti-monotone)oApriori算法的频繁项集产生Apriori算法的频繁项集产生Aprio
6、ri算法Apriori算法Apriori算法的频繁项集产生的部分有两个重耍的特点：它是一个逐层算法。即从频繁1•项集到最长的频繁项集，它每次遍历项集格中的一层它使用产生■测试策略來发现频繁项集。在每次迭代，新的候选项集由前一次迭代发现的频繁项集产生，然后对每个候选的支持度进行计数，并与最小支持度阈值进行比较。该算法需耍的总迭代次数是kmax+1,其中kmax是频繁项集的最大长度候选的产生与剪枝构造apriori-gen函数蛮力方法蛮力方法把所有的k・项集都看作可能的候选，然后使用候选剪枝除去不必要的候选第k层产生的候选项集的数口为虽然候选产生是相当简单-的，但是候选
7、剪枝的开销极大，因为必须考察的项集数量太大。设每一个候选项集所需的计算量为0(k),这种方法的总复杂度为候选的产生与剪枝候选的产生与剪枝这种方法用其他频繁项来扩展每个频繁(k・l)■项集这种方法将产生个候选k・项集，其中
8、Fj
9、表示频繁卜项集的个数。这种方法总复杂度是这种方法是完全的，因为每一个频繁k-项集都是由一个频繁(k・l)■项集和一个频繁1■项集组成的。因此，所有的频繁k■项集是这种方法所产生的候选k■项集的一部分。然而，这种方法很难避免重复地产生候选项集。女口：面包，尿布，牛奶不仅可以由合并项集面包，尿布和牛奶得到，而且还可以由合并面包，牛奶和尿布得到
