牟 瓊,程云龍,,吳成英,張清華

(1.重慶郵電大學(xué) 數(shù)理學(xué)院,重慶 400065;2.重慶郵電大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,重慶 400065;3.重慶郵電大學(xué) 計算智能重慶市重點實驗室,重慶 400065)

0 引 言

粒計算是信息處理的一種新的計算范式。美國著名控制論專家Zadeh[1]于1979年首次提出了模糊信息粒。中國張鈸院士[2]指出“人類智能的一個公認(rèn)特點就是人們能從極不相同的粒度上觀察和分析同一問題”。波蘭科學(xué)家Pawlak[3]提出的粗糙集是粒計算的一個具體模型,已被廣泛應(yīng)用于人工智能、機器學(xué)習(xí)、模式識別、數(shù)據(jù)挖掘等領(lǐng)域。

現(xiàn)實生活中,信息不完備現(xiàn)象廣泛存在。Kryszkiewicz[4]首次提出了基于容差關(guān)系的粗糙集模型以研究不完備信息系統(tǒng)。Stefanowski[5]等提出了量化容差關(guān)系,利用已知信息的相同程度去刻畫對象之間的相似程度。針對不一致不完備決策系統(tǒng),Qian等[6]提出了基于辨識矩陣的屬性約簡方法。文獻[7-10]分別研究了不完備信息系統(tǒng)中的屬性約簡。然而,上述不完備信息系統(tǒng)描述的是固定尺度下的對象信息,即每個對象在給定屬性下只能取唯一的屬性值。顯然,這種固定粒度框架下的知識挖掘方法已遠遠不能滿足實際應(yīng)用的需要。

同一個對象通常可用不同尺度來測量[11]。針對這種多尺度標(biāo)記的層次數(shù)據(jù),Wu和Leung[12]首次提出了多尺度信息系統(tǒng),被稱為Wu-Leung模型。在多尺度信息系統(tǒng)中,屬性和尺度是決定粒度大小的2個關(guān)鍵因素。由于已經(jīng)有很多經(jīng)典的算法可處理單尺度決策系統(tǒng)的屬性約簡,因而現(xiàn)有的多尺度研究更多關(guān)注最優(yōu)尺度選擇問題。例如,完備多尺度決策系統(tǒng)的最優(yōu)尺度選擇[13-14]與局部最優(yōu)尺度選擇[15],不完備多尺度決策系統(tǒng)的最優(yōu)尺度選擇[16-17]。然而,在上述多尺度決策系統(tǒng)中,所有屬性被假定具有相同的尺度個數(shù)。Li和Hu[18]假設(shè)不同屬性可以取不同的尺度個數(shù),提出了完備廣義多尺度信息系統(tǒng),并給出了2種方法求所有最優(yōu)尺度組合。針對完備廣義多尺度信息系統(tǒng),Li等[19]提出了逐步最優(yōu)尺度選擇方法,Huang等[20]研究了決策屬性為多尺度的情形,Huang等[21]研究了屬性值為直覺模糊數(shù)的情形,Zhang等[22-24]探究了尺度組合間的偏序關(guān)系及其性質(zhì),提出了求所有最優(yōu)尺度組合的三支決策模型,該模型顯著降低了現(xiàn)有算法的時間、空間復(fù)雜度。

然而,鮮有文獻研究不完備多尺度決策系統(tǒng)的最優(yōu)尺度選擇算法,且現(xiàn)有的多尺度研究方法不一定能獲得全局最優(yōu)尺度組合。該研究的主要目的是設(shè)計一個高效的、不完備廣義多尺度決策系統(tǒng)的最優(yōu)尺度組合選擇算法。首先,介紹了不完備廣義多尺度決策系統(tǒng)及其上下近似集的性質(zhì);其次,采取屬性約簡與尺度選擇同步優(yōu)化策略,定義了一個新的尺度組合,以獲得全局最優(yōu)尺度組合;最后,從提高一致性判斷效率和減少一致性判斷次數(shù)2個角度,分別設(shè)計了求相容類的快速算法和不完備廣義多尺度決策系統(tǒng)的逐步最優(yōu)尺度選擇算法。

1 基礎(chǔ)知識

(1)

設(shè)B?A,l∈{1,2,…,L},記Bl所導(dǎo)出的相容關(guān)系TBl和相容類TBl(x)分別為

TBl(x)={y|(x,y)∈TBl},x∈U。

顯然,任何一個不完備多尺度決策系統(tǒng)

可分解為L個單尺度決策系統(tǒng)

設(shè)Rd={(x,y)∈U×U|d(x)=d(y)},決策屬性d對論域U的劃分U/Rd={D1,D2,…,Dr}。若RAl?Rd,則稱Sl是一致的,否則稱為不一致。特別地,若RAI?Rd,則稱S是一致的。

定義2[17]設(shè)S=(U,A∪j5i0abt0b)為不完備多尺度決策系統(tǒng),若Sl是一致的,且當(dāng)l≥2時,Sl-1是不一致的,則l是S的最優(yōu)尺度。

表1 不完備多尺度決策系統(tǒng)

雖然,S可分解為3個單尺度決策系統(tǒng):S3,S2,S1,其中,S2如表1中陰影部分所示。由表1可知:

U/Rd={{x1,x2},{x3,x4,x5,x6,x7,x8}},

U/TA3={{x1},{x2},{x3},{x4},{x5},{x6},{x7},{x8}},U/TA2={{x1,x2},{x3},{x4},{x5},{x6,x7},{x8}},

U/TA1={{x1,x2,x3},{x1,x2,x3,x8}{x4,x6},

{x5,x6,x7},{x4,x5,x6,x7},{x3,x8}}。

U/TB={{x1,x2},{x3,x5,x6},{x4,x6},{x6,x7,x8},{x3,x4,x5,x6,x7,x8}}?U/Rd,

例1表明先由定義2得到最優(yōu)尺度,然后對最優(yōu)尺度所對應(yīng)的單尺度決策表進行屬性約簡,不一定能獲得最優(yōu)粒度。究其原因:①因為定義2要求所有屬性的尺度必須相等;②尺度選擇后屬性約簡的這種串行處理方式所致。

2 不完備廣義多尺度決策系統(tǒng)

針對不完備廣義多尺度決策系統(tǒng),本節(jié)提出一個新的尺度組合以同步優(yōu)化尺度選擇與屬性約簡。

定義4S=(U,A∪j5i0abt0b)為不完備廣義多尺度決策系統(tǒng),lj為屬性aj所選取的尺度,0≤lj≤Ij,且lj=0表示屬性aj未被選擇, 則全體屬性所選取的尺度組成的向量K=(l1,l2,…,lm)稱為S的一個尺度組合。最細尺度組合I=(I1,I2,…,Im),最粗尺度組合0=(0,0,…,0)。所有尺度組合所構(gòu)成的集合稱為尺度空間Ω,即

Ω={K=(l1,l2,…,lm)|0≤lj≤Ij,

j=1,2,…,m}。

(2)

TAK(x)={y|(x,y)∈TAK},x∈U

(3)

于是,X(X?U)關(guān)于AK的下近似和上近似分別為

(4)

(5)

且D=j5i0abt0b關(guān)于AK的正域為

(6)

由(1)—(3)式,易知如下性質(zhì)成立。

性質(zhì)1設(shè)I≥K1K20,則

1)TAI?TAK1?TAK2?TA0;

2)TAI(x)?TAK1(x)?TAK2(x)?TA0(x),x∈U。

性質(zhì)2表明,給定一個不完備廣義多尺度決策系統(tǒng),若尺度組合K逐漸變粗,則由K導(dǎo)出的相容類逐漸變大。

性質(zhì)2設(shè)S=(U,A∪j5i0abt0b)為不完備廣義多尺度決策系統(tǒng),X,Y?U,K,K1,K2∈Ω,則

顯然,對?K∈Ω,可由S=(U,A∪j5i0abt0b)導(dǎo)出一個單尺度決策系統(tǒng)SK=(U,AK∪j5i0abt0b)。若SK滿足POSAK(D)=POSAI(D),則稱SK是一致的,并稱K為一致尺度組合。若POSAK(D)=U,則稱S是一致的,否則稱S是不一致的。

由定義5,性質(zhì)4成立。

圖1 尺度格Fig.1 Scale lattice

3 逐步最優(yōu)尺度選擇

提出一個快速的相容類算法和不完備廣義多尺度決策系統(tǒng)的逐步最優(yōu)尺度選擇算法。

在不完備決策系統(tǒng)中,需要求SK的相容類以判斷SK是否一致。針對兩兩比較法求相容類存在時間復(fù)雜度高的缺陷,提出了基于排序和粒運算的相容類求法。考慮到同一個等價類中任意2個對象的相容類相等,即對?xi,xj∈[x]AK,則TAK(xi)=TAK(xj)。受此啟發(fā),首先將論域U分為不含缺失值的對象集U1和含缺失值的對象集U2;然后利用排序求U1的等價類[22],記作{X1,X2,…,Xs},并將每一個等價類標(biāo)記為一個新的對象;最后利用兩兩比較法判別U2中的對象與粒子{X1,X2,…,Xs}的相容關(guān)系,以及U2中對象間的相容關(guān)系。具體流程見算法1。

算法1基于排序與粒運算的相容類算法

輸入:單尺度決策系統(tǒng)SK=(U,AK∪j5i0abt0b)

輸出:SK的相容類Sim

Step 1:Sim←{};

Step 2:將U分解為不含缺失值的對象集U1和含缺失值的對象集U2={xj1,xj2,…,xjr};

Step 3:利用排序求U1關(guān)于AK的等價類,記

U1/RAK={X1,X2,…,Xs};

Step 4:Sim(i)←Xi,i={1,2,…,s},

Sim(s+i)←xji,i={1,2,…,r};

Step 5: 求xji∈U2的相容類

fori=1:r

Sim(u)←xji,u∈Ind;

forv=i+1:r

ifxjv與xji滿足相容關(guān)系

Sim(s+i)←xjv;

Sim(s+v)←xji;

end

end

end

Step 6: 輸出Sim

例2(續(xù)例1) 設(shè)K=(1,0,2),根據(jù)表1可知,U1={x1,x2,x4,x5,x7,x8},U2={x3,x6}。在K尺度下,對U1按屬性值升序排列可得U1/RAK,即

U1/RAK={{x1,x2},{x4},{x7,x8},{x5}}=

{X1,X2,X3,X4}。

于是

X1:Sim(1)={x1,x2},X2:Sim(2)={x4},

X3:Sim(3)={x7,x8},X4:Sim(4)={x5},

x3:Sim(5)={x3},x6:Sim(6)={x6}。

在K尺度下,x3=(*,3)與粒子X4,與對象x6滿足相容關(guān)系,故將X4中的對象以及對象x6添加到Sim(5)中,即Sim(5)={x3,x5,x6}。同時,相容關(guān)系的對稱性有Sim(4)={x5,x3},Sim(6)={x6,x3}。

同理,x6=(4,*)與粒子X2,X3,X4相容,故Sim(6)={x6,x3,x4,x7,x8,x5},Sim(2)={x4,x6},Sim(3)={x7,x8,x6},Sim(4)={x5,x3,x6}。

因此,由AK導(dǎo)出的相容類為

Sim(1)={x1,x2},Sim(2)={x4,x6},

Sim(3)={x7,x8,x6},Sim(4)=Sim(5)={x5,x3,x6},Sim(6)={x6,x3,x4,x7,x8,x5}。

算法1的時間復(fù)雜度分析:步驟2的時間復(fù)雜度為O(m|U|),其中|·|表示集合的基數(shù);步驟3的時間復(fù)雜度為O(m|U1|);由于|Xi|<<|U1|,故步驟5的時間復(fù)雜度近似為O(m|U2|2);其余步驟的時間復(fù)雜度為常數(shù)。因此,算法1的時間復(fù)雜度為O(m(|U|+|U2|2))。通常|U2|<|U|,故算法1的時間復(fù)雜度低于兩兩比較的時間復(fù)雜度O(m|U|2)。

當(dāng)屬性或尺度個數(shù)遞增時,尺度組合個數(shù)將急劇增加。針對該情形,Li等[19]提出了逐步最優(yōu)尺度選擇算法求完備多尺度決策系統(tǒng)在Ω+上的最優(yōu)尺度組合。然而,在計算多尺度屬性重要度時,需要計算每一個屬性在每一個尺度下的重要度,對高維數(shù)據(jù)情形,存在耗時較高的缺陷。同時,若屬性在最細尺度下的重要度較小,則該屬性在粗尺度下的重要度更小。因此,可用最細尺度組合下的屬性重要度代替多尺度屬性重要度。

設(shè)S=(U,A∪j5i0abt0b)為不完備廣義多尺度決策系統(tǒng),Kj=(I1,…,Ij-1,0,Ij+1,…,Im),定義屬性aj在S中的重要度為

sig(aj,A,D)=γAI(D)-γAKj(D),

(7)

不完備廣義多尺度決策系統(tǒng)的逐步最優(yōu)尺度選擇算法見算法2。

例3詳細說明了算法2的具體流程。

例3(續(xù)例1)屬性a1,a2,a3的重要度分別為

因此,屬性排列順序為(a2,a1,a3)。

令K=I=(3,3,3)。

算法2不完備廣義多尺度決策系統(tǒng)的逐步最優(yōu)尺度選擇

輸入:不完備多尺度決策系統(tǒng)S=(U,A∪j5i0abt0b)

輸出:最優(yōu)尺度組合(optimal scale combination,OSC)

Step1:根據(jù)(6)式,計算屬性重要度,并按升序排列,不妨假設(shè)為(aj1,aj2,…,ajm);

Step2:K←I=(I1,I2,…,Im);

Step3:fori=1:m%m為屬性個數(shù)

K(ji)←0,%令屬性aji的尺度為零;

whileK(ji)

ifSK一致

break;

else

K(ji)←K(ji)+1;

end

end

end

Step4:OSC←K。

首先考慮屬性a2:將K中屬性a2的尺度變?yōu)樽畲殖叨?即K=(3,0,3)。SK是一致的,故屬性a2的最優(yōu)尺度為0;

其次考慮屬性a1:將K中屬性a1的尺度變?yōu)樽畲殖叨?即K=(0,0,3)。SK是不一致的,于是屬性a1的尺度加1,即K=(1,0,3);此時,SK是一致的,故屬性a1的最優(yōu)尺度為1。

最后考慮屬性a3:將K中屬性a3的尺度變?yōu)樽畲殖叨?即K=(1,0,0)。SK是不一致的,于是屬性a3的尺度加1,即K=(1,0,1)。SK是不一致的,于是屬性a3的尺度繼續(xù)加1,即K=(1,0,2)。此時,SK是一致的,故屬性a3的最優(yōu)尺度為2。

因此,K*=K=(1,0,2)是S的最優(yōu)尺度組合。

顯然,算法2的空間復(fù)雜度為O(m|U|)。

4 數(shù)值實驗

數(shù)據(jù)集來源于UCI機器學(xué)習(xí)數(shù)據(jù)庫,數(shù)據(jù)集詳細描述如表2所示,其中數(shù)據(jù)集1-6是文獻[18-19,22-24]的實驗數(shù)據(jù)集。實驗環(huán)境為Windows XP操作系統(tǒng), Intel(R) Core(TM) i7, CPU 1.80 GHz,程序通過Matlab7.0軟件實現(xiàn)。

表2 數(shù)據(jù)集描述

數(shù)據(jù)集1-8均是單尺度決策系統(tǒng),利用Li等[19]提出的方法將單尺度決策系統(tǒng)轉(zhuǎn)換為多尺度決策系統(tǒng)。同時,數(shù)據(jù)集1-5是完備決策系統(tǒng),為了得到不完備決策系統(tǒng),采用先隨機選取對象,再隨機選取屬性和尺度的方法,將部分屬性值改為缺失值,缺失率α=0.1。

在完備信息的情形下,Zhan等[22]提出了基于三支決策和哈斯圖求所有最優(yōu)尺度組合的方法。對完備數(shù)據(jù)集1-5,算法2與文獻[22]所求得的最優(yōu)尺度組合如表3所示。由表3可看出,算法2所得到的最優(yōu)尺度組合是文獻[22]所得到的全體最優(yōu)尺度組合中的一個。數(shù)值實驗表明由算法2求得的結(jié)果是有效的。

表3 完備數(shù)據(jù)集1-5的最優(yōu)尺度組合

圖2 2種求相容類方法的運行時間Fig.2 Running time of two methodsfor finding similar classes

對數(shù)據(jù)集1-8,2種方法所得到的最優(yōu)尺度組合及其運行時間如表4所示,其中“-”表示在24小時內(nèi)未求得最優(yōu)尺度組合。

由表4可看出,大多數(shù)情形下,2種方法所得到的最優(yōu)尺度組合是不同的,L-H算法所得到的尺度之和更小。例如,對數(shù)據(jù)集1,L-H算法得到的尺度之和為12,算法2得到的尺度之和為13,而對數(shù)據(jù)集2、3、4、6,2種算法得到的尺度之和是相等的。然而,算法2的運行時間顯著低于L-H算法的運行時間,例如:對數(shù)據(jù)集4,L-H算法的運行時間是39.6 s,而算法2的運行時間是2.3 s;數(shù)據(jù)集5有4 148 928個尺度組合,L-H算法在24 h內(nèi)未得到最優(yōu)尺度組合;對數(shù)據(jù)集7和8, 運行L-H算法時,系統(tǒng)提示內(nèi)存不足。數(shù)值實驗表明,算法2能在一個可容忍的時間內(nèi)獲得一個滿意解。

表4 最優(yōu)尺度組合與運行時間

5 結(jié) 論

針對傳統(tǒng)的先尺度選擇后屬性約簡的串行處理方式有可能得不到全局最優(yōu)尺度組合的問題,提出了新的尺度組合以同步優(yōu)化尺度選擇與屬性約簡。針對缺乏高效的不完備多尺度決策系統(tǒng)的最優(yōu)尺度選擇算法問題,設(shè)計了一個高效的求相容類算法,在此基礎(chǔ)上提出了逐步最優(yōu)尺度選擇算法以快速地獲得不完備廣義多尺度決策系統(tǒng)的一個最優(yōu)尺度組合。