二次挖掘的关联规则增量更新算法
- 格式：pdf
- 大小：87.05 KB
- 文档页数：4
可信度表达的就是在出现项集 ) 的事务集 5 中， 项集 E 也同时出现的概率。 （ 1） 频繁项集与非频繁项集： 对于用户给定的最 小支持度 ?=;@:GG， 若 @:GGHI> （ )） 则称 ) 为 5?=;@:GG， 频繁项集， 反之就称为非频繁项集。 3- 3 基本定理 设 O， P是 库 5 的项集
支持度描述了 ) 和 E 这两个项集在所有事务中 同时出现的概率。 （ E ）可信度 （ KH;L=M9;K9 ） ： 可信度即是 “ 值得信赖 性” 。设 )， E 是项集， 对于事务集 5， )* 5 ， E * 5， ) )&E 的可信度定义为： 可信度 （ ) & E ）A 包 +E A ! ， 含 ) 和 E 的元组数 J 包含 ) 的元组数， 即 KH;L=M9;K9（ )&E ） A + （ E D )） A @:GGHI>NKH:;> （ )) E） @:GGHI> NKH:;> （ )）
3$$. !收稿日期： 0 $. 0 $4
作者简介： 胡锦丽 （,241 0 ! ） ， 女， 福建信息职业技术学院讲师、 高 级工程师
!K K
福建商业高等专科学校学报L L L L L L L L L L L L L $KKM 年 $ 月 对于解决关联规则更新问题国内研究很多， 其中 ［ 8］ 最直观和最简单的方法就是直接运用 ;<=>0=> 算法 对更新后的数据重新进行挖掘。这种方法虽然实现简 单， 但是它没有充分利用以前的发现结果， 效率较低， 为了充分利用以前的发现结果， 文献 ［!］ 给出了一个 基本框架与 ;<=>0=> 算法—致的经典算法 ?@A； 但 ?@A 算法需要多次扫描原始数据库以得到更新后的候选项 集， 使得算法性能降低。在以往解决关联规则增量更 新问题的研究中， 已经有不少学者对数据量增加而支 持度不变时的关联规则更新提出了相应算法。如： 李 ［: ］ 宝东等提出的关联规则增量更新算法研究 ， 李雄飞
［ B］ 等提出的二次挖掘相联规则算法 ， 孙浩等提出的一 ［ C］ 种增量更新算法 。但这些算法有 的存在频繁项集 的遗漏问题， 有的产生较多的候选项集， 有的占用较大
定理 ! ： 非频繁项集的所有父集一定也是非频繁 项集， 即 "* #， 若 " 是非频繁项集， 则 # 一定是非频
［ $］ 繁项集 。
非频繁项集的所有父集一定也是非频繁是非频繁项集则一定是非频分别是原数据库新增数据增加数据更新后数据集的频繁项集集合给定的最小支持度为的项目集属于则其一定不属于关联规则的增量更新问题对于关联规则挖掘的两个子问题相对而言第二个子问题即如何从频繁项集来生成关联规则是较为容易解决的
3$$4 年 3 月第 , 期 ! ! ! ! ! ! ! ! 二次挖掘的关联规则增量更新算法
［3 ］ 3- , 基本定义
%’5。设 ) 是 ’ 中一个或多个项的集合， 如果 )*%， 则 称事务 % 包含 )。事务数据库是事务的集合 （ 也称为 事务集） ， 则 5 A｛%= D %= * ’ ， , 4= 4? ｝ 。 （" ） 关联规则： 关联规则是如下形式的逻辑蕴涵： ) & E， 其中 )、 E 是项集， ) * ’， E*’， ) + E A ! 。一 般以下两个参数描述关联规则的属性： （ )） 支持度 （ F:GGHI>） ： 支持度 （ ) & E ）A 包含 ) 和 E 的元组数 J 元组总数。即 F:GGHI> （ )&E ） A + （ ))E ） A 7H:;> （ )) E） KH:;> （ %）
22
二次挖掘的关联规则增业技术学院， 福建 福州!
"#$$$"）
〔摘 ! ! 要〕 ! 针对事务数据库的内容不断增加后相应关联规则的更新问题， 提出了一种二次挖掘的关联规 则增量更新算法 （ %&’()） 。 %&’() 算法充分利用第一次挖掘得到的原数据库中的频繁项集， 对新增数据库挖掘 得到新增频繁项集； 只需对原事务数据库扫描一遍 ， 提高了关联规则的更新效率； 并与已有的 *(+ 算法进行了分 析比较。 〔关 键 词〕 ! 数据挖掘； 关联规则； 增量更新； 新增频繁项集 中图分类号： %+"$,- .! 文献标识码： )! 文章编号： ,$$/ 0 121$ （ 3$$4 ） $, 0 $$22 0 $$1 ! ! , 引言 关联规则是数据 挖掘问题中的 一个重要研究 内 容， 广泛应用于大型零售、 邮递、 追加销售、 仓储规划以 及基于购买模式对客户进行划分等方面。在实际应用 中， 数据信息并不是固定不变， 而是随着时间而不断变 化的， 由此， 关联规则的更新问题也就成为数据挖掘一 个重要的方面。关联规则的更新问题主要集中在三个 方面： （ ,）数据量增加而支持度不变时的关联规则更 新； （3） 数据量减少而支持度不变时的关联规则更新； （" ） 数据库的容量不变而改变最小支持度的关联规则 更新。相对而言， 第 （,） 个是一种最重要且频繁的数 据库操作。例如， 一个销售系统的记录几乎是每天都 在增加的， 这就需要高效的算法来更新维护这些已经 挖掘出来的规则以达到节省资源的目的。针对第 （,） 个问题， 比较有代表性的是 5- 6- 789:;< 提出了 *(+ ［, ］ 算法 ， 但 *(+ 算法需要多次的扫描原始数据库以得 到更新后的候选项集， 使得算法性能降低。针对以上 问题， 本文提出了一种高效的二次挖掘的关联规则增 量更新算法， 并与已有的 *(+ 算法进行了分析比较。 3 基本定义与定理
定理 $ ： 设 %& ’ 、 % () 、 %& ’ * () 分别是原数据库 &’ 、 新 增数据 () 、 增加数据更新后数据集 &’ * () 的频繁项 集集合， 给定的最小支持度为 +， , &’ , 、 , () , 、 , &’ * () , 分别是 &’ 、 ()、 &’ * () 的事务记录数。如果一个长 度为 - 的项目集 " 属于 %& ’ ， 但不属于 %& ’ * () ， 则其一 定不属于 % () 。 证明："-%& ’ ， 有 &’. /. /01235 + 4 , &’ , ， "6%& ’ * () ， 有 （ &’ * ()） . /. /0123 5 + 4 （ , &’ , * , () , ） ； 而 (). /. /0123 6 （ &’ * () ） . /. /0123 7 &’. /. /0123 5 , (), 4 +， 即 " 6%() 。 8 关联规则的增量更新问题 ［ $］ 对于关联规则挖掘的两个子问题 ， 相对而言第 二个子问题即如何从频繁项集来生成关联规则是较为 容易解决的。挖掘关联规则的工作主要集中在第一个 子问题上， 即如何挖掘出数据库当中的频繁项集。对 于本文所考虑的在用户最小支持度和最小可信度都不 变的情况下， 数据库添加新的数据时关联规则的更新 问题， 可以描述为： 设原事务数据库为 &’， + 为最小支 持度， , &’ , 为 &’ 中事务的记录数， %& ’ 为频繁项目集 的集合。对 %& ’ 中每个项目集 9 ， /. /0123 表示 9 在 &’ 中的支持计数， /. /0123 5 + 4 , &’ , 。设新增的事务数 据库为 () ， , () , 为 () 中事务的记录数。关联规则的 更新问题就是要找出总事务数据库 &’ * () 的频繁项 集集 合 %& ’ * () ， 对 %& ’ * () 中 每个项 目集 9 ， /. /0123 5 +4 （ , &’ , * , (), ） 。 当新增的事务数据库 () 添加到原数据库 &’ 中 时， 对于新增后的总事务数据库 &’ * () 中一个项集 /， 具体会有以下四种情况存在： （ !） 在 &’ 中是频繁项集， 在 () 中也是频繁项集 （ $） 在 &’ 中是频繁项集， 在 () 中却不是频繁项 集或不出现 （ 8） 在 &’ 中不 是频繁 项集， 在 () 中却 是频繁 项集 （ :） 在 &’ 中不是频繁项集， 在 () 中也不是频繁 项集或不出现 对于第 （!） （ :） 、 情况， 处理比较简单， 第 （!） 种情 况下， 可以肯定是频繁项集。而第 （:） 种可以肯定不 是频繁项集， 可以不予以处理。但是对于第 （$） （8） 种 情况的处理比较复杂， 需要重新扫描 新的关联规则。 库才能得到
（ ,） 项集： 项的集 合称为 项集 （ =>9?@9> ） 。设 ’ A ｛ =, ， =3 ， --， =; ｝ 是一个项集， 其中 =（ , 4B 4 ;） 表示不同 B 的数据项。C 项集： 包含 C 个项的 项集被成 为 C 项 集， C 表示项集中项的数目。 （ 3） 事务、 事务 库： 事务是项的集合， 设有事 务 %， 则 % * ’ 。对 应每 个事 务有 唯 一的 标 识， 记为
