史　嬋

(西安郵電大學(xué) 通信與信息工程學(xué)院， 陜西 西安 710121)

用于不精確和不確定數(shù)據(jù)信息分析的粗糙集理論[1],作為一種有效的知識發(fā)現(xiàn)與獲取工具，倍受關(guān)注[2-8]。粗糙集理論以數(shù)據(jù)庫為基礎(chǔ)，兩者發(fā)展關(guān)系密切。早期信息系統(tǒng)的屬性取值域有限，只探討等價關(guān)系。隨著數(shù)據(jù)庫的深入分析，信息系統(tǒng)的取值域及其論域上的二元關(guān)系也不斷擴展。結(jié)合其他理論，涌現(xiàn)出許多新的信息系統(tǒng)。例如取值為區(qū)間的區(qū)間值信息系統(tǒng)[9-10]，取值為集合的集值信息系統(tǒng)[11-12]，取值在特定區(qū)間內(nèi)的連續(xù)值信息系統(tǒng)[13]等?；趯嶋H生活中的優(yōu)勢關(guān)系，信息系統(tǒng)被擴展為序信息系統(tǒng)[14-15]。基于模糊集理論，信息系統(tǒng)又被擴展為模糊信息系統(tǒng)[16-18]。不過，這些信息系統(tǒng)都無法直接處理信息表中的多維數(shù)據(jù)。

其實，對于信息系統(tǒng)，除了討論其取值域以及二元關(guān)系之外，還可以考慮從取值域的代數(shù)結(jié)構(gòu)和幾何結(jié)構(gòu)進行分析。如將所有屬性值限定在同一個度量空間，那么，在引入度量之后，所得度量信息系統(tǒng)則可解決信息表中多維數(shù)據(jù)的處理問題。此外，度量信息系統(tǒng)更是部分信息系統(tǒng)的推廣，這些信息系統(tǒng)不過是度量信息系統(tǒng)在合適度量下的特例；在相同的信息表中，引入不同度量，還可從不同角度獲取不同知識。

屬性約簡是信息系統(tǒng)理論研究的核心問題之一[8]，即在保持知識庫分類能力不變的條件下，刪除其中不相關(guān)或不重要的屬性，從而簡化知識的表示。本文將基于度量空間研究信息系統(tǒng)的屬性約簡與特征描述。

1　度量信息系統(tǒng)

將度量引入信息系統(tǒng)，考慮度量信息系統(tǒng)上論域子集在相似關(guān)系下的上、下近似。

定義1[19]稱(T,d)為度量空間，其中

d:T×T→

是一個非負函數(shù)，且對任意x,y,z∈T,滿足

(1)d(x,x)=0,

(2)d(x,y)=d(y,x),

(3)d(x,z)≤d(x,y)+d(y,z)。

定義2稱信息系統(tǒng)(U,A,F,T)是一個度量信息系統(tǒng)，若(U,A,F)是信息系統(tǒng)，其中

U={x1,x2,…,xn},A={a1,a2,…,am},F={fl:U→T,al∈A},

且(T,d)為度量空間。

定義3設(shè)(U,A,F,T)是一個度量信息系統(tǒng)。對于任意的ε>0,B?A，定義二元關(guān)系

并記

其中,ε稱為系統(tǒng)誤差。

例1某市內(nèi)行政區(qū)規(guī)劃的部分數(shù)據(jù)如表1所示。對象集U={x1,x2,x3,x4,x5}是5個住宅區(qū)。屬性集A={a1,a2,a3,a4}是規(guī)劃擬建的4個公園。屬性值表示各住宅區(qū)相對于特定公園的距離(單位：km)。例如，第1列表示以公園a1為笛卡爾坐標(biāo)系的坐標(biāo)原點，住宅區(qū)xi(i=1，2，3，4，5)所在的位置。那么，(U,A,F,T)即是度量信息系統(tǒng)。其中:fl∈F，如f1(x1)表示對象x1在屬性a1下的屬性值，即f1(x1)=(-1，0);T=2為二維平面，d代表歐氏距離，即對任意(x1,y1),(x2,y2)∈2，有

表1　度量信息系統(tǒng)實例

當(dāng)ε=2，B=A時，按照定義3，可以求得

即若以與住宅區(qū)相對距離在2 km之內(nèi)為準則，建設(shè)4個公園，則住宅區(qū)x1和x2將被劃歸同一個居住帶,亦即小區(qū)x1和x2的居民距公園遠近或游玩的便利程度相當(dāng)。

定義4設(shè)(U,A,F,T)是一個度量信息系統(tǒng)，X?U,ε>0,稱

為X關(guān)于B的ε-下近似，稱

為X關(guān)于B的ε-上近似。

例2設(shè)(U,A,F,T)是例1提到的度量信息系統(tǒng)。取X={x1,x5}，由定義4可知

定理1設(shè)(U,A,F,T)是一個度量信息系統(tǒng)，任給ε>0，X,Y?U,則X和Y關(guān)于B的ε-下近似與X和Y關(guān)于B的ε-上近似具有性質(zhì)

(1)

(2)

(3)

(4)

其中,┐X=U-X。

證明僅證明式(3)中的

其余類似可證。

故有等價式

故待證等式成立。

2　度量信息系統(tǒng)的屬性約簡

針對度量信息系統(tǒng)的屬性約簡問題給出約簡準則，并利用辨識矩陣進行屬性約簡。

定義6設(shè)(U,A,F,T)是一個度量信息系統(tǒng)，記

Dε(xi,xj)={al∈A:d(fl(xi),fl(xj))>ε},D=[Dε(xi,xj)](xi,xj∈U),

稱Dε(xi,xj)為xi與xj間的辨識集，D為度量信息系統(tǒng)的辨識矩陣。

定理2設(shè)(U,A,F,T)是一個度量信息系統(tǒng)，則B是ε-協(xié)調(diào)集,當(dāng)且僅當(dāng)Dε(xi,xj)非空時，B∩Dε(xi,xj)也非空。

例3表1所對應(yīng)的辨識矩陣D可表示為

其中

D1={a1,a2,a3,a4},D2={a1,a2,a4},D3={a2,a3}。

取B1={a1,a3}，由定理2可知，B1為2-協(xié)調(diào)集。因B2={a1}?B1和B3={a3}?B1不滿足定理2的條件， 故其不是2-協(xié)調(diào)集。除B2和B3外，B1再無其他非空真子集，故由定義5知，B5={a3,a4}和B1={a1,a3}為2-約簡。另外，在上述矩陣中亦可以觀察到B4={a2}，也是2-約簡。

3　度量信息系統(tǒng)的屬性特征

設(shè)(U,A,F,T)是度量信息系統(tǒng)，給定ε>0,B={Bk:k≤l}是所有ε-約簡構(gòu)成的集合。記

則稱C為(U,A,F,T)的核心屬性集，K為(U,A,F,T)的相對必要屬性集，I是(U,A,F,T)的絕對不必要屬性集。

定理3設(shè)(U,A,F,T)是一個度量信息系統(tǒng)，則有等價命題

(1)a∈C；

(2) 存在xi,xj∈U，使得Dε(xi,xj)={a}；

定理4設(shè)(U,A,F,T)是一個度量信息系統(tǒng)，則成立命題

故a不在任何ε-約簡中，所以a∈I。

(2) 結(jié)合命題(1)，由定理3及C，I和K的定義,即可知命題(2)顯然成立。

例4分析例1給出的度量信息系統(tǒng)。由例3知，{a1,a3}，{a3,a4}，{a2}為該度量信息系統(tǒng)的全部ε-約簡，故由C,I和K的定義知

C=?，K={a1,a2,a3,a4}，I=?。

結(jié)合實際得到的屬性約簡結(jié)果表明,為了節(jié)約地皮同時保證居住帶不變，可以不用建設(shè)4個公園，只需建設(shè)公園a1,a3或者只需建設(shè)公園a3,a4或者只需建設(shè)公園a2。同樣可以保證同一居住帶居民的休息娛樂場所。

4　結(jié)語

通過結(jié)合度量空間，改變信息系統(tǒng)的取值域，提出度量信息系統(tǒng)。針對度量信息系統(tǒng)，給出了屬性約簡的判定定理、利用辨識矩陣求解約簡的方法以及3種屬性特征的等價刻畫。

度量信息系統(tǒng)在一定程度上是經(jīng)典信息系統(tǒng)及連續(xù)值信息系統(tǒng)的推廣，本文考慮的是沒有決策的信息系統(tǒng)，關(guān)于度量信息系統(tǒng)上的決策問題還可另行討論。在信息系統(tǒng)上引入度量，不僅為以后利用鄰域概念等討論屬性間的依賴關(guān)系創(chuàng)造了條件，還可以研究信息系統(tǒng)之間的同構(gòu)關(guān)系，由此對信息系統(tǒng)作分類，便于信息系統(tǒng)的統(tǒng)一。