文档介绍：Apriori算法研究Apriori算法是一个挖掘关联规则的算法,是Agrawal等设计的一个基本算法。它采用两阶段挖掘的思想,并且基于多次扫描事务数据库来执行。关联规则基本概念关联规则是形如X→Y的蕴涵式,表示通过X可以推导“得到”Y,其中X和Y分别称为关联规则的先导(antecedent或left-hand-side,LHS)和后继(consequent或right-hand-side,RHS)。关联规则A->B的支持度support=P(AB),指的是事件A和事件B同时发生的概率。置信度confidence=P(B|A)=P(AB)/P(A),指的是发生事件A的基础上发生事件B的概率。同时满足最小支持度阈值和最小置信度阈值的规则称为强规则。如果事件A中包含k个元素,那么称这个事件A为k项集,并且事件A满足最小支持度阈值的事件称为频繁k项集。挖掘过程第一,找出所有的频繁项集;其目标是发现满足最小支持度阈值的所有项集,这些项集称作频繁项集。第二,由频繁项集产生强规则。其目标是从上一步发现的频繁项集中提取所有高置信度的规则,这些规则称为强规则。通常,频繁项集产生的计算开销远大于产生规则所需的计算开销。Apriori算法思想Apriori算法使用频繁项集的先验知识,使用一种称作逐层搜索的迭代方法,k项集用于探索(k+1)项集。首先,通过扫描事务(交易)记录,找出所有的频繁1项集,该集合记做L1,然后利用L1找频繁2项集的集合L2,L2找L3,如此下去,直到不能再找到任何频繁k项集。最后再在所有的频繁集中找出强规则,即产生用户感兴趣的关联规则。其中,Apriori算法具有这样一条性质:任一频繁项集的所有非空子集也必须是频繁的。因为假如P(I)<最小支持度阈值,当有元素A添加到I中时,结果项集(A∩I)不可能比I出现次数更多。因此A∩I也不是频繁的。该算法的基本思想是:首先找出所有的频集,这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则,这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则,产生只包含集合的项的所有规则,其中每一条规则的右部只有一项,这里采用的是中规则的定义。一旦这些规则被生成,那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集,使用了递归的方法。Apriori算法步骤Apriori算法的设计可以分解为两步骤来执行挖掘:挖掘所有频繁项集从事务数据库(D)中挖掘出所有频繁项集。支持度大于最小支持度minSup的项集(Itemset)称为频集(FrequentItemset)。首先需要挖掘出频繁1-项集;然后,继续采用递推的方式来挖掘频繁k-项集(k>1),具体做法是:在挖掘出候选频繁k-项集(Ck)之后,根据最小置信度minSup来筛选,得到频繁k-项集。最后合并全部的频繁k-项集(k>0)。挖掘频繁项集的算法描述如下:算法Apriori算法的频繁集产生L1=find_frequent_1-itemsets(D);//挖掘频繁1-项集,比较容易for(k=2;Lk-1≠Φ;k++){Ck=apriori_gen(Lk-1,min_sup);//调用apriori_gen方法生成候选频繁k-项集foreachtransactiont∈D{//扫描事务数据库DCt=subse