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

史　嬋

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

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

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

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

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

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

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

d:T×T→

是一個(gè)非負(fù)函數(shù)，且對(duì)任意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稱(chēng)信息系統(tǒng)(U,A,F,T)是一個(gè)度量信息系統(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)是一個(gè)度量信息系統(tǒng)。對(duì)于任意的ε>0,B?A，定義二元關(guān)系

并記

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

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

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

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

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

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

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

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

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

定理1設(shè)(U,A,F,T)是一個(gè)度量信息系統(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)中的

其余類(lèi)似可證。

故有等價(jià)式

故待證等式成立。

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

針對(duì)度量信息系統(tǒng)的屬性約簡(jiǎn)問(wèn)題給出約簡(jiǎn)準(zhǔn)則，并利用辨識(shí)矩陣進(jìn)行屬性約簡(jiǎn)。

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

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

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

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

例3表1所對(duì)應(yīng)的辨識(shí)矩陣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再無(wú)其他非空真子集，故由定義5知，B5={a3,a4}和B1={a1,a3}為2-約簡(jiǎn)。另外，在上述矩陣中亦可以觀察到B4={a2}，也是2-約簡(jiǎn)。

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

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

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

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

(1)a∈C；

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

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

故a不在任何ε-約簡(jiǎn)中，所以a∈I。

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

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

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

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

4　結(jié)語(yǔ)

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

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