基于P-集合和FCA的中文领域本体学习方法

侯丽鑫,郑山红,赵 辉,董亚则,彭馨仪

(1.长春工业大学 计算机科学与工程学院,长春 130012;2.长春工业大学 软件职业技术学院,长春 130012)

1 预备知识

本体是共享概念模型的明确形式化规范说明[1].它作为一种能在语义和知识层次上描述信息系统的概念模型,实现了人们从对信息的理解到计算机能够处理数据和信息的连接,是语义网的核心.本体应用的基础是本体构建.虽然目前已构建出许多领域本体,但大部分领域本体都是在特定的领域为特定的目的而构建,没有统一规范化的构建方法,且多数都是手工构建.手工构建本体费时、 费力,难应用于复杂领域及自动更新.

本体学习是本体领域的研究热点,多数采用自然语言处理技术、 统计学和机器学习等方法进行本体学习.在中文环境下的本体学习研究目前较少.

FCA(formal concept analysis)是Wille[2]提出的一种建立在数学基础上,从形式背景进行数据分析和规则提取的工具,用于概念的发现、 聚类和显示.形式概念分析与本体有许多共同点[3],如都采用形式化方式描述概念及其间的关系,因此将形式概念分析应用于本体学习是合理的.事实上,各领域的信息都是动态变化的,而P-集合[4-7]体现了属性迁移带来领域对象的动态变化,因此本文将P-集合理论引入到形式背景的获取,提出一种基于形式概念分析的中文领域本体学习方法.

1.1 P-集合

定义1给定普通集Y={y1,y2,…,yn}⊂U,其属性集a={a1,a2,…,aj}⊂V,则Y的内P-集合为

(1)

(2)

aF=a∪{a|∃β∈V,β∉a,f(β)=ω∈a,f∈F}.

(3)

定义2给定普通集Y={y1,y2,…,yn}⊂U,其属性集a={a1,a2,…,aj}⊂V,则Y的外P-集合为

YF=Y∪Y+;

(4)

Y的F-元素补充集合为

Y+={u|u∈U,u∉Y,f(u)=y′∈Y,f∈F};

(5)

(6)

1.2 形式概念分析

形式背景和概念格等是形式概念分析(FCA)的重要组成部分.FCA在Web语义检索、 本体研究、 知识发现和软件工程等领域应用广泛.

定义4形式背景K∶=(O,A,I),其中:O表示对象集(objects);A表示属性集(attributes);I表示O和A之间的二元关系,即I⊆O×A.表1列出了一些形式背景示例,其中：行表示对象;列表示属性;行列交叉处表示对象具有的属性.

表1 形式背景示例Table 1 Examples of formal context

定义5(o,a)∈I或oIa,表示“属性a是对象o的属性之一”.对任一对象子集X,可定义

X′={a∈A|∀x∈X,∃(x,a)∈I},

表示子集X中全体对象所共有的属性.同理,对任一属性子集Y,也可定义

Y′={o∈O|∀y∈Y,∃(o,y)∈I},

表示包含Y中所有属性全体对象的集合.

定义6若X⊆O,Y⊆A,满足X′=Y且Y′=X,则C=(X,Y)是形式背景K=(O,A,I)的一个形式概念,X称为C的外延,Y称为C的内涵.

定义7形式背景中所有形式概念(如(x1,y1),(x2,y2)),如果存在因概念层次包含关系(子概念-超概念)而形成的偏序,即

(x1,y1)(x2,y2) ⟺x1⊆x2(且y2⊆y1),

则该偏序关系集为形式背景的概念格,此时(x2,y2)是(x1,y1)的超概念,(x1,y1)是(x2,y2)的子概念.

图1 概念格的Hasse图Fig.1 Hasse diagram of concept lattice

概念格是形式概念分析理论中的核心数据结构,由其定义可知,概念格是根据二元关系建立的,反映概念间泛化和特化关系的概念层次结构,并能以图形化的方式(如Hasse图)表示.表1示例形式背景的概念格如图1所示.

1.3 P-集合与FCA的关系

通过P-集合与FCA的定义知二者有相似之处,即都具有一定属性的个体集.P-集合体现了属性迁移带来的个体集变化,而FCA侧重于概念的聚类.概念格体现层次关系,如图1中的概念节点(Ø,abcd),(34,acd),(134,ad),(1234,a),它们的个体数随属性数的减少而增多,由P-集合的定义知,这些概念节点构成的集合即为一个P-集合.

2 基于P-集合和FCA的本体学习方法

2.1 基于P-集合的形式背景获取

形式背景是采用FCA方法进行本体学习的基础.本体在实际应用中需要进化,为提高本体重用性,满足形式背景变化的需求,本文将P-集合理论引入到形式背景获取中.先采用第三代智能分词系统3GWS对文本进行词性标注,得到带词性的文本数据,再按汉语语法规则,从中抽取出句子的主干.将主语(名词、 名词性短语等)作为对象,对应出现的宾语作为描述该对象的属性,这两部分匹配后作为一个对象-属性对置于形式背景中.如“大豆虽然生活在陆地,但是它需要水”通过3GWS进行分析和词性标注后,得到如下信息：

“大豆/n虽然/c生活/vi在/p陆地/n,/wd但是/c它/rr需要/v水/n./wj”.

根据以上标注信息,抽取句子的主干,可得到(大豆,生活在陆地)和(大豆,需要水)这样的对象属性对,但少量数据获取的形式背景有时不能有效地区分个体,见表2.

将P-集合引入形式背景的获取,对多文本学习得到更多属性,自动更新形式背景,以便有效地区分个体,得到质量较高的形式背景(表3).

表2 未能有效区分个体的形式背景Table 2 Formal context failed to distinguish between individuals

表3 能有效区分个体的形式背景Table 3 Formal context to distinguish between individuals effectively

2.2 从形式背景到概念格的构造

概念格是FCA的核心,是概念格构造算法作用于形式背景的结果.概念格不受数据或属性排列顺序的影响,即一个形式背景有唯一的概念格.概念格构造算法可分为渐近式构造算法[8-9]和批处理构造算法[10-13].

渐近式构造算法又分为基于对象的渐近式构造算法和基于属性的渐近式构造算法两类.经典的渐近式构造算法主要包括Capineto算法、 Earpinet算法和Godin算法等.批处理构造算法出现相对较早,基本思想是：先根据对象及属性生成所有概念,然后建立所有概念节点间的直接前趋和直接后继关系,即父子关系,以此完成概念格的整个构建过程.按照构造概念格方式不同,又可分为自底向上、 自顶向下和枚举算法3类.经典的批处理算法有Bordat算法、 FastConcept算法和Chein算法等.

本文采用基于对象的渐近式构造算法----Godin算法构造概念格.Godin算法是Godin等[14]提出的一种渐近式构造算法,在概念格生成过程中需要解决两个问题[15]: 1) 节点的更新;2) 格节点间边的更新.新生成的概念格节点类型有3种: 不变节点、 更新节点和新增节点.

定义8设L(K)是形式背景所对应的概念格,Mi=(xi,yi)是格上的任意一个节点,新增对象xj所对应的属性集为yj,根据yj和yi之间的关系,将加入xj后的新概念格节点分为3种类型：

1) 如果yj∩yi=Ø,则Mi=(xi,yi)∈L′(K),Mi称为不变节点;

2) 如果yi⊂yj,则将M修改为M′=(xi∪xj,yi),加入L′(K)中,M′称为更新节点;

3) 如果yj∩yi≠Ø,且不存在((yj∩yi)′,yj∩yi)∈L(K),则生成一个新节点M′=(xj∪xi,jj∩yi)加入到L′(K)中,M′称为新增节点.

基于Godin算法构造概念格的算法流程如下：

1) 初始化一个空概念格；

2) 从形式背景中取出一个对象O；

① 从L(K)中依次取出形式概念Mi=(xi,yi)；

3) 将2)中的新增节点插入概念格中,并更新节点间的边；

4) 循环2)和3),直到生成完整的概念格.

2.3 概念格到OWL本体模型的映射

概念格是一种概念聚类的过程,体现概念间的层次(泛化)关系.将概念格节点之间的层次关系映射为OWL本体中的父类-子类关系； 概念格节点映射为本体类； 概念格节点的外延映射为对应类的实例； 概念格节点的内涵映射为对应类的数据类型属性.由于所有子类将继承父类的属性和实例,因此,在实际映射过程中,为节省资源只需将每个节点类相对于其父节点新增的属性映射为其代表类的属性,相对于其子节点新增的对象映射为其代表类的实例.

本文采用W3C推荐的本体描述语言OWL描述映射得到的本体.按以上映射原理,得到FCA格元素与OWL中语义要素的如下映射规则定义.

定义9设O∶=(C,root,c)是领域本体,其中:C为概念集;root为根元素;c为概念间的层次关系；L(K)是形式背景所对应的概念格,Hi=(xi,yi)和Hj=(xj,yj)是格L(K)上的任意两个格节点,e是FCA格元素,C是Hi对应的类名,supC是Hj对应的类名,则定义f:L(K)→O为概念格到领域本体的映射.映射规则如下：

1)R1: IFeisHiTHEN 〈owl: Class rdf: about=“#C”/〉 INO;

2)R2：IFeisHiANDHi≤HjTHEN

临近年底，备受关注的《个人所得税专项附加扣除暂行办法》（以下简称《暂行办法》）终于正式亮相，标志着我国综合与分类相结合的个税改革迈出关键一步，释放出更加惠民的积极信号。

〈owl: Class rdf: about=“#C”〉

〈rdfs: subClassOf rdf: resource=“#supC”/〉

〈/owl: Class〉 INO;

3)R3：IFe∈xiTHEN

〈owl: NamedIndividual rdf: about=“#xi”〉

〈rdf: type rdf: resource=“#C”/〉

〈/owl: NamedIndividual〉 INO;

4)R4：IFe∈yiTHEN

〈owl: DatatypeProperty rdf: about=“#yj”/〉

〈rdfs: domain rdf: resource=“#C”/〉

〈/owl: DatatypeProperty〉 INO.

基于定义9,概念格到OWL本体映射的算法设计如下：

1) 初始化一个空本体O；

2) 将概念格L(K)最顶层节点根据规则R1映射为root；

3) 取根节点的子节点Hi=(xi,yi)；

4) 应用映射规则：

① 对格节点Hi使用规则R1；

② 对根节点与子节点间的层次关系使用规则R2；

④ 对子节点Hi相对父节点新增的属性使用规则R4；

6) 重复执行3)～5),直到整个概念格映射完成.

3 实验结果

为验证本文所提出的基于P-集合和FCA的中文领域本体学习方法的可行性,下面应用该方法对多篇生物和水的文本进行学习,学习过程分为3个阶段：1) 从文本中获取形式背景； 2) 基于形式背景构造概念格； 3) 概念格到本体模型的映射.最终得到一个关于生物和水的中文领域本体.

3.1 学习生物和水的文本获取形式背景

为提高本体的可重用性,满足本体进化过程中形式背景动态变化的需求,采用本文提出的基于P-集合的形式背景获取方法,对多篇生物和水的文本进行学习,学习完成后给予修正,最终得到的形式背景列于表4.

表4 生物和水的形式背景Table 4 Formal context about biology and water

1.大豆;2.玉米;3.水草;4.娃娃鱼;5.蛙;6.狗;7.芦苇;8.水蛭.a.需要水;b.生活在水中;c.生活在陆地;d.有叶绿素;e.双子叶;f.单子叶;g.能运动;h.有四肢;i.哺乳.图2 生物和水的概念格Fig.2 Concept lattice about biology and water

3.2 构造概念格

采用Godin算法,先对生物和水的形式背景进行形式概念分析,再对部分节点位置进行调整,最终得到生物和水的概念格如图2所示.

由Hasse图可知概念格从本质上描述了概念之间的泛化和特化关系,位于上方的是父节点,位于下方的是子节点.概念格中的每个节点都是一个形式概念,由形式概念定义知最顶层的节点包含的对象最多,属性最少.

3.3 中文领域本体的生成

基于FCA格元素与OWL本体描述的映射规则,将图2中的概念格映射为中文领域本体,并使用美国斯坦福大学开发的本体编辑器Protégé中的OntoGraf插件对构建的中文领域本体进行图形化描述,如图3所示.

图3 生物和水领域本体Fig.3 Domain ontology about biology and water

4 实验对比分析

文献[7]中的Philipp Cimiano方法是使用一个自然语言的解析器,通过该解析器从领域文本中的每个句子得到一颗语法树,由语法树直接得到动词对象间的依赖关系； 进一步通过词典查询,对提取的动词和对象用词的原形规范化表示.如bought/buys转换成原形buy,并给动词加上后缀 -able,使其更像是属性； 最后,将FCA中的概念和本体中的概念直接等同,得到概念格,由概念格得领域本体.

通过本文提出的本体学习方法与Philipp Cimiano方法比较分析得出：本文提出的方法不仅能从非结构化的中文领域数据中得到期望的本体,还能发挥形式概念分析自动客观提取语义的特点； 将P-集合引入到形式背景的获取,使获取的形式背景既有利于个体的有效区分,又不会使属性集过于庞大导致系统资源的浪费； 本文给出的概念格到OWL本体映射算法,不仅包含了层次关系的映射,还包括个体及对象属性的映射,使得到的本体比使用Philipp Cimiano方法得到的本体更丰富完整.

[1] Studer R,Benjamins V R,Fensel D.Knowledge Enineering: Principles and Methods [J].Data and Knowledge Engineering,1998,25(1/2): 161-197.

[2] Wille R.Restructuring Lattice Theory: An Approach Based on Hierarchies of Concept [C]//Lecture Notes in Computer Science.Berlin: Springer-Verlag,2009: 314-339.

[3] OUYANG Chun-ping,HU Chang-jun,LI Yang,et al.Approach of Ontology Learning from Relational Database on FCA [J].Computer Science,2011,38(12): 167-171.(欧阳纯萍,胡长军,李扬,等.一种基于FCA的面向关系数据库的本体学习方法 [J].计算机科学,2011,38(12): 167-171.)

[4] SHI Kai-quan.P-sets and Its Applied Characteristics [J].Computer Science,2010,37(8)：1-8.(史开泉.P-集合与它的应用特征 [J].计算机科学,2010,37(8)：1-8.)

[5] WANG Yang,SHI Jin-chang,SHI Kai-quan.P-Sets andF-Memory Information Characteristic: Application [J].Computer Science,2011,38(5): 212-215.(汪洋,史金昌,史开泉.P-集合与F-记忆信息特性: 应用 [J].计算机科学,2011,38(5): 212-215.)

[6] YAN Hong-can,WANG Jian,LIU Bao-xiang.Ontology Background Extraction Method Based on P-Sets [J].Application Research of Computers,2012,29(6): 2196-2199.(阎红灿,王坚,刘保相.基于P-集合的本体形式背景抽取 [J].计算机应用研究,2012,29(6): 2196-2199.)

[7] HUANG Mei-li,LIU Zong-tian.Research on Domain Ontology Building Methods Based on Formal Concept Analysis [J].Computer Science,2006,33(1): 210-212.(黄美丽,刘宗田.基于形式概念分析的领域本体构建方法研究 [J].计算机科学,2006,33(1): 210-212.)

[8] Merwe D,van der,Obiedkov S,Kourie D.AddIntent：A New Incremental Algorithm for Constructing Concept Lattices [C]//Proc of the 2nd Int Conf on Formal Concept Analysis.Berlin：Springer,2004：372-385.

[9] LIU Zong-tian,QIANG Yu,ZHOU Wen,et al.A Fuzzy Concept Lattice Model and Its Incremental Construction Algorithm [J].Chinese Journal of Computers,2007,30(2)：184-188.(刘宗田,强宇,周文,等.一种模糊概念格模型及其渐近式构造算法 [J].计算机学报,2007,30(2)：184-188.)

[10] Kuznesov S O,Obiedkov S A.Comparing Performance of Algorithms for Generating Concept Lattices [J].Journal of Experimental &Theoretical Artificial Intelligence,2002,14(2/3): 189-216.

[11] Baixeries J,Szathmary L,Valtchev P,et al.Yet a Faster Algorithm for Building the Hasse Diagram of a Concept Lattice [C]//Lecture Notes in Computer Science.Berlin: Springer-Verlag,2009: 162-177.

[12] CHEN Qing-yan.Improvement on Bordat Algorithm for Constructing Concept Lattice [J].Computer Engineering and Applications， 2010， 46(35)：33-35.(陈庆燕.Bordat 概念格构造算法的改进 [J].计算机工程与应用， 2010， 46(35)：33-35.)

[13] JI Tong-kun.The Research and Improvement of Concept Lattice Chein Algorithm [D].Guangzhou: South China University of Technology， 2012.(纪彤坤.概念格Chein算法的研究与改进 [D].广州：华南理工大学， 2012.)

[14] Godin R,Missaoui R,Alaoui H.Incremental Concept Formation Algorithms Based on Galois (Concept) Lattices [J].Computational Intelligence,1995,11(2): 246-267.

[15] JIANG Yi-yong,ZHANG Ji-fu,ZHANG Su-lan.Incremental Construction of Concept Lattice Based on Linked List Structure [J].Computer Engineering and Applications,2007,43(11): 178-180.(蒋义勇,张继福,张素兰.基于链表结构的概念格渐近式构造 [J].计算机工程与应用,2007,43(11): 178-180.)