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

1 / 13谈改进 的关联挖掘算法的实践应用内容摘要：介绍了数据挖掘技术在图书馆中的应用，并运用改进的 Apriori关联挖掘算法对安徽省图书馆自动化系统中读者流通库进行挖掘，并对挖掘出的结果及其意义进行评价，从而为图书馆读者管理、图书资源的采购提供决策支持。 关键词：数据挖掘 Apriori算法 图书馆管理 读者管理 数据挖掘技术在商业领域内的应用给图书馆带来了很大的启发。图书馆的数据库可以运用数据挖掘技术中的关联规则分析、聚类分析、决策树、时间序列分析等数据挖掘方法，以找出数据库中蕴藏的对于图书馆管理有用的潜在规则，并且通过描述和预测，为图书馆的图书采购、读者服务、馆藏目录设置等管理工作提供决策支持。 关联规则是与多数人想象的挖掘过程中最相近的一种数据挖掘形式，即寻找在同一事件中出现的不同项的相2 / 13关性。关联规则的研究有助于发现数据库中不同商品间的联系，找出顾客购买行为模式。在图书馆运用关联规则分析可以细分出读者群，根据其借阅情况提供不同的服务，为图书馆的管理决策提供参考。关联规则的核心算法是Apriori算法。 关联规则的基本概念及算法 挖掘流通借阅事务数据库中所有的关联规则的问题可以被划分成如下两个子问题： 找出所有具有最小支持度的项集，可用 Apriori算法来找出频繁项集。由频繁项集产生强关联规则，对于每一个频繁项集 I，找出其中所有的非空子集，然后，对于每一个这样的子集 a，如果 support与 support的比值大于最小置信度，则存在规则 a=。 关联规则算法 3 / 13关联规则的挖掘主要是在数据库中找出支持用户指定的最小支持度 S和最小置信度 C的关联规则，从而指导人们的一些管理决策。目前，关联规则的挖掘方法主要是找出数据库中的频繁项集，然后由频繁项集产生关联规则。Aprior算法 Apriori算法是一种挖掘布尔关联规则的频繁项集的算法，它主要是利用逐层搜索的迭代方法来寻找数据库中频繁出现的项集。主要步骤是：第一步，产生频繁 1-项集L1，扫描数据库 D，出现在 D中各个数据项的集合就是频繁1-项候选项集 C1，并统计出每个数据项出现的次数，次数大于最小支持计数定义的项的集合就是频繁 1-项集 L1；第K步，产生频繁 K-项集 Lk，利用上一步产生的频繁-项集Lk-1，与自己连接产生 K-项集候选集 Ck，扫描数据库事务库，计算 Ck中每个成员出现的次数，将小于最小支持度的候选项删除，最后产生频繁 K-项集。 算法：Apriori 使用根据候选生成的逐层迭代找出频繁项集 4 / 13输入：流通借阅数据库 D；最要支持度阈值 minsup 输出：D 中的频繁项集 L 算法代码： 1）L1 一所有频繁项集 1-项目集； 2）for 3）Ck=apriori_gen(Lk-1，minsupport） 4）for all CCt do 5）Ct=Subset 6）For all cCt do 7）+； 8） 5 / 139）Lk=cCk|support=minsup 10） 11）return L=所有的 Lk Apriori算法的第 1步找出频繁 1-项集的集合 L1。在第 210步中，Lk-1 用于产生候选 Ck，以找出Lk。Apriori 过程产生候选，第 3步使用 Apriori性质删除那些具有非频繁子集的候选，第 4步扫描数据库，第 5步使用 subset函数找出事务中的候选的所有子集，第 6步和第 7步对每个这样的候选累加计数。最后，所有满足最小支持度的候选会形成频繁项集 L。 Apriori-gen过程 Apriori-gen过程由 Lk-1产生第 K次迭代时的候选项集 Ck，该过程描述如下： For each itemset I1Lk-1 6 / 13For each itemset I2Lk-1 If (I12=I22 Then c=I1，I12，I1K-I，I2K-1） ； Ck=Ck U c； For If 从 Ck中删除 C； Return； 改进的 Apriori算法在图书馆的具体实现 7 / 13以安徽省图书馆某年度读者借阅事务库为例，可从图书馆借阅记录中挖掘出形如“读者-图书”强关联规则。首先要进行数据清洗，只保留属性概念中分层最低层的属性项，将同一个读者的所有借阅记录合并为一条记录。 算法思想 在读者借阅记录关联规则挖掘过程中有一些特殊的性质，因为每一个读者借阅记录的长度是固定的，即含有五个单项，前四个是属性值，最后一个是图书分类号，并且要挖掘的规则最后一项必须是图书分类号，且不能出现冲突的属性值或图书分类号。基于这些特殊性质，在数据挖掘中对 Apriori改进算法如下： 1）把压缩过的事务集读入内存； 2）扫描事务集，找到每一类频繁单项：即频繁的年龄段、频繁的学历、频繁的职称、频繁的职业、频繁的图书分类。 8 / 133） 把各类频繁的属性单项和频繁的图书分类单项连接成 2 - 候选频繁项集， k = 2。即生成年龄-图书类，学历-图书类，职业-图书类，职称-图书类，分别生成频繁2项集。 4） 检查 k-候选频繁项集，记录其支持度和前件的支持度。频繁项集的连接条件是前 n项是为读者属性项，且读者的属性项内容各不相同，最后一项为相同的图书分类项。 5） 输出置信度和支持度达到要求的频繁 k - 频繁项集。置信度为支持度除以前件的支持度。 6） 用得到 k - 频繁项集互相连接得到 k+1 - 候选频繁项集。通过剪枝，可减少连接的频繁项集的个数，提高程序运行的效率。下面的是剪枝连接的规则： a） 如果频繁项集 A 和 B 最后一项不同的时候不能连接。 b） 含有属于同一属性类别的不同单项，则不能连9 / 13接。 c） 频繁项集也不能和自身连接。d） 如果用 conf代表前件支持度，那么当 min /最小支持度 candidates； vector patterns； generate2candidates； / 生成候选 2项集 while） / 当候选项集为空时中止 verify_candidate；/ 过滤候选 k-1项集， 返回用于连接生成候选 k项集的列表，同时输出满足所有条件的规则 generate_k_candidates； / 连接生成候选 k项集，准备下一次循环 ； 10 / 13 生成 K项候选频繁集： inline void Apriori：generate_k_candidates for； +i）/ 遍历过滤后的候选 k-1项集， 两两连接 for； +j） if）/ 首先判断能否连接 ifmin / minSupport_ = minConf_） Items items = Items_method：join_Items；/ 连接得到 k项集， 保存到输出列表 _back） ； 11 / 13 算法评价 通过上述的介绍，可以看到本算法的思路基本上与Apriori算法保持一致，即它们的共同之处是通过扫描数据得到那些支持度不小于用户给定的最小支持度的频繁项集，但是又有不同之处就是在扫描数据库之前就进行了剪枝，在剪枝后再重新连接扫描数据库，减少了扫描的次数。 在算法效率上，通过数据压缩可将挖掘的数据一次性扫描进入内存中，避免了重复磁盘 I/O操作，没有压缩的数据不可能一次性读入内存，从而提高了计算效率；另通过数据压缩减少了每一项字符长度，特别是在比较两项是否相同的时候，需比较的字符数就少了很多，可以提高运算速度。通过使用数据压缩的方式，节省了内存，减少了候选集比较的时间，从而生成频繁项集速度将更快，同时加入了同属性列只能出现一次和后件必须相同的约束，使得连接次数大大减少，计算复杂度也降低了。在对图书12 / 13馆这样的大型数据库而言，这种节省对数据挖掘效率提高的作用就显而易见。 关联规则挖掘结果分析 根据以上关联规则挖掘结果分析，可以看到这种算法改进具有一定的实际意义： 通过研究读者群体的特征和关系，可以按年龄、学历、职业等因素对读者群体进行分类，也可以进行聚类，把读者群体细分，可以更清楚地了解读者的特点和需求；通过以上挖掘出的规则，进一步了解读者的特点，提高图书馆的吸引力，改进读者服务和提高读者的满意度；可以统计出读者的借阅频率、书籍流通趋势和周期，通过更科学地规划馆藏，提高图书的借阅率；通过分类，对重要的读者提供更优质的服务，从而使读者忠诚度更高；提高图书馆管理效率，提高决策水平，改进服务流程，使图书馆的服务流程更合理，最终提高管理效率；提