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

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

0 引 言

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

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

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

1 預備知識

2 基于外因驅動的單步動態(tài)信息系統模型

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

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

為了討論方便，嘗試在最簡單的情況下對動態(tài)的信息系統建立模型，假設滿足以下條件：1)W是非空有限的條件屬性集；2)信息系統變化過程中論域U和屬性集合A都不發(fā)生變化，即U=U′，A=A′；3)根據哲學中外因對事物發(fā)展變化是通過內因起作用的原理，假設信息系統的變化是通過A中各個屬性值的變化來體現，即ρa;Va→V′a.

一個外因屬性能觸發(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)

以下幾種表示方法是等價的

3 近似算子對外因與內因的分析

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

定義3設T=(Ω,W,R)為外因驅動的近似空間，Ω是S到S′的屬性值變遷集，G?W，定義一對近似算子▽,△：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)

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

定義4設T=(Ω,W,R)為外因驅動的近似空間，Ω是S到S′的屬性值變遷集，X?Ω，定義一對近似算子▽,△: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)

根據定義4的算子定義，X▽中每一個外因屬性能觸發(fā)的屬性值變遷全都在X中，X△中每一個外因屬性能觸發(fā)的屬性值變遷至少有1個在X中.

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

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

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△.假設 (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.假設(a,x,x′)?GC▽C，則(a,x,x′)∈GC▽,即R(a,x,x′)?GC.又由假設條件(a,x,x′)∈G△得,R(a,x,x′)∩G≠φ.矛盾.故(a,x,x′)∈GC▽C.

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

2)X▽△▽=X▽.

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

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

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

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

(9)

(10)

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

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

(11)

(12)

根據定義6的算子定義，X★中每一個外因屬性能觸發(fā)值變遷的屬性全都在X中，X☆中每一個外因屬性能觸發(fā)值變遷的屬性至少有1個包含在X中.

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

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假設G?W,X?A,則算子▽,△,★和☆具有以下性質：

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 結 語

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

[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].西安交通大學學報,2000,34(12):75-79.

[14]張文修,吳偉志.基于隨機集的粗糙集模型(Ⅱ)[J].西安交通大學學報,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]商琳，萬瓊，姚望舒，等.一種連續(xù)值屬性約簡方法ReCA[J].計算機研究與發(fā)展，2005,42(7)：1217-1224.

[17]崔玉泉,史開泉.粗集的動態(tài)特性分析及應用[J].中國管理科學,2003,11(6):66-70.

[18]劉清.信息變換函數及動態(tài)信息系統[J].計算機科學，2004,31(10A):15-17.