分布式数据库关联规则更新算法

分布式数据库关联规则更新算法 2007年4月Apr . 2007 J OURNALOFXI′ANJIAOTONGUNIVERSITY 2012-07-19#############2012-07-19######2#0#12-07-19######## 分布式数据库关联规则更新算法 1 ,2 1宋宝莉, 覃征 ()11 西安交通大学计算机科学与技术系 , 710049 , 西安 ; 21 深圳市劳动保障局 , 518029 , 深圳 ( ) 摘要 : 提出了一种分布式关联规则增量更新算法 IU A A R,它可对数据库发生变化的情况进行归 类. 该算法主要采用改进了的 F P 树结构 ,通过传送被约束子树来挖掘全局频繁项目集 ,并充分利 用快速分布式挖掘算法建立的各局部 F P 树 ,只对新增加了的全局频繁项目修改相应的改进 F P 树 ,挖掘其对应的被约束子树 ,同时利用已挖掘的全局频繁项目集对原全局频繁项目对应的被约束 子树进行有效修剪 . 实验结果 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明 ,该算法的运算速度比快速分布式挖掘算法提高了 1 倍 ,在最坏 的情况下 ,对各局部数据库也仅需要扫描一遍 ,从而可提高数据库的维护效率 . 关键词 : 分布式数据库 ;全局频繁项目集 ;约束子树 ;增量更新 () 中图分类号 : T P301 文献标识码 : A 文章编号 : 0253Ο987 X 200704Ο0416Ο05 Updat ing Min ing Algorithm f or Distributed Assoc iat ion Rules 1 ,2 1So ng Baoli, Qi n Zhe ng ( 1 . Depa rt ment of Co mp ut er Science a nd Technolo gy , Xi′a n J iaoto ng U niver sit y , Xi′a n 710049 , Chi na ; )2 . Shenzhen L a bo r and Social Securit y Bureau , Shenzhen 518029 , Chi na () Abstract : A new al go rit h m IU A A R i ncre me nt al up dati ng al go rit h m fo r a ssociatio n r ule si s i n2 t ro duced , by w hich t he c ha nge of dat a ba se reco r ds ca n be cla ssified . The i mp ro ve d F P2t ree st r uc2 t ure i s a dop t e d a nd t he glo bal f reque nt it e mset s a re mi ne d by t ra n smit ti ng co n st rai ned su b2t ree . () U tilizi ng t he local F P2t ree creat ed by FDMA f a st di st ri but ed mi ni ng al go rit h mo nl y t he F P2t ree of t he a dded glo bal f reque nt it e m s i s mo dified . Mo reo ver , u si ng t he mi ned re sult s , t he co n st rai n2 ed sub2t ree s of t he i ncre me nt al glo bal f reque nt it e m set s t hat a re t ra n smit t e d i n net wo r k a re mi ne d. The co n st rai ned sub2t ree s of t he o ri gi nal glo bal f reque nt it e m set s ca n be p r uned wit ho ut t ra n smit ti ng t he m. Exp eri me nt s sho w t hat i n t he wo r st ca se , IU A A R o nl y sca n s eve r y local t ra n sactio n dat a ba se o nce , t h u s t he co mmu nicatio n co st i s dra maticall y decrea sed a nd t he mai nt e2 na nce efficie ncy of glo bal f reque nt it e m set s i s i mp ro ve d , a nd t he mi ni ng sp ee d of IU A A R al go2 rit h m i s i ncrea se d by at lea st t wo ti me s i n co mp a ri so n wit h FDMA . Key words : di st ri but ed dat a ba se ; glo bal f reque nt it e mset ; co n st rai ne d su b2t ree ; i ncre me nt al up2 dati ng [ 6 ] ) 挖掘关联规则是数据挖掘 研究 的一 个重 要 方 MA等 . 它们的目标是降低网络通讯开销 , 并 在 ,而频繁模式的挖掘是关联规则挖掘任务中的主 面 一定程度上提高挖掘效率 ,但对多项目的海量数据 [ 1 ] 要步骤,涉及这方面的研究主要是针对集中式频 库仍不可避免地产生大量的局部候选项目集 ,使得 [ 1 ] [ 2Ο3 ] 繁项目集的挖掘与更新,著名算法有计数分步 通讯开销问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 没有得到真正的解决. FDMA 采用改 [ 4 ] ( ) 算法 CD等 ,而在分布式环境下有分布式双决策 进的 F P 树存储结构 ,通过传输被约束子树来挖掘 [ 5 ] ( ) ( ,有效地降低了网络通讯开销 ,提高 全局频繁项目集 挖掘器 算 法 DDDM 及 快 速 分 布 式 算 法 FD2 2012-07-19#############2012-07-19######2#0#12-07-19######## i i i 了全局频繁项目集的挖掘效率 ,但如何对全局频繁 一个站点 S 使得 X . co u nt ?D sup , 即 X 在站点 min S i 项目集进行高效挖掘 、更新却无详细报道. 目前 ,常 是局部频繁项目集 . 由引理 1 得 , X 的所有非空 i 用 的 频 繁 项 目 维 护 算 法 , 如 频 繁 项 集 增 量 更 新 子集在站点 S 上为局部频繁项目集 , 证毕. [ 2Ο3 ,7 ] ( ) FU P算法等, 仅适应于单机环境 , 而全局频 可见 , 全局频繁项目集是从局部频繁项目集中 [ 8 ] ( ) 繁项目集更新算法 U A GF I适用于分布式环境 , 获得的 , 而减少局部频繁项目集引起的通讯代价是 但由于其会生成大量的条件频繁模式树 ,所以网络 提高效率的关键. 代价比较高 . 11 2 FPΟ′Tree 及被约束子树 本文针对上述问题 ,提出了一种分布式关联规 文献 [ 6 ] 中 F P树是′改进的 F P 树 , 与传 统 F P ( ) 则增量更新算法 IU A A R,它考虑了数据库记录发 树不同之处为 : ?F P 树是双向的 , 而 F P′树是单向 生变化时的全局频繁项目集的更新情况 ,在最坏的 的 , 包含较少的指针 , 可节省 1/ 4 的空间 ; ?F P 树的 情况下 ,仅须对局部数据库扫描一遍 ,并能充分利用 结点采用项标记 , 而 F P′树的结点采用项的序号标 已挖掘的结果 ,从而避免了传送原全局频繁项目对 ( 记 , 且包含 4 个 字段 项 的序 号 o r der 、支 持 度计 数 应的被约束子树 ,降低了网络通讯代价 . co unt 、指向最左子女结点或父结点的指针 a hea d 和 1 相关概念和结论 指 向 右 兄 弟 结 点 或 结 点 链 中 下 一 结 点 的 指 针 11 1 全局频繁项目集 ) ne xt . 本文沿用了文献 [ 6 ]的记号 , 而且模型中的分布 F P树′中所有被{ k, ?, k, k} 约束的子路径组 i 2 1 数据库是水平划分的 , 各部分的数据库模式逻辑同 1 2 n 成的 子 树 称 为 被 { k, ?, k, k} 约 束 的 子 树 , 记 作 i 2 1 构 . 有 n 个站点 S , S, ?, S , 相应的成员数据库分 n( ) S T k, k, ?, k, 它是 F P树的一′条包含根的特殊 1 2 i 1 2 n i i 别为 DB, DB, ?, DB , DB = ?DB , 而 D 及 D 分i = 1 子树. 该子树可用指针数组 bra nch [ ]表示且指向一 i 别表示 DB 及 DB 中的 交易 数 . 对 某一 项目 集 X , 条被约束子路径的端点 , 用整型数组 ba se2co unt [ ] i i X . co unt 及 X . co unt 分别表示在 DB 及 DB 中含 记录每个被约束子路径的基本频度计数 , 用一个整 11 3 关联规则的更新模式 X 的交易数 . i ( ) ( 型数组 S T k, k, ?, k. co unt [ ] 记录 S T k, k,1 2 i 1 2 定义 1 ( ( ) X . sup X . co u nt / D 及 X . sup X . 若 通常把关联规则的更新挖掘分为以下 5 种情形 i i i ) ?, k中具有相同序号的结点频度计数和 .i [ 4 ] ) co unt / D 分别表示 X 在 DB 及 DB 中的支持度 , 来处理 . i 则称 X . sup 为 X 的全局支持度 , X . sup 为 X 在站 情形 1新 支 持 度 阈 值 sup 小 于 原 支 持 度 阈 值 new i 点 S 的局部支持度 . sup ,这种情形可能会产生新频繁项目 , 也可能出 old ( ) 定义 2若 X . sup ?sup 最小支持度阈值, 则 X min 现原频繁项目计数增加 . i 为全局频繁项目集 ; 若 X . sup ?sup , 则 X 为站点min 情形 2sup 大于 sup, 这种情形可能会删除新 new old i S 的局部频繁项目集. 频繁项目 , 也可能出现原频繁项目计数减小 . i 情形 3 向交易数据集中增加新交易数据 , 在支持 引理 1 若 X 为站点 S 上的局部频繁项目集 , 则 X i 度保持不变的条件下可能产生新频繁项目 , 也可能 的所 有 非 空 子 集 均 为 站 点 S 上 的 局 部 频 繁 项 目 [ 8 ] 出现原频繁项目计数增加 , 或转化为情形 1 . 集. 情形 4 从交易数据集中删除旧交易数据 . 由于新 推论 1 若项目集 X 不是局部频繁项目集 , 则 X 的 交易数据集 DB′比原交易数据集 DB 的交易数据要 超集一定不是局部频繁项目集 . 类似地 , 若 X 为全 少 , 因此在支持度保持不变的条件下可能会删除原 局频繁项目集 , 则 X 的所有非空子集均为全局频繁 频繁项目 , 也可能出现频繁项目计数减小 , 这类似于 项目集. 情形 2 . i性质 1 若 X 为全局频繁项目集 , 则存在一站点 S 情形 5 根据已发现的规则集 R, 利用知识推理手 1 i( ) 1 ?i ?n使得 X 及 X 的所有非空子集在站点 S 段 , 通过扫描数据集 DB 形成新规则集 R.2 上为局部频繁项目集 . 前 4 种情形实际可归为 2 种情形 , 即情形 1 和 证明 若将 n 个站点看成是 n 个鸽巢 , 项目集 X 在情形 2 . DB 中出现的次数对应于鸽子的个数 , 则 X . co unt ? 1 2 3 , 另一部分是推理机在扫描了 知识一部分是原有的 表 1 站点 S 、S及 S 上的交易数据库数据 ( ) 数据集 DB 之后 , 利用现有的知识 R生成新的知 1 数据库 标识 交易 ( ) 识 R并追加进知识库 , 由此关联规则得以更新 .f , a , c , d , g , i , m , p 2 10 1 DB 20 a , b , c , f , l , m , o 这里不再赘述. 下面只讨论情形 1 和情形 2 . b , f , h , j , o 30 2 DB 2 IU A A R 算法 40 b , c , k , s , p 50 a , f , c , e , l , p , m , n 21 1 FDMA 算法思路 3DB 60 k , s 为了叙述方便 , 将 DB 对应的 F P树′记为 F,t ree i it ( ) DB 对应的 F P树′记为 F1 ?i ?n, 所有的全局ree 频繁项目组成的集合记为 F , 从 DB 挖掘得到的全 局频繁 项 目 集 所 组 成 的 集 合 为 L . 对 于 给 定 的 sup , FDMA 算法挖掘全局频繁集的任务可分为 2min ii t ( ) 部分 : ?建立 F及相应的被约束子树 S Tj; ?挖ree ii ii t ( ) ( t ( ) ) 掘各 F的被约束子树 S TjF| S Tj , 获得ree ree 全局频繁集 . 文献 [ 6 ]通过引入下面的定理 1 和定理 2 , 并将分布式数据库的全局频繁项目集的挖掘转化 ( ) 为基于各约束子树的挖掘 , 即对 F| S T a进行全t ree 1 ( ) 局频繁项目集的挖掘 , 而 F| S T a的全局频繁项t ree 图 1 Ft ree ii ( ) 目集的挖掘可从 Ft | S Ta的局部频繁项目集中ree 得到. ( ( ) ) ( ) 若 L F| S T aa ?F为对 F P 树的被 定理 1t ree ( ) 约束子树 S T a进行挖掘而生成的全局频繁项目 ( ( ) ) 集 , 则 L = ?L F| S T a.t ree a ?F i ii i( ( ) ) ( )定理 2 若 L F| S Taa ?F t 为对 Ft 的被ree ree i ( ) 约束子树 S Ta进行挖掘而生成的局部频繁项目 n i ii ( ( ) ) ( ( ) ) t 集 , 则 L F| S T aΑ ?L F| S Ta.t ree ree i = 1 ( ( ) ) 证明若 X ?L F| S T a, 即 X 是全局频繁项 t ree i ( ) 目集 , 则由性质 1 知 , 存在一站点 S 1 ?i ?n使得 3 F图 2 t ree i ii ( )t X 为局部频繁项目集. 由在 S 上对 F 的 S Taree i ii ( t ( ) ) 挖掘的生成过程知 , X ?L F| S Ta, 证毕 .ree ( 由于 FDMA 算法采用传送被约束子树 可用 3 ) 个很小的数组来表示的方式来挖掘全局频繁项目 集 , 避免了传送大量候选项集或频繁模式树 , 从而显 著降低了网络通讯代价 , 提高了全局频繁项目集的 挖掘效率 . 1 2 3 例 1 设 3 个站点 S 、S 及 S上的交易数据库分 1 2 3 别为 DB、DB及 DB, 如表 1 所示 . 1 3 3 对 sup = 01 5 , 由 算 法 FDMA 建 立 的 Ft r 和min ee ( )图 3 F的被束子树 S T 6 t ree 3 如图 1 、图 2 所示 . 为了便于维护全局频繁项目 Ft ree 3 集 , 在各局部频繁模式树上的头表中保留所有项目 ( ) 按照 FDMA 算法的通讯策略 , 将 S T6传送 ( ) . 下面通过求 F| 的全局频度 S T 6得到全局频繁 t ree 1 1 到站点 S , 并在 S上进行挖掘便可得到全局频繁 3 3 ( ) t r 项目集来说明 FDMA 算法 . F中的 S T6如图 3ee 项目集{ f , c , a , m , p} 及 全 局 频 繁 项 目 子 集 . 通 过 所示. 据合成方法合成一个交易数据库集 DB , 并将 该 数 式数据库关联规则更新算法 ,它在最坏的情况下仅 据库集均分到 3 个站点 . 其 中 , 总的 交易 数 为 D = 对各局部数据库扫描一遍 ,并可利用已挖掘的结果 , 390 000 , 项目数为 N = 1 000 , 潜在的全局频繁项目 从而避免了传送某些原全局频繁项目对应的被约束 数| L | = 1 500 . 在操作系统为 Wi ndo w s 2000 Se r ve r 子树 ,降了低网络通讯代价 . 实验结果表明 IU A A R 的局域网中 , 由 3 台 CPU 为 P ?350 , 内 存 为 128 算法是有效 、可行的 . i MB 的 PC 机构成分布式站点 , 且各站点的 DB 记 参考文献 : 录数相等 . 用 V C + + 61 0 对 DDDM 、FDMA 和 IU2 2 A grawal R , Srikant R. Fa st algo rit hms fo r mining a s[ 1 ] A A R 算法进行测试 , 结果如图 4 ,图 6 所示 . 由图 sociatio n r ule s [ EB/ OL ] . [ 2006 Ο05 Ο11 ] . ht tp : ? 4 、图 5 知 , 由于 IU A A R 有效地利用了最小支持度 www . r srika nt . co m/ p aper s/ vldb94 . p df . 阈值为 2 %下挖掘的全局频繁集 , 因而有效地提高 [ 2 ] Cheung D W , Han J W , N g V T , et al . Maintenance 了全局频繁项目集的维护效率 . of di sco vered a ssociatio n r ules in la r ge data ba se s : a n incremental up dating technique [ C ] ?Proceedings of t he 12t h Inter natio nal Co nf erence o n Data Engineer2 ing. Lo s Ala mito s : IE E E Co mp uter Societ y , 1996 : 106Ο114 . [ 3 ] 易彤 ,徐宝文 , 吴方君 . 一种基于 F P 树的挖掘关联规 () 则的增量式更新算法 [J ] . 计算机学报 , 2004 ,27 5: 703Ο710 . Yi To ng , Xu Bao wen , Wu Fangj un. A n F PΟt ree ba sed incremental up dati ng al go rit hm fo r mining a ssociatio n 图 4 网络通讯量 r ule s [ J ] . Chinese J o ur nal of Co mp uter s , 2004 , 27 () 5:703Ο710 . [ 4 ] A grawal R , Shaf er J . Pa rallel mi ning of a ssociatio n r ule s [J ] . IE E E Tra ns o n Kno wledge a nd Data Engi2 () neeri ng , 1996 ,8 6:962Ο969 . [ 5 ] Schust er A , Wolff R. Co mmunicatio n efficient di st rib2 uted mining of a ssociatio n r ules [ C ] ?Proceedings of t he ACM SI GMOD Inter natio nal Co nf erence o n Ma n2 agement of Data . New Yo r k : A CM , 2001 :473Ο484 . 宋[ 6 ] 宝莉 ,覃征 . 分布式全局频繁项目集的快速挖掘方 法 图 5 算法的执行时间 () [J ] . 西安交通大学学报 ,2006 ,40 8:923Ο927 . So ng Baoli ,Qin Zheng. Fa st mining algo rit hm fo r di s2 t ributed glo bal f requent itemset s [J ] . J o ur nal of Xi′a n J () [ 7 ] iao to ng U niver sit y , 2006 , 40 8:923Ο927 . 冯玉才 ,冯剑琳 . 关联规则的增量式更新算法 [ J ] . 软 () 件学报 ,1998 ,9 4:301Ο306 . Feng Yucai , Feng J ia nlin. Incremental up dating algo2 rit hms fo r mi ning a ssociatio n r ule s [ J ] . J o ur nal of [ 8 ] () Sof t wa re , 1998 ,9 4:301Ο306 . 杨明 ,孙志挥 ,宋余庆 . 快速更新全局频繁项目集 [J ] . ( )图 6 算法的执行时间 支持度为 1 % () 软件学报 ,2004 ,15 08:1189Ο1197 . Ya ng Ming , Sun Zhihui , So ng Yuqing. Fa st up dating of glo bally f requent itemset s [J ] . J o ur nal of Sof t wa re , 4 结束语 () 2004 , 15 8:1189Ο1197 . ()编辑 苗凌 本文在算法 FDMA 的基础上 ,提出了一种分布 Your requestcould not be processed becauseof a configurationerror: "Could not connect to LDAPserver." For assistance,contact your network support team. file:///C|/Users/Administrator/Desktop/新建文本文档.txt 涵盖各行业最丰富完备的资料文献,最前瞻权威的行业动态,是专业人士的不二选择。 file:///C|/Users/Administrator/Desktop/新建文本文档.txt2012/8/26 12:19:58