孫 敬

（1.湖北工業(yè)大學(xué)理學(xué)院 武漢 430068）（2.鄭州工業(yè)應(yīng)用技術(shù)學(xué)院信息工程學(xué)院 鄭州 451100）

1 引言

屬性約簡(jiǎn)是粗糙集理論的主要研究?jī)?nèi)容之一，尋找高效屬性約簡(jiǎn)算法一直是學(xué)者關(guān)注的焦點(diǎn)［1～2］。目前，許多學(xué)者先后從強(qiáng)化正域［3］、條件熵［4～5］、互信息［6］、區(qū)分矩陣［7～8］、粒計(jì)算［9～12］、知識(shí)粒度［13］、決策重要度［14］、遺傳粒子群［15］、加權(quán)濃縮樹［16］等方面提出了自己的方法。但是，這些算法雖然比較了不同屬性集的各方面能力，卻容易忽略知識(shí)本身之間的關(guān)系。本文將利用粒計(jì)算理論，從信息粒庫(kù)出發(fā)，運(yùn)用粒之間的運(yùn)算計(jì)算對(duì)應(yīng)的相對(duì)信息粒度，據(jù)此提出一種基于相對(duì)信息粒度的屬性約簡(jiǎn)改進(jìn)算法。

2 相對(duì)信息粒度與屬性約簡(jiǎn)

2.1 信息粒庫(kù)

定義 1［1］設(shè)四元組 S=（U，C∪D，V，f）為決策信息系統(tǒng)，其中U 為非空有限的對(duì)象集合；C 為條件屬性集，D 為決策屬性集，且C∩D=?，D≠?；V=∪a∈AVa，其中 Va為某屬性 a 的值域；f 為 U×C∪D→V 的信息函數(shù)，即對(duì)任意的a∈C∪D，x∈U，均有 f（x，a）∈Va。

定義2 設(shè)S=（U，C∪D，V，f）為一個(gè)決策信息系統(tǒng)，令 a∈C∪D，v∈Va，則稱（a，v）或av為 S 上原子公式。令 m 為 S 上的粒函數(shù)，其中 m（av）=｛x | f（x，a）=v，a∈C∪D，x∈U｝，則稱 Gr（a）=（av，m（av））為S上關(guān)于屬性a的一個(gè)原子粒。

定義3 設(shè)S=（U，C∪D，V，f）為一個(gè)決策信息系統(tǒng)，設(shè)φ、ψ為S 上有限個(gè)原子公式利用聯(lián)結(jié)詞（∧）構(gòu)成的兩個(gè)復(fù)合公式，令m（φ）、m（ψ）為滿足公式φ、ψ的對(duì)象集合，則稱 Gr（φ）=（φ，m（φ））、Gr（ψ）=（ψ，m（ψ））分別為S 上關(guān)于φ、ψ的復(fù)合粒，且Gr（φ）∧Gr（ψ）=（φ，m（φ））∧（ψ，m（ψ））=（φ∧ψ，m（φ）∩m（ψ））。

為了更好地從語(yǔ)法和語(yǔ)義方面刻畫屬性與對(duì)象之間的關(guān)系，借助粒計(jì)算理論，下面給出由復(fù)合公式和粒函數(shù)所確定的信息粒庫(kù)的定義。

定義4 設(shè)S=（U，C∪D，V，f）為一個(gè)決策信息系統(tǒng)，P?C 且 P=｛p1，p2，…，pn｝（n 為 P 的屬性個(gè)數(shù)），vi∈Vp1×Vp2×…×Vpn，令公式集φp=｛Pvi|Pvi=（p1，v1i）∧（p2，v2i）∧…∧（pn，vni），vi1∈Vp1，vi2∈Vp2，…，vin∈Vpn，i=1，2，3，…｝，令

則稱 Gr（P）為 P 對(duì)應(yīng)的 n 階信息粒庫(kù)，（Pvi，m（Pvi））為Gr（P）一個(gè)n階信息粒。

由定義 4 可知，Gr（P）用公式 Pvi從語(yǔ)法角度闡述了粒的產(chǎn)生規(guī)則，m（Pvi）從語(yǔ)義角度闡述了粒的構(gòu)成對(duì)象。

定義5 設(shè)S=（U，C∪D，V，f）為一個(gè)決策信息系統(tǒng)，P、Q?C，Gr（P）、Gr（Q）為P、Q的信息粒庫(kù)，若對(duì) ?（Pvi，m（Pvi））∈Gr（P），均存在一個(gè)（Qvi，m（Qvi））∈Gr（Q），使得m（Qvi）?m（Pvi），則稱Gr（Q）比Gr（P）粒化更細(xì)，記為Gr（Q）?Gr（P）。

定理1 設(shè)S=（U，C∪D，V，f）為一個(gè)決策信息系統(tǒng)，若P?Q?C，相應(yīng)的信息粒庫(kù)為Gr（P）、Gr（Q），則有Gr（Q）?Gr（P）。

證明:令 P=｛p1，p2，…，pn｝（n 為 P 的屬性個(gè)數(shù)），由于 P?Q，則知 Q 比 P 的屬性個(gè)數(shù)多，令 Q=｛p1，p2，…，pn，pn+1，pn+2，…，pn+m｝（假設(shè)pn+1，pn+2，…，pn+m為Q比 P 多的 m 個(gè)屬性），對(duì)于任意的 m（Qvi）=m（（p1，v1i）∧（p2，v2i）∧…∧（pn，vni）∧（pn+1，vn+1i）∧（pn+1，vn+1i）∧…∧（pn+m，vn+mi））=m（p1，v1i）∩m（p2，v2i）∩…∩m（pn，vni）∩m（pn+1，vn+1i）∩m（pn+1，vn+1i）∩…∩m（pn+m，vn+mi）?m（p1，v1i）∩m（p2，v2i）∩…∩m（pn，vni）=m（（p1，v1i）∧（p2，v2i）∧…∧（pn，vni））=m（Pvi），又知m（Qvi）是任選的，由定義5知Gr（Q）?Gr（P）。

特別地，若 P=Q，則由定理 1 可知 Gr（Q）=Gr（P），此時(shí)稱Gr（P）、Gr（Q）?；嗤?/p>

2.2 相對(duì)信息粒度

定義6 設(shè)S=（U，C∪D，V，f）為一個(gè)決策信息系統(tǒng)，P?C，對(duì)任意的（Pvi，m（Pvi））∈Gr（P）、（Dvj，m（Dvj））∈Gr（D）（i=1，2，3，…，m，j=1，2，3，…，n，m、n分別為Gr（P）、Gr（D）的公式個(gè)數(shù)），令

則稱λ（P，D）為 P 關(guān)于D 的相對(duì)信息粒度，|·|是某個(gè)集合的元素個(gè)數(shù)。

由相對(duì)信息粒度定義可知，λ（P，D）反映的是屬性集P 關(guān)于D 的?；撚蚰芰?，顯然0 ≤λ（P，D）≤1。λ（P）值越大，說明該屬性集的?；芰υ綇?qiáng)，否則，?；芰驮饺酢?/p>

定理2 設(shè)S=（U，C∪D，V，f）為一個(gè)決策信息系統(tǒng)，P?Q?C，則有λ（P，D）≤ λ（Q，D）。

證明:由于P?Q，由定理1 知Gr（Q）?Gr（P），則存在一個(gè)（Qvi，m（Qvi））∈Gr（Q），使得m（Qvi）?m（Pvi）（i=1，2，3，…），可知m（Qvi）∩m（Dvj））?m（Pvi）∩m（Dvj））（j=1，2，3，…，n，n為Gr（D）的公式個(gè)數(shù)），由定義6可知，λ（P，D）≤ λ（Q，D）。

由定理2 可知，屬性集屬性個(gè)數(shù)越多，其對(duì)應(yīng)的信息粒庫(kù)?；芰υ綇?qiáng)，屬性集關(guān)于D的相對(duì)信息粒度值就越大，特別地，若P=Q，由定理2 可知，λ（P，D）= λ（Q，D），顯然，這兩個(gè)屬性集的?；芰ο嗤?。

2.3 屬性重要度與屬性約簡(jiǎn)

定義7 設(shè)S=（U，C∪D，V，f）為一個(gè)決策信息系統(tǒng)，對(duì)任意屬性a∈C，令

則稱 SIG（｛a｝，C，D）為屬性a 關(guān)于D 相對(duì)于C的屬性重要度。其中，λ（C，D）、λ（C-｛a｝，D）分別代表C、C-｛a｝關(guān)于D的相對(duì)信息粒度。

由定義7可知，SIG（｛a｝，C，D）衡量的是刪除屬性a 后引起的C 關(guān)于D 的相對(duì)信息粒度變化情況，顯然0 ≤ SIG（｛a｝，C，D）≤ 1。當(dāng)SIG（｛a｝，C，D）=0時(shí)，則知λ（C，D）-λ（C-｛a｝，D）=0，即λ（C，D）=λ（C-｛a｝，D），說明刪除屬性a 后C 關(guān)于D 的相對(duì)信息粒度并未發(fā)生變化，屬性a 在C 中是不重要的，或稱冗余的。

性質(zhì)1 對(duì)任意屬性a∈C，它是C 中必要屬性當(dāng)且僅當(dāng)SIG（｛a｝，C，D）＞0。

性質(zhì) 2 核集 COREC（D）=｛a∈C| SIG（｛a｝，C，D）＞0｝。

定義8 設(shè)S=（U，C∪D，V，f）為一個(gè)決策信息系統(tǒng)，P?C，對(duì)任意屬性a∈P，若SIG（｛a｝，C，D）＞0，則稱P是獨(dú)立的。

由于以核為起點(diǎn)的啟發(fā)式屬性約簡(jiǎn)中，需要不斷地往核集中添加屬性，所以下面給出另外一種屬性重要度的定義。

定義9 設(shè)S=（U，C∪D，V，f）為一個(gè)決策信息系統(tǒng)，P?C，對(duì)任意屬性a∈C-P，令

SIG（｛a｝，P∪｛a｝，D）=λ（P∪｛a｝，D）-λ（P，D）

則稱SIG（｛a｝，P∪｛a｝，D）為非P 屬性a 關(guān)于D相對(duì)于P的屬性重要度。其中，λ（P∪｛a｝，D）、λ（P，D）分別代表P∪｛a｝、P關(guān)于D的相對(duì)信息粒度。

由定義9可知，SIG（｛a｝，P∪｛a｝，D）衡量的是添加非P屬性a后引起的P關(guān)于D的相對(duì)信息粒度變化情況，顯然0 ≤ SIG（｛a｝，P∪｛a｝，D）≤ 1，SIG（｛a｝，P∪｛a｝，D）值越大，說明非P屬性a對(duì)P越重要。

定理3 設(shè)S=（U，C∪D，V，f）為一個(gè)決策信息系統(tǒng)，P?C。若P 是獨(dú)立的且λ（P，D）=λ（C，D），則稱P為C相對(duì)于D的一個(gè)約簡(jiǎn)。

2.4 基于相對(duì)信息粒度的屬性約簡(jiǎn)算法

該算法需要先從條件屬性集中選出必要屬性組成核集作為初始約簡(jiǎn)集，然后在該集合中不斷添加屬性重要度最大的屬性，循環(huán)判斷當(dāng)前約簡(jiǎn)集是否滿足定理3 中約簡(jiǎn)的要求，直至算法結(jié)束。下面給出本文基于相對(duì)信息粒度的屬性約簡(jiǎn)算法。

輸入:一個(gè)決策信息系統(tǒng)S=（U，C∪D，V，f）。

輸出:決策信息系統(tǒng)的約簡(jiǎn)Red（S）。

步驟1:計(jì)算λ（C，D），令Red（S）=COREC（D）；

步驟2:判斷λ（Red（S），D）=λ（C，D）是否成立，若成立，則跳轉(zhuǎn)到步驟4，否則跳轉(zhuǎn)到步驟3；

步驟3:對(duì)于任意a∈C-Red（S），計(jì)算其屬性重要度 SIG（｛a｝，Red（S）∪｛a｝，D），令 Red（S）=Red（S）∪｛a｝，其中屬性a為所有C-Red（S）中屬性重要度最大的屬性（若多個(gè)屬性值最大，任選一個(gè)加入Red（S）），執(zhí)行步驟2；

步驟4:算法結(jié)束，輸出約簡(jiǎn)Red（S）。

3 實(shí)例分析

利用文獻(xiàn)［1］中的一個(gè)決策信息系統(tǒng)（表1），下面將驗(yàn)證本文算法的有效性。其中，U=｛x1，x2，x3，x4，x5，x6｝，C=｛a，b，c｝，D=｛d｝，利用文獻(xiàn)［1］得到的約簡(jiǎn)為｛ab｝或｛ac｝。

結(jié)合上述決策信息系統(tǒng)，下面給出本文屬性約簡(jiǎn)算法的具體執(zhí)行過程，以此來(lái)驗(yàn)證本算法的有效性。

首 先 ，計(jì) 算 λ（C，D）。 Gr（C）∩Gr（D）=｛（（a2b2c0d1），｛x1｝），（a1b2c0d0），｛x2｝），（a1b2c0d1），｛x3｝），（（a0b0c0d0），｛x4｝），（（a1b0c1d0），｛x5｝），（a2b0c1d1），｛x6｝）｝，所以 m（C）∩m（D））=｛｛x1｝，｛x2｝，｛x3｝，｛x4｝，｛x5｝，｛x6｝｝，λ（C，D）=1-1/6=5/6。對(duì)任意的 a∈C，逐一計(jì)算 SIG（｛a｝，C，D），可得 SIG（｛a｝，C，D）=5/6-7/9=1/15，SIG（｛b｝，C，D）=SIG（｛c｝，C，D）=5/6-5/6=0，COREC（D）=｛a｝，令Red（S）=COREC（D）=｛a｝。

表1 決策信息系統(tǒng)S

判斷當(dāng)前約簡(jiǎn)集是否滿足條件λ（Red（S），D）=λ（C，D）。由于λ（Red（S），D）= λ（｛a｝，D）=13/18≠5/6=λ（C，D），所以對(duì)任意的b∈C-Red（S），計(jì)算SIG（｛a｝，Red（S）∪｛a｝，D），可得 SIG（｛b｝，｛a｝∪｛b｝，D）=SIG（｛c｝，｛a｝∪｛c｝，D）=5/6-13/18=1/9＞0，按步驟3任選屬性b加入約簡(jiǎn)集中，即Red（S）=｛ac｝。

對(duì)于Red（S）=｛ac｝，判斷λ（Red（S），D）=λ（C，D）是否成立。由于λ（｛ac｝，D）=λ（C，D）=5/6，條件成立，轉(zhuǎn)向步驟4，算法結(jié)束，輸出約簡(jiǎn)集Red（S）=｛ac｝。

同樣，可驗(yàn)證｛ab｝也是該決策信息系統(tǒng)的約簡(jiǎn)，這與文獻(xiàn)得到的約簡(jiǎn)集是一致的，說明該算法是有效的。

4 結(jié)語(yǔ)

本文依托粒計(jì)算理論，從原子粒和復(fù)合粒出發(fā)，介紹了信息粒庫(kù)的概念，據(jù)此給出了相對(duì)信息粒度來(lái)度量某屬性集關(guān)于決策屬性集的相對(duì)?；芰Γ⑻岢隽艘环N基于相對(duì)信息粒度的屬性約簡(jiǎn)算法，結(jié)合實(shí)例分析為決策信息系統(tǒng)屬性約簡(jiǎn)提供了一種新的研究方法。