基于改进的Apriori算法的关联规则分析

Analysis of Association Rules Based on Improved Apriori Algorithm

摘要: 关联规则反映事物与其他事物之间的关联性，是数据挖掘领域研究的一个重要方面，关键概念包括支持度，置信度，提升度。在关联规则中，Apriori算法是其重要组成部分。传统的Apriori算法存在如多次扫描数据库，需要很大的I/O负载，以及产生大量冗余性的候选项集等瓶颈问题。因此，对Apriori算法进行改进，通过布尔矩阵进行行列压缩来减少扫描数据的规模，通过引用索引表的形式来替代生成候选项集，并且以Tried树的形式来对最后所生成的所有频繁项集进行查找，从而加快了计算置信度的时间，以此来解决其瓶颈问题。最终实验结果表明，改进后的算法相比于传统的算法，大大提高了Apriori算法的时间及空间效率。

Abstract: Association rules reflect the association between things and other things, which is an important aspect of data mining research. The key concepts include support, confidence and promotion. Apriori algorithm is an important part of association rules. The traditional Apriori algorithm has some bottleneck problems, such as scanning the database many times, requiring a lot of I/O load, and producing a large number of redundant candidate itemsets. Therefore, the Apriori algorithm is improved. The scale of scanning data is reduced by row and column compression of Boolean matrix. The candidate itemsets are generated by using index table instead. All frequent itemsets are searched in the form of tried tree, which speeds up the calculation time of confidence, so as to solve the bottleneck problem. The final experimental results show that the improved algorithm greatly improves the time and space efficiency of Apriori algorithm compared with the traditional algorithm.

1. 引言

当今社会，是一个大数据的社会，数据挖掘技术的应用越来越广泛。数据挖掘是指从大量不完整的且有噪声的随机数据中，提取隐含在其中人们事先不知道但可能有潜在作用的信息和知识。在第十一届国际联合人工智能学术会议上“从数据库中发现知识(KDD)”一词首次出现，这标志着数据挖掘的初始形成。20世纪60年代，还停留在数据的搜集阶段，主要以存储在计算机，磁带或者磁盘里的静态的历史数据为主；到了20世纪80年代，可以在关系型数据库中通过结构化查询语言对历史性的数据进行动态访问；20世纪90年代，可以在多维的数据库及数据仓库中通过联机分析处理等技术对数据进行动态访问；21世纪，通过一些高级的算法，多处理器计算机，达到对于数据的海量存储，并把这些数据进行数据预处理，除噪等操作，从海量的数据中获取有价值的数据信息。到目前为止，数据挖掘技术规模逐渐变大，也逐渐成熟。而关联规则 [1] 反映了一个事物与其他事物之间的相互依存性与关联性关系，通过关联规则，可以发现大型数据集之间的频繁项集，由频繁项集产生强关联规则，进而找到数据间的相关性。在如此的核心思想下，Apriori算法应运而生。

传统的Apriori算法通过迭代的方法扫描数据库，先将项集进行连接操作，找到不满足支持度的项集进行剪枝，然后将符合要求的频繁项集进行再次连接，依次迭代进而找到满足最小支持度阈值的频繁项集，再由频繁项集找到满足最小支持度阈值与最小置信度阈值的强关联规则。在对传统的Apriori算法使用过程中，越来越发现其存在的不足之处。对于每次循环，候选集都要扫描数据库，如果说一个频繁的大项目包含10个项的话，那么就至少需要扫描事务数据库10遍，并且在这个过程中产生了庞大的候选项集，这对算法运行的时间及主存的空间都是一种挑战 [2]。基于以上问题，本文提出了一种通过布尔矩阵压缩，生成索引表，再将索引表转换成Tried树的方式来对Apriori算法进行改进。改进后的算法将事务数据库转换为布尔矩阵，并对该矩阵进行行压缩与列压缩，从而有效减少了所需扫描数据的规模，减少了扫描次数。并且通过数学运算的方式代替事务查找，即通过按位与运算，从布尔矩阵中找到项集的索引表，在这个过程中不用再生成候选项集，免去了产生庞大的候选项集的麻烦。最后将索引表转换为Trie树的形式来查找频繁项集进而计算置信度找到强关联规则。以上改进解决了传统Apriori算法中存在的性能问题，提高了该算法的运行效率。

2. Apriori算法

2.1. Apriori算法概述

1993年，Rakesh Agrawal [3] 等首次提出了顾客交易数据库中项集间关联规则挖掘问题，随后大批科研人员对于该问题进行了深入研究。1994年，Rakesh Agrawal和Ramakrishnan Srikant正式提出Apriori算法用于挖掘数据库中的频繁项集。Apriori在拉丁语中的意思为“来自以前”，也就是先验或者假设的理论，Apriori算法的名字正是基于这样的一个事实：算法使用频繁项集的先验性质，即频繁项集的所有非空子集也一定是频繁项集。Apriori算法作为第一个关联规则挖掘算法，也是数据挖掘中最经典的关联规则挖掘算法，其主要是找到数据集间的关系来帮助人们做一些决策，现阶段已经被广泛应用到商业，农业，医学等各个领域。

2.2. Apriori算法核心思想

Apriori算法通过迭代 [4]，检索事务数据库中所有的频繁项集，即支持度不低于用户设定阈值的项集，然后再利用频繁项集构造出满足用户最小置信度的关联规则。首先通过扫描事务数据库，生成候选项集C₁，并计算它的支持度，通过筛选去掉支持度低于阈值的候选1项集，得到频繁1项集，将该集合记作L₁，然后再连接频繁1项集得到候选2项集并计算支持度，通过筛选去掉不满足支持度的候选2项集，得到频繁2项集，将该集合记作L₂，L₂找L₃，以此类推，不断循环，直到不能再找到任何的频繁K项集。最后，在所有的频繁项集中查找并计算置信度，同时满足最小支持度阈值与最小置信度阈值的规则即为强关联规则。

Apriori算法的先验性质是其一大特点，所有频繁项集的子集必是频繁项集。从而也可以得到一个推论，非频繁项集的超集必是非频繁的 [5]。依据这一性质一推论，挖掘出满足支持度和可信度阈值的所有级别的频繁项集。

3. 改进的Apriori算法

3.1. 改进算法的思想

改进该算法的主要思想是通过布尔矩阵进行行列压缩，减少事务数据库的扫描次数 [6] - [12]；在扫描过程中以索引表的形式替代候选项集，免去了生成大量候选项集的麻烦；在查找频繁项集并计算置信度时以Tried树的形式加快查找速度。

1) 将事务数据库D转换为矩阵Mat，其中事务按照列顺序排序，项集按照行顺序排序，该矩阵的表示如下：

$\begin{array}{l}\begin{array}{cccc}{\text{T}}_{\text{1}}& {\text{T}}_{\text{2}}& \cdots & {\text{T}}_n\end{array}\\ \text{Mat}=\left[\begin{array}{cccc}{d}_{11}& d_{12}& \cdots & d_{1n}\\ d_{21}& d_{22}& \cdots & d_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ d_{m1}& d_{m2}& \cdots & d_{mn}\end{array}\right]\begin{array}{c}{I}_1\\ I_2\\ ⋮\\ I_m\end{array}\end{array}$ (1)

2) 如果第i个项集在第j个事务中，则矩阵第i行，第j列的值d_ij为1，否则为0，由此得到布尔矩阵。

3) 由上一步得到的布尔矩阵可以计算该矩阵中某一行形成的项集的支持度。支持度由各行向量通过按位与运算得到。

$\text{support\_count}\left(\text{mathrm}\left\{{\text{C}}_k\right\}\right)={\displaystyle {\sum }_{j=1}^n\left(d_{i_{1}j}\wedge d_{i_{2}j}\wedge d_{i_{3}j}\wedge \cdots \wedge d_{i_{k}j}\right)}$ (2)

4) 由布尔矩阵以及支持度的计算方法，得到各项集的支持度，依此得到项集索引表，再与所设置的最小支持度比较得到频繁项集。

5) 依据频繁项集的一性质一推论，如果一个项集是非频繁的，那么所有包含该项集的项集也是非频繁的，可以将其直接进行删除，也就是进行行压缩。

6) 由于布尔矩阵每个事务对应一个列向量，所以如果一个事务的长度小于K，那么不可能包含K-频繁项集L_k，在搜索时可直接将该事务删除，也就是进行列压缩。

7) 将压缩后的布尔矩阵再次进行扫描，计算支持度，创建索引表。重复上述步骤，直到不能再产生K-频繁项集，最终以索引表的形式得到所有频繁项集。

8) 最后引用Tried树的形式对所有的频繁项集进行查找，计算置信度，从而产生强关联规则，即产生用户感兴趣的关联规则。

3.2. 改进算法实例说明

以一实例来对该算法进行简单说明，如表1为事务数据库D：

Table 1. Database D

表1. 数据库D

将该数据库转换为布尔矩阵，该矩阵的表示如下：

$\begin{array}{l}{\text{T}}_{\text{1}}{\text{T}}_{\text{2}}{\text{T}}_{\text{3}}{\text{T}}_{\text{4}}{\text{T}}_{\text{5}}{\text{T}}_{\text{6}}\\ \text{Mat}=\begin{array}{c}1\\ 2\\ 3\\ 4\\ 5\end{array}\left[\begin{array}{cccccc}1& 0& 1& 1& 0& 1\\ 1& 1& 1& 1& 1& 0\\ 0& 0& 1& 0& 1& 1\\ 0& 1& 1& 1& 0& 0\\ 1& 0& 0& 0& 0& 0\end{array}\right]\end{array}$ (3)

假设该数据库最小支持度阈值(min_support)为2，通过按位与运算得到各行向量的支持度，形成索引表，如表2。因为min_support = 2，所以Count需要大于等于2，即可把不满足要求的直接删除，得到如表3。

Table 2. Indextable-L1

表2. 索引表-L₁

Table 3. Frequent itemsets-L1

表3. 频繁项集-L₁

论将频繁项集-L₁转换为矩阵形式，得到M₁，该矩阵的表示如下：

$\begin{array}{l}{\text{T}}_{\text{1}}{\text{T}}_{\text{2}}{\text{T}}_{\text{3}}{\text{T}}_{\text{4}}{\text{T}}_{\text{5}}{\text{T}}_{\text{6}}\\ M_1=\begin{array}{c}1\\ 2\\ 3\\ 4\end{array}\left[\begin{array}{cccccc}1& 0& 1& 1& 0& 1\\ 1& 1& 1& 1& 1& 0\\ 0& 0& 1& 0& 1& 1\\ 0& 1& 1& 1& 0& 0\end{array}\right]\end{array}$ (4)

由M₁得到索引表-L₂索与频繁项集-L₂，如表4，表5。

Table 4. Indextable-L2

表4. 索引表-L₂

Table 5. Frequent itemsets-L2

表5. 频繁项集-L₂

再由M₁删除少于3项的事务，即进行列压缩，得到M₂，该矩阵的表示如下：

$\begin{array}{l}{\text{T}}_{\text{3}}{\text{T}}_{\text{4}}\\ M_2=\begin{array}{c}1\\ 2\\ 3\\ 4\end{array}\left[\begin{array}{cc}1& 1\\ 1& 1\\ 1& 0\\ 1& 1\end{array}\right]\end{array}$ (5)

由M₂得到索引表-L₃索与频繁项集-L₃，如表6，表7。

Table 6. Indextable-L3

表6. 索引表-L₃

Table 7. Frequent itemsets-L3

表7. 频繁项集-L₃

将所得所有频繁项集存入索引表中，然后将频繁项集转换为Tried树的形式进行查找，并计算得到所有满足最小置信度的规则，产生的规则既为强关联规则。

3.3. 改进算法的实现

1) 将数据集转换为矩阵

public void addData(String[] projects) {

BitSet bitSet = new BitSet();

for (String temp : projects) {

ProjectAttr projectAttr = projectMap.get(temp);

if (Objects.isNull(projectAttr)) {

projectAttr = new ProjectAttr();

projectAttr.index = projectMap.size();

projectMap.put(temp, projectAttr);

this.maxProjectSize = projectMap.size();

projectIndexMap.put(projectAttr.index, temp);

}

projectAttr.count++;

bitSet.set(projectAttr.index);

}}

1) 行压缩

public Map supportCountOneProjectAndCompressProjects(int threshold) {

Map map = new HashMap<>();

List willRemoveProjects = new LinkedList<>();

for (Entry entry : projectMap.entrySet()){

if (entry.getValue().count >= threshold) {

map.put(entry.getKey(), entry.getValue().count);

} else {

willRemoveProjects.add(entry.getKey());

}

}

2) 列压缩

public void compressAffair(int threshold) {

Iterator iterator = matrix.iterator();

while (iterator.hasNext()) {

BitSet next = iterator.next();

if (next.cardinality() < threshold) {

iterator.remove();

for (int i = 0; i < next.size(); i++) {

if (next.get(i)) {

String projectKey = projectIndexMap.get(i);

ProjectAttr projectAttr = this.projectMap.get(projectKey);

if (Objects.nonNull(projectAttr)) {

projectAttr.count--;

}

}

}

}

}}

3) 索引表查找与Tried树查找

public class IndexRecord implements Comparable {

public static IndexRecord of(Collection item, int count) {

return new IndexRecord(item, count);}

public IndexRecord inspectTakeIndexRecord(final Collection item) {

if (Objects.isNull(rootMatcher)) {

this.resetMatcher();}

TriedNode parent = this.rootMatcher;

for (String temp : item) {

parent = parent.map.get(temp);}

return parent.item;}}

private int getCount(Collection collection) {

long start = System.nanoTime();

int count = 0;

if (triedFlag) {

IndexRecordinspectTakeIndexRecord = triedHallows.inspectTakeIndexRecord(collection);

if (Objects.nonNull(inspectTakeIndexRecord)) {

count = inspectTakeIndexRecord.getCount();}

} else {

for (IndexRecord indexRecord : indexTable) {

if (indexRecord.collectionEquals(collection)) {

count = indexRecord.getCount();

break;}}}

long end = System.nanoTime();

sum += end - start;

return count;}

4. 算法性能验证及结果分析

为了更好的证明改进后的算法相比于改进前的算法在性能及效率上的提升，因此进行了对比实验。在不同事务数以及不同最小支持度阈值的情况下，对比改进前的算法与改进后的算法在运行后产生频繁项集所需的时间；在查找频繁项集计算置信度时对以索引表的形式查找和以Tried树的形式进行查找进行对比实验。从而更加清晰直观有效的证明了改进后的算法在效率上有了相当大的提升。

4.1. 对产生频繁项集所需时间的对比

本实验所采用的数据为模拟随机生成的数据集，共7组数据，分别为1000，2000，5000，10,000，20,000，50,000以及80,000条事务，并将其存入.txt文件中。

如图1，为相同最小支持度阈值，不同事务数的情况下得到的实验结果转化而成的折线图。实验结果为：事务数据量为1000时，算法优化前所需时间为258毫秒，优化后所需时间为59毫秒；事务数

Figure 1. Under different number of transactions

图1. 不同事务数情况下

据量为2000时，算法优化前所需时间为682毫秒，优化后所需时间为82毫秒；事务数据量为5000时，算法优化前所需时间为3316毫秒，优化后所需时间为184毫秒；事务数据量为10,000时，算法优化前所需时间为10,750毫秒，优化后所需时间为466毫秒；事务数据量为20,000时，算法优化前所需时间为28,160毫秒，优化后所需时间为649毫秒；事务数据量为50,000时，算法优化前所需时间为98,016毫秒，优化后所需时间为1731毫秒；事务数据量为80,000时，算法优化前所需时间为196,606毫秒，优化后所需时间为3516毫秒；由图1可知：在相同最小支持度阈值的情况下，随着事务数的不断增大，改进前的算法与改进后的算法运行所花费时间均增长；但整体上看，各事务数相同的情况下，改进后的算法要比改进前的算法快的多，这充分证明了改进后的算法在apriori算法性能优化方面是高效的。

2) 如图2，为相同事务数，不同最小支持度阈值的情况下得到的实验结果转化而成的折线图。由于在实验过程中产生大量的偶发情况，如某一支持度下运行时网络突然不好则运行结果会相当大，故图2展示的实验结果为进行大批量实验后，所有实验结果的平均值。选择事务数为80,000情况下的实验结果进行描述，80,000情况下的实验结果为：最小支持度阈值为0.01时，算法优化前所需的时间为386,369毫秒，优化后所需时间为153,255毫秒；最小支持度阈值为0.02时，算法优化前所需的时间为309,468毫秒，优化后所需时间为5740毫秒；最小支持度阈值为0.03时，算法优化前所需的时间为248,277毫秒，优化后所需时间为3901毫秒；最小支持度阈值为0.04时，算法优化前所需的时间为207,720毫秒，优化后所需时间为2783毫秒；最小支持度阈值为0.05时，算法优化前所需的时间为193,114毫秒，优化后所需时间为1781毫秒；最小支持度阈值为0.06时，算法优化前所需的时间为192,231毫秒，优化后所需时间为1585毫秒；由图2知，在相同事务数的情况下，随着最小支持度阈值的不断增大，改进前的算法与改进后的算法运行所花费的时间均不断减小，并且改进后的算法相比于改进前的算法，在不同最小支持度下均是改进后的算法所需的时间少，效率比改进之前的有明显提高。由该图也可分析出，如果当最小支持度阈值达到一定程度，运行所需要的时间可能会达到0，且增大到一定程度时，也有可能改进前与改进后的算法运行所需时间相同；如果最小支持度阈值越小，则改进前算法与改进后算法所需时间差距也就越大，因为设置的最小支持度越小，则满足条件的频繁项集就越多，在数据集多的情况下，更能体现出改进后的算法在运行时间性能等上的优越性。

Figure 2. In the case of different minimum support thresholds

图2. 不同最小支持度阈值情况下

4.2. 对查找频繁项集生成强关联规则所需时间的对比

将上一步中查找出来的频繁项集存在索引表中，随后进行再次查找并计算置信度，从而得到强关联规则。为了更快的得到强关联规则，所以决定把索引表的形式转化为Tried树的形式进行查找。通过实验，对比以索引表的形式查找和以Tried树的形式进行查找所需的时间，有力的证明了以Tried树的形式查找要比以索引表的形式查找快的多。

如图3，为相同最小支持度以及事务数的情况下，以索引表形式进行查找和以Tried树进行查找所需时间的对比。在进行多次实验后选取平均值。由该图可知：最小支持度为0.01时，以索引表形式查找所需时间为184毫秒，以Tried树形式查找所需时间为73毫秒；最小支持度为0.02时，以索引表形式查找所需时间为142毫秒，以Tried树形式查找所需时间为56毫秒；最小支持度为0.03时，以索引表形式查找所需时间为137毫秒，以Tried树形式查找所需时间为55毫秒；最小支持度为0.04时，以索引表形式查找所需时间为135毫秒，以Tried树形式查找所需时间为53毫秒；最小支持度为0.05时，以索引表形式查找所需时间为135毫秒，以Tried树形式查找所需时间为50毫秒；最小支持度为0.06时，以索引表形式查找所需时间为130毫秒，以Tried树形式查找所需时间为49毫秒。

Figure 3. Different search results

图3. 不同查找结果的情况下

5. 结语

本文通过分析传统的Apriori算法存在的缺点，因此对其进行了改进。改进后的算法通过运用布尔矩阵进行行列压缩，通过运用索引表替代事务查找，通过Tried树减少查找计算置信度时所需的时间。在多次实验中证明了改进后算法的优越性，同时从实验结果中也可知此改进的算法更适用于海量数据的处理。总体上解决了传统Apriori算法中存在的那些性能问题，有效减少了挖掘时间。