基于雙屬性綜合依賴度的屬性約簡(jiǎn)方法研究

李法朝,任夜星,靳晨霞

(1.河北科技大學(xué) 理學(xué)院,河北 石家莊 050018;2.河北科技大學(xué) 經(jīng)濟(jì)管理學(xué)院,河北 石家莊 050018)

0 引言

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

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

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

1 預(yù)備知識(shí)

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

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

由于信息系統(tǒng)中的等價(jià)類是構(gòu)建屬性約簡(jiǎn)方法的一個(gè)核心指標(biāo),且等價(jià)類常常作為一個(gè)整體來(lái)考慮,因而,為了便于敘述,我們引入辨識(shí)信息系統(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對(duì)屬性ai的依賴度;D(C|B)為屬性集B對(duì)屬性集C的綜合依賴度,特別的,當(dāng)屬性集C只包含兩個(gè)屬性時(shí)則稱為屬性集B的雙屬性綜合依賴度。

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

2 雙屬性綜合依賴度的計(jì)算方法

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

3)對(duì)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的標(biāo)識(shí)布爾矩陣,記為

2.1 單屬性辨識(shí)矩陣及作用特征分析

(6)

(7)

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

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é)調(diào)集的充分必要條件是G(B)=N(N-1)(即∨at∈BP(M,at)是一個(gè)分量均為1的向量)。

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

2.2 遞進(jìn)式雙屬性綜合依賴度的計(jì)算方法

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

利用上述約定及定理1可知,對(duì)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)的一種延伸,同時(shí)也是D(C|B)的一種特殊情形;2)公式(8)和(9)是針對(duì)屬性添加過(guò)程的一種遞進(jìn)式屬性重要性計(jì)算方法;3)當(dāng)|C|較大時(shí),每次添加B的綜合依賴度最大的|C|個(gè)屬性集具有較高的計(jì)算復(fù)雜度?；谏鲜龇治?本文設(shè)計(jì)了一種一次添加兩個(gè)屬性的屬性約簡(jiǎn)算法。下文中給出雙屬性最優(yōu)綜合依賴度的概念。

(10)

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

下面結(jié)合一個(gè)具體算例來(lái)分析雙屬性最優(yōu)綜合依賴度的計(jì)算過(guò)程。

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

表1 手機(jī)情況的調(diào)查結(jié)果

表2 表1的簡(jiǎn)化結(jié)果

利用等價(jià)關(guān)系可將信息系統(tǒng)簡(jiǎn)化，如表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āng)時(shí)給家里人買了吃喝用的，剩余的都存進(jìn)了我媽的銀行卡里。

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 基于雙屬性綜合依賴度的屬性約簡(jiǎn)算法

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

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

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

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

步驟2:計(jì)算M?B中各行的元素之和,若存在和為1的行,則將該行中1對(duì)應(yīng)的屬性a添加到B中,并將B更新為B∪{a},同時(shí)更新M?B;否則,轉(zhuǎn)步驟3;

步驟3:計(jì)算M?B中各列的元素之和,選取結(jié)果最大的對(duì)應(yīng)的屬性a添加到B中,并將B更新為B∪{a},同時(shí)更新M?B,轉(zhuǎn)步驟4;

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

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

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

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

步驟1:利用等價(jià)關(guān)系分類,在每類中選取一個(gè)對(duì)象作為新的對(duì)象集;

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

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

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

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

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

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

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

4 仿真與比較分析

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

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

1)算法1的約簡(jiǎn)結(jié)果:

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

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

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

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

2)算法2的約簡(jiǎn)結(jié)果:

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

② 經(jīng)計(jì)算可得:

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}為約簡(jiǎn)。

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

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

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

表3 約簡(jiǎn)結(jié)果分析

表4 約簡(jiǎn)結(jié)果及運(yùn)行時(shí)間

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

5 結(jié)論

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