关联规则算法改进-科学化图书馆管理与阅读推广　

（一）Apriori算法简介

作为挖掘数据之间关联规则的算法，Apriori算法从1994年被提出至今，不断地改进并衍生出多个版本，比如FP-Growth算法。在被其他理论学科引用的同时，Apriori算法在应用领域也拥有广泛的市场^[7]。例如，网络入侵检测技术，消费市场价格分析，辅助通信运营商调查数据获得市场动态信息等。迭代是Apriori算法的核心内容。Apriori算法是基于频繁集的搜索和频繁集规则产生过程的递推算法，目标是找到最大K项频繁集。根据支持度、置信度评估频繁集是否合适。支持度指的是关联数据条数在总数据条数中出现的概率；置信度指的是数据出现的条件概率，也就是一个数据出现概率对另一个数据出现概率的依赖性。Apriori算法的基本流程：①扫描整个数据库计算出所有的频繁项集，同时发现并先前设定支持度一致的频繁项集；②基于上一步产生频繁项集的规则，通过扫描候选项频繁K项集的支持度，丢弃候选频繁K项集中支持度低于阈值的数据集，得到适合项目实际需求的频繁K项集。通过K次迭代得到的结果可能为空集合，在返回第K-1项频繁集为最后结果。

Apriori算法每次生成关联规则都要迭代扫描整个数据库，通过频繁K-1项集找到频繁K项集，在数据大且类别多时，这种做法效率比较低。影响效率的主要因素如下：①因需计算频繁项集中的每个值，计算需要多次迭代，导致在每次迭代过程中都要扫描整个数据库，造成扫描次数较多，浪费计算资源和计算时间；②尽管数据清洗减少了初始数据量，并且在计算过程中采取了适用的剪枝策略，但是由于数据库中数据集合较多，每次计算扫描数据库导致候选频繁项集数量庞大；③测试候选集需要花费大量的时间和资源。

虽然Apriori算法非常经典，但是它也存在一些不足之处。因此，研究者一直在对它进行改进。结合图书馆数据特点，笔者对Apriori算法进行了改进。针对冗余事务进行处理，在进行事务精简的同时也简化了候选集，通过提早删除冗余事务减少数据扫描量来提高效率。

（二）Apriori算法改进

数据挖掘系统需要通过迭代扫描数据库，在候选集中计算出频繁项集。在数据库中包括频繁项集和非频繁项集，随着项集的增多，迭代找出频繁项集，导致每次扫描整个存储系统的成本都非常高。为了节约扫描成本，可以从减少项集数量出发，在扫描整个集项之间删除非频繁集项，提高系统的扫描效率。此外，可以从候选集的属性出发，删除不可能产生候选集合的属性，从而减少候选集产生的数量。笔者对Apriori算法进行了优化，处理非频繁集和候选集：①在k-1项的频繁项集生产后，及时删除非频繁集，将会大大减少花费在候选集重组上的时间；②随着事务的减少，当k-1项频繁集合生成时不会再被计数。上面提到的改进思路和过程如逐步去除矩阵中的行和列。改进的大致思路和流程如下：

（1）将数据进行矩阵化，假如数据会被表示成关联矩阵——（M*N）的形式，根据Apriori算法的要求，首先计算项集的支持度，计算方法是对N列进行求和处理后，将计算结果与最小支持度的阈值进行比较，大于则为频繁项集；反之，则为非频繁集。(www.xing528.com)

（2）根据上一步骤中的计算结果，删除矩阵中表示非频繁集的所有列，去除非频繁集后的矩阵中，删除一行中值全是0或者一行中值为1的个数少于等于1的行。

（3）在完成前两步优化以后，需要对关联矩阵中的每一列执行以下三步操作：

第一，合并两列。这一步的操作是将关联矩阵（M*N）中的每列标示项元素进行比较，某两列中除第M个元素不同外，其他M-1个元素都相同。执行合并操作，首先保持先前相同的M-1个列元素表示不变，将两列中的两个不同元素新增加到相同元素之后。例如，两个标示项ABCDE和ABCDF，合并后变为ABCDEF。

第二，新标示的列是将先前两个对应的列通过逻辑和计算得到的。

第三，按照前两步中的步骤合并矩阵中所有的列，直到所有的列都被合并位置。最后，经过合并后的新关联矩阵每一列的长度都会加1。

迭代执行以上提到的三个步骤，将最初的关联矩阵合并成一个空矩阵或者关联矩阵只有一列。