侯麗鑫,鄭山紅,趙 輝,董亞則,彭馨儀

(1.長春工業(yè)大學 計算機科學與工程學院,長春 130012;2.長春工業(yè)大學 軟件職業(yè)技術學院,長春 130012)

1 預備知識

本體是共享概念模型的明確形式化規(guī)范說明[1].它作為一種能在語義和知識層次上描述信息系統(tǒng)的概念模型,實現(xiàn)了人們從對信息的理解到計算機能夠處理數(shù)據(jù)和信息的連接,是語義網(wǎng)的核心.本體應用的基礎是本體構(gòu)建.雖然目前已構(gòu)建出許多領域本體,但大部分領域本體都是在特定的領域為特定的目的而構(gòu)建,沒有統(tǒng)一規(guī)范化的構(gòu)建方法,且多數(shù)都是手工構(gòu)建.手工構(gòu)建本體費時、 費力,難應用于復雜領域及自動更新.

本體學習是本體領域的研究熱點,多數(shù)采用自然語言處理技術、 統(tǒng)計學和機器學習等方法進行本體學習.在中文環(huán)境下的本體學習研究目前較少.

FCA(formal concept analysis)是Wille[2]提出的一種建立在數(shù)學基礎上,從形式背景進行數(shù)據(jù)分析和規(guī)則提取的工具,用于概念的發(fā)現(xiàn)、 聚類和顯示.形式概念分析與本體有許多共同點[3],如都采用形式化方式描述概念及其間的關系,因此將形式概念分析應用于本體學習是合理的.事實上,各領域的信息都是動態(tài)變化的,而P-集合[4-7]體現(xiàn)了屬性遷移帶來領域?qū)ο蟮膭討B(tài)變化,因此本文將P-集合理論引入到形式背景的獲取,提出一種基于形式概念分析的中文領域本體學習方法.

1.1 P-集合

定義1給定普通集Y={y1,y2,…,yn}?U,其屬性集a={a1,a2,…,aj}?V,則Y的內(nèi)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語義檢索、 本體研究、 知識發(fā)現(xiàn)和軟件工程等領域應用廣泛.

定義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的內(nèi)涵.

定義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

概念格是形式概念分析理論中的核心數(shù)據(jù)結(jié)構(gòu),由其定義可知,概念格是根據(jù)二元關系建立的,反映概念間泛化和特化關系的概念層次結(jié)構(gòu),并能以圖形化的方式(如Hasse圖)表示.表1示例形式背景的概念格如圖1所示.

1.3 P-集合與FCA的關系

通過P-集合與FCA的定義知二者有相似之處,即都具有一定屬性的個體集.P-集合體現(xiàn)了屬性遷移帶來的個體集變化,而FCA側(cè)重于概念的聚類.概念格體現(xiàn)層次關系,如圖1中的概念節(jié)點(?,abcd),(34,acd),(134,ad),(1234,a),它們的個體數(shù)隨屬性數(shù)的減少而增多,由P-集合的定義知,這些概念節(jié)點構(gòu)成的集合即為一個P-集合.

2 基于P-集合和FCA的本體學習方法

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

形式背景是采用FCA方法進行本體學習的基礎.本體在實際應用中需要進化,為提高本體重用性,滿足形式背景變化的需求,本文將P-集合理論引入到形式背景獲取中.先采用第三代智能分詞系統(tǒng)3GWS對文本進行詞性標注,得到帶詞性的文本數(shù)據(jù),再按漢語語法規(guī)則,從中抽取出句子的主干.將主語(名詞、 名詞性短語等)作為對象,對應出現(xiàn)的賓語作為描述該對象的屬性,這兩部分匹配后作為一個對象-屬性對置于形式背景中.如“大豆雖然生活在陸地,但是它需要水”通過3GWS進行分析和詞性標注后,得到如下信息：

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

根據(jù)以上標注信息,抽取句子的主干,可得到(大豆,生活在陸地)和(大豆,需要水)這樣的對象屬性對,但少量數(shù)據(jù)獲取的形式背景有時不能有效地區(qū)分個體,見表2.

將P-集合引入形式背景的獲取,對多文本學習得到更多屬性,自動更新形式背景,以便有效地區(qū)分個體,得到質(zhì)量較高的形式背景(表3).

表2 未能有效區(qū)分個體的形式背景Table 2 Formal context failed to distinguish between individuals

表3 能有效區(qū)分個體的形式背景Table 3 Formal context to distinguish between individuals effectively

2.2 從形式背景到概念格的構(gòu)造

概念格是FCA的核心,是概念格構(gòu)造算法作用于形式背景的結(jié)果.概念格不受數(shù)據(jù)或?qū)傩耘帕许樞虻挠绊?即一個形式背景有唯一的概念格.概念格構(gòu)造算法可分為漸近式構(gòu)造算法[8-9]和批處理構(gòu)造算法[10-13].

漸近式構(gòu)造算法又分為基于對象的漸近式構(gòu)造算法和基于屬性的漸近式構(gòu)造算法兩類.經(jīng)典的漸近式構(gòu)造算法主要包括Capineto算法、 Earpinet算法和Godin算法等.批處理構(gòu)造算法出現(xiàn)相對較早,基本思想是：先根據(jù)對象及屬性生成所有概念,然后建立所有概念節(jié)點間的直接前趨和直接后繼關系,即父子關系,以此完成概念格的整個構(gòu)建過程.按照構(gòu)造概念格方式不同,又可分為自底向上、 自頂向下和枚舉算法3類.經(jīng)典的批處理算法有Bordat算法、 FastConcept算法和Chein算法等.

本文采用基于對象的漸近式構(gòu)造算法----Godin算法構(gòu)造概念格.Godin算法是Godin等[14]提出的一種漸近式構(gòu)造算法,在概念格生成過程中需要解決兩個問題[15]: 1) 節(jié)點的更新;2) 格節(jié)點間邊的更新.新生成的概念格節(jié)點類型有3種: 不變節(jié)點、 更新節(jié)點和新增節(jié)點.

定義8設L(K)是形式背景所對應的概念格,Mi=(xi,yi)是格上的任意一個節(jié)點,新增對象xj所對應的屬性集為yj,根據(jù)yj和yi之間的關系,將加入xj后的新概念格節(jié)點分為3種類型：

1) 如果yj∩yi=?,則Mi=(xi,yi)∈L′(K),Mi稱為不變節(jié)點;

2) 如果yi?yj,則將M修改為M′=(xi∪xj,yi),加入L′(K)中,M′稱為更新節(jié)點;

3) 如果yj∩yi≠?,且不存在((yj∩yi)′,yj∩yi)∈L(K),則生成一個新節(jié)點M′=(xj∪xi,jj∩yi)加入到L′(K)中,M′稱為新增節(jié)點.

基于Godin算法構(gòu)造概念格的算法流程如下：

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

2) 從形式背景中取出一個對象O；

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

3) 將2)中的新增節(jié)點插入概念格中,并更新節(jié)點間的邊；

4) 循環(huán)2)和3),直到生成完整的概念格.

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

概念格是一種概念聚類的過程,體現(xiàn)概念間的層次(泛化)關系.將概念格節(jié)點之間的層次關系映射為OWL本體中的父類-子類關系； 概念格節(jié)點映射為本體類； 概念格節(jié)點的外延映射為對應類的實例； 概念格節(jié)點的內(nèi)涵映射為對應類的數(shù)據(jù)類型屬性.由于所有子類將繼承父類的屬性和實例,因此,在實際映射過程中,為節(jié)省資源只需將每個節(jié)點類相對于其父節(jié)點新增的屬性映射為其代表類的屬性,相對于其子節(jié)點新增的對象映射為其代表類的實例.

本文采用W3C推薦的本體描述語言OWL描述映射得到的本體.按以上映射原理,得到FCA格元素與OWL中語義要素的如下映射規(guī)則定義.

定義9設O∶=(C,root,c)是領域本體,其中:C為概念集;root為根元素;c為概念間的層次關系；L(K)是形式背景所對應的概念格,Hi=(xi,yi)和Hj=(xj,yj)是格L(K)上的任意兩個格節(jié)點,e是FCA格元素,C是Hi對應的類名,supC是Hj對應的類名,則定義f:L(K)→O為概念格到領域本體的映射.映射規(guī)則如下：

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

2)R2：IFeisHiANDHi≤HjTHEN

臨近年底，備受關注的《個人所得稅專項附加扣除暫行辦法》（以下簡稱《暫行辦法》）終于正式亮相，標志著我國綜合與分類相結(jié)合的個稅改革邁出關鍵一步，釋放出更加惠民的積極信號。

〈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)最頂層節(jié)點根據(jù)規(guī)則R1映射為root；

3) 取根節(jié)點的子節(jié)點Hi=(xi,yi)；

4) 應用映射規(guī)則：

① 對格節(jié)點Hi使用規(guī)則R1；

② 對根節(jié)點與子節(jié)點間的層次關系使用規(guī)則R2；

④ 對子節(jié)點Hi相對父節(jié)點新增的屬性使用規(guī)則R4；

6) 重復執(zhí)行3)～5),直到整個概念格映射完成.

3 實驗結(jié)果

為驗證本文所提出的基于P-集合和FCA的中文領域本體學習方法的可行性,下面應用該方法對多篇生物和水的文本進行學習,學習過程分為3個階段：1) 從文本中獲取形式背景； 2) 基于形式背景構(gòu)造概念格； 3) 概念格到本體模型的映射.最終得到一個關于生物和水的中文領域本體.

3.1 學習生物和水的文本獲取形式背景

為提高本體的可重用性,滿足本體進化過程中形式背景動態(tài)變化的需求,采用本文提出的基于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 構(gòu)造概念格

采用Godin算法,先對生物和水的形式背景進行形式概念分析,再對部分節(jié)點位置進行調(diào)整,最終得到生物和水的概念格如圖2所示.

由Hasse圖可知概念格從本質(zhì)上描述了概念之間的泛化和特化關系,位于上方的是父節(jié)點,位于下方的是子節(jié)點.概念格中的每個節(jié)點都是一個形式概念,由形式概念定義知最頂層的節(jié)點包含的對象最多,屬性最少.

3.3 中文領域本體的生成

基于FCA格元素與OWL本體描述的映射規(guī)則,將圖2中的概念格映射為中文領域本體,并使用美國斯坦福大學開發(fā)的本體編輯器Protégé中的OntoGraf插件對構(gòu)建的中文領域本體進行圖形化描述,如圖3所示.

圖3 生物和水領域本體Fig.3 Domain ontology about biology and water

4 實驗對比分析

文獻[7]中的Philipp Cimiano方法是使用一個自然語言的解析器,通過該解析器從領域文本中的每個句子得到一顆語法樹,由語法樹直接得到動詞對象間的依賴關系； 進一步通過詞典查詢,對提取的動詞和對象用詞的原形規(guī)范化表示.如bought/buys轉(zhuǎn)換成原形buy,并給動詞加上后綴 -able,使其更像是屬性； 最后,將FCA中的概念和本體中的概念直接等同,得到概念格,由概念格得領域本體.

通過本文提出的本體學習方法與Philipp Cimiano方法比較分析得出：本文提出的方法不僅能從非結(jié)構(gòu)化的中文領域數(shù)據(jù)中得到期望的本體,還能發(fā)揮形式概念分析自動客觀提取語義的特點； 將P-集合引入到形式背景的獲取,使獲取的形式背景既有利于個體的有效區(qū)分,又不會使屬性集過于龐大導致系統(tǒng)資源的浪費； 本文給出的概念格到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的面向關系數(shù)據(jù)庫的本體學習方法 [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.(黃美麗,劉宗田.基于形式概念分析的領域本體構(gòu)建方法研究 [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.(劉宗田,強宇,周文,等.一種模糊概念格模型及其漸近式構(gòu)造算法 [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 概念格構(gòu)造算法的改進 [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.(蔣義勇,張繼福,張素蘭.基于鏈表結(jié)構(gòu)的概念格漸近式構(gòu)造 [J].計算機工程與應用,2007,43(11): 178-180.)