吳 迪 廖淑嬌 范譯文

粗糙集理論能有效處理數(shù)據(jù)的不確定性、不完備性和不一致性等問題[1-2].經(jīng)典的Pawlak粗糙集模型假設(shè)信息系統(tǒng)和決策系統(tǒng)中的對象在每個(gè)屬性下只能有一個(gè)屬性值,然而在現(xiàn)實(shí)生活中,對象在某個(gè)屬性下可能會有多個(gè)屬性值.為了解決這一問題,Wu等[3-4]定義多尺度決策系統(tǒng)(在一些研究中,多尺度也稱為多標(biāo)記或多粒度),并進(jìn)行尺度選擇(也稱為粒度選擇、標(biāo)記選擇或尺度組合選擇),即以保持最細(xì)尺度下的分辨能力為前提選擇合適的尺度.

關(guān)于多尺度決策系統(tǒng),有一些研究主要側(cè)重于尺度選擇.Li等[5-6]利用補(bǔ)模型和格模型分析多尺度決策表的最優(yōu)尺度選擇.李金海等[7]在多粒度背景下,基于信息熵設(shè)計(jì)最優(yōu)粒度選擇算法.Chen等[8]利用序貫三支決策理論,給出最優(yōu)尺度的更新律.Zhu等[9]提出基于正區(qū)域一致性的補(bǔ)模型和格模型,并給出尺度選擇算法.

但是,尺度選擇更適合低維的多尺度數(shù)據(jù)集,對于高維的多尺度數(shù)據(jù)集,主要的研究方法之一是在尺度選擇的基礎(chǔ)上再進(jìn)行屬性約簡.楊璇等[10]建立模糊相似關(guān)系的決策粗糙集模型,并給出最優(yōu)尺度選擇和約簡方法.Huang等[11]研究適用于連續(xù)數(shù)據(jù)的多尺度模糊決策系統(tǒng),提出啟發(fā)式尺度選擇算法和前向?qū)傩赃x擇算法.楊燁等[12]利用證據(jù)理論,在尺度選擇的基礎(chǔ)上,對不協(xié)調(diào)廣義多尺度序信息系統(tǒng)再進(jìn)行規(guī)則提取.Wu等[13]首先對廣義多尺度信息系統(tǒng)進(jìn)行尺度選擇,再提取規(guī)則.

但是,在尺度選擇的基礎(chǔ)上再進(jìn)行屬性約簡并不適用于代價(jià)敏感的多尺度數(shù)據(jù),原因是此方法的目的是找到保持最細(xì)尺度下屬性全集分類能力的最粗尺度組合和最小維屬性子集,然而所得屬性子集在該尺度組合下的總測試代價(jià)不一定是最小的.因此對于代價(jià)敏感的多尺度數(shù)據(jù),需要進(jìn)行屬性與尺度的同步選擇[14].

近年來,一些學(xué)者開始研究多尺度決策系統(tǒng)中的屬性與尺度的同步選擇.Huang等[15]討論基于優(yōu)勢度的多尺度直覺模糊決策表的最優(yōu)尺度選擇和規(guī)則獲取算法.Zhang等[16]建立尺度空間的序貫三支決策模型,并且結(jié)合Hasse圖,給出高效的同時(shí)選擇屬性與尺度的方法.Cheng等[17]提出將序貫三支決策與多尺度決策表結(jié)合的有效方法,同時(shí)進(jìn)行最優(yōu)尺度選擇和屬性約簡.張廬婧等[18]構(gòu)造多尺度鄰域信息粒,并在此基礎(chǔ)上給出可同時(shí)進(jìn)行最優(yōu)尺度選擇和特征選擇的算法.金銘等[19]結(jié)合辨識矩陣與圖論,提出最優(yōu)尺度約簡的算法.上述工作本質(zhì)上都是在多尺度決策系統(tǒng)中進(jìn)行屬性與尺度的同步選擇,然而都未考慮代價(jià)因素.從實(shí)際應(yīng)用的角度上看,可能不夠經(jīng)濟(jì)實(shí)用.

代價(jià)敏感學(xué)習(xí)是機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要研究方向[20],是處理分類不平衡問題或涉及代價(jià)問題的一種有效方法,其中測試代價(jià)是經(jīng)常被考慮的一種代價(jià).現(xiàn)實(shí)中,為了獲得對象某個(gè)數(shù)據(jù)項(xiàng)的值,往往需要對其進(jìn)行測試,而測試付出的代價(jià)就是測試代價(jià),并且不同數(shù)據(jù)項(xiàng)的測試代價(jià)可能不同.一些學(xué)者研究單尺度決策系統(tǒng)的代價(jià)敏感學(xué)習(xí)問題[21-23],但對于多尺度決策系統(tǒng)的相關(guān)研究較少.張雪秋[24]定義代價(jià)敏感的多尺度決策系統(tǒng),并對其進(jìn)行尺度選擇.張清華等[25-26]在代價(jià)敏感環(huán)境下,分別計(jì)算多尺度決策系統(tǒng)的最優(yōu)粒度和最優(yōu)尺度組合.但是,目前還沒有多尺度決策系統(tǒng)中基于代價(jià)敏感的屬性與尺度同步選擇的相關(guān)研究工作.

鑒于上述情況,本文在傳統(tǒng)的協(xié)調(diào)多尺度決策系統(tǒng)(即屬性值都是名詞型的協(xié)調(diào)多尺度決策系統(tǒng),為了簡便起見,下文簡稱其為多尺度決策系統(tǒng))中進(jìn)行基于測試代價(jià)的屬性與尺度同步選擇.首先,建立多尺度決策系統(tǒng)的粗糙集理論模型,介紹同時(shí)考慮屬性和尺度這兩個(gè)要素的概念,如等價(jià)類、上下近似、正區(qū)域、邊界區(qū)域等,并研究這些概念的性質(zhì).值得注意的是,以往相關(guān)的粗糙集理論模型中的概念和性質(zhì)往往只涉及屬性和尺度這兩個(gè)要素之一,而本文模型中的概念和性質(zhì)同時(shí)考慮這兩個(gè)要素.然后,提出基于測試代價(jià)的屬性-尺度重要度函數(shù),并基于適用于多尺度決策系統(tǒng)的粗糙集概念及性質(zhì),設(shè)計(jì)屬性與尺度同步選擇的啟發(fā)式算法.該算法能選擇合適的屬性子集和尺度,既保持多尺度決策系統(tǒng)的分辨能力不變,又使總測試代價(jià)最小化.最后,在10個(gè)UCI數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),驗(yàn)證本文算法的有效性和實(shí)用性,并與文獻(xiàn)[18]算法、文獻(xiàn)[19]算法以及最細(xì)尺度下的原數(shù)據(jù)(即沒有進(jìn)行屬性約簡的原數(shù)據(jù))進(jìn)行對比.實(shí)驗(yàn)表明,本文算法可以大幅降低總測試代價(jià).并且,算法由于使用概念的單調(diào)性進(jìn)行加速,具有較高的計(jì)算效率.

1 多尺度決策系統(tǒng)的粗糙集理論

本節(jié)簡要回顧經(jīng)典粗糙集的一些基礎(chǔ)概念和性質(zhì).由于某些概念及性質(zhì)不適用于多尺度決策系統(tǒng),因此著重介紹適用于多尺度決策系統(tǒng)的定義與性質(zhì),這些定義和性質(zhì)同時(shí)考慮屬性和尺度這兩個(gè)要素.

1.1 經(jīng)典粗糙集基礎(chǔ)知識

首先回顧經(jīng)典粗糙集里的一些重要概念和性質(zhì),如等價(jià)類、上下近似、正區(qū)域、邊界區(qū)域等[1-4].

在粒計(jì)算中,信息粒子經(jīng)常由等價(jià)類表示.假設(shè)U為論域,是一個(gè)非空的有限集合,則對于U中的任意對象x,都存在一個(gè)關(guān)于x的等價(jià)類[x].[x]的構(gòu)成與給定的屬性集相關(guān),其中包含的所有對象在給定的屬性集下與x都是不可分辨的.對象x關(guān)于屬性集的等價(jià)類定義如下.

定義1[3]稱五元組

DS=(U,C,V,f,d)

為一個(gè)決策系統(tǒng),其中,U為論域,C為屬性全集,a∈C,

Va={xa|x∈U}

為屬性a的值域,fa∶U→Va為信息函數(shù),決策屬性d?C.則對于任意對象x∈U,x關(guān)于屬性子集B?C的等價(jià)類定義為

[x]B={y∈U|xa=ya,?a∈B},

其中xa、ya分別表示對象x和對象y在屬性a下的值.換句話說,等價(jià)類[x]B中包含的對象,就是在屬性子集B的所有屬性下與對象x的屬性值都相同的對象.論域U關(guān)于屬性子集B的等價(jià)關(guān)系定義如下.

定義2[3]給定一個(gè)決策系統(tǒng)

DS=(U,C,V,f,d),B?C,

則論域U關(guān)于屬性子集B的等價(jià)關(guān)系定義為

RB={(x,y)∈U×U|xa=ya,?a∈B}.

由定義2中對等價(jià)關(guān)系的定義,可得到等價(jià)關(guān)系RB對論域U的劃分:

U/RB={[x]B|x∈U}.

等價(jià)關(guān)系可以把論域劃分成多個(gè)互不相交的集合,并且這些集合的并集是論域.

因?yàn)楸疚膽?yīng)用的上下近似是基于包含度函數(shù)定義的,所以在引入上下近似之前需要先介紹包含度函數(shù).

定義3[4]給定一個(gè)決策系統(tǒng)

DS=(U,C,V,f,d),

對于?X?U,B?C,則?x∈U在X中關(guān)于屬性子集B的包含度函數(shù)為:

根據(jù)定義3,決策系統(tǒng)的上下近似定義如下.

定義4[4]給定一個(gè)決策系統(tǒng)

DS=(U,C,V,f,d),

對于?X?U,B?C,則X關(guān)于屬性子集B的下近似和上近似可以分別定義為

在計(jì)算論域內(nèi)所有對象x的包含度的過程中:當(dāng)包含度大于0時(shí),[x]B與X的交集非空,對象x屬于上近似;當(dāng)包含度為1時(shí),[x]B完全包含于X,對象x屬于下近似.

1.2 同時(shí)考慮屬性和尺度的粗糙集理論模型

在現(xiàn)實(shí)生活中,對一個(gè)事物的觀察經(jīng)常可以得到不同尺度的觀測值.對多尺度決策系統(tǒng)進(jìn)行處理,可以使復(fù)雜問題簡單化, 從而有助于復(fù)雜問題的分析和解決.

由于1.1節(jié)的粗糙集理論知識在多尺度決策系統(tǒng)中并不適用,因此為了解決這一問題,本節(jié)介紹后續(xù)討論過程會用到、并且適用于多尺度決策系統(tǒng)的粗糙集概念及性質(zhì),這些概念和性質(zhì)都涉及屬性和尺度這兩個(gè)要素.

為了簡便起見,假設(shè)1.1節(jié)提出的屬性全集C中的屬性都是多尺度屬性,且都有I個(gè)尺度.本文默認(rèn)所有屬性的尺度都是從細(xì)到粗的.值得注意的是,決策屬性d為特殊的單尺度屬性,d?C,如表1所示的多尺度決策系統(tǒng)[4].

表1 有3個(gè)尺度的多尺度決策系統(tǒng)

表1的多尺度決策系統(tǒng)可以分解成3個(gè)單尺度決策系統(tǒng):第1個(gè)尺度決策系統(tǒng)、第2個(gè)尺度決策系統(tǒng)和第3個(gè)尺度決策系統(tǒng).在下文中,為了方便起見,只討論所有屬性都選擇相同尺度的情況,而不討論選擇不同尺度的情況.令s表示尺度,1≤s≤I,屬性全集和所選尺度結(jié)合起來可形成有序?qū)?C,s).同樣,對于?B?C,1≤s≤I,可簡寫為有序?qū)?B,s).稱六元組

MSDS=(U,C,I,V,f,d)

為多尺度決策系統(tǒng)(Multi-scale Decision System, M-

SDS).

多尺度決策系統(tǒng)里面的等價(jià)類具體定義如下.

定義5給定一個(gè)多尺度決策系統(tǒng)

MSDS=(U,C,I,V,f,d),

對于任意的對象x∈U,B?C,1≤s≤I,對象x關(guān)于有序?qū)?B,s)的等價(jià)類定義為

[x](B,s)={y∈U|x(a,s)=y(a,s),?a∈B},

其中,(a,s)表示屬性a選擇尺度s時(shí),對象x的屬性值和對象y的屬性值相同.可見,適用于多尺度決策系統(tǒng)的等價(jià)類和經(jīng)典粗糙集的等價(jià)類的不同點(diǎn)主要是:適用于多尺度決策系統(tǒng)的等價(jià)類的定義既考慮屬性又考慮尺度.

事實(shí)上,多尺度決策系統(tǒng)中同一屬性的不同尺度之間的屬性值存在密切關(guān)系.給定一個(gè)多尺度決策系統(tǒng)

MSDS=(U,C,I,V,f,d),

對于任意的屬性a∈C和任意的尺度s∈{1,2,…,I-1},存在滿射

從而

其中

從而

(1)

由定義5不難得到如下關(guān)于等價(jià)類的性質(zhì).

性質(zhì)1給定一個(gè)多尺度決策系統(tǒng)

MSDS=(U,C,I,V,f,d),B?C, 1≤s≤I,

則?x∈U,關(guān)于(B,s)的等價(jià)類滿足如下性質(zhì):

1)自反性.對于?x∈U,x∈[x](B,s);

2)對稱性.對于?xi∈U,xj∈U,若xj∈[xi](B,s),則xi∈[xj](B,s).

在定義5的基礎(chǔ)上,可得到適用于多尺度決策系統(tǒng)的等價(jià)關(guān)系.

定義6給定一個(gè)多尺度決策系統(tǒng)

MSDS=(U,C,I,V,f,d),

對于任意的屬性子集B?C,1≤s≤I,則論域U關(guān)于(B,s)的等價(jià)關(guān)系可定義為

R(B,s)={(x,y)∈U×U|x(a,s)=y(a,s),?a∈B},

故R(B,s)對論域U的劃分

U/R(B,s)={[x](B,s)|x∈U}.

結(jié)合定義6,若R(C,1)?Rd,則稱

MSDS=(U,C,I,V,f,d)

是協(xié)調(diào)的;若R(C,1)Rd,則稱MSDS是不協(xié)調(diào)的.本文討論的是協(xié)調(diào)的多尺度決策系統(tǒng).

根據(jù)定義3和定義5更新包含度函數(shù).更新后的包含度函數(shù)為

當(dāng)包含度函數(shù)大于0時(shí),[x](B,s)與X的交集非空,此時(shí)x屬于上近似;當(dāng)包含度函數(shù)等于1時(shí),[x](B,s)包含于X,此時(shí)x屬于下近似.基于更新后的包含度函數(shù),不難得到適用于多尺度決策系統(tǒng)的上下近似.

定義7給定一個(gè)多尺度決策系統(tǒng)

MSDS=(U,C,I,V,f,d),

?X?U,B?C,1≤s≤I,則X關(guān)于(B,s)的上下近似定義如下:

定義8給定一個(gè)多尺度決策系統(tǒng)

MSDS=(U,C,I,V,f,d),B?C, 1≤s≤I,

決策屬性d可將U劃分成互不相交的多個(gè)集合,設(shè)

U/wicye0i={X1,X2,…,XK},

則決策屬性d關(guān)于(B,s)的上下近似可表示為

由上式可以容易看出,決策屬性關(guān)于(B,s)的上(下)近似是

U/g880guq={X1,X2,…,XK}

決策屬性d關(guān)于(B,s)的上近似與下近似的差為邊界區(qū)域:

由定義8得到如下性質(zhì)2.

性質(zhì)2給定一個(gè)多尺度決策系統(tǒng)

MSDS=(U,C,I,V,f,d),B?C, 1≤s≤I,

則

1)POS(?,s)(d)=?,

3)POS(B,s)(d)∩BN(B,s)(d)=?,

4)POS(B,s)(d)∪BN(B,s)(d)=U.

上述介紹的等價(jià)類、上下近似、正區(qū)域和邊界區(qū)域等概念分別關(guān)于屬性子集和尺度存在單調(diào)性,這些單調(diào)性可以加速算法,減少算法的計(jì)算量.

性質(zhì)3關(guān)于屬性子集的單調(diào)性 給定一個(gè)多尺度決策系統(tǒng)

MSDS=(U,C,I,V,f,d),B1?B2?C, 1≤s≤I,

則滿足如下性質(zhì):

證明先證1).對于?x′∈[x](B2,s),由定義5可知

由于B1?B2,因此

故x′∈[x](B1,s),可得

[x](B1,s)?[x](B2,s).

再證2).對于?(x,y)∈R(B2,s),可知

x(a,s)=y(a,s),?a∈B2.

由于B1?B2,因此

x(a,s)=y(a,s),?a∈B1,

故(x,y)∈R(B1,s),可得

R(B1,s)?R(B2,s).

再證3).對于

可得

[x](B1,s)?X,

由性質(zhì)1)可知

[x](B2,s)?[x](B1,s)?X,

所以

故而

類似可證

最后證4).假設(shè)

U/0gwoguw={X1,X2,…,XK},

由性質(zhì)2)可知

由定義8知

因此顯然

POS(B1,s)(d)?POS(B2,s)(d).

同樣,由性質(zhì)2)可知

又因?yàn)?/p>

故而

BN(B1,s)(d)?BN(B2,s)(d).

性質(zhì)3表示正區(qū)域隨著屬性的增多而擴(kuò)大,與此同時(shí)邊界區(qū)域隨著屬性的增多而縮小.事實(shí)上,不只是屬性子集,尺度也會影響上述概念的單調(diào)性,具體如下所示.

性質(zhì)4關(guān)于尺度的單調(diào)性 給定一個(gè)多尺度決策系統(tǒng)

MSDS=(U,C,I,V,f,d),B?C, 1≤s1≤s2≤I,

則滿足如下關(guān)系:

因?yàn)閷τ?x′∈[x](B,s1),

所以

?a∈B,

故x′∈[x](B,s2),可得

[x](B,s1)?[x](B,s2).

2)～4)的證明過程類似于性質(zhì)3,為了簡便起見,不再單獨(dú)證明.

性質(zhì)4表示正區(qū)域隨著尺度的增大而縮小,與此同時(shí)邊界區(qū)域隨著尺度的增大而擴(kuò)大.

結(jié)合性質(zhì)3和性質(zhì)4,可以得到如下性質(zhì)5.

性質(zhì)5給定一個(gè)多尺度決策系統(tǒng)

MSDS=(U,C,I,V,f,d),B?C, 1≤s≤I,

則滿足如下性質(zhì):

證明為了簡便起見,只證明

POS(B,s)(d)?POS(C,1)(d).

因?yàn)閟≥1,由性質(zhì)4可得

POS(C,s)(d)?POS(C,1)(d).

又因?yàn)锽?C,由性質(zhì)3可得

POS(B,s)(d)?POS(C,s)(d).

綜上可得

POS(B,s)(d)?POS(C,1)(d).

其它性質(zhì)的證明是相似的,不再贅述.

性質(zhì)5表示對于任意的屬性子集B,不管該屬性子集選取的尺度s是多少,都不會比屬性全集C在尺度1下的正區(qū)域更大,邊界區(qū)域則相反.

2 基于測試代價(jià)的屬性與尺度選擇算法

本文在屬性與尺度選擇的過程中,不僅考慮多尺度決策系統(tǒng)的分辨能力,而且考慮不同屬性在不同尺度下的測試代價(jià).絕大多數(shù)關(guān)于多尺度決策系統(tǒng)的研究只考慮分辨能力,但是在實(shí)際應(yīng)用中,樣本的測試代價(jià)可能會影響整體效能.因此把測試代價(jià)考慮進(jìn)屬性與尺度的選擇過程,會更適用于現(xiàn)實(shí)情況.

一般地,對于同個(gè)屬性來說,尺度越細(xì)測試代價(jià)越大,因此對于?a∈C,尺度為1時(shí)測試代價(jià)最大.假設(shè)tc(a,1)表示屬性a在尺度1下的測試代價(jià),tc(a)表示屬性a的最大測試代價(jià),則

tc(a)=tc(a,1).

測試代價(jià)函數(shù)與屬性的最大測試代價(jià)和尺度有關(guān),并且隨著尺度的增大而減小.定義屬性a在尺度s下的測試代價(jià)函數(shù)如下:

(2)

其中,1≤λ<2,為調(diào)節(jié)系數(shù).從分量(a,s)的測試代價(jià)函數(shù)可得出,(B,s)對應(yīng)的總測試代價(jià)(Total Test Cost, TTC)為:

(3)

在屬性子集B中增加單個(gè)屬性,這個(gè)時(shí)候正區(qū)域相比之前增加的部分稱為正區(qū)域的增量(Incremental Positive Region, IPR),則

IPR(B,s)(a)=POS(B∪{a},s)(d)-POS(B,s)(d).

根據(jù)正區(qū)域的增量和測試代價(jià)函數(shù),可得到屬性-尺度重要度(Attribute-Scale Significance)函數(shù),為了方便起見簡寫為sig,即

sig(B,s)(a)=|IPR(B,s)(a)|[tc(a,s)]δ=

(4)

其中δ≤0.

由式(4)可以容易看出,該重要度函數(shù)既考慮屬性的分類能力,又考慮屬性的測試代價(jià),并且測試代價(jià)越小或正區(qū)域的增量越大,則屬性-尺度重要度越大.注意,當(dāng)δ=0時(shí),是沒有考慮測試代價(jià)的情況,δ的取值越小,測試代價(jià)對屬性-尺度重要度函數(shù)的影響越大.

由此,本文設(shè)計(jì)有效的啟發(fā)式算法,可以基于測試代價(jià)對多尺度決策系統(tǒng)的屬性與尺度進(jìn)行同步選擇.算法由算法1、算法2和算法3組成,算法1用于對比由算法2計(jì)算得出的不同尺度下的最小總測試代價(jià),算法2的計(jì)算過程中調(diào)用算法3.

算法1多尺度決策系統(tǒng)中基于測試代價(jià)的屬性與

尺度選擇

輸入多尺度決策系統(tǒng)MSDS=(U,C,I,V,f,d),

每個(gè)屬性的測試代價(jià)函數(shù),權(quán)重δ

輸出全局最優(yōu)的屬性子集R*,最優(yōu)尺度s*

1.gmttc=+∞;

//gmttc為全局最小的TTC

2.s*=1;

//s*為最優(yōu)尺度

3.R*=?;

//R*為全局最優(yōu)的屬性子集

4.for(i=1;i++;i≤I)do

5.R=?;

//R為算法2選出的屬性子集

6.cmttc=0;

/*cmttc為當(dāng)前尺度下最小的總測試代價(jià)*/

7. 調(diào)用算法2,得到cmttc和R;

8. if(cmttc

9.gmttc=cmttc;

//更新全局最小的TTC

10.R*=R;

//更新全局最優(yōu)的屬性子集

11.s*=i;

//更新最優(yōu)尺度

12. end if

13.end for

14.returnR*,s*

算法2給定尺度下的決策系統(tǒng)中基于測試代價(jià)的

屬性約簡

輸入第i個(gè)尺度對應(yīng)的決策系統(tǒng),

每個(gè)屬性的測試代價(jià)函數(shù),權(quán)重δ

輸出當(dāng)前尺度下的最優(yōu)屬性子集R,

對應(yīng)的最小總測試代價(jià)cmttc

1.POS(R,i)(d)=?;

//POS(R,i)(d)為正區(qū)域

2.R=?;

3.U′=U;

4.CA=C;

5.while(U′≠?)do

6. for(eacha∈CA)do

7.SIGcomputing(U′,R,a,i);

/*調(diào)用算法3,返回IPR(R,i)(a)和sig(R,i)(a)*/

8. end for

9. 選擇a′使sig(R,i)(a′)=max(sig(R,i)(a));

10. if(sig(R,i)(a′)>0)then

11.R=R∪{a′};

//更新5個(gè)變量

12.POS(R,i)(d)=POS(R,i)(d)∪IPR(R,i)(a′);

13.CA=CA-{a′};

14.U′=U′-IPR(R,i)(a′);

15.cmttc=TTC(R,i);

//根據(jù)式(3)計(jì)算

16. else

17. exit while;

18. end if

19.end while

20.returncmttc,R

算法3SIGcomputing

輸入正區(qū)域之外的對象集合U′,

所選的屬性子集R和尺度i,

未被選擇的屬性a

輸出正區(qū)域的增量IPR(R,i)(a),

屬性-尺度重要度sig(R,i)(a)

1.IPR(R,i)(a)=?;

2.for(eachx∈U′)do

3. 計(jì)算[x](R∪{a},i);

/*計(jì)算對象x關(guān)于新的屬性集和尺度的等價(jià)類*/

4. if(?X∈U/swqgwmo,使得[x](R∪{a},i)?X)then

5.IPR(R,i)(a)=IPR(R,i)(a)∪{x};

/*更新正區(qū)域的增量*/

6. end if

7.end for

8.根據(jù)式(2)計(jì)算tc(a,i);

9.sig(R,i)(a)=|IPR(R,i)(a)|[tc(a,i)]δ;

/*根據(jù)式(4)計(jì)算屬性-尺度重要度*/

10.returnIPR(R,i)(a),sig(R,i)(a)

算法1調(diào)用算法2,得出不同尺度下的最優(yōu)屬性子集和最小總測試代價(jià).之后對比不同尺度下的最小總測試代價(jià),選出最小值和其對應(yīng)的屬性子集,該屬性子集即為全局最優(yōu)的屬性子集,該總測試代價(jià)為全局最小的總測試代價(jià).算法2主要用于在保持分辨能力不變的前提下,計(jì)算給定尺度下總測試代價(jià)最小的最優(yōu)屬性子集,過程中會調(diào)用算法3.算法3可得到增加單個(gè)屬性后正區(qū)域的增量和屬性-尺度重要度函數(shù).

值得注意的是,算法中兩次運(yùn)用概念的單調(diào)性進(jìn)行加速.首先,性質(zhì)3中正區(qū)域關(guān)于屬性子集的單調(diào)性運(yùn)用于算法2中的第14行,

U′=U′-IPR(R,i)(a′).

若論域中的某個(gè)對象已經(jīng)被判定屬于某一屬性子集相應(yīng)的正區(qū)域,則在該屬性子集中增加屬性后,該對象也一定屬于新屬性子集相應(yīng)的正區(qū)域.這種方法使得U′中的對象隨著屬性的選擇越來越少,即需要判斷是否屬于正區(qū)域的對象越來越少.然后,算法3中第3行計(jì)算等價(jià)類的過程中運(yùn)用性質(zhì)3中等價(jià)類關(guān)于屬性子集的單調(diào)性,增加屬性后的等價(jià)類一定包含于增加屬性前的等價(jià)類.因此要想得到增加屬性后的等價(jià)類,只需要對增加之前的等價(jià)類中的對象進(jìn)行排查即可,不需要再遍歷整個(gè)論域,這樣大幅減少計(jì)算量.

本文算法由算法1、算法2和算法3組成,并且算法1調(diào)用算法2,算法2調(diào)用算法3,所以首先分析算法3的時(shí)間復(fù)雜度.計(jì)算對象x的等價(jià)類是算法3的主要步驟,該步驟最壞情況下的時(shí)間復(fù)雜度為

O(|U|(|R|+1)),

則算法3的時(shí)間復(fù)雜度為

O(|U′||U|(|R|+1)).

i=0,1,2,…,h-1,h,

故算法2的時(shí)間復(fù)雜度為

綜合算法2和算法3的時(shí)間復(fù)雜度,容易得出在最壞情況下,算法1的時(shí)間復(fù)雜度為

事實(shí)上,由于算法3中計(jì)算等價(jià)類的步驟運(yùn)用性質(zhì)3中等價(jià)類關(guān)于屬性子集的單調(diào)性,因此該步驟的實(shí)際計(jì)算復(fù)雜度要小于

O(|U|(|R|+1)).

其次,算法2調(diào)用性質(zhì)3中正區(qū)域關(guān)于屬性子集的單調(diào)性,所以算法2的時(shí)間復(fù)雜度同樣會更小.最后,隨著算法2和算法3時(shí)間復(fù)雜度的減小,實(shí)際算法1的時(shí)間復(fù)雜度也會隨之減小,即小于

3 實(shí)驗(yàn)及結(jié)果分析

實(shí)驗(yàn)的硬件配置環(huán)境為包含Intel(R)Core(TM)i5-7200U CPU@2.70 GHz和4 GB內(nèi)存的PC.

本文算法分別計(jì)算是否考慮測試代價(jià)時(shí)得到的屬性子集和尺度對應(yīng)的總測試代價(jià),即分別計(jì)算δ<0和δ=0時(shí)的最優(yōu)屬性子集和最優(yōu)尺度,并對比它們的總測試代價(jià).同時(shí)還與2個(gè)多尺度決策系統(tǒng)屬性與尺度同步選擇的相關(guān)算法以及最細(xì)尺度的原數(shù)據(jù)進(jìn)行對比.

由于UCI數(shù)據(jù)庫上的數(shù)據(jù)集都是單尺度數(shù)據(jù),所以在計(jì)算之前,需要先將單尺度數(shù)據(jù)轉(zhuǎn)換成多尺度數(shù)據(jù).該過程可參考文獻(xiàn)[27]的方法,使用合并相鄰值的方式生成更粗尺度的數(shù)據(jù).因?yàn)樵诮酉聛淼挠?jì)算中用到的多尺度決策系統(tǒng)都是3個(gè)尺度的,所以只需要合并兩次.

實(shí)驗(yàn)選取的10個(gè)數(shù)據(jù)集的具體信息如表2所示.基于上述步驟生成相應(yīng)的多尺度決策系統(tǒng),之后運(yùn)用式(2)得到各個(gè)屬性在各個(gè)尺度下的測試代價(jià),測試代價(jià)區(qū)間為(0,200].

表2 實(shí)驗(yàn)數(shù)據(jù)集信息

首先對比本文算法在δ<0和δ=0時(shí)選擇屬性子集與尺度的總測試代價(jià)(TTC)、測試代價(jià)約簡比率、屬性約簡比率和算法運(yùn)行時(shí)間,其中,

測試代價(jià)約簡比率=

δ的取值區(qū)間為[-4,0],步長為0.5.

實(shí)驗(yàn)結(jié)果如表3～表11所示,并且為了直觀化,本文算法在10個(gè)數(shù)據(jù)集上的測試代價(jià)約簡比率如圖1所示.

(a)Arrhythmia (b)Person

表3 δ=-4時(shí)本文算法在10個(gè)數(shù)據(jù)集上的指標(biāo)值對比

表4 δ=-3.5時(shí)本文算法在10個(gè)數(shù)據(jù)集上的指標(biāo)值對比

表5 δ=-3時(shí)本文算法在10個(gè)數(shù)據(jù)集上的指標(biāo)值對比

表6 δ=-2.5時(shí)本文算法在10個(gè)數(shù)據(jù)集上的指標(biāo)值對比

表7 δ=-2時(shí)本文算法在10個(gè)數(shù)據(jù)集上的指標(biāo)值對比

表8 δ=-1.5時(shí)本文算法在10個(gè)數(shù)據(jù)集上的指標(biāo)值對比

表9 δ=-1時(shí)本文算法在10個(gè)數(shù)據(jù)集上的指標(biāo)值對比

表10 δ=-0.5時(shí)本文算法在10個(gè)數(shù)據(jù)集上的指標(biāo)值對比

表11 δ=0時(shí)本文算法在10個(gè)數(shù)據(jù)集上的指標(biāo)值對比

由表3～表11和圖1可以看出,相比δ=0時(shí),本文算法在δ<0時(shí)得到的總測試代價(jià)具有較大優(yōu)勢,考慮測試代價(jià)時(shí)所得的屬性子集和尺度對應(yīng)的總測試代價(jià)更低,即測試代價(jià)約簡比率更小,并且數(shù)據(jù)集越大,優(yōu)勢越明顯.同時(shí),算法能得到較低的屬性約簡比率,即使在δ<0時(shí)比在δ=0時(shí)多考慮測試代價(jià),實(shí)驗(yàn)結(jié)果中兩種情況下的運(yùn)行時(shí)間和屬性約簡比率相差卻不大,δ<0時(shí)有些屬性約簡比率甚至小于δ=0時(shí).

事實(shí)上,本文算法不只是進(jìn)行屬性約簡,約簡后的每個(gè)屬性都選擇相同的尺度,相比原始的多尺度決策系統(tǒng),數(shù)據(jù)結(jié)構(gòu)得到很大程度的精簡.此外,在每個(gè)δ下算法都具有較高的計(jì)算效率,并且δ取值在[-1.5,-0.5]時(shí)的TTC和測試代價(jià)約簡比率小于其它取值時(shí),所以可以縮減δ的取值范圍,從而進(jìn)一步減小算法的計(jì)算復(fù)雜度.因此在下文的對比實(shí)驗(yàn)中,本文算法δ的取值范圍將縮減至[-1.5,-0.5].

為了更客觀地評價(jià)本文算法,本文選取文獻(xiàn)[18]算法、文獻(xiàn)[19]算法以及最細(xì)尺度的原數(shù)據(jù)(簡稱為FIN)進(jìn)行實(shí)驗(yàn)對比.文獻(xiàn)[18]算法基于多尺度鄰域信息粒,同時(shí)進(jìn)行最優(yōu)尺度選擇和特征選擇.文獻(xiàn)[19]算法結(jié)合辨識矩陣與圖論,同步選擇屬性與尺度.

在對比實(shí)驗(yàn)中,分別對比各算法的總測試代價(jià)、測試代價(jià)約簡比率、屬性約簡比率以及在兩個(gè)分類器(SVM、CART決策樹)下的分類精度.還對比除了FIN以外的3種算法的運(yùn)行時(shí)間,具體結(jié)果如表12所示.表中黑體數(shù)字表示總測試代價(jià)、運(yùn)行時(shí)間的最優(yōu)結(jié)果.

表12 各算法在7個(gè)數(shù)據(jù)集上的指標(biāo)值對比

為了節(jié)省篇幅,表中僅列舉7個(gè)代表性數(shù)據(jù)集的對比結(jié)果.

從表12中可以看出,本文算法在5個(gè)數(shù)據(jù)集上的總測試代價(jià)最小,剩下兩個(gè)數(shù)據(jù)集雖然不是最小值,但差距不大,同時(shí)本文算法的運(yùn)行時(shí)間和在兩個(gè)分類器下的分類精度都是最優(yōu)值.從實(shí)驗(yàn)中可發(fā)現(xiàn),本文算法在大多數(shù)數(shù)據(jù)集上所得總測試代價(jià)都小于對比算法.本文算法主要目的是使總測試代價(jià)最小化,然而從表12最后兩列可以明顯看出,本文算法所得結(jié)果在兩個(gè)分類器下的分類精度與對比算法分類精度相差不大.并且從表中運(yùn)行時(shí)間可知,本文算法在所有數(shù)據(jù)集上的運(yùn)行時(shí)間最短,數(shù)據(jù)集越大優(yōu)勢越明顯.綜上所述,本文算法可以大幅縮減總測試代價(jià),并且算法的運(yùn)行時(shí)間較短.

4 結(jié) 束 語

為了選擇合適的屬性子集和尺度,使協(xié)調(diào)的多尺度決策系統(tǒng)的分辨能力不變,并且總測試代價(jià)最小,本文提出基于測試代價(jià)的屬性與尺度同步選擇方法.構(gòu)建多尺度決策系統(tǒng)的粗糙集理論模型,充分討論相關(guān)知識,并設(shè)計(jì)同步選擇的啟發(fā)式算法,實(shí)驗(yàn)結(jié)果驗(yàn)證算法的有效性和實(shí)用性.后續(xù)將進(jìn)一步研究新的測試代價(jià)敏感的屬性與尺度同步選擇方法,使不同的屬性可以選擇不同的尺度.此外,不止針對協(xié)調(diào)的多尺度決策系統(tǒng),未來還將本文方法應(yīng)用于不協(xié)調(diào)的多尺度決策系統(tǒng),從而使方法能更廣泛地應(yīng)用于現(xiàn)實(shí).