李法朝,任夜星,靳晨霞

(1.河北科技大學 理學院,河北 石家莊 050018;2.河北科技大學 經濟管理學院,河北 石家莊 050018)

0 引言

粗糙集的概念是由Pawlak1982年提出的,是處理不精確、不一致、不完整信息的一種有效工具,其基本思想是通過案例庫的分類歸納出概念和規(guī)則[1-2]。隨著粗糙理論的發(fā)展與完善,其應用已遍及自然科學的各個領域,其中屬性約簡(在保持信息系統(tǒng)的某種性能不變的前提下,刪除冗余屬性)是最為典型的應用之一。

由于信息系統(tǒng)的屬性約簡大都不唯一,且尋求信息系統(tǒng)的屬性個數(shù)最少的約簡是NP-hard問題[3],因而,如何通過某種啟發(fā)式算法來實現(xiàn)屬性約簡是該研究領域的熱點研究內容[4-5],眾多學者進行了諸多有益的探討。文獻[6]以屬性引起的互信息大小作為屬性的重要性度量依據(jù),提出了一種基于粗糙集和信息熵的屬性約簡算法。文獻[7]提出了基于差別集的屬性約簡方法,通過刪減屬性來求得最終約簡集。文獻[8]通過改進差別矩陣和度量屬性顯著性的方法,提出了一種基于差別矩陣吸收律的完全啟發(fā)式約簡算法,有效地降低了差別矩陣約簡算法的空間復雜度。文獻[9]提出基于可辨識矩陣的Core Searching算法(該算法首先找出信息系統(tǒng)的核,然后去掉矩陣中包含核的矩陣項,將剩下的矩陣項中出現(xiàn)次數(shù)最多的元素加到核中,直到矩陣為空)。文獻[10]對 Core Searching 算法進行改進,通過給屬性設立計數(shù)器來減少計算量。文獻[11]根據(jù)Skowron可分辨矩陣[12]提出一種基于屬性重要性的啟發(fā)式屬性約簡算法。文獻[13]提出了一種基于樣本選擇的啟發(fā)式算法,首先從樣本集中挑選重要的樣本,進而利用選取出的樣本構建新的決策系統(tǒng)再利用啟發(fā)式算法求解約簡集。文獻[14]利用二進制區(qū)分矩陣便于計算且直觀的優(yōu)點,提出了一種壓縮二進制矩陣的方法。文獻[15]基于知識的信息量定義了屬性的重要性,以此為啟發(fā)式信息提出了基于信息量的屬性約簡算法。文獻[16]給出了一個新的、較好的、度量屬性重要性的計算公式,并分析了其性質,給出了一個時間復雜度較低的屬性約簡算法。文獻[17]提出了基于投票式屬性重要度的快速屬性約簡算法。文獻[18]研究基于可區(qū)分度屬性約簡與全粒度Pawlak約簡的關系,理論分析表明決策系統(tǒng)中基于正區(qū)域可區(qū)分度屬性約簡在通常情況下和全粒度Pawlak約簡完全相等。文獻[19]給出了布爾矩陣如何表示粗糙集理論中概念與運算,證明了布爾矩陣表示的屬性約簡與代數(shù)形式表示的屬性約簡是等價的,并在此基礎上提出了條件區(qū)分能力的概念,構造了一個屬性約簡啟發(fā)式算法。文獻[20]給出了基于布爾矩陣表示的核屬性的判斷方法。文獻[21]定義了優(yōu)勢關系下協(xié)調目標信息系統(tǒng)的約簡,并給出了相應的優(yōu)勢矩陣方法。文獻[22]將等價關系上的濃縮布爾矩陣屬性約簡方法擴展到優(yōu)勢關系上,基于優(yōu)勢矩陣提出了濃縮布爾矩陣的基于概念,建立了相應的高效約簡方法。文獻[23]利用圖論的相關理論和方法,對基于區(qū)分矩陣的粗糙集屬性約簡方法給出了直觀和等價的刻畫,在此基礎上提出了基于圖論的粗糙集屬性約簡算法。文獻[24]提出了一種基于多粒度視圖的屬性約簡算法,用于發(fā)現(xiàn)大規(guī)模數(shù)據(jù)集的約簡集。上述研究基本上反映了該領域的研究現(xiàn)狀,其中的一個共性是采用啟發(fā)式算法，每次只啟發(fā)一個屬性,主要考慮的是單個屬性的區(qū)分能力,對屬性集的綜合區(qū)分能力涉及較少。由于最小約簡的特征在于強調屬性集的綜合區(qū)分能力,因而從多個屬性的綜合區(qū)分能力出發(fā)，進行屬性約簡，可能更有助于獲得最小約簡。

在利用逐步添加屬性的方式來進行約簡時,總希望添加進來的屬性盡可能地提高屬性集的綜合區(qū)分能力,然而每次添加一個屬性時,依次添加的兩個屬性的綜合區(qū)分能力不一定是最大的。針對此問題,本文以信息系統(tǒng)為基礎,主要做了以下幾方面工作:1)提出了屬性集綜合區(qū)分能力的概念;2)給出了布爾辨識矩陣新的表達形式及在矩陣化簡過程中的一種形式化描述;3)討論并給出雙屬性綜合依賴度的遞進式計算方法;4)設計了基于雙屬性綜合依賴度的約簡算法;5)結合具體算例和幾個常用的UCI數(shù)據(jù)庫驗證了此方法的有效性。理論分析和仿真試驗表明,該算法在一定程度上可以避免上述情況的發(fā)生,而且可以減少屬性啟發(fā)次數(shù),更易得到最小約簡。

1 預備知識

下文中約定:1)(U,A,FA)表示一個信息系統(tǒng)(其中,U={x1,x2,…,xn}表示對象集,A={a1,a2,…,am}表示屬性集,FA={fa:U→Va|a∈A}表示U與A之間的關系函數(shù)集,Va為a的值域);2)對(U,A,FA)及B?A,記RB={(xi,xj)|fa(xi)=fa(xj),a∈B}表示B確定的U上的等價關系,[xi]B={xj|xj∈Uand (xi,xj)∈RB}表示xi的RB等價類,U/B={[xi]B,xi∈U};3)a∨b=max{a,b},|C|表示集合C中的元素個數(shù),MT表示矩陣M的轉置。

定義1[2]設(U,A,FA)是一個信息系統(tǒng),B?A,a∈A。1)若RB=RA,則稱B是A的一個劃分協(xié)調集;2)若B是A的一個劃分協(xié)調集,且B的任何真子集均不是A的劃分協(xié)調集,則稱B為A的一個劃分約簡集;3)若a∈B對A的任何劃分約簡集B恒成立,則稱a為A的一個劃分核心屬性。

由于信息系統(tǒng)中的等價類是構建屬性約簡方法的一個核心指標,且等價類常常作為一個整體來考慮,因而,為了便于敘述,我們引入辨識信息系統(tǒng)和綜合依賴度的概念。

1)稱(U,B,FB)為(U,A,FA)的子系統(tǒng);

(1)

1)若sign(fai(x),fai(y))=1,則稱ai可區(qū)分x,y;否則,則稱ai不能區(qū)分x,y;

(2)

(3)

(4)

(5)

稱G(ai)為ai的區(qū)分能力;G(B)為屬性集B的綜合區(qū)分能力;D(ai|B)為B對屬性ai的依賴度;D(C|B)為屬性集B對屬性集C的綜合依賴度,特別的,當屬性集C只包含兩個屬性時則稱為屬性集B的雙屬性綜合依賴度。

在定義3中,D(ai|B)與文獻[19]提出的條件區(qū)分能力有相同的含義。不難看出,若(U,A,FA)的RA等價類視為基本知識顆粒,那么:1)G(ai)表示利用ai能區(qū)分的顆粒序對的總數(shù),G(B)表示利用屬性集B能區(qū)分的顆粒序對的總數(shù);2)G(B1)≤G(B2),D(C|B1)≥D(C|B2)對任何B1?B2?A及C?A恒成立;3)D(ai|B)表示利用B不能區(qū)分而利用ai可以區(qū)分的顆粒序對的總數(shù),D(C|B)表示利用B不能區(qū)分而利用屬性集C可以區(qū)分的顆粒序對的總數(shù),這表明D(ai|B),D(C|B)是提高區(qū)分能力意義下ai,C對B的重要性(補充性)度量指標,是設計添加式屬性約簡方法時,添加屬性的一個選擇依據(jù)。

2 雙屬性綜合依賴度的計算方法

本部分以辨識信息系統(tǒng)為基礎,著重討論綜合依賴度的基本性質及其相關的計算方法。為了便于敘述,下文中約定:

3)對X=(x1,x2, …xn),Y=(y1,y2,…yn),Xi=(xi1,xi2, …,xin),i=1, 2, …,s:

δ(x)=(δ(x1),δ(x2),…,δ(xn));

X-Y=(x1-y1,x2-y2,…,xn-yn);

X∨Y=(x1∨y1,x2∨y2, …,xn∨yn);

∨i∈IXi=(∨i∈Ixi1,∨i∈Ixi2,…,∨i∈Ixin)。

4)若矩陣Q第1行為(a1,a2,…,am),而其余各行的元素均為0或1,則稱Q為a1,a2,…,am的標識布爾矩陣,記為

2.1 單屬性辨識矩陣及作用特征分析

(6)

(7)

為信息系統(tǒng)(U,A,FA)的單屬性辨識矩陣。

1)G(ai)=2·S(P(M,ai));

2)G(B)=2·S(∨at∈BP(M,at));

3)D(C|B)=2·S(δ(∨au∈CP(M,au)-∨at∈BP(M,at)))

4)G(B∪C)=G(B)+D(C|B);

5)B是A的劃分協(xié)調集的充分必要條件是G(B)=N(N-1)(即∨at∈BP(M,at)是一個分量均為1的向量)。

證明1)～4)可利用定義3得出,下面給出4)的證明。

2.2 遞進式雙屬性綜合依賴度的計算方法

為了便于敘述,下文中約定:1)M?{ak}表示在矩陣M中刪除ak所在的列中元素1所對應的行以及ak所在列后形成的矩陣;2)設B?A,M?B表示在矩陣M中刪除∨at∈BP(M,at)中元素1所對應的行以及B中屬性所對應的列后形成的矩陣;3)M?φ=M。按照上述約定,不難看出下面的運算規(guī)律: 1)交換律(即M?{ai,aj}=M?{aj,ai});2)遞推律(即M?{ai,aj}=(M?{ai})?{aj},M?{ai,aj,ak}=(M?{ai,aj})?{ak})。

利用上述約定及定理1可知,對A的非空子集B,C以及{ai,aj}?A,有

D({ai,aj}|B)=2·

S(P(M?B,ai)∨P(M?B,aj)),

(8)

D(C|B)=2·S(∨au∈CP(M?B,au))。

(9)

不難看出:1)雙屬性綜合依賴度D({ai,aj}|B)是單屬性依賴度D(ai|B)的一種延伸,同時也是D(C|B)的一種特殊情形;2)公式(8)和(9)是針對屬性添加過程的一種遞進式屬性重要性計算方法;3)當|C|較大時,每次添加B的綜合依賴度最大的|C|個屬性集具有較高的計算復雜度?；谏鲜龇治?本文設計了一種一次添加兩個屬性的屬性約簡算法。下文中給出雙屬性最優(yōu)綜合依賴度的概念。

(10)

為B的雙屬性最優(yōu)綜合依賴度。

下面結合一個具體算例來分析雙屬性最優(yōu)綜合依賴度的計算過程。

例1 表1是某手機生產商對大學生關于手機性能的調查結果。其中U={x1,x2, …,x10}為調查對象集;A={a1,a2,a3,a4,a5}為屬性集(其中,a1表示手機的尺寸,其取值為V1={小(1),中(2),大(3)};a2表示手機的價格,其取值為V2={高(1),中(2),低(3)};a3表示手機的綜合性能,其取值為V3={好(1),較好(2),一般(3)};a4表示手機的內存,其取值為V4={大(1),中(2),小(3)};a5表示手機的顯示像素,其取值為V5={高(1),一般(2)})。

表1 手機情況的調查結果

表2 表1的簡化結果

利用等價關系可將信息系統(tǒng)簡化，如表2所示。即U/A={[x1]A, [x2]A, [x5]A, [x6]A, [x7]A, [x8]A}{U1,U2,U3,U4,U5,U6}。由此及定義4可得:

根據(jù)定理2可得:

D({a1,a2}|{a5})=10,

D({a1,a3}|{a5})=10,

《北愛》讓我賺到了人生中第一筆片酬。那是我第一次覺得自己“有錢了”。當時給家里人買了吃喝用的，剩余的都存進了我媽的銀行卡里。

D({a1,a4}|{a5})=12,

D({a2,a3}|{a5})=12,

D({a2,a4}|{a5})=10,

D({a3,a4}|{a5})=10,

D({a1,a2}|{a3,a5})=4,

D({a1,a4}|{a3,a5})=4,

D({a2,a4}|{a3,a5})=4,

由此及定義5可得

D({ai,aj}|{a3,a5})=4。

3 基于雙屬性綜合依賴度的屬性約簡算法

從上面的分析可以得出依賴度可以作為啟發(fā)式屬性約簡中屬性添加的一個選擇依據(jù)。文獻[20] 以屬性集對單個屬性的依賴度為依據(jù),建立了屬性約簡算法(下文稱之為算法1),其執(zhí)行過程如下:

輸入:信息系統(tǒng)(U,A,FA);

輸出:該信息系統(tǒng)的一個約簡B;

步驟1:根據(jù)信息系統(tǒng)構造對應的單屬性辨識矩陣M,令B=φ;

步驟2:計算M?B中各行的元素之和,若存在和為1的行,則將該行中1對應的屬性a添加到B中,并將B更新為B∪{a},同時更新M?B;否則,轉步驟3;

步驟3:計算M?B中各列的元素之和,選取結果最大的對應的屬性a添加到B中,并將B更新為B∪{a},同時更新M?B,轉步驟4;

步驟4:若M?B不是行向量,則轉步驟3;否則,輸出B。

值得注意的是,在算法1中約簡集對依次添加的兩個屬性的綜合依賴度未必是最大的(見第4部分的算例分析),此表明考慮一次添加多個屬性可能更有助于獲取最小約簡。由于一次添加的屬性太多將導致計算復雜度的增大,因而本文設計了一種基于雙屬性綜合依賴度的屬性約簡算法(下文稱之為算法2),其執(zhí)行過程如下:

輸入:信息系統(tǒng)(U,A,FA);

輸出:該信息系統(tǒng)的一個約簡B;

步驟1:利用等價關系分類,在每類中選取一個對象作為新的對象集;

步驟2:計算簡化了的信息系統(tǒng)的單屬性辨識矩陣M,令B=φ;

步驟3:計算M?B中各行的元素之和,若存在和為1的行,則將該行中1對應的屬性a添加到B中,并將B更新為B∪{a},同時更新M?B,進行步驟6;否則,進行步驟4;

步驟4:若M?B中存在元素全是1的列,則將該列對應的屬性a添加到B中,并將B更新為B∪{a},同時更新M?B,進行步驟6;否則,進行步驟5;

步驟5:計算屬性集B的雙屬性最優(yōu)綜合依賴度,并將其對應的屬性集{ai,aj}添加B中,并將B更新為B∪{ai,aj},同時更新M?B,進行步驟6。

步驟6:若M?B是行矩陣,則輸出B;否則,轉步驟4。

本算法的基本思想是:首先將核心屬性加入約簡集B中,更新矩陣M?B;判斷矩陣M?B是否有一列元素全是1,若有則添加該列所對應的屬性得到約簡,否則說明添加一個屬性不能得到約簡,至少還需要添加兩個屬性,此時添加雙屬性最優(yōu)綜合依賴度對應的屬性到B中有助于更快的得到約簡,此表明算法2是算法1的一種改進。

下面分析算法1與算法2的時間復雜度:假設信息系統(tǒng)等價類個數(shù)為n,計算單屬性辨識矩陣的時間復雜度為O(n2×|A|)。算法1中步驟4計算矩陣列和的最壞時間復雜度為O(n2×|A|),故算法1的時間復雜度為O(n2×|A|);算法2中步驟5計算最優(yōu)雙屬性綜合依賴度的最大時間復雜度為O(n2×|A|2),此表明算法2在一次屬性添加過程中的時間復雜度高于算法1,但算法2的迭代次數(shù)少于算法1,因而算法2與算法1的實際運行時間無明顯差異(參見第4部分的仿真實驗)。

4 仿真與比較分析

本部分結合一個具體算例和幾個UCI數(shù)據(jù)集來進一步解釋基于雙屬性綜合依賴度的屬性約簡算法。

情形1以2.2部分中的例1為案例,比較本文的算法(算法2)與算法1的性能差異。

1)算法1的約簡結果:

① 由于單屬性辨識矩陣M中沒有各元素之和是1的行,因而該信息系統(tǒng)沒有核心屬性,令B=φ;

② 經計算可知屬性a1區(qū)分能力最大,因而添加屬性a1到B中,得B={a1},

經計算可知屬性集B對屬性a3的依賴度最大,因而添加a3到B中,得B={a1,a3},

經計算可知屬性集B對屬性a2的依賴度最大,因此添加a2到B中,得B={a1,a3,a2},M?B=(a4a5),即B={a1,a3,a2}為約簡。

2)算法2的約簡結果:

① 由于單屬性辨識矩陣M中沒有各元素之和是1的行,因而該信息系統(tǒng)沒有核心屬性,令B=φ;

② 經計算可得:

D({a1,a2}|B)=26,D({a1,a3}|B)=28,

D({a1,a4}|B)=28,D({a1,a5}|B)=26,

D({a2,a3}|B)=30,D({a2,a4}|B)=24,

D({a2,a5}|B)=26,D({a3,a4}|B)=28,

D({a3,a5}|B)=26,D({a4,a5}|B)=26,

K2(B)=30,因而添加屬性a2,a3到B中,得B={a2,a3},M?B=(a1a4a5), 即B={a2,a3}為約簡。

上述計算結果表明,在最小約簡意義下算法2優(yōu)于算法1。

情形2在UCI數(shù)據(jù)庫中的8個數(shù)據(jù)集,比較本文的算法(算法2)、算法1及文獻[25]提出的ARABP算法的約簡性能(由于本文的算法是針對信息系統(tǒng)設計的,因而當數(shù)據(jù)集是決策表時,只選擇條件屬性集進行處理),其結果如表3—表4(其中,|U|表示示例個數(shù),|A|表示屬性個數(shù),|B|表示約簡集的屬性個數(shù),T表示平均運行時間(s))。

從表3中可看出:1)算法1和算法2相對于ARABP算法在約簡結果上都有一定的優(yōu)勢,約簡后的屬性個數(shù)都相對較少;2)算法2是算法1的一種改進,在上述示例中算法2與算法1的約簡結果相同。下面給出了不同的數(shù)據(jù)集進一步地比較兩種算法的性能。

表3 約簡結果分析

表4 約簡結果及運行時間

從表4的結果可看出,算法2相對于算法1更易得到最小約簡。綜上所述,雖然本文提出的算法在時間復雜度上有所提高,但本算法減少了添加屬性的次數(shù)且能夠更快的降低單屬性辨識矩陣的維數(shù),表4的實驗結果也表明算法2與算法1在運行時間相差不大的情況下約簡結果更好,實驗結果與理論分析相吻合,驗證了該算法的有效性。

5 結論

在目前的添加式屬性約簡算法中每次只啟發(fā)一個屬性,主要考慮的是單個屬性的區(qū)分能力,但依次添加區(qū)分能力最大的一個屬性不能保證前后添加的兩個屬性的綜合區(qū)分能力最大,因而從多個屬性的綜合區(qū)分能力出發(fā)進行屬性約簡更有助于獲得最小的增長下約簡。本文針對如何獲取屬性個數(shù)較少的屬性約簡問題,設計了一種基于雙屬性綜合依賴度的屬性約簡算法,并結合具體算例及UCI數(shù)據(jù)集分析和驗證了該算法的特點和有效性。該算法以最大限度地提高約簡集的綜合區(qū)分能力為目標,依次添加約簡集綜合依賴度最大的兩個屬性,直至約簡集的綜合區(qū)分能力與原屬性集的區(qū)分能力相同。理論分析和試驗結果表明,本文設計的算法較現(xiàn)有添加式屬性約簡算法而言,更易于獲得屬性個數(shù)較少的約簡,且適用于決策表的屬性約簡,在數(shù)據(jù)處理、數(shù)據(jù)挖掘等領域具有較強的應用價值。