一種基于相對信息粒度的屬性約簡算法?

孫 敬

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

1 引言

屬性約簡是粗糙集理論的主要研究內(nèi)容之一，尋找高效屬性約簡算法一直是學(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ì)算理論，從信息粒庫出發(fā)，運(yùn)用粒之間的運(yùn)算計(jì)算對應(yīng)的相對信息粒度，據(jù)此提出一種基于相對信息粒度的屬性約簡改進(jìn)算法。

2 相對信息粒度與屬性約簡

2.1 信息粒庫

定義 1［1］設(shè)四元組 S=（U，C∪D，V，f）為決策信息系統(tǒng)，其中U 為非空有限的對象集合；C 為條件屬性集，D 為決策屬性集，且C∩D=?，D≠?；V=∪a∈AVa，其中 Va為某屬性 a 的值域；f 為 U×C∪D→V 的信息函數(shù)，即對任意的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（ψ）為滿足公式φ、ψ的對象集合，則稱 Gr（φ）=（φ，m（φ））、Gr（ψ）=（ψ，m（ψ））分別為S 上關(guān)于φ、ψ的復(fù)合粒，且Gr（φ）∧Gr（ψ）=（φ，m（φ））∧（ψ，m（ψ））=（φ∧ψ，m（φ）∩m（ψ））。

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

定義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 對應(yīng)的 n 階信息粒庫，（Pvi，m（Pvi））為Gr（P）一個(gè)n階信息粒。

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

定義5 設(shè)S=（U，C∪D，V，f）為一個(gè)決策信息系統(tǒng)，P、Q?C，Gr（P）、Gr（Q）為P、Q的信息粒庫，若對 ?（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)的信息粒庫為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è)屬性），對于任意的 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 相對信息粒度

定義6 設(shè)S=（U，C∪D，V，f）為一個(gè)決策信息系統(tǒng)，P?C，對任意的（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 的相對信息粒度，|·|是某個(gè)集合的元素個(gè)數(shù)。

由相對信息粒度定義可知，λ（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ù)越多，其對應(yīng)的信息粒庫?；芰υ綇?qiáng)，屬性集關(guān)于D的相對信息粒度值就越大，特別地，若P=Q，由定理2 可知，λ（P，D）= λ（Q，D），顯然，這兩個(gè)屬性集的?；芰ο嗤?/p>

2.3 屬性重要度與屬性約簡

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

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

由定義7可知，SIG（｛a｝，C，D）衡量的是刪除屬性a 后引起的C 關(guān)于D 的相對信息粒度變化情況，顯然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 的相對信息粒度并未發(fā)生變化，屬性a 在C 中是不重要的，或稱冗余的。

性質(zhì)1 對任意屬性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，對任意屬性a∈P，若SIG（｛a｝，C，D）＞0，則稱P是獨(dú)立的。

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

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

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

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

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

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

2.4 基于相對信息粒度的屬性約簡算法

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

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

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

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

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

步驟3:對于任意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é)束，輸出約簡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］得到的約簡為｛ab｝或｛ac｝。

結(jié)合上述決策信息系統(tǒng)，下面給出本文屬性約簡算法的具體執(zhí)行過程，以此來驗(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。對任意的 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)前約簡集是否滿足條件λ（Red（S），D）=λ（C，D）。由于λ（Red（S），D）= λ（｛a｝，D）=13/18≠5/6=λ（C，D），所以對任意的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加入約簡集中，即Red（S）=｛ac｝。

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

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

4 結(jié)語

本文依托粒計(jì)算理論，從原子粒和復(fù)合粒出發(fā)，介紹了信息粒庫的概念，據(jù)此給出了相對信息粒度來度量某屬性集關(guān)于決策屬性集的相對粒化能力，并提出了一種基于相對信息粒度的屬性約簡算法，結(jié)合實(shí)例分析為決策信息系統(tǒng)屬性約簡提供了一種新的研究方法。