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

1、谈改进的关联挖掘算法的实践应用         09-08-02 10:59:00     作者：范生万鲍静    编辑：studa20内容摘要：本文介绍了数据挖掘技术在图书馆中的应用，并运用改进的Apriori关联挖掘算法对安徽省图书馆自动化系统中读者流通库进行挖掘，并对挖掘出的结果及其意义进行评价，从而为图书馆读者管理、图书资源的采购提供决策支持。 关键词：数据挖掘 Apriori算法 图书馆管理 读者管理 数据挖掘技术在商业领域内

2、的应用给图书馆带来了很大的启发。图书馆的数据库可以运用数据挖掘技术中的关联规则分析、聚类分析、决策树、时间序列分析等数据挖掘方法，以找出数据库中蕴藏的对于图书馆管理有用的潜在规则，并且通过描述和预测，为图书馆的图书采购、读者服务、馆藏目录设置等管理工作提供决策支持。 关联规则是与多数人想象的挖掘过程中最相近的一种数据挖掘形式，即寻找在同一事件中出现的不同项的相关性。关联规则的研究有助于发现数据库中不同商品间的联系，找出顾客购买行为模式。在图书馆运用关联规则分析可以细分出读者群，根据其借阅情况提供不同的服务，为图书馆的管理决策提供参考。关联规则的核心算法是Apriori算法。 关联规则的基本概念

3、及算法 挖掘流通借阅事务数据库中所有的关联规则的问题可以被划分成如下两个子问题： 找出所有具有最小支持度的项集（即频繁项集），可用Apriori算法来找出频繁项集。由频繁项集产生强关联规则，对于每一个频繁项集I，找出其中所有的非空子集，然后，对于每一个这样的子集a，如果support（I）与support（a）的比值大于最小置信度，则存在规则a=>（I-a）。 （一）关联规则算法 关联规则的挖掘主要是在数据库中找出支持用户指定的最小支持度S和最小置信度C的关联规则，从而指导人们的一些管理决策。目前，关联规则的挖掘方法主要是找出数据库中的频繁项集，然后由频繁项集产生关联规则。 （二）Apr

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

5、项集 输入：流通借阅数据库D；最要支持度阈值minsup 输出：D中的频繁项集L 算法代码： 1）L1一所有频繁项集1-项目集； 2）for（k=2；Lk，k+） 3）Ck=apriori_gen(Lk-1，minsupport） 4）for all CCt do 5）Ct=Subset（Ck，T） 6）For all cCt do 7）c.count+； 8） 9）Lk=cCk|support（c）>=minsup 10） 11）return L=所有的Lk Apriori算法的第1步找出频繁1-项集的集合L1。在第210步中，Lk-1用于产生候选Ck，以找出Lk。Apriori过程产

6、生候选，第3步使用Apriori性质删除那些具有非频繁子集的候选，第4步扫描数据库，第5步使用subset函数找出事务中的候选的所有子集，第6步和第7步对每个这样的候选累加计数。最后，所有满足最小支持度的候选会形成频繁项集L。 Apriori-gen过程 Apriori-gen过程由Lk-1产生第K次迭代时的候选项集Ck，该过程描述如下： For each itemset I1Lk-1 For each itemset I2Lk-1 If （I11=I21）(I12=I22（I1K-2=I2K-2）（I1K-1 =I2 K-2）（I1K-I=I2K-1） Then c=I1，I12，I1K-I

7、，I2K-1）； Ck=Ck U c； For（c的每个包含k-1个项目的子集s） If（s不属于Fk-1） 从Ck中删除C； Return（Ck）； 改进的Apriori算法在图书馆的具体实现 以安徽省图书馆某年度读者借阅事务库为例，可从图书馆借阅记录中挖掘出形如“读者-图书”强关联规则。首先要进行数据清洗，只保留属性概念中分层最低层的属性项，将同一个读者的所有借阅记录合并为一条记录。 （一）算法思想 在读者借阅记录关联规则挖掘过程中有一些特殊的性质，因为每一个读者借阅记录的长度是固定的，即含有五个单项，前四个是属性值，最后一个是图书分类号，并且要挖掘的规则最后一项必须是图书分类号，且不能出

8、现冲突的属性值或图书分类号。基于这些特殊性质，在数据挖掘中对Apriori改进算法如下： 1）把压缩过的事务集读入内存； 2）扫描事务集，找到每一类频繁单项：即频繁的年龄段、频繁的学历、频繁的职称、频繁的职业、频繁的图书分类。 3） 把各类频繁的属性单项和频繁的图书分类单项连接成 2 - 候选频繁项集， k = 2。即生成年龄-图书类，学历-图书类，职业-图书类，职称-图书类，分别生成频繁2项集。 4） 检查k-候选频繁项集，记录其支持度和前件的支持度。频繁项集的连接条件是前n项是为读者属性项，且读者的属性项内容各不相同，最后一项为相同的图书分类项。 5） 输出置信度和支持度达到要求的频繁 k - 频繁项集。置信度为支持度除以前件的支持度。 6） 用得到k - 频繁项集互相连接得到k+1 - 候选频繁项集。通过剪枝，可减少连接的频繁项集的个数，提高程序运行的效率。下面的是剪枝连接的规则： a） 如果频繁项集A 和 B 最后一项不同的时候不能连接。 b） 含有属于同一属性类别的不同单项