（管理科学与工程专业论文）决策表中的知识发现研究.pdf

中国科学技术大学博士学位论文决策表中的知识发现研究 中文摘要 j 知识发现是人工智能、机器学习、统计学、数据库和数据仓库等学科相互交叉所形 成的一个活跃的且具有广阔应用前景的研究领域。 作为记录过程化决策情形的一种数据库，决策表也是知识发现研究的一个对象。根 据决策表自身所具备的特点，如何从中有效地提取有用的信息和发现新的知识，是摆在 决策分析和技术研究者们面前的一个新的亟待解决的课题事本文对决策表中的知识发现 研究从基本理论概念到实际应用分析，从理论模型到算法实现和系统应用，都进行了较 为深入系统的讨论。 我们介绍了目前知识发现的研究现状，讨论了决策表与知识发现之间的关系。知识 发现研究中，一直存在着信息的不确定性等问题，经典逻辑不足以解决这些不确定性问 题。f 人们提出的解决方法，包括统计方法、模糊集理论以及证据理论等，都有一些内在 的缺碚或限定范围。粗糙集理论是一种研究不精确、不确定性知识的数学工具，它为知 识发现提供了一种新的方法和工具。但粗糙集理论也存在着局限性：一是研究的信息系 统的属性值必须是离散的，二是研究的信息系统的数据必须是完全的。 数据丢失是导致数据不完全的一个重要原因，也是现实决策表中的一个常见特征。 统计学和计算机科学两个领域的研究者已经提出了一些处理不完全数据的方法，在知识 发现领域，已有研究者对能处理丢失数据的知识发现方法进行了研究，并开发了相应的 系统。决策表中的条件属性之间不是相互独立的，我们通过主成分分析方法来分析条件 属性之间的相关性，并以此来估计丢失数据，提出了基于主成分分析方法的不完全数据 补齐方法，并将该算法与均值替换法进行了比较。在进行决策表丢失数据补齐的时侯， 还应该考虑决策表中信息的变化，特别是冲突情况的变化，我们要避免在进行数据补齐 的过程中人为地引入冲突信息。一个决策表系统中的数据基本反映了它所涉及的问题的 基本特征，尽管系统中可能存在不完全数据，决策表不完全数据的填补应该尽可能反映 系统所反映的基本特征以及隐含的内在规律。基于这种思想，我们讨论了基于粗糙集理 论的不完全数据补齐算法，该算法能够使完整化后的决策表系统产生的分类规则具有尽 可能高的支持度，产生的规则比较集中。 目前国际上针对离散化问题也获得了一些有价值的研究成果，但这些方法通常会给 原始决策表引入冲突。棒文分析了决策表的属性重要性问题，提出了根据不可辨另l j 矩阵 来计算条件属性重要性的新算法，基于属性重要性，提出了不改变决策表原有的不可分 辨关系的离散化新算法，弥补了经典离散化方法的不足。 ，决策表的知识获取主要通过对决策表进行约简从而获得决策规则，约简又分为属性 约简和值约简，值约简是属性约简的进一步简化。通过可辨别矩阵和逻辑运算，可以得 到决策表的所有可能的属性约简结果，基于可辨别矩阵和逻辑运算的属性约简算法可以 i i 中国科学技术大学博士学位论文决策表中的知识发现研究 得到决策表的所有可能的属性约简结果，但算法中的许多计算是重复的，计算量大。对 此，我们提出一种改进方法，先从可辨别矩阵中寻找相对属性核，然后去除可辨别矩阵 中包含核属性的元素，使得原矩阵大大的简化，降低了算法的复杂度，提高了效率。决 策表中往往存在冲突，经典的属性约简算法只是针对完全相容决策表的，而并不适用于 包含冲突的决策表。对此才我们提出了包含冲突样本的决策表中决策规则发现算法，我 们讨论了含冲突决策表中的决策规则，引入可信度因子和支持度因子两个概念，并通过 人为删除核属性来引入更多的冲突，使得获取的决策规则具有更广泛的适应性。 ( 经典的塑蕉集堡j 垒和方法已经成功地用于处理不精确、不确定的数据或知识，但它 限定所面对的数据库中所有属性值均是已知的，即数据是完全的。为了突破这一局限， 我们将经典的不可辨别关系加以扩充，形成了容差关系、非对称相似关系和扩展的不可 辨别关系，同时我们还对经典的可辨别矩阵进行了扩充。在不完全决策表中，经典的规 则支持度和可信度通常不便计算，但我们可以运用扩充的不可辨别关系对其作出最大和 最小估计。基于容差关系，我们提出未知相似算法来发现不完全决策表中的决策规则， 这种算法得到的规则是集中的，并具有最高的规则支持度，但规则可信度不一定是最大； 未知相异算法是基于扩展的不可辨别关系的，这种算法得到分布较广的决策规则，规则 支持度最低，但规则可信度不一定是最小的。 在上述讨论研究之后，为了形象地说明决策表中的知识发现研究方法，1 本文系统地 介绍了应用前几章介绍的理论方法解决实际问题的知识获取实例深圳市房屋租赁 定价系统，并对系统从训练样本中产生的决策规则结果进行了解释。最后。我们讨论了 知识发现的进一步研究方向以及本文工作的进一步研究方向。 ( 本文的创新之处如下： 将主成分分析方法运用于不完全决策表的丢失数据处理中来，提出了基于主成分分 析方法的不完全数据补齐方法。 丢失数据的填补应尽可能地反映原始决策表系统的基本特征，提出了基于粗糙集理 论的不完全数据补齐方法。 经典离散化算法常常会给原始决策表系统引入冲突，讨论了决策表条件属性的重要 性问题，提出基于可辨别矩阵的属性重要性计算的新方法，并提出基于条件属性重要性 的决策表离散化新算法，弥补经典算法的不足。 讨论了含冲突决策表中的决策规则，引入可信度因子和支持度因子两个概念，提出 了包含冲突样本的决策表中决策规则发现算法。 讨论了不完全决策表中的分类关系：容差关系、非对称相似关系以及扩展的不可辨 别关系：讨论了不完全决策表中的决策规则，给出了计算规则因子的最大和最小公式； 提出了歪塞全达苎壅中决策规则发现的两种算法：基于容差关系的未知相似算法和基于 扩展的不可辨别关系的未知相异算法。1 i i l 中国 ! 堂技术大学博士学位论文决策表中的知识发现研究 a b s t r a c t k n o w l e d g ed i s c o v e r y , w h i c h i s e v o l v i n gb y i n t e r s e c t i o no fa r t i f i c i a l i n t e l l i g e n c e ， m a c h i n el e a r n i n g ，d a t a b a s e sa n dd a t aw a r e h o u s e ，i sad e v e l o p i n ga r e ao fr e s e a r c hw i t ha b r o a d p r o s p e c to f a p p l i c a t i o n s b e i n gak i n do f d a t a b a s et or e c o r dt h ed e c i s i o np r o c e s s ，d e c i s i o nt a b l ei so n eo ft h e r e s e a r c ho b j e c t si nt h ef i e l do f k n o w l e d g ed i s c o v e r y a c c o r d i n gt oi t sc h a r a c t e r i s t i c ，h o wt o e x t r a c tn e w k n o w l e d g e f r o mt h ed e c i s i o nt a b l ei san e wi s s u ef o rd i s c u s s i o n i nt h i st h e s i s ，w e c o n d u c tac o m p a r a t i v e l yt h o r o u g h g o i n ga n ds y s t e m a t i cs t u d y0 1 1k n o w l e d g ed i s c o v e r yi n d e c i s i o nt a b l e s w ei n t r o d u c et h ee x i s t i n gs t a t eo fr e s e a r c h e so nk n o w l e d g ed i s c o v e r ya n dd i s c u s st h e r e l a t i o n s h i p b e t w e e nd e c i s i o nt a b l e sa n dk n o w l e d g ed i s c o v e r y u n c e r t a i ni n f o r m a t i o ni s a l w a y s a ni s s u ei nt h er e s e a r c h e so f k n o w l e d g ed i s c o v e r y , t h ep r o b l e m so f u n c e r t a i n t yc a n t b es o l v e dw i t ht r a d i t i o n a ll o g i c t h e r ea r ea l w a y ss o m el i m i t a t i o n s i nt h o s er e s o l v i n g m e t h o d ss u c hl i k es t a t i s t i c s ，f u z z ys e ta n de v i d e n c et h e o r y r o u g hs e tt h e o r yi sar e l a t i v e l y n e ws o f tc o m p u t i n gt o o lt od e a lw i t hv a g u e n e s sa n du n c e r t a i n t y , b u ti th a st w ol i m i t a t i o n s ， o n ei st h a tt h ea t t r i b u t i o nv a l u e so fi n f o r m a t i o ns y s t e mm u s tb ed i s c m t e ；a n o t h e ri st h a tt h e d a t ao fi n f o r m a t i o ns y s t e mm u s tb ec o m p l e t e m i s s i n gd a t ai so n eo f t h ei m p o r t a n tr e a s o n sf o rd a t ai n c o m p l e t e n e s s s o m em e t h o d sa r e p r e s e n t e dt od e a lw i t hi n c o m p l e t ed a t a t h et e n d i t i o n - a t t r i b u t i o u si nd e c i s i o nt a b l e sa r en o t i n d e p e n d e n t ，w ea n a l y z et h e r e l a t i v i t i e s a m o n gc o n d i t i o n - a t t r i b u t i o n s w i t ht h e p r i n c i p l e c o m p o n e n ta n a l y s i s ，a n dp r e s e n t am e t h o dt oi m p u t et h em i s s i n gd a t a w h i l ei m p u t i n gt h e m i s s i n gd a t a , w e s h o u l dc o n s i d e ro f t h ei n f o r m a t i o nc h a n g i n g ，n e wc o n f l i c t i o n ss h o u l dn o tb e i m p o r t e di n t oo r i g i n a ls y s t e m i n ad e c i s i o nt a b l e ，t h ed a t ab a s i c a l l yr e f l e c t si t sc h a r a c t e r i s t i c e v e n p a r ti sm i s s i n g ，s ot h ei m p u t a t i o n o f m i s s i n g d a t ai nd e c i s i o nt a b l e ss h o u l db eh e l p f u lt o t h er e f l e c t i o n a c c o r d i n gt ot h i si d e a , w ed i s c u s st h ei m p u t a t i o nm e t h o db a s e do nr o u g hs e t t h e o r y , i tc a na c q u i r e ah i g h l ys u p p o r t e dr u l e se x t r a c t e df r o mt h en e wd e c i s i o nt a b l e m o s to ft h ed i s c r e t i z a t i o nm e t h o d s w i l lb r i n gc o n f l i c t i o n si n t ot h eo r i 洲d e c i s i o nt a b l e s w e p r o p o s ean e w m e t h o dt oc a l c u l a t et h ei m p o r t a n c ev a l u eo fc o n d i t i o n - a t t r i b u t e st h r o u g h d i s c e r n i b i l i t ym a t r i x w i t l lt h ei m p o r t a n c ev a l u e ，w ec a l ld i s c r e t i z em u l t i - v a l u e da t t r i b u t e si n an e w w a y w i t h o u tc h a n g i n gt h eo r i g i n a ld i s c e m i b i l i t yr e l a t i o n s t h em a i nw a yt oe x t r a c tr u l e sf r o md e c i s i o nt a b l e si sr e d u c t i o n ，i n c l u d i n ga t t r i b u t e s r e d u c t i o na n dv a l u er e d u c t i o n ，t h el a t t e ri sa nu l t e r i o rs t e po ft h ef o r m e r w i t hd i s c e r n i b i l i t y m a t r i xa n d l o g i co p e r a t i o n , a l lp o s s i b l er e s u l t so f a t t r i b u t e sr e d u c t i o nc a r tb eo b t a i n e d ，b u t i v 中国科学技术大学博士学位论文决策表中的知识发现研究 b e c a u s eo ft o om u c h r e p e a t e dc a l c u l a t i o n ，t h ec o s ti sh i g h w eh a v ei m p r o v e dt h em e t h o d ， f i r s t l y , c o m p a r a t i v e l yc o r e - a t t r i b u t e sa r ef o u n do u tf r o mt h ed i s c e m i b i l i t ym a t r i x ，t h e nt h e e l e m e n t sc o n t a i n i n gt h ec o r e - a t t r i b u t e sa r ew i p e do f f , t h i ss i m p l i f i e st h eo r i g i n a lm a t r i x r e d u c et h ec o s ta n di m p r o v et h ee f f i c i e n c y t h e r ea r ea l w a y sc o n f l i c t i o n si nd e c i s i o nt a b l e s ， t r a d i t i o n a lr e d u c t i o nm e t h o d sm a i n l yd e a lw i t hc o m p a t i b l ys a m p l e sb u tn o ti n c o m p a t i b l y o n e s w e p r e s e n ta n e wm e t h o dt od e a lw i t hd e c i s i o nt a b l e sw i t hc o n f l i c t e ds a m p l e s w i t ht h e t w of a c t o r s ，c o n f i d e n c ea n ds u p p o r t ，w ed i s c u s st h ed e c i s i o nr u l e si ni n c o m p a t i b l yt a b l e s c o r e - a t t r i b u t e sa r ec u tt oe x t r a c td e c i s i o nr u l e s 、i t l lm o r ee x t e n s i v ea d a p t a b i l i t y w ed e v e l o pt h et r a d i t i o n a ld i s c e r n i b i l i t yr e l a t i o nt ot o l e r a n c er e l a t i o n ，n o n - s y m m e t r i c s i m i l a r i t yr e l a t i o na n de x t e n d e dd i s c e r n i b i l i t yr e l a t i o n ，t h et r a d i t i o n a ld i s c e r n i b i l i t ym a t r i xi s e x t e n d e dt o o i ni n c o m p l e t ed e c i s i o nt a b l e s ，t r a d i t i o n a lr u l es u p p o r ta n dc o n f i d e n c ef a c t o r s c a n tb ec a l c u l a t e d ，w eu s et h ee x t e n d e dd i s c e r n i b i l i t yr e l a t i o nt om a k eam a x i m u ma n d m i n i m u me s t i m a t e b a s e do nt o l e r a n c er e l a t i o n ，w ep r e s e n tam e t h o dt oe x t r a c tr u l e sf r o m i n c o m p l e t ed e c i s i o nt a b l e s ，t h er e s u l ti sc e n t r a l i z e da n dh a v et h eh i g h e s ts u p p o r t a n o t h e r m e t h o di sb a s e do ne x t e n d e d d i s c e r n i b i l i t yr e l a t i o n ，t h er e s u l ti ss c a t t e r e da n dh a v et h el o w e s t s u p p o r t b a s e do nt h et h e o r i e sd i s c u s s e di nt h ef o r m e rc h a p t e r s ，ac a s en a m e dp r i c e - m a k i n g s y s t e mi nh o u s e - l e a s i n gm a r k e ti ss t u d i e d t h et r a i n i n gd a t ai sa c q u i r e df r o ms h e n z h e n s c o m m e r c i a lh o u s el e a s i n gm a r k e t f i n a l l yw ec o n c l u d et h et h e s i s 、i t l lt h ef u r t h e rr e s e a r c h d i r e c t i o no f k n o w l e d g e d i s c o v e r y a sw e l la so u rw o r k 0 u rw o r k b r i n g sf o r t hn e w i d e a sa sf o l l o w s ： 1 1 a p p l yp r i n c i p l ec o m p o n e n ta n a l y s i st oi m p u t et h em i s s i n gd a t ai n i n c o m p l e t e d e c i s i o nt a b l e sa n d p r o p o s e an e wm e t h o d o f i m p u t a t i o n 2 t h e i m p u t a t i o no fm i s s i n gd a t ai nd e c i s i o nt a b l e ss h o u l db eh e l p f u lt ot h er e f l e c t i o n i t sc h a r a c t e r i s t i c an e w i m p u t a t i o nm e t h o d i sp r o p o s e db a s e do n r o u g h s e tt h e o r y 3 t r a d i t i o nd i s c r e t i z a t i o nm e t h o d sa l w a y s b r i n gn e w c o n f l i c t i o n si n t oo r i g i n a ld e c i s i o n t a b l e s w ed i s c u s s i m p o r t a n c ev a l u eo fc o n d i t i o na t t r i b u t e sw i t h d i s c e r n i b i l i t ym a t r i x 。 a n dp r o p o s ean e wm e t h o dt oc a l c u l a t et h ei m p o r t a n c ev a l u e an e w d i s c r e t i z a t i o n m e t h o di sp r e s e n t e db a s e do nt h ei m p o r t a n c ev a l u e 4 r u l e si n i n c o m p a t i b l yd e c i s i o nt a b l e sa r ed i s c u s s e dw i t ht w of a c t o r s ，s u p p o r ta n d c o n f i d e n c e am e t h o do f e x t r a c t i n gr u l e sf r o md e c i s i o nt a b l e sw i t hc o n f l i c t e ds a m p l e s i sp r o p o s e d 5 t o l e r a n c er e l a t i o n , n o n - s y m m e t r i c s i m i l a r i t y r e l a t i o na n de x t e n d e dd i s c e r n i b i l i t v 。e l a t i o na r ed i s c u s s e di ni n c o m p l e t ed e c i s i o nt a b l e s t h e p r o p e r t i e so fs u p p o na i l d v 中国科学技术大学博士学位论文决策表中的知识发现研究 c o n f i d e n c eo fd e c i s i o nr u l e si nt h ei n c o m p l e t ed e c i s i o nt a b l e sa r es t u d i e di nd e t m l h o wt oe s t i m a t et h es u p p o ra n dc o n f i d e n c eo fd e c i s i o nr u l e si nt h ei n c o m p l e t e d e c i s i o nt a b l e si se x a m i n e d t w oa l g o r i t h m sf o rd i s c o v e r i n gk n o w l e d g eu n d e rt h e e n v i r o n m e n to f i n c o m p l e t ed a t aa r ep r e s e n t e d b a s e do nt h et o l e r a n c er e l a t i o na n dt h e e x t e n d e dd i s c e r n i b i l i t yr e l a t i o n v i 中国科学技术大学博士学位论文决策表中的知识发现研究 致谢 在即将结束本文写作的时侯，我自然会想起那些在我攻读博士学位期间直接或间接 指导、帮助和关心我的人们。 首先要感谢我的导师梁棵教授。他那渊博的知识给我指明了研究方向；敏捷的思维 启迪了我的研究思路；严谨的治学精神培养了我的研究能力；开明的作风为我创造了良 好的研究环境。是在梁老师悉心的指导和精心的培养下，我才具有了现在的研究工作的 能力，他对我的教导和影响也必将在我以后的科研工作中起到很大的作用。 感谢吴城庆博士、奚炜博士；感谢博士生吴文明、姚佐文、刘德林、殷尹、周俊、 郭强、李红艳、杨波、王国华、余玉刚和刘晓伟。在平时的合作和接触中，他( 她) 们 或给我有益的启发，或给我许多有形或无形的帮助。 感谢华中生教授在我论文完成过程中所给予的指导和关心：还要感谢陈韵韵老师、 吴晓萍老师，在进行文献调研过程中她们为我提供了很大的帮助。 在此，我还要感谢我的妻子刘燕燕女士，是她的大力支持才使我能够顺利完成研究 工作和本文的写作。我的父母和家人给予了我无微不至的关心，这些都是我完成本文的 基础。 中国科学技术大学博士学位论文 决策表中的知识发现研究 图序 图1 ；知识发现的一般过程 图2 ：x 的上近似集、下近似集 图3 ：求已知属性的均值 图4 ：已知数据标准化 图5 ：求协方差阵 图6 ：决策表1 0 离散化的第四种断点集 图7 ：决策表1 0 离散化的第一种断点集 图8 ：决策表妒的可辨别矩阵 图9 ：新决策表的可辨别矩阵 图1 0 ：关于气象信息的决策表系统的可辨别矩阵 图1 1 ：去除核属性后的新可辨别矩阵 图1 2 ：表2 l 的扩展可辨别矩阵( 未知相似) 图1 3 ：表2 l 的扩展可辨别矩阵( 未知相异) x o j 掳 侈 加 强 亚 扣 甜 鹌 钉 加 他 中国科学技术大学博士学位论文 决策表中的知识发现研究 表序 表1 ：一个决策系统的例子 表2 ：表1 中由属性集 口，6 划分的等价类 表3 ：不完全决策表 表4 ：测试数据( 粗体数据表示丢失数据) 表5 ：利用主成分分析方法估计丢失数据值的结果 表6 ：利用均值体替换算法估计丢失数据值的结果 表7 ：不完全决策表系统妒 表8 ：中间信息系统一 表9 ：完整化后的决策表系统铲 表1 0 ：待离散化的决策表 表1l ：决策表1 0 的断点信息表 表1 2 ：决策表1 0 的断点统计信息表 表1 3 ：原始决策表妒 表1 4 ：属性b 离散化后的决策表s 1 表1 5 ：属性a 离散化后的信息表铲 表1 6 ：关于气象信息的决策表系统 表1 7 ：决策表1 6 的一个约简结果 m ，a 2 ，d 4 ) 表1 8 ：决策表1 6 的另_ 个约简结果 口i ，a 3 ，a 4 表1 9 ：决策表 表2 0 ：决策规则和约束条件 表2 l ：关于汽车信息的不完全决策表 表2 2 ：房屋租赁定价系统的条件属性 表2 3 ：房屋租赁价格预测分类系统 表2 4 ：决策表2 3 的一个约简结果 墙 插 孔 孔 扎 拍 拍 拍 如 ” ” 弘 甜 拍 如 矾 矾 酯 他 第1 章绪论 知识发现( k n o w l e d g ed i s c o v e r y ) 是人工智能、机器学习、统计学、数据库和数 据仓库等学科相互交叉所形成的一个活跃的且具有广阔应用前景的研究领域。在当前的 知识经济时代，面对人类社会数据的海洋，人们日益需要从中挖掘和发现有价值的信息。 决策表作为一种特殊的信息系统，它描述了过程化决策情形，表中的若干条件状态 决定着一组行动的执行。决策表通常以数据库的形式存在，是过程化决策数据的重要存 储载体，其中存有大量具有潜在价值的信息，这些重要信息可以更好地支持人们的决策， 如何根据决策表白身的特性有效地从中提取有用的信息和发现新的知识，是摆在决策分 析和技术研究者们面前的一个新的亟待解决的课题。 本章作为绪论，首先对知识发现的研究进行了综述；研究者们频繁使用的知识发现 和数据挖掘这两个术语是否等同。它们之间存在着什么样的联系知识发现的一般过程 包含了哪些步骤，这些问题在1 2 节给出了具体的回答；1 3 节主要讨论了目前知识发 现所采用的方法，对粗糙集理论进行了重点介绍，为以后的章节打下理论基础；1 4 节 讨论了决策表与知识发现的关系；最后，1 5 节初步介绍了本文的工作和内容安排。 1 1 知识发现的研究综述 知识发现，目前具体为数据库中的知识发现( 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 ) ，是应用需求推动下多种学科融合的结果( f a y y a d ，1 9 9 6 ；高，1 9 9 8 ；李，2 0 0 0 ) 。 随着数据库技术的不断发展及数据库管理系统的广泛应用，大型数据库系统已经在 各行各业普及，数据库中存储的数据量急剧增大。在大量的数据背后隐藏着许多重要信 息，这些信息是关于数据的整体特征的描述及对发展趋势的预测，在决策生成的过程中 具有重要的参考价值。数据库技术的日益成熟和数据仓库的发展为知识发现提供了发挥 的平台。 由于数据存储技术的日渐成熟，数据库和联机事务处理( o l t p ) 已经被广泛应用于 金融、证券、保险、销售以及天气预报、工业生产、分子生物学、基因工程研究等各行 各业( t w oc r o w s ，1 9 9 9 ：g a o ，2 0 0 0 ；张，1 9 9 8 ；朱，1 9 9 9 ；石，2 0 0 0 ；田，1 9 9 9 a ： 田，1 9 9 9 b h 在工业领域，关键设备的在线监测系统和定期巡检系统日益普及。这些都 积累了大量数据，而且更多的数据正在产生。对于这些数据，人们已经不满足于传统的 统计分析手段，而需要发现更深层次的规律，提供更有效的决策支持。 在数据库技术飞速发展的同时，人工智能领域的一个分支机器学习的研究也取 得了很大进展。自5 0 年代开始以来，机器学习的研究先后经历了神经模型和决策理论、 概念符号获取及知识加强和论域专用学习三个阶段，根据人类学习的不同模式人们提出 中国科学技术大学博士学位论文 决策表中的知识发现研究 了很多机器学习方法，如：实例学习、观察和发现学习、神经网络和遗传算法等等。其 中某些常用且较为成熟的算法已被人们运用于实际的应用系统及智能计算机的设计和 实现中。知识发现中的许多方法就来源于机器学习( m a n n i l a ，1 9 9 7 ；b e r s o n ，1 9 9 7 ) 。 知识发现是一个众多学科诸如人工智能、机器学习、统计学、数据库、模式识别、 可视化技术等相互交叉、相互融合所形成的一个具有广阔应用前景的领域，目前对它的 研究集中在以下三个方面：数据库和数据仓库、人工智能和统计学( e l d e r ，1 9 9 6 ； g l y m o u r ，i 9 9 6 , g 1 y m o u r ，1 9 9 6 ) 。知识发现的对象是某一专业领域中积累的数据，挖 掘过程是一个人机交互、多次反复的过程，挖掘的结果要应用于该专业。因此知识发现 的整个过程都离不开应用领域的专业知识。目前知识发现技术在货篮数据( b a s k e t d a t a ) 分析、金融风险预测、产品产量、质量分析、分子生物学、基因工程研究、i n t e r n e t 站点访问模式发现以及信息搜索和分类等许多领域得到了成功的应用( i b m ，1 9 9 8 ； m u n a k a t a ，1 9 9 9 ：m i t c h e l l ，1 9 9 9 ；v a l d e s p e r e z ，1 9 9 9 ) 。计算机“深蓝”( d e e pb l u e ) 能够战胜人类国际象棋世界冠军，成功的一个重要因素是具有知识发现能力，能从存储 了7 0 万盘棋谱的数据库中提取有用的知识( c a m p b e l l ，1 9 9 9 ) , 如果你通过i n t e r n e t 访问著名的亚马逊网上书店，会发现当你选中一本书后，会出现“该书的购买者中有百 分之x 同时购买了x x 书”的推荐。可见，知识发现技术已经得到广泛的应用。 针对知识发现的处理过程、功能模型、算法研究和应用等不同层面，每年都有大量 的文献涌现，我们可以从知识发现的功能模型和挖掘对象两个方面对知识发现进行分类 ( b e r s o n ，1 9 9 7 ；t w oc r o w s ，1 9 9 9 ；郑，1 9 9 9 ) 。知识发现功能模型回答了“知识发现 能够干什么”的闯题，其又可分为预测模型和描述模型。预测模型包括分类模型、回归 模型和时间序列模型；描述模型包括聚类模型、关联模型和序列模型。前者也称为有监 督学习，后者称为无监督学习。按照不同的数据类型，知识发现研究在时间序列数据、 空间数据、文本数据、多媒体数据等方面展开( r o g e r s ，1 9 9 9 , 庄，1 9 9 9 ) 。 知识发现作为一个专题，首次出现在1 9 8 9 年的第十一届国际人工智能联合会 ( i j c a i ) 上。到目前为止，由美国人工智能协会( a a a i ) 主办的k d d 国际研讨会已经 召开了九次。从1 9 9 5 年起，k d d 由原来的专题研讨会发展到每年一度的国际学术会议。 i e e e ，a c m ，v l d b ，8 i g m o d 等其他学会也纷纷把k d d 作为会议主题或出版专刊。目前较 有影响的学刊是9 7 年3 月创刊的由u f a y y a d 主办的( d a t am i n i n ga n dk n o w l e d g e d i s c o v e r y 。近几年来，美国i b m 公司的a l m a d e n 研究中心，g t e ，s a s ，a t & t ，m i c r o s o f t ， s i l i c o ng r a p h i c s 等公司和加拿大的s i m o nf r a s e r 大学相继开发了一些成功的k d d 应 用系统。此外，在因特网上也有众多的k d d 研究和应用站点，如g p i a t e t s k y s h a p i r o 主办的k n o w l e d g ed i s c o v e r yn u g g e s t s 站点。与此同时，许多著名的计算机公司开始 尝试着k d d 软件的开发。比较典型的如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 i 公司的s e t m i n e r ，s p s 8 公司的c l e m e n t i n e 等。 与国外相比，国内对知识发现的研究稍晚。1 9 9 3 年国家自然科学基金开始对数据 2 中国科学技术大学博士学位论文 第1 章绪论 挖掘研究进行支持。1 9 9 9 年4 月在北京召开的第三届亚太地区k d d 国际会议( p a k d d 9 9 ) 响应热烈，收到论文1 5 8 篇。目前国内许多高校和科研单位在从事知识发现的基础理论 和应用研究，如北京系统工程研究所对模糊方法在知识发现中的应用研究，北京大学对 数据立方体的研究，中国科技大学、西安交通大学、华中理工大学、复旦大学、浙江大 学等也在从不同角度对知识发现进行研究。 1 2 知识发现的定义 在目前众多的有关知识发现的文献中，研究者们常常不加区别地使用知识发现和数 据挖掘( d a t am i n i n g ) 这两个术语。数据挖掘一词最早来自于统计学界，后来逐渐被 数据分析、管理信息系统和数据库界普遍采用；而知识发现一词则是在1 9 8 9 年的第一 届k d d 专题讨论会上被首次采用，这一术语强调了知识是数据发现的最终产品并很快在 人工智能和机器学习领域得到广泛采用。 知识发现领域知名学者f a y y a d 和p i a t e t s k y s h a p i r o 在文 f a y y a d ，1 9 9 6 中认 为，知识发现是从数据库中发现知识的整个过程，数据挖掘指的是此整个过程中的一个 特定的步骤。数据挖掘是从数据中提取模式的特定算法的应用，而在知识发现整个过程 中还包含了其它步骤，如数据预处理、数据选择、数据清洁、集成已有的知识、对挖掘 结果进行恰当的评价和解释等等，这些步骤对有效的知识发现过程来说是必不可少的。 1 2 1 基本定义 k d d 至今有多种定义，其中得到公认的是( f a y y a d ，1 9 9 6 ) ： 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 si st h en o n t r i v i a lp r o c e s so fi d e n t i f y i n g v a l i d ，n o v e l ，p o t e n t i a l l yu s e f u l ，a n du l t i m a t e l yu n d e r s t a n d a b l ep a t t e r n si n d a t a 数据库中知识发现是从数据中识别出有效的、新颖的、潜在有用的乃至最终可理解 的模式的非平凡过程。 在以上定义中： 数据：是指事实f ( 例如，数据库中的一条记录) 的集合，它是用来描述事物有关 方面的信息，是我们进一步发现知识的原材料。 模式