模糊概念圖知識表示及其推理機制研究

摘 要:通過對現有模糊概念圖的研究，針對概念的所指域與模糊信息間的冗余問題和用模糊度表示模糊概念問題，提出一種改進的模糊概念圖知識表示方法。在改進的模糊概念圖中，用模糊集合表示概念圖中的模糊概念和模糊關系，并將模糊概念的所指域同模糊集合合并，減少信息冗余。根據改進的模糊概念圖，重點研究了模糊概念圖的匹配推理機制，設計了基于語義約束的匹配推理算法，并定量分析了算法的時間復雜度和空間復雜度。經過在《計算機文化基礎》課程中實驗測試，算法反映了考生主觀題的答卷情況，同人工閱卷結果基本一致。

關鍵詞:模糊概念圖; 知識表示; 知識推理

中圖分類號:TP311文獻標志碼:A

文章編號:1001-3695(2010)06-2119-04

doi:10.3969/j.issn.1001-3695.2010.06.036

Research on knowledge representation and inference mechanismsabout fuzzy conceptual graphs

LIU Peiqi1， LI Zengzhi2

(1.School of Information Control Engineering， Xi’an University of Architecture Technology， Xi’an 710055， China; 2.School of Electronics Information Engineering， Xi’an Jiaotong University， Xi’an 710049， China)

Abstract:By analyzing the existing fuzzy conceptual graphs， detected the information redundancy between referent and fuzzy degree of the concept. At the same time， fuzzy degree of some concepts doesn’t reflect fuzzy uncertainty of the concept completely. Based on analysis， put forward a new fuzzy conceptual graph. In the improved fuzzy conceptual graphs， used the fuzzy set to replace the fuzzy degree and enlarge the referent. It reduced information redundancy and increased the ability of the knowledge representation. According to the new fuzzy conceptual graphs， studied the matching reasoning mechanism of the fuzzy conceptual graphs， and designed the matching reasoning algorithms based on semantic constraint. The paper accomplished the quantitative analysis of the time complexity and space complexity of the algorithm. Via the experimental test in the culture foundation of computer science， the algorithm is the same as manuals of checking over subjective examination basically.

Key words:fuzzy conceptual graphs; knowledge representation; knowledge reasoning

概念圖(conceptual graphs，CGs)是美國計算機科學家Sowa[1]提出的一種集語言學、心理學和哲學為一體的圖形知識表示方法，它具有簡單、直觀、語義表達能力強等優點，可表示自然語言的語義知識和深層格關系。Granet和Tsul等人已證明概念圖是一種優秀的知識表示方法。自從概念圖知識表示提出之后，受到計算機界，特別是人工智能界學者的廣泛關注，并在自然語言理解、數據庫自然語言接口、知識表示、信息自動檢索等方面取得了可喜成果[2，3]。

雖然概念圖可以表示一階邏輯、高階邏輯和模態邏輯等，但在模糊知識的表示和處理能力方面略顯不足。目前已有一些學者將模糊數學理論與概念圖相結合，研究了模糊概念圖(fuzzy conceptual graphs， FCGs)知識表示方法，并在一些實際問題中獲得應用[4]。但是在現有的模糊概念圖中存在概念節點的所指域和模糊度域的重復現象，以及模糊度不能真正反映模糊概念的特性等問題，使其在模糊知識表示和處理能力方面略顯不足。本文主要從概念圖中概念的類標志符和所指域出發，研究一種改進的模糊概念圖知識表示方法，并將模糊度用模糊集合表示。在新的模糊概念圖知識表示的基礎上，重點研究模糊概念圖的推理機制和算法。

1 模糊概念圖知識表示

在用概念圖表示和處理模糊不確定知識的研究中，Morton和Wuwongse等人分別提出了模糊概念圖知識表示方法[4，5]。為了便于模糊不確定性知識處理，Morton在Sowa的概念圖中引入了模糊度的概念[3]。在這種模糊概念圖中，將一個概念c定義為[t:x|μc]。其中:μc:Le×I→[0，1]是實體的子類Le和標記集合I叉積到區間[0，1]的一個偏函數，t=type(c)∈Le， x=referent(c)∈I。這里的type()和referent()分別將一個概念映射為概念類型和所指域。對于任意一個模糊關系r可定義為(type(r)|μr)。其中μr是指連接在關系r上的概念滿足關系的程度。由模糊概念、模糊關系和映射關系組成模糊概念圖。

這種模糊概念圖知識表示在一定程度上反映了概念和關系的模糊程度，可解決一些模糊不確定性知識的表示問題。但是在這種模糊概念圖中，存在兩個嚴重缺陷:a)模糊度僅僅反映了一些概念和關系的模糊不確定性，對于難以用一個模糊度表示其模糊不確定程度的概念和關系就無法確切表示。b)在這種表示方法中，沒有充分考慮概念圖中概念節點所指域的特點，存在表示方法重復和不能進行概念所指域的聚集計算問題。針對Morton提出的模糊概念圖存在的問題，首先提出用模糊集合表示概念和關系的模糊性質，并對概念節點所指域進行適當擴展，使概念所指域中包含模糊集合，體現模糊概念的外延。

在新模糊概念圖表示方法中，任何概念節點由概念標志符和概念所指域組成，其中概念標志符是概念內涵的體現，概念所指域是概念標志符的定義域，為概念外延的體現，它可以是一個個體、一個cantor集合，也可以是一個模糊集合等。

定義1 設Le是實體的子類，I為標記集，任意一個概念c可表示為[t:Y]。其中:t=type(c)∈Le，Y=referent(c)∈I。在這里Y實際上是概念c的論域，當Y為“*”時，表示概念c存在，是清晰的但不確定;當Y為一個帶序號的數字或Y為一個名詞時，表示概念c是一個特殊的清晰概念;當Y是一個cantor集合時，概念c是一個清晰概念，Y為概念取值范圍;當Y是一個模糊集合A~時，c為模糊概念。在有限論域Uc中，A~=∑x∈Uc μA~(x)/x;對于無限論域Uc，A~=∫x∈Uc μA~(x)/x。模糊集A~中的x是模糊概念c論域中的元素，μA~(x)表示x屬于c的程度。

為了簡化概念所指域的形式，將論域Uc中任意集合X表示成特征函數形式，即

μ(x)=1 x∈X0 xX

可以看出，清晰集合是模糊集合的特例。在概念圖的所指域中，可將模糊集合與清晰集合表示形式統一。

定義2 在FCGs， 假設確定概念的論域為U={true，1}，則模糊集可定義為{1/true +0/1}。

在概念所指域中，將“*x”表示為{*}，個體x表示成{x}，就可將概念的所指域統一為集合形式。當概念所指域不確定時，所指域可省略。在概念圖匹配中為了便于概念所指域的操作，特引入概念標志符的聚集運算律。

定理1 設{*}為一般概念集合， X為普通集合，A~、B~為模糊概念集合，論域為Uc，則標志符的聚集運算遵守以下聚集運算律:

a){*}∪{*}={*}

b) {*}∪X={x|x∈X∨x=*}

c) {*}∪A~=∑x∈Uc μA~(x)/x，當x=*時μA~(x)=1

d) X∪A~=∑x∈Uc μA~(x)/x，當x∈X時μA~(x)=1

e)A~∪B~=∑x∈Uc(μA~(x)∨μB~(x))/x

f){*}∩{*}={*}

g){*}∩X=X

h){*}∩A~=∑x∈Uc∧μA~(x)≠0 μA~(x)/x

i)X∩μA~={ x|x∈X∧μA~(x)≠0}

j)A~∩B~=∑x∈Uc(μA~(x)∧μB~(x)) /x

定義3 對于任意概念關系r，關系節點可表示為(t:A~)。其中:t=type(r);A~為模糊集合。在有限論域Ur中，A~=∑r∈Ur μA~(r)/r。其中:r是關系R論域中的元素，μ(r)是r屬于關系R的程度; 在無限論域Ur中，A~=∫r∈Ur μA~(r)/r。對于確定關系也可以按照定義3表示成模糊集合的形式。

根據以上定義，概念圖中的概念和關系可用統一形式描述，確定的概念圖可作為模糊概念圖的特例。模糊概念圖可形式化定義為

定義4 模糊概念圖可用三元組表示:FCGs=(C，R，F)。其中:C={c1，c2，…，cm}為模糊概念節點的集合;R={r1，r2，…，rn}為模糊關系節點集合;F=(C×R)∪(R×C)為弧的集合。

例如，語句“A young child eats pie，and it is not certain whether it is a boy or a girl who performs the eating. The certainty of girl is 0.6， the certainty of boy is 0.4. If it is a girl eats pie， her name probably (with 0.8 of certainty) called Lucy.”可線性表示為

[EAT:A~]—(AGNT:B~)→[GIRL:C~]→(AGE:A~)→[YOUNG:D~]

(OBJ:A~)→[PIE:A~]

其中:A~=1/true+0/1，B~=0.6/girl+0.4/boy，C~=0.8/Lucy+0.2/other，D~=∑x∈X(1+(x/20)2)-1/x;X={1，2，…，120}。為表示和閱讀方便，省略非模糊概念和關系中的模糊集合，簡化后的模糊概念圖的線性形式為

[EAT]—(AGNT:B)→[GIRL:C]→(AGE)→[YOUNG:D]

(OBJ)→[PIE]

2 模糊概念圖推理機制

在傳統概念圖中有三種重要的推理方式，分別是完全匹配推理、投影匹配推理和相容匹配推理。由于完全匹配推理很簡單， 投影匹配推理已在其他文獻中有詳細論述，相容匹配推理有其自身的弊病，下面將結合模糊概念圖知識表示形式，主要研究模糊概念圖基于語義距離的語義約束匹配推理，并根據推理機制設計匹配推理算法。

2.1 基本概念

在語義約束匹配推理中，需要有關類、子類、概化(或特化)和概念格方面的簡單知識， 相關的詳細內容在文獻[6，7]中有較完整的介紹。

定義5 在概念的關系中，若概念c1比c2更具體，則稱c2是c1的超類，c1是c2的子類，記為c1≤c2。c1，c2∈C，若存在映射π:C→T，使得π(c1)=π(c2)成立，則稱概念c1和c2是同一類型概念，即c1=c2[5]。其中C和T分別為概念集和類集。

在概念c1和c2比較時，若c1≤c2成立，則稱c2是c1的概化(抽象)，c1是c2的特化(具體)。當兩個概念有相同的概念類標志符時等號成立。概念集合上概念間的“≤”是一種偏序關系，形成了概念的層次結構。若在概念空間中增加全局概念(┬)和不可能概念(┴)，關系“≤”組成概念空間上的格關系。

定義6 任意概念類型標志符s和t有最小公共超類(s∪t)和最大公共子類(s∩t)。若s≤u且t≤u，則┴≤s∪t≤u;若u≤s且u≤t，則u≤s∩t≤┬[2]。

定義7 設u和v為概念圖，Cu和Cv分別為u和v的概念節點集合。如果 (c1∈Cu) (c2∈Cv)c1≤c2，則u是v的特化(v是u的概化)，記為u≤v。

2.2 語義約束匹配推理

語義約束匹配推理是建立在概念相容基礎上的一種匹配推理方式。

定義8 若概念c1和c2存在最大公共子類c3，即對任意概念c，c≤c1，c≤c2，則c≤c3，則稱概念c1與c2為相容概念，記為c1⊕c2。

定理2 設u，v和w為概念圖。若Rw=Ru∪Rv，Cw={c|c=d⊕e∧d∈Cu∧e∈Cv}，則稱w是u和v的相容概念圖，記為w=u⊕v。

定理中的R和C分別為概念圖的關系節點集合和概念節點集合。通過定理得到了相容概念圖的形成方法，在相容概念圖中，累加了原始圖的相容概念，保留了概念圖的不同部分。例如有概念圖:

u:[Eat]—(MANR)→[Fast]

(AGNT)→[Person: {Sue}]

v:[Eat]—(OBJ)→[Pie]

(AGNT)→[Girl: {*x}]

則在概念圖u和v中，概念節點[Person: {Sue}]和[Girl:{*x}]的相容概念為[Girl:{Sue}]，概念圖u和v的相容概念圖w為

w:[Eat]—(MANR)→[Fast]

(AGNT)→[Girl:{Sue}]

(OBJ)→[Pie]

在相容匹配推理中，匹配約束很弱。例如，概念[Person:{Sue}]和[Girl:{*x}]在投影匹配時不能進行合一，但在相容匹配中可合一成[Girl:{Sue}]，這在一定程度上暴露出相容匹配的不嚴謹性。產生這種結果的主要原因是在推理過程中僅考慮了概念之間的概化(或特化)關系和相容關系，沒有考慮概念在概念格中的語義距離。

在概念格中，不同概念在格中的層次和位置不同。概念間的連接線反映了概念之間的概化(或特化)關系。自底向上概念逐步抽象化(概化);反之，概念越來越具體(特化)。子層概念繼承父類概念的所有特性。一個概念與其他概念間的差異不僅反映在概念的概化和特化關系上，而且還反映在概念所在層次結構中的具體位置。

定義9 在概念格中，將邊〈a，b〉的語義距離(semantic distance)定義為1，記為SD(a，b)=1。若概念格中任兩個概念a和b間存在一條長為k的路徑，則SD(a，b)=k;若概念a和b間存在n條路徑，則a到b的語義距離為a到b間n條路徑中的最短語義距離，即

SD(a，b)=minni=1SDi(a，b)

根據定義9，若概念類標志符a和b的最大公共下界為概念類標志符c，則a和b間的語義距離為

SD(a，b)=SD(a，c)+SD(b，c)

定義10 設a、b是概念圖中的兩個概念，λ∈R+。如果存在a和b的最小公共上界c，并且滿足:

SD(a，c)+SD(b，c)≤λ

則稱概念a、b為語義約束匹配。兩概念圖中相應節點間的語義約束匹配為概念圖的語義約束匹配推理。

可以看出，概念圖的語義約束匹配推理是在相容推理的基礎上加入語義距離約束的匹配推理，顯然，語義約束匹配推理能更好地反映出用戶需求，符合實際需要。語義約束匹配算法(matching algorithm of restricted the semantic distance，MARSD)描述如下:

算法:MARSD算法

(1)Input:u，v，λ，T//λ為語義距離的閾值，T為概念格

(2)Output:w //w為u和v的最大連接圖

(3)begin

(4)Cw=Φ;Rw=Φ;

(5)while Ru≠Φ and Rv≠Φ

(6){(r)r∈Ru， dirdj;Ru=Ru-{r};

(7)if r∈Rv and ckrcl

(8){if ck， di is consistent and cl， dj is consistent

(9){lookfor(T， ck，di); lookfor(T， cl，dj);

//在T中查找相容概念

(10)g=ck⊕di;//g是ck和di的相容概念

(11)h=cl⊕dj;//h是cl和dj的相容概念

(12)if SD(g，ck)+SD(g，di)≤λ and SD(h，cl)+SD(h，dj)≤λ

(13){Cw=Cw∪{g，h};Rw=Rw∪{r};

(14)θu={di/g，dj/h};θv={ck/g，cl/h};

(15)calculating the referent of concept g and h;

(16)Rv=Rv-{r};}}

(17)else//將不屬于Rv的r加入到w中

(18) {Cw=Cw∪{di，dj};Rw=Rw∪{r};}}

(19) while Rv≠Φ

//概念圖v中的其他概念和概念關系的處理

(20){(r)r∈Rv，ckrcl; Rv=Rv-{r};

(21)Cw=Cw∪{ck，cl};Rw=Rw∪{r};}

(22)end

在MARSD算法中，C為概念節點集合，R為關系節點集合。算法對模糊概念圖u中關系節點r進行循環，找到u中與r相關的概念;再在v中搜索關系r和相關概念;然后在T中搜索對應滿足約束條件λ的相容概念，并按聚集運算律計算概念所指域。

3 算法分析

在MARSD中，輸入為u、v和概念格T，輸出為w。從(5)~(18)對Ru循環，每次循環中都要在v中找出對應關系。在第一次循環中需查找|Rv|次， 第二次循環需查找|Rv|-1次， 第|Ru|次循環需查找|Rv|-|Ru|+1次。總循環次數為|Rv||Ru|-∑|Ru|-1i=1i=|Ru|(|Rv|-|Ru|+1)，最壞情況下循環|Ru||Rv|次。在(9)中的lookfor()是一個改進的寬度優先搜索算法，在概念格T中搜索ck和dl，在概念集合中找到ck和dl需要|Cu||Cv|次，再沿著兩個概念向下搜索找到相容概念ck⊕dl。設T深度為n，最大寬度為m，則lookfor()最多查找nm次，總查找次數最大上界為|Ru||Rv|nm。(19)是將v中不屬于u的關系加入到w中，需循環|Rv|-|Rv∩Ru|次。因此算法MARSD在最壞情況下的總時間代價為|Ru||Rv|(nm+|Cu||Cv|)。

一般情況下，概念圖中的關系為二元關系，每個關系同兩個概念關聯。因此在一個概念圖中，概念節點的個數近似為關系節點個數的2倍，并且有nm>>|Ru|和nm>>|Rv|。因此，MARSD算法最壞情況下總時間復雜度為O(nm)。

MARSD算法的空間復雜度為存儲概念圖u、v和w的概念節點及關系節點所需的存儲空間、概念類型格的存儲空間以及臨時變量所需的存儲空間，因此算法總的空間復雜度的解析式為|Rw|+|Ru|+|Rv|+|Cw|+|Cu|+|Cv|+nm+τ。對于u、v和w都為二元關系的簡單概念圖，則存儲空間近似為3(|Ru|+|Rv|+|Rw|)+nm+τ，所以總的空間復雜度為O(nm)。

4 實驗設計與分析

在對模糊概念圖和推理機制的研究中，以《計算機文化基礎》課程為背景，通過概念類型理論對課程中主要知識點進行分析，組成課程的概念類型格[7]。對于概念類型格中任意兩個概念x和y，模糊匹配度μ定義為

μ(x，y)=1-SD(x，y)/max(x)

當x=y時，μ(x，y)=1;x，y不滿足序關系(≤)時，μ(x，y)=0。實際上，要準確得到答案必須將標準答案圖與學生答案圖逐個比較匹配，再取對應節點匹配結果中模糊匹配度的最大值。為了便于根據知識點計算學生最后得分，在概念圖中引入權值，如學生概念圖和標準答案概念圖的匹配結果為模糊概念圖:

[計算機系統|0]—(COMP)→[硬件系統:A~|0.5]

→[軟件系統:B~|0.5]

其中，A~=1/硬件系統+0/OS+0/Windows，B~=0/硬件系統+0.7/OS+0.43/Windows。式中的0和0.5分別為概念節點的權值。設Πu中概念節點k的權值為λk，所指域為模糊集合所取的最大值ρk，題目分值為Pt ，則考生得分Ps為

Ps=Pt∑k∈Cλk×ρk

在本文的研究過程中， 通過《計算機文化基礎》課程中四個簡答題對96名同學課堂測試，試題總數為384，平均每題15個概念，結果如表1所示。在表1中，正確試題率有所提高，另外有10.16%的試題出錯概念數較高。在實際考試中， 只要進一步規范題目文字，正確率可達到90%，基本能滿足實際考試要求，可用于實際考試;另外約10%的題目可在組卷中適當規避或采用人工方式協助批閱。

表1 實驗結果統計

試題數出錯概念數(≦)正確概念率/%正確試題率/%

91010023.70

15228739.58

10247326.56

238475.99

16≧9≦404.17

5 結束語

在人工智能的研究中，知識表示是一個重要研究課題，也是制約人工智能發展的重要瓶頸。本文以概念圖知識表示為基礎，研究了現有模糊概念圖知識表示中存在的問題，提出一種改進的模糊概念圖知識表示方法。在改進的模糊概念圖知識表示基礎上研究了模糊概念圖基于語義約束匹配推理機制，設計了MARSD算法，并定量分析了算法的時間復雜度和空間復雜度。結合高等院校《計算機文化基礎》課程特定主觀題自動閱卷問題，進行了MARSD算法的實驗和應用，運行結果基本達到了實用水平。該課題的研究對于知識表示方法和計算機自動閱卷問題的研究具有一定參考價值。

參考文獻:

[1]SOWA J F. Conceptual structure[M]. New Jersey: Addison Welslely，1984.

[2]MULHEMY P， LEOWZ W K， LEE Y K. Fuzzy conceptual graphs for matching images of natural scenes[C]//Proc of the 17th International Joint Conference on Artificial Intelligence.2001:1397-1407.

[3]MAISONNASSE L， CHEVALLET J P， BERRUT C. Incomplete and fuzzy conceptual graphs to automatically index medical reports[C]//Proc of the 12th International Conference on Applications of Natural Language to Information Systems. Berlin: Springer，2007:240-251.

[4]MORTON S. Conceptual graphs and fuzziness in artificial intelligence[D].Bristol: University of Bristol，1987.

[5]WUWONGSE V， MANZANO M. Fuzzy conceptual graph[C]//Proc ofInternational Conference on Conceptual Graphs for Know Ledge Repre sentation. London: SpringerVerlag，1993: 430-449.

[6]劉培奇，李增智.基于模糊含權概念圖的主觀題自動閱卷方法研究[J].計算機應用研究，2009，26(12):4564- 4567.

[7]劉培奇，李增智.主觀題中模糊含權概念圖匹配問題研究[J].計算機應用研究，2009，26(12):4568-4571.