作者：郑晓敏
关联规则算法作为一种广泛应用的数据挖掘算法，其目的是在一个数据集中找出各项之间的相关关系，是Agrawal等人在1993年首先提出的，于此同时Agrawal还给出了相应的挖掘算法AIS，但算法性能不是很高。1994年，Agrawal和Srikant共同提出了著名的基于逐层迭代思想的Apriori算法，至今Apriori算法仍然被广泛应用于社会生产的各行各业，以后许多数据挖掘领域的研究人员对关联规则的挖掘问题进行了大量的研究。Savasere等人提出了一种基于划分思想的频繁项集发现算法；Tiovonen提出了基于抽样的思想算法，该策略实际上是以牺牲精度为代价来换取算法的执行效率，适合以效率为重的挖掘任务；Crestana-Jensen等人提出的JSApriori算法采用逐层迭代的思想在多关系挖据中挖掘关联规则。
在网络安全领域Apriori算法取得了广泛应用，将关联规则算法用于入侵检测技术中也是当前研究的热点。网络发展日新月异使得攻击手段不断多样化，传统的仅靠单一的基于模式匹配方法的入侵检测技术难以适用于目前的网络状况。与其他网络安全产品不同的是，智能化的需求在入侵检测系统中格外迫切，它需要具有快速、有效分析数据的能力，并以友好的方式给出有用的结果。一个合格的入侵检测系统可以最大限度地减轻网络管理员的工作，大大提高系统检测的准确性，保证网络系统安全可靠地运行。采用作用度的Apriori算法削弱了Apriori算法的挖掘结果规则，使网络入侵检测系统可以精确地发现用户的行为模式，能够高效地分析出网络攻击者，提高了基于关联规则的入侵检测系统的检测性能。
关联规则挖掘技术能从大量数据中挖掘出有价值、反映数据项之间潜在联系的知识信息。随着数据不断的积累，存储在数据库中的数据规模越来越大，从这些数据中挖掘相应的关联知识信息显得尤为重要，这些关联知识信息可以为决策者做出前沿判断提供有力支撑。
1传统的Apriori算法
关联规则挖掘是从事务集合中挖掘出满足支持度和置信度最低阈值要求的所有关联规则，这样的关联规则也称强关联规则。常用的关联规则算法如表1所示。
关联规则挖掘是从事务集合中挖掘出支持度和置信度大于最低阈值（minsup，minconf）的关联规则，该阈值是由用户根据公式(1)、公式(2)指定。
其中，Tcount表示所有事务的集合个数，（X,Y）count表示T中同时包含X和y的事务的个数，Xcount表示T中包含X的事务的个数。
关联规则挖掘总体过程主要包括生成频繁项目集和产生强关联规则两步。
1)以事先设定的最小支持度为根据，找出事务集合D中所有的频繁项目集。最终目的是根据K-频繁项目集生成需要的(K+1）一频繁项目集。
2)由频繁项目集和最小支持度产生强关联规则。一种比较容易的办法就是遍历所有的频繁项目集，然后从每个项目集中依次取1，2，…,K个元素作为后件，该项目集中的其他元素作为前件，通过计算该规则的置信度筛选出强关联规则。但是这种方法的效率不是很高。
Apriori关联规则挖掘的两步中，步骤1）根据最小支持度找出事务集合D中所有的频繁项目集是关联规则挖掘的中心问题，能否迅速高效地找出集合D中所有频繁项目集会对算法效率产生很大影响。步骤2）根据频繁项目集和最小支持度产生强关联规则求解相对简单和直接，但也需要根据用户和应用场景的不同来没置求解指标（如兴趣度的度量标准）。
1.1 Apriori算法计算复杂度
Apriopri算法的计算复杂度主要由支持度阈值、项数、事物数3个方面因素决定。
1.1.1支持度阈值
降低支持度阈值导致的后果就是频繁项集的增多，这会大大增加算法的计算复杂度，因为支持度阈值降低产生的候选项集大量增加并要统计候选项集的个数。此外，支持度阈值的降低还将增加频繁项集的最大长度，频繁项集最大长度的增加带来的后果就是算法需要更多次数的扫描数据集。所以，支持度阈值会对算法的计算复杂度产生很大影响。
1.1.2项数（维度）
Apriori算法项数的增加导致的一个直接结果就是支持度计数项的增多，为了存储支持度计数项就需要更大的存储空间。如果频繁项集的数目也随着数据维度增加而增长，那么算法产生的候选项集将会变得十分庞大，因此，计算量和I/O开销将明显增加。
1.1.3事务数
Apriori算法的一个特性就是运行时间随着事务数增加而增加，这是因为Apriori算法需要反复扫描数据集。Apriori算法采用逐层搜索的迭代方法，其核心思想是利用后项集来探索(k+l)项集。首先，通过扫描数据库，记录每个项的个数，从而产生频繁1-项集，同时收集满足最小支持度的这些项，得到的集合记为L1。接下来，用L1产生频繁2-项集L2，然后用L2来产生频繁3-项集L3依此类推，直到没有新的频繁k-项集产生，即/k=0。每产生一个Lk都需要把数据库全部扫描一遍。为提高逐层迭代产生频繁项集的效率，应用先验原理可以减少搜索空间，提高逐层迭代产生频繁项集的效率”。
1 12先验性质
先验性质( apriori property)要求频繁项集的所有非空子集也一定是频繁的。先验性质是一种用于压缩空间的重要性质，先验性质的应用可以提高频繁项集逐层产生的效率。根据定义，如果项集，不满足最小支持度阈值minsup，则，不是频繁的，即P(l)<min_sup。如果把项A添加到项集I中，则结果项集（即IUA）不可能比J，更频繁出现，因此，/UA也不是频繁的，即P(IUA)<min_sup。例如，如果{1，2}出现的次数小于最小支持度（非频繁的），那么超集{0,1，2}的组合肯定也是非频繁的。频繁项集的产生需要合并和剪枝两个步骤。
1.3经典的Apriori算法
下面将给出Apriori算法产生频繁项集的部分伪代码二事务集合D和最小支持度阈值（min_sup）作为算法输入二D中的频繁项集L作为算法输出。具体算法如下。
Ll= find_frequent_l-itemsets(D)；//从事务集合D中发现所有的频繁1一项集，定义为Ll
Ck=apriori_gen(Lk-l，min_sup);//产生候选项集
for each logt D{//扫描数据库，并计数
C1=subset(Ck，t)：//获得t所包含的候选项集for each log t Ct//循环遍历每个候选项集c∈C．
c．count++；1
Lk={ c∈CkI c.c,ount≥min_sup)}//提取频繁k-项集
return L=UkLk；
apriori_gen(Lk-l:frequent(k-l) -itemsets)
∥产生k一项候选项集
for each itemset ll∈Lk-l{//循环遍历每个项
for each itemset l2∈Lk_l{
if(l1[1]=l2[1])“(1.[2]=l:[2])“…”(1, [k-l]=12
[k-1])“(l1 [k-l]< 12[k-1]){
c=l1∞l2；//11和l2做笛卡尔积
if has-infrequent_subset(c,Lk-1)
delete c；／／删除非频繁的候选项
else add c to Ck；}
return Ck;
has_infrequent_subset(c:candidate k-itemset;Lk_,:frequent(k-l)-
itemsets)∥使用先验知识
for each itemset (k-l)-subset s of c{
if s 不属于Lk-1
return true,
return false;1
上述算法中的apriori-gen函数通过候选项集的产生和候选项集的剪枝操作产生候选项集。
1.4使用传统Apriori算法产生频繁项集
表2是一个日志审计数据库的具体例子。在这个数据库中有9条交易记录，也就是IDl=9。T1,T2，…，T9表示一条日志记录项集，以，a,b,c…表示一条日志记录中的项。
下面的步骤用来解释候选项集和频繁项集的产生，Itemset表示项集，Sup．count表示支持度计数。表1的事务数据最小支持计数为3。
1)扫描事务集合D，统计每个候选项的支持度计数，如表3所示。
2)比较候选项支持度计数与最小支持度计数，删掉不符合条件的候选，产生频繁1-项集L1，如表4所示。
5)将候选项支持度计数与最小支持度比较，产生频繁
2一项集l2，如表7所示。
8)将候选项支持度计数与最小支持度比较，删掉不符合条件的候选，产生频繁3-项集L3，如表10所示。
1.5 Apriori算法的改进方法
1.5.1基于动态项集计数的改进方法
基于动态项集计数的优化方法将数据库划分为标记开点的块，算法可以在任何开始点添加新的侯选项集。该方法动态地评估已被计数的所有项集的支持度，如果一个项集的所有子集己被确定为频繁的，则添加它作为新的侯选项集。
1.5.2基于哈希(Hash)表技术的改进方法
利用Hash表技术可以帮助有效减少候选k-项集Ck(k≥1)所占用的空间。利用这样Hash表技术可以有效减少需要检查的候选项集数目。
1.5.3基于采样的优化方法
基于采样的优化方法是在一个给定数据库D的随机样本S中进行挖掘，这种方法牺牲了精确性换取有效性，内存的大小决定了样本S的大小。样本S中的频繁项集不一定是数据库D中的频繁项集，而且，数据库D中的频繁项集不一定出现在样本S的频繁项集中。
2改进的Apriori算法
对于非常大的数据库，传统Apriori算法产生庞大的候选项集，所以它需要更大的计算代价。为了避免这个缺点，本文介绍一种改进的Apriori算法来减少候选集数量。本文提出的系统变量transaction_size(TS)包括个人交易项目的数量，如果transaction size小于阈值，这一交易将从数据库中删除。
2.1算法描述
改进的Apriori算法通过单遍扫描数据集确定每个项的支持度，进而就得到所有的频繁1一项集的集合L1。依照此方法，使用上一次迭代发现的频繁（K-1）-项集，产生新的候选k-项集。apriori-gen函数负责实现候选项的产生，算法需要再次扫描数据集，计算出候选项的支持度。计算候选项的支持度计数之后，算法将删除支持度计数小于min_sup的所有候选项集。更新数据库，通过扫描事务集合D、/k-1、Lk，将存在Lk-1中，不存在Lk中且未在频繁1一项集中出现的元素从数据库中删除。最后再一次扫描事务集合D，计算每个事物中的元素个数，若元素个数小于k则删除该条事物。当没有新的频繁项集产生，即/k=0时算法结束。
下面给出了改进的Apriori算法产生频繁项集的部分伪代码。事务集合D和最小支持度阈值(min_sup)作为算法输入，D中的频繁项集L作为算法输出。具体实现算法如下。
delete datarow;))//删除TS计数小于所求频繁项集数的记录
2.2算法实例
以下步骤是使用改进的Apriori算法产生表1 1的频繁项集，TS表示事务元素个数。
1)扫描表11每个1一项集的计数，生成候选l一项集，即表12，删除候选1一项集中不满足最小支持度的项集，生成频繁1一项集，即表13。
表1 1原始日志审计数据库实验数据
2)执行更新数据库的操作，删除数据库中未在频繁1一项集中出现的项，同时更新数据库中TS的计数。检查新数据库中每项事务TS是否小于k，若小于k，则在数据库中删除该项事务（k为候选项的个数），完成数据库更新，如表14所示。根据已产生的频繁1-项集，进行连接操作，生成候选2-项集，如表15所示。扫描数据库记录候选2-项集支持度计数，删除候选2-项集中不满足最小支持度计数的项，生成频繁2-项集，如表16所示。
3)再次执行更新数据库的操作，此时不再进行删项操
作，只检查新数据库中每项事务TS是否小于k，若小于k，则在数据库中删除该项事务（k为候选项的个数），完成数据库更新，新数据库如表17所示。根据已产生的频繁2-项集，进行连接操作，生成候选3-项集，如表18所示。扫描更新后的数据库记录候选3-项集支持度计数，删除候选3-项集中不满足最小支持度计数的项来生成频繁3-项集，如表19所示。
3传统Apriori和改进的Apriori算法性能比较
本文在不同的实例集和置信度上分别比较了两种算法的性能，如图1所示。
图l中，纵轴代表时间，横轴代表置信度。
从图1可以看出，对于3个不同的置信度执行改进的Apriori算法都比传统的Apriori算所花的时间少。因此，改进的Apriori算法是一个高效、可扩展的完整的频繁模式挖掘方法。
4结束语
本文通过分析Apriori算法，结合文献中已有的经典Apriopri算法，提出了_一种新的更高效的算法，并给出了算法实现思想。改进的Apriori算法通过消除数据库中不必要记录的传输有效减少了I/O所花费的时间，Apriori算法的效率得到了极大的优化，从海量数据中挖掘关联信息将会更陕。
评估这两种算法的性能是基于它们产生关联规则所用的时间。经过分析可以得出，改进的Apriori算法的性能比传统的Apriori算法更好。
但本文提出的改进Apriori算法除了具有Apriori普遍的缺点——产生大量的频繁项集外，当数据库中的频繁项集中元素个数较多时，算法执行时并没有太多冗余项可删除，这就造成了无谓的扫描数据库。因此该算法在有些情况下也会增加扫描数据库的次数，如何避免这种情况将是进一步研究的问题。
5摘要：
在当今这个信息极度发达的社会，网络数据急剧膨胀，激增的数据背后隐藏着许多重要的信息，所以对大量数据进行分析是必要的。Ap rio ri算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。可能产生大量的候选集，以及可能需要重复扫描数据库是Ap rio ri算法的两大缺点。文中提出了一种需要更少的扫描时间的Apriori算法，在剪枝候选项集的同时也在消除冗余的子项集的产生 改进的Apriori算法通过消除数据库中不需要记录的传输有效减少了I/O所花费的时间，Apriori算法的效率得到了极大的优化。文章给出了算法实现思想及证明，并对传统的和改进的Ap rio ri算法进行比较和分析。
