《商务智能与数据挖掘》-商务智能05

关联规则挖掘目录2关联分析常用算法3关联规则评价4基本概念1关联规则应用5关联分析（associationanalysis）是一种在大规模数据集中寻找有趣关系的任务，这些关系可以有两种形式：频繁项集（frequentitemset）或者关联规则(associationrule)。1基本概念

在上述交易单中，每一小件商品（如A、C、D）称为项(Item)，每一行交易商品组合（如ABC）称为事务(Transaction)所有的事务构成的集合称之为事务集，在上图中，{ABCD,ABCE,BDEF,BCDE,ACDF,ABC,ABE}称之为一个事务集项集（Itemset）：包含0个或多个项的集合，如{A},{A,B,C},{A,B,D}称为项集K项集表示项集中的元素个数为K，如{A,B,C}就是一个三项集1基本概念频繁项：在多个事务中频繁出现的项就是频繁项。频繁项集：假设有一系列的事务，将这些事务中同时出现的频繁项组成一个子集，且子集满足最小支持度阈值（MinimumSupport），这个集合称为频繁项集。关联规则（associationrules）：描述在一个事务中物品之间同时出现的规律的知识模式，通过量化的形式描述物品A的对物品B的影响。（两种物品之间可能存在很强的关联）

关联规则是形如A→B蕴含的表达式，其中A和B是不相交的项集，A称为规则的前件（antecedent），而B称为规则的后件（consequent）。如{牛奶，尿布}→{啤酒}1基本概念关联规则的度量指标包括支持度和置信度：支持度（Support）：包含项集的事务数与总事务数的比值，对某一特定项集{X，Y}，计算公式：如商品{A，B}在交易集合中同时出现的概率，支持度表示项集的重要程度（频繁程度）。置信度(Confidence)：一个数据出现后，另一个数据出现的概率，或者说包含X的交易中也包含Y的条件概率。（当一个人已经买了钉子，那么他有多大的可能也会买锤子？），置信度表示关系的可信程度。1基本概念提升度（Lift）：表示含有A的条件下，同时含有B的概率，与B总体发生的概率之比Lift(A—>B)=P(B/A)/P(B)=Confidence(A—>B)/P(B)提升度表示先购买A对购买B的概率的提升作用，用来判断规则是否有实际价值，即使用关联规则后商品在购物车中出现的次数是否高于商品单独出现在购物车中的频率。如果大于1说明规则有效，小于1则无效。2关联规则挖掘关联规则挖掘的过程主要包含两个阶段：第一阶段从资料集合中找出所有的频繁项集，即项集的支持度均大于等于最小支持度阈值；第二阶段从频繁项中产生关联规则（AssociationRules）。关联规则挖掘过程

以一个包含A与B两个项的2-itemset为例，可以求得包含{A，B}项集的支持度，若支持度大于等于所设定的最小支持度（MinimumSupport）阈值时，则{A，B}称为频繁项集。一个满足最小支持度的k-itemset，则称为k-频繁项集（Frequentk-itemset），一般表示为Largek或Frequentk。接下来，算法从Largek的项组中再产生Largek+1，直到无法再找到更长的频繁项集为止。经由频繁k-项集{A，B}所产生的规则A->B，求得其置信度，若信赖度大于等于最小置信度，则称A->B为关联规则。案例2关联规则挖掘在从数据中挖掘出所有的频繁项集后，就可以获得相应的关联规则，也就是要产生满足最小支持度和最小信任度的强关联规则。关联规则挖掘算法就是从事务数据库、关系数据库或其他信息存储的大量数据的项集之间发现频繁出现的模式、关联和相关性。典型的关联分析的算法包括Apriori算法、FP-Growth（FrequentpatternGrowth，频繁模式增长树）算法、FreeSpan算法及Prefixspan算法等。3关联分析常用算法Apriori算法是第一个关联规则挖掘算法，它开创性地使用基于支持度的剪枝技术，系统地控制候选项集指数增长。3关联分析常用算法Apriori算法思想：先确定候选的所有可能项（即1项集）以及相应的支持度，识别并保留所有高于支持度的1项集，得到频繁1项集。然后，对剩下的频繁1项集进行连接，得到候选的频繁2项集，再次识别并保留高于支持度的候选频繁2项集，得到真正的频繁二项集，以此类推，进行迭代，直到无法找到频繁k+1项集为止，对应的频繁k项集的集合即为算法的输出结果。然后，再利用找到的频繁项集与预先设定的最小置信度的阈值生成强关联规则。3关联分析常用算法Apriori算法具体步骤：初始通过单遍扫描数据集，确定每个项的支持度，得到所有频繁1-项集的集合F1（单个项的，例如{A}和{D}）迭代地使用上一步得到的k-1项集，产生新的候选k项集。为了对候选项的支持度计数，算法需要再次扫描一遍数据集。计算候选项的支持度，删除支持度小于最小支持度的左右候选集。当没有新的频繁项集产生，算法结束。Apriori算法是一个采用候选消除的算法，每一次消除都需要扫描一次所有数据记录，这导致该算法在面临大数据集时效率低下。为了解决该问题，一个新的关联规则挖掘算法FP-Growth被提出。3关联分析常用算法FP-Growth算法思想：把数据集中的事务映射到一棵FP-tree上面，再根据这棵树找出频繁项集。FP-Growth算法被用于挖掘频繁项集，将数据集存储为FP树的数据结构，以更高效地发现频繁项集或频繁项对。相比于Apriori算法对每个潜在的频繁项集都扫描数据集，判定是否满足支持度，FP-Growth算法只需要对数据库进行两次遍历，就可以高效发现频繁项集，因此，它在大数据集上的速度要优于Apriori算法。3关联分析常用算法FP-Growth算法步骤FP-Growth算法的步骤，大体上可以分成两步：一、FP-tree的构建；二、在FP-Tree上挖掘频繁项集。具体看：（1）扫描第一遍数据库，找出频繁项；（2）将记录（事务）按照频繁项集的支持度由大到小顺序重新排列；（3）扫描第二遍数据库，产生FP-tree；（4）从FP-tree挖掘得到频繁项集。4关联规则评价客观标准

通过统计论据可以建立客观度量的标准，其中涉及相互独立的项或覆盖少量事务的模式被认为是不令人感兴趣的，因为其可能反映数据中的伪联系。利用客观统计论据评价模式时，一般通过计算模式的客观兴趣度来度量，而这样的度量一般是基于相依表（contingencytable）。常见的评价方法有以下几种：提升度与兴趣因子进行度量相关分析进行度量IS度量4关联规则评价主观标准通过主观论据可以建立主观度量的标准。如果一个规则不能揭示料想不到的信息或提供导致有益的行动的有用信息，则主观认为该规则是无趣的。在评估关联规则时，将主观信息加入到规则的评价中是一件比较困难的事情，因为这需要来自相关领域专家的大量先验信息作为支持。常见的将主观信息加入到规则发现任务的方法有以下几种：可视化（visualization）这种方法需要友好的环境，保持用户参与，允许领域专家解释和检验被发现的模式，与数据挖掘系统交互。基于模板的方法(template-basedapproach)这种方法允许用户限制挖掘算法提取的模式类型。只把满足用户指定的模板的规则提供给用户，而不是报告提取所有模式。主观兴趣度度量(subjectiveinterestingnessmeasure)主观度最可以基于领域信息来定义，如概念分层或商品利润等。然后，使用这些度量来过滤