（计算机软件与理论专业论文）基于领域知识的解题方法语义化档案系统的研究.pdf

皋于领域知识的解题方法语义化档案系统的研究 基于领域知识的解题方法语义化档案系统的研究 摘要 国际大学生程序设计竞赛( a c m i c p c ) 是美国计算机协会 ( a c m ) 主办的全球性的程序设计比赛。每所参赛学校为了获得 更优异的成绩，都会培养优秀的学生去参加a c m 比赛。现在随着 i n t e m e t 技术的发展，w e b 空间里也有许多关于a c m 程序设计的 解题方法，但是对于很多参赛选手在训练时却很难充分利用这些资 源。 究其原因：1 ) 现有的w e b 空间的解题方法还仅仅是一个“信 息”的容器，其内容只适合给参赛选手浏览，而不具备机器所能理 解的语义。机器在进行资源查找的时候，能够得到的语义信息相当 有限。2 ) 现有的w e b 空间的解题方法的描述比较片面，参赛选手 往往由于得不到完整的信息而不能彻底地解决问题，并造成机器在 传递语义信息时也有所疏漏。3 ) 现有的w e b 空间的解题方法相互 之间没有联系，造成参赛选手不能有序地去把握所有方法之间的差 异，机器传递语义时也不具备结构性。 针对以上问题，本文提出基于领域知识的解题方法语义化档案 系统，并选取了大量的题目及相关解题方法作为应用的实例展开研 甚于领域知识的解题方法语义化档案系统的研究 究。本文与现有w e b 空间的解题方法最大的区别在于，将解题方 法语义化，并对解题方法建立联系，来帮助参赛选手训练。 论文首先将本体论纳入领域知识的模型分析中去，通过对解题 方法原理的分析得到领域知识的本体模型。这个模型符合人脑对程 序设计解题方法所反映的概念化的模型，适用于整个a c m 程序设 计的领域，领域中程序设计方法可以通过这个模型表现出来。通过 这个模型，将解题方法抽象化，并可以对所有的解题方法的模型进 行整合。 其次，论文提出了面向a c m 领域的解题方法语义化档案系统 的结构，该结构整合了语义化的解题方法。通过形式概念分析对解 题方法建立概念格，这个概念格直观地描述出语义化的解题方法之 间的联系。并且又利用了形式概念分析的理论和网络流中最小费用 最大流理论为背景，创新地提出解题方法相似度的概念。解题方法 相似度是用来描述各种解题方法的相似程度。通过概念格和解题方 法相似度，参赛选手可以对自己解决和未解决的程序设计问题有个 整体到局部的认识。 最后本文基于上述理论描述了解题方法语义化档案系统的实 例应用系统。通过实例应用来验证和检验本文的研究工作。 似度 关键字：解题方法，本体模型，形势概念分析，概念格，网络流，相 基于领域知识的解题方法语义化档案系统的研究 t h er e s e a r c ho fs e 【a n t i cp r o b l e m s o l u t i o ns y s t e mb a s e do nd o m a i n k n o 凡e d e g e a b s t r a c t i n t e r n a t i o n a lc o l l e g i a t ep r o g r a m m i n gc o n t e s ti st h ew o r l dw i d e p r o g r a m m i n g c o n t e s th o l d b y a s s o c i a t i o nf o rt h e c o m p u t i n g m a c h i n e r y ( a c m ) i no r d e rt og e tg o o da c h i e v e m e n t ，e a c h s c h o o lw i l l t r a i n g o o ds t u d e n t s t oa t t e n di t w i t ht h ed e v e l o p m e n to fi n t e r n e t t e c h n o l o g y ，t h e r ea r em a n ya c mp r o b l e ms o l u t i o n si nt h ec u r r e n tw e b s p a c e b u tm a n ys t u d e n t sc a n n o tr e a l l ym a k ef u l lu s eo ft h e m t h e r ea r em a i n l yt h r e er e a s o n sf o rt h i sp h e n o m e n o n ：1 ) t h e c u r r e n tw e bi sj u s tac o n t a i n e ro f i n f o r m a t i o n ，o fw h i c ht h ec o n t e n t s a r eo n l ys u i t a b l ef o rs t u d e n t s ，n o tw i t hm a c h i n e - r e a d a b l es e m a n t i c s ， w h i c hc a u s e st h el a c ko fe n o u g hs e m a n t i c sf o rm a c h i n e ss e a r c h i n gt h e w e b 2 ) t h ec u r r e n tw e bd e s c r i b e sp r o g r a m m i n gs o l u t i o n su n i l a t e r a l l y ， 7 幕十领域知识的解题方法语义化档案系统的研究 w h i c hl e a d st h a ts t u d e n t sc o u l dn o tg e tf u l li n f o r m a t i o na n ds o l v et h e p r o b l e mt h o r o u g h l y 3 ) t h es o l u t i o ni nt h ec u r r e n tw e bh a sn or e l a t i o n w i t he a c h o t h e r ，w h i c hl e a d st h a t s t u d e n t sc o u l dn o tr e a l i z et h e d i f f e r e n c e a m o n gt h e s o l u t i o na n dm a c h i n e r e a d a b l es e m a n t i c s i n f o r m a t i o nh a sn os t r u c t u r e a i m e dt os o l v es u c hp r o b l e m s ，t h i sp a p e rc r e a t e sp r o g r a m m i n g s o l u t i o ns e m a n t i c ss y s t e mb a s e do nd o m a i nk n o w l e d g ea n dd e s i g n m a n yp r o g r a m m i n gp r o b l e ma n dt h e i rs o l u t i o na se x a m p l e st od e v e l o p r e s e a r c h e s m a c h i n e r e a d a b l es e m a n t i c ss o l u t i o nw i t hs o m ec e r t a i n r e l a t i o n s h i p a n dh e l p i n gs t u d e n t ss o l v e p r o b l e m sa r e t h e b i g g e s t d i f f e r e n c eb e t w e e nt h i sp a p e ra n dt h ec u r r e n tw e b f i r s t l y ，t h i sp a p e ra n a l y s e st h ed o m a i nk n o w l e d g em o d e lb y o n t o l o g ya n dd e s i g nt h ep r o g r a m m i n gs o l u t i o no n t o l o g i c a lm o d e l t h i s m o d e lm e e t st h e c o n c e p tm o d e l w h i c h i st h er e a c t i o no ft h e p r o g r a m m i n g s o l u t i o ni n p e o p l e h e a d i ti ss u i t a b l ef o ra c m p r o g r a m m i n ga n de a c hs o l u t i o ni na c mp r o g r a m m i n gc a nu s ei t t h o u g ht h i sm o d e l ，p r o g r a m m i n gs o l u t i o nw i l lb es e m a n t i c s i tw i l lb e u s e f u lt oc o m b i n ea l lt h es o l u t i o n s s e c o n d l y ，t h i sp a p e rd e s i g n st h e s t r u c t u r eo fp r o g r a m m i n g s o l u t i o ns e m a n t i c ss y s t e mb a s e do na c m d o m a i n ，w h i c hc o m b i n ea l l t h es e m a n t i c ss o l u t i o n s t h ec o n c e p tl a t t i c eo np r o g r a m m i n gs o l u t i o ni s 8 皋于领域知识的解题方泫语义化档案系统的研究 b u i l tb yf o r m a tc o n c e p ta n a l y s i s t h ec o n c e p tl a t t i c ec a nd e s c r i b et h e r e l a t i o n s h i pa m o n gs e m a n t i c sp r o g r a m m i n gs o l u t i o n s a n dt h i sp a p e r d e s i g n st h ec o n c e p t o fp r o g r a m m i n gs o l u t i o ns i m i l a r i t yb yu s i n g f o r m a tc o n c e p ta n a l y s i sa n dn e t w o r kf l o wm i n i m u mc o s tm a x i m u m f l o w t h ec o n c e p to fp r o g r a m m i n gs o l u t i o ns i m i l a r i t yi s u s e dt o d e s c r i b e s i m i l a r i t y b e t w e e nt w op r o g r a m m i n gs o l u t i o n t h o u g h c o n c e p tl a t t i c e a n dp r o g r a m m i n gs o l u t i o ns i m i l a r i t y ，s t u d e n t s c a n r e a l i z ea l lt h es o l v e dp r o b l e m sa n du n s o l v e dp r o b l e m st h o r o u g h l yf r o m t h ew h o l et ot h el o c a l a tl a s t ，t h i sp a p e rd e s c r i b e so n ea p p l i c a t i o no fp r o g r a m m i n g s o l u t i o ns e m a n t i c ss y s t e mb a s e do nt h ea b o v et h e o r y i ts h o w st h e c o r r e c t n e s so ft h er e s e a r c hw o r ki nt h i sp a p e r k e yw o r d s ：p r o g r a m m i n gs o l u t i o n ，o n t o l o g ym o d e l ，f o r m a t c o n c e p ta n a l y s i s ，c o n c e p tl a t t i c e ，n e t w o r kf l o w ，s i m i l a r i t y 9 基于领域知识的解题方法语义化档案系统的研究 东华大学学位论文原创性声明 本人郑重声明：我恪守学术道德，崇尚严谨学风。所呈交的学位论文，是 本人在导师的指导下，独立进行研究工作所取得的成果。除文中已明确注明和 引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品及 成果的内容。论文为本人亲自撰写，我对所写的内容负责，并完全意识到本声 明的法律结果由本人承担。 e t 期：芝雾雾静期：硼年匆月i 哔 一前日 基于领域知识的解题方法语义化档案系统的研究 东华大学学位论文版权使用授权书 学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅或借阅。本人授权东华大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 学位论文作者签名： 保密口，在年解密后适用本版权书。 不保密口。 同期：谢年易月气日 指导教师签名： 豺逸邪射遇 日期：矽多年孑月善日 雉十领域知识的解题方泫语义化档案系统的研究 1 1 研究背景和意义 1 1 1 解题方法所属领域 第一章绪论 a c m i c p c ( a c mi n t e r n a t i o n a lc o l l e g i a t ep r o g r a m m i n gc o n t e s t ，国际大学 生程序设计竞赛) 是由国际计算机界历史悠久、颇具权威性的组织a c m ( a s s o c i a t i o nf o rc o m p u t i n gm a c h i n e r y ，国际计算机协会) 主办的，世界上公 认的规模最大、水平最高的国际大学生程序设计竞赛，其目的旨在使大学生运 用计算机来充分展示自己分析问题和解决问题的能力。a c m 国际大学生程序 设计竞赛已成为世界各国大学生最具影响力的国际级计算机类的赛事，是广大 爱好计算机编程的大学生展示才华的舞台，是著名大学计算机教育成果的直接 体现。 a c m 参赛选手需要对程序设计有深入的了解。除了会分析问题以外，也 要用程序描述出来。本课题研究的解题方法是针对a c m 程序设计竞赛题目的 解决方法。 1 1 2 解题方法资源研究现状缺陷 现在随着i n t e m e t 技术的发展，w e b 空| 、日j 里也有许多关于a c m 程序设计 的解题方法。如果能有效地利用这其中丰富的解题方法资源无疑对提高参赛选 手的a c m 程序设计水平有很大的帮助。图1 1 是一个著名的描述解题方法的 网站的部分资源。 e 十顿域j , h i j l 呐解地方法语义他档禀系统的究 h * p d ，7 _ f 。￥* 。* sp h “r 。* 1 “h c 一“ d h ，一“。- h t u h j j ij wh 1 f 6r 1 n _ o t t 一】 。1 t _ - 。+ ”c * 【r 、 v - h _ ”，1 1l re _ f u ii 并乳的描述斛题方法的嘲站的筒f 分资源 从中我们町u 发玑，传统的搞述解题方法资源的w e b 空川订以r ，当缺 陷： 1 现有的解题方法资源在川站l 的纠纵结构通常是按照题目收集的先后 顺序决定的，川，。需要按倾序来浏览返雌资源柬部助i 己解扶问题； 2 虮有的解题方法描述大都儿有解题算法，然而往往在a c m 比赛和圳 练t ，解题并没柯正确解决题目的原n 是输入和输川的处理l ，尤其是训学者： 3m 有的角 4 _ 地方法资源存网站针对菜一道题，只描述了种方法，然而 州分题目有两种或以卜的解题方法，导致h 广没有全山】地了解该舾日的解题方 浊： 4 现有的解题方法资源对桐刚的解题疗法t 口以解决多个题日缺乏描述； 缺l i f t1 、2 说明解题斤法资源缺少语义化信息，缺陷3 、4 | 兑叫现自资源 没有建崎解题力法之问的联系。故愤统的解题方法资源主要存在以i ? 两方面的 不足而无法满足川户的个眭化使用： 1 现有的解题方法资源缺少语义化信息。 2 现有的解题方法资源不能建议解题方法之m 的联系。 本文的研究工作将隔绕j 述两个问题展”。 皋十领域知识的解题方法语义化档案系统的研究 1 1 3 语义w e b 与本体论的引进 语义网( s e m a n t i cw e b ) 是由w 3 c ( w o r l dw i d ew e bc o n s o r t i u m ) 的创始人 t i mb e m e r s l e e 1 】在1 9 9 8 年提出的一个概念，它的核心是：通过给万维网上 的文档( 如h t m l ) 添加元数据( m e t a d a t a ) ，以表达能够被计算机所理解的 语义，从而使整个互联网成为一个通用的信息交换媒介。 w e b 应当被带着这样的目的设计成一个信息空间的：它不仅要对人与人 之问的沟通信息有用，而且可以使机器能够一起参与进来并有所帮助。要实现 这一目的的最大障碍之一是，w e b 被设计成了专给人类来使用，w e b 上数据 的组织形式对一个浏览网页的机器人来说是不适合的。相比一些人工智能的课 题关于如何对机器进行训练使它们能像人一样来思考，s e m a n t i cw e b 的方法是 研究开发能够将信息表现成机器可以处理的形式的语言【2 j 。 而本体( o n t o l o g y ) 本来是哲学中的一个概念。近年来，本体被引入到了 语义网的建设中，用于w e b 信息的表示、组织与管理。 。 本体是描述特定领域的概念模型，通过明确、形式化地定义领域内的概念 以及概念之间的关系，使该领域内的概念具有清晰的机器可以理解的语义信 息，然后通过将领域中的概念去描述w e b 上的资源，为资源添加元数据，使 资源也具有机器可理解的明确的语义。 本课题就是利用本体论来解决1 1 2 中所描述的现有解题方法资源缺乏语 义化信息的问题。 1 1 4 解题方法语义化档案系统的提出 随着越来越多的学生参与到a c m 程序设计竞赛，学校自己要花很大力量 培训学生具备各种a c m 程序设计竞赛技能，学生也要自我培训各种技能，然 而j 下如1 1 2 所描述的，现有的解题方法资源不能全面的帮助学生解决a c m 程序设计问题。所以提出解题方法语义化档案系统来帮助解决上述问题。 整个档案系统先是对解题方法语义化，然后通过解题方法语义化的信息， 建立解题方法与解题方法之间的联系，通过这种联系可以帮助学生解决a c m 1 7 幕于领域知识的解题方法语义化档案系统的圳究 程序设计问题。例如，学生做了一道题目，可以找出与之解题方法相似的题目 提示学生。也可以帮助与本课题相关的另一个课题的研究内容出题器，进行出 题。例如，给定部分知识点，通过档案系统求出这些知识点能否组成一道题目。 解题方法语义化档案系统研究的是组成这个档案系统的方法，并不限定这 个档案库罩具体有些什么样的题目及相应的解题方法。但理沦模型应有实践检 验，本课题最后选取了一些题目并求出其解题方法，作为实例来验证这个方法 的可行性。 1 2 研究问题及技术路线 本课题的研究问题及解决方法阐述如下。 1 2 1 语义化解题方法的模型 现有解题方法资源仅仅描述了解题方法一部分信息，有的描述了算法部 分，有的只描述了数据结构部分，这些信息并不能够完整的构成一种解题方法。 这是没有将解题方法语义化所造成的。语义化解题方法的提取就是先要对解题 方法进行语义分析，抽象出解题方法的语义模型。然后在相同题目的情况下， 通过语义模型相同部分的不同内容重新组合得到不同的多个解题方法。 技术路线：本体论是研究“存在事物”的理沦。在计算机领域，本体被用来 描述特定领域的概念模型，通过明确、形式化地定义领域内的概念以及概念之 问的关系，使该领域内的概念具有清晰的机器可以理解的语义信息。因此，本 课题设计了解题方法语义模型，并采用本体描述语言o w l ( w e bo n t o l o g y l a n g u a g e ) 来描述机器可读的本体模型。元模型包括程序设计的五个部分，每 个部分可以自由添加实例。在元模型的建立中，可以采用p r o t 6 9 6 本体编辑器 来进行模型的编辑。在实例模型的建模过程中，可以借助p r o t 6 9 6 o w la p i 在应用程序中进行实例的创建。 基于领域知识的解题方法语义化档案系统的研究 1 2 2 语义化解题方法的形式概念格 一种解题方法仅仅描述对一道题目的一种解题方法。解题方法语义化档案 系统里面包含很多题目的多个解题方法，但是对其建立语义化的信息是为了边 一步建立解题方法之间的联系。解题方法形式概念格是建立解题方法与解题方 法之间联系的种方法。建立这种联系可以明确表示出解题方法与解题方法之 间的一种共性。其中即包含了相同题目的不同解题方法之间的联系，也包含了 不同题目的解题方法之间的联系。通过这种联系寻找到解题方法之间的共性， 学生可以对a c m 程序设计的解题方法有个彻底的了解，也可以根据自身情况 选择解决问题的先后顺序。其理论基础是应用了形式概念分析的理论。 技术路线：形式概念分析是由德国数学家w i l l e 于1 9 8 2 年首先提出的， 用于概念的发现、排序和显示，所有的概念连同它们之间的泛化、特化关系构 成一个概念格。从形式背景中生成概念格的过程实质上是一种概念聚类过程， 概念格可用于许多机器学习的任务，目前概念格在信息检索、软件工程和知识 发现等方面得到应用。 1 2 3 语义化解题方法的概念相似度 语义化解题方法的概念相似度是另外一种建立解题方法与解题方法之间 联系的方法。相似度是一个度量的概念，本文解题方法相似度的取值范围是 0 0 0 1 0 0 。0 0 0 表示两种解题方法完全不相似。1 0 0 表示两种解题方法完全相 等。其理论基础是应用了算法导论中网络流最大流最小费用的模型。 技术路线：解题方法相似度是通过语义距离和语义相似度的概念以及其度 量来描述解题方法属性距离、解题方法属性相似度、解题方法概念距离和解题 方法概念相似度的定义，再由属性相似度求出属性距离，通过最小费用最大流 模型求出概念距离，再转换成最终解题方法概念相似度。 1 2 4 解题方法语义化档案系统的应用 本课题描述了解题方法语义化档案系统的三种应用，一、分类；二、推荐； 1 9 暴于领域知识的解题方法语义化档案系统的j 【i j f 究 三、出题。 分类的对象是题目的解题方法，通过分类可以得出用户所指定的题目对应 的解题方法同样可以解决的其他题目。 推荐解题则是对用户已掌握的解题方法基础之上再进一步解决是现己掌 握的解题方法不能解决的问题。这种推荐是人性化的，找出最适合用户现在去 解决的问题，最容易现在去解决的问题。 出题的应用就是由出题器给定一些知识点，然后从解题方法档案系统中返 回是否这些知识点可以组成一道题目，知识点选于知识词典。 技术路线：分类和出题的理论基础主要是构建解题方法形式概念格，并且 求出解题方法形式背景h a s s e 图。从图中进行分析，得到分类和出题的结果。 推荐则利用语义化解题方法的概念相似度理论。 1 3 论文主要工作 1 ) 研究本体论以及语义w e b 的相关知识。学习和探索语义化和本体的建 模方法。 2 ) 通过对解题方法原理的分析，利用本体建模的方法建立解题方法语义 化模型。 3 ) 采用本体描述语言o w l 描述解题方法语义化模型，使该模型能够让 计算机理解。 4 ) 研究形式概念分析理论及相关知识。通过形式概念格对解题方法之间 建立联系。 5 ) 研究网络流知识以及最小费用最大流模型。通过该模型求解解题方法 之间的相似程度。 6 ) 搭建解题方法语义化档案系统结构。通过解题方法形式概念格和解题 方法语义相似度对整个系统做出应用。这里的应用简单概括为：分类、 推荐、出题。 2 0 基十领域知识的解题方法语义化档案系统的研究 1 4 与其他相关课题描述 本文有两个相关课题，一、面向程序设计知识资源自动发现的机器可解 读词典研究；二、基于网络知识资源语义化电子试卷自动生成系统研究， 简称出题器。 面向程序设计知识资源自动发现的机器可解读词典研究描述的是程序 设计领域的知识点，是解题方法底层的理论研究。解题方法也是由多个知识点 组合而成的。本课题设计的解题方法语义化模型涵盖了知识点的集合。 基于网络知识资源语义化电子试卷自动生成系统研究描述的是对 a c m 程序设计竞赛自动出题出卷的方法。本课题提供了出题器一个接口即 1 3 1 描述的出题的应用，出题器给定一些知识点，然后从解题方法档案系统 中返回是否这些知识点可以组成一道题目。 1 5 论文组织结构 本文的组织结构如下： 第一章为绪论部分，首先介绍了课题的背景，阐明了现存的资源的缺陷， 提出本课题的解决方案以及技术路线，并简单描述了本课题的应用意义，最后 介绍了与本课题相关的其它课题。 第二章介绍与本课题相关的理论。首先介绍了o w l 语言与本体建模和形 式概念分析，再对网络流的相关知识做出描述。 第三章提出了解题方法语义化模型，并给出解题记录模型到解题方法语义 化模型的构成方法。 第四章描述了建立解题方法之| 、日j 联系的两种技术路线，解题方法形式概念 格和解题方法相似度，并举例分析。 第五章描述了解题方法语义化档案系统的构成，并描述了档案系统的应 用。并对关键的技术做出介绍。 第六章为结束语。 幕于领域知识的解题方法语义化档案系统的研究 第二章相关理论技术 2 1o w l 语言与本体建模 语义网【3 删是对未来网络的一个设想，在这样的网络中，信息都被赋 予了明确的含义，机器能够自动地处理和集成网上可用的信息。语义网使用 x m l 5 删来定义定制的标签格式以及用r d f 7 】【8 】的灵活性来表达数据，下一步 需要的就是一种o n t o l o g y 9 1 【l o 】的网络语言( 比如o w l ) 来描述网络文档中的 术语的明确含义和它们之间的关系。 本体语言o w l ( w e bo n t o l o g yl a n g u a g e ) 是w 3 c i l1 推荐的本体描述语言， 由d a m l t l 2 1 和o i l 1 3 】所结合演变而来，是用来定义和实例化本体的。o w l ( w e bo n t o l o g yl a n g u a g e ) 适用于这样的应用，在这些应用中，不仅仅需要提 供给用户可读的文档内容，而且希望能够处理文档的内容信息。o w l 能够被 用于清晰地表达词汇表中的词条( t e r m ) 的含义以及这些词条之间的关系。而 这种对词条和它们之间的关系的表达就称作o n t o l o g y 。o w l 相对x m l 、r d f 和r d f s c h e m a 拥有更多的机制来表达语义，从而o w l 超越了x m l 、r d f 和r d f s c h e m a 仅仅能够表达网上机器可读的文档内容的能力【1 4 1 。 本体论有“客观事物”和“概念事物”的概念。“客观事物”是指客观世界中的 真实事物。“客观事物”被人脑认识后就变为人脑中的“概念事物”。人们通过事 物的特性来感知事物的存在，被人们感知的事物特性称为概念事物的属性【1 5 】。 在计算机领域中，本体论的“客观事物”就是软件系统所涉及的真实世界中的客 观事物，本体论的“概念事物”就是系统分析人员对客观事物的认识结果，用计 算机的术语来说就是对象( o b j e c t ) 。 通常所说的本体模型( o n t o l o g i c a lm o d e l ) 包含两方面的含义：元模型与 实例模型。本课题就是运用本体建模来构建解题方法语义化模型的。下面主要 介绍如何利用o w l 来进行本体建模。 幕于领域知识的解题方法语义化档案系统的研究 2 1 1o w l 本体模型的元模型 元模型是描述实例模型的模型。本体模型的建立是将现实世界中的具体事 物转换为概念事物的过程。本体论的建模元语包括“概念”和“实例”。从语义上 讲，概念就是对象的集合；而实例就是对象。例如，“个人知识结构”是一个概 念，而“学生a 的个人知识结构”是一个实例。 对应o w l 语言描述的本体，元模型中有如下这样几个重要的概念。 类( c l a s s ) ：在o w l 中，有两种不同的类命名的类( n a m e dc l a s s ) 和匿名的类( a n o n y m o u sc l a s s ) 。命名的类用来创建个体( i n d i v i d u a l ) ，而匿 名的类则用来明确命名的类的逻辑特征( 限制) 。 一个类可以是另一个类的子类( s u b c l a s s ) 。 属性( p r o p e r t y ) 属性是一个二元关系( b i n a r yr e l a t i o n ) ，分为两种 数据类型属性( d a t a t y p ep r o p e r t y ) 和对象属性( o b j e c tp r o p e r t y ) 。数据类型 属性指的是类的实例和r d f 实字、x m ls c h e m a 数据类型之问的关系；对象 属性指的是两个类的实例之间的关系。 属性特征( p r o p e r t yc h a r a c t e r i s t i c s ) ：通过明确属性的特征，可以提供更 强大的关于属性的推理的机制。 o传递属性( t r a n s i t i v ep r o p e r t y ) - p 伍a n d 尸仉矽i m p l i e sp 似矽 o 对称属性( s y m m e t r i cp r o p e r t y ) ：p “纠f f p 咖砂 o 函数型属性( f u n c t i o n a lp r o p e r t y ) ：尸伍a n d p 以矽i m p l i e s y 彳 0 逆属性( i n v e r s e o f ) ：p 1 阮纠i f f p 2 佛砂 。 反函数属性( i n v e r s ef u n c t i o n a lp r o p e r t y ) ：p 以矽a n dp ( z ，砂i m p l i e s y 2 z 属性限制( p r o p e r t yr e s t r i c t i o n s ) ：除了能够指定属性特性，我们还能够使 用多种方法进一步在一个明确的上下文中限制属性的值域。 oo w l ：a l l v a l u e s f r o m ：约束a l l v a l u e s f r o m 是对属性适用于某个类时 声明的。它的意思是这个属性用于这个类时有一个局部性值域约束。 摹于领域知识的解题方法语义化档案系统的j i j 究 0o w l ：s o m e v a l u e s f r o m ：是对属性适用于某个类时声明的。一个类可 能对它的属性有个约束，即这个属性至少有一个值是属于某个类型。 0 o w h m i n c a r d i n a l i t y ：基数是对属性应用于某个类时声明的。如果 就某个类而言，声明一个属性的m i n c a r d i n a l i t y ( 最小基数) 为l ，则这个 类的任何一个实例都通过该属性至少和一个个体相关。 0 o w l ：m a x c a r d i n a l i t y ：基数是对属性适用于某个类时声明的。如果 属性适用于某个类时的m a x c a r d i n a l i t y ( 最大基数) 为l ，则这个类的任意 实例都通过这个属性和至多一个个体关联。 在o w l 本体中，这些真实世界中的事物被抽象成一个个的类( c l a s s ) ， 并加以相关的属性( p r o p e r t y ) 来描述事物的特性。例如，解题方法库中的题 目信息可以被抽象成一个类p r o b l e m ，用o w l 语言表示为： 题目信息有题目编号、题目描述等特性，这些特性反映到o w l 本体模型 中表示为p r o b l e m 类具有数据类型属性( d a t a t y p ep r o p e r t y ) p r o b l e m i d 和 p r o b l e md e s c r i p i t i o n 等属性。用o w l 语言表示题目编号对应的数据类型属性 通过r d f s ：r a n g e 可以指定题目编号数据类型属性的取值范围为字符串型； 通过r d f s ：d o m a i n 则用来指定题目编号属性的作用领域为p r o b l e m 。 本体模型描述的，是一个特定领域罩重要的概念( 类) 和它们之间的关系， 并且为这个领域提供了一个词汇表以及这个词汇表中术语意义的计算机化的 规范【l6 1 。因此，解题方法本体元模型由相关的类、属性以及它们之间的关系 所组成，并且定义了这个领域内的一组相关词汇来更好地进行描述。 皋于领域知识的解题方法语义化卡当案系统的研究 2 1 2o w l 本体模型的实例模型 实例模型则是描述个体( i n d i v i d u a l ) 的模型。如果说解题方法库的题目 信息在o w l 本体中被抽象成了一个类_ p r o b l e m ，那么具体的题目a 则被 视为一个个体( i n d i v i d u a l ) 。简单地说，一个个体可以被声明为一个类的一个 成员。用o w l 语言可以这样声明一个p r o b l e m 类的个体p r o b l e ma ： 对本体模型进行实例化包括给个体的属性赋值的过程。例如，可以这样将 数据类型属性p r o b l e mn a m e 的值取为a 。 p r o b l e m 类中p r o b l e mn a m e 的取值范围指定了s t r i n g 类型，如果取i n t 类型的 值就被视为是错误的。 将本体模型的元模型进行实例化的过程，可以视为为组成这个元模型的类 和关系创建多个个体实例，并为相关的属性添加具体值的过程。一个本体的元 模型可以对应多个实例模型；一个解题方法的元模型也可对应多种解题方法本 题实例。 o w l 本体语言提供了丰富的语义上的支持，可以帮助解题方法语义化本 体模型的建模；而p r o t 6 9 6 一o w l a p i 1 7 】贝0 使在应用程序中大量建立个解题方法 语义模型的个体成为可能。 2 2 形式概念分析 形式概念分卡斤【1 8 1 是由德国数学家w i u e 于1 9 8 2 年【1 9 1 首先提出的，用于概 念的发现、排序和显示，所有的概念【2 0 】川连同它们之间的泛化、特化关系构 成一个概念格。从形式背景中生成概念格的过程实质上是一种概念聚类过程， 概念格可用于许多机器学习的任务，目前概念格在信息检索、软件工程和知识 发现等方面得到应用。以下是形式概念分析中4 个很重要的定义： 皋于领域知识的解题方法语义化档案系统的研究 定义1 ：形式背景【2 2 】【2 3 l ( f o r m a l c o n t e x t ) k = ( d ，a ，r ) 由集合d ，彳以及它 们之问的关系r 组成，d 中的元素称为对象( o b j e c t ) ，a t 的元素称为属性 ( a t t r i b u t e ) 。为了表示一个对象0 和一个属性a 在关系尺中，可以写成o r a 或 ( 0 ，a ) r 。 定义2 ：给定对象集合d ，对于对象子集m d ，定义 m = a av o m ，o r a ) 表示m 中全体对象所共有的属性集。对于属性子集 n a ，定义n = 0 0lv a n ，o r a ) 表示同时具有肿所有属性的对象的集 定义3 ：形式背景( 0 ，a ，r ) 中的一个形式概念( f o r m a l c o n c e p t ) 是一个对 ( e ，i ) ，其中e 互0 ，i a ，满足e = i 且，_ e ，e 、玢别称为形式概念( e ，i ) 的外延( e x t e n t ) 和内涵( i n t e n t ) 。8 ( 0 ，a ，r ) 表示形式背景( o ，a ，r ) 所有形式概 念的集合。 定义4 ：如果( 巨，i 。) ，( 易，1 2 ) 是两个形式概念2 4 麟1 ，如果巨e 2 ( 等同于 1 1 1 2 ) ，那么( e l ，i 。) 被称为( e 2 ，：) 的子概念，( 易，：) 被称为( e l ，i 。) 的超概 念，记为( 巨，( e 2 ，：) ，关系s 称为形式概念之间的序。按此方式有序的 ( d ，彳，尺) 所有形式概念的集合被表示为万( d ，a ，r ) ，并称为形式背景( 0 ，a ，r ) 的 概念格( c o n c e p t l a t t i c e ) 。 下面通过举例描述形式背景。 题目1 的解题方法需要用到枚举算法。 题目2 的解题方法需要用到大数算法。 题目a m 解题方法既要用到枚举算法，也要用到大数算法。 题目1 、题目2 、题目3 各自的解题方法组成了形式背景的对象集o 。下面 简写为l 、2 、3 。 基于领域知识的解题方法语义化档案系统的研究 这里，对象集d 所包含的所有属性即属性翱为，枚举( a ) 、大数( b ) 。 对象集d 和属性翱。可用下面二元关系表2 1 表示。“x ”表示该对象具有 相应的属性。 表2 - 1 形式背景表举例 性 ab 对翁 lx 2x 3xx 本课题运用了形式概念分析的知识建立解题方法语义化形式背景，通过形 式概念格的理论建立解题方法之间的联系。 2 3 语义距离与语义相似度 语言学家认为语义距离和语义相似度之间有着密切的联系。一般来说， 两个语义的语义距离越小，语义越相近，相似度越大；反之，两语义距离越大， 相似度越小。二者之间可以建立一个简单的对应关系，这种对应关系需要满足 以下几个条件： ( 1 ) 两个语义的距离为0 时，其相似度为l ； ( 2 ) 两个语义的距离为无穷大时，其相似度为o ； ( 3 ) 两个语义的距离越大，其相似度越小( 单调下降) ； ( 4 ) 语义相似度的区间为0 到1 。 对于两个语义断、，记其相似度s ( ，) ，语义距离为d ( 彬，吸) ， 可以定义一个满足上述条件的简单关系。 s ( ，) = d ( w j i , w 兰_ 2 一) + a r ( 式中，仅是一个可调节参数) 式2 1 通过转换可得 2 7 接十领域知识的解题方法语义化档案系统的研究 。( 2 赢川 式2 - 2 本课题运用语义距离与语义信息来定义解题方法概念距离和概念相似度 的度量的。 2 4 网络流最小费用最大流 在现实中，考虑从一个地点到另一个地点的运输问题，我不能只把距离作 为选择道路的唯一标准，因为也许某些较短的路可能没有人行道，它也可能很 泥泞，起伏，有时被泥石流阻塞，以及其他缺点。鉴于这些原因，我们在求得 所有的最大流后，更希望通过比较，得到一个最合理的方案，因为找到的所有 这样的流的工作的代价可能是承受不起，所以我们需要不仅能找到最大流 【2 7 】【2 8 】【2 9 1 的算法，而且还要找到最小代价最大流的算法。 2 4 1 网络流相关概念 前向弧和后向弧【3 0 】【3 i 】：在网络d = ( 矿，a ，c ) 中，如果对连接发点魄和 收点v t 的一条链p 方向规定为从魄到，则当链p 中弧( ，v ，) 的方向与规 定的方向一致时，称弧( v ，) 为前向弧，否则称为后向弧。不在这条链上的弧， 不定义前向弧和后向弧。 可扩充链【3 0 】【3 1 】：设局为一可行流( 假设为非负值) ，如果存在从发点 魄到收点的链p ，在链p 上，下列两条同时满足，则称p 为可扩充链： ( 1 ) 对于p 上的前向弧( v f ，v ，) 有f i j c i j 。 ( 2 ) 对于p 上的后向弧( v ，) 有舻o 。 最小费用最大流【3 2 】【3 3 】：在网络d = ( y ，彳，c ) 中，对应每一条弧 ( ，v ) a ，除了已给定的弧( 1 ，y ) 的容量c f ，