基于关联规则算法的改进研究_图文

1、第 5卷 第 3期 2007年 9月 职 教 与 经 济 研 究Vocati o na lEducati o n and Econo m ic Research V o. l 5 No . 3Sept. , 2007收稿日期 :2007-08-27作者简介 :李新良 (1974-, 女 , 娄底职业技术学院讲师 , 湖南大学在读研究生。研究方向 :数据挖掘与软件开发。基于关联规则算法的改进研究李新良(娄底职业技术学院 , 湖南 娄底 417000摘 要 :目前 , 已经提出了许多挖掘关联规则的 算法及其变型 , 其中 最著名的是 A pri o ri 算法 , 但传 统的算法效率太低 , 为了

2、解决这些问题 , 提出了一种快速更新的关联挖掘算法 。关键词 :数据挖掘 ; 关联规则 ; 频繁项集 ; A pr i or i 算法中图分类号 :TP3 文献标识码 :A 文章编号 :(2007 03-0054-05Researchi ng the Im prove m ent of A lgorith m on A ssoci ati ona l RulesLI X in -liang(Loud iV ocationa l&T echnical Co ll ege , Loud i H u m an 417000Abstrac t :N o w adaysa l o t o f a

3、lgo rithm s , inc l u d i n g the w e ll-kno wn Aprior, i has been put for w ard .To solve the prob le m s of lo w e fficiency caused by the traditi o na l a l g orith m, a ne w algorithm na m ed M i n i n g A l g orit h m for A ssociati o n is proposed . K ey word s :data m i n i n g ; associati o

4、na l r u le ; frequency ite m se; t A priori algo rithm 数据挖掘是数据库研究、 开发和应用最活跃的 分支之一。它不满足于对数据的简单查询 , 而是想 从众多的数据中找出更多 有用的东西 (知识 , 所 以数据挖掘的过程又被称为知识发现的过程。从 某种意义上讲 , 数据挖掘的自主性使得计算机具有 一定的 智能 , 可以实现许多人力 所无法完成的 事情 , 让计算机对人类的辅助作用得到 更大的发 挥 , 信息资源也得到更大的利用。关联分析是数据 挖掘诸多功能中的一种 , 也是最为重要和应用最广 泛的一种。关联分析用于发现关联规则 , 关联规则

5、 描述了给定数据集的项之间的有趣联系。通过这 些描述 , 可以从大量的事务记录中发现有趣的关联 关系 , 可以帮助制定许多重大决策。 1 关联规则挖掘 1. 1 基本概述关联规则挖掘问题是 R. Ag ra w al 等人于 1993年在文献中首先提出来的1。关联规则挖掘是指从一个大型的数据集中发现有趣的关联或相关关 系 , 即从数据集中识别出频繁出现的属性值集 , 也 称为频繁项集 (Frequent Ite m sets , 简称频繁集 , 然 后再利用这些频繁集创建描述关联规则的过程4。关联规则中的支持度和置信度是两个规则兴 趣度的度量 , 它们分别反应了所发现规则的有 用 性、 确定性

6、、 新颖性和简洁性。通常 , 用户为了达到 一定的要求 , 都需要指定规则必须满足的支持度和 信任度的门限 , 称其为最小支持度和最小信任度。 1. 2 关联规则挖掘问题关联规则是描述数据库中数据项之间存在的 潜在的 关 系规 则。 问题 可 以 描述 如 下 :I =i 1, i 2,. . , i m 是所有项的集合 , 相当与商品的种类集 合。 D 是所有事务的子集 , 相当于数据库中的记录集合。每个事务 T 由 I 中的若干项组成 , 是 I 的子 集 , 用唯一的 I D 标识 , 记为 T =t 1, t 2,. . , t n ,t ! , i 相当于每次交易中的商品列表。假设

7、X, Y 是数 据项集 , X 中含有的项的数目为 k , 称为 k 数据 项集 , 是 I 的子集。关联 规则表 示为 :(T 中包 含 X (T 中包含 Y 。意义在于一次交易中 (数据库 中的一条记录 存在 X 项目 , 意味着该交易中也存 在 Y 项目。通常简写为 X (Y, X 称 为关联规则的 前项 , Y 称为该关联规则的后项 , (称为关联操作。关联规则挖掘问题可以分为两个子问题 :(1 找出事务数据库中所有大于等 于用户指定的最小支持度的数据项集 , 即具有最小支持度的 数据项集。 (强项集 (2 利用最大数据项集生成所需要的关联 规 则 , 根据用户指定的最小置信度规则的取

8、舍 , 最后 得到强关联规则。 2 关联规则的算法2. 1 Apriori 算法Apriori 算法是关联规则是最典型的算法 , 它通 过对数据库 D 的多趟扫描来发现所有的强项集。 该算法的流程如下 :该算法有如下两个基本性质 :性质 1:任何强项集的子集必定是强项集。 性质 2:任何弱项集的超集必定是弱项集。Apriori 算法 6用代码描述如下 :Inpu:t Database D of transactions ; m ini m um sup port thresho ldM i n supportM et h od ,Outpu:t L 1frequent ite m sets i

9、n D L 1=Lar ge1-ite m sets;for (k=2; L k-1#(;k+ do beg in C k =apriori_gen(L k -1, m i n support; /*生成 候选 k-项集 */for all transactions t ! D do beg inC t =subset(C k , t; /*候选集 C k 中提取包含 在事务 t 中的候选 k-项集 */for allC and i d ates C ! C t do C . Count+; endL k =C ! C k |C . Conut m i n supporrt;Ans w er=

10、UkLk ; /*求 L 的和 */函数 A priori _gen 按 如 下 方 式 分 两 步 进 行 工作 :(1 合并 Insert i n to Ck Select P . ite m 1, P .ite m 2, %, P.ite m k-1,Q. ite m k-1Fr o m L k-1P , L k-1 QW here P . ite m 1=Q. ite m 1, %, P . ite m k -2=Q. ite m k -2, P. ite m k-1=Q. ite m k -1;(2 修剪 :如果 k-项集 C ! Ck 的某 (k -1 子 集不是 (k-1 -强项

11、集 , 则将 C 从候选集 Ck 中 删除。for a ll ite m sets C ! Ck do for a ll(k-1 -subsets b o f c do if(b L k -1 then De l e te C fro m C kApriori_gen函数充分利用了前述的性质来 生 55总第 15期 李新良 :基于关联规则算法的改进研究速度和扫描数据库的速度均有较大提高 , 算法的效 率得到较大改善。2. 2 Apriori 算法的问题描述以上的关联分析 Ap i o r i 算法 , 在应用时会遇到 项集生成瓶颈 2的问题。即由于生成的侯选项 集太多而造成算法效率的急剧降低。

12、同时 , 过多的 侯选项集可能会生成大量的规则 , 怎样从中选择出 用户感兴趣的规则成为了另一问题。而生成过多 侯选项集的原因 , 主要有两种 :(1 被挖掘数据库 的容量很大 ; (2 用户选择的支持度阈值过小。文 献 &2 提出了一种无冗余快速关联规则发现算法 , 该算法基本原理与 Apriori 算法相似 , 但采取了不 同的计算候选项集支持度的方法。减少了 I/O操 作而提高效率 , 但没有有效地利用频繁项集中的特 性 , 下面提出了一种快速发现关联规则的算法。3 改进的算法3. 1 快速发现关联规则算法为解决 Apriori 算法中存在问题 : 生成较小的 候选项目集 , 即

13、尽可能不生成和计算那些不能成 为频繁项集的候选项集。它利用了这样一个基本 性质 :即一个频繁项集的任意子集必定 是频繁项 集。对于一个给定的强项集 L , 可首先生成以一个 数据项为结果的关联规则 ; 然后 , 利用这些规则的 结果和前述的 Apriori_gen函数 , 生成所有可 能从 强项集 L 中产生的、 以两个数据项为结果的潜在规 则 , 即候选规则 , 最后 , 检验这些候 选规则的 置信 度 , 若其置信度满足给定的最小置信度 m i n con, f 则 得以两个数据项为结果的关联规则 , 以此类推。因 此 , 关联规则发现快速算法的代码描述如下 :for allLarge k

14、-ite m s L k , K 2do beg in H 1=Consequents o f r u les derived fro m L k w ith one ite m in t h e Consequent;Ca ll ap_genrules(L k , H 1; /*由以单个数据项 为结果的规则生成以多个数据项为结果的所有规 则 */end其中 :ap_genru les 函数是以 m 个数据项 为结 果的规则集 H m 生成以 m 数据项为结果的规则集 H m+1的 递 归 函 数 , ap _genrules 函 数 的 基 本 代 码 描述 :ap_genru les(L

15、k , H m if(k>m +1 then beg in1mfor a ll h m+1! H m+1dobeg i n Confidence=Support(L k /Support(L k -h m+1if(Confi d ence m i n confi d ence thenOutput the rule (L k -h m+1? h m+1w it h Con fi dence=cont and Support=Support(L k ;else De l e te h m+1fr o m H m+1;endCall ap_genru les(L k , H m+1;End3

16、. 2 尚未解决的问题描述快速发现关联规则算法能尽快地发现候选集 , 但在关联规则挖掘过程中 , 为发现事先未知的关联 规则 , 用户必然要不断反复调整最小支持度和最小 置信度这两个门限值 , 则对于新的最小支持度 , 须 将 Apriori 算法重新运行 一遍 , 所有的强项集都 必 须从头进行计算 , 在原最小支持度下进行的强项集 的计算都被浪费掉 , 不利于高效发现新的最小支持 度下的关联规则。3. 3 强项集的快速更新算法为解决反复改变最小支持度和最小置信度带 来的统一资源浪费问题 , 提出一种强项集的快速更 新算法。假设事务数据库不变 , 当最小支持度发生 变化时 , 在 Aprio

17、ri 算法发现的最小支持度下的 强 项集基础上高效地生成新的强项集 6。给定事务数据库 D , 设原最小支持度 为 m i n sup , L k (k=1, 2, %, n1 为此时 k-强项集 ; 新的最 小支持度为 m i n sup (, L k (k=1, 2, %, n2 为此时 k -强项集的集。当最小支持度发生变化时 , 可以分 为如下两种情况 :(1m i n sup ( m insup , 此时原 L k 中的某些强 项集可能不再满足新的最小支持度而成为弱项集。 (2m i n sup (<=m i n sup , 此时原 L k 中的所 有 强项集在新的最小支持度也

18、成为强项集。对于第一种情况 , 新的强项集必然包含在原强 项集中 , 即 L k ' L k 。同时 , 强项集的更新很直观 , 只要利用原强项集的支持度计数域 C ount 重新 进 行判断即可。其算法的基本代码描述如下 :最小支持度 增大时的 强项集更 新算法 (m i n sup (>m i n sup:for(k=1; k n1; k+ dobeg i n L k = c ! L k |c . count m i n isuppor, t ;Endw56职 教 与 经 济 研 究 总第 15期最小支持 度减小 时的强项 集更新算 法 (m i n sup (<=m

19、i n sup:L 12=ne w large 1-ite m sets;L 11=L 1; L 1(= L 11+L 12;for(k=2; L k-1(#(;k+ dobeg in C k 0=apriori_gen(L k-11 -L k ; C k 2=apri ori_gen(L k-12; C k 3= ;for(i=1; i k-1; k+ dobeg in C k 3=C k 3+C k 3_gen (L i 1, L k-i 2, L k-13; endfor all transactions t ! D dobeg in C t 0=subset(C k 0, t; /*在

20、候选集 C k 0中 提取包含在事务 t 中的候选 k-项集 */for all cand i d ates c ! C t 0do c . Count+; C t 2=subset(C k 2, t; /*在候选集 C t 2中提取 包含在事务 t 中的候选 k-项集 */for all cand i d ates c ! C t 2do c . Count+; C t 3=subset(C k 3, t; /*在候选集 C k 3中提取 包含在事务 t 中的候选 k-项集for all cand i d ates c ! C t 3do c . Count+; endendL k 0=c

21、! C k 0|c . Coun t m i n sup (;L k 2=c ! C k 2|c . Count m i n sup (;L k 3=c ! C k 3|c . Count m i n sup (;L k 1=L k 0+L k ; L k (=L k 1+L k 2+L k 3;endAns w er=+k L k (;4 算法检验及性能分析4. 1 算法检验在计算机上用 VC +实现了上述算法 , 并利 用模拟测试数据集分别对产生强项集的 apriori 算 法和更新算法进行了验证 , 比较了它们的运行结果 和算法的执行时间。采用随机方式生成事务数据 记录数为 800个的测

22、试数据集 , 其数据项用数据项 目数为 10。验证计算测试数据集在 800个记录的 六种情况下进行 , 最小支持度分别为 0. 275, 0. 25, 0. 225, 0. 200, 0. 175, 0. 15, 0. 135和 0. 125。运算 表明 :两种算法在上述各种最小支持度下所得到的 强项集是相同的 , 更新算法的时间更短。当最小支 持度增大时 (即 m insup (>m i n sup, 更新维护算法 的效率远优于 Apri o ri 算 法 ; 当最小支持度减小 时 (即 m insup (<=m i n sup, 两种算法在各种情况下 执行时间的运算结果 (见下

23、表 记录数为 800条时两算法的运行时间对比表表 1 记录数为 800条时两算法的运行时间对比表算法最小支持度0. 2750. 250. 2250. 2000. 1750. 150. 1350. 125 A priori 算法 0. 820. 811. 743. 163. 564. 017. 9210. 12更 新 维 护 算 法 原最小支持度0. 275-0. 711. 562. 892. 993. 696. 148. 66 0. 25-1. 442. 782. 453. 346. 018. 01 0. 225-2. 092. 333. 215. 237. 45 0. 200-1. 982.

24、 174. 887. 23 0. 175-2. 224. 327. 01 0. 15-4. 126. 45 0. 135-5. 21从验证结果可以看出 , 更新维护算法的运行速 度比 Apri o ri 算法快 , 其运行速度的 改善程度取决 于新旧最小支持度的差异和其强项集的分布情况。 当新旧最小支持度的差异较小 , 且原最小支持度下 的强项集 Lk 较大时 , 更新维护算法的效率可以得 到较大的提高。4. 2 性能分析在 m i n sup (>m i n sup 的情况下 , 由于算法只需 要利用原强项集的支持度计数域重新进行判断 , 而 不需要重新生成候选集 , 更不需要对数据库

25、进行扫 57总第 15期 李新良 :基于关联规则算法的改进研究描。因此 , 在这种情况下 , 算法的效率将大大提高。 在 m insup (<=m insup 的情况下 , 算法效率提 高的关键在于高效地生成了较小的候选集。主要 有以 下 几方 面 :首先 , 在第 一 趟 扫描 数 据 库 时 , Apriori 算法需要对数据库的全体数据项集 I 中的 所有单个数据项进行支持度计数以生成 I-强项 集 , 而更新算法只需要对 (I-L1 中的单个数据项 进行支持度计数 ; 其次 , 在后续的第 k 趟扫描数据 库中 , A priori 算法中只需要进行支持度计数的候选 集为 Ck a =A pr i o ri_gen(l K -1(, 而更新算法需 要进行支持度计数的候选集为 Ck (=Cka -Lk , 显 然 , Ck (比 Cka 小 , 则算法的计算量减 少 , 而且 Lk 越大 , 算法效率提高越明显 ; 第三 , 在生成候选集的 修剪步骤中 , Apriori 算法必须检查整个 Lk-1(才 能进行有效的修剪 , 而更新算法在生成 Ck (的三个 子集 Ck0, Ck2, Ck3时 , 只需要对其对应的 Lk-11, Lk-12和 Lk-13单独进行检查就能实现有效的 修剪。由于 Lk-11, Lk-12和 L