基于改进Apriori算法在图书馆数据挖掘中应用分析

李华群

(河南理工大学 图书馆，河南 焦作 484000)

关联规则挖掘就是从大量的数据中挖掘出有价值描述数据项之间相互联系的有关知识，作为数据挖掘中最经典的方法之一，被广泛应用于各行各业中。如应用到商业零售行业，分析顾客的购买特性来指导商品的排架、商品定价、商品的采购；应用到金融和保险服务行业，通过分析大量的金融数据，为投资活动建立贸易和风险模型，指导股票选择、货币交易等；应用到科学研究领域，可以从大量的、漫无头绪的科学数据中提炼出有用的信息；还被应用于电信网络管理、医疗数据挖掘、制造业故障诊断等其他应用领域[1]。目前高校图书馆每天会产生大量的图书流通数据，运用关联规则分析也可以从大量的读者历史借阅数据中挖掘出有用的信息和隐含信息来指导图书馆服务和管理工作。

近年来，越来越多学者将关联规则Apriori算法应用到图书馆数据挖掘中。张雪艳[2]将Apriori算法的关联规则应用到图书馆资源配置中，不仅可简化采访工作，还可以更好地进行读者导读服务；陈淑英[3]等将关联规则应用到高校图书馆图书推荐服务中，通过对不同专业不同用户群体在不同年级时的图书关联规则分析，探索有效和有针对性的图书推荐服务策略；高晟[4]等将关联规则与贝叶斯网络相结合的高校图书馆个性化图书推荐服务；文芳[5]等提出基于FP-growth关联规则的图书馆数据快速挖掘算法研究，通过改进关联规则算法，在运行效率方面有了明显的提升。通过大量研究，发现关联规则应用到图书馆数据挖掘中，有明显的实际效果和意义，但因传统的关联规则Apriori算法本身存在一些结构缺点，如会产生大量的频繁项集，每次搜索项集都要在数据库中访问，造成了非常大的内存消耗和I/O过载，如果能减少数据库扫描的次数，则可以大大提高关联规则的运行效率。基于此，笔者对关联规则Apriori算法进行改进，将矩阵思想运用进来，并对算法进行优化，减少扫描次数，优化生成频繁项集的步骤，以此达到提高运行效率的目的。

1 Apriori算法简介

Apriori算法是关联规则所需频繁项集的基本算法。是根据有关频繁项集特性的先验知识而命名的。该算法利用了层次顺序搜索的循环方法来完成频繁项集的挖掘工作。具体步骤就是：首先找出频繁1-项集，记为L1；然后利用L1来挖掘L2，得到频繁2-项集；如此不断循环下去直到无法发现更多的频繁k项集为止，每挖掘一层都需要扫描整个数据库一遍。

Apriori算法将关联规则的挖掘问题可以分为两个子问题：第一步是找出事务数据库中所有大于等于用户指定的最小支持度的数据项集；第二步是利用频繁项集生成所需要的关联规则，根据用户设定的最小置信度进行取舍，最后得到强关联规则。其中第一步是最核心要解决的问题，通过迭代方法每挖掘一层都需要扫描整个数据库来求出事务集中所有的频繁项集[6]。

因Apriori算法采用了逐层搜索迭代的方法，虽然算法简单明了，没有复杂的理论推导，也易于实现，但有一些难以克服的缺点：①多次扫描事务数据库，需要很大的I/O负载。对于第k次循环，候选集Ck中的每个元素都必须通过扫描数据库一次来验证其是否加入Lk。假如有一个频繁项集包含10个项的话，那么就至少需要扫描事务数据库10遍。 ②可能产生庞大的候选集。候选项集合在项目数过多时产生的候选集呈指数型增长。特别是频繁2-项集，例如105的1-项集就有可能产生接近109个元素的2-候选集。如此大的候选集对时间和存储空间都是一种挑战，严重影响计算效率[7]。

2 基于改进的Apriori算法

2.1 基本思想

Apriori算法中，事务数据存放在数据库，为了获取候选集，需要多次扫描事务数据库，导致I/O负载过大，另外由Lk-1得到Ck的过程，会导致产生大量的没有实际操作意义的候选集，为了改善算法的运行效率，采用矩阵方式存储事务项和数据项。

基于矩阵的关联规则数据挖掘算法，若事务数据库D含有n个事务(T1，T2，…，Tn)，m个项(I1,I2,…,Im)，由事务数据库D映射成对应的布尔矩阵M形式如图1[8]。

图1 事务数据库对应的矩阵M

首先是将事务与数据项对应的关系利用多维矩阵的形式表达出来，对事务项进行量化，用1或0表示当前事务项是否存在，若第i个项集在第j个事务中，则矩阵第i行第j列的值dij为1，否则为0。

其次是对矩阵进行修剪、压缩，先对每个行向量进行求和，并依照支持度大小降序排列，其和小于最小支持度的将对应的行向量删除；再对每个列向量进行求和，将一个事务小于k项的事务项删除，得到新的矩阵M1。

然后对矩阵M1中m行任取k行形成k项集Ck={Ii1，Ii2，…，Iik}，进行逻辑与运算，其支持度为：

最后，判断所有支持度，将不小于支持度的项，加入频繁项集Lk中，直到不能产生频繁项集，算法至此结束，所有频繁项集为L=∪Lk。

2.2 基于改进的Apriori算法主要步骤

如表1，第一列分别代表事务项T100、T200、T300、T400、T500、T600、T700，第二列分别代表各事务的数据项。

表1 事务型数据库

第一步：首先将此表构造成一个矩阵M0，扫描该事务数据库，存在数据项被初始化为1，否则为0；如表2。

表2 初始矩阵M0

第二步：行压缩，删除矩阵中出现次数小于最小支持度的单个数据项。设定最小支持度为1。因关联规则里的频繁项集的所有非空子集必然也是频繁项集，因此可以对出现次数小于等于最小支持度的数据项进行删除。分别对以上矩阵的每个行向量进行求和，并依照支持度大小降序排序，得到数据项D出现次数≤1，删除数据项D，对矩阵进行修剪压缩。

第三步：列压缩，删除矩阵中事务数量少于等于(k-1)的事务，设K=3，因为一个事务不足K个项，他不可能包含k-频繁项集，所以删除事务T500、T600、T700后形成的新矩阵M1如表3。

表3 新矩阵M1

第四步：对新矩阵M1中的各行进行矩阵逻辑与运算，得出i1∧i2={1110，3}，i2∧i3={0111，3}，i1∧i3={0110，2}，i2∧i4={0011，2}，i1∧i4={0010，1}，i3∧i4={0010，1}，并依照支持度降序，删除支持度≤1的项，得到频繁2-项集L2={AB，BC，AC，BE}。

第五步：根据频繁项集的所有非空子集都必须是频繁的，将频繁2项集进行连接操作，同时扫描矩阵M1，对连接各行进行逻辑与运算，得出i1∧i2∧i3={0110，2}，i2∧i3∧i4={0011，2}，i1∧i2∧i4={0010，1}，删除支持度≤1的项，得到频繁3-项集L3={ABC，BCE}。生成K-项集，停止本次矩阵逻辑与运算。

3 改进Apriori算法在图书馆数据挖掘中应用

3.1 实验环境

为了对文中提出的改进的Apriori算法进行分析和验证， 进行了仿真测试。硬件环境为： Intel Core i5-4590，8G Hz 处理器，4G 内存，1T 硬盘。软件环境为： Windows 7操作系统，MatlabR2016b仿真软件。

3.2 数据预处理

本实验采用了某高校图书管理系统中的数据集。该数据集包含2019年的计算机类专业1 200名本科生4 365条图书借阅历史日志记录。首先对原始数据进行数据预处理，仅保留有用数据列，如读者号、索书号、题名、年级等，数据清理和集成后数据入表4。

表4 处理后图书馆借阅数据记录

3.3 算法运行

笔者依据改进关联规则的算法步骤，对读者借阅图书的索书号与借阅图书的索书号进行数据挖掘关联规则分析，经过反复试验，设置最小支持度为0.5%，最小置信度为10%，K=3。首先将读者号和借阅书籍的索书号对应关系如表5，生成相应的布尔矩阵，行矩阵代表索书号，列矩阵代表每个读者号。

表5 索书号和读者号对应关系

再在计算生成频繁项集之前，先对矩阵进行修剪和压缩，减少隐含信息量少的记录，保留蕴含有重要信息的行向量和列向量，减少数据的存储，获得需要较小存储空间的新矩阵，再对任意各行向量之间求逻辑与，生成候选项集，最后得到满足条件的频繁项集如表6。

表6 关联规则

由此得出的关联规则可知，借阅了Java类书和C、C++语言基础书的，有29.4%的学生都借阅了HTML+Java网页制作类书；借阅了Java类的书有27.8%的学生都借阅了Python学习类书籍，有30%学生还借阅了Android程序设计与开发类书；借阅了C语言基础类书的有23.8%的学生还借阅了叙事类故事性强的文学书，而且学生大多分布在大一大二年级。依据此分析结果特性，我们可根据不同年级推荐相应感兴趣的书籍，在大一大二期间，主要以基础计算机语言学习和休闲类书籍为主，大三大四更以专业性针对性很强的计算机类书籍为主，主要集中在热门的Java类、python、网页设计、Android程序设计为主。

通过以上分析，改进的Apriori算法可以对读者的历史借阅图书的索书号进行数据挖掘关联分析，挖掘出读者需求的隐含信息，可以指导图书馆人员提供主动化、个性化图书借阅服务，方便读者依据自己的爱好和习惯快速找到符合需求的书籍，避免盲目“逛馆”的情况。

3.4 算法性能分析

使用相同的最小支持度和置信度， 随着事务数不断增加的情况下，比较传统的关联规则Apriori算法和基于改进的关联规则Apriori算法执行时间，如图2所示，可知，当事务数比较小时，两者算法运行时间相差无几， 但当事务数逐渐增多时，因传统算法每次产生频繁项集时都需要重新对数据库都扫描一遍，而改进算法仅在生成矩阵时扫描一次数据库，这样其效率大大提高，明显优于传统的关联规则算法。

图2 不同事务数两种算法执行时间对比

4 结束语

笔者利用高效图书馆的历史借阅数据，结合改进的关联规则Apriori算法，从中挖掘出不同读者对借阅书籍索书号的关联规则，发现了一些借阅书籍的共同喜好，分析出的关联规则不仅可以快速帮忙读者获取自己喜好和符合需求的书籍，还可以帮助图书馆工作人员采取主动化、个性化推荐信息服务。读者在检索图书时，可以优先推荐强关联规则的图书，快速确定符合自己需求的书籍，缩短借阅时间，也提高了热门书籍的借阅率。笔者分析了改进的单维关联规则，对读者借阅的图书索书号与索书号之间进行了关联挖掘分析，挖掘出的信息还是有限的，在后续的研究中，应从多维的角度，比如借阅的时间与借阅分类号之间的关联分析等多个因素加入进行更全面关联分析，以此来深入挖掘图书馆更多复杂数据信息，为读者提供更快捷、更符合需求的服务，为图书馆个性化推荐服务提供更多的理论指导。