（基础数学专业论文）频繁项集挖掘问题的研究.pdf

兰州大学博上论文频繁项集挖掘问题的研究 摘要 频繁项集挖掘是一类基本的数据挖掘问题 可以广泛应用在关 联规则分析 相关性分析 孤立点分析 分类和聚类等多种数据挖 掘任务中 本文对频繁项集挖掘问题进行了深入的研究和探索 主 要研究工作内容和贡献如下 t 对频繁项集挖掘中搜索空间剪枝问题进行深入研究 在认 真分析现有的7 种搜索空问剪枝策略的基础上 提出了两种新的搜 索空间剪枝策略 扩展支持度相等性剪枝策略l 和扩展支持度相等 性剪枝策略2 它们都基于项集的扩展支持度相等性进行搜索空间 削减 可用于最大频繁项集挖掘任务和封闭频繁项集挖掘任务 对 其它剪枝策略无法处理的搜索空间有效地进行剪枝 同时证明了相 关的定理和推论 保证了这两种新的搜索空间剪枝策略的正确性和 有效性 2 进行最大频繁项集挖掘算法的研究 在详细分析公认的高 效最大频繁项集挖掘算法一一m a f i a 算法的基础上 应用新的搜索 空间剪枝策略对m a f i a 算法进行优化改进 得到效率更高的最大频 繁项集挖掘算法一一m a f i a 算法 通过实验对改进后的算法进行 验证 实验结果表明 m a f i a 算法在不同的测试数据集上性能都 优于m a f i a 算法 尤其是在拥有大量长的最大频繁项集的测试数据 集上 效率比原有的m a f i a 算法提高约3 倍 3 进行封闭频繁项集挖掘算法的研究 提出一种新的封闭频 繁项集挖掘算法一 e c f i m a 算法 该算法采用深度优先和广度优 先相结合的策略访问搜索空间 使用垂直位图向量存储表示项集和 事务数据库 同时利用基本剪枝策略 相等性剪枝策略 扩展支持 度相等性剪枝策略1 和扩展支持度相等性剪枝策略2 进行侯选空间 剪枝 采用多种不同特性的测试数据集进行实验 实验结果表明 e c f i m a 算法是一种高效的封闭频繁项集挖掘算法 在多种测试数 据集上性能都优丁c h a r m 算法 尤其是在拥有大量长的封闭频繁 项集的测试数据集上 效率比c h a r m 算法提高约2 3 倍 兰帅 大学博十论文 频繁项集挖掘问题的研究 关键词 数据挖掘 频繁项集挖掘 最大频繁项集挖掘 封闭频繁 项集挖掘 剪枝策略 搜索空问 扩展支持度 a b s t r a c t f r e q u e n ti t e m s e t sm i n i n gi saf u n d a m e n t a la n de ss e n t i a lp r o b l e mi nd a t a m i n i n ga n dc a nb eu s e di nm a n yd a t am i n i n ga p p l i c a t i o n s t h es ea p p l i c a t i o n s i n c l u d ea s s o c i a t i o nr u l e s a n a l y s i s c o r r e l a t i o n sa n a l y s is c l a ss i f i c a t i o n c l u s t e r i n g o u t l i e ra n a l ys i sa n dm a n yo t h eri m p o r t a n td i s c o v e r yt a s k s 1 nt h is t h e s is w et a k ea ni n d e p t hs t u d yo nf r e q u e n ti t e m s e t sm i n i n gp r o b l e m t h e m a i nr e s e a r c hc o n t e n t sa n dc o n t r i b u t i o n si n c l u d e f ir s t b a s e do na n a l y s iso fe x i s t i n gs e a r c hs p a c epr u n i n gs t r a t e g i e s t h i s t h e s lsp r e s e n t st w on e ws e a r c h s p a c ep r u n i n gs t r a t e g i e s e s e q u i v p s la n d e s e q u i v p s 2 t h e y u s e e q u i v a l e n c y o fi t e m s e x t e n s i o n s u p p o r t s t o e f f i c i e n t l ypr u n es e a r c hs p a c ew h ic hc a nn o tb ep r u n e db ye x is t i n gp r u n i n g s t r a t e g i es e s e q u i v p s1 a n de s e q u i v p s 2c a nb ea p p l i e di nm a x i m a lf r e q u e n t i t e m s e t sm i n i n gt a s ka n dc l o s e d f r e q u e n li t e m s e t sm i n i n gt a s k i na d d i t i o n ep r o v er e l e v a n tt h e o r e m sa n dl e m m a st oe n s u r et h ev a l i d i t yo fn e w p r u n i n g s t r a t e g i e s s e c o n d t h ist h e s i spr e s e n t sm a f i a an e we f f i c i e n t a i g o r i t h mf o r m i a i n gm a x i m a lf r e q u e n ti t e m s e t s b a s e do ni n d e p t h a n a l y s i so fm a f i a w h i c hi soneo fw e l l k n o w nm a x i m a lf r e q u e n ti t e m s e t sm i n i n ga l g o r i t h m s w i t hh i g hp e r f o r m a n c e m a f i a i sa ni m p r o v e m e n to fm a f i ab ya p p l y i n g e s e q u i v p sia n de s e q u i v p s 2 t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tm a f i a p e r f o r mb e t t ert h a nm a f l ao nd i f f er e n td a t a s e t e s p e c i a l l yo nd a t a s e tw i t ha 10 to fl o n g e rm a x i m a lf r e q u e n ti t e ms e t s n e wa l g o r i t h mr n n s a r o u n dt h r e e t i m esf a s t e rt h a np r e v i o u sm a f i aa l g o r i t h m i na d d i t i o n t h ist h es ispr e s e n t se c f i m a an e wa l g o r i t h mf o rm i n i n g c l o s e d f r e q u e n ti t e ms e t s i tu s e sa c o m b i n a t i o nw a yo fd f sa n db f st o e n u m er a t es e a r c h s p a c e a n du s esav e r t i c a l b i t m a pr e p r es e n t a t i o nf o r d a t a b a s ea n di t e m s e t s i ta l s o a p p l i e sb a s i c p s1 e q u i v p s e s e q u i v p s1 a n de s e q u i v p s 2t op r u n es e a r c hs p a c e o u re x p e r i m e n t a lr e s u i t ss h o wt h a t e c f i m aisa ne f f i c i e n t a l g or i t h m i tp e r f or m sb e t t e rt h a nc h a r mo n 兰州人学博士论立频繁项集挖掘问题的研究 d i f f er e n td a t a s e t e s p e c i a l l yo i ld a t a s e tw i t hal o to fl o n g e rc l o s e df r e q u e n t i t e m s e t s n e wa l g o r i t h mr u n sa r o u n dt o wo rt h r e et i m e sf a s t e rt h a nc h a r m a l g o r i t h m k e yw o r d s d a t am i n i n g fr e q u e n t i t e ms e t sm i n i n g s e a r c h s p a c e m a x i m a lfr e q u e n ti t e ms e t s m i l 3 i n g c i o s e df r e q u e n t i t e m s e t s m i n i n g p r u n i n gs t r a t e g y e x t e n s i o ns u p p o r t s 兰州i 大学博士论文频繁项集挖掘问题的研究 图1 图2 图3 图4 图5 幽6 幽7 幽8 图9 图10 幽1 1 幽l2 幽13 幽1 4 幽i5 幽16 图17 幽l8 图19 图2 0 图2 1 图2 2 图2 3 剧2 4 图2 5 幽2 6 剀2 7 图示 数据挖搞系统结构 a p r i o r i 算法中挖掘所有频繁项集的伪代码 a p r i o r i 算法中生成强关联规则部分的伪代码 表1 所示事务数据库的f p 树 f p g r o w t h 算法中i n s e r t t r e e 过程的伪代码 f p gr o w t h 过程的伪代码 项目集台f i 2 3 4 的词典序子集枚举树 项目集合 1 2 3 4 5 的频繁项集扩展树 b a s i c p s l 剪枝策略的例子 b a s i e p s 2 剪枝策略的例子 m a x p s l 剪枝策略的例子 m a x p s 2 剪枝策略的例子 m a x p s 3 剪枝策略的例f d f m a x p s 剪枝镱略的例子 e q u i v p s 剪枝策略的例子 e q u i v p s 剪枝箫略实施后的搜索空间 e s e q u i v p s l 剪枝策略的例子 e s e q u i v p s 2 剪枝策略的例子 m a f i a 算法的伪代码 m a f i a 过程的伪代码 动态排序的例子 项集和事务数据库的水平位图格式 事务数据库的垂赢位图表示 m a f i a 算法伪代码 m a f i a 过稃的伪代码 e s e q u i v p s 过程的伪代码 两种测试数据集中最人频繁项集的分布 川 m m m 蕊 拍 扣 加 钉 钉 躯 甜 酊 钉 卯 他 兰卅 大学博十论文 频繁项集挖掘问题的石j f 究 2 8 在b m s w e b v ie w l 实验结果 2 9 在c o n n e c t 4 实验结果 3 0 e c f i m a 基本算法的伪代码 3 1e c f i m a 算法的伪代码 3 2d f s 和1 3 f s 相结合的访问策略 3 3 e s e 2 c h e e k 过程的伪代码 3 4 改进后的e s e 2 c h e c k 过程的伪代码 3 5connec t 的封闭频繁项集的分布特征 3 61 4 0t 1 0 d 1 0 0 k 的封口j 频繁项集的分布特征 3 7g a z e l l e 的封闭频繁项集的分布特征 3 8在c o n i t o c t 数据测试集上的实验结果 3 9 在t 4 0 f 10 d 10 0 k 数据测试集上的实验结果 4 0 在g a ze l le 数据测试集上的实验结果 蛐 趴 罟昌 蛇 卯 鳐 图图瞬图图图图图图剧图幽图 兰州大学博士论文 频繁项集挖掘问题的研究 表格 表l数据库技术的发展演化 表2例1 的事务数据库 表3 例2 的事务数据库 表4例3 的事务数据库 表5e c f l m a 算法使片j 的3 种测试数据集的特征 9 2 3 5 2 5 8 9 4 原创性声明 本人郑重声明 本人所呈交的学位论文 是在导师的指导下独立进行研究 所取得的成果 学位论文中凡引用他人已经发表或未发表的成果 数据 观 点等 均已明确注明出处 除文中已经注明引用的内容外 不包含任何其他 个人或集体已经发表或撰写过的科研成果 对本文的研究成果做出重要贡献的 个人和集体 均已在文中以明确方式标明 本声明的法律责任由本人承担 迹 i 建中 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品 知识产权归属兰州大 学 本人完全了解兰州大学有关保存 使用学位论文的规定 同意学校保存或 向国家有关部门或机构送交论文的纸质版和电子版 允许论文被查阅和借阅 本人授权兰州大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索 可以采用任何复制手段保存和汇编本学位论文 本人离校后发表 使用学 位论文或与该论文直接相关的学术论文或成果时 第一署名单位仍然为兰州大 学 保密论文在解密后应遵守此规定 论文作者签名 导师签名 型 签 日期 建堕 p 兰卅i 大学博士论文频繁项集挖掘问题的研究 第1 章绪论 1 1 研究工作的背景和意义 进入二十一世纪 人类已经生活在一个信息高度发达的时代 在传统信息媒体方面 纽约时报 由6 0 年代的1 0 2 0 版扩张至 现在的10 0 2 0 0 版 最高曾达15 7 2 版 北京青年报 也已是 1 6 4 0 版 市场营销报 已达10 0 版 中国大部分地区可以收 看的到的电视节目接近1 0 0 套 中国每年公开出版发行的书刊上万 种 同时 在互联网上各类网站提供的信息也在爆炸性增长 全球 w e b 页面的数目已经超过4 0 亿 中国的w e b 页面数超过了3 亿 同时 随着数据库技术的迅速发展以及数据库管理系统的广泛应 用 各种政府机构 科研结构和企业建设了多种数据处理平台并积 累了大量的数据资源 在现实社会中 我们已经逐渐习惯面对这样 一个事实 超量的 多种形式的数据和信息充斥着我们的电脑 网 络和生活 大量信息在给人们生活和工作带来方便的同时也带来了严重 的问题 第一是信息过量 难以消化 第二是信息真假难以辨识 第三是信息安全难以保证 第四是信息形式不一致 难以统一处理 更为严峻的是 随着网络技术 硬件技术的飞速发展和数据库 技术的广泛应用 导致人类在数据搜集和数据组织的能力与数据分 析能力之问存在的距离正在迅速扩大 目前大多数数据库系统在分 析理解大规模数据集的能力远落后于数据的采集和存储数据的能 力 由于缺乏数据分析和挖掘手段 我们无法有效的发现数据背后 隐藏的知识 无法有效的发现数据中存在的关系和规则 无法根据 现有的数据有效预测未来的发展趋势 出现了 数据爆炸但知识贫 乏 的现象 因此 对大型的 复杂的 信息丰富的数据集的分析 理解实际上已经成为所有商业 科学 工程领域的迫切需要 人们 开始考虑 如何才能不被信息淹没 而是从中及时发现有用的知识 提高信息利用率 兰卅1 人学博士论文 频繁项集挖掘问题的研究 面对这一挑战 数据挖掘 d a t am i n i n g 技术应运而生 并显 示出强大的生命力 数据挖掘是 一个从已知数据集合中发现或提取各种模型 概 要和导出值的过程 2 8 它是人们长期对信息技术尤其是数据库技 术研究和开发的自然演化结果 数据挖掘是一种典型的探索型归纳 推理方法 它的两个基本目标是 预测和描述 数据挖掘的基本功能和它们可以发现的模式类型有 概念 类 描述 分类 聚类 孤立点分析 关联规则分析 演变分析等f 27 f 2 引 其中关联规则分析又称为关联规则挖掘 它寻找给定数据记录集中 数据项之间隐藏的关联关系 描述数据之问的密切度 通过关联规 则分析可以发现大量数据中项集之间有趣的关联规则或相关联系 关联规则挖掘可以广泛的应用于购买行为分析 w e b 挖掘 入侵检 测等各种应用领域 关联规则挖掘包含两个基本过程 一是找出满足最小支持度闽 值的所有项集 二是根据这些项集产生所有的强关联规则 其中第 二个过程相对简单一些 可以利用已知项集的支持度信息 直接通 过计算置信度枚举出所有强关联规则 因此挖掘关联规则过程的整 体性能主要由第一步决定 所以关联规则挖掘问题的核心是第一个 过程 该过程称为频繁项集挖掘 f r e q u e n ti t e m s e t sm i n i n g 目 从a g r a w a l 等 l 2 3 1 1 9 9 3 年通过研究顾客交易数据库中项集间的关 联规则提出关联规则分析问题后 频繁项集挖掘问题的研究就一直 是关联规则分析研究领域的核心 大部分的研究工作都围绕频繁项 集挖掘问题进行 同时 频繁项集挖掘方法并不只局限于挖掘关联 规则 还可以广泛应用于相关性分析 孤立点分析 分类和聚类等 多种数据挖掘任务和入侵检测 序列模式 w e b 挖掘等多种数据挖 掘应用和数据分析处理任务中 2 7 f 28 1 因此频繁项集挖掘问题是一个具有重要理论意义和广阔应用 前景的研究课题 受到理论界和产业界的广泛重视 如今 在数据 库研究和应用领域已经形成了一个以频繁项集挖掘问题为重点的 重要研究方向 兰州大学博 h 论文频繁项集挖掘问题的研究 1 2 本文研究工作的内容和目标 本文研究工作主要是进行频繁项集挖掘问题的基础理论研究 包括频繁项集挖掘问题综述 频繁项集挖掘中的搜索空间剪枝策略 研究 最大频繁项集挖掘算法研究和封闭频繁项集挖掘算法研究 具体的研究内容如下 1 频繁项集挖掘问题综述 结合数据挖掘技术的发展过程和主 要的数据挖掘任务 研究了频繁项集挖掘问题的产生背景 全面论 述了关联规则分析问题和关联规则分析的基本过程 并在此基础上 对频繁项集挖掘问题进行详细描述 分析了两种最有影响的频繁项 集挖掘挖掘算法一一a p r i o r i 算法和f p g r o w t h 算法 另外详细描述 了频繁项集挖掘问题的两个子问题一一最大频繁项集挖掘问题和 封闭频繁项集挖掘问题 并探讨分析了它们之间以及与频繁项集挖 掘问题的区别和联系 同时对频繁项集挖掘问题 最大频繁项集挖 掘问题和封闭频繁项集挖掘问题的国内外相关研究工作进行了详 细的介绍 2 频繁项集挖掘中的搜索空间剪枝策略研究 频繁项集挖掘 任务在执行过程中 所有可能的侯选项集共同构成了挖掘任务的目 标搜索空问 因此频繁项集挖掘问题本质上是一类目标空阳j 上的搜 索问题 在此项研究工作中 首先结合频繁项集挖掘过程中搜索空 间的描述方式一一词典序子集合枚举树 详细分析描述了现有的7 种重要的搜索空间剪枝策略 基本剪枝策略1 基本剪枝策略2 最 大剪枝策略l 最大剪枝策略2 最大剪枝策略3 深度优先最大剪 枝策略 相等性剪枝策略 在此基础上 我们f 提出了两种新的 高 效的剪枝策略 扩展支持度相等性剪枝策略l 和扩展支持度相等性 剪枝策略2 同时证明了相关的定理和推论 保证了这两种新的搜 索空间剪枝策略的正确性和有效性 3 最大频繁项集挖掘算法研究 此项研究工作的主要内容是 结合扩展支持度相等性剪枝策略l 和扩展支持度相等性剪枝策略2 进行最大频繁项集挖掘算法研究 首先从空间剪枝策略 事务数据 库的存储表示 频度计算方法和子集检测方法三方面详细研究分析 兰州人学博十论文 频繁项集挖掘问题的研究 了公认的高效最大频繁项集挖掘算法一一m a f i a 算法 在此基础上 采用扩展支持度相等性剪枝策略1 和扩展支持度相等性剪枝策略2 对m a f i a 算法进行优化改进 提出一种新的最大频繁项集挖掘算法 m a f i a 对m a f i a 算法进行了详细描述和程序实现 采用与 m a f i a 算法相同的实验环境和测试数据集 进行实验验证并分析实 验结果 4 封闭频繁项集挖掘算法研究 此项研究工作的主要内容是 提出 种新的封闭频繁项集挖掘算法一一扩展支持度相等性封闭 频繁项集挖掘算法e c f i m a 该算法采用深度优先和广度优先相结 合的策略访问搜索空间 使用垂直位图向量格式存储表示项集和事 务数据库 同时利用基本剪枝策略 相等性剪枝策略 扩展支持度 相等性剪枝策略1 和扩展支持度相等性剪枝策略2 进行侯选空间剪 枝 对e c f i m a 算法进行了详细描述和程序实现 采用权威的测试 数据集进行实验验证 结合其它公认的封闭频繁项集挖掘算法的实 验结果进行对比分析 并分析实验结果 本文研究工作的主要目标是 1 对搜索空问这一频繁项集挖掘问题的重要研究内容进行深 入研究 在认真分析现有的7 种搜索空间剪枝策略的基础上 提出 新的搜索空间剪枝策略 2 对最大频繁项集挖掘算法进行深入研究 在详细分析公认 的高效最大频繁项集挖掘算法一一m a f i a 算法的基础上 应用新的 搜索空间剪枝策略对m a f i a 算法进行优化改进 得到效率更高的最 大频繁项集挖掘算法 并结合实验对改进后的算法的有效性进行验 证 3 对封闭频繁项集挖掘算法进行深入研究 提出一种全新的 高效的封闭频繁项集挖掘算法 该算法采用深度优先和广度优先相 结合的策略访问搜索空问 使用垂直位图向量格式存储表示项集和 事务数据库 同时利用基本剪枝策略 相等性剪枝策略 扩展支持 度相等性剪枝策略1 和扩展支持度相等性剪枝策略2 进行侯选空间 剪枝 采用权威的测试数据集进行实验 结合其它公认的封闭频繁 项集挖掘算法进行对比分析 验证算法的 f 确性和有效性 兰州大学博上论文频繁项集挖掘问题的研究 1 3 本文的主要研究成果和创新之处 本文对频繁项集挖掘这一具有重要理论意义和广阔应用前景 的研究课题进行了研究和探索 取得的主要研究成果和创新之处如 下 1 针对搜索空i h 这一频繁项集挖掘问题的重要研究内容进行 深入研究一在认真分析现有的7 种搜索空间剪枝策略的基础上 提 出了两种新的搜索空问剪枝策略 扩展支持度相等性剪枝策略1 和 扩展支持度相等性剪枝策略2 它们都基于项集的扩展支持度相等 性进行搜索空间削减 可用于最大频繁项集挖掘任务和封闭频繁项 集挖掘任务 对其它剪枝策略无法处理的搜索窄问有效地进行剪 枝 同时证明了相关的定理和推论 保证了这两种新的搜索空间剪 枝策略的正确性和有效性 2 对最大频繁项集挖掘算法进行深入研究 在详细分析公认 的高效最大频繁项集挖掘算法一一m a f i a 算法的基础上 应用新的 搜索空间剪枝策略对m a f i a 算法进行优化改进 得到效率更高的最 大频繁项集挖掘算法一一m a f i a 算法 并结合实验对改进后的算 法进行验证 实验结果表明 m a f i a 算法在不i 刊的 坝4 试数据集上 性能都优于m a f i a 算法 尤其是在拥有大量长的最大频繁项集的测 试数据集上 效率比原有的m a f i a 算法提高约3 倍 3 对封闭频繁项集挖掘算法进行深入研究 提出一种全新的 高效的封闭频繁项集挖掘算法一一e c f i m a 算法 该算法采用深度 优先和广度优先相结合的策略访问搜索空间 使用垂直位图向量格 式存储表示项集和事务数据库 同时利用基本剪枝策略 相等性剪 枝策略 扩展支持度相等性剪枝策略1 和扩展支持度相等性剪枝策 略2 进行候选空 日j 剪枝 采用权威的测试数据集以及结合公认的高 效封闭频繁项集挖掘算法一 c h a r m 算法进行对比验汪实验 实 验结果表明 e c f i m a 算法是一种高效的封闭频繁项集挖掘算法 在不同特性的测试数据集上性能都优于c h a r m 算法 尤其是在拥 有大量长的封闭频繁项集的测试数据集e e c f i m a 算法效率是 c h a r m 算法的2 3 倍 c h a r m 算法的2 3 倍 兰州大学博上论立频繁项集挖掘问题的研究 1 4 本文的组织结构 第1 章 首先介绍了本文的研究工作的背景 接着阐述了本文 的主要研究内容和目标 最后总结了本文的研究成果和创新之处 第2 章 频繁项集挖掘问题综述 首先简单介绍了数据挖掘技 术的进展和主要的数据挖掘任务 其次 认真分析了关联规则挖掘 问题和基本过程 在此基础上 详细描述了频繁项集挖掘问题 给 出了相关术语的定义 探讨了基本的频繁项集挖掘算法 介绍相关 研究工作进展 对最大频繁项集挖掘问题和封闭频繁项集挖掘问题 进行了详细描述 并介绍了相关研究工作进展 第3 章 频繁项集合挖掘中搜索空间的剪枝策略的研究 首先 描述了词典序子集枚举树 详细分析了现有的主要7 种搜索空问剪 枝策略 在此基础上提出了两种新的搜索空间剪枝策略 扩展支持 度相等性剪枝策略1 和扩展支持度相等性剪枝策略2 它们基于项 集的扩展支持度相等性有效的进行搜索空问削减 可用于最大频繁 项集挖掘任务和封闭频繁项集挖掘任务 第4 章 最大频繁项集挖掘算法的研究 本章的主要内容是应 用扩展支持度相等性剪枝策略l 和扩展支持度相等性翦枝策略2 进 行最大频繁项集挖掘算法研究 首先从空间剪枝策略 事务数据库 的存储表示 频度计算方法和子集检测方法三方面详细分析了 m a f i a 算法 在此基础上采用扩展支持度相等性剪枝策略1 和扩 展支持度相等性剪枝策略2 对m a f i a 算法进行优化改进 提出一 种新的最大频繁项集挖掘算法m a f i a 对m a f i a 算法进行详细 描述 最后分析了算法的实验结果 第5 章 最大频繁项集挖掘算法的研究 本章的主要内容进行 封闭频繁项集挖掘算法研究 提出一种新的封闭频繁项集挖掘算法 一一扩展支持度相等性封闭频繁项集挖掘算法 e c f i m a 本章首 先讨论了e c f i m a 算法的基本思想 然后从算法采用的搜索空问访 问策略 使用的剪枝策略 动态排序 项集和事务数据库的存储表 示方式 支持度计算等方面对e c f i m a 进行详细分析 最后分析了 算法的实验结果 兰州大学博十论文 频繁项集挖掘问题的研究 第6 章 总结和下一步研究工作展望 主要对本论文的研究工 作进行总结 并对下一步的工作进行展望 兰州大学博士论文频繁项集挖掘问题的研究 第2 章频繁项集挖掘问题综述 频繁项集挖掘是一类重要的数据挖掘问题 可以广泛应用在关 联规则挖掘 相关性分析 入侵检测 序列模式 分类和聚类等多 种数据挖掘任务中1 2 7 1 2 8 i 引1 1 3 2 1 a g r a w a l 等 1 2 儿3 19 9 3 年通过研究 顾客交易数据库中项集间的关联规则提出关联规则分析问题 同时 研究结果表明 解决关联规则分析问题的核心是挖掘出可以产生强 关联规则的频繁项集合 因此 从1 9 9 3 年开始 频繁项集挖掘问 题一直受到计算机科学理论研究的广泛重视 近十年来先后提出了 多种有价值的频繁项集挖掘算法和研究成果 本章首先对数据挖掘技术进行探讨 并在此基础上结合关联规 则分析对频繁项集挖掘问题进行详细描述 同时对两种有重要影响 的频繁项集挖掘方法进行分析 另外 对最大频繁项集挖掘问题和 封闭频繁项集挖掘问题进行详细描述 并分析了这两类问题的相关 研究工作进展 2 1 数据挖掘技术概述 数掘挖掘技术是人们长期对信息技术尤其是数据库技术研究 和开发的自然演化结果 如表1 所示 自2 0 世纪6 0 年代以来 数 据处理已经系统地从原始的文件处理演化到复杂的 功能强大的数 据库系统 自7 0 年代以来 数据库系统的研究和开发已经从层次 和网状数据库系统发展到关系型数据库系统 数据存放在关系表 中 数据建模工具 索引和数据组织技术 自8 0 年代以来 数 据库技术的特点是广泛接受了关系技术 研究和丌发新的 功能强 大的数据库系统 产生了扩充关系模型 面向对象模型 对象一关 系模型和演绎模型等先进的数据模型 出现了时间的 空间的 分 前i 的 多媒体的 丰动的和科学计算的数据库 知识库在内的多种 面向应用的数据库系统 自9 0 年代以来 数据库技术进入了一个 崭新的阶段 出现了联机分析处理 o l a p 多维数据库 数据 兰州大学博士论义频繁项集挖掘问题的研究 仓库和基于w e b 的数据库系统等新技术 发展阶段支持技术特点 原始的文件处理演化到复杂提供历史性的 静 数据搜集 6 0 年代 7 0 年代 的 功能强大的数据库系统态的数据信息 在记录级提供历 关系数据库 r d b m s 结 数据访问 8 0 年代 史性的 动态数据 构化南询语言 s q l o d b c 信息 联机分析处理 o l a p 多在各种层次上提 数据仓库 决策支持 9 0 年 维数据库 数据仓库 基于供回溯的 动态的 代 w e b 的数据库系统数据信息 数据挖捌算法 多处理器计算提供预测性的信 数据挖掘 现在 机 海量数据库存储访问 息 表1数据库技术的发展演化 随着数据库技术的发展和数据库系统的广泛应用 必然产生了 对强有力的数据分析和决策支持工具的需求 电子数据处理的初 期 人们就试图通过某些方法来实现自动数据分析和决策支持 当 时机器学习成为人们关心的焦点 机器学习的过程就是将一些已知 的并已被成功解决的问题作为范例输入计算机 机器通过学习这些 范例 总结并生成相应的规则 这些规则具有通用性 使用它们可 以解决某一类的问题 随后 随着神经网络技术 n e u r a ln e t w o r k 的形成和发展 人们的注意力转向知识工程 k n o w l e d g e e n g i n e e r i n g 知识工程不同于机器学习那样给计算机输入范例 让它生成出规则 而是直接给计算机输入已被代码化的规则 而计 算机是通过使用这些规则来解决某些问题 专家系统就是这种方法 所得到的成果 但它有投资大 效果不甚理想等不足 8 0 年代人 们又在新的神经网络理论的指导下 蘑新回到机器学习的方法上 并将其成果应用于处理大型商业数据库 9 0 年代出现了新的数据 库结构一一数据仓库 这是一种多个异种数据源在单个站点以统一 兰卅l 大学博士论文 频繁项集挖捅问题的研究 的模式组织的存储 以支持管理决策 数据仓库技术包括数据清理 数据集成和联机分析处理 o l a p o l a p 具有汇总 合并 和 聚集功能 以及从不同角度观察信息的能力 可以支持多维分析和 决策 但对于数据分类 聚类 关联和数据的时变特征分析等高级 分析功能 不能提供有效的支持 在此基础上 数据挖掘技术的出 现有效的补充了o l a p 的不足 为全面的数据分析和决策支持提供 了强大的技术支撑 另外 其他基础技术和基础条件的发展和完善为数据挖掘技术 的产生和发展的提供了良好的支持 f r i e d m a n 1 列举了激发了数据 挖掘的开发 应用和研究兴趣的四个主要的技术理由 1 超大规 模数据库的出现 例如商业数据仓库和计算机自动收集的数据记 录 2 先进的计算机技术 例如更快和更大的计算能力和并行体 系结构 3 对海量数据集的快速访问 4 对这些数据应用精深的 统计方法计算的能力 目前 这些对数据挖掘技术进行支持的基础 技术和基础条件已经逐渐发展成熟 商业数据库现在j 下在以一个空 前的速度增长 并且数据仓库正在广泛地应用于各种行业 成熟的 并行多处理机的技术可以满足对计算机硬件性能越来越高的要求 另外数据挖掘方法经过了这1 0 多年的研究发展 也已经成为一种成 熟 稳定 且易于理解和操作的技术 数据挖掘是 1 个从已知数据集合中发现或提取各种模型 概 要和导出值的过程 1 28 定义中 过程 的概念非常重要 原因是数 据挖掘不只是一些独立工具的集合 同时数据挖掘是一个反复的过 程 每次反复可能会采取不同的工具去匹配问题的不同角度 与数据挖掘类似的术语还有数据库中知识发现 知识提取 数 据 模式提取 数据考古和数据捕捞等 其中最重要的是数据库中 的知识发现 k d d k n o w l e d g ed i s c o v e r yi nd a t a b a s e 它泛指所 有从源数据中发掘模式或联系的方法 在学术界对数据挖掘有两种 观点1 2 8 1 一种是广义的观点 即数据挖掘就是数据库中知识发现 的同意词 另一种观点是数据挖掘只是数据库中知识发现过程的一 个基本步骤 目前两种观点都得到广泛认可 本文采用第二种观点 即k d d 描述了整个数据库中知识发掘的过程 包括从最开始的制 0 兰州大学博士论文 频繁项集挖掘问题的研究 定主题目标 数据清理 数据集成 数据选择 数据变换 数据挖 掘 模式评估 知识表示到最终的结果分析 而数据挖掘是k d d 的一个重要组成部分 它以数据仓库或数据库中的大量数据为对 象 以挖掘算法为手段 最终以获得模式或规则为结果 并通过结 果展示表现 图l 给出了数据挖掘系统结构图 其中 数据挖掘引擎是数据 挖掘系统的核心部分 由一组实现具体挖掘功能的数据挖掘算法组 成 用于特征化 关联 分类 聚类分析以及演变和偏差分析 图1数据挖掘系统结构 知识库主要是存放领域知识 用于指导搜索或评估模式的兴趣 度 这种知识可能包括概念分层 用于将属性或属性值组织成不同 的抽象层 用户确信方面的知识也可以包含在内 另外 领域知识 还包括兴趣度限制 闽值 和元数据 描述来自多个异种数据源的 数据 模式评估部分主要是使用兴趣度度量方法 识别表示知识的真 正有价值的模式 有时 也可采用用户交互式模式评估的方法 数据库和数据仓库主要根据用户的数据挖掘主题目标 为具体 的挖掘任务提供数据资源 数据仓库与数据挖掘联系非常紧密 w h 1 n m o n 在 b u i l d i n gt h ed a t aw a r e h o u s e 45 一书中对数据仓 库给出了如下定义 数据仓库是面向主题的 集成的 时变的以 及非易失的数据集合体 数据仓库是促进数据挖掘迅速发展的原 兰州大学博士论文 频繁项集挖掘问题的研究 因之一 它与数据挖掘有着密切的关系 从数据仓库的观点看 数 据挖掘是联机分析处理 o l a p 的高级阶段 但是 数据仓库并 不是数据挖掘的唯一先决条件 因为有很多数据挖掘任务可直接在 原始数据库中进行 用户界面和结果展示部分主要由交互式用户界面组成 该部分 以各种形式对获取的模式和知识可视化 同时该部分允许用户和数 据挖掘系统交互 浏览数据库和数据仓库模式和数据结构 指定数 据挖掘查询或任务 提供信息根据数据挖掘的中间结果进行探索式 数据挖掘 数据挖掘是一种典型的探索型归纳推理方法口引 按形式逻辑学 的研究 推理是由已知事实通过一定的逻辑手段获得未知事实 其 中 与决策有关的推理有三种 演绎推理 归纳推理和归纳演绎推 理 演绎推理是从已知的一般性规则出发推导出个体事实的结果 归纳推理是由大量个体事实出发推导出一般性规则 在这两种推理 的基础上可以引申出归纳演绎推理 即首先利用归纳推理从大量事 实中归纳出一般性规则 再利用该规则通过演绎推理推导出另一类 个体事实的结论 数据挖掘功能主要用于指定数据挖掘任务中要找的模式类型 数据挖掘的两个基本目标是 预测和描述 预测涉及到使用数据集 中的 一些变量或域来预测其他我们关心的未知或未来的值 描述关 注的则是找出可由人类解释的数据模式 因此 数据挖掘任务一般 可以分为两类 预测型数据挖掘和描述型数据挖掘 预测型数据挖 掘主要是找出已知数据集所蕴涵的系统模型 并进行推断 以进行 预测 描述型数据挖掘刻画数据集中数据的一般特性 并在此基础 上生成新的 未知的信息 数据挖掘的基本功能和它们可以发现的模式类型如下 l 概念 类描述 c l a s s e o n c e p td e s c r i p t i o n 数据可以与类或概念相关联 用汇总的 简洁的 精确的方式 描述每个类和概念称为概念 类描述 主要采用的方法有 1 数据特征化 是目标类数据的 般性特征或特性的汇总 2 数 据区分 将目标类对象的一般特性与其他类的一般特性相比较 兰州大学博士论文频繁项集挖掘问题的研究 2 分类 c l a s s i f i c a t i o i l 分类是找出描述并区分数据类或概念的的规律或模型 以便能 够使用模型预测类标记未知的对象类 由于大量的数据对象可以根 据其表象特征分为不同的类 而这些类之间具有其内在的本质差 别 如何由不同表象而进一步挖掘出其内在性质的不同 这就是分 类方法的主要工作 在分类的基础上可以进一步推演以实现推测数 据对象的类标记和部分数据值 被称为预测 p r e d i c t i o n 分类 常用的方法有 决策树方法 粗集方法 贝叶斯 b a y e s 方法 人工神经网络方法和遗传算法等 3 聚类分析 c l u s t e r i n ga n a l y s i s 聚类分析是将物理或抽象的数据对象集合划分成表象特征相 近的多个类 在同类中的数据具有表象的相似性 而类间的数据具 有表象的相异性 聚类分析是一种普遍的描述性任务 它与分类不 同 主要分析数据对象 而不考虑预先定义的类和已知的类标记 聚类的主要采用基于距离的聚类分析 常用的方法有 遗传算法 划分法 层次法 基于密度方法 基于网格方法和基于模型的方法 等 4 关联分析 a ss o c i a t i o na n a l ys i s 关联分析主要是挖掘发现大量数据中项集之间有趣的关联规 则或相关联系 关联分析的结果一般有两种 关联规则和序列模式 它是无指导机器学习系统中挖掘本地模式的最普通形式 利用该过 程可以获取数据集中事先并不了解或不能肯定的有价值信息 5 孤立点分析 o u t l i e ra n a l y s i s 在系统中存在一些数据 它们不符合数据的一般模型 与其他 数据对象不同或不一致 这样的数据对象被称为孤立点 孤立点可 能是度量或操作错误所导致 也有可能是固有的数据变异性的结 果 在大多数据挖掘任务中要求孤立点的影响最小化 或清除它们 但在其他 些应用 如欺诈行为检测中 孤立点本身可能非常重要 隐藏着重要的信息 因此 孤立点分析和检测是一种非常有价值的 数据挖掘任务 主要的孤立点分析方法有 基于统计的孤立点检测 基于距离的孤立点检测 基于偏离的孤立点检测 兰州大学博士论文频繁项集挖掘问题的研究 6 演变分析 e v o l u t i o na n a l y s is 演变分析是通过数据分析描述行为随时问变化的规律或特征 并对其建模 主要的演变分析方法包括 时间序列数据分析 序列 或周期模式匹配和基于类似性的数据分析 近年来 数据挖掘研究已经成为数据库乃至计算机技术研究 开发和应用领域中最活跃和最受关注的分支之一 吸引了大批的学 者和研究机构从事相关的研究工作 先后在上述6 个方面产生了许 多有价值的研究成果 2 2 关联规则分析和频繁项集挖掘问题描述 关联规则分析又称为关联规则挖掘 是一类重要的数据挖掘任 务 a g r a w a l 等 1 f 2 1 3 于1 9 9 3 年首先研究了顾客交易数据库中项集 问的关联规则 进而提出了关联规则分析问题和频繁项集挖掘问 题 关联规则分析寻找给定数据记录集中数据项之间隐藏的关联关 系 描述数据之间的密切度 是数据挖掘中的重要功能之一 通过 关联分析可以发现大量数据中项集之间有趣的关联规则或相关联 系 关联分析的结果一般有两种 关联规则和序列模式 关联规则 用于描述在同一个事件中出现的不同项的相关性 更确切的说 关 联规则是通过量化的描述对象x 的出现对对象y 的出现有多大的 影响 序列模式描述的是事件之间时间上的相关性 关联规则挖掘 可以广泛的应用于购买行为分析 w e b 挖掘 入侵检测等各种应用 领域 受到广泛关注 关联规则挖掘的典型例子是购物篮分析 该 过程主要通过分析顾客采购的不同商品间的联系 发现顾客的购买 行为模式 帮助零售商制定相应的营销策略 如商品货架设计 库 存安排以及根据购买模式对用户进行分类等 关联规则挖掘问题描述如下 定义1 项目集合i i i 其中j k 1 2 m 表示一个项 目 集合x 被称为项集 如果x i 如果i x k 则x 被称为k 项集 定义2 事务t 是 个二元组 t t i d x 1 其中 t i d 称为事 务号 是该事务唯一的标识 x l 是 个项集 兰州大学博士论文频繁项集挖掘问题的研究 定义3 事务数据库d 是i 上事务的集合 d t 一t 其中 t k k l 2 n 是一个事务 d 中所有事务的事务号组成的集合称为 事务号集合 记为 t i d s e t 定义4 项集x 的支持数是事务数据库d 中包含x 的所有事 务数 记为 s u p p o r t x 即s u p p o r t x i t i d l r i d i d x i i 项集x 的支持度是d 中包含x 的事务数占所有事务数的百分比 它是概 率p x 川己为 s x 川口s 酌 p x 警 如果事务数据库确定 支持度和支持数的概念具有相同的度量 意义 因此本文并不明确区分支持度和支持数 文中此后出现的支 持度都具有支持数的意义 并且本文统一使用s u p p o r t x 来表示支持 度的概念 定义5 一个关联规则是形如x j y 的蕴含式 这罩x c i y c i 并且x n y a 规则x j y 在事务数据库d 中成立 具有支持度s 则s 是d 中项集x u y 的支持度 记为s u p p o r t f x jy 即 s u p p r t x j y s u p p o