融合概念格约简的中文领域本体学习方法

侯丽鑫, 郑山红, 贺海涛, 赵 辉, 韩 冬

(长春工业大学 a. 计算机科学与工程学院； b. 软件职业技术学院, 长春 130012)

0 引 言

本体学习是指自动或半自动地构建本体, 目的是利用知识获取技术降低本体构建的开销,目前本体学习已成为本体领域的研究热点之一。形式概念分析(FCA： Formal Concept Analysis)[1]与本体有许多相似之处[2], 近年来, 人们开始尝试将FCA应用于本体学习领域。Obitkom等[3]将FCA应用于分布式的领域本体开发环境, 通过构建概念格探寻潜在的对象和属性, 并将现有的和潜在的实体以可视化的方式自动呈现； 张斌等[4]利用FCA与统计理论进行政务本体学习。概念格是FCA的核心数据结构, 在机器学习、 模式识别、 决策分析等领域应用广泛[5-8]。概念格约简理论[9,10]能更容易发现形式背景中隐含的知识, 也使这些知识的表示变得更简单, 提高概念格构造的效率。

笔者在已有工作[11]的基础上, 提出了一种融合概念格约简的中文领域本体学习方法。该方法应用语义依存分析技术获取领域形式背景, 将概念格约简应用于概念格的构造, 通过对象约简和属性约简完成初始概念格的构造, 再采用约简概念格修复得到完整概念格, 最后根据映射规则完成中文领域本体的生成。通过对萝藦科植物及其药用性的领域文本进行学习, 得到萝藦科植物领域本体, 提高了本体构建的效率。

1 基于语义依存的形式背景的获取

形式背景是基于FCA进行本体学习的基础, 笔者将语义依存技术用于从中文领域文本中获取形式背景。下面给出形式背景的定义及从领域文本中获取形式背景的具体算法。

定义1 形式背景是三元组K=(G,M,I), 其中G和M分别是对象集和属性集, 二元关系I⊆G×M。通常用(g,m)∈I或gIm, 表示“对象g拥有属性m”。

形式背景是采用FCA方法进行本体学习的基础。笔者借鉴AIFB研究机构在IST-Dot Kom项目中应用Philipp Cimiano方法[12]的思想, 利用基于汉语的依存语法分析器[13], 给定文本集中的一个句子作为输入, 产生一棵标注依存关系、 语义角色的语法分析树,从中抽取句子的主干。将主语作为对象, 将对应出现的宾语作为描述该对象的属性, 这两部分匹配后作为一个对象-属性对放入形式背景中。具体算法如下。

输入： 中文领域文本。

输出： 对象属性对构成形式背景。

Step 1 初始化HashMap, 用于存储对象-属性对；

Step 2 基于CRF(Conditional Random Fields)模型, 对文本集中的每句子i(i是句子的编号)进行分词, 得到wordList；

Step 3 对句子i中的每个词j(j为词在句中的编号), 采用GParser(全称为Graph-based Parser)输出该词在句子中的依存关系；

Step 4 判断词j的依存关系的类型, 若依存关系的类型为“SBV(Subject-Verb)”, 则词j为一个对象； 若依存关系的类型为“VOB(Verb-Object)”, 则词j为对象对应的属性；

Step 5 以HashMap中所有的对象G及属性M构成形式背景K(G,M,I)。

以“牛皮消是一种草本植物。”为例, 采用ltp-service的语义依存分析结果如表1所示。

表1 示例的语义依存分析结果

从表1可以看出, “白薇”的依存句法分析的依存关系为“SBV”, 即主谓关系；“是”为核心(HED： Head), 即“是”为谓语； “草本植物”的依存句法分析的依存关系为“VOB”, 即动宾关系。因此可以得出下面的结果

name=“白薇”; value=“草本植物”; hashmap.put(name,value);

最终得到一组对象属性对是： (“白薇”, “草本植物”)。

基于提出的基于语义依存的形式背景获取方法, 通过对多篇介绍萝藦科植物以及它们的药用性的领域文本进行学习, 得到的部分形式背景如表2所示。

表2 萝藦科植物形式背景

2 基于概念格约简的概念格构造

概念格是FCA的核心, 体现概念间的层次(泛化)关系。它是概念格构造算法[14,15]作用于形式背景的结果。为了提高概念格构造效率, 笔者引入概念格约简理论。为方便讨论, 给出如下定义。

定义2 对于A⊆G和B⊆M, 可定义如下两种映射

f(A)={m∈M|∀g∈A,∃(g,m)∈I}

g(B)={g∈G|∀m∈B,∃(g,m)∈I}

定义3 若A⊆G,B⊆M, 满足f(A)=B且g(B)=A, 则C=(A,B)是K=(G,M,I)的一个形式概念。A称为C的外延, 记作Ext(C),B称为C的内涵, 记作Int(C)。

定义4 形式背景的概念格记作L(K),L(K)是一个偏序集, 由形式背景中存在层次包含关系的概念形成, 即(A1,B1)(A2,B2)⟺A1⊆A2(且B2⊆B1)。此时(A2,B2)是超概念, (A1,B1)是子概念。

定义5 设L(G,M1,I1)和L(G,M2,I2)是两个概念格。若对于∀(A2,B2)∈L(G,M2,I2), ∃(A1,B1)∈L(G,M1,I1), 使A1=A2, 则称L(G,M1,I1)细于L(G,M2,I2), 记作L(G,M1,I1)≤L(G,M2,I2)。若L(G,M1,I1)≤L(G,M2,I2), 且L(G,M2,I2)≤L(G,M1,I1), 则称两个概念格同构, 记作L(G,M1,I1)≅L(G,M2,I2)。

定义6 在形式背景K=(G,M,I)中, 若∃A⊆M,IA=I∩(G×A), 使L(G,A,IA)≅L(G,M,I), 则称A是K=(G,M,I)的协调集。如果∀a∈A, 有L(G,A-{a},IA-{a})不同构于L(G,M,I), 则称A是K=(G,M,I)的约简。

2.1 形式背景的对象约简和属性约简

对于形式背景K=(G,M,I), 既可以对对象又可以对属性进行约简。下面给出对象、 属性约简定理。为方便讨论给出如下定义。

定义7 对于形式背景K=(G,M,I), 其中G={g1,g2,…,gm},M={m1,m2,…,mn},I⊆G×M。对于∀g∈G, ∀m∈M, 定义R(g)={m∈M|gIm}为对象的属性空间,D(m)={g∈G|gIm}为属性的对象空间。

基于定义7, 根据各对象的属性空间之间的关系和各属性的对象空间之间的关系, 描述如下4条形式背景的约简定理。

定理1(对象的交约简) 在形式背景(G,M,I)中：

1) 如果∃gi,gj∈G,i,j∈[1,m], 使R(gi)=R(gj), 则对象gi或gj是冗余的, 因此, 可约简gi或gj所在的行;

2) 如果∃gi,gj,gl∈G,i,j,l∈[1,m], 使R(gl)⊂R(gi),R(gl)⊂R(gj)且R(gi)∩R(gj)=R(gl), 则对象gl是冗余的, 因此, 可约简gl所在的行。

定理2(对象的全约简) 在形式背景(G,M,I)中, 如果∃gi∈G,i∈[1,m], 使R(gi)=M, 则对象gi是冗余的, 则可约简gi所在的行。

定理3(属性的交约简) 在形式背景(G,M,I)中：

1) 如果∃mi,mj∈M,i,j∈[1,n], 使D(mi)=D(mj), 则属性mi或mj是冗余的, 因此, 可约简mi或mj所在的列;

2) 如果∃mi,mj,ml∈M,i,j,l∈[1,n], 使D(ml)⊂D(mi),D(ml)⊂D(mj)且D(mi)∩D(mj)=D(ml), 则属性ml是冗余的, 因此, 可约简ml所在的列。

定理4(属性的全约简) 在形式背景(G,M,I)中, 如果∃mi∈M,i∈[1,n], 使D(mi)=G, 则属性mi是冗余的, 因此, 可约简mi所在的列。

由于渐进式构造算法可根据形式背景的变化对原有概念格做相应调整, 而不用重新构造概念格, 从而节省了大量时间。因此渐进式构造算法一直是概念格构造算法的研究热点。笔者采用基于对象的渐进式构造算法----Godin算法, 在概念格构造过程中引入概念格属性约简理论, 采用以上约简定理, 对已获得的形式背景进行约简； 以约简后的形式背景为数据源, 采用Godin算法构造概念格。

基于表2萝藦科植物形式背景, 概念格构造过程如下。

步骤1 根据表2, 列出所有属性的对象空间和对象的属性空间:

D(草本植物)={牛皮消,白薇,徐长卿,一枝香,萝藦}D(藤本植物)={夜来香}

D(止咳)={白薇}D(祛风湿)={徐长卿,一枝香}D(圆锥花絮)={徐长卿,一枝香}

D(聚伞花序)={牛皮消,夜来香}D(伞形花序)={夜来香}D(总状花序)={萝藦}

R(牛皮消)={草本植物,聚伞花序}R(白薇)={草本植物,止咳}R(徐长卿)={草本植物,祛风湿,圆锥花絮}

R(一枝香)={草本植物,祛风湿,圆锥花絮}R(萝藦)={草本植物,总状花序}R(夜来香)={藤本植物,聚伞花序,伞形花序}

步骤2 分析D(m)之间的关系和R(g)之间的关系, 得到：

1)D(祛风湿)=D(圆锥花絮)；

2)D(藤本植物)=D(伞形花序)；

3)R(徐长卿)=R(一枝香)。

步骤3 根据D(m)、R(g)间的关系结果以及定理1、 定理3, 约简“圆锥花絮”、 “伞形花序”所在的列及“一枝香”所在的行, 得到的约简形式背景如表3所示。

表3 约简的萝藦科形式背景

步骤4 采用Godin算法对表3的形式背景构造概念格, 其结果如图1所示。

图1 约简概念格

图1的Hasse图是一个简化的概念格视图, 实际上每个节点都包含一个对象集和一个属性集, 每个节点的对象集合由该节点下所有子节点中出现的对象集构成, 而每个节点的属性集合则由该节点的所有父节点中出现的属性集构成。

由比较表2和表3结果可知, 构造概念格时, 运算次数由原来的26+28次减少到25+26次, 即运算效率提高70%。

2.2 约简概念格的修复

为了保持概念格约简前后的同构性, 笔者根据2.1节采用的定理1、 定理3得出如下概念格修复定理。

定理5(直接添加约简项法) 对于形式背景(G,M,I), 如果采用R(gi)=R(gj),D(mi)=D(mj)的方式约简gj所在的行和mj所在的列, 则在修复概念格时直接将gj,mj添加到约简格中所有格节点中。

根据概念格修复定理, 对图1的约简概念格进行修复, 即将“圆锥花絮”直接添加到约简概念格中内涵含有“祛风湿”的格节点中。将“伞形花序”直接添加到约简概念格中内涵含有“藤本植物”的格节点中。将“一枝香”直接添加到约简概念格中外延含有“徐长卿”的格节点中。修复后完整的概念格如图2所示。

图2 萝藦科植物完整概念格

3 概念格到中文领域本体的映射

图3 萝藦科植物本体

由定义4可知, 概念格是一种概念聚类的过程, 体现了概念间的层次关系, 即超概念是子概念的泛化, 相应的子概念是超概念的特化, 因此, 将概念格中的每个概念节点映射成本体中的一个Class, 层次关系映射成本体中的subClassOf关系； 概念格节点的外延表示该格节点所包含的对象, 相当于类的实例, 因此映射成Class的Individual； 概念格节点的内涵表示该格节点中的对象共同拥有的属性, 相当于类的属性, 因此将该节点的内涵映射成Class的DatatypeProperty。

采用上述映射规则, 实现萝藦科植物概念格到萝藦科植物本体的映射, 并使用斯坦福大学开发的本体编辑器Protégé中的OntoGraf插件对构建的中文领域本体进行图形化描述(见图3)。

4 结 语

笔者提出一种融合概念格约简的中文领域本体学习方法, 并以多篇有关萝藦科植物及其药用性的中文文本为数据源, 应用该方法进行中文领域本体学习, 最终得到了萝藦科植物本体, 并用可视化的方式描述。在学习过程中, 采用语义依存分析技术获取形式背景, 基于概念格约简理论构造概念格, 然后根据映射规则实现概念格到领域本体的映射。将FCA应用于本体构建, 既能发挥形式概念分析自动客观提取语义的特点, 又能使构建的本体在知识重用和知识共享等应用层面上比单纯的分类法具有更大的优势。将概念格约简理论应用于概念格构造, 实验验证可提高概念格构建效率。实验结果表明, 该本体学习方法能提高本体构建的效率和形式化程度。但仍有需要改进的地方, 下一步会设计更明确的映射算法实现概念格到本体的映射, 减少人工参与, 进一步提高本体学习的自动化程度。

参考文献：

[1]WILLE R. Restructuring Lattice Theory: An Approach Based on Hierarchies of Concept [C]∥ICFCA 2009. Berlin: Springer-Verlag, 2009: 314-339.

[2]欧阳纯萍, 胡长军, 李扬, 等. 一种基于FCA的面向关系数据库的本体学习方法 [J]. 计算机科学, 2011, 12(12): 167-171.

OUYANG Chun-ping, HU Chang-jun, LI Yang, et al. Approach of Ontology Learning from Relational Database on FCA [J]. Computer Science, 2011, 12(12): 167-171.

[4]张斌, 刘增良, 余达太, 等. 基于形式概念分析与统计理论的本体构建模型 [J]. 计算机应用研究, 2011, 28(1): 111-113.

ZHANG Bin, LIU Zeng-liang, YU Da-tai, et al. Ontology Construction Model Based on Formal Concept Analysis and Statistical Theory [J]. Application Research of Computers, 2011, 28(1): 111-113.

[5]PENG Qiang-qiang, DU Ya-jun, HAI Yu-feng, et al. Topic Specific Crawling on the Web with Concept Context Graph Based on FCA [C]∥Proc of Int Conf on Management and Service Science. Piscataway, NJ: IEEE, 2009: 1-4.

[6]SHYNG J Y, SHIEH H M, TZENG G H. An Integration Method Combining Rough Set Theory with Formal Concept Analysis for Personal Investment Portfolios [J]. Knowledge-Based System, 2010, 23(6): 586-597.

[7]SNASEL V, HORAK Z, KOCIBOVA J, et al. A Analyzing Social Networks Using FCA: Complexity Aspects [C]∥Proc of 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence(WI) and Intelligent Agent Technologies(IAT). Piscataway, NJ: IEEE, 2009: 38-41.

[8]LI Yang, YANG Xu. Decision Making with Uncertainty Information Based on Lattice-Valued Fuzzy Concept Lattice [J]. International Journal of General Systems, 2010, 39(3): 235-253.

[9]张文修, 魏玲, 祁建军. 概念格的属性约简理论与方法 [J]. 中国科学E辑: 信息科学, 2005, 35(6): 628-639.

ZHANG Wen-xiu, WEI Ling, QI Jian-jun. The Theory and Method of Concept Lattice Attributes Reduction [J]. Science in China Series E: Technological Sciences,2005, 35(6): 628-639.

[10]杨丽, 徐扬. 基于形式背景的概念格约简及其修复 [J]. 计算机工程, 2008, 34(9): 22-24.

YANG Li, XU Yang. Concept Lattice Reduction and Reparation Based on Formal Context [J]. Computer Engineering, 2008, 34(9): 22-24.

[11]侯丽鑫, 郑山红, 赵辉, 等. 基于P-集合和FCA的中文领域本体学习方法 [J]. 吉林大学学报: 理学版, 2013, 51(4): 659-665.

HOU Li-xin, ZHENG Shan-hong, ZHAO Hui, et al. Research on Chinese Domain Ontology Learning Based on P-Sets and Formal Concept Analysis [J]. Journal of Jilin University: Science Edition, 2013, 51(4): 659-665.

[12]黄美丽, 刘宗田. 基于形式概念分析的领域本体构建方法研究 [J]. 计算机科学, 2006, 33(1): 210-212.

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.

[13]CHE Wan-xiang, LI Zheng-hua, LIU Ting. LTP: A Chinese Language Technology Platform [C]∥Proceedings of the Coling 2010: Demonstrations. Beijing, China： [s.n.], 2010: 13-16.

[14]BAIXERIES J, SZATHMARY L, VALTCHEV P, et al. Yet a Faster Algorithm for Building the Hasse Diagram of a Concept Lattice [C]∥ICFCA 2009. Berlin, Germany: Springer-Verlag, 2009: 162-177.

[15]蒋义勇, 张继福, 张素兰. 基于链表结构的概念格渐进式构造 [J]. 计算机工程与应用, 2007, 43(11): 178-180.

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.