基于相對辨識關(guān)系的屬性約簡算法

孫 濱，毛建景

(鄭州工業(yè)應(yīng)用技術(shù)學院 信息工程學院，河南 鄭州 451100)

0 引 言

粗糙集理論可以有效地進行不精確、不完備數(shù)據(jù)分析與處理，國外在這方面的研究已經(jīng)取得了不錯的成績[1-4]，其中決策信息系統(tǒng)中的屬性約簡是其核心研究內(nèi)容。許多學者利用多種方法來度量決策信息系統(tǒng)中屬性的重要度。文獻[5]在分析信息熵度量不確定性數(shù)據(jù)的基礎(chǔ)上，定義信息熵屬性重要度概念，引入蟻群優(yōu)化算法，提出基于信息熵與蟻群優(yōu)化的最小屬性約簡算法。文獻[6]通過減少約簡過程中基數(shù)排序次數(shù)來提升效率，設(shè)計了相對分辨能力的約簡算法。文獻[7]設(shè)計了一種啟發(fā)式函數(shù)—決策重要度，這種啟發(fā)式函數(shù)根據(jù)每個屬性正決策對象集合的大小來定義其重要性，正決策對象集合越大表示重要性越高，由此構(gòu)造了基于決策重要度的啟發(fā)式屬性約簡算法。文獻[8]的約簡算法既考慮信息決策表的相對正域，也考慮以核屬性為啟發(fā)信息逐個增加條件屬性時對邊界域樣本的影響。文獻[9]定義了一種粒度差別矩陣和基于該差別矩陣的屬性約簡，并證明了該差別矩陣的屬性約簡定義與基于知識粒度的屬性約簡定義等價。文獻[10]給出了對象矩陣的屬性約簡定義，證明了屬性約簡與基于正區(qū)域的屬性約簡的等價性。

因此，對于如何從海量數(shù)據(jù)集中尋找一種高效的屬性約簡算法，不僅能保持分類能力不變，還能簡化決策規(guī)則生成過程，便具有重要的研究意義。文中依據(jù)相對辨識關(guān)系給出了基于相對辨識關(guān)系的屬性約簡算法，從而為屬性約簡提供了新的研究思路。

1 可辨識關(guān)系與屬性重要度

在決策信息系統(tǒng)中，對于論域U，若存在屬性集P、Q?C∪D且P、Q≠?，使得U關(guān)于P、Q的劃分相等，即U/P=U/Q，則稱P、Q具有相同的可辨識能力，否則若屬性集P辨識論域U中的對象對越多，則稱P的可辨識能力越強，反之則辨識能力越弱。下面給出屬性集的可辨識關(guān)系。

1.1 可辨識關(guān)系

為了更好地引入可辨識關(guān)系，先給出一個屬性集所對應(yīng)的劃分的性質(zhì)，方便對可辨識關(guān)系的理解。

性質(zhì)1[11]：設(shè)S=(U,C∪D,V,f)為一個決策信息系統(tǒng)，若P?Q?C，則有U/Q?U/P，此時稱U關(guān)于Q的劃分比P更精細，U關(guān)于P的劃分比Q更粗糙。

性質(zhì)1僅描述了屬性集對應(yīng)的劃分之間辨識能力的高低，并未對屬性集的可辨識能力進行精確描述，因此下面給出可辨識關(guān)系的形式化定義來加以闡述。

定義1：設(shè)S=(U,C∪D,V,f)為一個決策信息系統(tǒng)，n為所有對象個數(shù)，對P?C∪D，若令

DIS(P)={|存在屬性a∈P，f(xi,a)≠f(xj,a)，1≤i≤j≤n,xi,xj∈U}

則稱DIS(P)為屬性集P在U上的可辨識關(guān)系。

由定義1可知，DIS(P)是屬性集P能辨識的所有對象對，考察的是P的辨識能力，并且可知0≤|DIS(P)|≤[|U|·(|U|-1)]/2。當U/P={{x1,x2,…,xn}}時，DIS(P)取得最小值0；當U/P={{x1},{x2},…,{xn}}時，DIS(P)取得最大值[|U|·(|U|-1)]/2。

顯然U/P越精細，DIS(P)包含的對象對越多，說明利用P能辨識的對象對個數(shù)越多，越容易將論域中對象兩兩辨識，說明P的辨識能力越強，否則反之。

由定義1可得性質(zhì)2。

性質(zhì)2：設(shè)S=(U,C∪D,V,f)為一個決策信息系統(tǒng)，P?C∪D，對任意的xi、xj∈U(1≤i≤j≤n，n為論域U中對象個數(shù))，令[xi]P、[xj]P為xi、xj所對應(yīng)的P等價類，則

(1)若[xi]P∩[xj]P≠?，則有∈DIS(P)；

(2)若[xi]P∩[xj]P=?，則有?DIS(P)。

由性質(zhì)2可知，DIS(U,P)能辨識不同P等價類中的對象，而無法辨識同一P等價類中的對象。

由定義1可得定理1。

定理1：設(shè)S=(U,C∪D,V,f)為一個決策信息系統(tǒng)，P?Q?C，DIS(P)、DIS(Q)分別為P、Q的可辨識關(guān)系，則有DIS(P)?DIS(Q)。

證明：令任意的xi、xj∈U，其中1≤i≤j≤n。由定義1可知，若∈DIS(P)，則存在屬性a∈P，f(xi,a)≠f(xj,a)，由于P?Q，則有a∈P?Q，按照定義1可知，存在屬性a∈Q，f(xi,a)≠f(xj,a)，即得∈DIS(Q)。由于具有任意性，所以可得DIS(P)?DIS(Q)。證畢。

由定理1知，對任意集P?Q?C，則有DIS(P)?DIS(Q)，說明Q比P所辨識的對象對相等或更多，可辨識能力更強。特別地，當P=Q時，則有DIS(P)=DIS(Q)，此時稱P、Q可辨識能力相同。

1.2 相對可辨識關(guān)系

定義2：設(shè)S=(U,C∪D,V,f)為一個決策信息系統(tǒng)，n為所有對象個數(shù)，對P?C，若令

DIS(P,D)={|存在屬性a∈P，f(xi,a)≠f(xj,a)并且f(xi,D)≠f(xj,D)，1≤i≤j≤n,xi,xj∈U}

則稱DIS(P)為屬性集P在U上關(guān)于D的相對可辨識關(guān)系。

由定義2可知，DIS(P,D)是屬性集P相對于決策屬性集D能辨識的所有相對對象對，考察的是P關(guān)于D的相對辨識能力。按照定義2，可得性質(zhì)3。

性質(zhì)3:設(shè)S=(U,C∪D,V,f)為一個決策信息系統(tǒng)，DIS(P)、DIS(D)分別為P、D的可辨識關(guān)系，DIS(P,D)為P關(guān)于D的相對可辨識關(guān)系，則有DIS(P,D)=DIS(P)∩DIS(D)。

結(jié)合定義2和性質(zhì)3，可得定理2。

定理2:設(shè)S=(U,C∪D,V,f)為一個決策信息系統(tǒng)，P?Q?C，DIS(P)、DIS(Q)、DIS(D)分別為P、Q、D的可辨識關(guān)系，DIS(P,D)、DIS(Q,D)分別為P、Q關(guān)于D的相對可辨識關(guān)系，則有DIS(P,D)?DIS(Q,D)。

證明：由性質(zhì)3可知，DIS(P,D)=DIS(P)∩DIS(D)，又知P?Q，由定理1可知，DIS(P)?DIS(Q)。故DIS(P,D)=DIS(P)∩DIS(D)?DIS(Q)∩DIS(D)=DIS(Q,D)，即得DIS(P,D)?DIS(Q,D)。證畢。

由定理2可知，對任意集合P?Q?C，則有DIS(P,D)?DIS(Q,D)，說明Q比P關(guān)于D所辨識的對象對相等或更多，相對可辨識能力更強。特別地，當P=Q時，則有DIS(P,D)=DIS(Q,D)，此時稱P、Q相對可辨識能力相同。

1.3 屬性重要度

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

SigP(a)=(|DIS(P∪{a},D)|-

|DIS(P,D)|)/|U|2

則稱SigP(a)為屬性a相對于P的屬性重要度。其中，|DIS(P∪{a},D)|、|DIS(P,D)|分別表示相對可辨識關(guān)系DIS(P∪{a},D)、DIS(P,D)所辨識的對象對個數(shù)，|U|為論域U的對象個數(shù)。

由于P?P∪{a}，由定理2可知，DIS(P,D)?DIS(P∪{a},D)，則存在|DIS(P∪{a},D)|≥|DIS(P,D)|，即SigP(a)≥0。顯然，SigP(a)描述的是添加屬性a后引起P關(guān)于D所辨識對象對的變化，SigP(a)越大，P關(guān)于D所辨識對象對越多，說明添加屬性a后P的相對辨識能力提高，從而屬性a對P的重要性越大。

SigP(a)度量的是在原有屬性集P中添加不屬于P的屬性a的屬性重要度，下面給出一種度量原有屬性集P中每個屬性a(即a∈P)的屬性重要度。

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

SigP-{a}(a)=(|DIS(P,D)|-

|DIS(P-{a},D)|)/|U|2

稱SigP-{a}(a)為屬性a相對于P的重要度。其中，|DIS(P,D)|、|DIS(P-{a},D)|分別為相對可辨識關(guān)系DIS(P,D)、DIS(P-{a},D)所辨識的對象對個數(shù)，|U|為論域U的對象個數(shù)，顯然SigP-{a}(a)≥0。

SigP-{a}(a)描述的是在P中刪除屬性a后引起P關(guān)于D所辨識對象對的變化，SigP-{a}(a)越大，P關(guān)于D所辨識對象對越多，說明刪除屬性a后P的相對辨識能力下降，從而屬性a對P的重要性越大。特別地，當SigP-{a}(a)=0時，由定義4可知，DIS(P,D)=DIS(P-{a},D)，即P、P-{a}的相對辨識能力相同，說明刪除屬性a后，P的相對辨識能力并未發(fā)生變化，此時稱屬性a為P的不必要屬性或冗余屬性。

結(jié)合定義4，下面給出屬性a相對于P是必要屬性還是不必要屬性。

定義5:設(shè)S=(U,C∪D,V,f)為一個決策信息系統(tǒng)，P?C。若對任意的a∈P，都有SigP-{a}(a)>0，則每個a相對于P均是必要的，則稱P為獨立的，否則稱P為依賴的。

1.4 約 簡

定義4給出了屬性集P中任意屬性的屬性重要度SigP-{a}(a)，定義5用來判斷a在P中是不必要的還是必要的，結(jié)合定義4和定義5便可給出基于相對辨識關(guān)系的屬性約簡方法。為了證明基于相對辨識關(guān)系的約簡與文獻[5]中的約簡是等價的，下面先給出文獻[5]中約簡的定義。

定義6:設(shè)S=(U,C∪D,V,f)為一個決策信息系統(tǒng)，P?C。如果P滿足：U/C=U/P；則對任意a∈P，U/C≠U/(P-{a})，則稱P是C的一個約簡。

由定義4、5、6，給出基于相對辨識關(guān)系的約簡的判定方法，可得定理3。

定理3:設(shè)S=(U,C∪D,V,f)為一個決策信息系統(tǒng)，P?C。若P是獨立的且DIS(P,D)=DIS(C,D)，則稱P為C的一個約簡。

證明：若P是獨立的且DIS(P,D)=DIS(C,D)，因P?C，由定理1得DIS(P)?DIS(C)，若U/P≠U/C，則DIS(P)?DIS(C)，DIS(P)∩DIS(D)?DIS(C)∩DIS(D)，由定理2可知，DIS(P,D)?DIS(C,D)與條件DIS(P,D)=DIS(C,D)矛盾，所以U/P=U/C，P滿足定義6第一個條件。

又因為P是獨立的，則對任意的a∈P，都有SigP-{a}(a)=(|DIS(P,D)|-|DIS(P-{a},D)|) / |U|>0，則知|DIS(P,D)|>|DIS(P-{a},D)|，即DIS(P-{a},D)?DIS(P,D)，故U/P-{a}≠U/P，所以U/P-{a}≠U/C，P滿足定義6第二個條件，可知P是C的一個約簡。

由定理3可知，文中約簡與文獻[5]中約簡等價。

2 基于相對辨識關(guān)系的屬性約簡算法

2.1 算法思想

基于相對辨識關(guān)系的屬性約簡算法思想是首先令約簡集Red(S)=?，對任意屬性a∈C，按照定義3依次計算各條件屬性關(guān)于D的相對可辨識關(guān)系DIS({a},D)，選擇對象對個數(shù)最大的屬性加入約簡集Red(S)中。然后，判斷當前約簡集Red(S)關(guān)于D的可辨識關(guān)系是否等于DIS(C,D)，若是則輸出Red(S),即為該決策信息系統(tǒng)的約簡;否則，對任意屬性a∈C-Red(S)，按照定義3依次計算屬性重要度SigRed(S)(a)，選擇對象對個數(shù)最大的屬性加入約簡集Red(S)中，再次判斷是否滿足定理3關(guān)于約簡的要求，不斷重復這個過程，最終輸出滿足要求的Red(S)，即為該決策信息系統(tǒng)的約簡。

由此可知，該算法是從條件屬性集中先判斷各個屬性的相對可辨識關(guān)系，其對象對個數(shù)最大者組成約簡集，然后再在此約簡集中逐漸添加屬性，直至滿足約簡條件，是一種無核的屬性約簡算法，無論算法時間復雜度還是約簡工作量在一定程度上都有所降低。

2.2 算法實現(xiàn)

定理3利用相對辨識關(guān)系約定了約簡滿足的要求，下面給出一種基于相對辨識度的屬性約簡算法—RDR算法(an attribute reduction algorithm based on relative discernible relation)。

輸入：一個決策信息系統(tǒng)S=(U,C∪D,V,f)，其中U={x1,x2,…,xn}，C={a1,a2,…,am}；

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

步驟1：令Red(S)=?，按定義2計算相對可辨識關(guān)系DIS(C,D)；

步驟2：令Red(S)={a}，其中|DIS({a},D)|=max{|DIS({ai},D)|ai∈C,i=1,2,…,m}(如果多個屬性均滿足，則任選一個加入Red(S))且|DIS({ai},D)|≠0；

步驟3：若DIS(Red(S),D)=DIS(C,D)，則算法終止，輸出Red(S)(此時的Red(S)為S的一個約簡)，否則執(zhí)行步驟4；

步驟4：令Red(S)=Red(S)∪，并且SigRed(S)(b)=max{SigRed(S)(b')|bi∈C-Red(S),i=1,2,…,m}(如果多個屬性滿足，任選一個加入Red(S))，轉(zhuǎn)步驟3。

2.3 實例驗證

下面是采用文獻[12]中的決策信息系統(tǒng)(見表1)，其中文獻[12]得到的約簡是{a1,a3}。

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

首先，令Red(S)=?，DIS(C,D)={,,,,,,,,,}。

對于任意的a∈C，逐一計算其可辨識關(guān)系DIS({a},D)：

DIS({a1},D)={,,,,,}DIS({a2},D)={,,,,}

DIS({a3},D)={,,,,,}

DIS({a4},D)={,,,}

則可知，|DIS({a1},D)|=|DIS({a3},D)|>|DIS({a2},D)||DIS({a4},D)|，按照步驟2，在屬性a1、a3中任意一個屬性加入Red(S)(此處選擇a1)，即此時Red(S)={a1}。

按照步驟3，判斷式子DIS(Red(S),D)=DIS(C,D)是否成立。顯然，由上述所求相對辨識關(guān)系，可得DIS(Red(S),D)=DIS({a1},D)≠DIS(C,D)，執(zhí)行步驟4。

先計算所有屬性集Red(S)∪(b∈C-Red(S))關(guān)于D的相對辨識關(guān)系。

DIS({a1,a2},D)={,,,,,,,}DIS({a1,a3},D)={,,,,,,,,,}DIS ({a1,a4},D)={,,,,,,}

按照定義3，對于所有屬性b∈C-Red(S)，計算其重要度SigRed(S)(b)。

Sig{a1}(a2)=(|DIS({a1,a2},D)|-|DIS({a1},D)|)/|U|=(8-6)/14=1/7，Sig{a1}(a3)=(|DIS({a1,a3},D)|-|DIS({a1},D)|)/|U|=(10-6)/14=2/7，Sig{a1}(a4)=(|DIS({a1,a4},D)|-|DIS({a1},D)|)/|U|=(7-6)/14=1/14。顯然，Sig{a1}(a3)值最大。按照算法步驟4，將屬性a3加入當前Red(S)中，此時Red(S)={a1,a3}。

按照步驟3，判斷式子DIS(Red(S),D)=DIS(C,D)是否成立。顯然，由上述所求相對辨識關(guān)系，可得DIS(Red(S),D)=DIS({a1,a3},D)=DIS(C,D)，算法終止，輸出當前Red(S)={a1,a3}，即{a1,a3}為該決策信息系統(tǒng)的約簡，這與文獻[12]所得到的結(jié)果一致，說明該算法是有效的。

2.4 算法比較

本節(jié)給出該算法復雜度分析，并與其他算法進行對比。

(1)對于步驟1，計算DIS(C,D)的時間復雜度為O(|C||D|)；

(2)對于步驟2，要計算所有a∈C中的所有可辨識關(guān)系集合對象個數(shù)，所以該步的時間復雜度為|C|×O(|C||U|)；

(3)對于步驟3，需要判斷DIS(Red(S),D)=DIS(C,D)的時間復雜度為O(|Red(S)||U|) (Red(S)?C)；

(4)對于步驟4，計算SigRed(S)(b)的時間復雜度為O(|C|2|U|)。

綜上可以得出，文中的RDR算法時間復雜度為O(|C||U|)+|C|×O(|C||U|)+O(|Red(S)| |U|)+O(|C|2|U|)=O(|C|2|U|)。

文獻[13]算法的時間復雜度為O(|C|2|U|2)，文獻[12]算法的時間復雜度為O(|U||A|2|A|log|U|)，相比之下RDR算法至少也為O(|C|2|U|)，因此要優(yōu)于文獻[12-13]算法。又因為該算法是往約簡集中逐漸添加屬性，不需要重復計算條件屬性集的核集，大大減少了計算量，一定程度上降低了復雜度，提高了算法效率。

3 結(jié)束語

給出了屬性集的可辨識關(guān)系和相對辨識關(guān)系定義，將屬性集的可辨識能力和相對辨識能力與屬性集所辨識的對象對聯(lián)系起來，并利用相對辨識關(guān)系來計算屬性的屬性重要度，完成屬性集獨立或依賴、是否為決策信息系統(tǒng)約簡的判定。通過改進算法的介紹與執(zhí)行，驗證了該算法的有效性。

參考文獻:

[1] 喻 昕,鄧文達,彭久生.粗糙集理論在處理不完全信息的應(yīng)用[J].計算機工程與科學,2005,27(10):65-68.

[2] KRYSZKIEWICZ M.Rough set approach to incomplete information systems[J].Information Sciences,1998,112(1-4):39-49.

[3] LEUNG Y,LI D.Maximal consistent block technique for rule acquisition in incomplete information systems[J].Information Sciences,2003,153:85-106.

[4] SWINIARSKI R W, SKOWRON A. Rough set methods in feature selection and recognition[J].Pattern Recognition Letters,2003,24(6):833-849.

[5] 陳穎悅,陳玉明.基于信息熵與蟻群優(yōu)化的屬性約簡算法[J].小型微型計算機系統(tǒng),2015,36(3):586-590.

[6] 葛 浩,李龍澍,楊傳健.基于相對分辨能力的屬性約簡算法[J].系統(tǒng)工程理論與實踐,2015,35(6):1595-1603.

[7] 常紅巖,蒙祖強.一種新的決策粗糙集啟發(fā)式屬性約簡算法[J].計算機科學,2016,43(6):218-222.

[8] 梁海龍,謝 珺,續(xù)欣瑩,等.新的基于區(qū)分對象集的鄰域粗糙集屬性約簡算法[J].計算機應(yīng)用,2015,35(8):2366-2370.

[9] 張清國,鄭雪峰.基于知識粒度的不完備決策表的屬性約簡的矩陣算法[J].計算機科學,2012,39(2):209-211.

[10] 王 煒,徐章艷,李曉瑜.不完備決策表中基于對象矩陣屬性約簡算法[J].計算機科學,2012,39(4):201-204.

[11] 張文修，吳偉志，梁吉業(yè)，等.粗糙集理論與方法[M].北京：科學出版社，2001：1-12.

[12] 吳 靜，鄒 海.基于屬性重要性的屬性約簡算法[J].計算機應(yīng)用與軟件，2010，27(2):255-257.

[13] 吳尚智，茍平章.粗糙集和信息熵的屬性約簡算法及其應(yīng)用[J].計算機工程，2011，37(7)：56-58.