第48页 Apriori

目标

该算法功能是寻找所有支持度不小于minsup的项集

主要概念：

频繁项集：支持度不小与minsup的项集（如果物品集合出现在多个”篮子“中，则说该物品集合是频繁地，而该集合称为频繁项集）

Apriori性质： 频繁项集的子集必是频繁地（自下而上闭合性）

Join Operation：to find Lk，a set of candidate K-itermset is generated by joining Lk−1 with itself

相关定义

关联规则: X=>Y，其意义在于一个事务中某些项的出现，可以推导出另一些项也在该事务中出现

支持度、最小支持度：包含该项集的事务占所有事务的比例

置信度、最小置信度：假设J是频繁项集，则J−{j}也是频繁项集，则定义为confidence=support(J)/support(J−{j})
注意：置信度表示规则的强度， 支持度表示在规则中出现的频度。最小支持度阈值minsupport表示数据项集在统计意义上的最低主要性。最小置信度阈值mincontinence表示规则的最低可靠性。（**什么意思？？？？**)
算法思想

在Apriori算法中,寻找最大项目集的基本思想是:

算法需要对数据集进行多步处理.

第一步,简单统计所有含一个元素项目集出现的频率,并找出那些不小于最小支持度的项目集,即一维最大项目集.

从第二步开始循环处理直到再没有最大项目集生成.循环过程是:第k步中,根据第k-1步生成的（k-1）维最大项目集产生k维候选项目集,然后对数据库进行搜索,得到候选项目集的项集支持度,与最小支持度比较,从而找到k维最大项目集.

算法评价

优点：简单、易理解、数据要求低

缺点：

在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素
每次计算项集的支持度时，都对数据库D中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。
进一步阅读：

FP-growth算法