（交通信息工程及控制专业论文）数据库中的关联规则及挖掘算法研究.pdf

第i i 页 的算法 西南交通大学研究生博士论文 。另外， 对于算法中的不足， 提出一个分而治之的解决方法。并说明 给出的算法是可并行化的，同时给出一个并行处理的框架过程。 而且， 通过 甲 的给定， 使得用户在一定程度上能参与到挖掘过程中， 提高了挖掘的效率。 4 . 针对属性集的变化， 提出一种增量式更新对象集的上、 、习护/ 实现了多个属性同时增加与删除时的增量式更新。 在此基础上， 下近似方法， 提出一种从 数据中挖掘分类规则的伪增量式算法，能够更有效地支持知识更新的需要。 关键词数据库;数据挖掘;关联规则;粗糙集;兴趣度量 西南交通大学博士研究生学位论文第 i i i 页 ab s t r a c t d a t a mi n i n g c u r r e n t l y i s t h e r e s e a r c h f r o n t i e r w i t h i n t h e i n f o r ma t i o n s c i e n c e f i e l d . t h e r e l a t e d r e s e a r c h e s a n d a p p l i c a t i o n s h a v e g r e a t l y i m p r o v e d t h e a b i l i t y f o r d e c i s i o n s u p p o rt i n g . a s s o c i a t i o n r u l e , w h i c h h a s b r o a d a p p l i c a t i o n s , i s o n e o f i m p o rt a n t r e s e a r c h a r e a s i n d a t a m i n i n g . a t p r e s e n t t h e r e s e a r c h o n a s s o c i a t i o n r u l e a n d m i n i n g a l g o r i t h m a r e s t i l l f a r f r o m p e r f e c t . t h a t c a n b e s e e n i n s e v e r a l a s p e c t s a s f o l l o w s : r e s e a r c h o n t h e t h e o r y o f a s s o c i a t i o n rul e s i g n i f i c a n t l y l a g s b e h i n d t h e d e v e l o p m e n t o f i t s a p p l i c a t i o n s ; t h e g e n e r a t i o n o f j i l l i o n r u l e s i n t h e m i n i n g p r o c e s s m a k e s p e o p l e h a r d t o u n d e r s t a n d a n d u s e t h e m e ff e c t i v e l y ; t h a t a l l i t e m s e t s a r e t r e a t e d c o o r d i n a t e l y a n d u s i n g o n e a n d o n l y m i n i m u m s u p p o rt a s a m e a s u r e s t a n d a r d a r e n o t a c c o r d w i t h t h e n e e d o f p r a c t i c e ; t h e u s e r s a r e h a r d t o a t t a c h t h e m t o t h e m i n i n g p r o c e s s ; t h e p r o b l e m o f h o w t o u s e t h e e x i s t i n g k n o w l e d g e t o u p d a t e t h e k n o w l e d g e i s n o t s e t t l e d s a t i s f a c t o r i l y . i n t h i s d i s s e rt a t i o n , m u c h e ff o rt h a s b e e n m a d e t o s t u d y t h e a b o v e p r o b l e ms . t h e ma i n wo r k i s a s f o l l o ws : 1 . b a s e d o n t h e s t u d y a n d s u m m a r i z a t i o n o f t h e p r o b l e m o f a s s o c i a t i o n rul e m i n i n g , t h e e x i s t i n g mi n i n g a l g o r i t h m s o f a s s o c i a t i o n r u l e w e r e s o r t e d a n d s o m e t y p i c a l a l g o r i t h ms w e r e a n a l y z e d a n d d i s c u s s e d t h o r o u g h l y . t h e n , t h e r e l a t i o n b e t w e e n t h e i t e m s e t i n t h e p r o b l e m o f a s s o c i a t i o n r u l e m i n i n g a n d l a t t i c e , f i x e d p o i n t , c o n c e p t l a t t i c e i n m a t h e m a t i c s w a s d i s c u s s e d . t h e r e s u l t s t h a t t h e s e t o f a l l c l o s e d i t e m s e t i s a c o m p l e t e l a t t i c e w e r e p r o v e d . t h a t a c l o s e d i t e m s e t i s n o t o n l y a c o n n o t a t i o n o f a c o n c e p t i n a s s o c i a t i o n r e l a t i o n b u t a l s o a f i x e d p o i n t o f g a l o i s c l o s e d o p e r a t o r w a s p o i n t e d o u t . a t t h e s a m e t i m e , t h e r e s u l t t h a t t h e s e t o f a l l f i x e d p o i n t s o f g a l o i s c l o s e d o p e r a t o r i s t h e s e t o f a l l c l o s e d i t e m s e t i n a t r a n s a c t i o n d a t a b a s e w a s p r o v e d . t h e s e r e s u l t s p r o v i d e s o m e i m p o r t a n t f o u n d a t i o n f o r r e s e a r c h o n t h e t h e o ry o f a s s o c i a t i o n r u l e . 2 . t h e c o n c e p t s o f u p p e r , l o w e r c l o s e d i t e m s e t a n d g e n e r a l i z e d b a s e o f a s s o c i a t i o n r u l e w e r e p r o p o s e d a n d s o m e p r o p e r t i e s w e r e o b t a i n e d . b y u s e o f t h e p r o p e rt i e s , t h a t a g e n e r a l i z e d b a s e o f a s s o c i a t i o n r u l e c o n c l u d e s a l l t h e i n f o r m a t i o n o f a l l t h e a s s o c i a t i o n rul e s i n d a t a b a s e w a s p o i n t e d o u t . a l s o , t h e m e t h o d o f h o w t o o b t a i n a g e n e r a l i z e d b a s e o f a s s o c i a t i o n r u l e f r o m t h e s e t o f a l l t h e a s s o c i a t i o n r u l e s w a s g i v e n . s i m u l t a n e o u s l y , a n a l g o r i t h m f o r m i n i n g i t d i r e c t l y f r o m d a t a b a s e w a s p r o p o s e d , w h i c h w o u l d e n h a n c e t h e e f f i c i e n c y o f g e n e r a t i o n o f r u l e s . mo r e o v e r , t h e d i s a d v a n t a g e s o f i t w e r e s t u d i e d a n d a n a l g o r i t h m f o r m i n i n g a l l t h e l o w e r c l o s e d i t e m s e t o f a f r e q u e n t c l o s e d i t e m s e t w a s p r e s e n t e d . i n a d d i t i o n , t h e i n t e r e s t i n g n e s s m e a s u r e s c o m m o n l y u s e d i n t h e p r o b l e m o f a s s o c i a t i o n r u l e m i n i n g w e r e s t u d i e d a n d s o m e i m p o r t a n t c o n c l u s i o n s w e r e d r a w n . a t t h e s a m e t i m e . a n e w i n t e r e s t i n g n e s s me a s u r e w a s g i v e n , w h i c h h a s g o o d p r o p e rt i e s a n d c a n b e u s e d t o o r d e r t h e r u l e s a n d o b t a i n t h e i n t e r e s t i n g r u l e s . t h e s e r e s u l t s , t o a c e rt a i n e x t e n t , c a n s o l v e t h e p r o b l e m o f t h e g e n e r a t i o n o f j i l l i o n r u l e s i n m i n i n g p r o c e s s . 3 . b y i n t r o d u c i n g t h e f u n c t i o n o f i n t e r e s t d e g r e e o f i t e m s e t , cp , a n e w k i n d o f t h e g e n e r a l i z e d p r o b l e m o f a s s o c i a t i o n r u l e m i n i n g , (p - a s s o c i a t i o n r u l e m i n i n g , w a s p r o p o s e d a n d t h e d i s a d v a n t a g e s t h a t a l l i t e m s e t s a r e t r e a t e d c o o r d i n a t e l y a n d u s i n g o n e a n d o n l y m i n i m u m s u p p o rt a s a m e a s u r e s t a n d a r d i n t h e c l a s s i c a l p r o b l e m a s s o c i a t i o n r u l e w e r e m a d e u p . b a s e d o n f p - t r e e , a c o m m o n l y u s e d a l g o r i t h m f o r m i n i n g ( p - f r e q u e n t c l o s e d i t e m s e t w a s p r e s e n t e d . f o r a k i n d o f s p e c i a l (p . a n i m p r o v e d a l g o r i t h m w a s g i v e n . mo r e o v e r , a d i v i d e a n d c o n q u e r m e t h o d f o r s o l v i n g t h e s h o r t a g e s o f t h e a l g o r i t h m s w a s p r o p o s e d . t h a t t h e g i v e n a l g o r i t h m s c a n b e p a r a l l e l e d w e r e s h o w n a n d a f r a m e f o r p a r a l l e l p r o c e s s i n g w a s p r e s e n t e d . f u rt h e r m o r e , f r o m t h e d e f i n i t i o n o f c p , t h e u s e r c a n a t t a c h h i m t o t h e m i n i n g p r o c e s s t o a c e r t a i n e x t e n t a n d t h e m i n i n g e f f i c i e n c y i s e n h a n c e d . 4 . a i m i n g a t t h e c h a n g i n g a t t r i b u t e s e t , t h e m e t h o d f o r i n c r e m e n t a l l y u p d a t i n g t h e u p p e r , lo w e r a p p r o x i m a t i o n o f a n o b j e c t s e t w a s p r e s e n t e d , w h i c h r e a l i z e t h e i n c r e m e n t a l l y u p d a t i n g w h e n m u l t i - a t t r i b u t e s w e r e a d d o r d e l e t e d s i m u l t a n e o u s l y . b a s e d o n t h a t , a q u a s i - i n c r e m e n t a l a l g o r i t h m f o r l e a r n i n g c l a s s i f i c a t i o n r u l e s f r o m d a t a w a s p r o p o s e d a n d i t c a n m e e t t h e n e e d o f k n o w l e d g e u p d a t i n g e f f e c t i v e l y . 厂 k e y wo r d sd a t a b a s e , d a t a mi n i n g , a s s o c i a t i o n r u l e , r o u g h s e t , i n t e r e s t i n g n e s s d e g r e e 西南交通大学博士研究生学位论文第 1 页 第 1 章 绪论 1 . 1数据挖掘概述 近年来，随着信息产业的快速发展，人们积累的数据越来越多。激增 的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分 析， 以便更好地利用这些数据。 传统的数据管理方法可以高效地实现数据的 录入、查询、统计等功能， 但无法发现数据中存在的关系和规则，无法根据 现有的数据预测未来的发展趋势。 缺乏挖掘数据背后隐藏的知识的手段， 导 致了“ 数据爆炸但知识贫乏”的现象。 于是， 人们不得不去寻找一种新的方 法和技术， 使之能够智能地、自 动地将这些数据转化处理为有用的信息和知 识。 数据挖掘在这种背景下应运而生了。目 前， 它己成为计算机科学研究中 的一个十分活跃的前沿领域， 并在市场分析、金融投资、医疗卫生、 环境保 护、 产品制造和科学研究等许多领域获得了广泛的成功应用， 取得了十分可 观的社会效益和经济效益。 同时， 数据挖掘的研究和应用对于人工智能这门 前沿学科的发展注入了新的活力， 有力地促进了计算机科学与技术朝着纵深 方向顺利发展。 1 . 1 . 1数据挖掘的定义 数据挖掘就是从大量数据中发现潜在规律、提取有用知识的方法和技 术。 因 为 与 数 据库密切相关， 又 称为 数据库知识发 现( k n o w l e d g e d i s c o v e r y i n d a t a b a s e s , k d d ) 。 数据挖掘不但能够学习己有的知识， 而且能够发现未 知的知识; 得到的知识是“ 显式” 的， 既能为人所理解， 又便于存储和应用， 因此一出现就得到广泛的重视。 从一开始到现在， 人们给数据挖掘下过很多定义。 随着数据挖掘研究的 不断深入， 人们对数据挖掘的理解越来越全面， 数据挖掘的定义也不断得到 修改， 其中 得到公认的是 下面的 这个定 义u l , 数据挖掘指的是从大量数据中提取出有效的、 新颖的、 潜在有用的，以 及最终可理解的模式的高级过程。 其中: 数据是指一个有关事实f的集合( 如员工档案数据库中有关员工 基本情况的各条记录) ，它是用来描述事物有关方面的信息，是我们进一步 发现知识的原材料。 第2页 西南交通大学研究生博士论文 薪 颖 指 的 是 经 过 数 据 挖 掘 提 取 出 的 模 式 必 须 是 新 颖 的不少对系统来说 应该如此。 模式是否新颖可以 通过两个途径来衡量: 其一是得到的数据， 通 过对比当前得到的数据和以前的数据或期望得到的数据之间的比较来判断 该模式的新颖程度; 其二是通过其内部所包含的知识， 通过对比发现的模式 与已有的模式的关系来判断。 通常我们可以用一个函数来表示模式的新颖程 度n ( e , f ) ,该函数的返回值是逻辑值或是对模式 e的新颖程度的一个判断 数值。 潜在有用指的是提取出的模式应该是有意义的， 这可以通过某些函数的 值来衡量。用u 表示模式e的有用程度，u = u ( e . f ) o 可被人理解指的是数据库中隐含的模式通过数据挖掘过程要以容易被 人理解的形式表现出来， 帮助人们更好地了解数据库中所包含的信息。 数据 挖掘不同于以往知识获取技术的一个特点是发现的知识是人们( 至少是领域 专家) 可以理解的，如“ i f . . . t h e n . . . ” 的形式，因此挖掘过程也是一个人机交 互、 螺旋上 升的过程。而以往的方法，如人工神经网络，不论是知识发现过 程还是知识应用过程，内部都是 一 个近 “ 黑箱”过程。 模式:对于集合f中的数据，可以用语言l来描述其中数据的特性。 表达式e r l , e所描述的数抓是集合f的一 个护 集凡。只有当表达式e比 列举所有凡中元素的描述方法史为简单时， 我们刁可称之为模式。 如: “ 如 果1戊 绩在8 5 - 9 5 之间，则成绩优秀”可称为个模式，而 “ 如果成绩为8 5 . 8 6 . 8 7 . 8 8 . 8 9 , 9 0 , 9 1 . 9 2 , 9 3 . 9 4 或9 5 ，则成绩优秀”就不能称之为 一 个模式。 高级过程是指一个多步骤的处理过程， 多步骤之间相互影响、 反复调整， 形成 一 种螺旋式上升过程。 数据挖掘是对数据进行更深层处理的过程， 而不 是仅仅对数据进行加减求和等简单运算或查询， 因此说它是一个高级的过程 1 2 - 6 1 1 . 1 .2数据挖掘的起源 数据挖掘于1 9 8 9 年3 月在美国底特律召开的第i i 届国际人工智能联合 会议的专题讨论会上被首次提出的。 由于是一门新兴的、 来自各种不同领域 的交叉性学科， 涉及到机器学习、 模式识别、 统计学、 智能数据库、 知识获 取、 数据可视化、高性能计算、专家系统等多个领域。 因此有很多不同的术 语名称，除了数据挖掘称呼外，主要还有 “ 知识抽取 ( i n f o r m a t io n e x t r a c t io n ) , “ 信息发 现” ( i n f o r m a t i o n d i s c o v e r y ) , “ 知识发 现” ( k n o w l e d g e 西南 交通大学博士研究生学位论文第3 页 . . -. -. -.- . -.一-.-.-. . . -. -曰.-.- d i s c o v e r y ) . “ 智能数 据分 析” ( i n t e l l i g e n t d a t a a n a l y s i s ) , “ 信息收获” ( i n f o r m a t i o n h a r v e s t in g ) 等 等 称 法4 5 , 4 7 1 。 从 数 据 挖 掘的 定 义中 可以 看出 ， 数据挖掘更强调与数据库的联系。 另外， 在数据库知识发现的过程中实施知 识发现这一步骤也称为数据挖掘，因此有人认为数据挖掘是k d d的一个环 节。本文将不加区别地使用两者。 一切新事物的产生都是由需求驱动的。 数据挖掘也不例外， 它是应用需 求推动下多种学科融合的结果8 - i l l 。 首先是数据库技术。 随着数据库技术的 不断发展及数据库管理系统的广泛应用， 大型数据库系统已经在各行各业普 及， 数据库中存储的数据量急剧增大。 在大量的数据背后隐藏着许多重要信 息， 而这些重要信息可以很好地支持人们的决策。 可是目前用于对这些数据 进行分析处理的工具却很少。目前人们用到的主要是数据库的存储功能， 而 隐藏在这些数据之后的更重要的信息则没有充分利用。 这些信息是关于数据 的整体特征的描述及对发展趋势的预测， 在决策生成的过程中具有重要的参 考价值。 数据库技术的日益成熟和数据仓库的发展为数据挖掘提供了发挥的 平台。 其次， 在数据库技术飞速发展的同时， 人工智能领域的一个分支一一机 器学习的研究也取得很大进展。自5 0年代开始机器学习的研究以来，先后 经历了神经模型和决策理论、 概念符号获取及知识加强和论域专用学习三个 阶段， 根据人类学习的不同模式人们提出了很多机器学习方法， 如:实例学 习、 观察和发现学习、 神经网络和遗传算法等等。 其中某些常用且较成熟的 算法已被人们运用于实际的应用系统及智能计算机的设计和实现中。 数据挖 掘中的许多方法就来源于机器学习 1 0 - 1 3 1 最后，是应用领域的推动。由于数据存储技术的日渐成熟，数据库和联 机事务处理( o l t p ) 已经被广泛应用于金融、证券、保险、销售以及天气预 报、 工业生产、 分子生物学、 基因工程研究等各行各业2 , 3 , 5 - 7 , 1 2 1 。 这些都积 累了大量数据， 而且在产生着更多的数据。 对于这些数据， 人们已经不满足 于传统的统计分析手段， 而需要发现更深层次的规律， 提供更有效的决策支 持。专家系统靠人工获取知识这一 “ 瓶颈”在日益膨胀的“ 数据山” 面前显 得更加无力。 因此，我们说数据挖掘是应用需求推动下跨学科发展的产物。 1 . 1 . 3数据挖掘研究现状 数据挖掘就是从大量数据中发现隐含的知识和规律。 它既是一种知识获 西南 交 通 大 学 博士 研究 生 学 位 论文第9 页 一-曰 -. 一.-. . . . - . .一. . .-.-. 一 要求的 先验概率和模糊集中 要 求的 隶属度等， 算法简 单、 易 于 操作， 可用于 分类等挖掘任务; 规则归纳:通过统计方法归纳、提取有价值的 i f - t h e n规则。规则归 纳的技术在数据挖掘中被广泛使用，例如关联规则的挖掘; 可视化:采用直观、形象生动的方式将信息模式、数据的关联或趋势 等呈现给决策者，决策者可以通过可视化技术交互式地对数据进行分析。 3 .根据发现的知识种类分类，这种分类有:关联规则挖掘、总结规则 挖掘、 特征规则挖掘、 聚类规则挖掘、分类规则挖掘、 偏差分析、 趋势分析、 模式分析等。如果以挖掘知识的抽象层次划分，又有原始层次的数据挖掘、 高层次的数据挖掘和多层次的数据挖掘等。 1 . 1 . 6数据挖掘与相关学科的区别与联系 与数据挖掘关系密切的相关学科包括机器学习、统计学、数据库技术 和可 视化 技术等6 , 1 0 - 1 3 , 8 1. 8 2 1 。 下 面 我们将分别 讨论数 据挖 掘与机器学习、 统 计学和数据库技术之间的关系。 机器学习被认为和数据挖掘的关系最密切，二者的主要区别在于:数 据挖掘的任务是发现可以理解的知识，而机器学习关心的是提高系统的性 能， 因此训练神经网络来控制一根倒立棒是一种机器学习过程， 但不是数据 挖掘; 数据挖掘的对象是大型的数据库， 要处理的数据量非常巨大。 而机器 学习处理的数据集相对要小得多。 所以， 数据挖掘算法的效率、 有效性和可 扩展性都显得至关重要。 数据挖掘和统计学相同之处:都是从数据中得到知识，该知识可以是 对相关模式的理解和数据值之间因果关系的解释， 或者是对未来数值的预测 等。 它们之间不同之处是: 统计学在进行数据分析时主要考虑的是模型给定， 参数估计， 诊断检查， 模型比较和渐近估计等， 而数据挖掘则主要考虑的是 模型的复杂性，挖掘的复杂性，挖掘速度，挖掘的精度，可概括性等。 数据挖掘与传统的数据库技术也不同。 ( i ) 数据挖掘与数据库报表工具 不同， 他们之间的区别是: 数据库报表制作工具是将数据库中的某些数据抽 取出来， 经过一些数学运算， 最终以特定的格式呈现给用户， 而数据挖掘则 是对数据背后隐藏的特征和趋势进行分析， 最终给出关于数据的总体特征和 发展趋势。 ( 2 )与数据库的查询系统相比较，数据挖掘技术也存在着显著的不同。 首先，传统的数据库查询一般都具有严格的查询表达式，可以用 s q l语句 第 1 0 页 西南交通大学研究生博士论文 描述。 而数据挖掘则不 一 定具有严格的要求， 常常表现出即时、 随机的特点。 查询要求也不确定。整个挖掘过程也无法仅用 s q l语台 就能完整表达，实 际上，数据挖掘常常用 一 种类s q l语言来描述。再者，传统的数据库查询 一 般生成严格的结果集， 但数据挖掘可能并不生成严格的结果集。 挖掘过程 往往基于统计规律， 产生的规则并不要求对所有的数据项总是成立， 而是只 要达到 一 定的事先给定的闻值就可以了。第三， 通常情况下， 数据库查询只 、 数据库的原始字段进行， 而数据挖掘则可能在数据库的不同层次 l 发掘知 识规则。 ( 3 )数据挖掘与o l a p也不同，虽然两者均属于分析型的t具，但两 者之间有着明显的区别。 数抓挖掘是一种挖掘型的z 一 具， 它能自动地发现隐 藏在大量数据背后的模式并作出预测性的分析结论。而 o l a p是 一 种自卜 向 卜 、小断深入的验证型分析 1 1 1 , 月 厂 需要光提出问题或假设。例如， 个典型的 o l a p问题是:去年哪取的用厂 购买了史多的汽车，是北京或 海?o l a p的可能的回答足:在去年，北京的川户购买了8 0 0 0辆汽车，而 海的用户购买了7 0 0 0 辆汽车。而个典型的数据挖掘问题是:根据去年 的销不 1事 信息，预测人们购买 汽车的情况。数据挖掘i j 能的回答是: 这取决于 时i 1 和地点，fi t : 夏季，处 1 . 9 - 个年龄段， 收入在某个数值区f, i p 1 j t 京1 1 户比 f 几 海相同的) ) ， 会购买史多的汽乍。 1 . 1 . 7数据挖掘的应用 数据挖掘技术的潜在应用足 1 分) “ 泛的，从政府若理决策、商业经营、 科学研究和 1 二 业企业决策支持等各个领域都1,r 以找到数据挖掘技术的用武 之地。1 1 前数据挖掘技术已在菜渡子数c , 分析、金融风险预测、产品产量、 质量分析、分子生物学、纂因1 程研究、i n t e r n e t 站点访问模式发现以及信 息搜索和分类等许多领域得到了 成功的应用!6 5 - 7 9 , 8 3 1 。从下面的例子也可以 看出这一 点。 通b y 电器公司 ( g e )与法川 屹 机发动机制造公司( s n e c ma ) ，利用数 据挖掘技术研制了c a s s i o p e e质量控制系统， 被 月 家欧洲航空公司用于诊 断和预测波音7 3 7的故障，带来了可观的经济效益。该系统于1 9 9 6年获欧 洲一等创造性应用奖。 美国钢铁公司和神户钢铁公司利用基于数据挖掘技术 的i s p a系统，研究分析产品性能规律和进行质量控制，取得了显著效果。 英国广播公司( b b c ) 也应用数据挖掘技术来预测电视收视率， 以便合理安 排电视节目时刻表。信用卡公司a m e r i c a n e x p r e s s 自 采用数据挖掘技术后， 西南 交 通大 学 博士研究 生学 位 论文第1 1 页 . 信用卡使用率增加了1 0 % 1 5 % e a t 在微观上指出犯罪人的特点， 划定罪犯的 范围，为侦破工作提供方向 18 5 1 而且，数据挖掘技术己经步入了人们的日常生活。如果你通过 i n t e r n e t 访问著名的亚马逊网上书店， 会发现当你选中一本书后，会出现 “ 该书的购 买者中有百分之 x x同时购买了x x书”的推荐。还有你通过 i n t e r n e t 使用 n e c的 r e s e a r c h l n d e x 来查找文献时，会发现当你找到一个文献并进行浏览 其摘要时，它会告诉你其他人浏览该文献之后还浏览了哪些文献等信息。 总之，如今有关数据挖掘的成功应用案例己是枚不胜举。数据挖掘技 术己经给人们的生活带来了巨大的变化，极大地提高人们的生活质量。 1 . 1 . 8数据挖掘今后的研究方向 数据挖掘今后需要在以 下方面进行更加深入地研究1 9 , 1 4 , 2 2 , 6 1 , 8 6 - 9 2 1 . i .基础理论研究。目前有关数据挖掘的理论基础方面的研究很罕见， 不利于数据挖掘进一步的深入发展。 在2 0 0 0 年k d d年会上， h e i k k i ma n n i l a 等专家就提出了要加强数据挖掘的理论研究， 建立数据挖掘的理论框架， 用 于发展数据挖掘的方法和高效算法。这里可能有人会问这样的问题:“ 为什 么要寻找数据挖掘的理论?数据挖掘是一个应用领域， 为什么我们还去关心 要不要有个理论给它?” 可能最简单的回答是让我们回顾关系数据库领域的 发展进程。数据库在6 0 年代就出现了，但该领域被认为是各种不同应用的 一个黑暗的死水潭而没有任何清晰的结构和没有任何感兴趣的理论问题。 c o d d的关系数据库模型是一个非常漂亮而又简单的理论框架，它指定了数 据的结构和将在其上进行的操作。 关系数据库模型的数学上优美结构使得它 有可能发展更为高级的查询优化和事务处理的方法。 而这些反过来又使得更 第 1 2页 西南交通大学研究生博士论文 有效、 更一般的数据库管理系统成为可能。 关系数据库模型把互不联系的各 种方法的一个大杂烩转变成人们感兴趣的、 可理解的一个整体， 同时促进了 一 个工业领域发展19 3 1 。这足以说明加强数据挖掘基础理论研究的重要性。 2 挖掘技术和算法的研究。它包括为各种各样的挖掘任务寻找好的算 法以及算法的改进与优化、 新技术新方法在数据挖掘中的应用、 并行算法的 设计与实现等。 此外， 数据挖掘了 j 一 往直接面对的是现实数据， 因此对不完整、 不确定或有噪声的数据以及各种不同类型的数据进行处理也是数据挖掘必 须解决的问题。 3 应用领域的拓展。这是数据挖掘最吸引人的地方，也是推动数据挖 掘发展的根本动力: 1 方面，数据挖掘需要向史多的应用领域渗透。另一方 面， 需要开发更多面向应用的数据挖掘系统和产品， 建立行业内的数据标准 和通用挖掘平台， 建立可交换信息和共享知识的通用数据仓库是今后要解决 的问题。 而且数据挖掘还要若重解决如卜 的两个问题: ( i ) 用户参i j 和领域知识:数据挖扶 1 的对象足某专 业领域中积累的 数抓 . 挖掘过程是个人机交) 1_ 、多次反鱼的过程: 挖掘的结果要应川于i 亥 专0 . . f* f 此数w挖# k1 的整个过不 r，(1 . 都离不1 f ! 仗 )ii 领域的 1 业知识。1 ii i 的数pl ,; 挖掘系统或_ i 具很少能11 . i i 做到1 1 : 1 1 1 户参与到挖b f i 过程il l . 用) ” 的背景知识 和指r 作1 f1 r 11 . 以加快挖掘的进程， i f l i . ni l f 发现的知识的有效性， 将相关领 域的知识融入数据挖掘系统， 1 1 足 一 个if要但没有很好解决的问题。 ( 2 ) 知识的维护和史新: i i i 的数据积* ; 1 4 能导致以前发现的知识失效， 这些知识需要动态维护和及时史新。 如何有效地利用已有的知识和信息来更 新知识将是今后研究的重t,i e 1 . 2本文的研究思路、主要工作和结构安排 1 . 2 . 1本文的研究思路 关联规则是数据挖掘中的 一 个重要的研究领域，有着广泛的应用背景。 如今它在顾客购物模式分析、日录设计、商品广告邮寄分析、 追加销售、仓 储规划、网络故障分析、站点访问模式分析、d n a分析和保险理赔分析等 领域中都有了成功的应用案例。 目前对关联规则的研究主要集中在挖掘算法 的研究，已出现了众多的挖掘算法， 应该说不同的算法各有优缺点，由于在 理论上还不能证明哪一个算法是最优的， 所以对现有的算法进行分类研究就 西南交通大学博士研究生学位论文第1 3 页 显得很有必要。 理论指导实践。 探讨关联规则的理论背景， 对关联规则的进一步深入发 展有重要的作用， 不仅可为它今后的发展提供有力的理论依据， 而且也为今 后一些相关的理论成果应用到关联规则中提供一个桥梁作用。 在传统关联规则挖掘问题中， 巨量规则的生成， 使得人们难以有效理解 和利用这些知识。 从某种意义上讲， 这将会影响关联规则向纵深领域的应用， 最终影响到关联规则的进一步发展。 这样， 如何减少规则的数量就成了一个 巫待解决的问题。 数据挖掘中一个至关重要的方面是挖掘出的知识应该是有趣的， 即是指 有用的， 意外的或新颖的。 近年来，已经出现了许多数据挖掘技术用来从数 据库中挖掘兴趣规则。 在关联规则挖掘问题中， 兴趣规则主要是通过引入一 个兴趣度量来获得的。目前出现了许多兴趣度量， 在相应的领域已经发挥了 重要作用。 由于不存在一个通用或者说理论上证明最有效的兴趣度量， 所以 对这些己出现的兴趣度量进行研究就显得非常重要， 有助于挖掘出真正的兴 趣规则和较好地解决关联规则中的规则质量问题。 另外， 传统关联规则挖掘问题中存在着两个不足， 即所有的项目集被同 等对待和用唯一的最小支持度与最小信任度来作为衡量的标准。 这样， 一方 面， 可能无法得到一些真正有用或者说是感兴趣的知识， 另一方面， 挖掘出 的知识中可能存在大量浅显的知识， 即明显的事实。 解决这些不足， 在一定 程度上， 也相当于解决关联规则挖掘问题中的数量和质量问题。 所以， 对这 个问题的研究十分有意义。 新的数据积累可能导致以前发现的知识失效， 这些知识需要动态维护和 及时更新，如何利用己有的知识来进行知识更新是数据挖掘的研究重点之 一。 粗糙集理论是一种研究不精确、 不确定性知识的数学工具，由于粗糙集 方法无需提供除与问题相关的数据集合外的任何先验信息， 所以适合于发现 数据中隐含的、 潜在有用的规律， 即知识， 而且粗糙集发现的知识是显式的 定量描述， 可被人理解， 这些正是数据挖掘所追求的。 所以 研究基于粗糙集 的增量式的更新算法就更有意义。 1 . 2 . 2本文的主要工作 本文是围绕国家自然科学基金项目进行的，主要的工作包括以下几个方 面: 1 .关联规则研究 第 1 4 页 西南交通大学研究生博士论文 丽 年 来 关 联 规 则 挖 掘 问 题 的 发 展 情 况 进 行 较 全 面 地 回 顾把现有的关 联规则挖掘算法进行分类，深入地分析和探讨一些典型的关联规则挖掘算 法。 给出一些关联规则应用的实例， 通过这些实例来说明关联规则在有关领 域的应用方法。 还讨论推广的关联规则问题及其典型算法以及关联规则与图 论之间的联系，并指出关联规则本身存在的不足之处。 2 .关联规则与数学 主要讨论关联规则中项目集与数学中的格、 不动点以及概念格之间的联 系， 建立一些有用的结论: 首先指出挖掘所有频繁项目集就相当于在项目集 格上挖掘具有支持度约束的所有结点的集合。 接着， 说明闭项目集就是关联 关系中一个伽罗瓦闭算子的不动点， 挖掘所有频繁闭项目集就相当于在闭项 目集格上挖掘具有支持度约束的所有结点的集合。 最后， 指出关联关系中一 个概念的内涵就是一个闭项目集. 而且关联关系的概念格上的每一个概念的 内涵的支持度都是山其外延所确定， 所以关联关系的概念格不仅保留了闭项 目集的信息也同时保留了闭项目集的支持度的信息， 那么， 挖掘所有的频繁 闭项目集就相当于在这个概念格上挖掘所有外延满足约束的概念。 通过这些 讨论，可以看到关联规则虽然来源于实际应用，但它有着深厚的理论背景， 这为它今后的发展提供了有力的理论依据。另外， 通过这些讨论，也为今后 能把格、 不动点和概念格等数学中的一些理论成果应用到关联规则中起到桥 梁作用。 3 .广义关联规则基 在传统关联规则挖掘问题中， 巨量规则的生成， 使得人们难以有效理解 和利用这些知识。 针对这个关联规则数量问题， 首先提出项目集的上、下闭 集的概念， 得到了一些性质。并借助于这些性质，再通过把关联规则的定义 扩充， 对原始的关联规则集施以两次删除策略， 得到了广义关联规则基。 也 给出一个直接从数据库中导出广义关联规则基的算法。 不仅提高了规则的生 成效率而且规则的数量大大减少， 有效解决关联规则挖掘问题中产生大量规 则这个问题。 最后还对广义关联规则基的不足进行分析， 并给出挖掘频繁闭 项目集的所有下闭集的算法。 4 .兴趣度量研究 这部分的主要工作针对关联规则中的规则质量问题， 对关联规则挖掘问 题中的常用兴趣度量进行研究， 通过与统计学中相关系数度量的比较， 得到 一 些有意义的结论: 一是基于支持度的删除策略确实可以删除不相关和负相 关的项目集: 二是我们发现在一定的支持度范围内一部分兴趣度量表现了统 西南 交通大学 博士 研究 生学位论文第巧页 . . . . . . . 计相关性， 但其它的兴趣度量却不能， 尽管从直观上看它们是有意义的; 三 是新构造的一个兴趣度量既反映了规则的支持度也体现了规则的兴趣度的 度量， 而且还具有强相关性。 在实际应用中利用它来对规则进行排序，以挖 掘出感兴趣的规则。 5 . 甲 一 频繁闭项目 挖掘问题研究 首先分析经典关联规则问题中的两个不足， 即所有的项目 集被同等对待 和用唯一的最小支持度与最小信任度来作为衡量的标准。 接着， 介绍目前解 决这两个不足的三类典型方法: 一是采用多重最小支持度的方法; 二是多层 次挖掘方法