基于內(nèi)外因分析的粗糙近似算子*

許黎明, 何小衛(wèi)

(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華 321004)

0 引 言

粗糙集理論是由波蘭數(shù)學(xué)家Pawlak在1982年提出的處理不完全與不精確問(wèn)題的有效的數(shù)學(xué)工具[1]，該理論在數(shù)據(jù)分析[2-3]、知識(shí)發(fā)現(xiàn)[4-5]、數(shù)據(jù)挖掘[6-7]、決策支持與分析[8-9]等方面得到了廣泛的應(yīng)用.經(jīng)典的粗糙集理論是建立在分類機(jī)制的基礎(chǔ)上，將分類理解成特定空間上的等價(jià)關(guān)系，這種等價(jià)關(guān)系構(gòu)成了對(duì)該空間的劃分.粗糙集理論的主要思想是將不確定和不精確知識(shí)用已知的知識(shí)來(lái)刻畫(huà).與其他處理不確定性和不精確問(wèn)題理論相比，粗糙集不需要提供問(wèn)題所需處理的數(shù)據(jù)集合之外的任何先驗(yàn)信息，所以它對(duì)問(wèn)題的不確定性的描述是比較客觀的.

Pawlak粗糙集模型的推廣是粗糙集理論研究的一個(gè)重要研究方向.Pawlak粗糙集模型的推廣有2種方法：構(gòu)造性方法和公理化方法.構(gòu)造性方法主要是從給定的近似空間出發(fā)去研究粗糙集和近似算子，由于這種方法研究的問(wèn)題一般源于實(shí)際，所以所建立的數(shù)學(xué)模型具有很強(qiáng)的應(yīng)用價(jià)值，但不容易深刻揭示近似算子的代數(shù)結(jié)構(gòu)，如一般關(guān)系下的粗糙集模型[10]、變精度粗糙集模型[11 ]、基于領(lǐng)域算子的粗糙集模型[12]、基于隨機(jī)集的粗糙集模型[13-14]等等.公理化的方法又稱為代數(shù)方法，它的主要思路是事先給定一對(duì)近似算子L和H：2U→2U.這種方法雖能深刻揭示近似算子的代數(shù)結(jié)構(gòu)，但應(yīng)用性不強(qiáng).除了以上對(duì)粗糙集模型推廣研究之外，還有把粗糙集理論用于概念格數(shù)據(jù)分析之中[15]，它體現(xiàn)了概念內(nèi)涵和外延的統(tǒng)一, 反映了對(duì)象和特征間的聯(lián)系以及概念間的泛化與例化關(guān)系.

粗糙集模型的各種推廣研究把粗糙集的理論研究和應(yīng)用滲透到各種領(lǐng)域，特別是信息系統(tǒng)的約簡(jiǎn)[16]、規(guī)則提取和屬性重要性分析等等.但運(yùn)用粗糙集對(duì)信息系統(tǒng)的研究,基本上只考慮靜態(tài)的信息系統(tǒng)，雖然也有學(xué)者對(duì)粗糙集的動(dòng)態(tài)特性進(jìn)行了一些研究[17]，但沒(méi)有考慮信息系統(tǒng)變化的外在因素.信息系統(tǒng)數(shù)據(jù)的變化是由外因驅(qū)動(dòng)的.筆者嘗試建立基于外因驅(qū)動(dòng)的動(dòng)態(tài)信息系統(tǒng)模型，用粗糙集的方法研究外因在信息系統(tǒng)數(shù)據(jù)變化過(guò)程中的作用.

1 預(yù)備知識(shí)

2 基于外因驅(qū)動(dòng)的單步動(dòng)態(tài)信息系統(tǒng)模型

內(nèi)因是事物變化的根據(jù)和基礎(chǔ)，外因是事物變化的條件，外因通過(guò)內(nèi)因起作用.動(dòng)態(tài)信息系統(tǒng)屬性數(shù)據(jù)的變化也是由外因驅(qū)動(dòng)的，不同屬性變化的外因是不同的，本文基于以上動(dòng)態(tài)信息系統(tǒng),建立了基于外因驅(qū)動(dòng)的動(dòng)態(tài)信息系統(tǒng)模型，用粗糙集的方法研究外因在信息系統(tǒng)數(shù)據(jù)變化過(guò)程中的作用.

考慮信息系統(tǒng)S在外部各種因素的作用下發(fā)生了變化，假設(shè)變化后的信息系統(tǒng)為S′=(U′,A′,V′,f′).稱S為初始信息系統(tǒng)，S′為目標(biāo)信息系統(tǒng)，信息系統(tǒng)S在外部條件W的作用下轉(zhuǎn)化為S′,其中W是外因 .

為了討論方便，嘗試在最簡(jiǎn)單的情況下對(duì)動(dòng)態(tài)的信息系統(tǒng)建立模型，假設(shè)滿足以下條件：1)W是非空有限的條件屬性集；2)信息系統(tǒng)變化過(guò)程中論域U和屬性集合A都不發(fā)生變化，即U=U′，A=A′；3)根據(jù)哲學(xué)中外因?qū)κ挛锇l(fā)展變化是通過(guò)內(nèi)因起作用的原理，假設(shè)信息系統(tǒng)的變化是通過(guò)A中各個(gè)屬性值的變化來(lái)體現(xiàn)，即ρa(bǔ);Va→V′a.

一個(gè)外因?qū)傩阅苡|發(fā)的屬性值遷移的集合記為

gR={(a,x,x′)∈Ω|gR(a,x,x′)}?Ω;

(1)

g能觸發(fā)的變遷屬性集合記為

(2)

所有能觸發(fā)屬性值遷移(a,x,x′)∈Ω的外因集合記為

R(a,x,x′)={g∈W|gR(a,x,x′)}?W;

(3)

所有能觸發(fā)屬性a上的屬性值遷移的外因集合記為

(4)

以下幾種表示方法是等價(jià)的

3 近似算子對(duì)外因與內(nèi)因的分析

上面建立了基于外因驅(qū)動(dòng)的單步動(dòng)態(tài)信息系統(tǒng)模型，接下來(lái)將給出2對(duì)近似算子，用以刻畫(huà)外部因素和屬性值變遷及變遷屬性集之間的關(guān)系.

定義3設(shè)T=(Ω,W,R)為外因驅(qū)動(dòng)的近似空間，Ω是S到S′的屬性值變遷集，G?W，定義一對(duì)近似算子▽,△：2W→2Ω為：

G▽={(a,x,x′)∈Ω| ?g∈W(gR(a,x,x′)?g∈G)}={(a,x,x′)∈Ω|R(a,x,x′)?G};

(5)

G△={(a,x,x′)∈Ω| ?g∈W(gR(a,x,x′)∧g∈G)}=

(6)

根據(jù)定義3的算子定義，W中能觸發(fā)G▽中的屬性值變遷的外部因素全都在G中，W中能觸發(fā)G▽中的屬性值變遷的外部因素至少有1個(gè)在G中.

定義4設(shè)T=(Ω,W,R)為外因驅(qū)動(dòng)的近似空間，Ω是S到S′的屬性值變遷集，X?Ω，定義一對(duì)近似算子▽,△:2Ω→2W為：

X▽={g∈W| ?(a,x,x′)∈Ω(gR(a,x,x′)?(a,x,x′)∈X)}={g∈W|gR?X};

(7)

X△={g∈W| ?(a,x,x′)∈W(gR(a,x,x′)∧(a,x,x′)∈X)}=

(8)

根據(jù)定義4的算子定義，X▽中每一個(gè)外因?qū)傩阅苡|發(fā)的屬性值變遷全都在X中，X△中每一個(gè)外因?qū)傩阅苡|發(fā)的屬性值變遷至少有1個(gè)在X中.

定理1假設(shè)G,G1,G2?W;X,X1,X2?Ω,則算子▽和△具有以下性質(zhì)：

1)GC▽C=G△,GC△C=G▽;XC▽C=X△,XC△C=X▽.其中C表示集合的補(bǔ)集.

2)若?(a,x,x′)∈Ω,R(a,x,x′)≠φ，則G▽?G△;若?g∈Ω,gR≠φ，則X▽?X△.

3)G1?G2?(G▽1?G▽2,G△1?G△2);X1?X2?(X▽1?X▽2,X△1?X△2) .

4)G▽△?G?G△▽;X▽△?X?X△▽.

5)G▽△▽=G▽,G△▽△=G△;X▽△▽=X▽,X△▽△=X△.

6)(G1∩G2)▽=G▽1∩G▽2,(G1∪G2)△=G△1∪G△2;(X1∩X2)▽=X▽1∩X▽2,(X1∪X2)△=X△1∪X△2.

證明 以GC▽C=G△和X▽△▽=X▽的證明為例 ，其余的證明方法類似，故略.

1)GC▽C=G△.

若(a,x,x′)∈GC▽C,則只需證明(a,x,x′)∈G△.假設(shè) (a,x,x′)?G△，則R(a,x,x′)∩G=φ,即R(a,x,x′)?GC,所以(a,x,x′)∈GC▽.矛盾.故(a,x,x′)∈G△.

若(a,x,x′)∈G△,則只需證明(a,x,x′)∈GC▽C.假設(shè)(a,x,x′)?GC▽C，則(a,x,x′)∈GC▽,即R(a,x,x′)?GC.又由假設(shè)條件(a,x,x′)∈G△得,R(a,x,x′)∩G≠φ.矛盾.故(a,x,x′)∈GC▽C.

綜上所述，GC▽C=G△.

2)X▽△▽=X▽.

若g∈X▽△▽,則gR?X▽△.那么，對(duì)所有的(a,x,x′)∈Ω,有g(shù)R(a,x,x′)?(a,x,x′)∈X▽△,即gR(a,x,x′)?R(a,x,x′)∩X▽≠φ.其中：gR(a,x,x′)意味著存在一個(gè)w∈W， 使得wR(a,x,x′)∧w∈X▽成立;w∈X▽意味著wR?X成立.由wR?X和wR(a,x,x′)可得到(a,x,x′)∈X成立.則對(duì)所有的(a,x,x′)∈Ω,gR(a,x,x′)?(a,x,x′)∈X,即g∈X▽成立.

若g∈X▽,則對(duì)于?(a,x,x′)∈Ω,有g(shù)R(a,x,x′)?R(a,x,x′)∩X▽≠φ成立,故對(duì)?(a,x,x′)∈Ω,gR(a,x,x′)?(a,x,x′)∈X▽△?g∈X▽△▽.

綜上所述，X▽△▽=X▽.

定義5設(shè)T=(Ω,W,R)為式(2)所描述的近似空間，Ω是S到S′的屬性值變遷集，G?W，定義一對(duì)近似算子★,☆:2W→2A為:

(9)

(10)

根據(jù)定義5的算子定義，W中能觸發(fā)G★中的屬性發(fā)生值變遷的外部因素全都在G中，W中能觸發(fā)G☆中的屬性發(fā)生值變遷的外部因素至少有1個(gè)包含在G中.

定義6設(shè)T=(Ω,W,R)為式(2)所描述的近似空間，Ω是S到S′的屬性值變遷集，X?A，定義一對(duì)近似算子★,☆：2A→2W為:

(11)

(12)

根據(jù)定義6的算子定義，X★中每一個(gè)外因?qū)傩阅苡|發(fā)值變遷的屬性全都在X中，X☆中每一個(gè)外因?qū)傩阅苡|發(fā)值變遷的屬性至少有1個(gè)包含在X中.

定理2假設(shè)G,G1,G2?W;X,X1,X2?A,則算子★和☆具有以下性質(zhì)：

1)GC★C=G☆,GC☆C=G★;XC★C=X☆,XC☆C=X★.

2)若?(a,x,x′)∈Ω,R(a,x,x′)≠φ，則G★?G☆;若?g∈Ω,gR≠φ,則X★?X☆.

3)G1?G2?(G★1?G★2,G☆1?G☆2);X1?X2?(X★1?X★2,X☆1?X☆2).

4)G★☆?G?G☆★;X★☆?X?X☆★.

5)G★☆★=G★,G☆★☆=G☆;X★☆★=X★,X☆★☆=X☆.

6)(G1∩G2)★=G★1∩G★2,(G1∪G2)☆=G☆1∪G☆2;(X1∩X2)★=X★1∩X★2,(X1∪X2)☆=X☆1∪X☆2.

證明 與定理1的證明類似,故略.

定理3假設(shè)G?W,X?A,則算子▽,△,★和☆具有以下性質(zhì)：

1)G★?Π(G▽),G☆?Π(G△)；

2)X▽?(Π(X))★,X△?(Π(X))☆；

3)GC★?Π(GC▽),GC☆?Π(GC△)；

4)XC▽?(Π(XC))★,XC△?(Π(XC))☆.

證明 1)只證明G★?Π(G▽),G☆?Π(G△)的證明與G★?Π(G▽)相似,故略.

3)與4)的證明中只需用GC替換1)中的G，用XC替換2)中的X,即可獲得證明.

4 結(jié) 語(yǔ)

本文根據(jù)事物發(fā)展變化過(guò)程中內(nèi)外因的哲學(xué)原理，建立了信息系統(tǒng)變化的動(dòng)態(tài)模型，提出了屬性值變遷集和屬性變遷集的概念，在經(jīng)典的二元關(guān)系下構(gòu)造了2對(duì)近似算子▽,△和★,☆,用以刻畫(huà)外部因素對(duì)屬性變化的作用以及2對(duì)算子之間的聯(lián)系.以后需要做的工作還很多，比如考慮在模糊關(guān)系下來(lái)討論外因和內(nèi)部屬性變化之間的聯(lián)系等等.

[1]Pawlak Z.Rough sets[J].International Journal of Computer and Information and Sciences,1982,11:341-356.

[2]Pawlak Z.Rough sets and intelligent data analysis[J].Information Sciences,2002,147(1/2/3/4):1-12.

[3]Yao Yiyu.A comparative study of formal concept analysis and rough set theory in data analysis[C]//Rough Sets and Current Trends in Computing.Berlin：Springer,2004:59-68.

[4]Michal R C,Grzymala-Busse J W.Global discretization of continuous attributes as preprocessing for machine learning[J].International Journal of Approximate Reasoning,1996,15(4):319-331.

[5]Pawlak Z.Rough sets:Theoretical Aspects of Reasoning about Data[M].Boston:Kluwer Academic Publishers,1991.

[6]Chan Chienchung.A rough set approach to attribute generalization in data mining[J].Journal of Information Sciences,1998,107(1):169-176.

[7]Lingras P J,Yao Yiyu.Data mining using extensions of the rough set model[J].Journal of the American Society for Information Science,1998,49(5):415-422.

[8]David M S.Knowledge discovery by inspection[J].Decision Support Systems,1997,21(1):43-47.

[9]Pawlak Z.Rough set approach to Knowledge-based decision support[J].European Journal of Operational Research,1997,99(1):48-57.

[10]Yao Yiyu,Lin T Y.Generalization of rough sets using modal logic[J].Intelligent Automation and Soft Computing,1996(2):103-120.

[11]Ziarko W.Variable precision rough set model[J].Journal of Computer and System Sciences,1993,46(1):39-59.

[12]Yao Yiyu.Relational Interpretations of Neighborhood Operators and Rough Set Approximation Operators[J].Information Sciences,1998,111(1/2/3/4):239-259.

[13]張文修,吳偉志.基于隨機(jī)集的粗糙集模型(Ⅰ)[J].西安交通大學(xué)學(xué)報(bào),2000,34(12):75-79.

[14]張文修,吳偉志.基于隨機(jī)集的粗糙集模型(Ⅱ)[J].西安交通大學(xué)學(xué)報(bào),2001,35(4):425-429.

[15]Yao Yiyu,Chen Yaohua.Rough set approximation in formal concept analysis,Transactions on Rough Sets[M].Berlin：Springer,2006:285-305.

[16]商琳，萬(wàn)瓊，姚望舒，等.一種連續(xù)值屬性約簡(jiǎn)方法ReCA[J].計(jì)算機(jī)研究與發(fā)展，2005,42(7)：1217-1224.

[17]崔玉泉,史開(kāi)泉.粗集的動(dòng)態(tài)特性分析及應(yīng)用[J].中國(guó)管理科學(xué),2003,11(6):66-70.

[18]劉清.信息變換函數(shù)及動(dòng)態(tài)信息系統(tǒng)[J].計(jì)算機(jī)科學(xué)，2004,31(10A):15-17.