０ 一 计算机光盘软件与应用 工程技术 Ｃｏｍｐｕｔｅｒ ＣＤ Ｓｏｆｔｗａｒｅ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ ２０１２年第１６期 基于用户兴趣度的关联规则挖掘算法 曹静 日Ｒ，． （湖北文理学院数学与计算机科学学院，湖北襄阳４４１０５３） 摘要：经典Ａｐｒｉｏｒｉ关联规则挖掘算法需要多次扫描整个事务数据库，产生庞大的候选集。文章提出基于Ａｐｒｉｏｒｉ的 ＩＯＩＲ算法，算法根据用户的兴趣，有选择的挖掘数据库，并通过对每个候选集进行支持数排序，从而减少扫描的数据量 和扫描的时间。 关键词：关联规则；数据挖掘；ＩＯＩＲ算法；兴趣度 中图分类号：ＴＰ３１１．１３ 文献标识码：Ａ 文章编号：１００７—９５９９（２０１２）１６—０１７０—０２ １ 前言 关联规则挖掘是数据挖掘技术的一个重要分支，帮助 发现大量数据库中项集之间的关联关系，以获得有用的帮 助用户决策的信息。经典Ａｐｒｉｏｒｉ关联规则挖掘算法需要多 次扫描整个事务数据库，产生庞大的候选集，并且需要很 大的Ｉ／Ｏ负载，生成的关联规则只有部分符合用户的需求。 目前有了很多针对不同条件的改进算法，主要是从减少扫 描次数、减少候选项集等方面优化。ＦＰ．ｔｒｅｅ算法只进行２ 次数据库扫描，不使用候选集，直接压缩数据库成一个频 繁模式树，最后通过这棵树生成关联规则，算法要递归生 成条件数据库和条件ＦＰ．ｒｔｅｅ，所以内存开销大，而且只能 用于挖掘单维的布尔关联规则。频繁闭合模式ｆｆｒｅｑｕｅｎｔ ｃｌｏｓｅｄ ｐａＵｅｍ）的相关挖掘算法由于每次扫描都要生成闭 合，且要对闭合进行计数，生成子集，并与新生成的闭合 进行比较判断，同样存在占用较大内存空间，影响结果生 成时间。 关联规则兴趣度是从主观或客观方面约束生成规则的 条件，从而减少时间或空间开销。客观的度量主要考虑数 据的统计显著性，如关联规则挖掘中用到的支持度、置信 度和提升度。主观的度量综合考虑原始数据和用户的领域 知识。论文提出ＩＯＩＲ算法（Ｉｎｔｅｒｅｓｔｉｎｇ Ｏｒｄｅｒ Ｉｔｅｍｓ Ｒｕｌｅ）， 提取用户感兴趣的事务进行关联规则挖掘，减少了频繁项 集的数量及空间开销。 ２ ｌ０ｌＲ算法 ２．１优化Ａｐｒｉｏｒｉ算法设计思路 在关联规则的实际数据挖掘中，事务数据库规模通常 较大，扫描事务数据库和产生频繁项目集是非常耗时的。 因此尽可能剔除无用的候选集和减少事务数据库扫描频率 是提高算法效率的关键。 由事务数据库中的事务是项目的集合且集合具有无序 性，可得在同一事务中，是不必考虑项目之间的顺序的。 如事务Ｔ的项目集合（Ａ，Ｂ，Ｃ，Ｄ，Ｅ）与｛Ｅ，Ａ，Ｂ，Ｄ，Ｃ）是相 同的。 在Ａｐｒｉｏｒｉ算法执行中对每次获取的Ｋ＿项候选集进行 排序，可用隔板的方法把不满足最小支持度的项集隔去， 剩下的就都是满足条件的项集了。 ２．２优化算法的设计步骤 先根据用户的兴趣，选择出用户感兴趣的数，并在生成 Ｋ－１项集过程中，对Ｋ－１项集进行按照支持数的值从小到 大排序，那么在ＬＫ－１连接生成候选集ＣＫ，ＣＫ也进行按 照支持数的值从小到大排序并采用支持度剪枝后，将使得 支持度小的频繁Ｋ．项集排在前面，依此类推，这样与 Ａｐｒｉｏｒｉ算法相比较就提升了速度。步骤如下： （１）用户根据自已的兴趣设置参数。这样扫描数据库就 可以只提取出用户感兴趣的一部分数据集。 （２）根据用户定义，在第一次扫描事务后，对每一个事务 进行计数，并删除长度小于最小支持度（ｓｕｐｐｏｒｔ）的当前事务， 因为该事务不会对生成频繁２．选项集起作用。以此类推。 在对每次事务扫描后，对每一个事务进行计数，并删除长 度小于最小支持度（ｓｕｐｐｏｒｔ）的当前事务，因为该事务不会对 以后生成的下层候选项集产生作用。如此，压缩了事务，提高 了效率，减少了Ｉ／Ｏ的开销。 （３）对Ｋ－１项集进行按照支持数的值从小到大排序． （４）由Ｋ－１．项集连接成Ｋ．项集并重复（２），（３）操作，直到 找出所有的频繁集。 （５）如果用户对挖掘的结果不满意，则重新设定参数，然 后重复（１）到（３）步骤完成操作。 ＩＯＩＲ算法实现： Ｗｉｔｈ（Ｄ１，Ｄ２…。１ ／／用户设置选择感兴趣 的项 Ｍｉｎｉｎｇ（）｛ Ｆｒｏｍ ＴＩＤ １ ｔＯ １厂ＩＤ２ ｝ ／／从事务数据库ＴＩＤ１中筛选出用户感兴趣 的事务数据放在ＴＩＤ２中 ＡｐｒｉｏｒｉＯ｛．．．．．．．．． Ｏｒｄｅｒｂｙ（ＣＫ－１）（ ＦＯＲ ａｌｌ ｉｔｅｍｓｅｔ Ｒ［ｘ］∈Ｌｋ一１ ＤＯ ｂｅｇｉｎ Ｍ＝Ｋ－１； ＦｏｒＩ＝０ＴｏＭ－１ Ｄｏｂｅｇｉｎ ｆ Ｆｏｒ Ｊ＝０ＴｏＭ—Ｉ一１ Ｄｏｂｅｇｉｎｆ ｌｆＲ［Ｊ＋１］＜Ｒ［Ｊ］Ｔｈｅｎ ｂｅｇｉｎ Ｔｅｍｐ Ｒ【Ｊ＋１］； Ｒ［Ｊ＋１］＝Ｒ［Ｊ］； Ｒ［Ｊ］＝Ｔｅｍｐ； Ｅｎｄｉｆ ｝｝）／／按照支持数的值对Ｋ＿１项集从ｄ，Ｎ大排序 ｝ ３实验结果分析 为了验证ＩＯＩＲ算法的性能，用ＪＡＶＡ分别实现Ａｐｆｉｏｆｉ —ｌ７０— 计算机光盘软件与应用 ２０１２年第ｌ６期 Ｃｏｍｐｕｔｅｒ ＣＤ Ｓｏｆｔｗａｒｅ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ 工程技术 算法和ＩＯＩＲ算法。硬件设备配置相同。用两种方式比较： １５００，２０００，２５００，５０００，１００００，２００００，项目数量为３０。 事务数据库中包含事务的个数分别１００，５００，１０００， 表１给出在最小支持度为４０％的运行时间对比。 表１．两种算法运行结果比较（单位：秒） １００ Ａｐｒｉｏｒｉ ＩｏＩＲ ０．１１ ０．１０ ５００ ０．２３ ０．２１ １０００ Ｏ＿３７ ０－３５ １５００ ０．４６ ０．４５ ２０００ Ｏ．５５ ０．５３ ２５００ ０．６７ ０．６４ ５０００ ０．７５ ０．７１ １００００ ０．８９ ０．８３ ２００００ ０．９７ ０．９１ 设置不同的支持度：１０％、２０％、３０％、４０％、５０％、６０％、７０％、８０％、９０％，表２给出了运行结果对比。 表２．不同支持度下两种算法运行结果比较（单位：秒） ｌ０％ ２０％ ３０％ ４０％ ５０％ ６０％ ７０％ ８Ｏ％ ９０％ Ａｐｒｉｏｒｉ算法 ＩＯＩＲ算法 ０．８９ ０．８８ ０．７６ ０．７４ ０．６４ ０．６３ ０．５５ ０．５４ ０．４３ ０．４１ ０．３７ ０－３６ ０Ｉ３ｌ ０．３０ ０．２２ Ｏ．２１ ０．１１ ０．０９ 由运行结果可以看出，在事务逐渐增多时，ＩＯＩＲ的优 势较明显；在不的支持度下也有一定的优势。 参考文献： ［１］Ｈａｒｔ Ｊ，Ｐｅｉ Ｊ，ａｎｄ Ｙｉｎ Ｙ．Ｍｉｎｉｎｇ ｆｒｅｑｕｅｎｔ ｐａｔｔｅｒｎｓ ｗｉｔｈｏｕｔ ｃａｎｄｉｄａｔｅ ｇｅｎｅｒａｉｔｏｎ［Ｊ］．Ｉｎ ＳＩＧＭＯＤ’００．Ｌｉｎｋ Ｍｉｎｉｎｇ，２０００． ４ ｌ０ＩＲ算法的改进方向 实验表明，ＩＯＩＲ算法适合在一定规模的事务数据库中 挖掘关联规则，对于在算法中要产生大量候选项集的情况 ［２］Ｇｅｎｇ Ｌ，Ｈａｍｉｌｔｏｎ Ｈ Ｊ．Ｉｎｔｅｒｅｓｔｉｎｇｎｅｓｓ ｍｅａｓｕｒｅｓ ｆｏｒ 下具有明显的效率优势。关联规则挖掘实际应用非常广泛， ｄａｔａ ｍｉｎｉｎｇ：ａ ｓｕｒｖｅｙＵ］．ＡＣＭ Ｃｏｍｐｕｔｉｎｇ Ｓｕｒｖｅｙｓ，２００６，３８０）： 如何进一步优化算法并让其适合在更多条件下，如同时挖 １—３２．掘一个事务项在多个不同属性、层次等方面的关联规则挖 掘等应用，是下一步的主要研究工作。 项目资助：湖北文理学院大学生科研项目 二维码为图书馆实现跨媒体的服务提供了可能，可以 的虚拟通道。图书馆可以在ＯＰＡＣ检索的检索结果中包含 改变图书馆的传统服务方式，在各种服务载体之间建立有 二维码，其中包括与读者获取图书密切相关的字段，如书 效通道。手机二维码目前已经得到广泛应用，图书馆应该 名、作者、出版社、索取号以及架位信息。读者使用手机 根据本馆特色，逐步推出基于二维码的服务方式，促进图 拍摄二维码即可获取相关信息，然后可以到书架上查找图 书。 （上接第１６９页） 书馆实现跨媒体的服务，为用户提供极大方便。 随着手机上网、手机应用等基于手机的服务已经逐步 融入人们的生活，成为人们获取信息的一个重要途径。图 二维码技术的特点之一是信息存储量大，这为将图书 书馆界已经意识到用户的这些行为变化，大力发展以手机 的编目信息生成二维码，然后在出版时贴到书的某个位置 等移动终端为媒介的移动服务。移动服务是一个持续和不 成为了可能。这样可以规范图书流通阶段的重复信息录入， 加快图书的流通速度。据悉，国家新闻出版总署在十一五 期间主持了《出版物二维码技术应用调研与开发项目》，相 关标准草案已经形成，并且软件已经验收通过。 如果图书馆二维码标准得以广泛推广和应用，今后图 书出版时将会贴上二维码，这样通过二维码识读便可读出 编目信息，图书馆在进行编目时直接识读二维码即可，从 而加快图书的流通速度。 短发展的过程，每一种新技术的出现到应用都需要～个漫 长的过程。图书馆应该密切关注任何一种可以改变图书馆 服务方式的技术和应用，适时引入图书馆，为图书馆转变 服务方式提供基础和方向。 ３－３二维码技术对编目的影响 参考文献： ［１］梁鹏．手机二维码业务研究卟电信科学，２００６（１２） ［２］沈朝阳．手机二维码业务分析和建议卟市场，２００８（Ｉ） ［３］张红兰，牛现云．基于ＷＡＰ的图书馆移动网站设计研 究卟数字技术与应用，２０１２（６） ４结束语 １７ｌ一
