数据挖掘中主要用到方法有分类(Classification)、估计(Estimation)、预测(Prediction)、关联规则(Association rules)、聚类(Clustering)等。Apriori算法是一个经典的数据挖掘算法，Apriori算法的用处是挖掘频繁项集的，频繁项集通俗的理解就是找出经常出现的组合，然后根据这些组合最终推出我们的关联规则。
算法定义
关联规则(Association Rules)挖掘,是数据挖掘技术的一个重要分支,主要研究的是事务数据库中有利用价值的项与项之间的联系,主要应用于商业推荐系统、医疗诊断系统、金融投资领域等,其关注重点不在于事务数据库中的项的意义以及其顺序,而在于项与项之间的关联。
关联规则挖掘主要解决的问题是诸如“当一个项A出现时,B或者C与它同时出现的几率有多大”,从而找出A与B或C之间的相互关系。关联规则挖掘的主要任务与数据挖掘的类似,都是为了减少原始数据的无序性,从海量无序的噪声数据中找出有价值的知识。不同的是关联规则专注的是项与项的关系而忽略其次序。但由于数据挖掘及关联规则挖掘所需要处理的原始数据规模都相当庞大,当其算法面对数据规模呈线性增长时,在进行数据分析与计算的过程中算法性能越来越显不足,所以如何利用现有技术提高算法性能越来越有必要,具有重要的研究意义。
Apriori算法是一种逐层搜索的迭代式算法，其中k项集用于挖掘(k+1)项集，这是依靠他的先验性质的：频繁项集的所有非空子集一定是也是频繁的。 通过这个性质可以对候选集进行剪枝。用k项集如何生成(k+1)项集呢，这个是算法里面最难也是最核心的部分。通过以下2个步骤 :
1、连接步，将频繁项自己与自己进行连接运算。
2、剪枝步，去除候选集项中的不符合要求的候选项，根据支持度完成剪枝操作，不符合要求指的是这个候选项的子集并非都是频繁项。
该算法有两条重要性质:
1.任一频繁项集的所有非空子集也必须是频繁的。假设一个项集{A,B}是频繁项集,即A、B同时出现在一条数据库事务中的次数大于等于最小支持度阈值,则它的子集的支持度必定大于等于最小支持度阈值,即它的子集都是频繁项集。
2.如果一个项集不是频繁项集,则它的所有超集都不是频繁项集。假设项集{A}不是频繁项集,即{A}的支持度小于最小支持度阈值,则它的任何超集,如{A,B}的支持度必定小于最小支持度阈值,因此其超集也必定不是频繁项集。
KEY CONCEPTS
对于关联规则A=>B (其中A和B是项目的集合),支持度定义为:
支持度(A=>B)=包含A和B的元组总数/元组总数
K阶项集：意义为由k个项组成的项集,例如二阶项集{奶粉,尿裤}。项集的支持度的意义为,某一项集在数据库中的事务中出现的频率,若某一项集在事务数据库中出现概率大于所设定的最小支持度阈值,则该项集为频繁项集。通常K阶频繁项集记做Lk。
连接操作：通过连接Lk-1频繁项集生成k阶频繁项候选集Ck。
向下封闭原则(Downward Closure Property)是这样定义的,对于任意符合最小支持度要求的项目集合,它的任何非空子集都必须符合最小支持度要求。
算法步骤
算法举例
算法局限性及改进方法
重复扫描数据库和规模巨大的候选集是Apriori算法的两大瓶颈，比如在某事务数据库中有10000个1阶候选项集，根据向下封闭原则完成连接操作后可能会生成10000000个频繁项候选集，这个数量将是巨大的。程序对整个事务数据库进行遍历,依次计算Ck中每一个候选项集C的支持度。对于很庞大的数据集时,传统的Apriori算法并不会将整个数据集加载到内存。
通过对Apriori算法的研究,我们发现算法中计算最繁重的任务是在事务数据库中计算包含某一频繁项目的支持计数(Support Count)。因此我们将这部分计算过程转移到GPU端,利用GPU高速并行计算能力,提高算法的执行速度和效率。其中涉及的关键点为：
(1)数据结构设计
(2)支持计数计算的并行实现
(3)大数据动态加载
方法一
在Apriori算法中应用的是传统的存储结构如图a所示，使用传统的水平结构存储，在计算支持度的时候都要讲候选项集和经过排序的事务数据库进行匹配，改匹配是不规则的且时间复杂度很高，需要大量的逻辑运算与缓存，GPU采用了弱化逻辑运算能力而强化并行计算能力的方式,所以这种水平存储方式不利于算法性能的提高。区别于传统的水平数据存储方式,存在另外一种数据存储方式,称之为垂直存储方式如图b。在垂直存储方式中,与水平存储方式类似,每一个项(Item)有一个Item ID,但它对应的是一个表示包含该Item的事务的Tid集,简称为Tidset，表示该项存在于其对应的多个事务中，同时以位图的形式表明其对应的事务。
处理过程：
1.事务数据集原本以水平存储方式存储，读入后以<item,bitvector>的垂直形式存储。
2.计算表中个项的频繁度，删除非频繁项。
3.按各项的频繁度进行从低到高的排序。
在完成以上三步后由一项频繁项集生成 frontier stack
Equivalent Class定义为具有相同大小k，有相同的k-1前缀，例如（1,2,3）（1,2,4）（1,2,5）。
开始frontier stack均为1项频繁项集，并均为相同的 Equivalent Class， Equivalent Class 出栈，完成自连接操作形成新的 Equivalent Class，即新的频繁项候选集。之后可由GPU计算各候选项集的频繁度，符合最小支持度（MIN_SUPPORT)的项集入栈，栈中的候选项集按照支持度始终以DESC的排列方式。一直重复以上步骤直至栈中为空。
深度优先遍历和广度优先遍历的对比，a图为DFS内存需求最小并行程度最低，b图为BFS内存需求最大并行化程度最高，c图为改进后的遍历策略，可扩展大小可以根据GPU计算能力，以实现最大的并行程度和最小的内存需要。图中可扩展大小为2，表示可以有两个节点可以同时处理。
下图对比了直接存储事务id方式项集间取交集过程（图a）和以位图的形式存储项集间取交集的过程（图b）。
支持度计算过程
基于位表的存储结构的支持度计算只需统计其位表中1的个数，逻辑方面十分简单，而计算任务繁重，正好符合GPU的计算特点。最后以规约的方式进行计算1的个数，规约优化方法可参照：CUDA并行算法系列之规约http://www.cnblogs.com/5long/p/algorithms-on-cuda-reduction.html 下图中为在一个线程块中、支持度计算方式。
方法二
Trie Compression
简单来说trie 就是一个 ordered tree 排列依据 可以是 alpha 也可以是 数值。并且是 递归的。这样的方式即可以大量压缩同前缀的串，也可以可容易作到子树的融合。生成apiori的candidate 与接下来的删枝 就可以在一个树上完成。实现细节如下：
方法三
在该算法中以一维数组的形式存储数据集，Transcations数组中线性存储事务数据集中的事务，tran_offset数组通过偏移量的形式来存储事务的边界。
通过基于直方图计数完成一项频繁项候选项集的生成和计数。直方图计数：给定一个包含一组元素的数据集，直方图表示每个元素的出现频率。如一个数据集如下所示：
Programming Massively Parallel Processors
构建一个字母出现频率的直方图. A(4次), C(1), E(1), G(1), …
如果输入的数组足够大，那么通过由多个线程来处理缓冲区的不同部分，将该数据集划分成多个block，每个block统计自己的情况，统一保存到一个数值里面，同时使用共享内存原子递增操作来确保计算的正确性。具体过程如下图所示：
若仅使用全局内存，则全局内存上的院子操作导致了性能的降低，当数千个线程尝试访问少量的内存位置时，将发生大量的竞争。要解决这一问题，我们将直方图计算分为两个阶段，在第一个阶段中，每个并行线程将计算它所处理数据的直方图。分配一个共享内存缓冲区并进行初始化，
用来保存每个线程块的临时直方图。第二个阶段，将每个线程块的临时直方图合并到全局缓冲区中。
通过直方图计算和剪枝操作得到 L1 频繁项集后， 由满足最小支持度的频繁项集的个数 k 生成一个只包含-1 的一维数组 mask[ ]长度为 k^2。 由生成邻接矩阵的方式生成下一阶段的频繁项候选集，具体步骤见《基于 GPU 的并行关联规则挖掘算法的设计》文档说明。
本文主要内容参考：
一、 Accelerating frequent itemset mining on graphics
二、A fast Apriori implementation
