（计算机应用技术专业论文）基于聚类与分类的自学习系统模型.pdf

华中科技大学硕士学位论文 摘要 ， 知识获取作为专家系统的核心，它能够根据系统运行的经验自动地修正和补充 知识库的内容，理解专家或其他来源的知识并编辑形成知识的内部表示形式。专家 系统是否具有知识进化能力成为其应用成败的关键，数据挖掘技术对于改进专家系 统的知识进化能力提供了新的途径。y 基于聚类和分类的知识获取方法具有很好的知识进化和知识鲥错能力。聚类就 是在未知分类规则的情况下对样本集进行分群，分类就是在特征空间中用已知的规 则对样本进行判剐或者预测，两者的结合可用予获取未知知识和整理己经获得的知 识，从而使知识得到进化或知识库中的错误得到纠正。 通过详细分析聚类与分类算法的性能、适用范围以及优缺点，建立一个集成的 自学习系统模型，采用集成聚类与分类的数据开采方法，由此建立起知识获取模型。 该模型无需事先整理大量样本作为训练集和测试集，能够伴随领域专家的日常工作 来学习专家的知识，并自动利用所学知识辘助专家工作。同时较好地解决了聚类分 析初始参数难以准确估计的难题。 在上述自学习系统模型中，通过聚类分柝来发现和修正知识库中的错误知识， 并且仅对出错邻类进行聚类分析，从而减少聚类分析的工作量，大大提高了系统的 学习效率。 实验系统基于面向对象的组件技术开发，采用了具有良好的移植性和可维护性 的j a v a 语言实现。知识的获取能力和进化能力在实验系统中得以验证，说明集成 的自学习系统模型具有很高的分类效率和系统性能。 ， ， 关键词：聚类f 分类；k 近旃；c 均盾鑫法；知囊取 天 华中科技大学硕士学位论文 a b s t r a c t a sak e ym o d u l eo fe x p e r ts y s t e m ，k n o w l e d g ea c q u i s i t i o nm o d u l ec a r l r e v i s ea n d s u p p l y t h ec o n t e n to f k n o w l e d g e d a t a b a s ec o n s t a n t l ya u t o m a t i c a l l yd u r i n gt h ee x p e r i e n c e o fs y s t e mo p e r a t i n g i tc a na l s ou n d e r s t a n dt h ek n o w l e d g ep r o v i d i n gb ye x p e r to rs o m e o t h e rr e s o u r c e ，c o m p i l ei tt oi t so w ni n t e r n a lf o r m a t i tc o m e st ob eak e yt ot h e i m p l e m e n t a t i o n o fe x p e r t s y s t e m t h a tw h e t h e rk n o w l e d g ea c q u i s i t i o nm o d u l eh a s k n o w l e d g ee v o l v e m e n tc a p a b i l i t y d a t am i n i n gt e c h n o l o g yp r o p o s ean e wa p p r o a c ht o e n h a n c ek n o w l e d g ee v o l v i n gc a p a b i l i t yo fe x p e r ts y s t e m k n o w l e d g ea c q u i s i t i o n b a s e do ni n t e g r a t i o no fc l u s t e r i n ga n dc l a s s i f i c a t i o nh a s s t r o n gk n o w l e d g ei n v o l v i n ga n dk n o w l e d g e c o r r e c t i o nc a p a b i l i t y t h ec l a s s i f i c a t i o ni st o d i f f e r e n t i a t e so rp r e d i c tw i t hk n o w nr u l et ot h es a m p l ea m o n gc h a r a c t e r i s t i cs p a c e t h e c l u s t e r i n gi st od i v i d et h es a m p l es e tt os e v e r a lc l u s t e r t h ec o m b i n a t i o no f b o t hc a r lb e u s e dt oe x p e r ts y s t e mt og e tu n k n o w nk n o w l e d g ea n dc o m p i l ek n o w l e d g e b a s e do nd e e p l ya n a l y z i n gp e r f o r m a n c ea n da p p l i c a b l es c o p eo fal o to fc l u s t e r i n g a n dc l a s s i f i c a t i o na l g o r i t h m si nd e t a i l ，w es u g g e s tb u i l d i n gas e l f - l e a n i n gs y s t e mm o d u l e w i t ht h ei n t e g r a t i o no f t w ok i n d so f d a t am i n i n gm e t h o d i tc a nm a k et w ok i n d so f m i n i n g m e t h o d sa b l et o b r i n g o u tt h eb e s ti ne a c ho t h e r t h es e l f - l e a r n i n gs y s t e mm o d u l e c o n s t r u c t e db yt h i sw a yc a n s t u d yk n o w l e d g eo f e x p e r tb yc o m p a n y i n ge x p e r td a i l yw o r k ， l e a r nk n o w l e d g et h a tc a l la i de x p e nw o r k w ew o r ko u tt h ep r o b l e mt h a ti t sh a r dt o a c c u r a t ei n i t i a lp a r a m e t e r o f c l u s t e r i n g i nt h e s e l f - l e a r n i n gs y s t e mm o d u l em e n t i o n e da b o v e ，w ep r o p o s eam e t h o d o f d i s c o v e r i n ga n da d o p t i n gw r o n gk n o w l e d g eo ft h eb a s eb yc l u s t e r i n g w er e d u c et h e w o r k l o a do f c l u s t e r i n gb yo n l yc l u s t e r i n gt ot h en e i g h b o ro fw r o n gc l a s st oi m p r o v et h e e f f i c i e n c yo f s e l f - l e a r n i n gs y s t e m a n e x p e r i m e n ts y s t e ma c c o r d i n gt ot h i sm o d u l ei m p l e m e n t e db yj a v ah a sp r o v e n t h i sm o d e lh a ss t r o n g l ya b i l i t yo fk n o w l e d g ea c q u i s i t i o na n dk n o w l e d g ee v o l u t i o na n d 1 1 华中科技大学硕士学位论文 h i g hc l a s s i f i c a t i o np e r f o r m a n c e k e yw o r d s ：c l u s t e r i n g ；c l a s s i f i c a t i o n ；k - n e a r e s tn e i g h b o rm e t h o d ：c m e a n sm e t h o d ； k n o w l e d g ea c q u i s i t i o n 一一 1 1 1 华中科技大学硕士学位论文 1 1 课题背景 1绪论 本课题来源于荆门市第一人民医院医疗辅助诊断系统，该医院为了加强医疗 工作管理，提高工作效率与服务质量，决定研制该系统。这一系统主要包括电子病 历、医技管理以及智能诊断三个部分。而智能诊断部分的任务就是运用专家系统的 设计原理与方法，模拟医学专家诊断、治疗疾病的思维过程编制的计算机程序，它 可以帮助医生解决复杂的医学问题晗1 ，作为医生诊断、治疗的辅助工具，这是一个 典型的机器学习过程，而学习过程的核心就是利用聚类或者分类理论，对已有样本 进行资料挖掘或者构造分类器来对未知样本进行分类判别 3 3 。 这样的专家系统主要是通过构造分类器对样本进行分类判别c 4 - 6 ，对这个问题的 四十多年的研究产生了很多算法，如：基于最小错误率的贝叶斯决策 豹，k 近邻 法挎3 ，最近提出的支持向量机( s v m ) 3 等。这些算法各有各自的优点，同时也各 有自己的缺陷和局限性e 1 1 。 基于分类理论的专家系统核心就是分类器的构造n 。分类器一般由知识工程师 负责构造。知识工程师同有关领域的专家进行交流，整理并形式化专家的经验和知 识，然后根据需求选择适当的算法实现分类器 3 。一般都需要一组训练集对其训练， 还需要一组测试集防止训练过度 1 3 3 。在构造分类器时，通常不考虑知识的更新和变 化，因此，这样产生的分类器具有以下缺陷 1 4 - 1 9 3 ： 1 分类器的知识结构是静态的，不能适应知识更新。 2 不能自动修正知识库的错误，而偶发性错误常常会严重影响系统分类的正 确性。 3 需要大量的样本作为训练集，这在很多情况下是很难甚至不能满足的。 4 噪声样本对系统性能影响严重。 聚类理论作为数据挖掘的主要算法，根据算法的不同有着各自不同的缺陷 2 0 3 。 l 华中科技大学硕士学位论文 一般都需要事先估计聚类参数，聚类参数估计的准确性对于聚类效果影响严重。另 外，聚类算法计算量较大，不适合大数据集的情况 2 1 - 2 5 】。 在荆门市第一人民医院的实际应用中，缺乏大量可用的样本集作为训练样本或 者聚类分析样本，同医院专家进行交流整理专家经验和知识从而构造分类器这一方 法工作量过于巨大，而且每个科室的知识差异很大，而且构造后的静态知识显然不 能适应当今目新月异的科技进步所带来知识频繁更新。本文的目的在于构造一个自 学习系统理论模型，使得它可以伴随领域专家的日常工作，不断学习积累专家的专 业知识，构造动态的知识系统，为了避免专家偶然性错误带来的严重后果，系统必 须具备一定的纠错能力，在发现系统知识错误时能够辅助纠正错误。同时还能利用 所学知识尽可能的为专家提供诊断信息。 本课题的研究，对于数据开采，模式识别，图像处理以及构建高效的专家系统 等方面课题的研究成果具有较为广泛的意义。 1 2 国内外研究概况 人工智能( a r t i f i c i a li n t e l l i g e n c e 简称a i ) 被誉为本世纪的三大科学技术( a i ， 原子能技术，空间技术) 成就之一，受到了世界各国的普遍重视 2 7 - 2 9 3 , 专家系统是 入工智能的一个分支，产生于六十年代中期，d e n d r a l 专家系统的出现标志着专 家系统的诞生1 3 0 , 虽然它只有不到四十年的历史，但其发展速度相当惊人，它的应 用几乎已渗透到自然科学界的各个领域门1 3 加。它同自然语言理解、机器学习并列为 人工智能的三大研究方向，并且是人工智能中最活跃的分支口”。 专家系统( e s ) 是一种具有专家级水平的，基于知识的，智能化的计算机程序。 是研究如何运用专家知识来解决某专门问题而建立的人机系统的方法和技术。它在 某些特定领域内，能以人类专家的水平动态地建立和解决该领域中的问题。在某些 方面甚至可以超过人类专家，专家系统在许多领域得到了广泛的应用。 2 华中科技大学硕士学位论文 121 专家系统研究概况 第一代专家系统_ d e n l d r a 和m a c s m a 出现。这两个系统的设计和实现 完全是针对其应用领域的，主要注意了系统的性能，而忽略了系统的透明性、灵活 性等方面的问题 3 4 3 。 七十年代专家系统趋于成熟专家系统的观点也开始广泛地被人们接受。七十 年代中期先后出现了以m y c i n 、h e a r s a y 、p r o s p e c t o r 等为代表的一批卓 有成效的专家系统，其中斯坦福大学研究开发的血液感染病诊断专家系统m y c i n 被国际上公认为最有影响的专家系统。在m y c i n 第一次使用了目前专家系统中非 常流行的知识库概念，并在系统中使用了似然推理技术来模拟人类的启发式问题求 解方法昭蚰。它对专家系统的理论和实践都有很大的贡献。h e a r s a y 系统是一个用 于语音识别的专家系统。在h e a r s a y - 一l 系统中提出的黑板系统结构已成为当今一 种非常流行的系统构造技术 3 6 3 0 另外，七十年代出现的元知识概念口们、产生式系 统、框架和语义网络知识表达方式圳也被广泛地应用到了以后的专家系统中， 知识工程概念的提出宣告了专家系统已走向成熟。 专家系统应用领域迅速扩大，处理问题的难度也不断增加。专家系统的开发转 向为骨架系统的开发与设计。骨架系统就是在知识表达，推理和执行方式，解释机 构以及学习机构等方面形成一个基本固定的模式。骨架系统的出现，使得专家系统 的开发速度大大提高，经费大幅下降 3 9 3 。但是一个完善的骨架系统只能够适用于与 其相类似的特定领域的e s ，有一定的专业领域使用范围。使用局限性较大，灵活性 较差。目前国内外开发的几百种专家系统7 0 都是采用骨架系统建成 4 0 1 0 e m y c l n ( e s s e n t i a lm y c i n ) 是美国斯坦福大学计算机系w v m e l l e 等人用 i n t e r l i s p 语言实现并在p d p 1 0 机和v a x 机上通行的e s 骨架系统，它主要适用于 解释型e s 的开发，特别适用于故障诊断这一类演绎问题c 4 1 。 k a s ( k n o w l e d g ea c q u i s i t i o ns y s t e m ) 是美国斯坦福研究院a l 中心的r o d u r a 。 等人用i m e r l i s p 语言实现，并在p d p l o 机和v a x 机上运行的基本规则的骨架系 统。利用它可开发诊断型、预测型e sh 铂。 v p e x p e r t 是美国p a p a r b a c k 软件公司于1 9 8 6 年推出的基于规则的骨架系统， 华中科技大学硕士学位论文 可容纳规贝较少( 一般1 5 0 5 0 0 条之问) ，可在2 8 6 、3 8 6 微机上运行，适用于构造 简单、小型预测型、决策诊断型e s 。有三个窗口( 会话显示窗口、推理搜索路径 显示窗口、结论显示窗口) 、有解释推理过程能力、有接口良好的链按功能、有文本 编辑口、有自动生成咨询问题、有图形显示搜索路径、有数学函数浮点运算、有执 行外部d o s 文件功能等。v p e x p e r t 有较强的生命力，有可能在今后几年中占领小 型e s 开发工具市场h ”。 z i p e 是浙江大学a i 研究所开发的基于结构规则的骨架系统 ，它把全部规 则分解成一组具有层次结构的规则集。它能运行于支持c 语言的机种上，是面向c 语言的骨架系统。它适用于开发较复杂的中、大型e s ( 超过5 0 0 条规则) 。不宜开 发简单小型e s 。与数据库、图形库、图形处理有良好接口。提供了与f o r t r a n p a s c a l 语言标准接口。该校利用它开发了汽轮机方案设计e 8 和液压挖掘机方案 设计e s 等。 华东工学院计算机系于9 0 年研制出g m d e s ( 通用机械设计e s ) 骨架系统h ”。 其主要特点为：1 机械知识的集成表示方法( 即把规则表示、框架表示和过程表示 相结合，根据不同类型特点，采用不同的表示方法) ；2 多级知识获取策略( 分概 念模型生成级，属性生成级，依赖关系生成级，无控制生成级等四组) ；3 正向、 反向、混合三种推理策略名多级模糊综合评判和模糊决策等；4 较理想的用户接口。 g m d e s 骨架系统对推动我国实用e s 的开发和提高e s 的质量和效能有重要意义。 1 2 ，2 目前系统的存在的问题 从第个专家系统的应用到现在已经有半个世纪，对专家系统的理论以及应 用的研究依然如火如茶，但是专家系统在理论和实施过程中仍然有许多问题没有得 到很好的解决。 1 推理分析理论还不够完善。现实的问题十分复杂，影响因素很多，基于距离 的分析理论容易引发“维数灾难”，基于布尔推理理论不能恰当的表达现实问题。同 时由于现实问题本身具有很大的不确定性。使得现有推理分析理论在结论的准确度 和精确度方面还不尽人意h 酗。 4 华中科技大学硕士学位论文 2 知识表达能力不够。由于在很多实际问题中常常不容易找到那些最重要的特 征，或受条件限制不能对他们进行测量，这就使特征选择和提取的任务复杂化而成 为构造专家系统首先要面对的难题“”。 3 知识获取能力不足。目前，知识获取是由知识工程师来完成的。知识工程师 是一个计算机方面的工程师，他从专家那里获取知识，并把它以正确的形式存储到 知识库里去。由于专家所掌握的知识和存储于计算机的知识形式之间通常存在较大 的差别，所以，要建立一个成功的专家系统，知识工程师与专家之间要多次交换意 见，以使知识库能正确地反映专家的知识。除此之外，知识工程师还需要选择推理 方法。知识获取是建立专家系统过程当中最为困难的阶段之一。很多专家系统中缺 少这种模块，或者把它的功能简化成为一个“知识编辑器”，仅有较简单的知识编码 和保持知识库的一致性的功能h 钔。 1 2 3 知识获取研究现状 知识获取作为专家系统的核心模块，它的功能在于根据系统运行的经验自动地 不断修正和补充知识库的内容，或者能根据专家提供的知识经过理解并编辑成所需 的内部形式，作为新知识加入知识库。由于人类认识世界的不断进步，知识处于不 断进化中，知识获取模块是否具有知识进化能力成为专家系统应用成败的关键如。 目前领域知识获取主要采用以下两种策略：手工+ 辅助工具( 图形用户界面) 和自动半自动+ 人工校对。前者相对简单一些，人工工作仍然为主体，知识为移植 者提供了一些图形化的辅助工具，以方便和加快领域知识获取过程。后者采用有指 导的，无指导的或者间接指导的机器学习技术从样本中自动或者半自动获取领域知 识，人工干预程度低。实际上这两种策略并不是完全对立的。只是自动化程度高低 不同而已。某种意义上讲，第一种策略仍然是一种人工编制知识库的过程，知识瓶 颈知识得到某种程度上的缓解。第二种策略才是解决知识获取问题的真正出路 。 北京化工大学袁洪芳，江志农提出了一种以融合多种学习策略为主题的集成式 学习算法。其基本思想为将维修记录库中的特殊例子升华为知识库中的规则，对于 维修记录中的人工诊断维修记录利用归纳学习分析实际例子，将满足定条件的维 华中科技大学硕士学位论文 修实例首先通过发生故障的设备，故障类型选出对应的规则库及概念库，将维修记 录中的故障原因与原知识库中前提逐层进行概念匹配，当完全匹配( 即前提条件及 其数量均相同) ，这时不必产生规则。自动调整原规则置信度，在原来的基础上附加 - - 4 , 步长，如果不匹配，( 即出现新的前提，包括前提或者属性) 专家可适当修改新 概念的描述以确保普遍性，以启发式提问方式使专家给出基本事实，让新的节点位 于概念网中合适的位置( 自动生成传播向量) ，形成新的概念库，然后再利用正向推 理算法启发式搜索策略从新的学习前提开始至故障目标形成规则链，并要求专家给 出默认较低前提与规则的置信度，所有产生的新的规则自动经知识库检验放入推理 规则库，完成机器学习。该例子学习需要有专家参与，实际上是一个例子学习与对 专家启发式提问的方式相结合的学习。该系统需要专家定期通过知识管理系统来检 查和维护知识库的完善性。其知识获取属于第一种知识获取策略 5 1 o 厦门大学的吴顺祥将成熟的r d b m s 技术同e s 结合，构造了个高效的以数据 库为载体的知识获取系统( d b k a s ) ，系统提供图形化的规则编辑界面，采用i f t h e n 形式表示规则。通过知识的可证明性检测，矛盾性检测，命题包 含检测，命题冗余检测来保证知识库的简洁性和正确性。利用索引进行快速规则匹 配。利用数据库事务管理来保证知识的一致性和完整性。该系统仍然属于第一种知 识获取策略”“。 p w a l a k 提出基于粗集理论的规则获取方法f 5 掣，首先根据专家经验和领域背景知 识确定各个条件属性的重要度，然后利用粗集方法分析数据之间的联系。挖掘数据 库中重要知识和信息，根据概率最优准则，提取最有用的最优规则用于构建知识库。 该方法自动化程度比较高，属于第二种知识获取策略。 1 3 关键技术分析 随着数据库技术和人工智能的日新月异的发展，必然引起知识获取方法的变革 现简述如下。 6 华中科技大学硕士学位论文 1 3 i 知识获取关键技术 人工智能与数据库技术是计算机科学的两大重要领域越来越多的研究成果表 明。这两种技术的相互渗透将给计算机应用带来更广阔的前景。结合数据库技术以 吸取对方经验和长处可克服人工智能短处，这也是人工智能成功的关键。 知识获取可借鉴数据库关于信息存贮、共享、并发控制和故障恢复技术对知 识获取后的知识库管理、设计以及对大型知识库、共享知识库和分布式知识库提供 帮助，改善知识库的特性，使之规模提高到实用水平。如数据库的基本范例( 输入、 检索、更新等) 可作为新的知识库范例数据库的基本目标( 共享性、独立性、分 布性等) 可作为新的知识库基本目标，数据库的三级表示与设计方法可用作新的知 识库设计方法1 5 ”。 1 3 2 聚类与分类关键技术 从人工智能技术产生以来，对于它的一系列算法的改进就从未止步。如：聚类 分析中理论上最为可靠，应用最为广泛的算法之一的c 均值算法1 5 5 1 。c 均值算法将 n 个目标分割到c 个聚类中去。首先选择c 个代表点，其余目标根据到代表点的距 离划分到c 个类中。然后用每个类的重心代表这个类，对目标进行从新分割，这 过程叠代进行，直到收敛。c 均值算法的难点在于选择初始c 值和代表点：另外， 在计算过程中，每次调整一个样本的类别，各类的聚类中心就要调整一次，所以计 算量较大。文献【5 6 】中对此提出了许多改进算法，比较典型的改进算法如i s o d a t a 法等。文献 5 7 】改进k 近邻法以减少计算量和存储量，文献【5 8 】采用数据标准化法 来确定c 均值算法的初始划分，通过计算 一c 曲线的拐点取得最优聚类数【5 8 1 。为 了解决维数灾难提出了支持向量机算法【5 9 1 。通过模糊集理论来提高现有算法的分类 效果，如模糊c 均值算法，模糊神经网络算法，模糊k 近邻分类法等6 们。波兰的 p a w l a k 针对g f r e g e 的边界区域思想提出了粗糙集理论( r o u g hs e t ) 网来处理知 识的不确定性和模糊性问题。w i e n e r 和n g 曾分别将神经网络用于图书分类专家系 统e w i e n e r 试过感知器方法( p e r c e p t r o na p p r o a c h ，无隐层) 和三层神经网络( 一 华中科技大学硕士学位论文 个隐层) 。n g 只用了感知器方法。这些系统中为每个分类建立一个神经网络，通过 学习得到从输入单词( 或者更复杂的特征词向量) 到分类的非线性映像。w i e n e r 的 实验建议将多层神经网络( m u l t i p l e c l a s sn n e t ，用于高层分类) 和多个两层神经网 络( t w o c l a s s n e t w o r k s ，用于最底层分类) 混合起来1 。 1 4 课题研究思路 从某种程度上说，集成的基本思想是“m a n yc o u l db eb e t t e rt h a no n e ” e 2 3 。 通过将分类器和聚类器集成起来，并采用与领域专家交互的方式，可将建立知识库 融于专家的正常工作中。知识库系统自动根据所学的知识对未知事物分类，如果系 统不能分类或者不能很有把握的分类，则继续向领域专家学习，并将所学知识存入 知识库。如果领域专家提示系统自动分类有误，则说明原有知识不正确，通过不断 的修正c 值，对所学样本进行c 均值分析，并将结果提请专家审核，最终选择合适 的c 值并更新知识库。对于专家和系统都不能准确分类的事物，则利用k 近邻法对 其进行分类，同时通过冲突检测来剔除噪声数据。这种学习方法符合人类认识世界 的基本规律和思维习惯，并且符合知识的相对性和进化性等特征。 因此，在专家系统的知识学习过程中，对于不同时机采用不同算法，使得能够 互相补充，相得益彰。从而使得系统能够自动进行知识更新，通过交互学习修正错 误并剔除噪声样本。 1 5 主要研究工作 在详细深入分析大量的聚类与分类算法的性能，适用范围以及优缺点的基础上， 给出了这两类独立的数据开采方法集成起来自学习系统模型，使两类方法能够相得 益彰。由此建立的知识获取模型无需事先整理大量样本作为训练集和测试集，能够 伴随领域专家的工作学习专家的知识，并自动利用所学知识辅助专家工作。 妥善的解决了聚类分析初始参数难以准确估计的难题。 8 华中科技大学硕士学位论文 给出了通过聚类分析来发现和修正知识库中的错误知识的方法。 给出了仅对出错邻类进行聚类分析的方法来减少聚类分析工作量，从而提高系 统效率的方法。 一 9 华中科技大学硕士学位论文 2 算法分析与设计 聚类和分类理论中都有很多典型的算法，并不是所有聚类算法都能和分类算法 集成，必须在对他们进行详细深入的性能分析，掌握其算法核心思想和实现细节， 从而寻找结合点。本章将根据智能诊断系统的应用和荆门市第一人民医院的现实情 况，深入讨论聚类和分类理论中具有代表性的算法的性能。通过性能比较，在聚类 理论和分类理论中各选择一种作为集成系统的核心算法。 2 1 系统需求 荆门市第一人民医院虽然电子病例已经使用一年多，但由于原来系统设计时没 有考虑到智能诊断系统的需要，其大量诊疗资料不能够使用。因此没有大量现成的 样本集可以用来构建训练集。采用知识工程师同医生交流的方式也变得不可行，这 样不但严重影响医生的日常工作，而且巨大的工作量让人无法承受。所以只能让专 家系统能够伴随医生的日常工作，通过学习来逐渐积累专家的知识。 医学是- - i 1 知识更新迅速的学科，每天都有新的病情和新的诊疗手段出现。这 就决定了专家系统必须能够动态调整知识库。使得知识库能够适应不断进步的科学 技术。 由于人类行为的主观性，不可避免的出现错误。为了避免系统错误知识“污染” 知识库，对专家系统的准确率造成严重影晌。该系统必须能够发现并纠正系统错误。 同时还必须在知识存入知识库之前进行检查，使得知识库不会出现互相矛盾的知识。 当然，作为个完整的专家系统还必须首先进行特征提取，将病人病征向量空 间转化为欧几里得空间等一系列工作。本文作为智能诊断系统的理论预研，目的是 提出一个能够满足现实需求的模型。所以要设计的专家系统具有如下特征； 1 具有动态知识库，能够边学习边工作，从而不需要构造大量的训练集。 2 具有自动纠错能力，能够对知识进行检测，防止冲突发生，在知识库出现错 1 0 华中科技大学硕士学位论文 误后能够帮助分析并纠正错误。 2 2 分类算法选择 2 2 1 分类算法概论 分类要解决的问题是为一个事件或对象归类。事实上，分类器就是一个( 或一 系列) 判别函数( 或决策面) 。基于分类的专家系统需要由知识工程师和领域专家不 断交流，总结专家知识并转化为分类规则。所以构造分类必须事先知道分类规则。 在使用上，既可以用此模型分析已有的样本，也可以用它来预测未来的样本。分类 器的基本构造如图2 1 。 x 1 x 2 1 1 ( x ) 决策 圈2 1 分类器构造图 分类器的评价标准有三种尺度：( 1 ) 预测准确度；( 2 ) 计算复杂度；( 3 ) 模型 描述的简洁度。值得注意的是，分类的效果一般和样本的特点有关，目前普遍认为 不存在某种方法能适合于各种特点的数据集。 卡内基梅隆大学的y i m i n gy a n g 在“文本分类方法回顾”一文中对五种文本分 类方法进行了测试研究：支持向量机( s v m ) ，k 近邻分类法( k n n ) ，神经网络 ( n n e t ) ，线性最小平方拟合法( l l s f ) 和简单贝叶斯分类法( n b ) 。侧重于这些方法在 1 1 华中科技大学硕士学位论文 非均匀分类分布上的健壮性及其性能。结果表明当训练集中的正确样本较少时( 少 于1 0 ) ，支持向量机，k 近邻分类法和线性最小平方拟合法比神经网络，简单贝叶 斯分类法显然要好，而当处理大分类( 超过3 0 0 个样本) 时性能相当。 2 2 2 典型分类算法性能分析 2 2 2 1 支持向量机( s v m ) 支持向量机( s u p p o r t v e c t o rm a c h i n e s ，s v m ) 由v a p n i k 在1 9 9 5 年提出，用于 解决二分类模式识别问题。它是基于风险最小化原则，并由此引出错误边界分析理 论它在向量空间中找到一个决策平面( d e c i s i o ns u r f a c e ) ，这个平面能“最好”地 分割两个分类中的样本点。为了定义“最好”分割，我们引入两个分类的边界( m a r g i n ) 定义。通过图2 2 和2 3 予以说明。图2 2 和2 3 中的实线显示了两个决策平面，每 个都可以正确分割两组样本。与实线平行的虚线表示决策平面可以平移的空间，这 种平移不会造成样本的分割错误。并行线间的距离称为边界。s v m 就是要在训练集 中找到具有最大边界的决策平面。 决策平面可以写作：访i b = 0 其中i 是要分类的任意样本点，茹和常数b 通过训练获得。令训练集 d = ( 弘，墨) ，y ， 1 ) 是对i 的分类( + 1 表示它是个正例子，1 为负例子) ，s v m 问题就是要找到满足如下条件的谤和b 访i ，一b + lf o ，y f = + l ( 1 ) 访舅，一b s 一1f o ，y 。= - 1 ( 2 ) 而且向量茹的模最小。 华中科技大学硕士学位论文 詈g 专 o c ： 图2 2 具有较小边界( 两虚线问的距离) 的决策线( 图中实线) 图2 3 具有最大边界韵决策线 说明：虚线所穿过的点为支持向量 1 s v m 的一个有趣特性是决策平面只是由那些刚好和决策面距离为百鲁的样本 w 点来决定，称为决策向量，删除其它样本点不会影响算法的结果( 即产生的决策函 数不变) 。这个特性是s v m 与其它分类方法不同之处。它是否会造成s v m 的性能 发生显著改变尚未可知。 j o a c h i m s 最近采用s v m 来进行样本分类，并声称它比其它方法都好，但他的评 价结果是非正式的。另外他的理论和算法还缺少完备测试，没有对不同分类分布进 行性能分析，特别是对那些极小分类，他报告的测试结果低于他人的结果。 2 2 2 2k 近邻法( k n n ) k 近邻分类法是著名的模式识别统计学方法，已经有四十年历史。它是分类效 果最好的分类算法之一。k 近邻分类法相当简单：给定一个测试样本，系统在训练 华中科技大学硕士学位论文 集中查找离它最近的k 个邻居，并根据这些邻居的分类来给该样本的候选分类评分。 把邻居样本和测试样本的相似度作为邻居样本所在分类的权重。如果这k 个邻居中 的部分样本属于同一个分类，则该分类中的每个邻居的权重求和并作为该分类和测 试样本的相似度。 通过对候选分类评分的排序，然后给出个阈值，就可以判定测试样本的分类。 k n n 中的决策规则可写作： y q ，c i ) =s i m ( i ，a i ) y ( a 。c j ) - bj a e t w 其中y ( 孑。，c ，) o ，1 ) 表示样本z 是否属于分类c j ( y = 1 为是，y = o 为否) ； s 砌( i ，孑，) 表示测试样本i 和训练样本乏的相似度；屯则是二元决策的阈值。为了方 便起见，我们采用两个向量的夹角余弦作为两个样本的相似度。各个分类的阈值6 。 则是通过训练获得，这些阈值将能得到最好的评价。 2 ，2 2 3 线性最小平方拟合( l l s f ) 线性最小平方拟合法( l i n e a r l e a s ts q u a r e sf i t ) 是y a n g 发明的映像方法。从训 练集样本和分类中学习得到的多元回归模型( m u l t i v a r i a t er e g r e s s i o nm o d e l ) 。训练 样本用输入，输出向量对表示，其中输入向量用传统向量空间模型表示的样本( 值和 权重) ，输出向量则是样本对应的分类( 带有二元权重) 。通过求解这些向量对的线 性最小平方拟合，可以得到一个样本分类的回归系数矩阵： 民= a r g m i t t l if a 一引1 2 f 其中矩阵f l s 为求解矩阵，定义了从任意样本到加权分类向量的映像。对这些 分类权重排序，则可以得到输入样本可能分类的列表。然后再指定阈值，就可以判 别样本的分类。阚值同样是从训练中学习获取的，与k 近邻分类法相同。 尽管线性最小平方拟合法与k 近邻分类法方法不同，但它们在我们所做的所有 测试上性能都很相似( 除了在极小分类上的健壮性比较) 。 华中科技大学硕士学位论文 2 22 4 神经网络( n n e t ) 神经网络( n e u r a l n e t w o r k ，n n e t ) 技术是人工智能中的成熟技术。神经网络的 基本思想是：如果神经元u i 接收到来自另一神经元u j 的输出，则当这个神经元同时 兴奋时，从u j 到u j 的权值w i 就得到加强。 神经网络的一个重要特点就是它能够较有效的解决很多非线性问题，从而在很 多工程应用中取得成功。但另一方面，神经网络中很多重要的问题尚没有从理论上 得到解决，因此实际应用中仍有许多因素要凭经验确定，比如如何选择网络节点数， 初始权值和学习步长等；局部极小点问题，过学习与欠学习问题等也是很多神经网 络方法中普遍存在的问题。 在实际应用中，值得关注还有训练的开销。因为神经网络的训练需要大量样本 作为训练集和检测集，而且所需时间开销要远远超过其它分类方法。在荆门市第一 人民医院的实际应用中，几乎没有现成可用的数据集，无论是对于开发人员还是对 于用户，构造数据集的工作也过于庞大丽无法忍受。 2 22 5 分类算法评价 从算法的时间空间复杂度，分类效果来看，支持向量机和k 近邻分类比其它方 法要好。神经网络分类效果同k 近邻分类法相当，但是训练的时间和空间消耗远远 超过其它分类方法。线性最小平方拟合法和k 近邻法虽然实现方法不同，但在测试 中各方面性能都相当，但线性最小平方拟合法在实现上较k 近邻法要困难得多。由 于支持向量机性能上尚有争议，尚未经过完备的测试，因此，在分类算法的选择上 本文倾向于k 近邻法。 华中科技大学硕士学位论文 2 3 聚类算法选择 23 1 聚类算法概论 聚类( c l u s t e r ) 是把整个样本分成不同的群组。它的目的是尽量使得群与群之 间差别很明显，而同一个群之间的样本尽量相似。聚类分析主要是基于物以类聚的 朴素思想。与分类不同，在开始聚集之前你不知道要把样本分成几组，也不知道怎 么分( 依照哪几个变量) 。因此在聚集之后需要由领域专家来解释这样分群的意义。 很多情况下一次聚集你得到的分群对你的业务来说可能并不好，这时你需要删除或 增加变量以影响分群的方式，经过几次反复之后才能最终得到一个理想的结果。c 均值法是比较常用的聚集算法。 聚类也可以视为相似样本的分组表达方式。在向量空间模型中，用户可以通过 比较查询向量和聚类的中心进行检索，并在聚类中进一步检索以找到壤相似的样本。 聚类算法包括：分层次聚类法( 最短距离法) ，最简单的聚类方法，最大距离样本， c 均值法( 距离平方和最小聚类法) ，叠代自组织( i s o d a t a ) 聚类法，i s o d a t a 法的改进，基于“核”的评估聚类方法等。下面仅对前四种方法进行讨论。 2 3 2 典型聚类算法分析 2 3 2 1 分层次聚类法( t l 短距离法) 分层次聚类法的基本思路是寻找“距离”最近的两个样本结合，事先给定k 值， 即聚类成k 类。算法首先确定最近的两个样本，然后将这两个样本合并成类，重 新计算新类的中心，并将该中心代替这两个样本重新计算最近的两个样本，如此递 归下去，知道只剩下k 个样本为止。剩下的k 个样本即为各类的类中心，被取代的 即为每一类的类集。 该算法简单有效，适用于类内距离小，类间距离大的样本集效果明显，同时对 于分布较为均匀的样本集也可以取得较好的效果。分类效果同取样顺序无关。但是 1 6 华中科技大学硕士学位论文 每轮计算都需要计算n 个样本之间的距离，使得算法时间复杂度达到o ( n 3 ) 级。 只适合于小样本集。而且需要事先确定k 值，k 值估计的好坏对于算法聚类效果影 响很大。 2 3 2 2 最简单聚类法 最简单聚类法不需要实现确定k 值：但需要事先给定相似性尺度( 距离) 阈值。 假定有n 个样本，z s = z l ， z 2 ，z n ) ，给定一个阈值t 。任取一个样本，例 如z l ，把z l 作为第一个类的中心，z 】= z 1 。然后依次取z i ( i = 2 ，3 ，n ) ，计算 z l 与z i 的距离d l i o 若d l i t ，则判定z 。属于z 。为中心的那个类；若d l i t ，则把 z 。作为新的类中心z 。然后对剩下的样本z 。分别计算与z ，z ：的距离d ，d 2 。若 其中较小者t ，则判定z ，属于较小的那一类。否则，就把z 。作为新的一个类的中 心z 。如此，继续，直至对全