（系统工程专业论文）基于数据挖掘的智能决策研究.pdf

摘要 .曰.曰.曰.曰. 日日 . . . . . . . 日 .曰. . . . . . .日 摘要 当今科学技术的飞速发展， 使得数据库的规模日益扩大， 存储的数据量急剧 增加。 因而， 迫切需要有新的、 更为有效的技术和工具对各种数据信息资源进行 开采以发挥其应用潜能。 知识发现和数据挖掘技术正是在这样的应用需求背景下 产生并随着决策系统的推动而发展的。本文从系统工程进行决策分析的角度出 发， 借助数据挖掘技术中粗糙集的基本理论， 在智能决策框架的指导下， 研究了 基于数据挖掘的智能决策理论及方法。 主要理论包括: 如何利用粗糙集对典型 的决策系统即相容性决策系统和不相容性决策系统运用不同的数据挖掘方法进 行有效的数据约减和规则提取; 在增量动态的 数据库环境下讨论了 在典型决策 系统中对原始数据和增量数据进行数据约减的方法; 分析了 带有优先权属性的 粗糙集数据挖掘方法: 以基本粗糙集为基础探讨了 粗糙集扩展模型的数据分析 方法;研究了粗糙集数据预处理方法。主要研究工作及创新如下: i .将决策系统分为相容性和不相容性决策系统，针对不同系统的特点提出 不同的挖掘模型。 对相容性决策系统从两个角度作为启发式信息对条件属性进行数据约减。 第 一种方法利用了知识的不可分辨性，并以逻辑推演的方式对决策表进行数据浓 缩: 第二种方法利用了知识的粒度， 并以 概念的提升方式对决策表进行数据浓缩。 在不相容决策系统中提出了两种改进算法即决策概念包含法和粗糙重复组法对 不相容的决策系统挖掘出具有一定可信度的分类规则。 2 .在增量式动态数据库中， 提出了相容性和不相容性决策系统的数据挖掘 模型， 在相容性决策系统中， 利用决策矩阵提出改进的处理多元决策属性值的数据 挖掘模型， 可方便地对增量的数据进行直接处理就可得到基于全局数据集合的分 类规则， 并对可能性规则的可信度进行了初步探讨: 在不相容性决策系统中， 利 用g d t表与r s概念的结合，提出 利用三个参数即归纳强度、噪声、隶属度判 别指标确定分类规则的强度， 通过属性的概念归纳， 在一定的概率条件下产生分 类规则，并能有效地处理增量式的数据。 3 .针对条件属性的等价关系和优先二元关系特性，提出了改进的带有优先 权属性的粗糙集数据挖掘模型。 论文在粗糙集拓广理论的基础上， 利用属性的有序特性即优先二元关系， 提 出有序属性的数据挖掘改进算法， 使基本粗糙集和带有准则的粗糙集在挖掘分类 精度上达到统一，且挖掘出的规则简练、更具合理性和综合性。 4 .建立了粗糙集与概率统计和模糊理论的拓展模型。 利用数据的统计特征， 将概率测度与分类规则结合起来， 提出了相应的知识 西北工业大学博士学位论文 约减算法; 利用模糊属性集合的 特点 ， 把粗糙集合与模糊集合有机结合起来， 将粗 糙集中分辨矩阵的思想引入到具有隶属度属性的隐式决策系统中 进行数据约减。 5 .利用数据的分布特征，提出了一种改进的领域独立的数据预处理模型。 该模型利用x 2 统计值测度进行 属性离散化， 并 提出了 对条件属性值的分段 间隔首先进行初始化分段算法， 使其之后的归并工作大大减少， 并以不一致性水 平闭值作为停机条件，提高了离散化速度。 b . 将本文理论部分提出的数据挖掘核心模型应用到电信c r m 的客户挖掘中。 将本文提出的数据挖掘核心模型应用于电 信 c r m 的客户挖掘中 ， 主要对电 信c r m中的客户行为进行了 分组， 提出了大客户识别和划分的依据，初步验证 了论文相关方法的正确性和有效性。 【 关键词】知识发现，数据挖掘，决策表，智能决策，分类规则，属性离散化 摘要 .曰.口.曰. ab s t r a c t w i t h t h e r a p i d d e v e lo p m e n t o f t h e s c i e n c e a n d t e c h n o l e d g e , t h e s c a l e o f t h e d a ta b a s e i s b e c o m i n g b i g g e r a n d 阮 q u a n t it i e s o f d a t a s t o r e d a r e r a p i d l y i n c r e a s e d . t h e r e f o r e , t h e m o r e n e w a n d m o r e e ff e c t i v e t o o l s a n d t e c h n o le d g e a r e n e e d e d t o m i n e a l l k i n d s o f i n f o r m a t i o n r e s o u r c e s i n o r d e r t o e x e r t t h e i r a p p l i c a t i o n p o t e n t i a l . t h e t e c h n o l e d g e o f k n o w l e d g e d i s c o v e ry a n d d a t a m i n i n g a r e p r o d u c e d o n t h e b a c k g r o u n d o f a p p l i c a t i o n r e q u i r e m e n t a n d d e v e l o p e d w i t h t h e d e c is i o n s y s t e m . t h i s p a p e r r e c u r r e d t o t h e b a s i c t h e o ry o f ro u g h s e t o f d a t a m i n i n g a n d u n d e r t h e d i r e c t i o n o f t h e fr a m e o f i n t e l l i g e n t d e c i s i o n , t h e m a i n t h e o r i e s i n c l u d e i )t h e d i ff e r e n t m e t h o d s o f d a t a m i n i n g o n t h e b a s e o f r o u g h s e t a r e u s e d t o d e a l w i t h t y p i c a l d e c i s i o n s y s t e m n a m e l y c o n s i s t e n t d e c i s i o n s y s t e m a n d i n c o n s i s t e n t d e c is i o n s y s t e m i n o r d e r t o c a r r y t h r o u g h d a t a r e d u c t i o n a n d r u l e d i s t i l m e n t ; i i ) i n t h e e n v ir o n m e n t o f d y n a m i c i n c r e m e n t d a t a b a s e , t h e m e t h o d s o f d a t a r e d u c t i o n t o d e a l w i t h t h e o r i g i n a l d a t a a n d i n c r e m e n t d a t a a r e d i s c u s s e d i n t h e c o n s i s t e n t a n d i n c o n s i s t e n t d e c i s i o n s y s t e m ; i i i ) t h e m e t h o d o f d a t a m i n i n g o f ro u g h s e t i s a n a l y s i z e d t o t r e a t w i t h t h e a t t r i b u t e s w i t h p r i o r i t y ; i v ) o n t h e b a s e o f b a s i c ro u g h s e t t h e o r y , t h e d a t a a n a l y s i s m e t h o d s o f a m a l g a m a t i o n o f ro u g h s e t t h e o ry ; v ) a n d a l s o t h e p r e - d i s p o s a l m e t h o d t o d a t a b a s e i s a n a ly s i z e . t h e r e s e a r c h a n d i n n o v a t i v e r e s u l t s a r e a s f o l l o w s : 1 . t h e s y s t e m s a r e r i g o u r l y d i v i d e d i n t o c o n s i s t e n t a n d i n c o n s i s t e n t d e c i s i o n s y s t e m, a n d d i f f e r e n t d a t a c h a r a c t e r i z a t i o n o f d i f f e r e n t mi n ingmo d e l s a r e p u t f o r w a r d i n a l l u s i o n t o s y s t e ms . i n c o n s i s t e n t d e c i s i o n s y s t e m , a c c o r d i n g t o h e u r i s t i c i n f o r m a t i o n fr o m t w o a n g l e s t h e c o n d i t i o n a t t r i b u t e s a r e r e d u c e d . t h e f i r s t m e t h o d u s e d t h e i n d i s t i n g u i s h c h a r a c t e r i z a t i o n o f t h e k n o w l e d g e a n d t h e m o d e o f l o g i c a l r e a s o n i n g t o c o n d e n s e t h e d a t a i n d e c i s i o n t a b l e s ; t h e s e c o n d m e t h o d u s e d t h e g r a n u l a r it y o f t h e k n o w l e d g e a n d t h e m o d e o f c o n c e p t e x a l t a t i o n t o c o n d e n s e t h e d a t a i n d e c i s i o n t a b l e s . i n i n c o n s i s t e n t d e c i s i o n s y s t e m t w o i m p r o v e d a l g o r i t h m s n a m e l y d e c i s i o n c o n c e p t i o n c o n c lu s i o n a n d r o u g h r e p e t i t i o n g r o u p s a r e p u t f o r w a r d t o m i n e t h e c l a s s i f i c a t i o n r u l e s w i t h c e r t a i n t y r e l i a b i l i t y . 2 . 1 n t h e d y n a m i c i n c r e m e n t d a t a b a s e ， d a t a m i n i n g m o d e l s o f c o n s i s t e n t a n d i n c o n s i s t e n t d e c i s i o n s y s t e m a r e f o r m u l a t e d . i n c o n s i s t e n t d e c i s i o n s y s t e m , u s i n g i m p r o v e d d e c i s i o n m a t r i x , d a t a m in i n g m o d e l i s p u t f o r w a r d t o t r e a t w i t h d e c i s i o n a t t r i b u t e w i t h s e v e r a l v a l u e s i n o r d e r t o 西北工业大学博士学位论文 d i r e c t l y d e a l w i t h i n c r e m e n t d a t a , w h i c h c a n o b t a i n c l a s s i f i c a t i o n r u l e s b a s e d o n g l o b a l d a t a s e t ; i n i n c o n s i s t e n t d e c i s i o n s y s t e m t h e c o n c e p t i n d u c e o f i n c o n s i s t e n t d e c i s i o n s y s t e m i s b u i l t w i t h t h r e e p a r a m e t e r s a t t h e a i d o f c o m b i n a t i o n o f g d t w i t h r s t o g e n e r a t e t h e c l a s s i f i c a t i o n r u l e s w i t h p r o b a b i l i t y c o n d i t i o n . 3 . i n a l l u s i o n t o t h e e q u iv a l e n c e r e l a t i o n a n d p r i o r i ty r e l a t i o n o f t h e c o n d i t i o n a t t r i b u t e s , t h e m e t h o d o f d a t a m i n i n g o f r o u g h s e t i s a n a l y s i z e d t o t r e a t w i t h t h e a t t r i b u t e s w i t h p r i o r i ty . o n t h e b a s e o f e x t e n d r o u g h s e t t h e o ry , t h i s p a p e r p u t f o r w a r d t h e i m p r o v e d d a t a m i n i n g a l g o r i t h m w i t h p r i o r i t y a t t r i b u t e s b a s e d o n t h e p r i o r i t y r e l a t i o n . t h e r e f o r e , t h e c l a s s i f i c a t i o n p r e c i s i o n o f b a s i c r o u g h s e t a n d r o u g h s e t w i t h p r i o r i t y a tt r i b u t e s r e a c h e d u n i fi c a t i o n a n d t h e c l a s s i f i c a t i o n r u l e s b y t h i s m o d e l i n t h e s e c t i o n a r e m o r e c u r t a i l a n d r a t i o n a l . 4 . b u i l d t h e e x t e n d e d m o d e l s o f t h e rou g h s e t a n d p r o b a b i l i ty a l o n g w i t h f u z z y s e t . u s i n g t h e s t a t i s t i c c h a r a c t e r i z a t i o n o f d a t a , t h e r e l e v a n t k n o w l e d g e r e d u c t i o n a lg o r i t h m i s p u t f o r w a r d b y c o m b i n i n g t h e p r o b a b i l i t y w i t h c l a s s i f i c a t i o n r u l e s ; u s i n g t h e c h a r a c t e r i z a t i o n o f f u z z y a t t r i b u t e s , t h e d e c i s i o n s y s t e m w i t h s u b j e c t i o n d e g r e e a t t r i b u t e i s b u i l t b y c o m b i n g t h e r o u g h s e t t h e o ry a n d f u z z y s e t t h e o ry , a n d t h e i d e a o f d i s t i n g u i s h m a t r ix i s i n d u c e d t o t h e c o n c e a l e d d e c i s i o n s y s t e m t o r e d u c e d a t a . 5 . u s i n g t h e d i s t r i b u t i n g c h a r a c t e r iz a t i o n o f d a t a , a k i n d o f d a t a p r e - p roc e s s m o d e l w i t h a u t o c e p h a l y f i e l d i s p u t f o r w a r d . t h i s m o d e l u s e d x s s t a t i s t ic v a lu e s t o d i s c r e t iz e c o n d it io n a tt r i b u t e s . i t s c o r e id e a i s f i r s t l y t o i n i t i a l s u b s e c t i o n i n t e r v a l i n o r d e r t o r e d u c e t h e c o m b i n a t i o n w o r k s a n d t h e t h r e s h o l d l e v e l o f i n c o n s i s t e n t i s i n d u c e d a s s t o p p i n g c o n d i t io n t o im p r o v e t h e d i s c r e t i z a t i o n s p e e d . 6 . a p p l y i n g t h e d a t a m i n i n g m o d e l s g i v e d b y t h i s p a p e r i n t o t h e c u s t o m m i n i n g i n c r m. i n t h i s p a p e r u s i n g t h e m a i n d a t a m i n i n g m o d e ls , t h e c u s t o m b e h a v i o r i s g r o u p e d i n t e l e c o m m u n i c a t io n c r m a n d t h e a c c o r d i n g s o f i m p o rt a n t c u s t o m i d e n t i f i e d a n d c l a s s i f ie d a r e g i v e d. t h e c o r r e c tn e s s a n d v a l i d it y o f r e l a t e d m e t h o d i n t h i s p a p e r a r e t e s t e d . k e y w o r d k n o w l e d g e d i s c o v e ry , d a t a m i n i n g , d e c i s i o n t a b l e , i n t e l l i g e n t de c i s i o n , c l a s s i f i c a t i on r u l e , a t t r i b u t i o n d i s c r e t i z a t i o n ; 第 i 章 绪论 第 1 章 绪 论 1 . 1 引言 当今计算机和网络通讯技术的飞跃发展使得各个领域的信息正在急剧增 长， 信息爆炸或信息泛滥是当今数字化社会面临的一个巨大挑战。 商业上对条形 码的普遍使用使得很多行业每天都积累了大量数据、 科学上对先进的现代观测仪 器的使用导致每天产生巨量的数据、 i n t e rn e t 的迅猛发展使得网络上的各种资源 信息异常丰富。 面对数据和数据库的飞速发展， 人们迫切的感到需要新的技术和 工具以便从大量的数据中智能地、自 动地抽取出有价值的知识或信息， 从而能辅 助人们进行有效地、智能地、可靠地、全面地决策。知识发现 ( k d d )技术于 是应运而生。由 于蕴藏知识的信息大多存储于数据库中，数据库中的知识发现， 又称数据挖掘 ( d m) 成为当今知识发现的主要研究课题. 从大量数据中发现知识一般可分为两个方面: 其一是与科学发现相关，即从 观测客观世界的大量实验数据中发现数据的整体结构特征和数据间的函数关系， 并根据统计特征等推断客观世界中 数据间存在的规律性; 其二研究如何从商业数 据等事务数据库所构成的大规模数据库中， 发现其中隐含的规律性或规则。 本论 文主要讨论的是第二种知识发现的情形，目 前， 它不仅被许多研究人员看作是数 据库系统和机器学习等方面一个重要的研究课题， 而且被许多工商界人士看作是 一个能带来巨大回报的重要领域。从数据库中发现出来的知识可以用在信息管 理、 查询响应、 决策支持、 过程控制等许多方面。 k d d这个术语首先出 现在1 9 8 9 年 8月在美国底特律召开的第 1 1届国际人工智能联合会议的专题讨论会上， 1 9 9 1 . 1 9 9 3 和1 9 9 4 又接着继续举行k d d专题讨论会.随着知识发现研究的进 展与诸多实际领域的成功应用， 这一领域越来越引起众多研究者注目。 于是， 从 1 9 9 5 年开始， 每年要举办一次k d d国际会议。 另外从 1 9 9 7 年开始， k d d也拥 有了自 己 的 专门 杂志 k n o w l e d g e d i s c o v e r y a n d d a t a m i n i n g ) 。除了 研究 外， 也 出现了相当数量的k d d产品和应用系统，并且、获得了一定的成功，得到了业 界的广泛关注。 本文的研究工作源于上述背景，其目的是对 k d d进行深入的研究，探讨新 的知识发现方法，以及研究如何将数据库和机器学习等方法有机地结合在一起， 从而进行智能地、有效地决w. 1 . 2 知识发现研究的进展评述 西北工业大学博士学位论文 1 . 2 . 1 1 . 2 . 1 . 1 知识发现和数据挖掘 基本定义 知识发现k d d这个术语于1 9 8 9 年出 现， 其定义几经变动， 最新的描述性 定义是在k d d %国际学术会议上f a y y a d u . s m y t h p 对k d d所作的定义: k d d 是识别出 存在于数据集中有效的、 新颖的、 具有潜在效用的 乃至最终可理解的模 式的非平凡过程。 在上面的定义中， 涉及几个需要进一步解释的概念: “ 数据集” 、 “ 模式” 、“ 过程” 、“ 有效性” 、“ 新颖性” 、“ 潜在有用性” 、“ 最终可理解性，. “ 非平凡过程” 。数据集是一组事实f ;模式是一个用语言l来表示的一个表达 式e ， 它可用来描述数据集f 中的某个子集乓， e 作为一个模式要求它比 对数据 子集 f e 的枚举要简单;过程在 k d d中通常指多阶段的一个过程，涉及数据准 备、 模式搜索、 知识评价、 以 及反复的修改求精; 有效性是指发现的 模式对新的 数据仍保留 一定的可信度; 新颖性要求发现的模式应该是新的; 潜在有用性是指 发现的知识将来有实际效用; 最终可理解性要求发现的模式能被用户理解; 非平 凡过程是指知识发现过程已 经超越了一般封闭形式的数量计算，而且包括对结 构、模式和参数的搜索过程。 数 据挖掘是k d d过程中的一 个特定步 骤 1 - 2 1 ， 它 是应用具体算法从数据中 提 取模式和知识。 具体来说， 数据挖掘就是应用一系列技术从大型数据库或数据仓 库的数据中提取人们感兴趣的信息和知识。 这些知识或信息是隐含的、 事先未知 而潜在有用的，提取的知识表现为概念 ( c o n c e p t s ) 、 规则 ( r u le s ) 、规律 ( r e g u l a r i t i e s ) 、 模式 ( p a t t e r n s ) 等形式. 数据开 采作为k d d过 程的 一 个特定 步骤， 它是一系列技术及应用， 或者说是对大容量数据及数据间关系进行考察和 建模的方法集合. 它的目 标是将大容量数据转化为有用的知识和信息. 其开采对 象从结构性数据源到半结构性及非结构性数据源， 包括关系数据库、 面向对象数 据库、 空间关系数据库、 推理数据库、 多媒体数据库、 时态数据库、 文本数据库、 图像数据库及音频和视频数据源等。 一个数据挖掘算法通常由以下元素组成: i ) 模型:包括模型功能和基函数等，从数据中确定参数之后就形成模型;2 )优先 准则: 由于数据的不精确性， 将导致模型的多样性和不完全性， 因此需要具有确 定模型或参数的优先机制，它一般是表示某种形式的模型对问 题的符合度函数。 3 ) 搜索算法:包括对模型、参数、优先准则的各种搜索算法。 1 .2 . 1 .2 k d d过程及k d d系统结构 k d d过程一般由三个主要的阶段组成:数据准备、开采操作、 结果表达和 解释。其主要步骤大致归纳如下: 第 t 章 绪论 s t e p 1 : 理 解领域知识的 先 验知识， 明 确系统目 标; s t e p 2 : 创建相关的目 标数据集， 即 选择数据集合或专注于需要发现的 变量或数 据样本的一个子集; s t e p 3 :数据整理和预处理， 例如去除明显错误的冗余的噪声数据，收集噪声信 息以决定在后续步骤采取何种解决噪声问题的方法; s t e p 4 : 数据约减和投影，寻找依赖于发现目 标的表达数据的有用特征，以 约减 数据规模; s t e p 5 : 选择一种与所选目 标相应的发现方法; s t e p 6 : 选 择发 现 算 法， 即 选 择 用 于 搜 索 数据中 模 式的 方 法; s t e p 7 : 实施知识发 现算法， 得到关联规则、 分类规则或聚类等形式来表达感兴 趣的模式; s t e p 8 : 解释得到的 模式， 也 可采 用可视化表示等: 可重复s t e p l - s t e p 7 的 迭代过 程; s t e p 9 : 巩固 得到的知识， 如检查与其它知识是否冲突， 将知识合并到另一系统， 以进一步加工利用等。 目 前知识发现系统k d d从知识发现、认知科学和智能系统交叉的 角度， 提 出了 双库协同 机制， 出 现了k d d的 扩展结 构b a s l e k d d扩展结构 是在k d d技 术的基础上融入双库协同机制，即构建真实数据库与基础知识库的内在联系通 道，从而用基础知识库制约与驱动k d d的发掘过程，改变k d d固有的运行机 制，在结构和功能上形成了相对于k d d而言的一个开放的、优化的扩体。 双库 协同机制的引入使得 k d d在功能上得到进一步的完善:1 )从数据挖掘方面， 双库协同机制使得知识库能够动态地参与数据库的挖掘过程， 用户的先验知识及 知识库中的固有知识通过此机制可以产生定向挖掘， 以提高认知自主性和避免海 量搜索的产生;2 ) 在知识库的维护方面，通过双库协同机制可在数据挖掘过程 实时地修改和维护知识库中的内容， 包括冗余性检验， 矛盾处理等. 其系统总体 结构图如图1 . 1 所示。 西北工业大学博士学位论文 将获得的规则嵌入发掘知识库检 查是否重复、冗余、矛盾 获得假设规则 定向发掘过程 聚焦 搜索发掘知识库中知识节点 的关联状态，确定有限等级 划分数据子库划分知识子库 预处理真实数据库基础知识库 图1 . 1 k d d系统总体结构图 具有双库协同机制的k d d具有如下特点: 1 ) k d d有机地沟通与融合了k d d新发现的知识与基础知识库中固有的知识， 使它们成为一个有机的整体:即实现了“ 用户的先验知识与先前发现的知识 可以祸合到知识发现过程中，. 2 )在知识发现过程中， k d d对于冗余性、 重复性、 不相容的信息作出了实时处 理，有效地减少了由于过程积累而造成的问题的复杂性，同时为新旧知识的 融合与合成提供了先决条件;实现了知识与数据库同步进化. 3 )从认知科学的角度看， k d d强化并提高了知识发现的智能化程度， 提高了认 知自 主性，较有效地克服领域专家的自 身局限性，实现了采用领域知识辅助 初始发现的聚集。 4 )作为k d d的核心技术一 双协同机制的研究。揭示了在一定建库原则下，知 识子库与数据子类结构之间的对应关系，为实现限制性的搜索而减少搜索空 间、提高挖掘效率提供了有效的技术方法 第 1 章 绪论 1 .2 . 2 k d d研究的主要问 题 由于知识发现系统的基本输入是数据库中的原始数据，因此需要特别关注 数据本身特有的一些性质 1 6 7 1 . 1 .数据的规模和冗余性 知识发现所面临的数据库一般是非常庞大的且可能包含冗余的信息。数据 的规模包含两方面的含义: 其一是数据对象的多少， 其二是数据对象的属性的多 少。 对象约减可以采用实值离散化技术， 对象属性约减可以 根据属性的重要性来 应用某种特征选择约减技术。 2 .数据的不确定性 数据的不确定性是指并非全域中的每个概念都可以通过属性值来充分与精 确地表达，知识发现的模式也只可能在一部分数据上有效。 3 .数据的不完整性 由于不完整的数据域和数据域上值的缺少所造成的不完整数据，必然会影 响发现的结果。目 前数据库并非是面向知识发现进行设计的， 而模式的发现、 评 价与解释很可能需要数据库中不存在的信息。 4 .数据的动态性 大多数据库中的内容将经常变化。在一个在线系统中，必须采用预警机制 来保证这些变化不导致错误的发现。 一般认为在数据库中发现知识是一种动态过 程，这就要求知识发现方法一般应是循序渐进式的。 5 .噪声数据和稀疏数据 错误的数据对现实世界数据库是在所难免的，这主要来源于数据采集的各 个环节。 数据库中的信息在实例空间中可能是稀疏的， 这必然会影响知识发现的 效率。 另一方面， 一些异常数据模式不仅不时噪声数据， 反而正是知识发现所关 注的目标。 6 .仅由正例构成的数据实例 基于实例的学习是通过正实例和反实例的观测来导出有效规则。但是，一 般在数据库中保存的数据通常只有正实例， 没有反实例。 为了仅从正实例中获得 知识， 在建造数据库时应附加数据间的必要约束、 属性值的层次结构与包含关系 等。 7 .不同类型的数据源 现今的数据库大多是关系数据库模型， 随着数据库规模和功能日 益完善， 新 的数据库模型不断出现， 企业网和国际互联网上也有众多的数据源， 各种知识库 也是一种数据源，这些数据源上的数据挖掘正吸引着越来越多研究人员的兴趣。 西北工业大学博士学位论文 1 . 2 .3知识发现的方法 在关系型数据库中，数据之间的关系是通过数据的属性和元组之间的逻辑 关系表示出 来的， 根据数据间逻辑关系的内涵与知识发现的具体目 标， 可将知识 发 现 的 方 法 归 纳 为 如 下 几 类 3 5 ,16 7 气 一、知识发现的信息论方法 该类方法是利用信息论原理， 计算数据库中各属性的信息量， 建立决策树或 决策规则树，它是对数据仓库发现有用知识的有效方法。 1 . i d 3 方法 它是利用信息论中互信息寻找数据库中具有最大信息量的字段，建立决策树 的一个结点，再根据字段的不同取值建立树的分枝，在每个分枝子集中重复 建立树的下层结点和分枝，叶子结点为正例 ( p ) 或反例 ( n ) 。 这样就建立了 决策树。 国际上罪有影响和最早的决策树方法是q u i u l a n 研制的i d 3 方法。 这 种方法对数据库越大效果越好. 后人在i d 3 方法的基础上又发展了 各种决策 树方法。 2 . i b l e方法 利用信息论中的信息容量，寻找数据库中信息量从大到小的多个字段的取值 建立决策规则树的一个结点，字段的取值是由译码函数按正例标准而决定的 值，字段的信道容量作为该字段的权值，结点中包含两个阐值。结点中的多 个字段名、权值、正例标准值、阐值共同构成了一个决策规则。权值和两个 基本点阐值进行比 较，分别建立左、中、右三个分枝，在各分枝子集中重复 建立树结点和分枝的过程， 叶子结点为正例 ( p ) 或反例 ( n ) 。 这就建立了决 策规则树。 i b l e 方法比i d 3 方法在识别率上提高了 十个百分点。 二、知识发现的集合论方法 1 .粗集方法 在数据库中将行元素看成对象，列元素看成属性。等价关系 r定义为不同对 象在某个属性上取值相同，这些满足等价关系的对象组成的集合称为该等价 关系r的等价类。 条件属性上的等价类e与决策属性上的等价类y之间有三 种关系:1 )下近似:y包含 e ; 2 )上近似:y和 e的交非空:3 )无关:y 和e的交为空。对下近似建立确定性规则，对上近似建立不确定性规则，对 无关情况不存在规则。 2 .概念树方法 数据库中记录的属性字段按归类方式进行抽象，建立起来的层次结构称为概 第 i 章 绪论 念树。利用概念树提升的方法可以 大大浓缩数据库中的记录。对多个属性字 段的 概念树提升， 将得到高 度概括的知识基表，再将它转换成规则。 3 .覆盖正例、排斥反例方法 它是利用覆盖所有正例、排斥所有反例的思想来寻找规则。比较典型的有 mi c h a l s k i 的a q 1 1 方法。 三、知识发现的仿生物技术 1 .神经网络方法 它模拟了人脑神经元结构， 以mp 模型和h e b b 学习规则为基础， 建立了 三大 类多种神经网 络模型。 1 )前馈式网络: 它含感知机、 反向传播模型、 函数型网络、 模糊神经网络等。 此网络可用于预测、模式识别等方面。 2 )反馈式网 络: 它以h o p f i e l d 的 离散 模型 和连续 模型为 代表， 分别用于联想 记忆和优化计算等。 3 )自 组织网 络: 它以a r t 模型、 k o h o l e n模型为代表，用于聚类分析。 2 .遗传方法 这是模拟生物进化过程的算法。它由三个基本算子组成: 1 )繁殖 ( 选择) : 从一个旧种群选择出生命力强的 个体产生新种群的过程。 2 )交叉 ( 重组) : 选择两个不同 个体的部分进行交换， 形成新个体。 3 )变异 ( 突变) :对某些个体的某些基因进行变异。 这种遗传算法能够产生一群优良 后代，这些后代力求满足适应值，经过若干 代的遗传，将得到满足要求的后代。遗传算法已 经在优化计算和分类机器学 习等方面发挥了显著的效果。 四、公式发现 在工程或数学数据库中对若干数据项进行一定的数据运算， 求得相应的数学 公式。 1 . b a c o n系统 比 较典型的b a c o n发现系统完成了物理学中大量定律的重新发现。它的基 本思想是对数据项进行初等数学运算形成组合数据项，逼近常数，经过若干 次运算，若组合数据项的值为常数项，就得到组合数据项等于常数的公式。 2 . f d d系统 基本思想是对两个数据项交替取初等函数后与另一种数据项的线性组合逼近 直线，经过若干次运算，若得到直线时，就找到了两个变换后的数据项的先 行组合公式。 西北工业大学博士学位论文 . 五、统计分析方法 利用统计学原 理对数 据库中的 数 据进行分析， 有如下 方法: 1 .群集和分类: 群 集 是一 种寻 找 相关 元 组的 技 术。 这些 分 组 通 常都 是由 最 小 化准 则的 分 组 数 据 点 确 定 。 一 旦 使 用已 有 数 据 确 定 群 集 之 后， 就 可以 把 新的 数 据点 分 类 到 它 们 所 属的 群 集中。 对 数 据分 类的 一 种常 用算 法是k最 近 相邻 算 法。 在 这 种算 法中 ， 将使用距离( 例如欧几里德距离或曼哈顿距离) 测度来确定最接近新数据点的k 个数据点。 在新数据点周围画出包含最临近k个数据点的n - 维圆圈， 然后画出 圆圈内每种类型的点数，最后估计新点位于 m 中的概率。新数据点属于概率值 最高的那一类。 这种方法的优点是易于理解， 而且非常有效. 其缺点是每一次都 必须执行所有的计算，所有数据都必须存储，而且结果取决于距离测度。 分类是基本的一种认知形式，这是属于一种元组之间的关系。在机器学习 研究的诸多算法运用概率统计、 决策树 ( i d 3 ) 、 神经网络方法、 多元代数空间理 论等， 使得分类算法的研究取得了长足的进展。 一般地， 可以 将分类规则分成两 类: 表示数据库中所有数据都满足的特征称为特征规则; 陈述某类概念和与其他 概念差异的规则称为分类规则。 2 .依赖关系: 构成一个描述变量之间函数依赖关系或相关关系的模型。函数依赖是数据 库设计中不可避免的， 同时也是数据内在联系的体现， 函数依赖属于属性之间的 关系。函数依赖关系的发现可以基于所发现的规则来产生。 3 .相关分析和回归分析 相关分析是用相关系数来度量变盆间的相关程度。回归分析是用数学公式来 表示变量间的数量关系，方法有线性回归和非线性回归。 4 .差异分析 从样本统计量的值得出的差异来确定总体参数之间是否存在差异。典型方法 为方差分析，它是通过分析实验数据中不同来源的变异对总体变异的贡献的 大小，从而确定实验中的可控因素是否对实验结果有重要的影响。 5 .因子分析 它是用较少的综合变量来表达多个观察变量。根据相关性大小把变良分组， 使得同组内的变量之间相关较高，不同组变量之间相关较低。 6 .判别分析 建立一个或多个判别函数，并确定一个判别标准，然后对未知属性的对象， 根据测定的观测值，将其划归已知判别中的一类。判别准则有错误率最小或 错误损失最小等. 第 1 章 绪论 六、其它方法 t .数据约减: 对于给定的数据库或数据集合， 产生其一满足一定条件的子集. 数据约减 包括数据对象的约减和对象属性的约减。 数据欲减会导致数据丢失， 但由于上面 所述的原始数据的种种特征， 知识发现往往要求产生一个可发掘的数据集合。 一 般地， 数据约减是与知识发现的目 标密切相关的。 除此之外， 我们可以根据数据 本身的性质， 给出数据约减过程中的不变量， 然后研究在确定的不变量保持不变 的的前提下的数据约减的方法。 2 .变化和偏差分析: 偏差包括很大一类潜在有趣的 知识，比 如分类中的反常实例、 模式的 例外、 观测结果对期望的 偏离以 及量值随时间的变化等等。 该方法的 基本思想是: 寻找 观察结果与参照量之间有意义的差别。 观察可以上一组变项值的某个模式， 参照 可以是给定模式的预测、外界提供的标准量或另一个观察。 3 .关联规则的发现: 关联规则就是描述数据库中数据项之间所存在的 关系的 规则。 知识发现过 程一般只对满足一定的 支持 度m i n i s u p p o rt 和可 信度m i n i c o n f i d e n c e 的 关联规则感 兴趣。 其发掘过程主要分