（技术经济及管理专业论文）数据挖掘中关联规则算法的研究及应用.pdf

哈尔滨理工大学管理学硕上学位论文 数据挖掘中关联规则算法的研究及应用 摘要 近年来，数据挖掘己经引起了信息产业界的极大关注，这是快速增长的数据 量和曰益贫乏的信息量之间矛盾运动的必然结果，对数据挖掘技术进行系统、 深入、全面、详尽地研究是全球信息化发展的客观需要。本文对数据挖掘技术， 尤其是关联规则数据挖掘技术进行了系统、深入、全面、详尽地分析和研究， 主要包括以下一些内容： 数据挖掘技术的分析与研究。对数据挖掘技术的国内外研究现状进行了广泛 而全面地归纳、分析和研究，对数据挖掘技术的未来发展趋势和热点研究领域 进行了总结和探讨，对数据挖掘的定义及定位进行了简要的回顾，在数据挖掘 基本概念的基础上，对数据挖掘常使用的技术和研究的对象进行了详细地分类、 归纳和总结。为本文的全面展开奠定了基础。 关联规则数据挖掘技术的分析与研究。在介绍关联规则基本概念的基础上， 对关联规则的a p r i o r i 算法进行了详细地分析和研究，并就目前针对提高该算法 效率的各种优化技术也进行了详细地描述，在此基础上提出了基于筛选压缩的 a p n o a 挖掘算法。并进行了模拟实验，比较结果显示基于筛选压缩的a p r i o r i 挖掘算法极大的提高了效率。 关键词数据挖掘；关联规则；a p r i o r i 算法 哈尔滨理工大学管理学硕士学位论文 r e s e a r c ha n d a p p l i c a t i o n o fa s s o c i a t i o n r u l e s a l g o r i t h m s i nd a t a m i n i n g a b s t r a c t i nr e c e n ty e a r s ，m a n yp e o p l ei ni n f o r m a t i o ni n d u s t r ya t t a c hm o r ei m p o r t a n c et o t h ed a t am i n i n gt e c h n i q u e ，w h i c hi sa t t r i b u t e dt ot h en e c e s s a r yc o n s e q u e n c eo ft h e c o n f l i c t i n gm o v e m e n tb e t w e e nt h er a p i d - i n c r e a s i n gd a t aa n dt h ep o o ri n f o r m a t i o n d a yb yd a y s t u d y i n g t h ed a t am i n i n gt e c h n i q u e s y s t e m a t i c a l l y ，d e e p l y ，r o u n d l ya n d d e t a i l e di sa no b j e c t i v er e q u i r e m e n tf o re x c h a n g i n gi n f o r m a t i o ni nt h eg l o b a l t h i s d i s s e r t a t i o ns y s t e m a t i c a l l y ，d e e p l y ，r o u n d l ya n dd e t a i l e ds t u d i e sa n da n a l y s e st h ed a t a m i n i n gt e c h n i q u e ，e s p e c i a l l yt h eo n ef o ra s s o c i a t i o nr u l e s t h em a i nc o n t e n t sa r e 珏s t e d 舔f o l l o w s ： a b s l y s e a n dr e s e a r c ho ft h ed a t a m i n i n gt e c h n i q u e t h e d i s s e r t a t i o n s u m m a r i z e s ，a n a l y s e sa n ds t u d i e st h ec u r r e n ts t a t u so ft h ed a t am i n i n gt e c h n i q u ei n o mn a t i v ec o u n t r ya n do v e r s e a sw i d e l ya n dr o u n d l ya n dt h e ns u m m a r i z e sa n d d i s c u s s e si t s d e v e l o p m e n t a lt r e n d sa n dh o tr e s e a r c hf i e l d s n e d e f i n i e n sa n d o r i e n t a t i o no ft h ed a t am i n i n gi sr e v i e w e di nb r i e ff i r s t b a s e d0 1 1t h eb a s i cc o n c e p t s o fd a t am i n i n g ，t h i sd i s s e r t a t i o nc l a s s i f i e sa n ds u m m a r i z e st h eo b j e c t so fd a t am i n i n g a n dt h ec o m l l l o nt e c h n i q u e si nd e t a i l i ns u c c e s s i o n ，a l lo ft h ea b o v eb e c o m et h e b a s i sf o rt h i sd i s s e r t a t i o n a n a l y s ea n dr e s e a r c ho ft h ed a t am i n i n gt e c h n i q u ef o ra s s o c i a t i o nr u l e s b a s e d o nt h eb a s i cc o n c e p t so ft h ea s s o c i a t i o nr u l e s ，a n a l y s e sa n ds t u d i e st h ea p r i o r i a l g o r i t h m so fa s s o c i a t i o nr u l e si nd e t a i l a l lk i n d so fo p t i m i z e dt e c h n i q u e sw h i c h a r e d e s i g n e dt op r o m o t et h ea l g o r i t h m se f f i c i e n c ya r ea l s os t u d i e da n dd i s c u s s e di nd e t a i l h e r e b a s e do nt h eb a s i c ，t h ea p r i o ra l g o r i t h mo ff i d d l i n gc o m p r e s s i o ni sp r o p o s e d a n dh a sc a r r i e do nt h es i m u l a t i o n ，t h er e s u l td e m o n s t r a t e dt h ea p r i o ra l g o r i t h mo f r i d d l i n gc o m p r e s s i o n c a ni m p r o v et h ee f f i c i e n c yg r e a t l y k e y w o r d s d a t am i n i n g ；a s s o c i a t i o nr u l e s ；a p r i o r ia l g o r i t h m s 哈尔滨理工大学管理学硕士学位论文 1 1 研究目的和意义 第1 章绪论 ，随着计算机科学与技术的发展，计算机被应用到各行各业，计算机软件带来 的效率、效益越来越被人们重视。然而由此带来的大量数据，使人们陷入“数 据的海洋”却在慨叹“知识贫乏”；如何从大量的数据中提取并找到有用信息以 指导决策，是要追切解决的问题，在这种情况下，“数据挖掘【1 j ”一新型的数据 分析技术于1 9 9 5 年诞生了。近十年，数据挖掘的研究工作取得了很大的进展， 各种数据挖掘软件的应用极大地推动了人们掌握、处理信息的能力，并为人们 带来了很好的经济效益。 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数 据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行 更高层次的分析，以便更好地利用这些数据。目前的数据库系统无法发现数据 中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。缺乏挖掘数 据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏”的现象。面对这一 挑战，数据开采和知识发现( d m k d ) 技术应运而生，并很快成为了一种决策支持 的新手段 2 1 1 3 1 1 4 。 1 9 8 9 年8 月，在第1 1 届国际人工智能联合会议的专题研讨会上，首次提出 “在数据库中的知识发现”( z 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 9 9 1 、 1 9 9 3 、1 9 9 4 年又相继举行了k d d 专题讨论会。1 9 9 5 年，在美国计算机年会( a c m l 上，提出了数据挖掘( d m ，d a t am i n i n g ) 的概念。即通过从数据库中抽取隐含的、 未知的、具有潜在使用价值信息的过程。 由于数据库中的数据被形象地比喻为矿床，因此，数据挖掘一词很快流传 开来。由于它应用的普遍性及由此带来的高效益，新型的数据分析技术一数据 挖掘成为一个具有广阔应用前景的热门研究方向。k d d 的研究吸引了大量的各 个领域的专家和研究机构从事该领域的研究。许多公司纷纷推出了自己的数据 采掘系统。 目前见到的专门讨论数掘挖掘技术在商业系统中的应用的论著还很少。目 前主要集中在单独应用数掘挖掘对公司的数据库进行针对性的分析当中，很少 喻尔试理工人学管理学硕 学位论义 有实际数据挖掘产品应用到商业系统中的零售业，为商业系统中的零售业进行 深入的销售、客户分析，来达到量体裁衣。 本研究想结合具体的一家零售业企业多年的客户数据，采用数据挖掘的一 些方法对其销售资料进行分析，找出销售、客户的一些共同的特征，通过这种 办法深入了解销售及客户的一些不为人知的行为，并通过分析对商品销售进行 分类、分组，预测那些潜在销售信息，看哪些商品可能成为零售业的高利润贡 献度的商品，以此帮助营销人员找到正确的营销组合和策略，从而降低成本， 提高营销的成功率及利润，挖掘出潜在的关联性和规律，从而为决策的科学性 提供理论依据。 1 2 国内外研究现状及未来发展趋势 近年来，数据挖掘引起了信息产业界的极大关注。国内外各研究机构纷纷 开展了对数据挖掘技术的研究和探索工作。下面，本文将分别从国内和国外两 个方面对数据挖掘技术的研究现状进行阐述，并对数据挖掘技术的未来发展趋 势、研究方向及热点问题进行探讨。 1 2 1 国外研究现状 从第一届k d d 国际研讨会于1 9 8 9 年8 月在美国底特律举行到2 0 0 2 年7 月第八届a c m s i g k d d 知识发现和数据挖掘国际会议在加拿大艾德蒙顿举行， 有关k d d 的国际学术会议己经召开了1 4 次，规模由原来的专题讨论会发展到 国际学术大会，人数由二三十人上升到七八百入，论文收录比例从2 ：1 上升到 3 0 8 ：4 4 ，研究重点也逐渐从发现方法转向系统应用，并且注重多种发现策略和 技术的集成，以及多种学科之间的相互渗透。2 0 0 3 年8 月，第九届a c m s i g k d d 知识发现和数据挖掘国际会议在美国华盛顿举行。还有一些其它国际或地区性 数据挖掘会议，如“知识发现和数据挖掘太平洋亚洲会议”f p a k d d ) ，“数掘库 中知识发现原理与实践欧洲会议”( p k d d ) ，“数据仓库与知识发现国际会议” ( d a w a k ) 等6 川i 。 涉及数据挖掘和数摒仓库的研究结果已在许多数据库国际学术会议论文集 发表包括“a c m s i g m o d 数据管理固际会议”( s i g m o d ) ，“超人型数掘库 国际会议”( v l d b l ，“a c m s i g m o d s i g a r t 数据库原i 唯研讨会”( p o d s ) ，“数 掘1 二柞凼际会议”( i c d e ) ，“扩展数掘库技术困际会议”( e d b t ) ，“数捌j 4 ：理论 哈尔滨理工大学管理学硕士学位论文 国际会议”( i c d t ) ，“信息与知识管理国际会议”( c i 垤) ，“数据库与专家系统 应用国际会议”( d e x a ) ，“数据库系统高级应用国际会议”( d a s f a a ) 等。 数据库、人工智能、信息处理、知识工程等领域的国际学术刊物也纷纷开 辟了k d d 专题或专刊，包括( ( i e e e 知识与数据工程汇刊c i x d e ) ， a c m 数 据库系统汇干f t o d s ) ，( ( a c m 杂志( j a c m ) ，信息系统， v l d b 杂志， 数据与知识工程，智能信息系统国际杂志( j 1 1 s ) 等，其中，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 技术专刊，所 发表的5 篇论文代表了当时k d d 研究的最新成果和动态，较全面地论述了k d d 系统方法论、发现结果的评价、k d d 系统设计的逻辑方法，集中讨论了鉴于数 据库的动态性冗余、高噪声和不确定性与其它传统的机器学习、专家系统、人 工神经网络、数理统计分析系统的联系和区别，以及相应的基本对策。6 篇论文 摘要展示了k d d 在从建立分子模型到设计制造业的具体应用。 一份最近的g a r t n e r 报告中列举了在今后3 5 年内对工业将产生重要影响 的五项关键技术，其中k d d 和人工智能排名第一。同时，这份报告将并行计算 机体系结构研究和k d d 列入今后5 年内公司应该投资的1 0 个新技术领域。根 据最近g a r t n e r 的h p c 研究表明，“随着数据捕获、传输和存储技术的快速发展， 大型系统用户将更多地需要采用新技术来挖掘市场以外的价值，采用更为广阔 的并行处理系统来创建新的商业增长点。”所有这些均表明数据挖掘己成为当前 计算机科学界的一大热点。 关联规则数据挖掘首先由a g r a w a l ，i m i e h s k i 和s w a m i l 9 j 提出，著名的a p d o r i 算法由a g r a w a l 和s r i k a n t 1 0 l 提出，使用类似的剪枝方法的算法变形由m a n n i l a 、 t o i v o n e n 和v e r k a m o “l 爵究。为提高关联规则挖掘效率，随之产生了很多新的 技术，例如，数列技术被p a r k 、c h e n 和y u 1 2 】研究，事务压缩技术被a g r a w a l 和s r i k a n t 1 3 1 ，h a n 和f u f l 4 1 ，以及p a r k 、c h e n 和y u 1 2 】研究，划分技术被s a v a s e r e 、 o m i e c i n s k i 和n a v a t h e ”l 提出，选样方法被t o i v o n e n 1 6 】研究，动态项集技数被 b r i n 、m o t w a n i 、u l l m a n 和t s u r 17 】提出等。许多新的方法被提出以扩充关联规 则数据挖掘，包括a g r a w a l 和s r i k a n t 的序列模式挖掘【1 8 j ，z a k i 、l e s h 和o 酉h a r a 的对p l a nf a i l u r e 的序列模式挖掘【”】，g u h a 、r a s t o 西和s h i m 的基于约束的序列 模式挖掘1 ，m a n t i l l a 、t o i v o n e n 和v e r k a m o 的e p i s o d e s 挖掘1 “】，k o p e r s k i 和 h a n 的空间关联规则挖掘【2 2 】，o z d e n 、r a m a s w a m y 和s i l b e r s e h a t z 的有环关联规 则挖掘l ，s a v a s e r e 、o m i e c i n s k i 和n a v a t h e 的否定关联规则挖掘【2 4 j ，l u 、h a n 和f e n g 的事务问关联规则挖掘| 2 ，r a m a s w a m y 、m a h a j a n 和s i l b e r s c h a t z 的r 历购物篮分析睇，b a y a r d 的最大模式的挖掘，p a s q u i e r 、b a s t i d e 、t a o u i l 和l a k h a l 啥尔滨理工大学管理学硕士学位论文 的频繁闭合项集的挖掘( 其有效挖掘算法由p e i 、h a n 和m a o 提出) ，h a n 、p e i 和y i n 提出的挖掘频繁项而不产生侯选的方法，f e l d m a n 和h i r s h 的文本数据库 中的关联规则挖掘等。另外，多层关联规则挖掘被h a n 和h u ，s k i k a n t 和a g r a w a l 研究，量化关联规则的非基于栅格的使用部分完全性度量的挖掘技术由s k i k a n t 和a g r a w a l 提出，强关联规则的兴趣度问题由c h e n 、h a n 和y u ，b r i n 、m o t w a n i 和s i l v e r s t e i n ，以及a g g a r w a l 和y u 研究，推广关联到相关的有效方法由b r i n 、 m o t w a n i 和s i l v e r s t e i n 给出，基于约束的关联规则挖掘被n g 、l a k s h m a n a n 、h a n 和p a n g ，l a k s h m a n a n 、n g 、h a n 和p a n g ，以及p e i 和h a n 研究，并行和分布关 联规则挖掘被p a r k 、c h e n 和y u ，a g r a w a l 和s h a f c r ，以及c h e n n g 、h a n 、n g 、 a f u 和y f u 研究等。 分类规则数据挖掘最常见的技术是判定树归纳，其算法包括c 4 5 算法、1 0 3 算法、i d 4 算法、i d s 算法、q u e s t 算法、p u b l i c 算法、c u m d 算法等；i n f e r u i l e 算法由非决定的数据学习构造判定树：k a t e 算法由复杂的结构化数据学习构造 判定树；s l i o 算法、s p r i n t 算法、“雨林”算法、b o a t 算法等强调构造可伸 缩性的判定树；判定树剪枝算法包括代价复杂性剪枝、减少错误剪枝、悲观估计 剪枝等；规则推导算法包括c n 2 算法、a q l 5 算法、i t r u l e 算法、f o i l 算法、s w a p 1 算法等。分类规则数据挖掘的其它方法还有贝叶斯分类法、向后传播算法、神 经瞬络方法、机器学习方法、关联分类法、c a e p 分类法、j e p 分类法、最临近 方法、遗传算法、粗糙集方法、模糊逻辑方法、回归技术等1 2 7 1 2 s 1 1 凹1 1 3 0 l 。 聚类规则数据挖掘的算法也有很多。关于划分的方法有k 平均算法、k - 中 心点算法、k - 模( 聚类分类数据) 算法、k 原型( 聚类混合数据) 算法、e m ( e x p e c t a t i o n m a x i m i z a t i o n ，最大期望濞法、c l a r a n s 算法等。凝聚的层次聚类f 如a g n e s ) 和分裂的层次聚类f 如d i a n a ) i 由k a n f m a n 和r o u s s e e u w 提出。d b s c a n 是一个 基于密度的聚类方法；o p t i c s 是一个基于密度的聚类排序方法；d e n c l u e 是一 个基于一组密度分布函数的算法。s t i n g 是一个基于网格的多分辨率方法； w a v e c l u s t e r 是一个通过小波变换来转换原始特征空问的多分辨率聚类方 法；c u q u e 是一个综合了基于密度和基于网格方法，用于聚类高维数据的聚类 算法。另外，还有基于模型的聚类方法、概念聚类方法、统计聚类方法、神经 网络方法、模糊聚类方法等。 随着数据挖掘理论研究的逐步成熟，数据挖掘产品也应运而生。目前，世 界上比较有影响的典型数据挖掘产品有：s a s 公司的e n t e r p r i s em i n e r 、i b m 公司 的i n t e l l i g e n tm i n e r 、s g l ( s i l i c o ng r a p h i c sl n c 1 公司的m i n e s e t 、加拿大 s i m o n f r a s e r 大学的d b m i n e r 、s p s s 公司的c l e m e n t i n e 、s y b a s e 公司的 哈尔滨理工大学管理学硕士学位论文 w a r e h o u s es t u d i o 、r u l e q u e s tr e s e a r c h 公司的s e e s 、i b m 公司a l m a d e n 研究中 心的q u e s t ，还有c o v e r s t o r y 、e x p l o a r 、k n o w l e 咄ed i s c o v e r yw o r k b e n c h 等。还 可以访问h t t p ：f w w w d a t a m i n i n g l a b t o m ，该网站提供了许多数据挖掘系统和工具 的性能测试报告。 1 2 2 国内研究现状 我国的数据挖掘研究开始于9 0 年代中期，到9 0 年代中后期，初步形成了知 识发现和数据挖掘的的基本框架。自9 0 年代中期一批研究成果r 学术论文) 逐渐发 表在计算机学报、计算机研究与发展、软件学报、人工智能与模式识 别等刊物上研究重点也正在从发现方法转向系统应用，并且注重多种发现策 略和技术的集成，以及多种学科之间的相互渗透。但是基本上还是以学术研究 为主，实际应用上处于起步阶段。与国外相比，国内对d m k d 的研究稍晚，没 有形成整体力量【3 l 】【3 2 】【3 3 h 3 4 1 ，进行的大多数研究项目是由政府资助进行的，如国 家自然科学基金、8 6 3 计划、”九五”计划等。1 9 9 3 年国家自然科学基金首次支持 该领域的研究项目。国内从事数据挖掘研究的人员主要在大学，也有部分在研 究所或公司，所涉及的研究领域很多，一般集中于学习算法的研究、数据挖掘的 实际应用以及有关数据挖掘理论方面的研究。如清华大学、中科院计算技术研 究所、空军第三研究所、海军装备论证中心等。其中，华中理工大学、复旦大 学、浙江大学、中国科技大学、中科院数学研究所、吉林大学等单位开展了对 关联规则开采算法的优化和改造。 1 2 3 未来发展趋势 当前，数据挖掘和知识发现的研究方兴未艾，其研究与开发的总体水平相 当于数据库技术在7 0 年代所处的地位，迫切需要类似于关系模式、d b m s 系统和 s o l 查询语言等理论和方法的指导。鉴于数据、数据挖掘任务和数据挖掘方法的 多样性，给数据挖掘技术提出了许多挑战性的课题，这些课题包括： 1 数据挖掘应用的探索： 2 可伸缩的方法： 3 。交互式发现： 4 与数据库系统、数据仓库系统和w e b 数据库系统的集成： 5 数据挖掘语言的标准化： 6 可视化数据挖掘 哈尔滨理工大学管理学硕上学位论文 7 复杂数据类型挖掘： 8 w e b 挖掘，隐私保护和信息安全等。 1 3 本文研究内容 1 3 1 数据挖掘技术的分析与研究 对数据挖掘技术的产生进行了简要的回顾，在提出数据挖掘基本概念的基 础上，对数据挖掘的对象、可发现的模式和常使用的技术进行了详细地分类、 归纳和总结。对数据挖掘技术的国内外研究现状进行了广泛而全面地归纳、分 析和研究，对数据挖掘技术的未来发展趋势和热点研究领域进行了客观地总结 和探讨，为本文的全面展开作好铺垫。 1 3 2 关联规则数据挖掘技术的分析与研究 在提出关联规则基本概念的基础上，对关联规则的种类进行了全面地分类、 归纳和总结，对关联规则的典型挖掘算法及其基本思想进行了详细地归纳、分 析和研究，对各算法之间的差别进行了客观地比较，针对提高算法效率的各种 优化技术也在这里被进行了详细地研究和讨论，同时客观地分析了它们的优缺 点和利与弊。 第一章指出论文的研究目的和意义，对数据挖掘的国内外研究现状及未来 发展趋势进行了综述。 第二章从数据挖掘的的定义和定位出发，介绍了数据挖掘的特点，并就其 相关的应用进行了比较：进而总结了数据挖掘的功能，然后对数据挖掘的分类 进行了比较分析，在此基础上介绍了针对数据挖掘的不同的目的应对数据挖掘 的结果采用不同的评估方法。 第三章从关联的规则挖掘的的基本概念出发，详细地介绍了关联规则相关 的定义，进而分析了关联规则的挖掘步骤，然后对关联规则挖掘应注意的问题 进行了探讨，在此基础上对关联规则按不同的分类标准进行了分类，最后分析、 比较、总结了关联规则的主要研究方向和典型算法。 第四章先对a p r i o r i 算法及性质进行了解释，并详细介绍了a p r i o r i 算法的 过程及a p r i o r i 算法存在的性能瓶颈问题；在此基础上提出的基于筛选压缩的 a p r i o r i 挖掘算法，提高了运行速度、减少运行时问和空问耗费，并应用改进的 哈尔演理r 人学管理学硕士学位论文 算法进行了模拟数据比较分析。 结论部分对本论文进行总结，并给出了一些可以进行后续研究的建议。 哈力i 滨理t 人学管理学硕士学位硷文 第2 章数据挖掘 计算机网络与数据库技术的发展和广泛应用，使得信息在企业发展中的重 要作用越来越得到人们的认同。人们利用信息技术生产和搜集数据的能力也大 幅度提高，无数个数据库被用于商业管理、政府办公、科学研究和工程开发等， 这一势头仍将持续发展下去。在这些数据背后隐藏着极为重要的商业知识，但 是这些商业知识是隐含的、事先未知的。于是，如何才能不被信息的汪洋大海 所淹没，从中及时发现有用的知识，提高信息利用率就显得尤为重要。在这样 地背景下，新的数据处理技术数据挖掘( d a t am i n i n g ) 技术便应运而生了。 2 1 数据挖掘定义和定位 2 1 1 定义 数据挖掘，英文是d a t am i n i n g ，中文又译作数据采掘，还有很多和这一术 语相近似的术语，如从数据库中发现知识( k d d l 、数据分析、数据融合( d a t a f u s i o n ) 以及决策支持等。一种比较公认的定义是u s a m amf a y y a d 、g p i a t e t s k y 、 s h a p i r o 等1 3 5 j 1 3 6 1 【3 7 1 人提出的：数据挖掘，就是从大型数据库的数据中提取人们感 兴趣的知识，这些知识是隐含的、事先未知的潜在有用的信息，提取的知识表 示为概念( c o n c e p t s ) 、模式( p a t t e r n s ) 、规贝1 ( r u l e s ) 、规律( r e g u l a r i t i e s ) 等形式，这 种定义把数据挖掘的对象定义为数据库，而更广泛的说法是【”1 ：数据挖掘意味 着在一些事实或观察数据的集合中寻找模式的决策支持过程，数据挖掘的对象 不仅仅是数据库，也可以是文件系统，或其它任何组织在一起的数据集合，例 如w w w 信息资源。最新的对象是数据仓库。数据挖掘如图2 1 所示 h2 1 数据挖捌 f i 9 21d a t am i n i n g 哈尔滨理t 大学管理学坝1 学位论文 2 1 2 定位 从数据挖掘的定义可以看出，作为一个学术领域，数据挖掘和数据库知识 发现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 ) 具有很大的重合度，大部分学者认为 数据挖掘和知识发现是等价的概念，人工智能( a i ) 领域习惯称k d d ，而数据库 领域习惯称数据挖掘，也有学者把k d d 看作发现知识的完整过程，而数据挖 掘只是这个过程中的一个部分1 3 9 】。我们倾向于前一种观点，认为数据挖掘从理 论和技术上继承了知识发现领域的成果，同时又有着独特的内涵。数据挖掘更 着眼于设计高效的算法以达到从巨量数据中发现知识的目的。数据挖掘充分利 用了机器学习、人工智能、模糊逻辑、人工神经网络的理论和方法。 与数据挖掘关系密切的研究包括归纳学习( i n d u c t i v el e a r n i n g ) 、机器学习 ( m a c h i n el e a r n j n 曲、统计( s t a t i s t i c s ) 分析。特别是机器学习，被认为和数据挖掘 的关系最密切。二者的主要区别在于：数据挖掘的任务是发现可以理解的知识， 而机器学习关心的是提高系统的性能，因此，训练神经网络来控制一根倒立棒 是一种机器学习过程，但不是数据挖掘：数据挖掘的对象是大型的数据库，一 般来说机器学习处理的数据集要小得多，因此效率问题对数据挖掘是至关重要 的。 再来看看数据挖掘在决策支持( d e c i s i o n s u p p o r t ) 中处于何种地位。 k p a r s a y e 把决策支持从应用层次分成4 个子空间i 舯】：数据空 b q ( d a t as p a c e ) 、 聚合空间( a g g r e g a t i o ns p a c e ) 、影响空间( i n f l u e n c es p a c e ) 和变化空f 司( v a r i a t i o n s p a c e ) 。如图2 2 所示。 幽2 2 献策支持 f i g2 - 2d e c i s i o ns u p p o r t t ) 一 哈尔滨删t 大学管理学硕士学位论文 数据空间处理基于关键字( k e v b a s e d ) 的决策查询，比如回答“产品a 的 价格是多少? ”这类浏览式的查询数据空间中最典型的是联机事务处理( o l t p ) 系统。对数据空间中数据元素进行聚合运算f 如s u ma v e r a g e ，m a x ，m i n 等) 形 成的空间就是聚合空间。目前，常用的提法有联机分析处理( o l ) 和多维空问 ( m u l t i d i m e n s i o n a ls p a c e ) 聚合空问处理诸如“某一商场在某月某种商品的销售 额是多少? ”这类关系到聚合运算的决策查询。 以上两种空间都是处理数据值的计算，而影响空间处理逻辑性质的决策支 持，比如回答“是什么因素影响在纽约的销售情况? ”这样的问题这个空间 能够提供比其它空间丰富得多的有用信息。这些信息就是通过数据挖掘而得到 的。 变化空间负责回答某种变化的过程和速率问题，例如“在过去3 个月中的 销售额增长是怎样变化的? ” 在以上4 个空间中，数据挖掘处于影响空间中从中我们可以看到数据挖 掘在整个决策支持空间中所处的重要位置如果一个企业的领导不仅仅满足于 一些统计报表，那么数据挖掘就是必要的。它提供非常主要的决策信息，而这 些信息对于决策者可能是完全崭新的。在当今高度复杂的社会，信息已成为世 上最有价值的商品，而数据挖掘所能提供给我们的信息比其它财产更宝贵，更 有用。 2 2 数据挖掘的特点 数据挖掘的对象数据，既可以是集中在主机上的数据库，也可以是分 布存放在i n t e m e t 网上的各种数据，这些数据可能有千兆字节或更多，数据挖 掘一般需要一些领域知识，最常见的是概念层次的知识。 由于数据挖掘使用的数据直接来自数据库或数据仓库，数据的组织形式， 数据规模都具有依赖数据库的特点，由于数据挖掘处理的数据量非常巨大，数 据的完整性，致性和正确性部难以保证。所以，数据挖掘算法的效率，有效 性和可扩充性都显得至关重要，然而充分利用现代数据库技术优势也是提高挖 掘的算法效率的有效途径。 1 数据挖掘与传统的数据库查询系统相比较传统的数据库查询一般都具 有严格的查询表达式，可以_ e f js o l 语，1 j 描述。而数据挖掘则不一定具有严格的 要求，常常表现出即时、随机的特t j 。在咖要求也不确定。整个挖掘过程山无 法仅用s q l 语言就能完黎表达爻m 、卜数扔：于窆掘常常用种类s 0 l 诺二j 彩 哈尔滨理工大学管理学硕j 一学位沦文 描述表达。 传统的数据库查询一般生成严格的结果集，但数据挖掘可能并不生成严格 的结果集，挖掘过程往往基于统计规律，产生规则并不要求所有的数据项总是 成立，而是只要达到一定的事先给定的阈值就可以了。 通常情况下，数据库查询只对数据库的原始字段进行；而数据挖掘则可能 在数据库的不同层次上挖掘知识规则。 2 数据挖掘( d m ) 与o l a p 的比较o l a p ( o nl i n ea n a l y t i c a lp r o c e s s i n g ) 也 是前几年发展起来的一个热门技术。由多维数据库( m u l t id i m e n s i o n a ld a t a b a s e ) 和数据立方体( d a i sc u b e ) 支持。每个维是某一个属性满足不同条件的值。它是 现有的数据库管理系统的检索，查询，和报表功能和多维分析，统计分析方法 的综合，一般是针对预选设计的复杂查询，是静态的，而且它只能用统计的方 法分析数据。o l a p 是一种验证型的工具。d m 是一种挖掘型的工具，它能自 动地发现隐藏在数据中的模式，它是现有人工智能，统计学等成熟技术在一定 的数据领域的应用。 如果从数据分析的深度和角度来看，o i a p 位于较浅的层次，而d m 所处 的位置则较深。如果按着e e c o d d 的数据分析模型来区分，那么应该说o l a p 实现了解释模型和思考模型，而d m 则实现了公式模型。 从决策支持的需要而言，o l a p 与数据挖掘可以起到相辅相成的作用。广 义地，可以把o l a p 视为数据挖掘的一种方法。 3 数据挖掘同知识发现、机器学习的比较在参考文献【4 1 】【4 2 】中，知识发现 是这样定义的：知识发现是识别出存在于数据库中有效的，新颖的，具有潜在 价值的乃至最终可理解的模式的非平凡过程。可见，知识发现和数据挖掘这两 个术语在内涵上大致相同。对这两个术语更严格的区分是在“知识发现9 6 国 际会议”上：f a r r a d ，p i a t e t s k y s h a p i r o 和s m y t h 指出：知识发现是从数据库中 发现知识的全部过程，而数据挖掘则是这些全部过程的一个特定的、关键的步 骤。 数据挖掘和机器学习都是从数掘中提取知识，其主要区别在于：机器学习 主要针对特定模式的数据进行学习：数据挖掘则是从实际的大量数据中抽取知 以，这些数掘源通常是一些大型数据库。 n a 尔滨理j 大学管理学硕士学位论文 2 - 3 数据挖掘功能和分类 2 3 1 功能 利用数据挖掘技术可以海量数据中获得决策所需的多种知 ： 。在许多情况 下，用户并不知道数据存在哪些有价值的信息知识，因此，对于一个数据挖掘 系统而言，它应该能够同时搜索发现多种模式的知识，以满足用户的期望和实 际需要。此外，数据挖掘系统还应该能够挖掘多种层次( 抽象水平) 的模式知识。 数据挖掘系统还应允许用户来指导挖掘搜索有价值的模式知识。 特别要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面向 特定数据库的简单检索查询调用，而且要对这些数据进行微观、中观乃至宏观 的统计分析、综合和推理，以指导实际问题的求解，企图发现事件间的相互关 联，甚至利用已有的数据对未来的活动进行预测。例如美国著名国家篮球队 n b a 的教练，利用某公司提供的数据挖掘技术，临场决定替换队员，一度在数 据库界被传为佳话。 这样一来，就把人们对数据的应用，从低层次的末端查询操作，提高到为 各级经营决策者提供决策支持。这种需求驱动力，比数据库查询更为强大。同 时需要指出的是，这里所说的知识发现，不是要求发现放之四海而皆准的真理， 所有发现的知识都是相对的，是有特定前提和约束条件、面向特定领域的，同 时还要能够易于被用户理解。 2 1 3 2 分类 常用的数据挖掘技术可以分成统汁分析类、知识发现类、和其他类型的数 据挖掘技术三大类。 1 统计分析类统计是数据搜集和描述数学的一个分支。统计推断分析一 般借助统计数学模型完成，他用已有信息推断未知信息的工作过程，如用过去 的资料来推测未- 柬，利用局部资料推断总体等等。统计分析工具可以用于一系 列的商业活动，例如使用统计j ：具进行数据分析，以寻求最佳机会，增加市场 份额和利润等。统计类数据挖掘技术已经成为目前最成熟的数掘挖掘技术。 其中有： 数据的聚集与度量技术咳技术需要用到数据库中常用的聚集函数。例如： c o u n l 0 ，s u n ( 1 ，a v 9 0 ，m a x 0 等。 哈尔滨理工大学管理学硕士学位论文 柱状图数据挖掘技术该技术能直观的显示该数据库中的一些重要信息。 线性回归数据挖掘技术回归是研究自变量与因变量之间关系的分析方法。 其目的在于根据已知自变量来估计和预测因变量的总平均值。例如：企业的盈 利与客户购买能力和销售成本有着依存关系。通过对这一依存关系的分析，在 己知有关客户数、客户购买能力和销售成本的条件下，可以预测企业的平均盈 利水平。 非线性回归数据挖掘技术当判定变量间的关系大致是一条直线反映其变 动关系时，可以拟合一条直线反映其变动关系。然而在很多情况下，变量间的 关系呈曲线形式，即非线性的，这时就拟合一条曲线来反映变量间的关系。非 线性回归有多种模型：双曲线模型、二次曲线模型、对数模型、三角函数模型 等。 聚类数据挖掘技术是将数据对象分组为多个类或簇的数据挖掘技术。 最近邻数据挖掘技术。用该方法进行预测的基本概念是相互之问“接近” 的对象具有相似的预测值。如果知道其中一个对象的预测值后，可以预测其最 近的邻居对象。例如：在预测某些人的收入时，常要了解他目前处于什么阶层 或获得什么学位。因为人们的收入高低往往与其所相处的人群、与他的文化程 度有关，因此需要检测与其最相邻的人群。 2 知识发现类知识发现是用一种间接的方式从数据中抽取信息的一种技 术，而这些信息是隐含的、未知的，并且具有潜在应用价值。知识发现可以堪 称一种有价值信息的搜寻过程，他不必预先假设或提出问题，但仍能找到那些 非预期的令人关注的信息；这些信息表示数据元素之间的关系和模式，它也能 通过完整的、全面的信息发现和数据分析，找到有价值的商业规则。 其中可分为： 关联规则型知识挖掘技术是数据挖掘的一种主要形式，而且是无教师学习 中最普遍的知识发现形式。它也是与大多数人想象的数据挖掘过程最为相似的 一种数据挖掘形式，即在大型数据仓库中发掘出一些原先不知道，或者不能明 确表达出来的有关数据库的信息。 神经网络型知识挖掘技术它主要由“神经元”的互联，或按层组织的节点 构成。通常，神经网络模型由三个层次组成：输入层，中间层和输出层。在每 个神经元求得输入值后，再汇总汁算总输入值：由过滤机制比较输入值，确定 网络的输出值。 遗传算法型知识挖掘技术遗传算法是模拟生物进化过程的计算模型，是自 然遗传学与计算机科学相互结合渗透的计算方法。遗传分析应用搜索技术先 疗匀；贾里1 入学百理学坝l 学位论卫 找出两个合适的父样本，通过“交叉变异”等带有生物遗传特点的操作产生 下一代样本，对子样本反复“交叉变异”操作直到子样本收敛为止，再找另 外两个合适的父样本重复上述过程，就能得到下一代的样本集。由此得到当酊 样本集较为可能的发展方向。 粗糙集型知识挖掘技术粗糙集是波兰学者p a w l a k z 在1 9 8 2 年提出的，这 是一种研究不确定性问题的数学l ：具。它作为集合论的扩展，主要用于研究不 完全和不完整信息描述的数据挖掘技术。它能够在缺少关于数据先验知识的情 况下，以考察数据的分类能力为基础，解决模糊或不确定数据的分析和处理。 3 其他数据挖掘技术除以上陈述的数据挖掘技术外，近年来，随着各种数 据处理工具、先进的数据库技术与因特网技术的迅速发展，还出现了一些其他 数据挖掘技术。如：文本挖掘技术、w e b 挖掘技术、分类分析技术、地理信息 系统与空间数据挖掘技术以及分布式数据挖掘技术等。 2 4 数据挖掘的过程 数据挖掘的实施，大体可分为以下三步： 1 数据准备( d a t ap r e p a r a t i o n ) 本阶段又可分为两步；数据集成，数据的选 择和预分析。 集成( i n t e g r a t i o