基于P-集合和FCA的中文領(lǐng)域本體學(xué)習(xí)方法

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

(1.長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,長(zhǎng)春 130012;2.長(zhǎng)春工業(yè)大學(xué) 軟件職業(yè)技術(shù)學(xué)院,長(zhǎng)春 130012)

1 預(yù)備知識(shí)

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

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

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

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-元素補(bǔ)充集合為

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

(5)

(6)

1.2 形式概念分析

形式背景和概念格等是形式概念分析(FCA)的重要組成部分.FCA在Web語(yǔ)義檢索、 本體研究、 知識(shí)發(fā)現(xiàn)和軟件工程等領(lǐng)域應(yīng)用廣泛.

定義4形式背景K∶=(O,A,I),其中:O表示對(duì)象集(objects);A表示屬性集(attributes);I表示O和A之間的二元關(guān)系,即I?O×A.表1列出了一些形式背景示例,其中：行表示對(duì)象;列表示屬性;行列交叉處表示對(duì)象具有的屬性.

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

定義5(o,a)∈I或oIa,表示“屬性a是對(duì)象o的屬性之一”.對(duì)任一對(duì)象子集X,可定義

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

表示子集X中全體對(duì)象所共有的屬性.同理,對(duì)任一屬性子集Y,也可定義

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

表示包含Y中所有屬性全體對(duì)象的集合.

定義6若X?O,Y?A,滿足X′=Y且Y′=X,則C=(X,Y)是形式背景K=(O,A,I)的一個(gè)形式概念,X稱為C的外延,Y稱為C的內(nèi)涵.

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

(x1,y1)(x2,y2) ?x1?x2(且y2?y1),

則該偏序關(guān)系集為形式背景的概念格,此時(shí)(x2,y2)是(x1,y1)的超概念,(x1,y1)是(x2,y2)的子概念.

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

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

1.3 P-集合與FCA的關(guān)系

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

2 基于P-集合和FCA的本體學(xué)習(xí)方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2) 從形式背景中取出一個(gè)對(duì)象O；

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

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

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

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

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

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

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

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

2)R2：IFeisHiANDHi≤HjTHEN

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

〈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本體映射的算法設(shè)計(jì)如下：

1) 初始化一個(gè)空本體O；

2) 將概念格L(K)最頂層節(jié)點(diǎn)根據(jù)規(guī)則R1映射為root；

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

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

① 對(duì)格節(jié)點(diǎn)Hi使用規(guī)則R1；

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

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

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

3 實(shí)驗(yàn)結(jié)果

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

3.1 學(xué)習(xí)生物和水的文本獲取形式背景

為提高本體的可重用性,滿足本體進(jìn)化過(guò)程中形式背景動(dòng)態(tài)變化的需求,采用本文提出的基于P-集合的形式背景獲取方法,對(duì)多篇生物和水的文本進(jìn)行學(xué)習(xí),學(xué)習(xí)完成后給予修正,最終得到的形式背景列于表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.能運(yùn)動(dòng);h.有四肢;i.哺乳.圖2 生物和水的概念格Fig.2 Concept lattice about biology and water

3.2 構(gòu)造概念格

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

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

3.3 中文領(lǐng)域本體的生成

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

圖3 生物和水領(lǐng)域本體Fig.3 Domain ontology about biology and water

4 實(shí)驗(yàn)對(duì)比分析

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

通過(guò)本文提出的本體學(xué)習(xí)方法與Philipp Cimiano方法比較分析得出：本文提出的方法不僅能從非結(jié)構(gòu)化的中文領(lǐng)域數(shù)據(jù)中得到期望的本體,還能發(fā)揮形式概念分析自動(dòng)客觀提取語(yǔ)義的特點(diǎn)； 將P-集合引入到形式背景的獲取,使獲取的形式背景既有利于個(gè)體的有效區(qū)分,又不會(huì)使屬性集過(guò)于龐大導(dǎo)致系統(tǒng)資源的浪費(fèi)； 本文給出的概念格到OWL本體映射算法,不僅包含了層次關(guān)系的映射,還包括個(gè)體及對(duì)象屬性的映射,使得到的本體比使用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.(歐陽(yáng)純萍,胡長(zhǎng)軍,李揚(yáng),等.一種基于FCA的面向關(guān)系數(shù)據(jù)庫(kù)的本體學(xué)習(xí)方法 [J].計(jì)算機(jī)科學(xué),2011,38(12): 167-171.)

[4] SHI Kai-quan.P-sets and Its Applied Characteristics [J].Computer Science,2010,37(8)：1-8.(史開(kāi)泉.P-集合與它的應(yīng)用特征 [J].計(jì)算機(jī)科學(xué),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.(汪洋,史金昌,史開(kāi)泉.P-集合與F-記憶信息特性: 應(yīng)用 [J].計(jì)算機(jī)科學(xué),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.(閻紅燦,王堅(jiān),劉保相.基于P-集合的本體形式背景抽取 [J].計(jì)算機(jī)應(yīng)用研究,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.(黃美麗,劉宗田.基于形式概念分析的領(lǐng)域本體構(gòu)建方法研究 [J].計(jì)算機(jī)科學(xué),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.(劉宗田,強(qiáng)宇,周文,等.一種模糊概念格模型及其漸近式構(gòu)造算法 [J].計(jì)算機(jī)學(xué)報(bào),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ìn) [J].計(jì)算機(jī)工程與應(yīng)用， 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.(紀(jì)彤坤.概念格Chein算法的研究與改進(jìn) [D].廣州：華南理工大學(xué)， 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].計(jì)算機(jī)工程與應(yīng)用,2007,43(11): 178-180.)