劉城霞, 何華燦, 張仰森, 朱敏玲

1.北京郵電大學(xué) 計(jì)算機(jī)學(xué)院, 北京　100876; 2.北京信息科技大學(xué), 北京　100101 3.西北工業(yè)大學(xué), 陜西 西安　710072

?

基于泛邏輯的泛容差關(guān)系的研究

劉城霞1,2, 何華燦1,3, 張仰森2, 朱敏玲2

1.北京郵電大學(xué) 計(jì)算機(jī)學(xué)院, 北京100876; 2.北京信息科技大學(xué), 北京100101 3.西北工業(yè)大學(xué), 陜西 西安710072

摘要：粗糙集是用確定的方法處理不確定信息和數(shù)據(jù)，但它要求屬性信息是離散的,而且針對(duì)的是完備信息系統(tǒng)。而泛邏輯是研究人工智能領(lǐng)域中的不確定性、不完全性以及模糊性，它針對(duì)的信息可以是離散的，也可以是連續(xù)的。針對(duì)不完備信息系統(tǒng)擴(kuò)展泛邏輯中的泛等價(jià)關(guān)系，得到泛容差關(guān)系，并對(duì)連續(xù)或離散的屬性取值應(yīng)用泛容差關(guān)系進(jìn)行分類，代替原來(lái)的擴(kuò)展粗糙集中的容差關(guān)系，定義新的相似度的計(jì)算方法，進(jìn)而進(jìn)行數(shù)據(jù)填充，最后用實(shí)例進(jìn)行了應(yīng)用說(shuō)明。

關(guān)鍵詞：粗糙集；泛邏輯；容差關(guān)系；泛容差關(guān)系

粗糙集理論[1]在1982 年由波蘭數(shù)學(xué)家Pawlak提出的一種處理不精確、不確定和模糊數(shù)據(jù)的數(shù)學(xué)工具，它能有效地從數(shù)據(jù)本身提供的信息中發(fā)現(xiàn)有效、潛在的知識(shí)。近年來(lái)該理論成功地在機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、智能數(shù)據(jù)分析等領(lǐng)域得到了廣泛應(yīng)用，受到了眾多學(xué)者的重視，取得了很大的發(fā)展。

泛邏輯理論[2]是本世紀(jì)初由何華燦教授提出的，它是針對(duì)人工智能等領(lǐng)域中傳統(tǒng)邏輯無(wú)法解決的問(wèn)題而開展的。它是在二值邏輯、多值邏輯和模糊邏輯的基礎(chǔ)上，研究人工智能領(lǐng)域中的不確定性、不完全性以及模糊性的一種柔性邏輯。其中對(duì)命題的真值域、命題連接詞、量詞等都進(jìn)行了柔性化，可以全面反映命題真值的不確定性、真值誤差的不確定性、命題之間相關(guān)關(guān)系的不確定性等，使之更適合于現(xiàn)實(shí)世界的推理規(guī)則。泛邏輯和粗糙集都適用于處理不精確、不確定的信息，而這也給二者的結(jié)合帶來(lái)了可行性與便利性。

1粗糙集理論基礎(chǔ)及其擴(kuò)充

1.1完備信息系統(tǒng)下的粗糙集理論基礎(chǔ)

(1)若?aj∈C使得V中不含空值,即f(xi,aj)≠φ,則稱S是完備信息系統(tǒng),即所處理的信息表是完備的,每個(gè)樣本對(duì)象的所有屬性值都是已知的。粗糙集理論正是基于完備信息系統(tǒng)這樣一個(gè)假設(shè)。

為便于數(shù)學(xué)推導(dǎo),粗糙集中通常用等價(jià)關(guān)系代替分類。定義R代表論域U上的一種關(guān)系,它可以是一種屬性的描述,也可以是一個(gè)屬性集合的描述。在一般敘述中,R 等價(jià)關(guān)系和R屬性都是同一概念。在屬性約簡(jiǎn)中,把任意非空屬性子集看做是關(guān)系R。任取非空屬性子集R?A,如果xi,xj∈U,?ak∈R,f(xi,ak)=f(xj,ak)均成立,則稱xi,xj關(guān)于R不可分辨,R為不可分辨關(guān)系,記為IND(R)。IND(R)即可把論域U中的元素分為若干個(gè)等價(jià)類,全體等價(jià)類的集合記為U/IND(R)。

給定信息系統(tǒng)S=(U,A,V,F),?X?U和等價(jià)關(guān)系R,則X關(guān)于R的下近似和上近似分別定義如下:

下近似

(2)上近似

(3)式中，[x]R表示的是包含元素x∈U的R等價(jià)類。

根據(jù)上、下近似的定義給出邊界域、正域和負(fù)域的概念如下：

BNDR(X)=R-(X)-R-(X) 稱為X的R邊界域。

POSR(X)=R-(X) 稱為X的R正域。

NEGR(X)=U-R-(X) 稱為X的R負(fù)域。

由上述定義可知下近似R-(X)和正域POSR(X)表示在知識(shí)R下論域U中確定屬于集合X的對(duì)象集,上近似R-(X)表示在知識(shí)R下論域U中可能屬于集合X的對(duì)象集,所以邊界域BNDR是在知識(shí)R不能確定是否屬于集合X的對(duì)象集,負(fù)域NEGR(X)則表示在知識(shí)R下論域U中與集合X無(wú)關(guān)的對(duì)象集。

1.2不完備信息系統(tǒng)中擴(kuò)充粗糙集模型的容差關(guān)系及量化容差關(guān)系

粗糙集理論是基于完備信息系統(tǒng)的,當(dāng)信息系統(tǒng)不完備時(shí),需要進(jìn)行數(shù)據(jù)補(bǔ)齊或?qū)Υ植诩Ｐ瓦M(jìn)行擴(kuò)充。數(shù)據(jù)補(bǔ)齊主要采用某種方法(通常是概率統(tǒng)計(jì))對(duì)所有未知屬性值進(jìn)行填補(bǔ),將不完備信息系統(tǒng)轉(zhuǎn)化為完備信息系統(tǒng),然后用經(jīng)典粗糙集理論來(lái)處理。比如現(xiàn)有的c4.5、刪除法、最大頻率法等[3]。數(shù)據(jù)補(bǔ)齊法應(yīng)用起來(lái)十分簡(jiǎn)便,但它是對(duì)原始信息系統(tǒng)中未知屬性值的一種人為估計(jì),對(duì)原始信息系統(tǒng)的信息有不同程度的擾動(dòng),不能反映原始系統(tǒng)的真實(shí)情況,獲得的知識(shí)可用性差。模型擴(kuò)展主要是將經(jīng)典粗糙集理論中的不可分辨關(guān)系這一等價(jià)關(guān)系擴(kuò)充為非等價(jià)關(guān)系,直接處理不完備信息系統(tǒng)。比如Kryszkiewicz提出容差關(guān)系[4],Stefanowski等人提出的非對(duì)稱相似關(guān)系[5],Stefanowski等人提出的量化容差關(guān)系[6],王國(guó)胤等人提出的限制容差關(guān)系[7],Grzymala-Buss提出的特征關(guān)系[8]等,都是對(duì)粗糙集運(yùn)算模型的擴(kuò)充。文獻(xiàn)[9]對(duì)不完備系統(tǒng)的粗糙集擴(kuò)充方法進(jìn)行了總結(jié)和研究。

1.2.1容差關(guān)系

當(dāng)不完備信息系統(tǒng)S中所有未知屬性值是遺漏型時(shí),對(duì)屬非空屬性子集B?A,M.Kryszkiewicz提出了如下容差關(guān)系

(4)

對(duì)任意對(duì)象x∈U的容差類

(5)

對(duì)象子集X?U的下近似和上近似分別為

(6)

(7)

容差關(guān)系滿足自反性和對(duì)稱性,但不一定滿足傳遞性。

1.2.2量化容差關(guān)系

對(duì)于不完備信息系統(tǒng)中的個(gè)體, 由于已知信息的不同, 也可以根據(jù)已知信息的相同程度來(lái)刻畫它們之間的相近似程度。 據(jù)此,Stefanowski等人提出了基于量化容差關(guān)系的擴(kuò)充Rough集模型。

在不完備信息系統(tǒng)S中,?b∈A記

(8)

若U中對(duì)象對(duì)每個(gè)屬性的取值獨(dú)立且均勻分布,則任意對(duì)象?x,y∈U關(guān)于屬性子集的相似度可定義為

(9)

容差關(guān)系所描述的樣本對(duì)象之間相似度的取值范圍是{0,1},Ⅰ型量化容差關(guān)系雖然將樣本對(duì)象相似度的取值范圍擴(kuò)充到了[0,1],但需要知道屬性取值的概率分布等相關(guān)知識(shí)。

量化容差關(guān)系還有不同的改進(jìn)模型,在文獻(xiàn)[10]中,定義了改進(jìn)的量化容差關(guān)系。

(10)

2泛邏輯理論基礎(chǔ)

本文第二作者為了探索邏輯的一般規(guī)律,提出建立能包容各種邏輯形態(tài)和推理模式的泛邏輯學(xué)理論。泛邏輯學(xué)針對(duì)現(xiàn)代邏輯中存在的缺陷,基于三角范數(shù)理論,利用廣義相關(guān)性和廣義自相關(guān)性將邏輯關(guān)系定義為一組連續(xù)可變的算子簇,并提出了和如何使用該算子簇中的算子,真正實(shí)現(xiàn)了模糊邏輯關(guān)系的柔性化。這里為簡(jiǎn)化計(jì)算,先不考慮廣義自相關(guān)性,只考慮廣義相關(guān)性,那么用到的零級(jí)泛邏輯理論。

1) 零級(jí)泛與及泛或

經(jīng)過(guò)多年的發(fā)展,現(xiàn)在普遍認(rèn)同的是以T范數(shù)表示邏輯與,以T余范數(shù)S表示邏輯或。T范數(shù)和S范數(shù)是是泛邏輯學(xué)研究泛與/或運(yùn)算的數(shù)學(xué)基礎(chǔ)。用h表示的是廣義相關(guān)性,對(duì)零級(jí)不確定性問(wèn)題, 用2個(gè)僅受h控制的函數(shù)F0(x,h)=xm和G0(x,h)=1-(1-x)m作為零級(jí)T性生成元完整簇和零級(jí)S性生成元完整簇,把它們帶入泛與何泛或運(yùn)算的基模型分別生成的零級(jí)T范數(shù)完整簇T(x,y,h)和零級(jí)S范數(shù)完整簇S(x,y,h)如下

(11)

(12)

式中

由于廣義相關(guān)系數(shù)h是連續(xù)變化的,因此會(huì)有無(wú)限多個(gè)連續(xù)的T(x,y,h)算子和S(x,y,h)算子。

2) 零級(jí)泛蘊(yùn)含與泛等價(jià)

由零級(jí)T性生成元完整簇F0(x,h)=xm代入蘊(yùn)含運(yùn)算的基模型生成零級(jí)I范數(shù)完整簇

(13)

記作由零級(jí)T性生成元完整簇F0(x,h)=xm代入等價(jià)運(yùn)算的基模型生成零級(jí)I范數(shù)完整簇

(14)

記作?h。

其中h>0.75為+,否則為-,m=(3-4h)/

(4h(1-h)),h=(1+m)-((1+m)2-3m)1/2)

/(2m)。

它有的4個(gè)特殊算子是:

最小等價(jià),又稱Zadeh等價(jià)Q(x,y,1)=Q3=ite{1|x=y;min(x,y)}

(15)

中極等價(jià),又稱概率等價(jià)Q(x,y,0.75)=Q2=min(x/y,y/x)

(16)

(Ⅰ等價(jià))

中心等價(jià),又稱有界等價(jià)

(17)

最大等價(jià)又稱突變等價(jià)Q(x,y,0)=Q0=ite{x|y=1;y|x=1;1}

(18)

3泛容差關(guān)系與相似度計(jì)算

在完備系統(tǒng)不可分辨關(guān)系定義中要求xi,xj∈U,?ak∈R,f(xi,ak)=f(xj,ak)均成立,這個(gè)定義適合離散型屬性,對(duì)于連續(xù)型的屬性,一般的做法是先將其離散化,然后再使用不可分辨關(guān)系進(jìn)行等價(jià)類的劃分。然而,離散化的算法、精度都會(huì)影響分類的效率和準(zhǔn)確性,進(jìn)而影響屬性約簡(jiǎn)的效率。如果能直接對(duì)連續(xù)屬性進(jìn)行不可分辨關(guān)系的分類,就可以避免人為離散化引起的取值誤差,而且可以省略離散化過(guò)程,提高效率和精度。

完備信息系統(tǒng)中可以用泛邏輯的泛等價(jià)關(guān)系

(19)

來(lái)作為不可分辨關(guān)系,則當(dāng)Qb(x,y,h)>1-α?xí)r認(rèn)為等價(jià),其中α為閥值,否則不等價(jià)。其中

這里h為廣義相關(guān)系數(shù),可以在使用時(shí)根據(jù)實(shí)際需要進(jìn)行調(diào)整。在多數(shù)情況下系統(tǒng)中用到的是相容相關(guān),即h∈[0.5,1],文中案例也是相容相關(guān)情況的實(shí)例。xi,k,xj,k代表xi,xj的屬性ak的值。利用該泛等價(jià)關(guān)系處理離散屬性時(shí)和原等價(jià)關(guān)系一致,連續(xù)屬性可以直接處理而不需要進(jìn)行離散化,有關(guān)該泛等價(jià)的性質(zhì)及證明在另外的文章中有詳細(xì)論述。

3.1泛容差關(guān)系

當(dāng)信息系統(tǒng)不完備時(shí),所有未知屬性值是遺漏型時(shí),對(duì)屬非空屬性子集B?A,定義泛容差關(guān)系

(20)

對(duì)任意對(duì)象x∈U的容差類

(21)

對(duì)象子集X?U的下近似和上近似分別為

(22)

(23)

泛容差關(guān)系滿足自反性和對(duì)稱性,但不一定滿足傳遞性。

對(duì)于泛容差關(guān)系,可以對(duì)其進(jìn)行量化,參考1.2.2中量化容差關(guān)系的定義,定義泛容差關(guān)系的量化方法

(24)

式中，N(bj±ba)代表的是屬性b取值在bj±ba范圍內(nèi)的對(duì)象個(gè)數(shù),如為離散屬性,則為屬性b取值等于bj的對(duì)象個(gè)數(shù),bα為滿足Qb(x,y,h)>(1-α)的該屬性的閥值。N表示所有在屬性b上有值的對(duì)象的個(gè)數(shù),Nbi表示對(duì)屬性b分類后每類的對(duì)象個(gè)數(shù),b為離散屬性時(shí)即為屬性b取值等于bi,i=1,…,m的對(duì)象個(gè)數(shù),b為連續(xù)屬性時(shí)即為屬性b取值分類每類的對(duì)象個(gè)數(shù)。

性質(zhì)1當(dāng)屬性全部為離散值時(shí),泛容差關(guān)系TQB相當(dāng)于容差關(guān)系；

性質(zhì)1證明當(dāng)屬性全部為離散值時(shí),泛容差關(guān)系TQB相當(dāng)于容差關(guān)系。

即當(dāng)屬性全部為離散值時(shí),泛容差關(guān)系TQB中Qb(x,y,h)>1-α等價(jià)于b(x)=b(y)。

顯然,當(dāng)b(x)=b(y)時(shí),Qb(x,y,h)=1>1-α成立。

當(dāng)Qb(x,y,h)>1-α即

以h=0.5為例,此時(shí)m=1

當(dāng)屬性離散時(shí),令閥值α取值小于任意2個(gè)屬性值之差,則|b(x)-b(y)|<α?xí)rb(x)=b(y)。

3.2實(shí)例分析

現(xiàn)以某醫(yī)院有關(guān)流感診斷的原始數(shù)據(jù)信息表S0=(U,A,V,F)為例,進(jìn)行對(duì)比分析。論域U={x1,x2,x3,x4,x5,x6,x7,x8,x9},屬性集合A={a1,a2,a3,a4,d}分別代表肌肉酸痛、咳嗽、頭痛、體溫和決策屬性是否為流感,a1,a2,a3取值集合為{0,1,2,3},分別代表{無(wú)癥狀,輕微,較嚴(yán)重,嚴(yán)重),a4取值集合為連續(xù)型數(shù)據(jù),取值范圍[35,40],d為決策屬性,取值集合為{0,1,2}分別代表{不是,疑似,是}?！?”表示遺漏值。

表1　連續(xù)型不完備信息系統(tǒng)表S0

對(duì)體溫屬性進(jìn)行離散化,[35,36.25)離散化為0,[36.25,37.5)離散化為1,[37.5,38.75)離散化為2,[38.75,40]離散化為3,離散化后取值{0,1,2,3},分別代表{偏低,正常,偏高,高}。

表2　離散化后的不完備信息系統(tǒng)表S0

表量化容差矩陣TⅡ

表4　根據(jù)量化容差矩陣TⅡ進(jìn)行補(bǔ)齊后的信息表SⅡb

由于TⅡ中對(duì)象間相似度都不同,所以取相似度大的進(jìn)行補(bǔ)齊,得到了完備信息系統(tǒng)SⅡ。

表量化容差矩陣Th

x4,xg2個(gè)對(duì)象的相似度

表6　根據(jù)量化容差矩陣Th進(jìn)行補(bǔ)齊后的信息表Sh

4結(jié)論

應(yīng)用粗糙集理論指導(dǎo)數(shù)據(jù)挖掘已經(jīng)應(yīng)用非常廣泛,但粗糙集有自身的局限性。比如必須要使用離散型數(shù)據(jù),必須是完備系統(tǒng)等。本文從對(duì)理論擴(kuò)展的角度,針對(duì)不完備系統(tǒng)應(yīng)用泛容差對(duì)容差關(guān)系進(jìn)行了重新定義,使之可以針對(duì)連續(xù)型數(shù)據(jù)進(jìn)行劃分,是對(duì)不完備系統(tǒng)下粗糙集運(yùn)算模型的擴(kuò)展。

參考文獻(xiàn)：

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

[2]何華燦. 泛邏輯學(xué)原理[M]. 北京：科學(xué)出版社，2001

He Huacan. The Theory of Universal Logic[M]. Beijing, Science Press, 2001 (in Chinese)

[3]Grzylama-Busse J W, Hu M. A Comparison of Several Approaches to Missing Attribute Values in Data Mining[C]∥Proceedings of the Second International Conference on Rough Sets and Current Trends in Conlputing RSCTC 2000, Banf, Canada, Springer Berlin, 2000: 340-347

[4]Kryszkiewicz M. Rough Set Approach to Incomplete Information Systems[J]. Information Sciences, 1998, 112: 39-49

[5]Stefanowski J, Tsoukias A. Incomplete Information Tables and Rough Classification[J]. Computational Intelligence, 2001, 17(3): 545-566

[6]Stefanowski J, Tsoukias A. Valued Tolerance and Decision Rules[C]∥Volume 2005 of Lecture Notes in Artificial Intelligence Berlin, Springer, 2001: 212-219

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

Wang Guoyin. Extension of Rough Set Under Incomplete Information System[J]. Journal of Computer Research and Development, 2002, 39(10): 1238-1243 (in Chinese)

[8]Grzymala-Busse J W. Rough Set Strategies to Data with Missing Attribute Values[C]∥The 3rd International Conference on Data Mining. Melbourne，F(xiàn)L，USA, 2003: 56-63

[9]官禮和. 基于粗糙集理論的不完備信息處理方法研究[J]. 重慶郵電大學(xué)學(xué)報(bào)，2009,21(4)：461-466

Guan Lihe. Processing Incomplete Information Methods Based on Rough Set[J]. Journal of Chongqing University of Posts and Telecommunications, 2009, 21(4): 461-466 (in Chinese)

[10] 鄧耀進(jìn), 李仁發(fā). 一種粗糙集理論中量化容差關(guān)系的改進(jìn)[J]. 計(jì)算機(jī)工程與科學(xué)，2009, 31(10): 105-108

Deng Yaojin, Li Renfa. An Improvement on the Valued Tolerance Relation in the Rough Set Theory[J]. Computer Engineering & Science, 2009, 31(10): 105-108 (in Chinese)

[11] Gao Yuqin, Fang Guohua, Liu Yaqin.θ-Improved Limited Tolerance Relation Model of Incomplete Information System for Evaluation of Water Conservancy Project Management Modernization[J]. Water Science and Engineering, 2013, 6(4): 469-477

收稿日期：2015-10-27

基金項(xiàng)目：“促進(jìn)高校內(nèi)涵發(fā)展-專業(yè)建設(shè)-面向大類人才培養(yǎng)模式的2016專業(yè)培養(yǎng)方案修訂”項(xiàng)目資助

作者簡(jiǎn)介：劉城霞(1978—)，女，北京郵電大學(xué)博士研究生，主要從事數(shù)據(jù)挖掘、粗糙集及泛邏輯的研究。

中圖分類號(hào)：TP301.6

文獻(xiàn)標(biāo)志碼：A

文章編號(hào):1000-2758(2016)03-0473-07

The Study of Universal Tolerance Relation Based on Universal Logic

Liu Chengxia1,2, He Huacan1,3, Zhang Yangsen2, Zhu Minling2

1.Computer School, Beijing University of Posts and Telecommunications, Beijing 100876, China 2.Beijing Information and Technology University, Beijing 100101, China 3.Northwestern Polytechnical University, Xi′an 710072, China

Abstract:Rough set theory can be used to deal with the imprecise data and information by certain method but its basis is that the attribute′s value must be discrete and the system must be complete .Universal logic can do with the uncertain, incomplete and fuzzy information in artificial intelligence and the data can be discrete or continuous. Use the universal logic to redefine the tolerance relation and use universal tolerance relation to classify the continuous or discrete attribute, we can extend the scope of application of rough set theory and universal logic. This paper makes focus on the new concept of universal tolerance relation and new computation method of similarity between objects and then we can complete the data based on this. At last an example is given to illustrate it.

Keywords:rough set; universal logic; tolerance relation; universal tolerance relation