多粒度空間與知識推理*

折延宏，李美麗西安石油大學 理學院，西安 710065

?

多粒度空間與知識推理*

折延宏+，李美麗
西安石油大學 理學院，西安 710065

SHE Yanhong,LI Meili.Multigranulation space and knowledge reasoning.Journal of Frontiers of Computer Science and Technology,2016,10(6):884-890

摘要：旨在建立起多粒度空間中粗糙近似算子與知識推理中認知算子之間的一一對應關系，從而給出多粒度空間中粗糙近似算子更為合理的語義解釋。對于任意邏輯公式，通過分析其語義集與加了認知算子后的語義集之間的關系，證明了全知算子EG對應于多粒度空間中模型AIU中的下近似算子，公共知識認知算子CG對應于模型RU中的下近似算子，分配知識認知算子DG對應于模型RI中的下近似算子，所得結論是模態邏輯與

*The National Natural Science Foundation of China under Grant Nos.61103133,61472471(國家自然科學基金);the Natural Science Foundation of Shaanxi Province under Grant No.2014JQ1032(陜西省自然科學基金);the Scientific Research Program of Education Department of Shaanxi Province under Grant No.15JK1573(陜西省教育廳科技計劃項目).

Received 2015-06,Accepted 2015-12.

CNKI網絡優先出版:2015-12-29,http://www.cnki.net/kcms/detail/11.5602.TP.20151229.0940.002.html

Pawlak粗糙集之間對應關系在多當事人環境下的推廣。關鍵詞：多粒度空間；粗糙近似；知識推理

ISSN 1673-9418CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(06)-0884-07

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

1　引言

粒計算[1-3]是一種粒化的思維方式及方法論，其核心概念之一是多層次和多視角粒結構。在多層次粒結構中，基本成分是粒與層，不同層次的粒通過粒度組織起來可以構成一個有序的多層次結構。這樣一個多層次結構是對問題的一種描述或觀點，稱為視角（view）。用多個多層次結構描述同一個問題，將形成多視角（multiview）。多視角代表對問題的不同角度的描述和理解。

作為粒計算的一種具體模型，粗糙集[4-5]自從1982年提出以來受到越來越多學者的研究與關注。特別是近年來，與粒計算所提倡的多層次與多視角思想相適應，一種處理多源信息的多粒度粗糙集模型[6-7]被提出。作為多粒度粗糙集模型的一種等價定義，可以證明在樂觀多粒度粗糙集模型中，其上、下近似集是通過對目標對象集在每個Pawlak近似空間下的下近似集取并，對上近似集取交得到的；而在悲觀多粒度粗糙集模型中，則是通過對目標對象集在每個Pawlak近似空間下的下近似集取交，對上近似集取并得到的。換言之，已有的多粒度粗糙集模型通過對每個Pawlak近似空間中的粗糙近似結果利用交、并運算進行合成得到，這自然可看作是多粒度空間中一種特殊的信息融合方式。通過進一步考慮基于等價關系的信息融合方式，可給出另外兩種不同的粗糙近似方式，最終可給出多粒度空間下一種統一的粗糙近似框架。

將邏輯學方法引入到不確定性信息的處理之中可更好實現基于不同數據庫的知識推理，在粗糙集理論中，亦是如此。粗糙集創始人Pawlak提出了粗糙邏輯，并于文獻[8]中指出“粗糙邏輯一種基于粗糙集思想的不精確推理邏輯，似乎是一種最為重要的研究課題”。文獻[9-11]進一步建立了粗糙集與模態邏輯之間的關系，并給出了若干基于粗糙語義的邏輯推理模型。這種融合粗糙集與邏輯推理為一體的思想理應在多粒度認知環境下得到進一步的延伸，這對基于多粒度信息的不確定性推理有較大的理論意義。

本文正是基于如上考慮，從邏輯學角度給出多粒度粗糙集的描述與刻畫。具體為：建立了多粒度近似算子與知識推理中的認知算子之間的密切關系，建立了多粒度空間中不同類型的粗糙近似算子與知識推理中的認知算子之間的對應關系。

本文組織結構如下：第2章給出多粒度空間下粗糙近似的一般框架；第3章介紹知識推理的相關內容；第4章建立多粒度空間下不同粗糙近似模型與知識推理算子之間的對應關系；第5章總結全文。

2　多粒度粗糙集的一般框架

本章通過考慮不同的信息合成方式，給出了多粒度空間下粗糙近似模型的統一框架。在此框架下，定義了兩種不同的粗糙集模型，針對每種粗糙集模型，又分別利用集合的交、并運算，給出不同的子模型。

2.1若干基本知識

本節簡要給出后續討論中需要用到的基本知識。

設U為一非空有限集合，稱為論域，不失一般性，設U中含有m個元素，在以下討論中不單獨說明。稱U×U的任意子集R?U×U為U上的一二元關系：

（1）稱R為自反的，若對于任意x∈U,有(x,x)∈R；

（2）稱R為對稱的，若對于任意x,y∈U，如果(x,y)∈R，則(y,x)∈R；

（3）稱R為傳遞的，若對于任意 x,y,z∈U，由(x,y)∈R以及(y,z)∈R，可推得(x,z)∈R；

（4）稱R為一等價關系，若R滿足自反性、對稱性以及傳遞性。

定義1[12]設R為論域U上的一二元關系，如果有U上的另外一個二元關系R*滿足：（1）R*是傳遞的；（2）R?R*；（3）對于U上的任一滿足傳遞性的二元關系R**，若R?R**，且R*?R**。則稱R*為R的傳遞閉包，記t(R)=R*。

由定義1可以看出，一個關系的傳遞閉包是包含這個關系的最小的傳遞關系。

對于一個二元關系R，R的冪次方按照如下方式定義：

由以上歸納定義，特別是式（1），不難驗證：

Rk={(x,y)|存在x0,x1,?,xk-1,xk,使得x0=x,y=xk,

對于任意j滿足0≤j≤k-1,使得(xj,xj+1)∈R}

2.2已有的多粒度粗糙集模型

本節簡要研究已有的多粒度粗糙集模型，指出這些模型在信息合成方面的特點，這為下一步引入多粒度空間下粗糙近似模型的一般框架做好鋪墊。

定義2[6]設U為一非空集合，稱為論域，E={R1, R2,?,Rn}為論域U上的n個等價關系集，則稱二元組(U,E)為一多粒度近似空間。

文獻[6]首次引入多粒度粗糙集的定義，為了統一起見，本文使用與原文獻[6]稍顯不同的記號系統。

定義3[6]設(U,E)為一多粒度近似空間，對于任意X?U，定義：

根據定義3可推得：

定義4設(U,E)為一多粒度近似空間，對于任意X?U，定義：

根據定義4可推得：

由以上定義可以看得出，在樂觀多粒度下近似中，一個對象x屬于目標集X的下近似當且僅當存在論域上的一個等價關系使得x在該等價關系下的等價類包含于X，而對于悲觀多粒度下近似而言，一個對象x屬于目標集X的下近似，當且僅當x在每一個等價關系下的等價類完全包含于X。前者條件寬松，后者條件苛刻，這正是樂觀與悲觀兩詞的由來。

定義3、定義4給出了多粒度粗糙集模型具有如下等價形式。

命題2設(U,E)為一多粒度近似空間，則?X?U，

值得注意的是，文獻[13]稱(U,E)為一多源近似系統，并稱由命題2中等價定義的粗糙近似算子為強下近似算子、弱上近似算子、弱下近似算子、強上近似算子。這兩種從不同出發點給出的多粒度近似空間中的粗糙近似算子在數學意義下是等價的。

由命題2可知多粒度粗糙集的近似策略：將多粒度近似空間(U,E)看作為n個Pawlak近似空間（或者稱為單粒度近似空間）的組合，對于一目標近似集X?U，在每個Pawlak近似空間下求得X的上、下近似，然后通過集合論中的并、交運算得到最終的多粒度近似結果。或者說，文獻[6,13]給出的多粒度模型是基于對近似結果進行合成的求解策略。

2.3多粒度近似空間中粗糙近似的一般框架

給定一多粒度近似空間(U,E)，以下分別基于對二元關系以及近似結果的合成策略，給出多粒度空間中粗糙近似的一般框架。由此得到的4種粗糙近似模型分別記作模型RI、模型RU、模型AIU以及模型AUI。

（1）模型RI中的粗糙近似

在該模型中，利用集合的交運算將一族等價關系E合成為一個等價關系?E。由于等價關系的任意交還是一等價關系，由一個多粒度近似空間(U,E)出發得到了一Pawlak近似空間(U,?E)。基于此，可給出模型RI中粗糙上、下近似的定義。

定義5[14]設X?U，定義：

（2）模型RU中的粗糙近似

在該模型中，利用等價關系的傳遞閉包將一族等價關系E合成為一個等價關系?*E。由于等價關系的傳遞閉包還是一等價關系，由一個多粒度近似空間(U,E)出發得到了一Pawlak近似空間(U,?*E)。基于此，可給出模型RU中粗糙上、下近似的定義。

定義6[14]設X?U，定義：

同模型RI與RU不同的是，以下給出的兩粗糙近似模型是通過對近似結果（而非等價關系）進行合成得到的。

（3）模型AIU中的粗糙近似

定義7[14]設X?U，定義：

（4）模型AUI中的粗糙近似

與如上類似，通過對下近似集取并集，對上近似集取交集，可定義另外一種不同的多粒度近似空間的粗糙近似模型。

定義8[14]設X?U，定義：

值得注意的是，從不同的信息合成角度出發定義的多粒度空間中的粗糙近似模型AIU與AUI與文獻[6]中給出的樂觀多粒度與悲觀多粒度粗糙集模型是一致的，這由命題2以及定義7、定義8可立即推出。這樣本文給出的多粒度空間中粗糙近似的統一框架自然包括了已有的多粒度粗糙集模型。

3　知識推理

文獻[15]是一本介紹知識推理的經典著作，這里的知識推理包括對客觀知識的推理，也包括對其他當事人知識的推理。同其他邏輯系統一樣，知識推理理論包括語構與語義兩大部分。

在語構方面，知識推理的語言由公式集組成。用Φ表示原子公式集，?表示邏輯非，∧表示邏輯合取，K1,K2,?,Kn表示與n個當事人所對應的模態算子。記全體邏輯公式為F(S)，它按照如下方式生成：

（1）Φ?F(S)；

（2）若φ,ψ∈F(S)，則{?φ,φ∧ψ,Kiφ}?F(S)；

（3）F(S)中任何一邏輯公式均通過（1）、（2）在有限步內生成。

基于?和∧，可引入如下形式的邏輯連接詞：

利用如上邏輯語言，可表達一些更為復雜的邏輯公式。如K1K2p∧?K2K1K2p，它表示第一個當事人知道第二個當事人知道p，而且第二個當事人不知道第一個當事人知道第二個當事人知道p。

除了如上介紹的語構理論之外，知識推理還包括語義理論，即用以判斷給定邏輯公式是否為真的形式化模型。知識推理的語義模型是通過可能世界語義定義的，所對應的數學結構被稱為Kripke結構。適用于當事人的Kripke結構如下：一n+2元組M= (S,π,κ1,κ2,?,κn)，這里S表示一可能世界集（或稱狀態集），對于S中任一狀態s，π(s)為原子公式集上的一賦值映射，即π(s)：Φ→{0,1}。κi是S上的一個二元關系。π(s)(p)告訴人們在狀態s下p是否為真。例如p表示“舊金山正在下雨”，則π(s)(p)=1表示在結構M的狀態s下，命題“舊金山正在下雨”為真。κi描述的是當事人i的可能關系，(s,t)∈κi表示在當事人i看來，在狀態s下，t是可能出現的。在以下討論中，設κi均為等價關系，用記號(M,s)|=φ表示φ在Kripke結構M的狀態s下為真，詳細定義如下：

對于滿足(s,t)∈κi的所有t成立。

在以上邏輯語言中，無法表達類似于公共知識、分配知識等概念。為此，在如上邏輯語言的基礎上，添加如下形式的模態詞。如EG（表示G中每個當事人都知道）、CG（表示某個命題是G中所有成員的公共知識）、DG（表示某個命題是G中成員的分配知識），這里G為{1,2,?,n}的一個非空子集。自然地，若φ是一邏輯公式，則EGφ、CGφ、DGφ也是邏輯公式。在擴充后的邏輯語言中，可以表達諸如K3?C1,2p（即第三個當事人知道p不是第一個當事人與第二個當事人的公共知識）的邏輯公式。

以下給出如EGφ、CGφ、DGφ等邏輯公式在Kripke結構下的賦值語言。

全知知識意思是說G中每個當事人都知道的知識，故在Kripke結構中的語義解釋為：

(M,s)|=EGφ當且僅當對于任意i∈G，(M,s)|=Kiφ。

對于公共知識而言，CGφ指的是G中每個成員都知道φ，G中每個成員都知道G中每個成員都知道φ等。與此相適應，公共知識在Kripke結構中的語義解釋為：

φ是G中成員的分配知識指的是將G中當事人的知識結合起來便可推得φ成立。例如在某Kripke結構中，在狀態s下，第一個當事人認為s、t是可能發生的，而第二個當事人認為s、u是可能的。結合這兩個當事人的知識便知在狀態s下，只有s是可能的。一般來講，通過消除G中當事人認為不可能的狀態便可達到結合G中當事人知識的目的。在數學上，這個通過對在同一狀態下不同當事人認為可能的狀態集進行取交得到，即：

(M,s)|=DGφ當且僅當對于任意(M,t)|=φ對于滿足(s,t)∈∩i∈Gκi的任意t都成立。

4　知識推理與多粒度近似空間

本章基于知識推理中的語義理論，建立起知識推理中的模態算子與多粒度近似空間下近似算子之間的密切聯系，這種聯系自然是文獻[9]中有關粗糙集與模態邏輯在多當事人環境下的推廣。

定義9設M=(S,Φ,κ1,κ2,?,κn)為一Kripke結構，則對于任意φ∈F(S)，定義：

稱v(φ)為φ的真狀態集。

命題3設M=(S,Φ,κ1,κ2,?,κn)為一Kripke結構，則對于任意φ∈F(S)，有：

證明 類似證明在文獻[9]中給出，略。

命題說明知識推理中的模態詞κi對應于Pawlak粗糙下近似算子。

命題4設M=(S,Φ,κ1,κ2,?,κn)為一Kripke結構，則對于任意φ∈F(S)，有：

這里EG={κi|i∈G}。

證明 根據定義，有：

即可得證。

命題4說明知識推理中的全知模態詞對應于多粒度近似空間中AIU模型中的粗糙下近似算子。

命題5設M=(S,Φ,κ1,κ2,?,κn)為一Kripke結構，則對于任意φ∈F(S)，有：

這里EG={κi|i∈G}。

為證明命題5，需要如下引理。

引理1設EG={κi|i∈G}，則對于任意(s,t)∈?*EG，存在自然數 k≥1以及狀態序列 s0,s1,?,sk使得s0=s,t=sk，且對于滿足0≤j≤k-1的任意 j，存在i∈G使得(sj,sj+1)∈κi。

引理2設M=(S,Φ,κ1,κ2,?,κn)為一Kripke結構，s∈S,φ∈F(S)，則s對于任意滿足如下條件（*）的任意t∈S，有M,t|=φ。

（*）存在狀態序列s0,s1,?,sk使得s0=s，t=sk，且對于滿足0≤j≤k-1的任意 j，存在i∈G使得(sj,sj+1)∈κi。

證明 根據M,s|=EGφ的定義，并通過對k進行歸納可以證明。

以下證明命題5。

命題6設M=(S,Φ,κ1,κ2,?,κn)為一Kripke結構，則對于任意φ∈F(S)，有：

這里EG={κi|i∈G}。

證明根據定義可立即推出。

本章結論可通過表1來表示。

Table 1 Relationship between knowledge reasoning and multigranulation space表1　知識推理與多粒度空間的對應關系

5　結束語

粗糙集近似算子與模態邏輯算子之間的對應關系在文獻[9]中已有論述，那里的討論僅局限于單粒度粗糙集與含有一個模態算子的模態邏輯。本文則是將在信息表達能力更強的多粒度近似空間與容納多個客體的知識推理中建立起類似的對應關系。主要結論是知識推理中的全知算子對應于文獻[6]中提出的悲觀下近似算子，即本文統一框架AIU模型中的下近似算子，公共知識算子對應于基于傳遞閉包的下近似算子，分配知識算子對應于基于等價關系交的下近似算子。這些結論為從邏輯角度研究多粒度粗糙集提供了新的思路與方法。

不難看出，若在知識推理中基于模態算子Ki定義其對偶算子以及全知算子的對偶算子，則所定義的算子自然對應于多粒度粗糙集中的悲觀上近似算子。由于模態邏輯與三值邏輯有密切的關系，在后續工作中，進一步從三值邏輯的角度研究多粒度粗糙集。

References:

[1]Lin T Y,Yao Yiyu,Zadeh L A.Data mining,rough sets and granular computing[M].Berlin:Springer Science Business Media,2002.

[2]Yao Yiyu.Perspectives of granular computing[C]//Prceedings of the 2005 IEEE International Conference on Granular Computing.Piscataway,USA:IEEE,2005,1:85-90.

[3]Yao Yiyu.The art of granular computing[M]//Rough Sets and Intelligent Systems Paradigms.Berlin,Heidelberg: Springer,2007:101-112.

[4]Pawlak Z.Rough sets[J].International Journal of Computer and Information Science,1982,11(5):341-356.

[5]Pawlak Z.Rough sets—theoretical aspects of reasoning about data[M].Hingham,USA:KluwerAcademic Publishers,1991.

[6]Qian Yuhua,Liang Jiye,Yao Yiyu,et al.MGRS:a multigranulation rough set[J].Information Sciences,2010,180 (6):949-970.

[7]Qian Yuhua,Liang Jiye,Dang Chuangyin.Incomplete multigranulation rough set[J].IEEE Transactions on Systems, Man and Cybernetics:PartASystems and Humans,2010,40 (2):420-431.

[8]Pawlak Z,Grzymala-Busse J,Slowinski R,et al.Rough sets[J]. Communications of theACM,1995,38(11):88-95.

[9]Yao Yiyu,Lin T Y.Generalization of rough sets using modal logics[J].Intelligent Automation Soft Computing,1996,2 (2):103-119.

[10]Banerjee M,Chakraborty M K.Rough sets through algebraic logic[J].Fundamenta Informaticae,1996,28(3):211-221.

[11]She Yanhong,He Xiaoli,Wang Guojun.Rough truth degrees of formulas and approximate reasoning in rough logic[J]. Fundamenta Informaticae,2011,107(1):67-83.

[12]Wang Guojun.Computation intelligence:computing with wordsandfuzzyset[M].Beijing:HigherEducationPress,2005.

[13]Khan M A,Banerjee M.Formal reasoning with rough sets in multiple-source approximation systems[J].International Journal ofApproximate Reasoning,2008,49(2):466-477.

[14]Yao Yiyu,She Yanhong.Rough set models in multigranulation spaces[J].Information Sciences,2016,327:40-56.

[15]Halpern J Y,Moses Y,Vardi M Y.Reasoning about knowledge[M].Cambridge,USA:MIT Press,1995.

附中文參考文獻:

[12]王國俊.計算智能(第二冊)：詞語計算與Fuzzy集[M].北京:高等教育出版社,2005.

SHE Yanhong was born in 1983.He received the Ph.D.degree in fundamental mathematics from Shaanxi Normal University in 2010.Now he is an associate professor at Xi’an Shiyou University.His research interests include uncertainty reasoning and granular computing,etc.

折延宏（1983—），男，陜西延安人，2010年于陜西師范大學獲得博士學位，現為西安石油大學副教授，主要研究領域為不確定性推理，粒計算等。

LI Meili was born in 1975.She received the Ph.D degree in navigation,guidance and control from Northwestern Polytechnical University in 2010.Now she is a lecturer at Xi’an Shiyou University.Her research interests include granular computing and image processing,etc.

李美麗（1975—），女，陜西渭南人，2010年于西北工業大學獲得博士學位，現為西安石油大學講師，主要研究領域為粒計算，圖像處理等。

+Corresponding author:E-mail:yanhongshe@gmail.com

文獻標志碼：A

中圖分類號：TP18

doi:10.3778/j.issn.1673-9418.1506014

Multigranulation Space and Knowledge Reasoning?

SHE Yanhong+,LI Meili
College of Science,Xi’an Shiyou University,Xi’an 710065,China

Abstract:This paper aims at establishing a one-to-one correspondence between rough approximation operators in multigranulation space and epistemic operators in knowledge reasoning,and thus providing a more reasonable semantic interpretation for rough approximation operators in multigranulation space.By deeply analyzing the close relationship between the semantic set of a logic formula and that of the formula obtained by adding different epistemic operators,this paper proves that EG,CG,DGare in one-to-one correspondence with rough lower approximation operator in model AIU,rough lower approximation operator in model RU and rough lower approximation operator in model RI,respectively.The obtained results are the generalization of the relationship between modal logic and Pawlak rough set in multi-agent environment.

Key words:multigranulation space;rough approximation;knowledge reasoning