开发者学堂课程【高校精品课-北京理工大学-数据仓库与数据挖掘（上）：频繁项集的产生】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/921/detail/15635
频繁项集的产生
频繁项集的产生在上一节的内容中，我们向大家介绍了关联规则挖掘的两步走策略，其中第一步就是首先产生频繁项集。我们首先来看一下频繁项集它的产生空间，
这个 PPT上展示的是由 ABCDE5 个项所组成的项集空间，那么这个项集空间包括意向及二项集、三项集、四项集，一直到五项集，那么总共的个数是二的五次方。
我们产生频繁项集的一个最直接的方法依然是暴力搜索法，也就是我们列出所有可能的频繁项集，然后对每一个可能的频繁项集去扫描数据库，利用事物去更新我们的频繁项集的支持度计数。对于这样的一种暴力搜索法，我们的算法复杂度是大 O 的 N 乘 M 乘以 W，其中 N 指的是我们事务数据集的数目，就是包含多少个数。M 指的是我们的候选频繁项集的个数。W 指的是事物的平均宽度，也就是平均一个事物包含项目地的数目。对于这样的一种暴力搜索法，它的计算复杂度是非常高的，其原因就是在于我们的 M，它的数量集非常大，等于二的 D 次方。那么对于这样的暴力搜索法，我们的计算复杂度很高。
怎么样去优化我们的算法？
我们有三种策略，其中有一种策略就是减少我们的候选频繁项集的数目，也就是减少 M 的数目，第二种策略呢就是减少我们四五级数据库中事务的数目，第三种策略是减少我们比较的次数，就是减少 N 乘 M 的数。
我们今天向大家主要是介绍 apriori 算法，在 apriori 算法中，它采用的是第一种策略，就是根据我们的一些先验原理去减少我们的候选频繁项集的空间。
首先来了解一下先验原理，先验原理指的是如果一个项集是频繁的。那他所有的子集也一定是频繁的。先验原理主要是根据支持度计数的计算方式得到的，那么也就是根据支持度计算方法，我们可以知道一个项集，他的支持度是不会超过他的子集的支持度。我们把这样的一种支持度的性质称之为他的反单调性。利用这种支持度的返单调性，我们就可以过滤掉一些非频繁项集。
这个展示的是由 ABCDE 5个项所构成的可能频繁项集的空间。那假设 AB 这个项集它是非频繁的，那么包含它的所有的项集肯定是非频繁的。这是因为它的超级的支持度是不会超过 ABI 这个子集的支持度，因为 AB 的子集这个支持度是低于最小支持度阈值的，因为它是非频繁的，所以那他所有超级的支持度肯定是低于最小支持度阈值的。那因此包含 AB 这个项集的所有超级一定是非频繁的。
利用这样的一种性质，我们就可以把这样的一些项集，在计算支持度之前就把它过滤掉，从而缩小了我们可能频繁相机的空间。我们这里举一个例子，给大家展示利用先验原理去过滤非频繁相机的一些作用。比如这个是大家熟悉的由五个事物构成的购物篮事务数据集。假设我们设定最小支持度阈值是五分之三，那我们首先统计每一个像他的支持度计数，如果我们使用暴力搜索法，我们可能的频繁项集的个数就是c六的一次方加c的二次方加c六的三次方，那么最后是等于四十一个，因为它一共是有六项组成，
如果我们使用我们的先验原理进行过滤的话，比如我们在得到所有一项集的项集的基础上，我们计算他的支持度，然后通过支持度的阈值，我们可以过滤掉一些不频繁的阈项值，然后剩下了四个频繁的阈项值，那么这个时候我的频繁项集的空间就是c六取一加c四取二加c四取三，那么就是等于十六个，也就是说我首先得到可能的频繁项集，然后再得到可能的频繁二项集，在此基础之上，我再得到可能的频繁三项，通过我们的经验原理可以极大地缩小我们的可能频繁项集的空间，
再举了下面的例子之后我们对我们的 opera ori 算法中产生频繁项集的算法做一个描述，我们用 f k 代表我们频繁的k项集，用 l k 代表候选的 k 项集，那我们的算法的过程是首先我们设置k等于一，然后从我们的事务数据集中产生所有的频繁一项集，在得到频繁项集的基础之上，重复以下步骤，直到得到所有的频繁项集，那么这些步骤主要包含四部，第一个就是候选项集的产生，我们首先通过频繁的k项集产生我们可能的k加一项集，然后使用先验原理对我们 K加一项及进行过滤，也就是如果 K 加一项集中包含不频繁的 K 项集，那么这个 K 项集它一定是不频繁的。
再利用先验原理经过过滤之后，我们就对每一个可能的频繁项集进行支持度计算。通过扫描我们的事务数据库，得到每一个频繁项集的支持度。第四步就是利用我们的支持度阈值对我们的候选频繁项集进行过滤，最终得到频繁的K加一项集。
在我们 of RI ori 算法进行评。频繁项集挖掘的过程中，有一个重要的环节，就是通过 K 项集怎么样得到候选的K加一项。在 opera ori 算法中，有两种方式，一种是可以利用我们频繁的 K 减一项集和频繁的意向及进行自连接。
得到我们可能的候选 K 项，那么第二种方式就是通过频繁的 K 减一项及进行自连接得到候选的 K 项。那么利用 K 点项集及进行自链接得到 K 项集的方法主要是，我们如果这个 K 减一项集他的前K减二项和另外一条 K 减一项集的前 K 减二项一样的话，我们可以把这 两个项目进行合。从而得到一条 K 加一项集。
比如说我们举一个例子，我们这里有一个频繁三项集的集合，里面包含了ABC ABD ACD BCD BDE和CDE，那么我们可以对其中的 ABC 和 ABD 进行合并，得到 ABCD。对 ABC 和 ABE 进行合并得到 ABCE，对 ABD 和 ADE 进行合并得到ABDE。这是因为这些向它的前两项都是一致的。但是对于我们的项集 ABD 和 ACD，它就不能进行合并，因为他的前两项并不一样。在 apriori 算法中，主要是通过这种方法，也就是通过K减一项集的自连接来得到候选集的。在得到候选集的基础之上，我们要对这些候选集利用先验原理进行过滤。比如我们刚才利用频繁三项集的集合 F3 得到了我们的候选四项 ABCD ABCD 和 aABDE。
但是我们可以发现，对于我们的 ABCE 这个项集来说，它的子集 ACE 和 BCE是 不频繁的。
所以 ABC 这个，项集它一定是不频繁的，对于我们的项集 ABD，因为它的子集 ADE 是不频繁的，所以对于项集ABDE 他也一定是不频繁的。那么通过这样的一些先验原理进行过滤之后，我们最后得到最终的候选四项集就只剩下ABCD，
那我们还是通过我们的购物篮事务局向大家展示关联规则中频繁项集的产生，那我们首先得到了频繁的一项集，然后利用平台的一项集进行至连接，得到我们的候选二项集。
在对候选二项集利用最小支持度计数进行过滤得到最终的候选二项集。
得到候选二项集的基础之上，我们再通过自连接得到我们的候选三项集，在利用我们的先验原理和支持度计数进行过滤之后，得到最终的三项集，这个就是在 apriori 算法中如何频繁数据挖掘的，
这里通过一个比较完整的例子向大家展示。那么在这个例子中，我们一共是有九条记录，那么它的项数一共是有I1 I2 I3 I4和I5一共是五项。我们设最小的支持度阈值是2，也是2/9。
首先第一步，我们对每一个一项集进行支持度计数，根据最小支持度阈值，经过筛选得到我们的频繁的一项集，再利用频繁的意向及进行自连接，得到候选的二项集。这个时候我们可以直接利用支持度进行过滤，得到我们候选的二项集，之后利用我们的最小支持度计数进行过滤，得到我们频繁的二项集。再用我们的平方二项集进行自连接，得到候选的三项集，那么大家注意，在得到候选三项集的时候，一定要利用我们的先验原理进行过滤，所以大家可以看到，在从 L2到 C3这个步骤中，那么有很多三项集已经是因为先验原理被过滤掉了，再得到候选三项集之后，我们依然是利用我们的支持度阈值进行过滤，最后得到我们的频繁的三项集。再令我们的频繁三项集再向下进行我们的迭代，一直得到最终的频繁项集，那么大家可以看到，通过我们的三项集再得到的四项集中已经不是频繁的了。所以我们到L3为止，我们所有的频繁项集挖掘就结束了。
我们再来看一下在频繁项集挖掘中另外一个重要的步骤就只支持度计数。
对于支持度计数来说，我们的步骤操作是比较复杂的，我们需要对每一个候选频繁项集，去扫描一遍数据库，把它和每一个事物的可能的子集进行对比，从而计算我们每一个候选频繁项集的支持度。那么这样的一种计算方式是非常非常复杂的，计算比较慢，
那么在 April 算法中，我们使用的是将每一个事物和我们所有的候选项集进行对比。也就是利用每一个事物去更新所有的候选项集的支持度计数。那么如果是利用这种方法来实现支持度计数。一个比较重要的步骤就是要把所有的事物的子集要列举出来，
比如像我们的这个 PPT 上，就把所有由12356所构成的子集全部列举出来了。在 opera ori 算法中，我们会首先使用哈希树对我们的候选集进行存储。
比如我们这里使用了哈希函数是对三相除取余，然后设置它的最大叶子数为三，利用这样的哈希函数和最大叶子树，我们构建了一个哈希树，并且把我们的三项及全部存储在我们这个哈希树中。在完成这个哈希树的构建之后，
那我们这样就可以把是12345所有的子集反列到我们的哈希树的各个分支上，从而和我们的候选频繁项集进行对比，用于更新频繁项集的支持度计数。
