谈改进的Ａｐｒｉｏｒｉ关联挖掘算法的实践应用

范生万　鲍　静

中图分类号：TP311 文献标识码：A

内容摘要：本文介绍了数据挖掘技术在图书馆中的应用，并运用改进的Apriori关联挖掘算法对安徽省图书馆自动化系统中读者流通库进行挖掘，并对挖掘出的结果及其意义进行评价，从而为图书馆读者管理、图书资源的采购提供决策支持。

关键词：数据挖掘 Apriori算法 图书馆管理 读者管理

数据挖掘技术在商业领域内的应用给图书馆带来了很大的启发。图书馆的数据库可以运用数据挖掘技术中的关联规则分析、聚类分析、决策树、时间序列分析等数据挖掘方法，以找出数据库中蕴藏的对于图书馆管理有用的潜在规则，并且通过描述和预测，为图书馆的图书采购、读者服务、馆藏目录设置等管理工作提供决策支持。

关联规则是与多数人想象的挖掘过程中最相近的一种数据挖掘形式，即寻找在同一事件中出现的不同项的相关性。关联规则的研究有助于发现数据库中不同商品间的联系，找出顾客购买行为模式。在图书馆运用关联规则分析可以细分出读者群，根据其借阅情况提供不同的服务，为图书馆的管理决策提供参考。关联规则的核心算法是Apriori算法。

关联规则的基本概念及算法

挖掘流通借阅事务数据库中所有的关联规则的问题可以被划分成如下两个子问题：

找出所有具有最小支持度的项集（即频繁项集），可用Apriori算法来找出频繁项集。由频繁项集产生强关联规则，对于每一个频繁项集I，找出其中所有的非空子集，然后，对于每一个这样的子集a，如果support（I）与support（a）的比值大于最小置信度，则存在规则a=>（I-a）。

（一）关联规则算法

关联规则的挖掘主要是在数据库中找出支持用户指定的最小支持度S和最小置信度C的关联规则，从而指导人们的一些管理决策。目前，关联规则的挖掘方法主要是找出数据库中的频繁项集，然后由频繁项集产生关联规则。

（二）Aprior算法

Apriori算法是一种挖掘布尔关联规则的频繁项集的算法，它主要是利用逐层搜索的迭代方法来寻找数据库中频繁出现的项集。主要步骤是：第一步，产生频繁1-项集L₁，扫描数据库D，出现在D中各个数据项的集合就是频繁1-项候选项集C1，并统计出每个数据项出现的次数，次数大于最小支持计数（预先）定义的项的集合就是频繁1-项集L₁；第K步，产生频繁K-项集L_k，利用上一步产生的频繁（K-1）-项集L_k-1，与自己连接产生K-项集候选集C_k，扫描数据库事务库，计算C_k中每个成员出现的次数，将小于最小支持度的候选项删除，最后产生频繁K-项集。

算法：Apriori使用根据候选生成的逐层迭代找出频繁项集

输入：流通借阅数据库D；最要支持度阈值minsup

输出：D中的频繁项集L

算法代码：

1）L₁一所有频繁项集1-项目集；

2）for（k=2；L_k≠φ，k++）{

3）C_k=apriori_gen(L_k-1，minsupport）

4）for all C∈C_tdo{

5）C_t=Subset（C_k，T）

6）For all c∈C_tdo

7）c.count++；

8）}

9）L_k={c∈C_k|support（c）>=minsup}

10）}

11）return L={所有的L_k}

Apriori算法的第1步找出频繁1-项集的集合L₁。在第2~10步中，L_k-1用于产生候选C_k，以找出L_k。Apriori过程产生候选，第3步使用Apriori性质删除那些具有非频繁子集的候选，第4步扫描数据库，第5步使用subset函数找出事务中的候选的所有子集，第6步和第7步对每个这样的候选累加计数。最后，所有满足最小支持度的候选会形成频繁项集L。

Apriori-gen过程

Apriori-gen过程由L_k-1产生第K次迭代时的候选项集C_k，该过程描述如下：

For each itemset I₁∈L_k-1

For each itemset I₂∈L_k-1

If （I₁[1]=I₂[1]）∧(I₁[2]=I₂[2]∧…∧（I₁[K-2]=I₂[K-2]）∧（I₁[K-1 ]=I₂[K-2]）∧（I₁[K-I]=I₂[K-1]）

Then {c=I[1]，I₁[2]，…I₁[K-I]，I₂[K-1]）；

C_k=C_kU c；

For（c的每个包含k-1个项目的子集s）{

If（s不属于F_k-1）

从C_k中删除C；

}

Return（C_k）；

改进的Apriori算法在图书馆的具体实现

以安徽省图书馆某年度读者借阅事务库为例，可从图书馆借阅记录中挖掘出形如“读者-图书”强关联规则。首先要进行数据清洗，只保留属性概念中分层最低层的属性项，将同一个读者的所有借阅记录合并为一条记录。

（一）算法思想

在读者借阅记录关联规则挖掘过程中有一些特殊的性质，因为每一个读者借阅记录的长度是固定的，即含有五个单项，前四个是属性值，最后一个是图书分类号，并且要挖掘的规则最后一项必须是图书分类号，且不能出现冲突的属性值或图书分类号。基于这些特殊性质，在数据挖掘中对Apriori改进算法如下：

1）把压缩过的事务集读入内存；

2）扫描事务集，找到每一类频繁单项：即频繁的年龄段、频繁的学历、频繁的职称、频繁的职业、频繁的图书分类。

3） 把各类频繁的属性单项和频繁的图书分类单项连接成 2 - 候选频繁项集， k = 2。即生成年龄-图书类，学历-图书类，职业-图书类，职称-图书类，分别生成频繁2项集。

4） 检查k-候选频繁项集，记录其支持度和前件的支持度。频繁项集的连接条件是前n项是为读者属性项，且读者的属性项内容各不相同，最后一项为相同的图书分类项。

5） 输出置信度和支持度达到要求的频繁 k - 频繁项集。置信度为支持度除以前件的支持度。

6） 用得到k - 频繁项集互相连接得到k+1 - 候选频繁项集。通过剪枝，可减少连接的频繁项集的个数，提高程序运行的效率。下面的是剪枝连接的规则：

a） 如果频繁项集A 和 B 最后一项不同的时候不能连接。

b） 含有属于同一属性类别的不同单项，则不能连接。

c） 频繁项集也不能和自身连接。

d） 如果用conf代表前件支持度，那么当min （ A.conf， B.conf）/最小支持度<最小置信度时，不能连接 A，B。

e） 其它情况可以连接。

7） k ++， 如果生成的候选频繁项集数目不为0，转4），否则结束。

本算法主要改进是步骤6， 这是经典的Apriori算法没有的。其他的连接过程可以参阅Apriori的连接。本文通过设置最小置信度阈值以找出强关联规则，令图书类型为每条规则后件，读者属性为每条规则前件，最后得到关联规则。

（二）程序实现

// apriori算法的程序

void Apriori::Do（）

{

vector candidates；

vector patterns；

generate2candidates（candidates）； // 生成候选2项集

while（!candidates.empty（）） // 当候选项集为空时中止

{ verify_candidate（candidates， patterns）；// 过滤候选k-1项集， 返回用于连接生成候选k项集的列表，同时输出满足所有条件的规则

generate_k_candidates（patterns，candidates）； // 连接生成候选k项集， 准备下一次循环

patterns.clear（）；

}

}

生成K项候选频繁集：

inline void Apriori：：generate_k_candidates（const vector&patterns，

vector&candidates）

{

for（int i = 0； i < patterns.size（）； ++i）// 遍历过滤后的候选k-1项集， 两两连接

for（int j = i+1； j < patterns.size（）； ++j）

if（Items_method：：Is_compatible_Items（patterns[i].items_，patterns[j].items_））// 首先判断能否连接

if（（double）min（patterns[i].freq_，patterns[j].freq_） / minSupport_ >= minConf_）

{Items items = Items_method：：join_Items（patterns[i].items_，patterns[j].items_）；// 连接得到k项集， 保存到输出列表

candidates.push_back（ItemsCounter（items，0，0））；

}

}

（三）算法评价

通过上述的介绍，可以看到本算法的思路基本上与Apriori算法保持一致，即它们的共同之处是通过扫描数据得到那些支持度不小于用户给定的最小支持度的频繁项集，但是又有不同之处就是在扫描数据库之前就进行了剪枝，在剪枝后再重新连接扫描数据库，减少了扫描的次数。

在算法效率上，通过数据压缩可将挖掘的数据一次性扫描进入内存中，避免了重复磁盘I/O操作，没有压缩的数据不可能一次性读入内存，从而提高了计算效率；另通过数据压缩减少了每一项字符长度，特别是在比较两项是否相同的时候，需比较的字符数就少了很多，可以提高运算速度。通过使用数据压缩的方式，节省了内存，减少了候选集比较的时间，从而生成频繁项集速度将更快，同时加入了同属性列只能出现一次和后件必须相同的约束，使得连接次数大大减少，计算复杂度也降低了。在对图书馆这样的大型数据库而言，这种节省对数据挖掘效率提高的作用就显而易见。

（四）关联规则挖掘结果分析

根据以上关联规则挖掘结果分析，可以看到这种算法改进具有一定的实际意义：

通过研究读者群体的特征和关系，可以按年龄、学历、职业等因素对读者群体进行分类，也可以进行聚类，把读者群体细分，可以更清楚地了解读者的特点和需求；通过以上挖掘出的规则，进一步了解读者的特点，提高图书馆的吸引力，改进读者服务和提高读者的满意度；可以统计出读者的借阅频率、书籍流通趋势和周期，通过更科学地规划馆藏，提高图书的借阅率；通过分类，对重要的读者提供更优质的服务，从而使读者忠诚度更高；提高图书馆管理效率，提高决策水平，改进服务流程，使图书馆的服务流程更合理，最终提高管理效率；提高读者兴趣度，改善采购水平和质量，购进读者需要的书籍；通过科学规划馆藏目录，提高馆藏借阅率。

总之，Apriori算法能有效地进行关联规则的数据挖掘。本文根据图书数据挖掘中最后一项是固定的图书分类的特点，提出的改进Apriori算法，是根据图书馆数据特点进行连接和剪枝，生成频繁项集，进一步缩小了挖掘的范围，提高了数据挖掘的效率，使得到的规则更加科学合理。

参考文献：

1.朱小栋，郑诚等.关联规则的哈希修剪算法研究.安徽大学学报（自然科学版），2005（7）

2.佟强，周园春，阎保平.关联规则挖掘算法.微电子学与计算机，2005（6）