开发者学堂课程【高校精品课-北京理工大学-数据仓库与数据挖掘（上）：基础概念】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/921/detail/15634
基础概念
关联规则挖掘是数据挖掘的重要组成内容。
在这一部分中，我们将向大家介绍关联规则挖掘的基本概念、频繁项集的产生、规则的产生、影响 apriori 算法计算复杂度的因素、频繁项集的压缩表示以及关联模式评估六个方面的内容。首先我们来看一下关联规则挖掘的基本概念。
关联规则挖掘就是我们利用给定的一组事物数据集。我们把它称之为叫做 transaction。根据这样的事物数据集，我们去挖掘一些规则，这些规则可以根据已发生的项目去预测还有哪些项目会发生。
首先我们来看一下在关联规则挖掘中所使用的事务数据。我们的 PPT 上展示了一个大家比较熟悉的购物篮事务数据。在这种事物数据集中，每一行代表的是顾客的一次购物记录，我们称之为一个 transaction，每一个 transaction事务由两部分组成。一部分指的是这个事务的 id,用于唯一地标识这个事务。第二部分指的是这个事物的项集。在我们的购物篮事务集中。每一个事物的项集代表的是在这次购物中顾客所购买的商品的项数。关联规则的形式就是行为由尿布推出啤酒。由牛奶面包推出鸡蛋、可乐油，由啤酒、面包，推出牛奶这样的规则。我们以尿布啤酒这个规则为例。
它的含义就是如果再一次购物中用户购买了尿布，那么在这次购物中用户还有可能购买啤酒。对于这样的关联规则，它蕴含的是项和项之间的关联关系。也就是项和项在一次事故中共同可能出现的频率比较高。
大家在学习关联规则挖掘的基本概念的时候，有一个地方需要注意。就是对于我们的关联规则，它蕴含的是项和项之间的关联关系。而没有蕴含项和项之间的因果关系。
我们刚才给大家介绍由尿布推出啤酒。它的含义是，如果顾客购买的尿布，他还有可能购买啤酒。
对于这种关联规则，它蕴含的这种关联关系并没有蕴含，因为这个顾客购买的尿布，所以这个顾客才购买啤酒。他没有蕴含这样的一种因果关系，这个是大家在学习关联规则，挖掘基本概念的时候需要特别注意的。
我们再来看一下项集。项集就指的是由一个或多个相组成的集合。比如在我们购物篮事务数据集中，我们的项指的是所有商品的名称。项集就是如牛奶、面包、啤酒这样的集合。K项集就指的是由K个项组成的项集。
对于项集来说，有一个度量指标，称之为支持度计数，就指的是这个项集它发生的次数，也就等于包含这个项集的事物的数目，比如在购物篮事物数据集包含牛奶、面包、尿布，他的支持度计数等于二，也就是我们有两条事物包含了牛奶、面包、尿布这样的一个项集。
项集的支持度指的是包含这个项集的事物的数目占全体事务数目的比率，比如我们的牛奶、面包、尿布这个项集。他的支持度计数就是包含这个三项集的事物的数目是2。我们整体事务集中有五个事物，所以它的支持度就是2/5。
频繁项集指的是我们事先设定一个最小支持度阈值。如果项集的支持度大于或等于这个支持度阈值，我们就只这个项集是频繁项集。频繁项集往往指的是在事故中出现频率比较高的项集。
我们再来看一下关联规则，关联规则就指的是形如由 X 推出 Y 这样的蕴涵表达式。其中 XY 是互不相交的项集，我们把箭头前面的这个项集 X 称之为叫做规则的前件，把箭头后面的这个项集 Y 称之为叫做规则的后件。
比如，我们可以从我们的购物男士勿数据中去挖掘得到一条规则，牛奶尿布推出啤酒。
对于关联规则有两个度量指标，一个是支持度，一个是置信度。这里关联规则的支持度指的是由关联规则前件X和后见 Y，两个项集组成的并集这个项集的支持度。对于关联规则的自信度。它的含义指的是包含 X 项集的事物中，外项集出现的概率。
下面通过一个例子向大家来介绍这两个指标的计算方法，比如依然是由五个事物组成的事物数据集。从这数据中，我们可以挖掘得到一条关联规则，也就是由牛奶尿布推出啤酒。
对于这样的一个规则，他的支持度是等于前件和后件并集所组成的这个项集，牛奶、尿布、啤酒的支持度。包含牛奶、尿布、啤酒的所有的事物总共有两个，那么它的支持度就是2/5等于0.4。对于这个规则，他的置信度指的是在包含牛奶、尿裤的食物中，啤酒这个项出现的概率。我们可以用橡皮、牛奶、面包、啤酒的支持度计数。除以牛奶尿布的支持度计数，等于2/3。
我们再来看一下关联规则挖掘的任务，关联规则挖掘的任务就指的是我们根据给定的事物数据集。
去挖掘那些支持度大于等于最小支持度阈值，置信度大于等于最小置信度阈值的规则，我们把这样的关联规则称之为强关联规则。通过我们设置的支持度，我们可以过滤到关联规则中一些没有意义的规则。如果一个规则他的支持度比较低，就意味着这个规则出现在我们事务中的概率比较低。比如说，如果在顾客的购物记录，比如说像尿布和啤酒出现的次数很低，那么就没有必要把尿布和啤酒放在一起进行促销。规则的自信度可以增强关联规则推理的可靠性。如果一个规则他的置信度比较高，就意味着有这个规则的前件，推出这个规则后进的可靠性比较高。通过设置这样的两个度量，我们就可以得到一些比较强的关联规则。
刚才我们通过介绍关联规则挖掘的概念，我们很自然的就会想到进行关联规则挖掘的方法。那么一种最直接的方法就是暴力搜索法。
对于暴力搜索法来说，它的步骤只要包含三步，
第一步，我们首先列出所有可能的关联规则。
第二步，我们去计算每一条可能关联规则的支持度和自信度。
第三点，我们就可以利用最小支持度和最小置信度阈值对这些规则进行过滤，最后得到我们想要的强关联规则。
但是这种暴力搜索法在实际中是不能够直接运用的，主要原因就是因为它的计算复杂度太高。
我们来看一下，假设我们的事物数据集是由 D 项组成。那么我们相集的个数是二的 D 次方，而我们规则的项数可能是三的D次方减去二的D次方加一再加一，就是说我们的规则的数目和我们项数之间是呈指数增长的，当我们的项数等于六的时候，我们的规则就可以达到602个。那么对于这么巨大的规则数，我们是不可能一一去计算它的支持度和自信度的。
我们来看一下对于这种情况该怎么处理。我们首先观察一下在我们事务数据集中和牛奶、尿布、啤酒这个三项相关的所有的关联规则。从这些关联规则中我们可以得到两点发现，第一个就是这些规则他所有的支持度都是一致的，都是等于我们项集牛奶、尿布和啤酒这个项集的支持度，但是他们的置信度不一样。第二点就是所有的这些规则都可以通过对项集牛奶尿布、啤酒进行二划分得到。
基于这个考虑，那我们可以把我们关联规则的挖掘步骤分为两步走，第一步，就是我们从所有的事物数据集中挖掘到所有的频繁项集。
第二步，就是根据频繁项集去产生我们的规则。
如果我们的项集是频繁项集，那么由这些频繁项集得到的所得的规则，他的支持度肯定是满足我们支持度要求的，所以我们首先去得到满足我们支持度计数的这样的一些规则，然后第二步，再利用我们的置信度对我们的项集进行二划分得到规则，再利用自信度进行过滤，得到我们的强关联规则。
