汪琳娜,楊 新(.四川工商學(xué)院電子信息工程學(xué)院,四川 成都 6745;2.西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院,四川 成都 6756;3.四川工商學(xué)院云計(jì)算與智能信息處理重點(diǎn)實(shí)驗(yàn)室,四川 成都 6745)
1979年Zadeh提出信息粒化(information granulation)的概念[1],試圖用信息粒化思想去發(fā)現(xiàn)知識(shí)。此后出現(xiàn)了采用?;P蛠斫鉀Q實(shí)際問題的情況,例如:1982年P(guān)awlak提出用粗糙集(rough set)理論處理不確定性問題[2];1990年張鈸等提出采用商空間(quotient space)模型解決信息融合、路徑規(guī)劃和推理等問題[3];1996年Zadeh提出了采用詞計(jì)算(computing with words)模型來進(jìn)行計(jì)算及推理[4];Lin 正式提出粒計(jì)算(granular computing)一詞[5-7],其后Zadeh根據(jù)粒計(jì)算思想,指出人類認(rèn)知由?;?、組織、因果3部分構(gòu)成,知識(shí)?;闪W?,然后又可按照某種關(guān)系組織在一起,進(jìn)而揭示原因和結(jié)果的聯(lián)系[8]。目前粒計(jì)算已經(jīng)成為人工智能計(jì)算領(lǐng)域中解決知識(shí)發(fā)現(xiàn)和模擬人類認(rèn)知的有效方法。知識(shí)的?;侨绾伟阎R(shí)從整體分解為部分,這已經(jīng)成為當(dāng)前粒計(jì)算研究的熱點(diǎn)問題。
Pawlak提出的經(jīng)典粗糙集模型是利用不可區(qū)分關(guān)系(indiscernibility relation),即等價(jià)關(guān)系,對(duì)論域進(jìn)行劃分,得到不可區(qū)分的等價(jià)類,然后在近似空間中構(gòu)造上下近似算子來逼近邊界模糊的集合,從而發(fā)現(xiàn)不確定性知識(shí)。在經(jīng)典粗糙集理論中,知識(shí)粒化依賴于不可區(qū)分關(guān)系(等價(jià)關(guān)系),當(dāng)把完備信息系統(tǒng)過渡到不完備信息系統(tǒng)時(shí),需要對(duì)等價(jià)關(guān)系進(jìn)行泛化,對(duì)自反性、對(duì)稱性和傳遞性重新組合得到其他二元關(guān)系,如Kryszkjewicz[9]提出的容差關(guān)系,Stefanowski等[10]提出的量化容差關(guān)系,王國(guó)胤[11]提出的限制容差關(guān)系,黃兵等[12]提出的基于集對(duì)聯(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個(gè)對(duì)象存在某一屬性不相等,則2個(gè)對(duì)象一定不在同一等價(jià)類;但是在實(shí)際完備信息系統(tǒng)?;^程中,有可能會(huì)出現(xiàn)每一個(gè)對(duì)象是一個(gè)等價(jià)類的知識(shí)粒度最細(xì)情況。此時(shí),?;Y(jié)果顯然不利于對(duì)信息的處理,需要進(jìn)一步對(duì)對(duì)象的相似性進(jìn)行刻畫,即如果對(duì)象滿足一定相似精度,在屬性不完全相等的情況下也可以分到同一類。Yao等[14]對(duì)粗糙集中的可區(qū)分關(guān)系(discernibility relation)和不可區(qū)分關(guān)系展開對(duì)立分析,提出了4種對(duì)象間的關(guān)系,即強(qiáng)不可區(qū)分關(guān)系、弱不可區(qū)分關(guān)系、強(qiáng)可區(qū)分關(guān)系和弱可區(qū)分關(guān)系,并基于以上關(guān)系提出了3種屬性約簡(jiǎn)的方式。秦克云等[15]提出采用程度不可區(qū)分關(guān)系的概念來刻畫信息系統(tǒng)中對(duì)象的可區(qū)分性程度的差異。本文在程度不可區(qū)分關(guān)系的基礎(chǔ)上,提出了程度可區(qū)分關(guān)系,并針對(duì)名義型數(shù)據(jù)在序信息系統(tǒng)中考慮屬性值的相似程度,進(jìn)一步提出了改進(jìn)的程度可區(qū)分關(guān)系,研究在信息粒度較細(xì)的情況下如何通過刻畫屬性值間的差異來進(jì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上的一個(gè)等價(jià)關(guān)系,表示U上任何2個(gè)對(duì)象在所有屬性上屬性值都相等,滿足自反、對(duì)稱、傳遞性質(zhì)。通過IND(A)可以對(duì)U進(jìn)行劃分,記為U/IND(A),對(duì)于任意1個(gè)對(duì)象x∈U,[x]A表示在IND(A)劃分下包含x的等價(jià)類,即[x]A={y∈U|(x,y)∈IND(A)}。為方便,簡(jiǎn)記等價(jià)關(guān)系為RA,等價(jià)類為[x]。
弱不可區(qū)分關(guān)系WIND(A)表示任意2個(gè)對(duì)象至少在一個(gè)屬性上屬性值相同,滿足自反、對(duì)稱性質(zhì),但不滿足傳遞性質(zhì)。
相對(duì)于不可區(qū)分關(guān)系,強(qiáng)可區(qū)分關(guān)系DIS(A)表示2個(gè)對(duì)象在所有屬性上都不相等,滿足對(duì)稱性質(zhì),但不滿足自反、傳遞性質(zhì)。弱可區(qū)分關(guān)系WDIS(A)表示2個(gè)對(duì)象至少在一個(gè)屬性上屬性值不相等,同樣滿足對(duì)稱性質(zhì),但不滿足自反、傳遞性質(zhì)。
其中,關(guān)于X的(α,β)正域、邊界域、負(fù)域定義為:
POS(α,β)(X)={x∈U|Pr(X|[x])≥α};
BND(α,β)(X)={x∈U|β NEG(α,β)(X)={x∈U|Pr(X|[x])≤β}。 定義5[15]設(shè)信息系統(tǒng)S=(U,A,V,f),對(duì)于任意B?A,由B誘導(dǎo)的程度不可區(qū)分關(guān)系GINDB(A),是U上的二元模糊關(guān)系,即GINDB:U×U→[0,1],且對(duì)于任意x,y∈U,有 從定義中可以看出,程度不可區(qū)分關(guān)系GINDB(A)表示B中不能區(qū)分x和y的屬性在B中所占的比例,且滿足自反和對(duì)稱性質(zhì),不滿足傳遞性質(zhì),用來刻畫對(duì)象間不可區(qū)分的程度。相反,如果要刻畫對(duì)象間可區(qū)分關(guān)系,可以得到程度可區(qū)分關(guān)系為 顯然有 GINDB(x,y)+GDISB(x,y)=1, (7) 且程度可區(qū)分關(guān)系GDIS(B)滿足自反和對(duì)稱性質(zhì),不滿足傳遞性質(zhì)。 當(dāng)GIND(A)=0,GDIS(A)=1時(shí),程度不可區(qū)分關(guān)系GIND(A)和程度可區(qū)分關(guān)系GDIS(A)同時(shí)泛化為強(qiáng)可區(qū)分關(guān)系DIS(A);當(dāng)0 程度不可區(qū)分關(guān)系GIND(A)是從對(duì)象間屬性相等的程度來描述不可區(qū)分的程度。程度可區(qū)分關(guān)系GDIS(A)是從對(duì)象間屬性不相等的程度來描述可區(qū)分程度。雖然從程度不可區(qū)分關(guān)系可以直接得到程度可區(qū)分關(guān)系,但是2種關(guān)系的分析視角不同,會(huì)導(dǎo)致對(duì)知識(shí)進(jìn)一步?;姆椒ê徒Y(jié)果不同。 如果假設(shè)一個(gè)程度閾值δ和δ′,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時(shí),δ-程度不可區(qū)分關(guān)系GINDδ(A)和δ′-程度可區(qū)分關(guān)系GDISδ′(A)同時(shí)泛化為強(qiáng)不可區(qū)分關(guān)系IND(A);當(dāng)0<δ<1時(shí),δ-程度不可區(qū)分關(guān)系GINDδ(A)泛化為弱不可區(qū)分關(guān)系WIND(A)。當(dāng)0<δ′<1時(shí),δ′-程度可區(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個(gè)對(duì)象間的關(guān)系,對(duì)?x,y∈U,關(guān)系矩陣可以定義為: 例1設(shè)一個(gè)學(xué)生成績(jī)信息表,對(duì)象集U={x1,x2,x3,x4,x5},分別代表不同的學(xué)生,屬性集A={a1,a2,a3,a4},分別代表語文、數(shù)學(xué)、英語、歷史,每個(gè)屬性的值域?yàn)閧1,2,3,…,6,7},代表成績(jī)的優(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)系下對(duì)象間的關(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)劃分得到的等價(jià)類為 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}。 由以上計(jì)算可知:在強(qiáng)不可區(qū)分關(guān)系IND(A)下產(chǎn)生了最細(xì)的劃分,每個(gè)對(duì)象兩兩之間都是可以區(qū)分的;在強(qiáng)可區(qū)分關(guān)系DIS(A)下,只有對(duì)象x3和x4之間的每個(gè)屬性都不相等,而其他對(duì)象容差類都是空集;在弱不可區(qū)分關(guān)系WIND(A)和弱可區(qū)分關(guān)系WDIS(A)下,對(duì)對(duì)象間關(guān)系的容忍又過大。此時(shí)4種關(guān)系均不利于進(jìn)一步分類和決策。 注意到對(duì)象x1、x2、x3之間只在a1屬性下可區(qū)分,其他屬性均不可區(qū)分。為體現(xiàn)不可區(qū)分的程度,根據(jù)GINDδ(A)的定義,設(shè)δ=3/4,計(jì)算得到δ-程度不可區(qū)分關(guān)系GINDδ(A)下對(duì)象間的關(guān)系矩陣為 因此,由δ-程度不可區(qū)分關(guān)系可得到: 可以看出,無論如何改變閾值δ,對(duì)象x1、x2、x3的不可區(qū)分程度始終相同,如果要進(jìn)一步刻畫對(duì)象間的相似度,只能考慮對(duì)象x1、x2、x3在屬性a1下的取值差異,即屬性值的可區(qū)分程度;因此,有必要從可區(qū)分程度研究知識(shí)?;?。觀察表1可以發(fā)現(xiàn),在屬性a1下x2和x1、x3屬性值相差較大,但是x1和x3屬性值相差較小,即學(xué)生x1和x3在語文上成績(jī)相差不大,但是學(xué)生x2和學(xué)生x1、x3在語文上成績(jī)相差太大,如果考慮具體分類和決策問題,顯然x1和x3應(yīng)該劃分到同一類,但如果考慮在語文屬性下的差異程度,此時(shí)x2不適宜與x1、x3在同一類。為了進(jìn)一步刻畫對(duì)象間的可區(qū)分程度,下面提出一種基于序信息系統(tǒng)的改進(jìn)程度可區(qū)分關(guān)系。 程度可區(qū)分關(guān)系主要是刻畫對(duì)象間可區(qū)分的程度??紤]進(jìn)一步刻畫對(duì)象間可區(qū)分程度,下面在序信息系統(tǒng)中針對(duì)名義型數(shù)據(jù),考慮屬性值的差別定義改進(jìn)的γ-程度可區(qū)分關(guān)系。 定義8設(shè)一個(gè)序信息系統(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)系。對(duì)于任意的條件屬性集合B?A,設(shè)γ是程度閾值,0≤γ≤1,改進(jìn)的γ-程度可區(qū)分關(guān)系IGDISγ(B)可定義為 IGDISγ(B)={(x,y)∈U|IGDISB(x,y)≤γ}。 (13) 式中: 其中,|Vai|是屬性ai值域的取值個(gè)數(shù),abs表示取絕對(duì)值。 從定義可知,?x,y∈U,0≤IGDISB(x,y)<1。γ-程度可區(qū)分關(guān)系IGDISγ(B)滿足自反和對(duì)稱性質(zhì),但不滿足傳遞關(guān)系。當(dāng)γ=0時(shí),γ-程度可區(qū)分關(guān)系IGDISγ(B)退化為等價(jià)關(guān)系IND(B)。 改進(jìn)的γ-程度可區(qū)分關(guān)系IGDISγ(B)主要針對(duì)整數(shù)名義型數(shù)據(jù),可以在序信息系統(tǒng)下進(jìn)一步刻畫對(duì)象間的相似度。下面給出基于改進(jìn)的γ-程度可區(qū)分關(guān)系IGDISγ(B)的概率粗糙集模型的定義。 定義9設(shè)信息系統(tǒng)S=(U,A,V,f),IGDISγ(A)是改進(jìn)的γ-程度可區(qū)分關(guān)系,給定一對(duì)閾值(α,β),并且滿足0≤β<α≤1,對(duì)于任意的X?U,則關(guān)于X的概率粗糙集的上下近似集定義為: 定理1設(shè)X,Y?U,則上述概率粗糙集的上下近似算子滿足以下性質(zhì): 根據(jù)改進(jìn)的γ-程度可區(qū)分關(guān)系IGDISγ(A),以表1為例計(jì)算可得: 由此可看出,x1,x2,x3相互間的可區(qū)分程度得到進(jìn)一步刻畫。取γ=2/28,計(jì)算得到程度可區(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)水平γ增大時(shí),對(duì)象間的可區(qū)分容忍程度變大,此時(shí)知識(shí)??赡茏兇笠部赡懿蛔?。 為解決?;^程中知識(shí)粒度過細(xì)帶來的分類和決策問題,通過分析信息系統(tǒng)下的不可區(qū)分關(guān)系和可區(qū)分關(guān)系,在程度不可區(qū)分關(guān)系的基礎(chǔ)上,逆向考慮對(duì)象間的可區(qū)分程度,提出了γ-程度可區(qū)分關(guān)系。為進(jìn)一步刻畫對(duì)象在屬性值上的差異程度,針對(duì)整數(shù)名義型數(shù)據(jù),在序信息系統(tǒng)中提出了一種改進(jìn)的γ-程度可區(qū)分關(guān)系,并且定義了基于改進(jìn)的γ-程度可區(qū)分關(guān)系的概率粗糙集模型?;诔潭瓤蓞^(qū)分關(guān)系下一步可在不完備信息系統(tǒng)下討論,還可以在考慮屬性重要度的情況下刻畫對(duì)象間的可區(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]王國(guó)胤.Rough集理論在不完備信息系統(tǒng)中的擴(kuò)充 [J].計(jì)算機(jī)研究與發(fā)展, 2002, 39(10):1238. [12]黃兵,周獻(xiàn)中.基于集對(duì)分析的不完備信息系統(tǒng)粗糙集模型 [J].計(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ì)算機(jī)科學(xué),2015,42(8):240. [16]YAO Y Y. Probabilistic rough set approximations [J]. International Journal of Approximate Reasoning, 2008, 49(2): 255.2 程度不可區(qū)分關(guān)系和程度可區(qū)分關(guān)系
3 改進(jìn)的程度可區(qū)分關(guān)系
4 結(jié)束語