汪琳娜，楊　新(.四川工商學院電子信息工程學院，四川 成都 6745；2.西南交通大學信息科學與技術學院，四川 成都 6756；3.四川工商學院云計算與智能信息處理重點實驗室，四川 成都 6745)

1979年Zadeh提出信息?；?information granulation)的概念[1]，試圖用信息?；枷肴グl(fā)現(xiàn)知識。此后出現(xiàn)了采用?；Ｐ蛠斫鉀Q實際問題的情況，例如：1982年Pawlak提出用粗糙集(rough set)理論處理不確定性問題[2]；1990年張鈸等提出采用商空間(quotient space)模型解決信息融合、路徑規(guī)劃和推理等問題[3]；1996年Zadeh提出了采用詞計算(computing with words)模型來進行計算及推理[4]；Lin 正式提出粒計算(granular computing)一詞[5-7]，其后Zadeh根據(jù)粒計算思想，指出人類認知由粒化、組織、因果3部分構成，知識?；闪Ｗ樱缓笥挚砂凑漳撤N關系組織在一起，進而揭示原因和結果的聯(lián)系[8]。目前粒計算已經(jīng)成為人工智能計算領域中解決知識發(fā)現(xiàn)和模擬人類認知的有效方法。知識的?；侨绾伟阎R從整體分解為部分，這已經(jīng)成為當前粒計算研究的熱點問題。

Pawlak提出的經(jīng)典粗糙集模型是利用不可區(qū)分關系(indiscernibility relation)，即等價關系，對論域進行劃分，得到不可區(qū)分的等價類，然后在近似空間中構造上下近似算子來逼近邊界模糊的集合，從而發(fā)現(xiàn)不確定性知識。在經(jīng)典粗糙集理論中，知識粒化依賴于不可區(qū)分關系(等價關系)，當把完備信息系統(tǒng)過渡到不完備信息系統(tǒng)時，需要對等價關系進行泛化,對自反性、對稱性和傳遞性重新組合得到其他二元關系，如Kryszkjewicz[9]提出的容差關系，Stefanowski等[10]提出的量化容差關系，王國胤[11]提出的限制容差關系，黃兵等[12]提出的基于集對聯(lián)系度的容差關系，Grzymala-busse[13]提出的特征關系。其后，眾多學者提出了不完備系統(tǒng)下的各種二元關系，但完備信息系統(tǒng)下的?；P系研究卻較少。

在完備信息系統(tǒng)下，在基于不可區(qū)分關系的各種粗糙集里，如果2個對象存在某一屬性不相等，則2個對象一定不在同一等價類；但是在實際完備信息系統(tǒng)?；^程中，有可能會出現(xiàn)每一個對象是一個等價類的知識粒度最細情況。此時，?；Y果顯然不利于對信息的處理，需要進一步對對象的相似性進行刻畫，即如果對象滿足一定相似精度，在屬性不完全相等的情況下也可以分到同一類。Yao等[14]對粗糙集中的可區(qū)分關系(discernibility relation)和不可區(qū)分關系展開對立分析，提出了4種對象間的關系，即強不可區(qū)分關系、弱不可區(qū)分關系、強可區(qū)分關系和弱可區(qū)分關系，并基于以上關系提出了3種屬性約簡的方式。秦克云等[15]提出采用程度不可區(qū)分關系的概念來刻畫信息系統(tǒng)中對象的可區(qū)分性程度的差異。本文在程度不可區(qū)分關系的基礎上，提出了程度可區(qū)分關系，并針對名義型數(shù)據(jù)在序信息系統(tǒng)中考慮屬性值的相似程度，進一步提出了改進的程度可區(qū)分關系，研究在信息粒度較細的情況下如何通過刻畫屬性值間的差異來進行更好的決策和分類。

1　不可區(qū)分關系和可區(qū)分關系

定義2[14]設信息系統(tǒng)S=(U,A,V,f)，強不可區(qū)分關系、弱不可區(qū)分關系、強可區(qū)分關系、弱可區(qū)分關系分別定義為：

IND(A)={(x,y)∈U2|?a∈A,f(a,x)=f(a,y)}；

WIND(A)={(x,y)∈U2|?a∈A,f(a,x)=f(a,y)}；

DIS(A)={(x,y)∈U2|?a∈A,f(a,x)≠f(a,y)}；

WDIS(A)={(x,y)∈U2|?a∈A,f(a,x)≠f(a,y)}。

(1)

其中，強不可區(qū)分關系IND(A)是U上的一個等價關系，表示U上任何2個對象在所有屬性上屬性值都相等，滿足自反、對稱、傳遞性質。通過IND(A)可以對U進行劃分，記為U/IND(A)，對于任意1個對象x∈U，[x]A表示在IND(A)劃分下包含x的等價類，即[x]A={y∈U|(x,y)∈IND(A)}。為方便，簡記等價關系為RA，等價類為[x]。

弱不可區(qū)分關系WIND(A)表示任意2個對象至少在一個屬性上屬性值相同，滿足自反、對稱性質，但不滿足傳遞性質。

相對于不可區(qū)分關系，強可區(qū)分關系DIS(A)表示2個對象在所有屬性上都不相等，滿足對稱性質，但不滿足自反、傳遞性質。弱可區(qū)分關系WDIS(A)表示2個對象至少在一個屬性上屬性值不相等，同樣滿足對稱性質，但不滿足自反、傳遞性質。

其中，關于X的(α,β)正域、邊界域、負域定義為：

POS(α,β)(X)={x∈U|Pr(X|[x])≥α}；

BND(α,β)(X)={x∈U|β

NEG(α,β)(X)={x∈U|Pr(X|[x])≤β}。

2　程度不可區(qū)分關系和程度可區(qū)分關系

定義5[15]設信息系統(tǒng)S=(U,A,V,f)，對于任意B?A，由B誘導的程度不可區(qū)分關系GINDB(A)，是U上的二元模糊關系，即GINDB:U×U→[0,1],且對于任意x,y∈U,有

從定義中可以看出，程度不可區(qū)分關系GINDB(A)表示B中不能區(qū)分x和y的屬性在B中所占的比例，且滿足自反和對稱性質，不滿足傳遞性質，用來刻畫對象間不可區(qū)分的程度。相反，如果要刻畫對象間可區(qū)分關系，可以得到程度可區(qū)分關系為

顯然有

GINDB(x,y)+GDISB(x,y)=1，

(7)

且程度可區(qū)分關系GDIS(B)滿足自反和對稱性質，不滿足傳遞性質。

當GIND(A)=0，GDIS(A)=1時，程度不可區(qū)分關系GIND(A)和程度可區(qū)分關系GDIS(A)同時泛化為強可區(qū)分關系DIS(A)；當0

程度不可區(qū)分關系GIND(A)是從對象間屬性相等的程度來描述不可區(qū)分的程度。程度可區(qū)分關系GDIS(A)是從對象間屬性不相等的程度來描述可區(qū)分程度。雖然從程度不可區(qū)分關系可以直接得到程度可區(qū)分關系，但是2種關系的分析視角不同，會導致對知識進一步粒化的方法和結果不同。

如果假設一個程度閾值δ和δ′，0≤δ≤1，0≤δ′≤1，則δ-程度不可區(qū)分關系定義為

GINDδ(A)={(x,y)∈U|GINDA(x,y)≥δ}。(8)

δ′-程度可區(qū)分關系定義為

GDISδ′(A)={(x,y)∈U|GDISA(x,y)≤δ′}。(9)

下面分別給出基于δ-程度不可區(qū)分關系GINDδ(A)和基于δ′-程度可區(qū)分關系GDISδ′(A)的概率粗糙集的定義。

(10)

(11)

當δ=1，δ′=0時，δ-程度不可區(qū)分關系GINDδ(A)和δ′-程度可區(qū)分關系GDISδ′(A)同時泛化為強不可區(qū)分關系IND(A)；當0<δ<1時，δ-程度不可區(qū)分關系GINDδ(A)泛化為弱不可區(qū)分關系WIND(A)。當0<δ′<1時，δ′-程度可區(qū)分關系GDISδ′(A)泛化為弱可區(qū)分關系WDIS(A)。

為分析比較程度不可區(qū)分關系GINDδ(A)和程度可區(qū)分關系GDISδ′(A)，下面先給出關系矩陣的定義，然后通過例子說明2種關系間的區(qū)別和聯(lián)系。

定義7設信息系統(tǒng)S=(U,A,V,f)，RrA表達U上任意2個對象間的關系，對?x,y∈U，關系矩陣可以定義為：

例1設一個學生成績信息表，對象集U={x1,x2,x3,x4,x5}，分別代表不同的學生，屬性集A={a1,a2,a3,a4}，分別代表語文、數(shù)學、英語、歷史，每個屬性的值域為{1,2,3,…,6,7}，代表成績的優(yōu)劣程度，從1到7分別表示{非常差，比較差，一般差，中等，一般好，比較好，非常好}。信息表如表1所示。

根據(jù)上文提到的4種關系IND(A)、WIND(A)、DIS(A)、WDIS(A)的定義，可以分別得到在強不可區(qū)分關系、弱不可區(qū)分關系、強可區(qū)分關系和弱可區(qū)分關系下對象間的關系矩陣：

顯然，不可區(qū)分關系和可區(qū)分關系存在聯(lián)系，弱不可區(qū)分關系包含強可區(qū)分關系，弱可區(qū)分關系包含強可區(qū)分關系，即：

IND(A)?WIND(A)；

DIS(A)?WDIS(A)。

如果考慮互補關系，則有：

WDIS(A)=INDC(A)；

WIND(A)=DISC(A)。

由表1可知，由強不可區(qū)分關系IND(A)劃分得到的等價類為

U/IND(A)={{x1},{x2},{x3},{x4},{x5}}。

由強可區(qū)分關系DIS(A)得到：

DISA(x1)=?；

DISA(x2)=?；

DISA(x3)=?；

DISA(x4)={x5}；

DISA(x5)={x4}。

在弱不可區(qū)分關系WIND(A)得到：

WINDA(x1)={x1,x2,x3,x4,x5}；

WINDA(x2)={x1,x2,x3,x4,x5}；

WINDA(x3)={x1,x2,x3,x4,x5}；

WINDA(x4)={x1,x2,x3,x4}；

WINDA(x5)={x1,x2,x3,x5}。

在弱可區(qū)分關系WDIS(A)得到：

WDISA(x1)={x2,x3,x4,x5}；

WDISA(x2)={x1,x3,x4,x5}；

WDISA(x3)={x1,x2,x4,x5}；

WDISA(x4)={x1,x2,x3,x5}；

WDISA(x5)={x1,x2,x3,x4}。

由以上計算可知：在強不可區(qū)分關系IND(A)下產(chǎn)生了最細的劃分，每個對象兩兩之間都是可以區(qū)分的；在強可區(qū)分關系DIS(A)下，只有對象x3和x4之間的每個屬性都不相等，而其他對象容差類都是空集；在弱不可區(qū)分關系WIND(A)和弱可區(qū)分關系WDIS(A)下，對對象間關系的容忍又過大。此時4種關系均不利于進一步分類和決策。

注意到對象x1、x2、x3之間只在a1屬性下可區(qū)分，其他屬性均不可區(qū)分。為體現(xiàn)不可區(qū)分的程度，根據(jù)GINDδ(A)的定義，設δ=3/4，計算得到δ-程度不可區(qū)分關系GINDδ(A)下對象間的關系矩陣為

因此，由δ-程度不可區(qū)分關系可得到：

可以看出，無論如何改變閾值δ，對象x1、x2、x3的不可區(qū)分程度始終相同，如果要進一步刻畫對象間的相似度，只能考慮對象x1、x2、x3在屬性a1下的取值差異，即屬性值的可區(qū)分程度；因此，有必要從可區(qū)分程度研究知識?；Ｓ^察表1可以發(fā)現(xiàn)，在屬性a1下x2和x1、x3屬性值相差較大，但是x1和x3屬性值相差較小，即學生x1和x3在語文上成績相差不大，但是學生x2和學生x1、x3在語文上成績相差太大，如果考慮具體分類和決策問題，顯然x1和x3應該劃分到同一類，但如果考慮在語文屬性下的差異程度，此時x2不適宜與x1、x3在同一類。為了進一步刻畫對象間的可區(qū)分程度，下面提出一種基于序信息系統(tǒng)的改進程度可區(qū)分關系。

3　改進的程度可區(qū)分關系

程度可區(qū)分關系主要是刻畫對象間可區(qū)分的程度?？紤]進一步刻畫對象間可區(qū)分程度，下面在序信息系統(tǒng)中針對名義型數(shù)據(jù)，考慮屬性值的差別定義改進的γ-程度可區(qū)分關系。

定義8設一個序信息系統(tǒng)S=(U,A,V,f),假定所有的條件屬性值都是整數(shù)名義型，且屬性值都是遞增或遞減偏好有序的，即?ai∈A，Vai={v1,v2,…,vj,…,v|Vai|}，vj∈N+且v1v2…v|Vai|或v1?v2?…?v|Vai|，和?代表偏好關系。對于任意的條件屬性集合B?A，設γ是程度閾值，0≤γ≤1，改進的γ-程度可區(qū)分關系IGDISγ(B)可定義為

IGDISγ(B)={(x,y)∈U|IGDISB(x,y)≤γ}。 (13)

式中：

其中，|Vai|是屬性ai值域的取值個數(shù)，abs表示取絕對值。

從定義可知，?x,y∈U,0≤IGDISB(x,y)<1。γ-程度可區(qū)分關系IGDISγ(B)滿足自反和對稱性質，但不滿足傳遞關系。當γ=0時，γ-程度可區(qū)分關系IGDISγ(B)退化為等價關系IND(B)。

改進的γ-程度可區(qū)分關系IGDISγ(B)主要針對整數(shù)名義型數(shù)據(jù)，可以在序信息系統(tǒng)下進一步刻畫對象間的相似度。下面給出基于改進的γ-程度可區(qū)分關系IGDISγ(B)的概率粗糙集模型的定義。

定義9設信息系統(tǒng)S=(U,A,V,f)，IGDISγ(A)是改進的γ-程度可區(qū)分關系，給定一對閾值(α,β)，并且滿足0≤β<α≤1，對于任意的X?U，則關于X的概率粗糙集的上下近似集定義為：

定理1設X,Y?U，則上述概率粗糙集的上下近似算子滿足以下性質：

根據(jù)改進的γ-程度可區(qū)分關系IGDISγ(A)，以表1為例計算可得：

由此可看出，x1,x2,x3相互間的可區(qū)分程度得到進一步刻畫。取γ=2/28，計算得到程度可區(qū)分關系矩陣

進而得到：

觀察發(fā)現(xiàn)，在改進的γ-程度可區(qū)分關系GDISBγ下，x2和x1、x3沒有在同一類。這是由于x2和x1、x3雖然在屬性a2、a3、a4下相同，但是在屬性a1下的屬性值相差較大。

如果取γ=3/28，可以得到：

觀察發(fā)現(xiàn)，當水平γ增大時，對象間的可區(qū)分容忍程度變大，此時知識?？赡茏兇笠部赡懿蛔?。

4　結束語

為解決粒化過程中知識粒度過細帶來的分類和決策問題，通過分析信息系統(tǒng)下的不可區(qū)分關系和可區(qū)分關系，在程度不可區(qū)分關系的基礎上，逆向考慮對象間的可區(qū)分程度，提出了γ-程度可區(qū)分關系。為進一步刻畫對象在屬性值上的差異程度，針對整數(shù)名義型數(shù)據(jù)，在序信息系統(tǒng)中提出了一種改進的γ-程度可區(qū)分關系，并且定義了基于改進的γ-程度可區(qū)分關系的概率粗糙集模型。基于程度可區(qū)分關系下一步可在不完備信息系統(tǒng)下討論，還可以在考慮屬性重要度的情況下刻畫對象間的可區(qū)分程度。

[1]ZADEH L A. Fuzzy sets and information granularity in advances in Fuzzy set theory and applications [M]. Amsterdam: North-Holland Publishing, 1979.

[2]PAWLAK Z. Rough set [J]. International Journal of Computer and Information Science, 1982, 11(5):341.

[3]張鈸,張鈴.問題求解理論及應用 [M].北京:清華大學出版社,1990.

[4]ZADEH L A. Fuzzy logic-computing with words [J]. IEEE Trans on Fuzzy Systems, 1996, 4(2):103.

[5]LIN T Y Y.Granular Computing [R]. [S.l.]:Announcement of the BISC Special Interest Group on Granular Computing, 1997.

[6]LIN T Y Y.Granular computing on binary relations I: data mining and neighborhood systems [J].Rough Sets in Knowledge Discovery，1998(2):165.

[7]LIN T Y Y. Data mining and machine oriented modeling: a granular computing approach [J]. Journal of Applied Intelligence, 2000, 13(2):113.

[8]ZADEH L A. Towards a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic [J]. Fuzzy Sets and Systems, 1997, 90(2):111.

[9]KRYSZKIEWICZ M. Rough set approach to incomplete information systems [J]. Information Sciences，1998，112(1): 39.

[10]STEFANOWSKI J, TSOUKIAS A. Incomplete information tables and rough classification [J]. Computational Intelligence, 2001, 17(3):545.

[11]王國胤.Rough集理論在不完備信息系統(tǒng)中的擴充 [J].計算機研究與發(fā)展, 2002, 39(10):1238.

[12]黃兵,周獻中.基于集對分析的不完備信息系統(tǒng)粗糙集模型 [J].計算機科學, 2002, 29(9):1.

[13]GRZYMALA-BUSSE J W. A rough set approach to data with missing attribute values [C]//Proceedings of the 1st International Conference of Rough Sets and Knowledge Technology (RSKT2006).chongqing: Springer-Verlag Berlin, Heidelberg,2006:58-67.

[14]YAO Y Y, ZHAO Y. Conflict analysis based on discernibility and indiscernibility [J]. IEEE Symposium on Foundations of Computational Intelligence， 2007, 177 (22):302.

[15]秦克云,羅珺方.基于程度不可區(qū)分關系的粗糙集模型[J].計算機科學,2015,42(8):240.

[16]YAO Y Y. Probabilistic rough set approximations [J]. International Journal of Approximate Reasoning, 2008, 49(2): 255.