（计算机软件与理论专业论文）基于序列数据库的数据挖掘系统的设计和研究.pdf

山东科技大学硕士学位论文摘要 摘要 序列模式挖掘就是发现序列数据库中的频繁子序列作为用户感兴趣的模式 它是当 前数据挖掘领域中一个很重要 很活跃的研究课题 在现实生活中有着广泛的应用 例 如 顾客购物模式分析 网络访问模式分析 科学研究或自然灾害中的序列或与时间有 关的过程分析 疾病治疗过程分析 d n a 序列分析等等 因此 对于序列模式挖掘的深 入研究必将有力地推动相关领域的研究 用户在使用数据挖掘系统进行数据挖掘时经常带有随意性 反复性 即用户不大可 能一次就确定进行数据挖掘的最小支持度阈值 而需要进行多次反复 如果数据挖掘系 统运行的速度很慢 那么用户就不可能容忍漫长的等待时间 为提高用户使用系统的满 意度 可以将用户使用系统过程中发现的知识保存在知识库中 以加快系统的运行速度 本文在此基础上 设计了序列模式数据挖掘系统的结构 提出了知识库所存储知识的结 构 知识库中存储有所包含知识的最小支持度阈值 所发现的序列模式以及它们的支持 度 然后根据用户查询时可能提出的最小支持度 将这些知识分块存储 便于查询 提 出了建立知识库的方法 知识库在何时更新 如何更新等等 对于序列模式数据挖掘来说 挖掘算法是系统成功的关键 研究人员一直在努力设 计效率更高的数据挖掘算法 本文在研究当前比较流行的一些序列模式挖掘算法的基础 上 重点分析了m e m i s p 算法的不足 针对这些不足 本文提出了一种改进的m e m i s p 算 法 在将数据读入内存时即将原数据库进行投影操作 去除了非频繁项 避免了在进行 数据挖掘时的无用读取 设计了新的算法处理的数据结构 并根据这样的结构 提出了 算法新的处理过程 使改进的算法更高效 关键词 数据仓库 知识库 序列模式 挖掘算法 塑塑塑型型鲨l 塑塞 a b s t r a c t s e q u e n t i a lp a t t e r n m i n i n g w h i c hd i s c o v e r s f r e q u e n ts u b s e q u e n c e sa s i n t e r e s r i n gp a t t e r n si nas e q u e n c ed a t a b a s e i sa ni m p o r t a n ta n da c t i v er e s e a r c h p r o b l e mw i t hb r o a da p p l i c a t i o na tp r e s e n t i n c l u d i n gt h ea n a l y s i so fc u s t o m e r p u r c h a s ep a t t e r n sa n dw e ba c c e s s p a t t e r n s t h ea n a l y s i so fs e q u e n c i n go r t l m e r e l a t e dp r o c e s s e ss u c ha ss c i e n t i f i ce x p e r i m e n t s n a t u r a ld i s a s t e r s a n d d l s e a s et r e a t m e n t s t h ea n a l y s i so fd n as e q u e n c e s a n ds oo n s o t h er e s e a r c h o ft h e s e q u e n t i a lp a t t e r nm i n i n gw i l l s t r o n g l yp r o m o t et h er e l a t e da r e a r e s e a r c h e s u s e r sm a yr e p e a t e d l yp u tf o r w a r d m a n yd i f f e r e n ts u p p o r tt h r e s h o l d sa tr a n d o m i ft h er u n n i n gs p e e do ft h ed a t a m i n i n gs y s t e mi sv e r ys l o w u s e r sm a yn o tt e l e r a t e s ol o n gp e r i o d f o ri m p r o v i n gu s e r ss a t i s f a c t i o ni nt h es y s t e mf u n c t i o n i n g t h es y s t e c a ns a v et h es e q u e n t i a lp a t t e r n si n t ot h ek n o w l e d g eb a s et h a tg a i n e d i nt h es y s t e mr u n n i n g a n ds p e e du pt h es y s t e mr u n n i n g t h i sd i s s e r t a t i o nd u t f o r w a r dt h es t r u c t u r eo ft h es e q u e n t i a lp a t t e r nm i n i n gs y s t e ma n dt h e k n o w l e d g e s a v e di nt h ek b t h ek n o w l e d g es t r u c t u r e s t o r e di nk bi n e l u d i n gt h em i n i 叫m s u p p o r tt h r e s h o l d s e q u e n t i a lp a t t e r n sa n dt h e i rs u p p o r t t h e s es e q u e n t i a l p a t t e r n ss t o r e di nk bi n b l o c kb a s e do nt h e i rs u p p o r t t h ed i s s e r t a t i o np r o p o s e d t h em e t h o do fc r e a t i n gk b a n dw h e na n dh o wt ou p d a t e t h ek b a st os e q u e n t i a l p a t t e r nm i n i n g m i n i n ga l g o r i t h mi s v e r yi m p o r t a n t r e 8 e a r c h e r sa r es t u d y i n gh a r dt od e v e l o pe f f i c i e n td a t a m i n i n ga l g o r i t h m sa ta l l t i m e s b a s e do ns o m e s e q u e n t i a lp a t t e r nm i n i n ga l g o r i t h m t h ed i s s e r t a t i o n a n a l y z e dt h es h o r t a g eo ft h em e m i s pa l g o r i t h m a n dp r o p o s e da ni m p r o v e dm e m i s p a l g o r i t h m t h ei m p r o v e dm e m i s pa l g o r i t h mp r o j e c t so r i g i n a ld a t a b a s ei n t ot h e m e m o r yw i t hf r e q u e n ti t e m s a n dr e m o v e st h o s ei n f r e q u e n t i t e m s t h ea l g o r i t l i i l a v o i d su s e l e s sr e a d i n gw h e nt h es y s t e mi s r u n n i n g t h ep a p e rp r o p o s e dn e wd a t a s t r u c t u r ea n dp r o c e s s i n gm e t h o do ft h ei m p r o v e da l g o r i t h m t h i sm a k e st h en e w a l g o r i t h mm o r ee f f i c i e n ta n de a s yt or u n k e y w o r d s d a t aw a r e h o u s e k n o w l e d g eb a s e s e q u e n t i a lp a t t e r n m i n i n ga l g o r it h m 2 山东科技大学硕士学位论文 l 绪论 1 绪论 1 1 选题的意义 随着计算机技术的日益普及 大容量存储技术的发展以及条形码等数据获取技术的 广泛应用 人们在日常事务处理和科学研究中积累了大量的数据 这些保存的数据中 其中绝大部分都是呈现时间序列类型的数据 所谓时间序列类型数据就是按照时间先后 顺序排列各个观测记录的数据集 时间序列在社会生活的各个领域都广泛地存在 如金 融证券市场中每天的股票价格变化 商业零售行业中某项商品每天的销售额 气象预报 研究中某一地区的每天气温与气压的读数 以及在生物医学中某一症状病人在每个时刻 的心跳变化等等 不仅如此 时间序列也是反映事物运动 发展 变化的一种最常见的 图形化描述方式 例如在1 9 7 4 年到1 9 8 9 年对1 5 种具有国际影响的报纸中 对其包含的 各种图形进行采样统计 结果发现其中至少7 5 是采用时间序列的图形方式进行描述 的 通过曲线打点的方式 非常有利于人们在高级层次上来展现和理解事物的变化 而 且人类早在1 0 世纪前就知道通过可视化时间序列来展现事物的变化发展 随着所存储的数据量的急剧增长 特别是零售业每天从超市的收银机中获得大量的 数据 现在的计算机用户很难再像从前那样自己根据数据的分布找出规律 并根据此规 律进行分析决策 因此 数据挖掘技术的应运而生给整个社会带来了生机 也给零售业带来了曙光 数据挖掘技术中的关联规则 序列模式挖掘等 可以发现这些商机 通过挖掘商家的历 史数据可以找到商品 顾客 销售时间 以及商品摆放位置之间的关系 数据挖掘技术 在零售业中得到了广泛的应用 一个非常流行的为企业带来巨大经济效益的数据挖掘实 例是 美国加州某个超市通过数据挖掘系统从记录着每天销售情况和顾客情况的数据库 中发现了一条规律 在下班后来超市购买婴儿尿布的多为年轻男性 而他们往往同时购 买了啤酒 因此 超市把这两者商品摆放在一起 同时把佐酒食品和一些男士日用品也 放在附近 结果上述几种商品的销量马上成倍增长 数据挖掘的目的是否能够达到在很大程度上和数据挖掘系统所采用的挖掘算法密切 相关 一些算法限制了挖掘的复杂度和挖掘的精度 因此 算法在数据挖掘中起了至关 重要的作用 本论文主要是研究数据挖掘中的序列挖掘算法 针对a p r i o r i 算法 s p a d e 算法和p r e f i x s p a n 算法等的缺点 改进了一种序列挖掘算法 m e m i s p 序列模式挖掘 些至型垫奎兰堡主兰堡笙苎 堕堡 算法 通过充分利用计算机资源 减少磁盘i o 和扫描数据库的次数 使数据直接在内 存中进行处理 加快序列模式挖掘算法的执行速度 减少执行时间 从而提高序列模式 挖掘的效率 1 2 数据挖掘技术产生的背景及定义 随着数据库应用技术和决策支持技术的发展 随着人们对信息需求水平的提高 数 据仓库技术和数据库知识发现技术越来越受到学术界和产业界的广泛关注 数据库中的 知识发现 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 s k d d 是近年来随着数据库和人工智能 技术的发展而出现的 它是从大量数据中提取出可信的 新颖的 有效的并能被人理解 的模式的高级处理过程 它主要采用机器学习算法或统计方法进行知识学习 1 2 1 数据爆炸但知识贫乏 随着数据库技术的迅速发展以及数据库管理系统的广泛应用 人们积累的数据越来 越多 激增的数据背后隐藏着许多重要的信息 人们希望能够对其进行更高层次的分析 以便更好地利用这些数据 目前的数据库系统可以高效地实现数据的录入 查询 统计等功能 但无法发现数 据中存在的关系和规则 无法根据现有的数据预测未来的发展趋势 缺乏挖掘数据背后 隐藏的知识的手段 导致了 数据爆炸而知识贫乏 的现象 计算机技术的另一领域 人工智能自1 9 5 6 年诞生之后取得了重大进展 经历了 博弈时期 自然语言理解 知识工程等阶段 目前的研究热点是机器学习 机器学习是 用计算机模拟人类学习的一门科学 比较成熟的算法有神经网络 遗传算法等 用数据库来存储数据 用机器学习的方法来分析数据 挖掘大量数据背后的知识 这两者的结合促成了数据挖掘的产生 数据挖掘也称为数据库中的知识发现 k d d k n o w e d g ed i s c o v e r yi nd a t a b a s e s 实际上 数据挖掘是一门交叉性学科 涉及到 数据库技术 统计学 机器学习 高性能计算 模式识别 神经网络 数据可视化 信 息检索 图像与信号处理和空间数据分析等多个领域的知识 数据挖掘发现的知识可以 用在信息管理 过程控制 科学研究 决策支持等许多方面 1 2 2 支持数据挖掘技术的基础 数据挖掘使数据库技术进入了一个更高级的阶段 它不仅能对过去的数据进行查询 2 些查型茎查兰堡主兰垒堡奎 堕笙 和遍历 并且能够找出过去数据之间的潜在联系 从而促进信息的传递 现在数据挖掘 技术在商业应用中已经可以投入使用 因为对这种技术进行支持的三种基础技术已经发 展成熟 他们是 海量数据搜集 商业数据库现在正在以一个空前的速度增长 并且数据仓库正在 广泛地应用于各种行业 强大的多处理器计算机 计算机硬件性能越来越高 并行多处理机技术也已经成 熟 数据挖掘算法 数据挖掘算法经过了这l o 多年的发展也已经成为一种成熟 稳 定且易于理解和操作的技术 1 2 3 数据挖掘的演变过程 数据挖掘其实是一个逐渐演变的过程 电子数据处理的初期 人们就试图通过某些 方法来实现自动决策支持 当时机器学习成为人们关心的焦点 机器学习的过程就是将 一些已知的并已被成功解决的问题作为范例输入计算机 机器通过学习这些范例总结并 生成相应的规则 这些规则具有通用性 使用它们可以解决某一类的问题 随后 随着 神经网络技术的形成和发展 人们的注意力转向知识工程 知识工程不同于机器学习 它直接给计算机输入己被代码化的规则 计算机通过使用这些规则来解决某些问题 专 家系统就是这种方法所得到的成果 但它有投资大 效果不甚理想等不足 8 0 年代人们 叉在新的神经网络理论的指导下 重新回到机器学习的方法上 并将其成果应用于处理 大型商业数据库 随之在8 0 年代末出现了一个新的术语 即数据库中的知识发现 简称 k d d k n o w l e d g ed i s c o v e r yi nd a a b a s e 它泛指所有从源数据中发掘模式或联系的方 法 人们接受了这个术语 并用k d d 来描述整个数据发掘的过程 包括最开始的制定业 务目标到最终的结果分析 而用数据挖掘 d a t am i n i n g 来描述使用挖掘算法进行数据 挖掘的子过程 但最近人们也常把这两种说法等同起来 数据挖掘侧重数据库角度 k d d 侧重人工智能角度 数据仓库技术的发展与数据挖掘有着密切的关系 数据仓库的发展是促进数据挖掘 越来越热的原因之一 但是 数据仓库并不是数据挖掘的先决条件 因为有很多数据挖 掘可直接从操作数据源中挖掘信息 山东科技大学硕士学位论文 l 绪论 1 2 4 数据挖掘的定义 数据挖掘 d a t am i n i n g 的比较公认的定义是w j f r a w l e y g p i a t e t s k y s h a p i r o 等人提出的 数据挖掘就是从大型数据p 的数据中提取人们感兴趣的知识 这些知识是 隐舍的 事先未知的 但潜在有用的信息 提取的知识可以表示为概念 c o n c e p t s 规则 r u l e s 规律 r e g u l a r i t i e s 模式 p a t t e r n s 等形式 所以 数据挖掘的对象可以是结构化的 如关系数据痒中的数据 也可以是半结构 化的 如文本 图形和图像数据 甚至是分布在网络上的异构型数据 发现知识的方法 可以是数学的 也可以是非数学的 可以是演绎的 也可以是归纳的 发现的知识可以 被用于信息管理 查询优化 决策支持和过程控制等 还可以用于数据自身的维护 因 此 数据挖掘是一门交叉学科 它把人们对数据的应用从低层次的简单查询 提升到从 数据中挖掘知识 提供决策支持 在这种需求牵引下 汇聚了不同领域的研究者 尤其 是数据库技术 人工智能技术 数理统计 可视化技术 并行计算等方面的学者和工程 技术人员 投身到数据挖掘这一新兴的研究领域 形成新的技术热点 这里所说的知识发现 不是要求发现放之四海而皆准的真理 也不是要去发现崭新 的自然科学定理和纯数学公式 更不是什么机器定理证明 实际上 所有发现的知识都 是相对的 是有特定前提和约束条件 面向特定领域的 同时还要能够易于被用户理解 最好能用自然语言表达所发现的结果 1 3 数据挖掘的研究对象 应用及其发展 1 3 1 数据挖掘的研究对象 数据挖掘中要分析的数据的范围非常广泛 从自然科学 社会科学 商业数据 到 科学处理产生的数据或卫星观测得到的数据 它们的数据表示形式也是各种各样 有关 系型 也有层次型 网状型 由于关系数据库应用广泛 具有规整统一的组织结构 规 范通用的查询语言 特别是关系之间及属性之间具有平等性的优点 因此 目前k d d 的 主要对象仍然是关系数据库 1 3 2 目前数据挖掘的应用情况 数据库中发现知识 k d d 一词是1 9 8 9 年在美国底特律市召开的第一届k d d 国际 数据库中投现知识 k d d 一词是1 9 8 9 年在美国底特律市召开的第一届k d d 国际 生堡型塾查堂堡主堂堡堕苎 堑堡 学术会议上正式形成的 到目前为止 由美国人工智能协会主办的k d d 国际研讨会已经 召开了8 次 规模由原来的专题讨论会发展到国际学术大会 研究重点也逐渐从发现方 法转向系统应用 注重多种发现策略和技术的集成 以及多种学科之间的相互渗透 随 着k d d 在学术界和工业界的影响越来越大 国际k d d 组委会于1 9 9 5 年把专题讨论会更名 为国际会议 在加拿大蒙特利尔市召开了第一届知识发现与数据挖掘国际学术会议 以 后每年召开一次 1 9 9 8 年在美国纽约举行的第四届知识发现与数据挖掘国际学术会议不 仅进行了学术讨论 并且有3 0 多家软件公司展示了他们的数据挖掘软件产品 不少软件 已在北美 欧洲等国得到应用 1 9 9 9 年 亚太地区在北京召开的第三届p a k d d 会议收到 1 5 8 篇论文 空前热烈 i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊率先在1 9 9 3 年 出版了k d d 技术专刊 并行计算 计算机网络和信息工程等其他领域的国际学会 学刊 也把数据挖掘和知识发现列为专题和专刊讨论 甚至到了脍炙人口的程度 数据挖掘所要处理的问题 就是在庞大的数据库中找出有价值的隐藏事件 并且加 以分析 获取有意义的信息 归纳出有用的结构 作为企业进行决策的依据 其应用非 常广泛 只要该产业有分析价值与需求的数据库 皆可利用m i n i n g 工具进行有目的的发 掘分析 常见的应用案例多发生在零售业 制造业 财务金融保险 通讯及医疗服务 1 商场从顾客购买商品中发现一定的关系 提供打折购物券等 提高销售额 2 保险公司通过数据挖掘建立预测模型 辨别出可能的欺诈行为 避免道德风险 减少成本 提高利润 3 在制造业中 半导体的生产和测试中都产生大量的数据 就必须对这些数据进 行分析 找出存在的问题 提高质量 4 电子商务的作用越来越大 可以用数据挖掘对网站进行分析 识别用户的行为 模式 保留客户 提供个性化服务 优化网站设计 一些公司运用数据挖掘的成功案例 显示了数据挖掘的强大生命力 美国的a u t o t r a d e r c o m 是世界上最大的汽车销售站点 每天都会有大量的用户对网 站上的信息点击 寻求信息 该站点运用了s a s 软件进行数据挖掘 每天对数据进行分 析 找出用户的访问模式 对产品的喜欢程度进行判断 并设置了特定服务 取得了成 功 r e u t e r e s 是世界著名的金融信息服务公司 其利用的数据大都是外部的数据 因此 数据的质量就是公司生存的关键所在 必须从数据中检测出错误的成分 r e u t e r e s 用 s p s s 的数据挖掘工具s p s s c l e m e n t i n e 建立数据挖掘模型 极大地提高了错误的检测 5 山东科技大学硕士学位论文 1 绪论 保证了信息的正确和权威性 b a s se x p o r t 是世界最大的啤酒进出口商之 在海外8 0 多个市场从事交易 每个 星期传送2 3 0 0 0 份定单 这就需要了解每个客户的习惯 如品牌的喜好等 b a s se x p o r t 用i b m 的i n t e l l i g e n tm i n e r 很好地解决了上述问题 1 3 3 国内数据挖掘研究情况 国内从事数据挖掘研究的人员主要在大学 也有部分在研究所或公司 所涉及的研 究领域很多 一般集中于学习算法的研究 数据挖掘的实际应用以及有关数据挖掘理论 方面的研究 目前进行的大多数研究项目是由政府资助进行的 如国家自然科学基金 8 6 3 计划 九五 计划等 但还没有关于国内数据挖掘产品的报道 1 3 4 数据挖掘的研究热点 就目前来看 数据挖掘的几个熟点包括基于w e b 的数据挖掘 w e bd a t am i n i n g 空间数据挖掘 s p a t i a ld a t am i n i n g 生物信息或基因 b i o i n f o r m a t i c s g e n o m i c s 的数据挖掘及其文本的数据挖掘 t e x t u a lm i n i n g 下面就这几个方面加以简单介绍 1 3 4 1 基于w e b 的数据挖掘 基于w e b 的数据挖掘 简称w e b 挖掘 的定义是 针对包括w e b 页面内容 页面之 间的结构 用户访问信息 电子商务信息等在内的各种w e b 数据 应用数据挖掘方法以 发现有用的知识来帮助人们从w w w 中提取知识 改进站点的设计 更好地开展电子商务 w e b 挖掘总的说来分为内容挖掘 访问信息挖掘和结构挖掘三类 1 3 4 2 空间数据挖掘 空间数据挖掘 或称为空间数据库上的知识发现 是提取空间数据库中的潜在知识 空间关系和发现有用的特征和模式 空间数据挖掘在地理信息系统 图像数据勘测和医 学图像处理等领域都有着广泛的应用 1 3 4 3 生物信息或基因的数据挖掘 基于生物信息或基因数据挖掘会给人类带来巨大好处 例如 基因的组合千变万化 得某种病的人的基因和正常人的基因到底差别多大 能否找出其中不同的地方 进而对 其不同之处加以改变 使之成为正常基因 这都需要数据挖掘技术的支持 对于生物信息或基因的数据挖掘和通常的数据挖掘相比 无论在数据的复杂程度 数据量还有分析和建立模型的算法而言 都要复杂得多 从分析算法上讲 更需要一些 6 坐奎型苎查兰婴主兰垡兰奎 竺鲨 新的和好的算法 现在很多研究机构和厂商正在致力于这方面的研究 但就技术和软件 而言 还远没有达到成熟的地步 1 3 4 4 文本数据挖掘 人们很关心的另外一个话题是文本数据挖掘 举个例子 在客户服务中心 把同客 户的谈话转化为文本数据 再对这些数据进行挖掘 进而了解客户对服务的满意程度和 客户的需求以及客户之间的相互关系等信息 从这个例子可以看出 无论是在数据结构 还是在分析处理方法方面 文本数据挖掘和前面谈到的数据挖掘相差很大 文本数据挖 掘并不是一件容易的事情 尤其是在分析方法方面 还有很多需要研究的专题 目前市 场上有 些类似的软件 但大部分方法只是把文本移来移去 或简单地计算一下某些词 汇的出现频率 并没有真正的分析功能 随着计算机计算能力的发展和业务复杂性的提高 数据的类型会越来越多 越来越 复杂 数据挖掘将发挥出越来越大的作用 1 3 5 其它方向 目前 数据挖掘研究与开发的总体水平相当于数据库技术在7 0 年代所处的地位 迫 切需要类似于关系模式 d b m s 系统和s q l 查询语言等理论和方法的指导 才能使数据挖 掘的应用得以普遍推广 因此 除了前文所述的四个领域的数据挖掘技术外 下面几个 也是具有挑战性的研究方向 发现语言的形式化描述 即研究专门用于知识发现的数据挖掘语言 也许会像s q l 语言一样走向形式化和标准化 加强对各种非结构化数据的开采 如对文本数据 图形数据 视频图像数据 声 音数据乃至综合多媒体数据的开采 知识的表达和解释机制 许多应用中重要的是用户能够理解发现的知识 这要求 知识的表达不仅限于数字或符号 而是更容易理解的方式 如图形 自然语言和 可视化技术等 只有当数据挖掘系统能提供更好的解释机制 用户才能更有效地 评价这些知识 并且区分出哪些是真正有用的知识 哪些只是常识性的知识或异 常情况 知识的维护和更新 新的数据积累可能导致以前发现的知识失效 这些知识需要 动态维护和及时更新 目前研究采用增量更新的方法来维护已有的知识 比如 d w c h e u n g 等提出了维护关联规则的增量算法 堂堕塑堂型兰墅堕 堑丝 不管怎样 需求的牵引与市场的推动是永恒的 数据挖掘将首先满足信息时代用户 的急需 大量的基于数据挖掘的决策支持软件产品将会问世 只有从数据中有效地提取 信息 从信息中及时地发现知识 才能为人类的思维决策和战略发展服务 也只有到那 时 数据才能够真正成为与物质 能源相媲美的资源 信息时代才会真正到来 1 4 数据挖掘中的疑难问题 数据挖掘的许多技术源于机器学习方法 但由于现实世界数据库存在一些固有的特 点 因此给d m 带来一些难点 正是这些关键之处 才形成了d m 领域自己独特的研究方 向 下面加以描述 1 动态变化的数据 数据的动态变化是大多数数据库的一个主要特点 一个联机系统应能够保证数据的 变化不会导致错误的发现 数据挖掘的数据源可以有关系数据库数据 多媒体数据 超 文本 空间数据 时态数据 事务数据 文本文件 电子表格等等 2 噪声 由于人为因素的影响 如数据的手工录入以及主观选取数据等 从而使得数据具有 噪声 带噪声的数据会影响抽取的模式的准确性 3 数据不完整 数据库中某些个别的记录其属性域可能存在空值现象 另外对某一发现来说还可能 完全不存在其所必需的记录域 这种数据的不完整性将给发现 评估和解释一些重要的 模式带来困难 4 冗余信息 数据库中同一信息有时存储在多个地方 函数依赖就是一个通常的冗余形式 冗余 信息可能造成错误的知识发现 至少有些发现是用户完全不感兴趣的 为避免这种情况 发生 系统需要知道数据库中有哪些固有的依赖关系 5 数据稀疏 相应于可能的巨大的发现空间 数据库中所记录的实际数据的密度是非常稀疏的 这对传统的经验定律发现方法是个挑战 6 超大数据量 数据库中数据的迅速增长是数据挖掘得以发展的原因之一 例如 气象 天文 地 生堡型茎查兰堡主兰垡堡苎 焦堡 震 每天千兆级 要求一天内处理完 这也正是对数据挖掘技术研究的挑战 穷举法 经验分析方法对数兆字节 数吉字节甚至数特字节的数据显得无能为力 此时d m 系统必 须采用一定的数据汇集方法根据用户定义的发现任务 选择有关的域空间 采取随机抽 样的方法 对样本进行分析 以上是现实世界数据库中存在的一些不利因素 在d m 发展的道路上还有许多困难要 加以克服 有许多问题有待研究 如不适当的统计意识 过多的冗余模式 现有系统的 集成 多策略系统等等 1 5 论文的主要研究内容和结构安排 目前 序列模式挖掘算法主要是以下几类算法 1 以a p r i o r i 为基础的序列模式挖掘算法 该类算法的最大缺点是需要多次扫描 数据库 同时采用哈希树作为主要存储结构 这样造成算法的时间和空间复杂度较大 同时挖掘的效率也很低 2 以s p a d e 为代表的非a p r i o r i 类算法 这类算法主要是针对以a p r i o r i 为基础 的序列模式算法中多次扫描数据库的缺点来改进的 它只需要对数据库扫描三次 3 以p r e f i x s p a n 算法为代表的模式增长算法 通过多次投影数据库 不断减少 数据库的大小 从而提高算法的执行效率 综上所述 这些算法或者是尽可能地减少数据库的扫描次数 或者是通过投影原数 据库 产生中间结果的数据库 减少要扫描的数据库的大小 但是 这些方法都不太理 想 本文所研究的m e m i s p 算法可以充分利用计算机资源 最大限度地提高序列模式数据 挖掘的效率 本文以下几部分构成情况如下 第二章介绍了数据挖掘的内容和实质 数据挖掘的步骤及数据挖掘系统的组成 数 据挖掘的功能 方法 以及数据挖掘与其它系统的关系 从总体上论述了数据挖掘技术 并介绍了数据仓库技术 第三章介绍了目前的序列模式数据挖掘算法 主要有g s p 算法 s p a d e 算法 p r e f i x s p a n 算法等 第四章论述了本文中所要研究的序列模式序列的设计 将每次进行数据挖掘时所得 到的知识保存到知识库中 并提出了知识库的结构 知识库的建立以及怎样更新知识库 等问题 9 山东科技大学硕士学位论文 i 绪论 第五章重点讨论了序列模式挖掘算法 提出了一种新的m e m i s p 算法处理数据的结 构 改进了m e m i s p 算法 使得该算法更容易处理数据挖掘问题 1 0 山东科技大学硕士学位论文 2 数据挖掘技术 2 数据挖掘技术 2 1 数据挖掘的内容和实质 随着数据挖掘技术研究的逐步走向深入 人们越来越清楚地认识到数据挖掘的研究 其实主要就是三个技术支柱 数据库 人工智能和数理统计 2 1 1 数据库技术 数据库技术在经过了2 0 世纪8 0 年代的辉煌之后 已经在各行各业成为一种数据库 文化或时尚 一方面f h 于数据库文化的迅速普及 用数据库作为知识源具有坚实的基础 另一方面 对于一个感兴趣的特定领域 客观世界 先用数据库技术将其形式化并组 织起来 就会大大提高知识获取起点 以后从中发掘或发现的所有知识都是针对该数据 库而言的 因此 在需求的驱动下 很多数据库学者转向对数据仓库和数据挖掘的研究 从对演绎数据库的研究转向对归纳数据库的研究 2 1 2 人工智能 人工智能学者开始着手基于案例的推理 尤其是从事机器学习的科学家们 不再满 足自己构造的小样本学习模式的象牙塔 开始正视现实生活中大量的 不完全的 有噪 声的 模糊的 随机的大数据样本 也走上了数据挖掘的道路 2 1 3 数理统计 数理统计是应用数学中最重要 最活跃的学科之一 它在计算机发明之前就诞生了 迄今已有几百年的发展历史 如今相当强大有效的数理统计方法和工具已成为信息咨询 业的基础 信息时代 咨询业更为发达 然而 数理统计和数据库技术结合得并不算快 数据库查询语言s q l 中的聚合函数功能极其简单 就是一个证明 一旦人们有了从数据 查询到知识发现 从数据演绎到数据归纳的要求 概率论和数理统计就获得了新的生命 力 所以才会在数据挖掘和知识发现 d m k d 这个结合点上 立即呈现出一派繁荣景象 一向以数理统计工具和可视化计算闻名的美国s a s 公司 领先宣布进入d m k d 行列 数据挖掘所能发现的知识有如下几种 1 广义型知识 反映同类事物共同性质的知识 l l 当至型苎查兰堡主兰垡堡苎 茎塑丝塑苎查 2 特征型知识 反映事物各方面的特征知识 3 差异型知识 反映不同事物之间属性差别的知识 4 关联型知识 反映事物之间依赖或关联的知识 5 预测型知识 根据历史的和当前的数据推测未来数据 6 偏离型知识 揭示事物偏离常规的异常现象 所有这些知识都可以在不同的概念层次上被发现 随着概念树的提升 从微观到中 观再到宏观 以满足不同用户 不同层次决策的需要 例如 从一家超市的数据仓库中 可以发现的一条典型关联规则可能是 买面包和黄油的顾客十有八九也买牛奶 也可能 是 买食品的顾客几乎都用信用卡 这种规则对于商家开发和实旅客户化的销售计划和 策略是非常有用的 2 2 数据挖掘的步骤及挖掘系统的组成 许多人把 数据挖掘 视为另一个常用的术语 数据库中的知识发现 或k d d 的同 义词 而另一些人只是把数据挖掘视为知识发现过程的一个基本步骤 知识发现的过程 如图2 1 所示 由以下几个步骤组成 1 数据清理 消除噪声或不一致数据 2 数据集成 多种数据源可以组合在一起 3 数据选择 从数据库中检索与分析任务相关的数据 4 数据变换 数据变换或统一成适合挖掘的形式 如通过汇总或聚集操作 5 数据挖掘 基本步骤 使用智能方法提取数据模式 6 模式评估 根据某种兴趣度度量 识别表示知识的真正有趣的模式 7 知识表示 使用可视化和知识表示技术 向用户提供挖掘的知识 山东科技大学硕士学位论文 2 数据挖掘技术 图2 1 数据挖掘的步骤 数据挖掘步骤可以与用户或知识库交互 有趣的模式提供给用户 或作为新的知识 存放在知识库中 根据这种观点 数据挖掘只是整个过程中的一步 尽管是最重要的一 步 因为它发现隐藏的模式 然而 在产业界 媒体和数据库研究界 数据挖掘 比较长的术语 数据库中的知 识发现 更流行 因此数据挖掘的广义观点 数据挖掘是从存放在数据库 数据仓库或 其他信息库中的大量数据中挖掘有趣知识的过程 基于这种观点 如图2 2 所示 典型的数据挖掘系统具有以下主要成分 1 数据库 数据仓库或其他信息库 这是一个或 组数据库 数据仓库 电子表 格或其他类型的信息库 可以在数据上进行数据清理和集成 2 数据库或数据仓库服务器 根据用户的数据挖掘请求 从数据库或数据仓库服 务器提取相关数据 3 知识库 这是领域知识 用于指导搜索 或评估结果模式的兴趣度 这种知识 可能包括概念分层 用于将属性或属性值组织成不同的抽象层 用户确信方面的知识也 可以包含在内 4 数据挖掘引擎 这是数据挖掘的基本部分 由一组功能模块组成 用于特征化 山东科技大学硕士学位论文 2 数据挖掘技术 关联 分类 聚类分析以及演变和偏差分析 5 模式评估模块 通常此成分使用兴趣度度量 并与数据挖掘模块交互 以便将 搜索聚焦在有趣的模式上 6 图形用户界面 本模块在用户和数据挖掘系统之间通信 允许用户与系统交互 指定数据挖掘或查询任务 提供信息 帮助搜索聚焦 根据数据挖掘的中间结果进行探 索式数据挖掘 图2 2 典型的数据挖掘系统结构 2 3 数据挖掘的功能和模式的度量 2 3 1 数据挖掘的功能 数据挖掘功能用于指定数据挖掘任务中要找的模式类型 数据挖掘任务一般可以分 为两类 描述和预测 描述性挖掘任务刻划数据库中数据的一般特性 预测性挖掘任务 在当前数据上进行推断 以进行预测 具体来说 数据挖掘的功能主要有如下几种 1 概念 类描述 特征化和区分 数据可以与类或概念相关联 类或概念的描述称为类 概念 c a s s c o n c e p t 1 4 山东科技大学硕士学位论文 2 数据挖掘技术 d e s c r i p t i o n 这种描述可以通过下述方法得到 数据特征化 一般地汇总所研究类 通常称为目标类 t a r g e tc l a s s 的数据 数据区分 将目标类与一个或多个比较 类 通常称为对比类 c o n t r a s t i n gc l a s s 进行比较 数据特征化和比较 数据特 征化 d a t ac h a r a c t e r i z a t i o n 是目标类数据的一般特征或特性的汇总 数据区分 d a t a d i s c r i m i n a t i o n 是将目标类对象的一般特性与一个或多个对比类对象的一般特性比较 2 关联分析 关联分析 a s s o c i a t i o na n a l y s i s 发现关联规则 这些规则展示属性一值频繁地在 给定数据集中一起出现的条件 关联分析广泛用于购物篮或事务数据分析 更形式地 关联规则 a s s o c i a t i o nr u l e 是形如x j y 即 a 1 八a 2 八a i i l 等b 1 八b 2 八 b n 的规则 其中 a i i f 1 2 m b j j f 1 2 n 是属性一值对 关联 规则解释为 满足x 中条件的数据库元组多半也满足y 中的条件 3 分类和预测 分类 c l a s s i f i c a t i o n 是这样的过程 它找出描述并区分数据类或概念的模型 或 函数 以便能够使用模型预测类标记未知的对象类 导出模型是基于对训练数据集 即 其类标记已知的数据对象 的分析 导出模型可以用多种形式表示 如分类 i f t h e n 规则 判定树 数学公式或神经网络 在某些应用中 人们可能希望预测某些空缺的或不知道的数据值 而表示类标记 当被预测的值是数值数据时 通常称之为预测 p r e d i c t i o n 4 聚类分析 与分类和预测不同 聚类 c l u s t e r i n g 分析数据对象 而不考虑已知的类标记 对象根据最大化类内的相似性 最小化类间的相似性的原则进行聚类或分组 即对象的 簇 聚类 这样形成 使得一个簇中的对象具有很高的相似性 而与其他簇中的对象很 不相似 5 孤立点分析 数据库中可能包含一些数据对象 它们与数据的一般行为或模式不一致 这些数据 对象是孤立点 o u t l i e r 大部分数据挖掘方法将孤立点视为噪声或异常而丢弃 然而 在一些应用中 如欺骗检测 罕见的事件可能比正常出现的那些更有趣 孤立点数据分 析称作孤立点挖掘 o u t l i e rm i n i n g 6 演变分析 数据演变分析 e v o l u t i o na n a l y s i s 描述行为随时间变化的对象的规律或趋势 1 5 坐垄型苎奎兰堡主兰堡丝兰 塾塑丝塑垫查 并对其建模 这类分析的不同特点包括时间序列数据分析 序列或周期模式匹配和基于 类似性的数据分析 2 3 2 数据挖掘的模式度量 数据挖掘系统具有产生数以千计 甚至数以万计的模式和规则的潜在能力 然而 实际上 对于给定用户来说 在可能产生的模式中 只有一小部分是他感兴趣的 一个模式是有趣的 i n t e r e s t i n g 如果 它易于被人理解 在某种程度上对于 新的或测试数据是有效的 是潜在有用的 是新颖的 如果一个模式符合用户确信 的某种假设 它也是有趣的 有趣的模式表示知识 存在一些模式兴趣度的客观度量 这些度量基于所发现模式的结构和关于它们的统 计 对于形如x j y 的关联规则 一种客观度量是规则的支持度 s u p p o r t 规则的支 持度表示满足规则的样本百分比 支持度是概率p x u y 其中 x u y 表示同时包含x 和y 的事务 即项集x 和y 的并 关联规则的另一种客观度量是置信度 c o n f i d e n c e 置信度是条件概率p y l x 即包含x 的事务也包含y 的概率 更形式地 支持度和置 信度定义为 s u p p o r t x 圳 p x u y 翌型c 竺o u n t 黜 1 3j c n f i d e n c e x y p yx 里 c o u n t铲 其中 s u p p o r t c o u n t x u y 是数据库中包含项集 x u y 的事务数 c o u n t d 是 数据库中的事务总数 c o u n t x 是数据库中包含项集x 的事务数 一般地 每个兴趣度度量都与一个阚值相关联 该阈值可以由用户控制 例如 不 满足置信度闽值5 0 的规则可以认为是无趣的 低于阚值的规则可能反映噪声 异常或 少数情况 可能不太有价值 2 4 数据挖掘的方法 随着数据挖掘研究逐步走向深入 数据挖掘和知识发现的研究已经形成了三个强大 的技术支柱 数据库 人工智能和数理统计 目前数据挖掘的主要研究内容包括基础理 论 挖掘算法 数据仓库 可视化技术 知识表示方法 发现知识的维护和再利用 半 结构化和非结构化数据中的知识发现以及网上数据挖掘等 1 6 些至型苎查竺堡主堂垡丝兰 墼塑垫塑垫查 数据挖掘算法的好坏将直接影响到所发现知识的好坏 目前大多数的研究都集中在 数据挖掘算法和应用上 数据挖掘中几种常用的方法如下 2 4 1 人工神经网络 a r t i f i c i e in e u r a in e t w o r k s 人工神经网络最常见的定义是 人工神经网络是由具有适应性的简单单元组成的广 泛互连的网络 它的组织能够模拟生物神经系统对真实世界所做出的交互反应 它从结构上模仿生物神经网络 是一种通过训练来学习的非线性预测模型 可以完 成分类 聚类 特征采掘等多种数据采掘任务 人工神经网络在m p 模型和h e b b 学习规则的基础上 建立了三大类多种模型 前馈式网络 它以感知机 反向传播模型 函数型网络为代表 可用于预测 模 式识别等方面 反馈式网络 它以h o p f i e l d 的离散模型和连续模型为代表 分别用于联想记忆 和优化计算 自组织网络 它以a r t 模型 k o h o l o n 模型为代表 主要用于聚类 通过人工神经网络所获取的知识体现在网络连接的权值上 这些权值是一个分布式 的矩阵结构 人工神经网络的学习体现在人工神经网络权值的逐步计算上 包括反复迭 代或累加计算 人工神经网络的学习分为有示教学习与无示教学习两类 但两种学习类 型也可以综合用于一个模型中 在数据挖掘中 较常用的人工神经网络模型有反向传播网模型 b a c kp r o p a g a t i o n b p 径向基