（管理科学与工程专业论文）基于cbr的知识发现方法研究.pdf

基于c b r 的知识发现方法研究 摘要 知谈发现是当今瀣蹶静具有广瓣痤震嚣景匏研究领域 是人工整戆 统诗喾 机器学习 数据库等移领域相互交叉的研究方向 帮助人们鼹好地利用套种数 据源 为做出正确的决饿而服务 其中基于范例推理 c a s e b a s e dr e a s o n i n gc b r 是知识发现研究中的黧蔡内容 c b r 是由目标辩例的提示丽彳罨到记忆中的源范 爨 并囊滚菝夔亲撂磐霆据范锈求辫豹一静策滔 萁痘蘑笾溪霾趋广泛 党其 在知识不随定义和缺麓专家知识的领域 应用起来效果很好 本文在对知识发现和范例推理技术研究的基础上 在以下几个方面进行了深 入的研究 i 综述了范镄疼鹃建立亵维护知识 范饲露上镌翔谖发税豹鼙耩 步骤 主要方法以及基于知识发现技术的c b r 系统等相关内容 2 提出基于c b r 的知识发现算法模型 该模型包括四个计算模块 分别用 来确定鬓瞧秘极重 簿鬣范倒之藏滋性主浆攘戗瞧 诗算耨 霞范夔之藩豹鞭 离 最终确定出目标藏铡可能属予鼢范铡库和该藏例库中与玛标范铡最为栩似 的范例 3 将旗于c b r 的知识发现算法模型应用于实际人力资源数据分辑 以合肥 菜企盘昃王酝鲎生淫藤麓戆赣关数攥为鸷景 建交蚕工工终态度裹 中 蔻等 范例库 并在这三个范例库中应用靛立的知识发观算法模型避行分析 验 c 藏了 该模型在宓际应用中的可能性 关键词 躲识发现 基于范铡接理 范镄痒 稳经往算法 r e s e a r c ho fk d dm e t h o db a s e do i lc b r a b s t r a c t k d d k n o w l c d g ed i s c o v e r yi nd a t a b a s e i saf i e l do fr e s e a r c hw h oh a sb r o a d p o s s i b i l i t i e s i ti s ac r o s s i n gr e s e a r c hw i t ha i s t a t i s t i c s m a c h i n ei g a m i n ga n d d a t a b a s e k d dh e l p sp e o p l et ou s ea l lk i n d so fd a t e sw e l la n dt om a k e r i g h td e c i s i o n c b r c a s e b a s e dr e a s o n i n g i sa ni m p o r t a n tc o n t e n ti nk d d c b rc a nu s et h ec u e o ft a r g e tc a s et of i n dt h eb a s ec a s e a n dg e tt h es o l u t i o nu n d e rt h eg u i d a n c eo ft h e b a s ec a s e a tt h ep r e s e n tt i m e c b ri sw i l d l yu s e di nm a n yf i l e d e s p e c i a l l yi nt h e f i e l dw h i c hi ss h o r to fk n o w l e d g e t h i sp a p e rm a k e sad e e ps t u d yi nk d d c b ra n dt h e s ep r o b l e m sa sf o l l o w s 1 g i v e sa no v e r v i e wo ft h eb u i l d i n ga n dm a i n t e n a n c eo ft h ec a s eb a s e i n t r o d u c e st h ea i m t h ep r o c e s s t h em a i nm e 也o d so fk d ca n dac b r s y s t e mb a s e d o n k d d 2 s e t su pa na l g o r i t h mm o d e l t h r o u g ht h ef o u rp a r t so ft h i sm o d e l t h ep a p e r c a ng e tt h ea t t r i b u t e s w e i g h i n g t h ed i s t a n c eb e t w e e nn e wa n do l dc a s e s a n df i n a l l y f i n dt h ec a s eb a s ea n dt h eb a s ec a s e st h a tm o s ts i m i l a rw i t ht h e t a r g e tc a s e 3 p u t st h em o d e li n t ou s eo ft h ed a t aa n a l y s i so fh u m a nr e s o u r c e u n d e rt h e d a t eo ft h ew o r k e r s l i f eq u a l i t yi na l le n t e r p r i s e t h ep a p e rs e t su pt h r e ec a s eb a s e s a b o u tw o r k i n ga t t i t u d e u s e st h em o d e lt o a n a l y z et h ed a t e sa n dt e s tt h em o d e l p o s s i b i l i t yi np r a c t i c eu s e k e yw o r d s k n o w l e d g ed i s c o v e r yi nd a t a b a s ek d d c a s e b a s e dr e a s o n i n gc b r c a s e b a s e s i m i l a r i t ym e a s u r e s 插图清单 图1 1k d d 过程示意图 图2 1c b r 工作原理 图3 1 c b r 的完整应用系统框架图 图3 2 基于知识发现技术的c b r 系统 图4 1 模型结构 一 图4 2 四个模块之间的关系 i h 加巧巧s 拍 表格清单 表5 1 特征属性的缀成 3 8 表5 2 濑例库各属性的取值范围 3 9 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果 据我所知 除了文中特别加以标注和致谢的地方外 论文中不包含其他人已经发表或撰写 过的研究成果 也不包含为获得 盒蟹王些太堂或其他教育机构的学位或证书而使 用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意 学位做作者签名 办l 畸畸 签字日期 嘭年彳月尹旧 学位论文版权使用授权书 本学位论文作者完全了解金妲王些友堂有关保留 使用学位论文的规定 有权保留 并向国家有关部门或机构送交论文的复印件和磁盘 允许论文被查阅和借阅 本人授权 金 罡王些盔堂可以将学位论文的全部或部分内容编入有关数据库进行检索 可以采用影印 缩印或扫描等复制手段保存 汇编学位论文 保密的学位论文在解密后适用本授权书 学位论文作者签名 刮畴畸 签字日期 湖挣6 月缈日 学位论文作者毕业后去向 工作单位 通讯地址 导师签名 签字日期 阳气户乡月乒日 电话 邮编 致谢 写完这篇论文 我也将离开熟悉的校园 三年的研究生生话中有许多老师 和同学给予我多方面的支持和帮助 在此一一致谢 首先我想感谢我的父母 在我整整十九年的求学生涯中 是他们给了我最 无私的鼓励与支持 也是他们教会了我乐观 认真地去面对生活 非常感谢我的导师梁昌勇教授 粱老师知识渊博 思路开阔 善于接受新 事物 在这三年的学习生活中 他教会了我作研究的基本方法 以及从大处入 手 全局把握的能力 而且梁老师还为我创造了很多成长的机会和独立的空间 鼓励我在学术上创新思维 让我得以在一个自由宽松的环境中进行学习和研究 梁老师还教会了我很多为人处世的道理 更让我终身受益 同时 我很感谢蒋翠清老师 在课题的研究中 他认真治学的态度和严谨 的学术作风影响着整个研究所的成员 在论文写作的过程中 他富有建设性的 意见给了我许多启发 感谢信息技术与工程管理研究所的俞家文 丁勇 陆文星等老师以及陈增 明 张俊岭 吴坚等博士对我的帮助与指导 我还要感谢在学习和生活中给了我很多关心与帮助的同龄人 张点 冯珍 赵艳霞 杨晖 郑崧 朱鹏 沈磊等 谢谢他们在三年中给我的每一份支持和 感动 作者 刘婷婷 2 0 0 6 年5 月1 5 日 第一章绪论 1 1 引言 随着政府 企业信息系统应用不断深入和时间的积累 政府和企业的信息 资源不断积聚 如何利用这些资源提高决策的有效性 成为人们研究的重点 知识发现是利用这些资源的重要方法 是目前活跃的具有广阔应用前景的研究 领域 是一门多领域相互交叉的学科 在当前数据量急剧增长的知识经济时代 人们需要从中发现出有价值的潜藏信息 从而更好地利用各种数据源 为做出 正确的决策服务 近年来 基于范例推理的研究及其系统的开发受到人们的普遍关注 c b r 简单而研究是从记忆中检索出与新问题相似的经验 根据新情况的具体背景 部分或全部复用旧的经验 必要时作相应的适应性修改 并在记忆中保存新的 经验 实现动态学习 c b r 不仅是关于人类认知的心理学理论 而且将成为智 能计算机系统技术新的基石之一 c b r 在企业管理决策 法律案例分析 系统 规划与设计等多方面具有巨大的潜力和广阔应用前景 因为c b r 提供了各种决 策方案的典型案例 为决策者做出正确决策提供了帮助 为决策实施起示范和 指导作用 也能帮助决策者发现自身问题 避免类似错误 从而大幅度提高了 决策质量和水平 基于范例推理技术作为知识发现的一个重要方法 以其获取知识过程简单 容易 维护知识方便等特点 受到知识专家的青睐 尤其是近年来 随着对c b r 的研究兴趣逐渐增大 法律 烹饪 医学 故障诊断 设计和规划 管理辅助 决策等领域得到了广泛的应用 因此 应用c b r 来挖掘知识 在科研和应用方 面都有重要意义 知识库和范例库的建立 为实现基于c b r 的知识发现的实现 提高知识发现的效率起了重要作用 本章作为绪论 首先回顾了知识发现定义 过程 任务和分类 基于c b r 的知识发现的研究现状和c b r 在知识发现中的应用及特点 提出了本文的研究 意义 最后给出本文的主要工作和内容安排 1 2 知识发现的概念及内涵 1 2 1 i d d 的定义 k d d 这一概念自1 9 8 9 年出现以来 其定义几经变动 最新的描述性定义 是由u s a m am f a y y y a d 等给出的吣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 ei 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 gv 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 nd a t a 其中 数据集 一个有关事实f 的集合 如学生档案管理数据库中有关学生基本 情况的各条记录 它用来描述事物有关方面的信息 是我们进 步发现知识的 原材料 有效 体现在发现知识的模式对于新的数据仍保持有一定的可信度 否则 k d d 就没有任何实际意义 新颖性 要求发现的模式必须是新的 至少对于系统来说应该如此 模式 是否新颖可以通过两个途径来衡量 其一是通过当前得到的数据和以前的数据 或期望得到的数据之间的比较来判断该模式的新颖程度 其二是通过其内部所 包含的知识 通过对比发现的模式与已有的模式来判断 通常我们可以用一个 函数来表示模式的新颖程度 佃 该函数的返回值是逻辑值或是对模式e 的新颖程度的一个判断数值 潜在有用性 提取出的模式或是发现的知识在将来有实际效用 如用于决 策支持系统里可提高经济效益 用u 表示模式e 的有作用程度 u u e f 1 可理解性 发现的模式能够被用户理解 知识发现的一个目标就是将数据 库中隐含的模式以容易被人理解的形式表现出来 从而帮助人们更好地了解数 据库所包含的信息 当然一个模式是否容易被人理解 这本身就很难衡量 比 较常用的方法是对其简单程度进行衡量 模式 一个用语言l 来表示的一个表达式e 它可用来描述数据集f 的某 个子集f e e 作为一个模式要求它比数据子集f e 的枚举要简单 所用的描述 信息量要少 如 成绩在8 1 到9 0 之间 则成绩优良 可称为一个模式 而 如 果成绩为8 1 8 2 8 3 8 4 8 5 8 6 8 7 8 8 8 9 或9 0 则成绩优良 就不能称 之为一个模式 对大量数据进行分析的过程 包括数据准备 模式搜索 知识评价 以及 反复的修改求精 是一个非平凡的过程 意思是它要求一定程度的智能性 自 动性 即无需人工干涉 1 2 2 k d d 的过程 k d d 过程可粗略得理解为三部分 数据准备f d a t ap r e p a r a t i o n 数据挖掘 d a t am i n i n g 以及结果的解释评估 h l t e r p r e t a t i o na n de v a l u a t i o n 1 3 6 1 2 m 知识 隅霉岘 毒 l口i i 融哆l j 匀一一 选多曰u 臼 日l i 图1 1k d d 过程示意图 1 数据准备阶段 数据准备又可分为三个子步骤 数据选择 d a t as e l e c t i o n 数据预处理 d a t a p r e p r o c e s s i n g 年l l 数据变换 d a t at r a n s f o r m a t i o n 数据选择的目的是确定发现任 务的操作对象 即目标数据 t a r g e t d a t a 它是根据用户的需要从原始数据库中 抽取的与k d d 相关的数据 在此过程中 会利用一些数据库操作对数据进行处 理 数据预处理是对数据选择阶段的数据进行再加工 一般包括消除噪声 推 导计算缺值数据 消除重复记录 完成数据类型转换 如把连续值数据转换为 离散型的数据 或是把离散型的转换为连续值型的 等 数据变换的主要目的 是消减数据维数或降维 d i m e n s i o nr e d u c t i o n 即从初始特征中找出真正有用的 特征以减少数据挖掘时要考虑的特征或变量个数 2 数据挖掘阶段 数据挖掘阶段首先要确定挖掘的任务或目的是什么 如数据总结 分类 聚类 关联规则发现或序列模式发现等 确定了挖掘任务后 就要决定使用什 么样的挖掘算法 同样的任务可以用不同的算法来实现 选择实现算法有两个 考虑因素 一是不同的数据有不同的特点 因此需要用与之相关的算法来挖掘 二是用户实际运行系统的要求 有的用户可能希望获取描述型的 d e s c r i p t i v e 容易理解的知识 而有的用户或系统的目的是获取预测准确度尽可能高的预测 型 p r e d i c t i v e 知识 完成了上述准备工作后 就可以实施数据挖掘操作了 数据挖掘算法是 k d d 的核心 也是目前研究人员主要努力的方向 但要获得好的挖掘效果 还 必须对各种挖掘算法的要求或前提假设有充分的理解 3 结果解释和评估 对发现的模式进行解释 在数据挖掘阶段发现出来的模式 经过用户或机 器的评估 可能存在冗余或无关的模式 甚至会出现一定的偏差 这时需要将 其剔除 也有可能模式不满足用户要求 这时则需要整个发现过程退回到发现 阶段之前 如重新选取数据 采用新的数据变换方法 设定新的数据挖掘参数 值 甚至换一种挖掘算法 另外 k d d 由于最终是面向人类用户的 因此可能 要对发现的模式进行可视化 或者把结果转换为用户易懂的另一种表示 如把 分类决策树转换为 i f i t h e n 规则 或者采用可视化技术以图形的方式来表示最后 结果 使其更加生动直观 可见整个发现过程不是步骤之间包含了循环和反复 这样 可以对所发现 的知识不断深化和求精 并使其便于理解 1 2 3 i o d 的分类 知识发现的分类从不同的角度可以得到不同的分类标准 常见的有以下分类 标准 挖掘对象 挖掘任务 挖掘方法和挖掘应用 6 8 1 根据挖掘对象分类 不同的数据库在数据的描述 组织和存储方式上均有很大不同 一般有关 系数据库 面向对象数据库 空间数据库 时态数据库 事务数据库 多媒体 数据库 异质数据库 遗产数据库以及环球网w e b 等等 因此数据挖掘可以按 照数据库的不同划分成不同种类 如从关系数据库挖掘知识的关系数据挖掘 是使用最广泛的一类数据挖掘技术 2 根据挖掘任务分类 通常知识发现的任务主要是发现下列五类知识 9 广义型知识 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 c l u s t e r i n 酌 反映同类事物共同性质的特征型知 识和不同事物之间差异型特征知识 用于反映数据的汇聚模式或根据对象的属 性区分其所属类别 关联型知识 a s s o c i a t i o n 反映一个事件和其它事件之间依赖或关联的知 识 又称依赖 d e p e n d e n c y 关系 这类知识可用于数据库中的归一化 查询优化 等 预测型知识 p r e d i c t i o n 通过时间序列型数据 由历史的和当前的数据去 预测未来的情况 它实际上是一种以时间为关键属性的关联知识 偏差型知识 d e v i a t i o n 通过分析标准类以外的特例 数据聚类外的离群值 实际观测值和系统预测值间的显著差别 来对差异和极端特例进行描述 同时这些知识也可以在不同的层面上表达 如 泛化知识 原始知识 多 层次知识等等 一个优秀的知识发现算法应该能全面完整的挖掘出隐含在不同 层面内的不同种类的知识 6 j 3 根据挖掘方法分类 4 根据挖掘方法可粗略地分为 机器学习方法 统计方法 神经网络方法和 数据库方法 机器学习中可细分为 决策树 规则归纳等 范例推理 遗传算 法等 统计方法中可细分为 回归分析 多元回归 自回归等 判别分析 贝 叶斯判别 费歇尔判别 非参数判别等 聚类分析 系统聚类 动态聚类等 以及探索性分析 主元分析法 相关分析法等 等 神经网络方法中可细分为 前向神经网络 b p 算法等 自组织神经网络 自组织特征映射 竞争学习等 等 数据库方法主要是多维数据分析或o l a p 方法 另外还有面向属性的归纳 方法 4 根据挖掘应用分类 不同的挖掘方法或系统往往更适合某一特定的领域 而在其他领域则不太 适应 因此 数据挖掘可根据其应用领域来分类 如 商业 电信 生物 医 疗 工业 农业等 不同的应用领域通常需要集成某些特定的挖掘方法 一般 很难设计一个通用的 有效的 适应于各个领域的知识挖掘系统 1 2 4k d d 的特点 k d d 就是利用机器学习的方法从数据库中提取有价值知识的过程 是数据 库技术和机器学习两个学科的交叉学科 数据库技术侧重于对数据存储处理的 高效率方法的研究 而机器学习则侧重于设计新的方法从数据中提取知识 k d d 利用数据库技术对数据进行前端处理 而利用机器学习方法则从处理后的数据 中提取有用的知识 k d d 与其他学科也有很强的联系 如统计学 数学和可视 化技术等等 z j k d d 使用的数据来自于实际的数据库 所要处理的数据量可能很大 因此 k d d 中的学习算法的效率和可扩充性就显的尤为重要 此外 k d d 所处理的 数据由于来自于现实世界 数据的完整性 一致性和正确性都很难保证 如何 将这些数据加工成学习算法可以接收的数据也需要进行深入的研究 再者 k d d 可以利用目前数据库技术所取得的研究成果来加快学习过程 提高学习的效率 另外 由于k d d 处理的数据来自于实际的数据库 而与这些数据库数据有关的 还有其他一些背景知识 这些背景知识的合理运用也会提高学习算法的效率 最后 k d d 是对数据背后隐藏的特征和趋势进行分析 最终给出关于数据的总体 特征和发展趋势1 2 o 1 3 基于c b r 的知识发现的研究现状 1 3 1 基于范例推理技术 基于范例推理 c a s e b a s e dr e a s o n i n g c b r 是人工智能领域中较新崛起的 一种重要的基于知识的问题求解和学习方法 人们为了解决一个新问题 先是 进行回忆 从记忆中找到一个与新问题相似的范例 然后把该范例中的有关信 5 息和知识复用到新问题的求解之中 以医生看病为例 在他对某个病人做了各 种检查之后 会想到以前看过的病人的情况 找出几个重要症状上相似的病人 参考那些病人的诊断和治疗方案 用于眼前的这个病人 c b r 起源于美国耶鲁大学r o g e rs c h a n k 教授在其1 9 8 2 年的著作 动态回 忆 d y n a m i cm e m o r y 中所做的描述 s c h a n k 教授提出的以记忆组织包 m e m o r y o r g a n i z a t i o np a c k e t s 为核心的动态记忆理论 d y n a m i cm e m o r yt h e o r y 1 1 0 1 被认 为是人工智能领域中最早的关于c b r 的思想 s c h a n k 教授的早期思想被他的学 生所推广 另一类相对独立的研究 如类比推理研究 哲学和心理学研究中的 概念形式理论及问题求解和经验学习理论 也对早期的c b r 思想产生影响 1 9 8 3 年 s c h a n k 的学生j a n e tk o l o d n e r 领导开发了第一个基于事例的推理 系统 c y r u s 实现了s c h a n k 著作中的很多思想 并于1 9 8 5 年在其文献中 首次使用了c b r 这一术语 为c b r 的建立奠定了基础 k o l o d e r 所给出的范例 c a s e 的定义是 范例是一段带有上下文信息的知识 该知识表达了推理机在达 到其目标的过程中能起关键作用的经验 具体来说 一个范例应该具有如下特性 1 是范例表示了与某个上下文 有关的具体知识 这种知识具有可操作性 二是范例可以是各式各样的 可以 有不同的形状和粒度 可涵盖或大或小的时间片 可带有问题的解答或动作执 行后的效应 三是范例记录了有用的经验 这种经验能帮助推理机在未来更容 易地达到目标 或给出推理机失败的可能性有多大等 在c y r u s 的事例记忆模型基础上 耶鲁大学 佐治亚工学院和麻省大学 的研究人员在法律 烹调和医药等领域中又建造了一些c b r 系统 如 m e d i a t o r c h e f u p e s u a d e r c a s e y l l 2 和j u l i a c b r 研究的迅速 发展是在8 0 年代的中后期 美国的d a r p a 将c b r 作为一个独立的研究领域 进行资助 c b r 领域中的许多研究成果都来源于d a r p a 的c b r 工作室 在认 知科学 机器学习和人工智能领域的许多杂志和会议上面也有很多关于c b r 的 文献 近年来国际上的研究性开发项目和应用系统达1 0 0 余项 至少已出现1 5 种 使用c b r 方法的商品化的工具 1 3 人们对c b r 的研究和应用 已深入到热门 的电子商务 w w w 及信息服务 规划 设计 烹饪 故障诊断 分类 辅助决 策 音乐 软件工程 辩论和法律案例推理 医学 争端调解以及智能教学等 领域 国内对c b r 的研究主要从9 0 年代开始 在规划 设计 法律 诊断 医 学 争端调解 智能教学以及辅助专家决策等领域 都获得了相当的成功 1 9 9 1 年史忠植 李宝东提出了记忆网模型和事例检索算法 1 4 1 9 9 2 年林闯提出了基 于案例推理系统的p e t r i 网模型 1 5 1 9 9 3 年周涵研制了基于事例学习的内燃机油 产品设计系统e o f d s 1 9 9 7 年张治洪研制的基于范例推理的结核病专家系统 16 1 1 9 9 9 年印鉴 李师贤提出了一种基于事例推理的检索模型1 1 钟诗胜等提 出的一个混合属性的实例检索模型 1 8 2 0 0 0 年叶施仁等研制了基于c b r 的鱼 情分析专家系统 1 9 2 0 0 1 年郭茂祖 苏晓红等提出的基于i b l 算法的c b r 系 统中索引与检索机制研究 加 张荣梅等开发了基于c b r 的交通事故智能处理系 统 2 1 1 总的说来 c b r 适用于理论抽象较弱而经验性因素较强的应用领域 1 3 2 基于c b r 的知识发现的研究现状 作为一种基于经验的问题求解技术 基于范例推理把当前所面临的问题或 情况称为目标范例 t a r g e tc a s e 而把记忆的问题或情况称为源范例 b a s e c a s e 对于范例推理 一个通俗的解释是 为了找到一个实际新问题的解 首 先在经验库中寻找相似的问题 从过去的相似问题中取出解 并把它作为求解 实际问题的起点 通过适应性修改而获得新问题的解 2 2 j 基于范例推理技术由 于其独特的推理风格和成功的应用 在知识发现领域有着广阔的研究和应用前 景 目前 基于c b r 的知识发现的研究热点主要集中在以下几点 c b r 作为知识发现的一种方法 和其他知识发现方法有着自然的联系和多 方面的互补性 因此 c b r 和其他技术集成起来 用知识发现能弥补c b r 的不 足和缺陷 例如文献 2 3 和 2 4 用神经网络来实现范例推理系统 文献 2 5 提出 了 个基于归纳技术的范例推理分类算法 文献 2 6 分析了用聚类分析的方法来 为范例库建立多级索引 文献 2 7 2 8 和 2 9 1 研究了范例推理和专家系统的集 成等 范例库 c a s eb a s e 是c b r 中最重要的知识库 文献 3 0 和 3 1 通过在范例推 理中引入数据挖掘技术 提出了自动获取范例库的思想和算法 文献1 3 2 1 提出了 一个基于范例增加的维护策略 文献 3 3 提出了基于范例库上的修正规则的发现 技术和算法 c b r 检索机制中相似性度量方法的研究也是基于c b r 的知识发现方法的 研究热点 例如文献 3 4 1 通过对几种范例匹配函数的研究和分析 寻求一种有效 的范例相似度评估方法来改善不良结构决策领域的c b r 系统的范例检索性能 文献 3 5 提出了一种根据范例间数值型属性对应成比例的原则进行范例匹配的 方法 它作为传统最近邻算法的一个补充 为找到最优相似范例提供了一条有 效途径 文献 3 6 针对最近邻算法的缺陷 提出了改进的算法 从而避免了盲目 搜索 优化了算法 1 3 3 基于范例推理技术在k d d 中的应用与特点 c b r 兴起的主要原因是因为传统的基于规则的系统存在诸多的缺点 2 2 如 知识获取的瓶颈问题 对于处理过的问题没有记忆 导致推理效率低下 处理 领域中例外事件格外困难 整体性较为脆弱等 而c b r 恰能较好的解决以上问 题 首先 范例推理技术比传统专窳系统较为容易的获取知识 避兔了传绞知 谖系统邋行知识获取时鹣簸颈闫题 c b r 使蔫的主要知谖楚蒗钢 不需要分解 和泛化经验以形成规则 因此范例的获取要比规则获取容易得雾 而且实际的 范例往往能比规则或是模型提供更雾的信息 其次 c b r 援铡为薅户送行知识维护提供了缀大静方矮 霹激不需要专容 豹干预蔼挝缺少的范翻加到范铡痒中 或把任务满求和环境的变化可毹导毅的 过时的知识从范例库中删除 第三 c b r 方法扩大了解决问题的范围 w 以得出创掰的解答 同时麓化 了求解逡耩 节鸯了瓣麓求簿薅阗 薅妻冬震耋毽褥剩挺离 c b r 系统主娶蘩予 类比推璁 通过适应悭修改可以形成与旧范例处瑷不同的创新解答 c b r 般 不需要考虑问题求解的县体细节 瓶例的复用节截了大量的时间 同样问题的 再次出现不会导致又 埝的重复操作 c b r 系统会记住和使髑上一次的缝聚 男辨 c b r 可瑷避免黧复失败隶瓣豹代徐 第四 c b r 得出的结果易于给出解释 并且易于用户接受 用户可能需要 证明他们得到的解答魁可信的 否则系统的价值将受到怀疑 基于规则的系统 必须通过它们的趣列嬲释结论 嚣遂些魏赠又霹戆不渡震户突全理簿或接受 c b r 系统的结论是戳从前的范辅为蕊础的 这些范例可以展示给作为系统得出 的结论的有力支持 1 4 本文耱研究意义 人工籍能的研究袋明 传统的专家系统推理模式存在着系统不会学习 维 护耗时 知识难以获取和推理脆弱一陡筹问题 特别是在需要丰寓以往经验的应 用领域里求解问题时 这种攘理模式存在着许多的局限性 由予c b r 是基予以 圭黎舞粪戳溷题赘敬范穰形式表示豹经骢躲识逡雩子推瑾 簸瑟获褥当前闷邋求 解结果的 种推理模式 因此 对c b r 的深入研究有助于探讨人类求解问题和 学习新知识的机制 有助于解决专家系统中知识获取和推理的脆弱性等问鼷 寅助于对不宠垒了解弱领蠛 蔽据叛徒筑经验骰滋某些霰设秘按溅 放瑟谨勃 解决新嚣穗的问题 考秘于在没有脊效算法时求襻闽题的解 基于濑例推理中关镳的一个环节是范例检索道程中得到的相似范例 c b r 的检索要达到以下两个皤标 一是檎索出来的范例尽可能少 二是检索出来蛇 莲爨应尽哥艉兹与童懿菠织龌关或稳钕 翻 鸯予藏锈检索是奁鞠叛篦较戆麓磁 上进行的 要检索到穗似的范例 就鼹应用合适酮相似性算法 算法不适合就 谈不上成功 因此 c b r 系统中的瓶例间的相似憔算法研究 对于基于c b r 的知识发砜鸯极其重要的意义 8 1 5 本文的主要工作和结构安排 理论研究 首先对基于范例的推理技术进行了探索性研究 综述了基于范例推理的本 质 工作原理以及c b r 的优缺点等 其次对范例库上的知识发现进行了深入研究 在前面探索性研究的基础上 对范例库的建立和维护 以及范例库上的知识发现 k d c 的步骤 方法和技术 进行了探讨 并提出了一个新的基于c b r 的知识发现算法模型 实证分析 尽管人力资源管理系统中积累了大量的人力资源数据 然而却不能简单的 聚拢在一起便可运行知识发现算法的 本文以合肥某企业员工职业生活质量的 相关数据为基础 建立员工工作态度高 中 低等范例库 并在这三个范例库 中用建立的算法模型进行知识发现研究 本文共分六章 其中第4 5 章构成本论文的核心内容 第一章绪论 对知识发现的定义 过程和任务等进行了综述 对基于c b r 的知识发现的研究现状以及范例推理技术在知识发现中的应用进行了说明 从 而提出了本文的研究意义 主要工作和本文的结构安排 第二章基于范例推理的基本知识 综述了c b r 中范例表示 检索 复用 修正等重要任务的相关研究成果 对c b r 的研究评价和c b r 的优缺点 第三章范例库上的知识发现 综述了范例库的相关知识以及范例库上的知 识发现的相关技术 第四章基于c b r 的知识发现算法模型 综述了相似性算法的基本知识 提 出了基于c b r 的知识发现算法模型 第五章实证研究 建立员工工作态度高 中 低等范例库 并在这三个范 例库中应用第四章提出的知识发现算法模型进行实例验证 为企业改善和提高 员工的职业生活质量 制定和完善企业的管理政策和措施提供依据 第六章是全文的总结和研究工作的展望 总结了本论文的主要内容和研究 体会 为以后在基于c b r 的知识发现的深入研究打下基础 第二章基于范例推理的基本知识 2 1 引言 基于范例推理是由目标范例的提示而得到历史记忆中的源范例 并由源范 例来指导目标范例求解的一种策略 其工作原理可以理解为修改旧的解决方案 以满足新的需要 使用旧范例解释新情况 评价新方案 构造新问题的解答 c b r 是一种重要的机器学习的方法 本章主要综述了c b r 的工作原理 从范例 的表示 检索 复用 修正 学习和记忆等几个方面详细探讨了c b r 的研究内 容以及c b r 的优缺点 2 2c b r 的工作原理 c b r 求解问题不是简单的从头推导 而是借鉴原有的经验和成功范例 不 断修改直至满足新的问题要求 这不但符合人的思维习惯 而且有助于人们利 用自己和众多设计者的经验智慧 因而c b r 技术近年来在许多领域得到了飞速 的发展 从使用者的角度来看 一个典型的c b r 问题求解可归纳为如图2 1 也可 以说c b r 循环归纳为四个步骤 1 2 2 3 8 删 检索限e t r i e v e 复p 目 r e u s e 修正 r e v i s e 保存限e t a i n 图2 1c b r 工作原理 1 检索 根据输入待解决的问题的有关信息 从范例库中检索相似的范 例集 2 复用 把检索到的范例或范例集中的信息和知识作为获取新问题求解 方案的基础 并判别是否符合需求 若符合 则复用这些信息和知识 否则需 要修正 3 修正 从相似范例中求解方案 使之适合于求解当前问题 得到当前 问题的新求解方案 1 0 4 保存 将新范例及其解根据一定的策略存入范例库中 以备将来使用 即为c b r 的学习方式 c b r 先从范例库中检索出与当前问题类似的以往问题的解决方案 再以此 为出发点 综合运用领域知识 不断交互修改该范例直至产生能够解决当前问 题的新方案 最后将评价合格的新方案作为范例存入范例库中 不管怎样 都 是为了实现经验的复用 2 2 1 范例的表示 范例的表示是c b r 技术的核心问题之一 范例推理所依赖的最重要的知识 存储在范例中 范例的集合为范例库 范例表示常常涉及到这样几个问题 什 么是范例 选择什么信息存放在一个范例中 如何选择合适的范例内容描述结 构 范例库如何组织和索引 以便于检索及复用 对于那些数量达到成千上万 而且十分复杂的范例 组织和索引问题是极其重要的1 4 简单地说 一个范例 就是能导致特定结果的事物的一系列特征属性的集合 范例可以是任何东西 4 例如可以是一个病人的病历 可以是一个菜谱 可以是去一个不熟悉的地方的 说明指南 可以是一个技术项目的规划 可以是 个法律的案例 还可以是计 算机操作失败的纪录 在建筑学上 范例既可以是简单的一座房子的平面图 也可以是一座正在建造的礼堂的最详细的全部设计图 3 7 l 从问题求解的角度来看 一个范例的内容主要由三部分组成 一是问题或 情境描述 s i t u a t i o n 二是解决方案描述 s o l u t i o n 三是结果描述 o u t c o m e 即 可以表示为三元组 c 怎样用 一种合适的方式把范例的三个部分表示出来 是c b r 系统首先要解决的问题 在c b r 系统中没有通用的范例表示方法 往往需要在分析具体问题领域的基础 上通过选择 综合或修改现有的各种知识表示方法来实现 最简单的方法是对 范例进行属性抽取 然后对各个属性赋值 1 属性抽取和表示是指在众多描述客观环境的要素中选择足以表达范例特征 的属性 并给出属性的类型和取值范围 一个属性的权重反映了该属性对于其 他属性的重要程度 以及单个属性对问题解决的贡献程度 4 3 4 4 目前属性权重的选取主要有以下几种方法 4 5 j 1 在库建立的时候由专家给定 通常的方法是由若干领域专家根据经验给出权重 这种方法简单易用 目 前适用于一些简单的范例库 其缺点是人为的因素较为突出 对一些问题的解 决不是很理想 2 通过统计进行估计 这种方法优点也是比较简单 但人为的因素也较为突出 而且由于是统计 后的结果 淡化了问题的特殊性 在实际的使用过程中 在范例库中找到的最 1 1 优范例未必是和要解决的问题最相似 3 用遗传算法来优化权重 由于待髂决超题的复杂瞧 领域专家缀难事先对 个指定趣鼹给出一个有 效粳重 检索蠲豹最耱像蕊铤对薪淘嚣静孵决也不够疆戆 为琵 k y u n g s h i k s h i n i n g o o h a n 把机器学习中的遗传算法应用至i j c b r 的范例检索和提取中 4 用它来优化范例属性的权璧 2 2 2 范镶豹梭豢 范例的检索是从范例库中找到一个或多个与当前问题最相似的箍例 当接 受了一个求解新问题的要求后 c b r 利用相似性知识和特征索引从艳例库中找 爨 缝与圣裁溺蘧据美戆餐会簧袁熬莛铡 著簌中选耩一令最绩蕊镶 嚣为硷 索得到的范例的数量和质熹 赢接影响闻熬的解决效粱 所以范例检綮在c b r 系 统中是非常关键的环节 范例检索邋过三个子过程实现的 楚特征辩识 就是对新润越避芎亍分析 掇敬范镄蠢关褥征藩萑 二楚初步医配 捂觚蓬镶瘁中筏餮一蕴与警蓊闫题穗 关的候选范例 三是最佳选定 就是从初步匹配过程中获得的一缀范例中选取 个或几个与当前问题最相关的范例 4 1 朋 基藏常用盼硷索模型蠢戳下尼静 2 2 0 羽 分类黼模黧 范移j 攘械据产胯纯层次缩构组织 稔索豺采用色上黼下盼探针 策略 越往下 相似程度越商 模板检索 它是根据系统或用户提供的具有特定性质的模式实现检索 在 蕊爨痒孛查羧繇蠢餐舍翁蕊镶 撰投检索鹣实魂类似关系蒙据疼串熬s q 延璃 最近邻检索法 核心思想是计算范例阔的相似度 找出一个或多个最大相 似度的范例为矮检索结果 所谓相似度熬一组属性匹配度的加权和 该方法的 缺点是在不同的鸳景下 范倒属性的重癸性不同 因此给予定量说鳃是很困难 瓣 焉盈该方法逶合于范镶簿中静范镶数不多辩 条 否翔 它静检索 逋度非常慢 因此不适含予大的范例库 归纳检索 虫n i d 3 4 7 4 8 1 通常用于检索目标或案例豹输出已经明确定义的情 掇下 疆豹是扶特定豹寨铡中魍续性戆总结出一个模型 这秘方法戆优点主要 蠢黼点 能够囊劾的进行寮俄分析 确定融最能够区分案例的属性 案例可以 魑根据检索的需要组织成屡次结构 缺点在于需要大燃的案例进行麴纳 实现 越来比较复杂 不确定因索太多会影响学习的好坏 基子袈识翁深捡素 宅楚壤疆滔题孛特征潺淫薰黉 鏊采赋予藩装不露载权 熬 通常与最j 琏邻方法结合使用 这是一类特殊的基于知识的检索 还有一类 刹用表层和深朕知识的结合 其深层知识包括领域的黝果模型 能针对推理过 羧 方法策略修敬的原则来对求解结果进行解释 英潆层知识避免了不相干范 1 2 例的检索 甚至可以搬检索过程中对索引方式进行动态修改 辜串缀网络检索方式 剥用神经阙络的诸多优点 建立一个菠铡库的并行分 布式李孛缀瓣络静表遮棱覆 熬螽禳瓣霜户输入来菠索范铡痒潮络 它其有浚速 自适应 抗噪声等优点 粗糙集检索方式 它不需要预先给定某些属性的数量描述 而是直接从给 定润霆懿捺述集合出发 逶过不可分瓣关系葶彝不可分辨类礁定绘定运题懿避似 域 从箍拭出该问题的内在规律 模糊梭索技术 针对定性和定缀混合范例属性的统一处理方法 当新问题 输入后 模糊机制首先将问题输入的定量属性转化为相应的定性属性 然尉同 遥题孛藤定惶震缝缝合在一莛进行徐索 褥鬟镶滚莲镄集 秀获孛筏赍最糖钕 的1 日有范例 2 2 3 范例的复用 恕羧索蘩静 嚣蔻秘瀚解答弼爨灏润逶或薪藏镶之孛 检索藏镄豹解静复瘸 包括两个方面 旧范例通过所给问题和范例库中瓶例比较得到新旧范例之间的 不同之处 然后回答哪魑解答部分w 以复用到新问题之中 从复耀静信息内容来看 主要蠢嚣葶孛类型 缨莱魏复用粒方法酶复矮 结 果的复蒲 就是当 嚣藏铡豹解答绩聚褥要调整辩 它依据一些转换操律知识 把旧范例中的种种可能解转换为新瓶例中相应的解 方法的筻用则关心旧撒例 中问题的求解方法 而不是其解答的结果 用哪一种方法依具体问题而定 簌笈惩熬方法来番 骞嚣秘方法 复裁器逶瓣 复馥 盛攘滓检索裂豹楣 似范倒的瓣决方案复伟8 c o p y 到新鞭例 作为新范例的解决方案 这是一种平 凡的复用 适配 在更多的系统中要考虑新范例和检索出的相似范例之间的菠 异以及相似范例的解决方案中哪些部分能够传递飨新范例 所以在推理过程中 进行遥醚 a d a p t a t i o n 转粥 2 2 4 范例的修正 范铡修正是c b r 斡中心超题 港点闽题 范铡修正毽括鼹个子任务 1 对蓖镶复弼除段产生斡掰范镄静解决方案进芎亍译佶 著成功剜瘘动学习过稳 2 否则 使用领域知识或用户输入对解决方案进行修正 使解决方案更加符 合新范例的背景 对复用结果进行评估 如果成劝 则不必修难 否则需要对 镬误帮不是遴牙骖正 遴抒绩栗浮德 可以菝摆它在实际巧凌审运行蜃麴复续 也可醴通过商专家询润究成 修正锩误一般涉及镰误探测和寻拽原因 寻找原 因是为了对错误进行解释分析 以找出原因对症下药 即修改造成错误的原因 使其不再发生 当然 修改既可以使用领域知识模型进行自修亚 也可以由用 户耱入采突成 常用的修正技术和方法有以下几种 2 2 1 1 替换方法是选择和确定一个替代物替换不适用新环境的旧有的解的一 部分 2 转换方法是使用启发式方法来替换 删除 增加成分到旧有的解中 以适应新环境 3 衍生类比方法是用得到旧有解的办法来类比推理新环境下的新解 这 要大量使用类比推理的原理 4 多范例综合方法是使用多个范例的结合来修正新问题以得到其解 5 使用范例转换和衍生类比来解决c b r 系统的修正问题 6 利用修正知识来修正新范例 以得到其解 7 基于范例的派生重演法是将过去的修正求解过程记录下来 作为范例 保存 以后的修正就用过去修正的实例作为基础 来对新问题进行c b r 推理 以完成新问题的修正阶段 8 用遗传算法来完成范例的修正 9 采用约束满足方法来修正 1 0 可以利用神经网络来表示范例 通过训练和学习 根据影响因子来 修正得到新范例的结果 2 2 5 范例学习与记忆 利用c b r 求解一个新问题 其解决过程或方案可能会用于与之相似的未来 问题 因此 有必要把它加入到范例库中作为一个新的范例 这就是c b r 的学 习和记忆 也就是知识获取 范例库的学习和记忆是扩充和更新范例库的重要 手段 也是确保有效和可靠利用c b r 系统的重要条件 c b r 的学习途径可分为 成功驱动的学习与失败驱动的学习 当问题得到解决时 c b r