融合概念格約簡(jiǎn)的中文領(lǐng)域本體學(xué)習(xí)方法

侯麗鑫, 鄭山紅, 賀海濤, 趙 輝, 韓 冬

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

0 引 言

本體學(xué)習(xí)是指自動(dòng)或半自動(dòng)地構(gòu)建本體, 目的是利用知識(shí)獲取技術(shù)降低本體構(gòu)建的開(kāi)銷(xiāo),目前本體學(xué)習(xí)已成為本體領(lǐng)域的研究熱點(diǎn)之一。形式概念分析(FCA： Formal Concept Analysis)[1]與本體有許多相似之處[2], 近年來(lái), 人們開(kāi)始嘗試將FCA應(yīng)用于本體學(xué)習(xí)領(lǐng)域。Obitkom等[3]將FCA應(yīng)用于分布式的領(lǐng)域本體開(kāi)發(fā)環(huán)境, 通過(guò)構(gòu)建概念格探尋潛在的對(duì)象和屬性, 并將現(xiàn)有的和潛在的實(shí)體以可視化的方式自動(dòng)呈現(xiàn)； 張斌等[4]利用FCA與統(tǒng)計(jì)理論進(jìn)行政務(wù)本體學(xué)習(xí)。概念格是FCA的核心數(shù)據(jù)結(jié)構(gòu), 在機(jī)器學(xué)習(xí)、 模式識(shí)別、 決策分析等領(lǐng)域應(yīng)用廣泛[5-8]。概念格約簡(jiǎn)理論[9,10]能更容易發(fā)現(xiàn)形式背景中隱含的知識(shí), 也使這些知識(shí)的表示變得更簡(jiǎn)單, 提高概念格構(gòu)造的效率。

筆者在已有工作[11]的基礎(chǔ)上, 提出了一種融合概念格約簡(jiǎn)的中文領(lǐng)域本體學(xué)習(xí)方法。該方法應(yīng)用語(yǔ)義依存分析技術(shù)獲取領(lǐng)域形式背景, 將概念格約簡(jiǎn)應(yīng)用于概念格的構(gòu)造, 通過(guò)對(duì)象約簡(jiǎn)和屬性約簡(jiǎn)完成初始概念格的構(gòu)造, 再采用約簡(jiǎn)概念格修復(fù)得到完整概念格, 最后根據(jù)映射規(guī)則完成中文領(lǐng)域本體的生成。通過(guò)對(duì)蘿藦科植物及其藥用性的領(lǐng)域文本進(jìn)行學(xué)習(xí), 得到蘿藦科植物領(lǐng)域本體, 提高了本體構(gòu)建的效率。

1 基于語(yǔ)義依存的形式背景的獲取

形式背景是基于FCA進(jìn)行本體學(xué)習(xí)的基礎(chǔ), 筆者將語(yǔ)義依存技術(shù)用于從中文領(lǐng)域文本中獲取形式背景。下面給出形式背景的定義及從領(lǐng)域文本中獲取形式背景的具體算法。

定義1 形式背景是三元組K=(G,M,I), 其中G和M分別是對(duì)象集和屬性集, 二元關(guān)系I?G×M。通常用(g,m)∈I或gIm, 表示“對(duì)象g擁有屬性m”。

形式背景是采用FCA方法進(jìn)行本體學(xué)習(xí)的基礎(chǔ)。筆者借鑒AIFB研究機(jī)構(gòu)在IST-Dot Kom項(xiàng)目中應(yīng)用Philipp Cimiano方法[12]的思想, 利用基于漢語(yǔ)的依存語(yǔ)法分析器[13], 給定文本集中的一個(gè)句子作為輸入, 產(chǎn)生一棵標(biāo)注依存關(guān)系、 語(yǔ)義角色的語(yǔ)法分析樹(shù),從中抽取句子的主干。將主語(yǔ)作為對(duì)象, 將對(duì)應(yīng)出現(xiàn)的賓語(yǔ)作為描述該對(duì)象的屬性, 這兩部分匹配后作為一個(gè)對(duì)象-屬性對(duì)放入形式背景中。具體算法如下。

輸入： 中文領(lǐng)域文本。

輸出： 對(duì)象屬性對(duì)構(gòu)成形式背景。

Step 1 初始化HashMap, 用于存儲(chǔ)對(duì)象-屬性對(duì)；

Step 2 基于CRF(Conditional Random Fields)模型, 對(duì)文本集中的每句子i(i是句子的編號(hào))進(jìn)行分詞, 得到wordList；

Step 3 對(duì)句子i中的每個(gè)詞j(j為詞在句中的編號(hào)), 采用GParser(全稱(chēng)為Graph-based Parser)輸出該詞在句子中的依存關(guān)系；

Step 4 判斷詞j的依存關(guān)系的類(lèi)型, 若依存關(guān)系的類(lèi)型為“SBV(Subject-Verb)”, 則詞j為一個(gè)對(duì)象； 若依存關(guān)系的類(lèi)型為“VOB(Verb-Object)”, 則詞j為對(duì)象對(duì)應(yīng)的屬性；

Step 5 以HashMap中所有的對(duì)象G及屬性M構(gòu)成形式背景K(G,M,I)。

以“牛皮消是一種草本植物?！睘槔? 采用ltp-service的語(yǔ)義依存分析結(jié)果如表1所示。

表1 示例的語(yǔ)義依存分析結(jié)果

從表1可以看出, “白薇”的依存句法分析的依存關(guān)系為“SBV”, 即主謂關(guān)系；“是”為核心(HED： Head), 即“是”為謂語(yǔ)； “草本植物”的依存句法分析的依存關(guān)系為“VOB”, 即動(dòng)賓關(guān)系。因此可以得出下面的結(jié)果

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

最終得到一組對(duì)象屬性對(duì)是： (“白薇”, “草本植物”)。

基于提出的基于語(yǔ)義依存的形式背景獲取方法, 通過(guò)對(duì)多篇介紹蘿藦科植物以及它們的藥用性的領(lǐng)域文本進(jìn)行學(xué)習(xí), 得到的部分形式背景如表2所示。

表2 蘿藦科植物形式背景

2 基于概念格約簡(jiǎn)的概念格構(gòu)造

概念格是FCA的核心, 體現(xiàn)概念間的層次(泛化)關(guān)系。它是概念格構(gòu)造算法[14,15]作用于形式背景的結(jié)果。為了提高概念格構(gòu)造效率, 筆者引入概念格約簡(jiǎn)理論。為方便討論, 給出如下定義。

定義2 對(duì)于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, 滿(mǎn)足f(A)=B且g(B)=A, 則C=(A,B)是K=(G,M,I)的一個(gè)形式概念。A稱(chēng)為C的外延, 記作Ext(C),B稱(chēng)為C的內(nèi)涵, 記作Int(C)。

定義4 形式背景的概念格記作L(K),L(K)是一個(gè)偏序集, 由形式背景中存在層次包含關(guān)系的概念形成, 即(A1,B1)(A2,B2)?A1?A2(且B2?B1)。此時(shí)(A2,B2)是超概念, (A1,B1)是子概念。

定義5 設(shè)L(G,M1,I1)和L(G,M2,I2)是兩個(gè)概念格。若對(duì)于?(A2,B2)∈L(G,M2,I2), ?(A1,B1)∈L(G,M1,I1), 使A1=A2, 則稱(chēng)L(G,M1,I1)細(xì)于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), 則稱(chēng)兩個(gè)概念格同構(gòu), 記作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), 則稱(chēng)A是K=(G,M,I)的協(xié)調(diào)集。如果?a∈A, 有L(G,A-{a},IA-{a})不同構(gòu)于L(G,M,I), 則稱(chēng)A是K=(G,M,I)的約簡(jiǎn)。

2.1 形式背景的對(duì)象約簡(jiǎn)和屬性約簡(jiǎn)

對(duì)于形式背景K=(G,M,I), 既可以對(duì)對(duì)象又可以對(duì)屬性進(jìn)行約簡(jiǎn)。下面給出對(duì)象、 屬性約簡(jiǎn)定理。為方便討論給出如下定義。

定義7 對(duì)于形式背景K=(G,M,I), 其中G={g1,g2,…,gm},M={m1,m2,…,mn},I?G×M。對(duì)于?g∈G, ?m∈M, 定義R(g)={m∈M|gIm}為對(duì)象的屬性空間,D(m)={g∈G|gIm}為屬性的對(duì)象空間。

基于定義7, 根據(jù)各對(duì)象的屬性空間之間的關(guān)系和各屬性的對(duì)象空間之間的關(guān)系, 描述如下4條形式背景的約簡(jiǎn)定理。

定理1(對(duì)象的交約簡(jiǎn)) 在形式背景(G,M,I)中：

1) 如果?gi,gj∈G,i,j∈[1,m], 使R(gi)=R(gj), 則對(duì)象gi或gj是冗余的, 因此, 可約簡(jiǎn)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), 則對(duì)象gl是冗余的, 因此, 可約簡(jiǎn)gl所在的行。

定理2(對(duì)象的全約簡(jiǎn)) 在形式背景(G,M,I)中, 如果?gi∈G,i∈[1,m], 使R(gi)=M, 則對(duì)象gi是冗余的, 則可約簡(jiǎn)gi所在的行。

定理3(屬性的交約簡(jiǎn)) 在形式背景(G,M,I)中：

1) 如果?mi,mj∈M,i,j∈[1,n], 使D(mi)=D(mj), 則屬性mi或mj是冗余的, 因此, 可約簡(jiǎn)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是冗余的, 因此, 可約簡(jiǎn)ml所在的列。

定理4(屬性的全約簡(jiǎn)) 在形式背景(G,M,I)中, 如果?mi∈M,i∈[1,n], 使D(mi)=G, 則屬性mi是冗余的, 因此, 可約簡(jiǎn)mi所在的列。

由于漸進(jìn)式構(gòu)造算法可根據(jù)形式背景的變化對(duì)原有概念格做相應(yīng)調(diào)整, 而不用重新構(gòu)造概念格, 從而節(jié)省了大量時(shí)間。因此漸進(jìn)式構(gòu)造算法一直是概念格構(gòu)造算法的研究熱點(diǎn)。筆者采用基于對(duì)象的漸進(jìn)式構(gòu)造算法----Godin算法, 在概念格構(gòu)造過(guò)程中引入概念格屬性約簡(jiǎn)理論, 采用以上約簡(jiǎn)定理, 對(duì)已獲得的形式背景進(jìn)行約簡(jiǎn)； 以約簡(jiǎn)后的形式背景為數(shù)據(jù)源, 采用Godin算法構(gòu)造概念格。

基于表2蘿藦科植物形式背景, 概念格構(gòu)造過(guò)程如下。

步驟1 根據(jù)表2, 列出所有屬性的對(duì)象空間和對(duì)象的屬性空間:

D(草本植物)={牛皮消,白薇,徐長(zhǎng)卿,一枝香,蘿藦}D(藤本植物)={夜來(lái)香}

D(止咳)={白薇}D(祛風(fēng)濕)={徐長(zhǎng)卿,一枝香}D(圓錐花絮)={徐長(zhǎng)卿,一枝香}

D(聚傘花序)={牛皮消,夜來(lái)香}D(傘形花序)={夜來(lái)香}D(總狀花序)={蘿藦}

R(牛皮消)={草本植物,聚傘花序}R(白薇)={草本植物,止咳}R(徐長(zhǎng)卿)={草本植物,祛風(fēng)濕,圓錐花絮}

R(一枝香)={草本植物,祛風(fēng)濕,圓錐花絮}R(蘿藦)={草本植物,總狀花序}R(夜來(lái)香)={藤本植物,聚傘花序,傘形花序}

步驟2 分析D(m)之間的關(guān)系和R(g)之間的關(guān)系, 得到：

1)D(祛風(fēng)濕)=D(圓錐花絮)；

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

3)R(徐長(zhǎng)卿)=R(一枝香)。

步驟3 根據(jù)D(m)、R(g)間的關(guān)系結(jié)果以及定理1、 定理3, 約簡(jiǎn)“圓錐花絮”、 “傘形花序”所在的列及“一枝香”所在的行, 得到的約簡(jiǎn)形式背景如表3所示。

表3 約簡(jiǎn)的蘿藦科形式背景

步驟4 采用Godin算法對(duì)表3的形式背景構(gòu)造概念格, 其結(jié)果如圖1所示。

圖1 約簡(jiǎn)概念格

圖1的Hasse圖是一個(gè)簡(jiǎn)化的概念格視圖, 實(shí)際上每個(gè)節(jié)點(diǎn)都包含一個(gè)對(duì)象集和一個(gè)屬性集, 每個(gè)節(jié)點(diǎn)的對(duì)象集合由該節(jié)點(diǎn)下所有子節(jié)點(diǎn)中出現(xiàn)的對(duì)象集構(gòu)成, 而每個(gè)節(jié)點(diǎn)的屬性集合則由該節(jié)點(diǎn)的所有父節(jié)點(diǎn)中出現(xiàn)的屬性集構(gòu)成。

由比較表2和表3結(jié)果可知, 構(gòu)造概念格時(shí), 運(yùn)算次數(shù)由原來(lái)的26+28次減少到25+26次, 即運(yùn)算效率提高70%。

2.2 約簡(jiǎn)概念格的修復(fù)

為了保持概念格約簡(jiǎn)前后的同構(gòu)性, 筆者根據(jù)2.1節(jié)采用的定理1、 定理3得出如下概念格修復(fù)定理。

定理5(直接添加約簡(jiǎn)項(xiàng)法) 對(duì)于形式背景(G,M,I), 如果采用R(gi)=R(gj),D(mi)=D(mj)的方式約簡(jiǎn)gj所在的行和mj所在的列, 則在修復(fù)概念格時(shí)直接將gj,mj添加到約簡(jiǎn)格中所有格節(jié)點(diǎn)中。

根據(jù)概念格修復(fù)定理, 對(duì)圖1的約簡(jiǎn)概念格進(jìn)行修復(fù), 即將“圓錐花絮”直接添加到約簡(jiǎn)概念格中內(nèi)涵含有“祛風(fēng)濕”的格節(jié)點(diǎn)中。將“傘形花序”直接添加到約簡(jiǎn)概念格中內(nèi)涵含有“藤本植物”的格節(jié)點(diǎn)中。將“一枝香”直接添加到約簡(jiǎn)概念格中外延含有“徐長(zhǎng)卿”的格節(jié)點(diǎn)中。修復(fù)后完整的概念格如圖2所示。

圖2 蘿藦科植物完整概念格

3 概念格到中文領(lǐng)域本體的映射

圖3 蘿藦科植物本體

由定義4可知, 概念格是一種概念聚類(lèi)的過(guò)程, 體現(xiàn)了概念間的層次關(guān)系, 即超概念是子概念的泛化, 相應(yīng)的子概念是超概念的特化, 因此, 將概念格中的每個(gè)概念節(jié)點(diǎn)映射成本體中的一個(gè)Class, 層次關(guān)系映射成本體中的subClassOf關(guān)系； 概念格節(jié)點(diǎn)的外延表示該格節(jié)點(diǎn)所包含的對(duì)象, 相當(dāng)于類(lèi)的實(shí)例, 因此映射成Class的Individual； 概念格節(jié)點(diǎn)的內(nèi)涵表示該格節(jié)點(diǎn)中的對(duì)象共同擁有的屬性, 相當(dāng)于類(lèi)的屬性, 因此將該節(jié)點(diǎn)的內(nèi)涵映射成Class的DatatypeProperty。

采用上述映射規(guī)則, 實(shí)現(xiàn)蘿藦科植物概念格到蘿藦科植物本體的映射, 并使用斯坦福大學(xué)開(kāi)發(fā)的本體編輯器Protégé中的OntoGraf插件對(duì)構(gòu)建的中文領(lǐng)域本體進(jìn)行圖形化描述(見(jiàn)圖3)。

4 結(jié) 語(yǔ)

筆者提出一種融合概念格約簡(jiǎn)的中文領(lǐng)域本體學(xué)習(xí)方法, 并以多篇有關(guān)蘿藦科植物及其藥用性的中文文本為數(shù)據(jù)源, 應(yīng)用該方法進(jìn)行中文領(lǐng)域本體學(xué)習(xí), 最終得到了蘿藦科植物本體, 并用可視化的方式描述。在學(xué)習(xí)過(guò)程中, 采用語(yǔ)義依存分析技術(shù)獲取形式背景, 基于概念格約簡(jiǎn)理論構(gòu)造概念格, 然后根據(jù)映射規(guī)則實(shí)現(xiàn)概念格到領(lǐng)域本體的映射。將FCA應(yīng)用于本體構(gòu)建, 既能發(fā)揮形式概念分析自動(dòng)客觀提取語(yǔ)義的特點(diǎn), 又能使構(gòu)建的本體在知識(shí)重用和知識(shí)共享等應(yīng)用層面上比單純的分類(lèi)法具有更大的優(yōu)勢(shì)。將概念格約簡(jiǎn)理論應(yīng)用于概念格構(gòu)造, 實(shí)驗(yàn)驗(yàn)證可提高概念格構(gòu)建效率。實(shí)驗(yàn)結(jié)果表明, 該本體學(xué)習(xí)方法能提高本體構(gòu)建的效率和形式化程度。但仍有需要改進(jìn)的地方, 下一步會(huì)設(shè)計(jì)更明確的映射算法實(shí)現(xiàn)概念格到本體的映射, 減少人工參與, 進(jìn)一步提高本體學(xué)習(xí)的自動(dòng)化程度。

參考文獻(xiàn)：

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

[2]歐陽(yáng)純萍, 胡長(zhǎng)軍, 李揚(yáng), 等. 一種基于FCA的面向關(guān)系數(shù)據(jù)庫(kù)的本體學(xué)習(xí)方法 [J]. 計(jì)算機(jī)科學(xué), 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]張斌, 劉增良, 余達(dá)太, 等. 基于形式概念分析與統(tǒng)計(jì)理論的本體構(gòu)建模型 [J]. 計(jì)算機(jī)應(yīng)用研究, 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]張文修, 魏玲, 祁建軍. 概念格的屬性約簡(jiǎn)理論與方法 [J]. 中國(guó)科學(xué)E輯: 信息科學(xué), 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]楊麗, 徐揚(yáng). 基于形式背景的概念格約簡(jiǎn)及其修復(fù) [J]. 計(jì)算機(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的中文領(lǐng)域本體學(xué)習(xí)方法 [J]. 吉林大學(xué)學(xué)報(bào): 理學(xué)版, 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]黃美麗, 劉宗田. 基于形式概念分析的領(lǐng)域本體構(gòu)建方法研究 [J]. 計(jì)算機(jī)科學(xué), 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]蔣義勇, 張繼福, 張素蘭. 基于鏈表結(jié)構(gòu)的概念格漸進(jìn)式構(gòu)造 [J]. 計(jì)算機(jī)工程與應(yīng)用, 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.