序信息系統(tǒng)下的程度可區(qū)分關(guān)系研究

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

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

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

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

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

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

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)

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

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

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

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

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

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

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

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

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

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

顯然有

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

(7)

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

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

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

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

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

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

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

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

(10)

(11)

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

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

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

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

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

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

IND(A)?WIND(A)；

DIS(A)?WDIS(A)。

如果考慮互補(bǔ)關(guān)系，則有：

WDIS(A)=INDC(A)；

WIND(A)=DISC(A)。

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

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

由強(qiáng)可區(qū)分關(guān)系DIS(A)得到：

DISA(x1)=?；

DISA(x2)=?；

DISA(x3)=?；

DISA(x4)={x5}；

DISA(x5)={x4}。

在弱不可區(qū)分關(guān)系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ū)分關(guān)系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}。

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

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

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

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

3　改進(jìn)的程度可區(qū)分關(guān)系

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

定義8設(shè)一個序信息系統(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|，和?代表偏好關(guān)系。對于任意的條件屬性集合B?A，設(shè)γ是程度閾值，0≤γ≤1，改進(jìn)的γ-程度可區(qū)分關(guān)系IGDISγ(B)可定義為

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

式中：

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

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

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

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

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

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

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

進(jìn)而得到：

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

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

觀察發(fā)現(xiàn)，當(dāng)水平γ增大時，對象間的可區(qū)分容忍程度變大，此時知識粒可能變大也可能不變。

4　結(jié)束語

為解決?；^程中知識粒度過細(xì)帶來的分類和決策問題，通過分析信息系統(tǒng)下的不可區(qū)分關(guān)系和可區(qū)分關(guān)系，在程度不可區(qū)分關(guān)系的基礎(chǔ)上，逆向考慮對象間的可區(qū)分程度，提出了γ-程度可區(qū)分關(guān)系。為進(jìn)一步刻畫對象在屬性值上的差異程度，針對整數(shù)名義型數(shù)據(jù)，在序信息系統(tǒng)中提出了一種改進(jìn)的γ-程度可區(qū)分關(guān)系，并且定義了基于改進(jìn)的γ-程度可區(qū)分關(guān)系的概率粗糙集模型?；诔潭瓤蓞^(qū)分關(guān)系下一步可在不完備信息系統(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]張鈸,張鈴.問題求解理論及應(yīng)用 [M].北京:清華大學(xué)出版社,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)中的擴(kuò)充 [J].計算機(jī)研究與發(fā)展, 2002, 39(10):1238.

[12]黃兵,周獻(xiàn)中.基于集對分析的不完備信息系統(tǒng)粗糙集模型 [J].計算機(jī)科學(xué), 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ū)分關(guān)系的粗糙集模型[J].計算機(jī)科學(xué),2015,42(8):240.

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