（计算机应用技术专业论文）基于领域知识的面向分类的属性泛化研究.pdf

基于领域知识的面向分类的属性泛化研究 摘要 数据规模的急剧增长使得数据挖掘越来越重要。当前的数据挖掘方法对数据的取 值基本上是单一层次的，而实际领域中数据的取值可能随着用户的任务需求而需要进 行适当的层次变换。由于现实中领域知识的丰富性及复杂性，可能有不同的层次变换 方向及取值可利用( 即多重多层次化变换m r m l ) ，而且不同取值与问题的相关性存在 较大差异。因此，本文针对这类具有多重多层次的属性泛化问题展开了研究。 论文的主要研究内容如下： ( 1 ) 详细地讨论了领域知识的各种不同的知识表示模型，探讨了由不同知识 表示模型表示的领域知识在知识发现过程各个阶段中的重要作用，展现了基于 领域知识的知识发现的应用前景及所面临的挑战。 ( 2 ) 描述了概念层次的基本概念以及表示方法，在此基础上，构建了多重多 层次属性泛化模型，表示了具体多种泛化路径的属性间的关系，并建立了基于 分类的泛化模型，用于控制属性层次变换。 ( 3 ) 在多重多层次属性泛化模型的基础上，提出一种基于m r m l 泛化关系 的分类规则泛化学习方法( c gd k ) ，该方法根据具体发现任务的需求和当前 实际数据库的内容，通过误分类率的控制，在挖掘的过程中选择最紧凑的泛化 层次和路径对属性进行泛化，以得到符合用户个性化要求的优化的分类规则。 ( 4 ) 在上述研究的基础上，构建了面向分类的多重多层次属性泛化原型系统 ( m r m lc g d k ) 。 关键词：数据挖掘领域知识多重多层次泛化分类 r e s e a r c ho fa t t r i b u t eg e n e r a l i z a f i o nt o w a r d sc l a s s i f i c a t i o n b a s e do nd o m a i nk n o w l e d g e a b s t r a c t d a t am i n i n gb e c o m em o r ea n dm o r ei m p o r t a n td u et ot h es h a r p l yi n c r e a s ei n d a t as c a l e n o w a d a y s ，d a t am i n i n gt e c h n i q u e sa l w a y su s eo r i g i n a ll e v e lo ft h ed a t a t om i n e ，h o w e v e r , t h ev a l u eo ft h ed a t ac a nb el e v e l e x c h a n g e da c c o r d i n gt ot h e c u s t o m e r sd e m a n d si nr e a la p p l i c a t i o n s b e c a u s eo ft h ea b u n d a n c ea n dc o m p l e x i t y i nt h er e a lf i e l d s ，m a n ya t t r i b u t e sh a v ed i f f e r e n tm e t h o d sa n dv a l u e st og e n e r a l i z e u n d e rd i f f e r e n tc o n d i t i o n s ( t h em u l t i r e l a t i o n a la n dm u l t i l e v e l ，m r m lf o rs h o r t ) ， a n dt h e r ei st r e m e n d o u sd i f f e r e n c eb e t w e e nd a t av a l u e sa n dt h er e l a t i v i t yo f p r o b l e m s t h e r e f o r e ，t h ep r o b l e mo fg e n e r a l i z a t i o nt o w a r d sm u l t i r e l a t i o n a la n d m u l t i - l e v e la t t r i b u t e si sr e s e a r c h e db yt h i sd i s s e r t a t i o n t h e o r g a n i z a t i o no ft h i sd i s s e r t a t i o ni sa sf o l l o w s ： ( 1 ) d i f f e r e n tk n o w l e d g er e p r e s e n t a t i o nm o d e l si nt h ef i e l do fd o m a i nk n o w l e d g ea r e d i s c u s s e di nd e t a i l t h es i g n i f i c a n tr o l eo fd o m a i nk n o w l e d g er e p r e s e n t e di nd i f f e r e n t m o d e l si nt h ep r o c e s so fd a t am i n i n gi sd i s c u s s e d t h ef u t u r ea p p l i c a t i o n sa n dc h a l l e n g e so f k n o w l e d g ed i s c o v e r i n g ，b a s e do nt h ed o m a i nk n o w l e d g e ，a r ee x h i b i t e d ( 2 ) b a s i cc o n c e p ta n dr e p r e s e n t a t i o no ft h ec o n c e p tl l i e r a r c h yi sd e s c r i b e d a n da m r m l g e n e r a l i z a t i o nm o d e li sc o n s t r u c t e dt oe x p r e s st h er e l a t i o no fa t t r i b u t e si ns p e c i f i c m u l t i g e n e r a l i z a t i o nw a y s ag e n e r a l i z a t i o nm o d e lf o rc l a s s i f i c a t i o n i sc o n s t r u c t e dt o c o n t r o ll e v e l e x c h a n g i n go fa t t r i b u t e s ( 3 ) ag e n e r a l i z a t i o nm e t h o df o ro b t a i n i n gc l a s s i f i c a t i o nr u l e s ( c g _ d k ) ，b a s e do n m r m l ，i sp r o p o s e d t h i sm e t h o dc h o o s e st h em o s tc o m p a c tg e n e r a l i z a t i o nl e v e la n dw a y t og e n e r a l i z et h ea t t r i b u t e sc o n t r o l l e db ym i s c l a s s i f i c a t i o nr a t i o t h i sm e t h o dc a no b t a i nt h e b e s tc l a s s i f i c a t i o nr u l e sa c c o r d i n gt ot h ei n d i v i d u a ld e m a n d s ( 4 ) b a s e do nt h ew o r ks t a t e da b o v e ，ap r o t o t y p es y s t e mw h i c hi sm u l t i r e l a t i o n a la n d m u l t i - l e v e la t t r i b u t e sg e n e r a l i z a t i o nt o w a r d sc l a s s i f i c a t i o ni si m p l e m e n t e d k e y w o r d s ：d a t am i n i n g ；d o m a i nk n o w l e d g e ；m u l t i r e l a t i o n a la n dm u l t i - l e v e l g e n e r a l i z a t i o n ；c l a s s i f i c a t i o n 插图清单 图1 1c r i s p d m 参考模型2 图2 1领域知识与知识发现过程中各环节的关系8 图2 2地域的概念层次示例1 0 图2 3属性价格的概念层次示例1 0 图3 1 概念层次示意图1 6 图3 2基于不同属性值个数的模式概念分层的自动产生2 0 图3 3行政区划示意图2 1 图3 4表3 3 表示的泛化关系格结构2 3 图5 1选择目标数据库3 7 图5 2选择目标数据表3 8 图5 3显示目标数据表与领域知识表3 8 图5 4不引入领域知识的运行结果截图3 9 图5 5使用c gd k 方法引入领域知识的运行结果截图3 9 v i 列表清单 表3 1属性a 的泛化映射上下文一2 2 表3 2某人的工作安排2 4 表3 3日期泛化关系2 4 表3 4时间泛化关系2 4 表3 5格中概念对应的具体内容2 4 表4 1算法c gd k 结果比较3 3 表4 2实验结果比较一3 4 v i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得 金理至些太堂 或其他教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名： 签字日期：汐孑年6 只f d 日 学位论文版权使用授权书 本学位论文作者完全了解金旦垦王些太堂有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权监 王些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：f 签字日期： p 潞卵一 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 彻肿 0 6 胡烈 轹 瑚 猁 阳 稚 字 j，t 鼢 签 脱1 护15 扬1 纱 致谢 三年的研究生生涯即将画上句号。这三年中让我得到的远不止是学习中的 进步，更主要的是让我感悟到很多为人处世的道理，以及老师、同学以及家人 朋友带来的温暖。 在论文完成之际，我要感谢我的胡学钢老师的热情关怀和悉心指导。胡老 师以其严谨求实的治学态度、高度的敬业精神、兢兢业业、孜孜以求的工作作 风和大胆创新的进取精神对我产生重要影响。在我撰写论文的过程中，胡老师 倾注了大量的心血和汗水，无论是在论文的选题、构思和资料的收集方面，还 是在论文的研究方法以及成文定稿方面，胡老师都始终给予我细心的指导和无 私的帮助，特别是他广博的学识、深厚的学术素养、严谨的治学精神和一丝不 苟的工作作风深深感染了我，使我学会了分析问题、解决问题的思维方法和许 多为人处事的道理。另外胡老师勤奋努力的工作态度、平易近人的生活态度也 是值得我终生学习的。在此，我要向胡老师表示真诚地感谢和深深的敬意。 同时我要感谢计算机与信息学院人工智能与数据挖掘实验室的老师们，特 别是张晶老师对我的帮助。感谢李培培、李笛、王翔、季钰、卫祥、王强在学 习、生活上对我的帮助，跟你们一起度过了愉快的三年，并且希望这样的友情 在10 年、2 0 年甚至更久以后依旧环绕在我们周围。感谢0 6 级与0 7 级的师弟 师妹们，感谢实验室每一个成员对我的关心和帮助! 我要衷心感谢我的家人，无论是顺境还是逆境总是默默的在我身边给我鼓 励，给我帮助。 最后，感谢计算机学院以及校研究生院老师们的辛勤工作，对所有给予我 关心和帮助的朋友们表示深深的谢意! i i i 作者：周循 2 0 0 8 年4 月 第1 章绪论 随着人类的发展和社会的进步，人工智能越来越受到人们的关注。并且随 着数据库规模的不断增大，数据库中的知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ，k d d ) 1 - 1 4 及其核心技术数据挖掘( d a t am i n i n g ) 3 也逐步受到重视。快 速增长的海量数据，远远超出了人类的理解能力。利用k d d 这种强有力的工 具，可以从海量的数据中挖掘出有效的、用户感兴趣的结果，对商务决策、知 识库、科学和医学研究做出巨大的贡献。本章主要介绍k d d 的发展和研究现 状，以及数据挖掘的研究和应用前景。 1 1 引言 随着数据库技术的普及，人类积累的数据量正在以指数速度增长，在这些 急剧增长的数据中包含着各个领域的有价值数据。然而，从如此大量的信息中， 获取我们有用的知识却变得越来越困难了。因此有效的利用和处理大量的数据 成为当前世界范围内所共同关心的问题，数据库中的知识发现( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ，k d d ) 及其核心技术数据挖掘( d a t am i n i n g ，d m ) 应运 而生。 1 2 数据挖掘 数据挖掘是数据库中知识发现的核心步骤。数据挖掘通过仔细分析大量数 据来解释有意义的新的关系、趋势和模式的过程。其出现于世纪8 0 年代后期， 使数据库研究中一个很有应用价值的新领域，是一门交叉性学科，融合了人工 智能、数据库技术、模式识别、机器学习、统计学和数据可视化等多个领域的 理论和技术。 1 2 1 数据挖掘的概念 数据挖掘产生于应用，且面向于应用。数据挖掘的交叉产业标准过程 ( c r o s s i n d u s t r ys t a n d a r dp r o c e s sf o rd a t am i n i n g ，c r i s p d m ) 是当今数据挖掘通 用流行的标准之一，是s p s s ( s t a t i s t i c a lp r o d u c ta n ds e r v i c es o l u t i o n s ，当时为 i n t e g r a l s o l u t i o n sl i m i t e d ，i s l ) 、n c r ( n a t i o n a lc a s hr e g i s t e r ) 和d a i m l e r c h r y s l e r ( 当时为d a i m l e r b e n z ) 3 家公司在1 9 9 6 年制定的，它强调的是在数据挖 掘中的应用，解决商业中存在的问题，而不是把数据挖掘局限在研究领域。 c r i s p d m 参考模型中包括：商业理解、数据准备、建立模型、模型评估和模 型发布，如图1 1 所示。 图1 1c r i s p d m 参考模型 数据挖掘的任务就是发现隐含的、事先未知数据中的潜在有用的模式。数 据挖掘的任务一般可以分为两类：描述型( d e s c r i p t i v e ) 和预测型( p r e d i c t i v e ) 。描 述型挖掘任务刻画数据库中数据的一般特性，而预测性挖掘任务则是在当前数 据上进行推断，以进行预测。具体来说，数据挖掘的基本任务主要有以下几种： 分类( c l a s s i f i c a t i o n ) 、预测( p r e d i c t i o n ) 、关联规则( a s s o c i a t i o nr u l e s ) 、序 列模式( s e q u e n t i a lp a t t e r n s ) 、聚类( c l u s t e r i n g ) 、偏离( d e v i a t i o n ) 。 数据挖掘常用的方法包括： 模糊( f u z z y ) 方法：美国控制论专家、数学家查德( z a d e h ) 于1 9 6 5 年发表的 论文模糊集合( f u z z ys e t s ) 2 3 1 ，标志着模糊数学这门学科的诞生。模糊集理 论以不确定性的事物为研究对象，是经典集合理论的扩展。 粗糙集( r o u g hs e t s ) 理论：粗糙集理论是由波兰华沙理工大学的z p a w l a k 教授于1 9 8 2 年提出的一种研究不完整、不确定知识和数据的表达、学习和归纳 的理论方法 2 4 1 ，现已成为d m k d d 研究中的最有力工具，也最有发展前途。 云( c l o u d ) 理论：云理论是李得益教授于1 9 9 5 年提出的用于处理不确定性 的一种新理论 2 5 1 。该理论把定性概念的模糊性和随机性完全集成到一起，构成 定性和定量相互间的映射，作为知识表示的基础【2 引。 证据理论( e v i d e n c et h e o r y ) ：证据理论又称d e m p s t e r s h a r e r 理论，是经典 概率论的扩充f 2 7 】。首先由d e m p s t e r 在2 0 世纪6 0 年代提出，在7 0 年代中期由 s h a r e r 进一步发展，形成处理不确定信息的证据理论。该理论的一个重要贡献 2 就是划清了不确定和不知的界限【2 8 1 。 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，a n n ) ：人工神经网络由多个神经元 按照某种方式相互连接形成，靠网络状态对外部输入信息的动态相应来处理信 息，网络的信息分布式存储于连接权系数中，使网络具有很强的容错性和鲁棒 性。神经网络的核心是结构和算法，例如以结构见长的h o p f i e l d 网络和一算法 见长的b p ( b a e kp r o p a g a t i o n ) 网【2 引。 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) ：遗传算法最先由j o h nh o l l a n d 于1 9 7 5 年提出 3 0 1 。其模拟生物的进化和遗传，借助于选择( s e l e c t i o n ) 、交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 操作，使要解决的问题从初始解逐步逼近最优解，解决了许多 全局优化问题。遗传算法易于并行，已广泛用于分类和优化问题。在数据挖掘 中，还可用于评估其他挖掘算法的适合度【3 。 归纳学习( i n d u c t i o nl e a r n i n g ) ：归纳学习是从大量的经验数据中归纳抽取出 一般的规则和模式，是一种重要的数据挖掘方法。归纳学习的算法大部分来自 于机器学习( m a c h i n el e a r n i n g ) 领域，其中最著名的是c 4 5 。针对数据概化( d a t a g e n e r a l i z a t i o n ) ，j h a n 提出了面向属性的归纳( a t t r i b u t eo r i e n t e di n d u c t i o n ， a o i ) t 32 1 。 1 2 2 分类的基本概念 分类是指将数据映射到预先定义好的群组或类。因为在分析测试数据之前， 类别就已经被确定了，所以分类通常被称作有指导学习。分类算法要求基于数 据属性值来定义类别。分类算法通常通过观察已知属性类别的数据的特征来描 述类别。 定义1 1 ：给定个由元组( 条目，记录) 组成的数据库d = t l ，t 2 9o ，t n ) 和 一个类别集合c = c l ，c 2 ，c m ) ，分类问题是指定义一个映射f ：d 一 c ，其中每个 元组t i 被分配到一个类中。一个类c j 精确地包含了被映射到其中的元组，即 c j = t i l f ( t i ) = c j ，1 i n ，且t i d ) 。 上述定义将分类视为一个从数据库到类别集合的映射。类别是预先定义的， 不重叠的，并且分割了整个数据库。数据库中的每个元组都被精确分配到某个 类中。对于一个分类问题的所有类别实际上是个等价类。 对于分类来说，没有一种技术总是优于其他的分类技术。每种技术都各有 优缺点。贝叶斯分类假设数据分布是独立的，并且具有离散的值。虽然它易于 使用和理解，但分类结果并不令人满意。决策树技术也易于理解，但它可能会 导致过拟合。 分类的主要问题是过拟合。如果分类策略精确的拟合训练数据，则它可能 不会很好地应用于更广泛的数据总体。缺失数据会导致分类产生问题。在分类 问题中的缺失数据于传统数据库中的空值是相似的。 1 2 3 数据挖掘涉及的问题及数据挖掘的未来 数据挖掘涉及许多重要的实现问题：人的作用、过拟合、异常点、结果的 解释、结果的可视化、大型数据库、高维、多媒体数据、缺失数据、不相关数 据、噪声数据、变化的数据、集成等。以上这些问题都是需要在设计数据挖掘 算法和产品时加以考虑和解决的。 在数据库系统的发展历程中，关系数据模型和结构化查询语言是两个里程 碑。目前数据挖掘还只是一个许多工具的集合，利用这些工具可以揭示出一些 隐藏在数据库中的信息。虽然在数据挖掘过程中有许多数据挖掘辅助工具，但 是还没有一个能够包括所有这些工具的模型或方法。估计过不了几年，不但会 出现一些界面友好的更加有效的算法，还会发展出一些相似的内容：算法、数 据模型和兴趣度。目前的数据挖掘工具不但需要人来定义需求，而且还要人来 解释结果。随着数据挖掘工具越来越完善，集成度越来越高，人的参与程度将 会降低。由于各种数据挖掘应用五花八门，所以迫切需要发展出一个全面的数 据挖掘模型。这方面主要的进展可能是一个复杂的“查询语言”的产生，它既包 括了传统的s q l 功能，同时也包括了一些更复杂的需求，这些需求在联机分析 处理( o n l i n ea n a l y t i cp r o c e s s i n g ，o l a p ) 和数据挖掘中经常用到。 数据挖掘语言或其它方面的标准化工作将有助于数据挖掘的系统化开发， 促进数据挖掘系统在企业和社会中的应用。数据挖掘国际会议( k d d ) 在2 0 0 0 年开始专门开辟标准专题讨论区。目前数据挖掘已经存在一些标准，包括数据 挖掘过程标准c r i s p d m ，预言模型交换标准p m m l 、m i c r o s o f t 的o l ed bf o r d a t am i n i n g 等，数据挖掘的标准化是该技术推广的必由之路【2 ，9 】，支持数据挖 掘标准的数据挖掘产品将拥有更广阔的市场和应用领域。 1 3 本文的课题来源和内容组织 1 3 1 本文的课题来源 安徽省自然科学基金课题( 编号0 5 0 4 2 0 2 0 7 ) 合肥工大科研发展基金课题( 编号0 5 0 5 0 4 f ) 1 3 2 本文内容的组织 本文由六章组成： 第一章主要简述知识发现产生的原因以及它的定义。描述了知识发现的 处理过程，介绍了经典的知识发现系统，并详细阐述了知识发现的核心技术 数据挖掘及其总体结构、挖掘的方法、知识表示的方法等。 第二章主要阐述领域知识的来源，以及领域知识在知识发现过程中各个 阶段不同的作用。介绍了领域知识常用的表示方法，以及每种表示方法对应于 4 知识挖掘的作用。最后综述了领域知识的研究现状及应用前景。 第三章详细描述了多重多层次关系的属性泛化。首先介绍了概念层次的基 本概念以及概念层次的应用，然后介绍了最常用的概念层次树。分析了概念层 次树存在的问题，详细阐述了多重多层次关系模型。 第四章介绍了a o i 及其改进算法，分析算法存在的问题。a o i 算法及其改 进算法都不能描述实际应用中存在的大量的复杂的属性间的关系多重多层 次关系( m r m l ) ，只能表示单一的泛化关系。考虑到实际存在的多重多层次属 性关系，提出了基于分类的多重多层次泛化算法c gd k ，并演示了算法。 第五章在基于分类的多重多层次属性泛化算法的研究上，设计并实现了 一个原型系统。 第六章全文的总结，对本文的主要研究工作进行简要的阐述和说明，并 对多重多层次关系属性泛化的研究工作中需要进一步解决的问题进行了探讨和 展望。 1 4 本章小结 由于人们急切需要将存在于数据库或其他信息仓库中的海量数据转化为有 用的知识，因而数据挖掘技术被认为是一个新兴的、非常重要的、具有广阔应 用前景和附有挑战性的研究领域，并引起了众多学科( 如数据库、人工智能、 统计学、数据仓库、在线分析处理、专家系统、数据可视化、高性能计算等) 研究者的广泛注意，而作为一个新兴学数据挖掘也是由上述众多学科相互交叉、 融会形成的，随着数据挖掘技术进一步发展，必然会带给用户更大的利益。 第2 章领域知识 数据规模的迅速增长要求数据挖掘能更有效地搜索与发现问题相关的数 据，使发现的模式更有意义。目前的知识发现算法大多是独立、无需领域知识 干预的发现，而在实际应用中，存储于用户或领域专家大脑中的或现有数据库 中的领域知识在知识发现中发挥着重要的作用。在知识发现过程中融入领域知 识已引起研究学者们的普遍关注，基于领域知识的知识发现已成为当前数据库 中知识发现的一个重要的研究方向。本章主要介绍领域知识的相关概念，详细 阐述领域知识常用的知识表示模型及其在知识发现过程各个阶段的重要作用， 综述领域知识的应用现状，并展望了有关研究和应用的前景。 2 1 引言 随着数据规模的不断扩大，从杂乱无章的数据中发现有用的知识变得越来 越困难。因此一些有用的，并不直接存在数据中但对知识发现可以产生积极影 响的信息逐渐受到人们的关注。目前，通用的知识发现算法没有考虑到应用领 域的特点和需求，是无需领域知识( d o m a i nk n o w l e d g e ) 的独立发现，既没有 发挥已有知识的作用，也没有对后续发现提供必要的积累。如果系统能够得到 并利用一定的领域知识，就可以用来提供系统自身的学习或发现能力，有目标 的进行知识发现。一方面可以提高挖掘效率，另一方面可以提高发现模式或结 果的兴趣度。因此，领域知识具有重要的研究和应用意义。 2 2 领域知识的基本概念 2 2 1 领域知识的定义 知识发现的重点之一在于有效运用领域知识。对于大型数据库而言，彻底 而详尽的搜索数据库以发现新的关系是不切实际的。除非领域专家或一种自动 的发现工具能够引导数据分析和知识发现过程，否则不可能成功发现有趣的、 新颖的信息。对于领域知识的定义，众多研究学者根据各自的理解，给出了很 多定义，但是较为常用的有以下三种： a d d i t i o n a lk n o w l e d g ei so f t e nu s e dt og u i d ea n dc o n s t r a i nt h es e a r c hf o r i n t e r e s t i n gk n o w l e d g e w er e f e rt ot h i sf o r mo fi n f o r m a t i o na sd o m a i nk n o w l e d g e o rb a c k g r o u n dk n o w l e d g e ”【1 , 3 1 】即在知识发现系统中，把加入的那些有关引导和 限制搜索感兴趣知识的知识称为背景知识或领域知识。 w ed e f i n ed o m a i nk n o w l e d g et om e a ni n f o r m a t i o na b o u tt h ei m p o r t a n tt o p i c s 6 o rc o n c e p t si nap a r t i c u l a rd o m a i na n dh o wt h e yr e l a t et oe a c ho t h e r 【3 3 】即将领域 知识定义为专门领域的重要问题或概念和这些问题和概念之间的相互关系3 4 1 。 d o m a i no rb a c k g r o u n dk n o w l e d g ec a nb ed e f i n e da sa n yi n f o r m a t i o nt h a ti s n o te x p l i c i t l yp r e s e n t e di nt h ed a t a b a s e 【3 5 , 3 6 1 即领域知识被定义为在数据库中没 有明确表达的信息 3 7 1 。 2 2 2 领域知识的来源 在领域知识的众多来源中，数据字典是领域知识最基本的形式。数据字典 中典型的信息包括：属性之间的关系( 函数依赖，f u n c t i o n a ld e p e n d e n c y , f d ) ， 属性的类型、大小、名称，每个属性的含义、格式、约束，属性的域，使用统 计，映射定义等。然而，一般来说，领域知识更为常见的是领域专家提供的， 表示数据库中一些属性的相关知识【l ，3 引。 从狭义方面理解，领域知识是关于应用领域的知识，然而我们在求解问题 的时候往往还会用到领域之外的一些背景知识，如常识，它们之间紧密联系， 有时还可以相互转换，在现有的研究中，往往并不将它们严格的加以区分，因 而在我们的定义里领域知识也是指广义上的，可以是常识、可以是关于应用领 域的知识、可以数据字典中的约束、也可以是用户或领域专家的指导，即所有 对问题求解有用的知识都称作是领域知识。这些不同的领域知识类型，它们所 适用的知识表示模型各不相同，基于各种不同知识表示模型所表示的领域知识 在知识发现过程各个阶段中的作用也各不相同，加上领域本身的复杂性，因而 基于领域知识的知识发现研究尚处于初级阶段。 2 3 领域知识在知识发现中的作用 从数据挖掘的本质上看，数据挖掘是完全由数据驱动的，然而完全依赖数 据本身提供的信息进行知识发现往往执行效率低下、且发现到的知识也无法满 足用户的需求，产生大量低层次的、无关的、冗余的规则。因此需要结合人的 操作控制。从理论上说，结合领域知识的知识发现实在操作者的主动参与下进 行知识发现的过程。领域知识可以结合到知识发现过程的各个环节中，两者的 关系如图2 1 所示。 7 图2 1 领域知识与知识发现过程中各环节的关系 2 3 1 领域知识在数据选择中的作用 数据选择的目的是辨别出需要分析的数据集合，缩小处理范围，提高知识 发现的质量。对于不同的数据的选择，不仅依赖于知识发现要求本身以及一些 通用的知识，而且更应该依赖于知识发现算法所应用的具体领域的专家经验和 知识，针对一种知识发现算法的具体应用领域定制数据源。 2 3 2 领域知识在数据预处理中的作用 现实世界的数据库中存在大量，不完整的、含噪音的和不一致的数据，在 数据挖掘之前，对这些数据进行预处理，可以大大提高数据挖掘的质量，降低 唉际挖掘所需要的时间。通过在预处理阶段结合领域知识，可以更有效的清洗 原数据集中的“脏”数据和噪音数据，补充其中被丢失的数据，将多个异地、 异构的数据集转换成为数据挖掘所需的数据源的形式，使数据挖掘在比较规范 的数据源中进行。 2 3 3 领域知识在数据转换阶段的作用 数据转换阶段主要工作是找到数据的特征表示，用维变换或转换方法减少 有效变量的数目或指导数据的不变式。 2 3 4 领域知识在数据挖掘阶段的作用 领域知识在知识发现过程中，尤其是数据挖掘阶段起到非常重要的作用。 在数据挖掘阶段应用领域知识，可以引导模型搜索、知识选择与算法选择，使 求解结果符合用户的需要，避免由通用挖掘方法所带来的大量与用户无关的知 识，从而可以提高挖掘效率、质量和在特定领域发现知识的针对性。具体来说， 首先，根据用户要求确定k d d 发现的知识类型，即确定数据挖掘的目标。因 为对k d d 的要求不同，会在具体的知识发现过程中采用不同的数据挖掘算法。 接着，选择合适的数据挖掘算法或工具，包括选取合适的模型和参数，并使得 挖掘算法与整个k d d 的评判标准相一致。另外，在进行发现型数据挖掘或验 证型数据挖掘的过程中，可以使用领域知识提供的信息对查询进行优化。 2 3 5 领域知识在模式解释评价阶段的作用 这个阶段的主要任务就是根据最终用户的决策目的对提取的信息进行分 析，把最有价值的信息区分出来，并且通过决策知识工具提交给决策者，因此 这一步骤的任务不仅是把结果表达出来，还要对信息进行过滤处理，如果不能 令决策者满意，还需要重复以上数据挖掘过程。因此，解释评价的手段和方法 直接和用户相关。有效的领域知识融入将使得这一阶段得到相应的支撑和辅助， 指导搜索，评估结果模式的兴趣度，使得结果更有效、更符合用户需要。 2 3 6 领域知识的反馈 通过知识发现过程所得到的知识是对其数据源的高度概括，是对隐藏在数 据源内部的知识的一种形式化描述，与领域专家的经验知识相比，这种知识它 来自实际数据，因而更具客观性。因而这种类型知识可以反馈到原来的知识库 中，或直接作为领域知识，或作为修正知识更新原来领域知识中的内容。通过 领域知识的这种反馈，可以不断地充实知识库，丰富已有知识库的内容，使知 识源源不断得到积累和更有效的利用。 2 4 常用的领域知识的表示方法 在数据挖掘过程中，针对不同的知识发现任务，存在相应的知识发现算法， 而不同知识发现算法所依赖的知识表示形式都不尽相同。为提高数据处理的效 率、简化数据操作过程、改善发现知识质量，都需要适当的知识表示方式，基 于一定知识表示模型的基础上进行知识发现。领域知识为满足不同的挖掘需求 同样可以采用不同的表示模型。下面主要介绍几种常用的领域知识的表示方法。 2 4 1 概念层次树与属性归纳算法 数据库中的数据及对象在基本概念层次中包含了许多细节性的数据信息， 对这些数据进行更高层次的抽象提供更为精练的描述是非常重要的。概念层次 是一种典型的领域知识类型。 如图2 2 所示为一个地域的概念层次。其中城市值包括v a n c o u v e r ，t o r o n t o ， n e wy o r k 和c h i c a g o 。然而，每个城市可以映射到他所属的省或州。例如， v a n c o u v e r 可以映射到b r i t i s hc o l u m b i a ，而c h i c a g o 映射到i l l i n o i s 。这些省和 州可以映射到它所属的国家，如加拿大或美国。 9 图2 2 地域的概念层次示例 概念层次也可以通过给定维或属性的值离散化或分组来定义。可以在值组 之间定义全序或偏序。集合分组概念层次的一个例子如图2 3 所示关于价格的 集合分组概念层次。其中，区间( $ x s y 表示由s x ( 不包括) 要i l j $ y ( 包括) 。 对于一个给定的属性，根据不同的用户视图，可能有多个概念层次。例如 用户可能愿意用i n e x p e n s i v e ，m o d e r a t e l yp r i c e d 和e x p e n s i v e 的定义范围来组织 价格。 概念层次定义为一个映射序列，将低层概念映射到更一般的高层概念。它 使得原始数据可以在较高的、泛化的抽象层次上进行。当某个属性 图2 3 属性价格的概念层次不例 值过多、过细，而挖掘过程又要求该属性值“浓缩 或者需要对数据集进 行汇总时，就可以依据对应的概念层次，对属性值进行概念提升，使之提升到 理想的层次。数据的泛化可以通过用较高层概念替换较低层概念来实现。从而 压缩数据规模，挖掘出用户更感兴趣的知识。 概念层次树是以树的形式表示概念之间的层次关系，提供了有关数据整体 的简洁清晰的描述，在整个树型的层次关系中，越往上，层次越高，粒度越大， 1 0 而越往下，层次越低，粒度越小。不同的用户常常会需要基于一定的主观和客 观标准从不同角度或不同的抽象水平进行概念描述，这里客观标准一般指描述 的简洁性及其所涵盖的范围，而主观标准则与用户的背景知识以及该应用领域 的一些信息有关。 2 4 2 领域知识的产生式表示 形式上，领域知识可以表示成x j y ( x 蕴含y ) ，其中x 和y 是数据库 中属性的简单谓词或合取谓词。设d k 是数据库中所有能获得的领域知识的集 合。定义d k 的闭合d k + ： d k + - - d k u d d k ild d k i 可由d k 推出 ) 随着数据库规模的急剧增长，在数据库中搜索所有可能的关系是n p - h a r d 问题 1 0 , 1 1 】。事实上，有些数据库的规模非常的大，即使使用最快的知识发现算 法，当应用于所有的数据时，开销也是极其巨大的。结构稍差的查询在如此庞 大的数据量上进行搜索将会非常困难，或者根本就无法获得所需要的信息。最 大程度地限制搜索空间可以使用如下三种方法：第一种，通过估计哪些属性不 参与发现过程来削减数据集中属性集的大小；第二种，对数据集进行抽样，在 数据集的一个随机样本中使用知识发现算法，然而，由于样本的代表性问题， 从样本中发现的规则与从完整的数据集合上发现的规则可能会存在不同，甚至 有偏差：第三种，使用额外的信息一一领域知识，用于引导并限制搜索，以发 现其它有趣的知识。 一个知识发现系统必须要有关于数据的形式以及相关数据约束之类的领域 知识加以引导。包含在数据库中的领域知识、特定发现问题的上下文、知识发 现的目的等都可以用于引导并限制搜索空间，从而在数据库中发现有趣的知识。 在知识发现中，以产生式表示的领域知识可以用于削减要搜索的数据库的规模； 优化假设( 该假设表示将要被发现的有趣知识) ；优化用于证明假设的查询；检 验已发现知识的正确性和精确性 1 0 , 1 1 】。 2 4 3 领域知识的本体描述 本体( o n t o l o g y ) 是一个哲学上的概念，用于描述事物的本质。近年来本体论 逐渐被引入计算机领域，用于知识表达、共享及重用。本体是一种能在语义和 知识层次上描述系统的概念模型，其目的在于以一种通用的方式来获取领域中 的知识，提供对领域中的概念的共同一致的理解，从而实现知识在不同的应用 程序和组织之间的共享和重用。较为通用的说法是，本体是某领域内概念的显 式说明，即把现实世界中的某个领域抽象成一组概念( 如实体、属性等) 以及 概念之间的关系，构造出这个领域的本体，从而使计算机对该领域的信息处理 大为方便 38 1 。 目前一个较为通用中的定义是：本体是某领域内概念的显式说明，即把现 实世界中的某个领域抽象成一组概念( 如实体、属性、进程等) 及概念间的关系， 一个领域本体将可能提高计算机在该领域内的自动化信息处理水平【4 。 根据本体的概念主题一般可以分为领域本体、通用本体、表示本体、任务 本体【3 9 1 ；根据本体的形式化程度分为高度非形式化本体、非形式化本体、办形 式化本体、严格形式化本体【4 0 1 。 在信息检索方面，本体的基本思想是：先建立相关领域的本体，根据本体 对收集的信息进行标注，用户的检索请求按本体转换成规定的格式，在本体的 帮助下匹配出符合条件的数据集合返回给用户。 在信息集成方面，自顶向下的基本思想是：先建立相关领域的本体，然后 由该本体来统一底层各信息源的语义。自底向上方法是先提取底层各信息源的 局部数据模式，再在局部数据模式上抽取局部概念模式，最后在局部概念模式 上构造全局概念模式【4 2 1 。 在机器翻译方面，通过把某种语言中的词汇映射到本体中的概念，可以支 持在源语言分析时进行歧义消解和目标语言生成时的词汇选择，并可以作为源 语言和目标语言的中间表示的概念来源【4 3 1 。 本体建模是根据应用需求，建立领域概念及其联系的过程。实际应用中可 采用自上而下的方式进行本体建模分析，即首先考虑用户所关心的对象类别， 然后逐一考虑描述这种对象所依赖的概念。本体建模原则是领域知识建模的指 导性原则。领域知识建模是对知识所包含的内容进行简练、概要描述，通常由 两部分组成：单多领域模式和单多领域知识库。 2 4 4 领域知识的概念网络表示 概念网络( c o n n e t ) 是中国科学院自动化研究所互联网研究发展中心在理论 和实践的基础上对人工智能研究的一种探索。它从认知心理学的角度揭示了思 维活动的基础结构，提出了思维活动的心理模型假说。概念网络将概念作为意 义的基本表达单元( 概念可以是词或短语) ，依靠概念之间的各种