王蕾晰 吳偉志 謝禎晃

大數(shù)據(jù)時(shí)代下,各行各業(yè)產(chǎn)生的數(shù)據(jù)具有不確定性和復(fù)雜性.高效處理數(shù)據(jù),挖掘數(shù)據(jù)背后的規(guī)律,并運(yùn)用于實(shí)際問題是數(shù)據(jù)挖掘的主要任務(wù).粒計(jì)算[1-3]是模擬人腦思維以處理數(shù)據(jù)不確定性和復(fù)雜性的一種方法,源于Zadeh[4]提出的“信息粒度”概念.粒計(jì)算的核心思想是通過合適的?；崛⌒畔⒘?對(duì)信息粒進(jìn)行處理和計(jì)算,進(jìn)而分析數(shù)據(jù)規(guī)律和解決實(shí)際問題[5-7].

在粒計(jì)算的研究和發(fā)展過程中,粗糙集數(shù)據(jù)分析發(fā)揮重要的作用.粗糙集最早由Pawlak[8]于1982年提出.粗糙集最初討論的對(duì)象-屬性取值多為數(shù)值或符號(hào).隨著數(shù)據(jù)挖掘的不斷深入和實(shí)際應(yīng)用的需要,學(xué)者們研究數(shù)據(jù)類型日趨多樣化,如集值、區(qū)間值、區(qū)間集、模糊數(shù)、混合數(shù)據(jù)類型等.

多重集[9-11]是一種元素可重復(fù)出現(xiàn)的集合,元素在多重集中出現(xiàn)的次數(shù)稱為該元素在多重集中的重?cái)?shù)并且元素的順序可以互換.多重集在組合數(shù)學(xué)[12]、關(guān)系數(shù)據(jù)庫(kù)理論[13]、圖論[14]等領(lǐng)域都有重要應(yīng)用.可以使用多重集描述決策分析中很多問題的數(shù)據(jù).例如,在專家評(píng)審系統(tǒng)中,有4位專家參與評(píng)審,專家評(píng)審結(jié)果可能存在重復(fù),如多重集{well,well,well,bad}中的元素分別為4位專家的評(píng)審結(jié)果.如果用經(jīng)典集合{well,bad}則無法體現(xiàn)專家對(duì)評(píng)審對(duì)象的具體評(píng)價(jià).此外,多重集在模式識(shí)別[15-16]、多準(zhǔn)則決策[17]、醫(yī)療診斷[18]等領(lǐng)域也有重要應(yīng)用.

當(dāng)信息系統(tǒng)的對(duì)象-屬性取值為多重集時(shí),該系統(tǒng)稱為多重集值信息系統(tǒng),多重集值信息系統(tǒng)是集值信息系統(tǒng)的推廣.多重集值信息系統(tǒng)在決策分析[19-21]、多源信息融合[22-23]等領(lǐng)域具有重要的研究?jī)r(jià)值.Zhao等[19]在多重集值信息系統(tǒng)中建立決策理論粗糙集模型.王虹等[20]結(jié)合多粒度粗糙集和模糊決策論,研究在多重集值信息系統(tǒng)中樂觀與悲觀粗糙集的上、下近似的性質(zhì),并討論粗糙集精度與粗度等問題.Zhang等[22]探索多重集值信息系統(tǒng)在多源信息融合領(lǐng)域的重要應(yīng)用.Huang等[23]利用多重集值信息系統(tǒng),解決在多源信息融合時(shí)產(chǎn)生的信息缺省問題,從粒計(jì)算的角度給出多重集值信息系統(tǒng)中的信息結(jié)構(gòu),并研究其在不確定度量中的應(yīng)用.

眾所周知,經(jīng)典粗糙集數(shù)據(jù)分析處理系統(tǒng)為單尺度信息系統(tǒng),即系統(tǒng)中每個(gè)對(duì)象在每個(gè)屬性下只能取唯一的值.但在實(shí)際應(yīng)用中,對(duì)象屬性的取值可以具有多種尺度的值,如成績(jī)的評(píng)定,有百分制、五級(jí)記分制或二級(jí)記分制.生活中存在許多類似的多尺度屬性的例子,尺度過細(xì)會(huì)導(dǎo)致數(shù)據(jù)的存儲(chǔ)代價(jià)過大,而尺度過粗又會(huì)導(dǎo)致決策的準(zhǔn)確性降低.因此,在不同決策問題中可能會(huì)采用不同的屬性尺度.針對(duì)類似問題,Wu等[24]首次提出多尺度粗糙集數(shù)據(jù)分析模型,處理的數(shù)據(jù)稱為多尺度信息系統(tǒng),這種系統(tǒng)中每個(gè)屬性對(duì)于同個(gè)對(duì)象具有不同尺度的取值,并且在不同的尺度之間存在粒度變換的關(guān)系.

近年來,多尺度粗糙集數(shù)據(jù)分析已成為粒計(jì)算領(lǐng)域的一個(gè)重要方向[25-29].陳應(yīng)生等[25]建立多尺度覆蓋決策系統(tǒng)模型,并使用布爾矩陣研究系統(tǒng)的粒描述.Zhan等[26]利用多尺度信息系統(tǒng)與多專家群體決策系統(tǒng)的關(guān)系,研究排序決策問題.陳艷等[27]提出多尺度集值信息系統(tǒng)的概念,給出系統(tǒng)在不同尺度下的粗糙近似.但多尺度集值信息系統(tǒng)無法處理屬性的取值為多重集的情形.

信息熵是刻畫信息系統(tǒng)不確定性的重要指標(biāo)之一,熵的概念最早來源于熱力學(xué)理論,由Shannon[30]引入信息論中.信息熵越大,系統(tǒng)的不確定程度越高.在保持信息熵不變的情況下,即在保持系統(tǒng)不確定性不變的情況下找到原系統(tǒng)的最優(yōu)尺度和屬性約簡(jiǎn),是多尺度數(shù)據(jù)分析研究的一個(gè)重要問題[31-32].張嘉宇[31]研究條件熵和互補(bǔ)熵在多尺度信息系統(tǒng)中的最優(yōu)尺度選擇問題,并類比兩種方法的效果.鄭嘉文等[32]利用香農(nóng)熵,研究多尺度信息系統(tǒng)中的最優(yōu)尺度選擇問題,并證明最優(yōu)尺度與熵最優(yōu)尺度的等價(jià)性,但香農(nóng)熵建立在由等價(jià)關(guān)系產(chǎn)生的劃分上.Liang等[33-34]引入在相似關(guān)系下知識(shí)粗糙熵的概念,并運(yùn)用于不完備系統(tǒng)的知識(shí)表示與知識(shí)約簡(jiǎn)中.之后,Liang等[35]討論不完備信息系統(tǒng)中的信息熵、粗糙熵和知識(shí)粒化之間的關(guān)系.Sun等[36]基于粗糙熵構(gòu)造低計(jì)算復(fù)雜度的啟發(fā)式算法.Ma等[37]研究雙論域上概率粗糙集的知識(shí)粒度和粗糙熵的不確定度量.鄧切等[38]討論雙論域覆蓋空間中的粗糙熵與知識(shí)粒度等問題.

針對(duì)現(xiàn)有的信息系統(tǒng)難以體現(xiàn)和處理數(shù)據(jù)融合時(shí)出現(xiàn)的數(shù)據(jù)重復(fù)問題,本文提出多尺度多重集值信息系統(tǒng)的概念,并討論該系統(tǒng)的最優(yōu)尺度選擇和屬性約簡(jiǎn)問題.首先,在多尺度多重集值信息系統(tǒng)的每個(gè)屬性中,基于屬性值域中多重集之間的海林格距離(Hellinger Distance)定義論域上的相似關(guān)系,并獲得由每個(gè)屬性子集導(dǎo)出的論域中所有對(duì)象的相似類構(gòu)成的信息粒.然后,引入多尺度多重集值信息系統(tǒng)中知識(shí)粗糙熵的概念,并進(jìn)一步給出多尺度多重集值信息系統(tǒng)中的最優(yōu)尺度與熵最優(yōu)尺度的概念,證明基于相似關(guān)系定義的最優(yōu)尺度和基于知識(shí)粗糙熵定義的最優(yōu)尺度是等價(jià)的.最后,在熵最優(yōu)尺度的基礎(chǔ)上提出系統(tǒng)中基于相似關(guān)系的約簡(jiǎn)和基于知識(shí)粗糙熵的約簡(jiǎn)的概念,并分別給出篩選熵最優(yōu)尺度和熵約簡(jiǎn)的算法.

1 基礎(chǔ)知識(shí)

本節(jié)介紹相關(guān)的基礎(chǔ)知識(shí),包括多重集、信息系統(tǒng)、多重集值信息系統(tǒng)、多尺度信息系統(tǒng)和熵的概念與基本性質(zhì).

定義1[9]設(shè)Z={z1,z2,…,zo}為一個(gè)非空有限集合,N為自然數(shù)集合,稱M為集合Z上的一個(gè)多重集,若Z中的元素zi(zi∈Z)在M中重復(fù)出現(xiàn)ki次,即

則M稱為Z上的一個(gè)多重集.

由定義1可見,一個(gè)多重集M可由函數(shù)CM∶Z→N表示,即

其中

CM(zi)=ki,zi∈Z.

由多重集的定義可知,多重集中元素的順序無關(guān)緊要.集合Z上所有多重集的集合記為M(Z),若集合Z的冪集記為P(Z),則

P(Z)?M(Z),

故多重集是經(jīng)典集的推廣.

一個(gè)多重集M的基數(shù)記為|M|,定義如下:

例1在專家評(píng)審系統(tǒng)中,每篇論文的評(píng)審結(jié)果由3位專家共同給出.假設(shè)每位專家的意見只可能有2種情況——接受(a)和拒絕(r).那么所有評(píng)審結(jié)果M都是多重集,且M∈M(Z),其中Z={a,r}.若3位專家中有2位專家給出接受的意見,1位專家給出拒絕的意見,則評(píng)審結(jié)果為

M={a,a,r},

也可以表示為

文獻(xiàn)[23]引入概率論中的海林格距離以定義多重集之間的距離.

定義2[23]對(duì)于Z={z1,z2,…,zo}上的兩個(gè)多重集M1∈M(Z),M2∈M(Z),M1和M2之間的海林格距離定義為

其中

有時(shí),一個(gè)多重集M也可以表示為

其中

例2多重集

M1={a,a,r,r},M2={a,r,r,r}

可以寫成

而M1和M2之間的海林格距離

定義3[8]稱S=(U,A)為一個(gè)信息系統(tǒng),其中

U={x1,x2,…,xn}

為非空有限對(duì)象集,稱為論域,

A={a1,a2,…,am}

為非空有限屬性集,對(duì)于

?aj∈A,aj∶U→Vj,

其中Vj為屬性aj的值域.

若信息系統(tǒng)中存在對(duì)象有未知的或缺省的屬性值,則稱該信息系統(tǒng)為不完備信息系統(tǒng),此時(shí),用符號(hào)*表示不完備信息系統(tǒng)中的缺省值.

定義4[19]稱S=(U,A)為一個(gè)多重集值信息系統(tǒng),其中

U={x1,x2,…,xn}

為非空有限對(duì)象集,稱為論域,

A={a1,a2,…,am}

為非空有限屬性集,每個(gè)對(duì)象的屬性取值都為多重集,即

?aj∈A,aj∶U→M(Vj),

其中Vj為屬性aj的值域.

針對(duì)對(duì)象的屬性可能存在多種尺度的情況,Wu等[24]首次提出多尺度信息系統(tǒng)的概念.

定義5[24]稱S=(U,A)為一個(gè)多尺度信息系統(tǒng),其中

U={x1,x2,…,xn}

為論域,

A={a1,a2,…,am}

為非空有限屬性集,每個(gè)屬性都具有多尺度.假設(shè)所有屬性的尺度個(gè)數(shù)都是I,則一個(gè)多尺度信息系統(tǒng)可以表示為

其中

使得

即

對(duì)于k=1,2,…,I,記

則一個(gè)多尺度信息系統(tǒng)S=(U,A)可以分解為I個(gè)子信息系統(tǒng)

Sk=(U,Ak),k=1,2,…,I.

定義6[39]稱S=(U,A)為一個(gè)多尺度集值信息系統(tǒng),其中

U={x1,x2,…,xn}

為論域,

A={a1,a2,…,am}

為非空有限屬性集,每個(gè)屬性都具有多尺度,且尺度個(gè)數(shù)都是I,每個(gè)對(duì)象的屬性取值都為集值.

非空有限集合U的冪集記為P(U),設(shè)

C={C1,C2,…,Ce}?P(U),

若??C,且

則稱C為U的一個(gè)覆蓋.進(jìn)一步,若

Ci∩Cj=?,i≠j,

i∈{1,2,…,e},j∈{1,2,…,e},

則稱C為U的一個(gè)劃分.

定義7[40]設(shè)U是非空有限集合,

X={X1,X2,…,Xt}, Y={Y1,Y2,…,Ys}

為U上的兩個(gè)覆蓋,若對(duì)于?Xi∈X,都存在Yj∈Y,使得Xi?Yj,則稱X細(xì)于Y,或稱Y粗于X,記作X?Y.另外,若進(jìn)一步存在Xi0∈X,Yj0∈Y,使得Xi0?Yj0,則稱X嚴(yán)格細(xì)于Y,或稱Y嚴(yán)格粗于X,記作XY.

定義8[28]設(shè)U為非空有限集合,若

X={X1,X2,…,Xt}

為U上的一個(gè)劃分,則X的信息(香農(nóng))熵H(X)定義為

其中

|·|表示集合的基數(shù).

命題1[41]設(shè)U為非空有限集合,對(duì)于U上兩個(gè)劃分X和Y,若滿足X?Y,則H(X)≥H(Y).

對(duì)于一個(gè)不完備信息系統(tǒng)(U,A),由任一屬性子集B產(chǎn)生的相似關(guān)系定義為

RB={(x,y)∈U×U|aj(x)=aj(y)∨

aj(x)=*∨aj(y)=*,?aj∈B}.

相似關(guān)系RB將論域U?；癁槿舾上嗨祁?/p>

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

其中

[x]B={y∈U|(x,y)∈RB}.

顯然,相似類全體U/RB構(gòu)成論域U的一個(gè)覆蓋.

香農(nóng)熵是定義在等價(jià)關(guān)系上的,但在相似關(guān)系上并不適用.為此,Liang等[33-34]在不完備信息系統(tǒng)中提出在相似關(guān)系下的知識(shí)粗糙熵的概念.

定義9[33]設(shè)(U,A)為一個(gè)不完備信息系統(tǒng),B?A,屬性集B的知識(shí)粗糙熵定義為

性質(zhì)1[33]設(shè)(U,A)為一個(gè)不完備信息系統(tǒng),B?A,C?A.若

U/RBU/RC,

則

E(B)

性質(zhì)2[33]設(shè)(U,A)為一個(gè)不完備信息系統(tǒng),B?A,則

U/RB=U/RA

當(dāng)且僅當(dāng)

E(B)=E(A).

2 多尺度多重集值信息系統(tǒng)

定義10稱S=(U,A)為一個(gè)多尺度多重集值信息系統(tǒng),其中

U={x1,x2,…,xn}

為非空有限對(duì)象集,稱為論域,

A={a1,a2,…,am}

為非空有限屬性集,每個(gè)屬性都具有多尺度且每個(gè)對(duì)象的屬性取值都為多重集.假設(shè)所有屬性的尺度個(gè)數(shù)都是I,則一個(gè)多尺度多重集值信息系統(tǒng)可以表示為

其中

使得

即

對(duì)于k=1,2,…,I,記

則一個(gè)多尺度多重集值信息系統(tǒng)S=(U,A)可以分解為I個(gè)多重集值信息系統(tǒng)

Sk=(U,Ak),k=1,2,…,I.

在多源信息融合問題中,數(shù)據(jù)來自于多個(gè)信息源,其等級(jí)尺度和屬性總量影響數(shù)據(jù)融合過程的效率和數(shù)據(jù)融合后信息系統(tǒng)的數(shù)據(jù)量,因此篩選合適的屬性尺度和屬性在實(shí)際應(yīng)用中具有研究意義.同時(shí),多重集值信息系統(tǒng)能夠有效應(yīng)對(duì)信息融合時(shí)容易出現(xiàn)的數(shù)據(jù)重復(fù)情況.

例3是一個(gè)手機(jī)質(zhì)檢問題,也是多源信息融合問題.不同檢測(cè)員表示不同信息源,將對(duì)不同品牌手機(jī)的檢測(cè)結(jié)果融合到一個(gè)信息系統(tǒng)中.

例3設(shè)

U={x1,x2,…,x8}

為論域,分別表示8個(gè)手機(jī)品牌,

A={a1,a2,a3}

為屬性集,多尺度多重集值信息系統(tǒng)如表1所示.

表1 一個(gè)多尺度多重集值信息系統(tǒng)Table 1 A multi-scale multiset-valued information system

表1中,屬性a1為4名檢測(cè)員對(duì)抽檢手機(jī)的處理器性能評(píng)分,屬性a2為4名檢測(cè)員對(duì)抽檢手機(jī)的使用流暢度評(píng)分,屬性a3為4名檢測(cè)員使用抽檢手機(jī)相同時(shí)間后所剩的電池容量,每個(gè)屬性的尺度個(gè)數(shù)都是2.

表1是一個(gè)多尺度多重集值信息系統(tǒng)

其屬性在不同尺度標(biāo)記之間的粒度變換為

根據(jù)定義2中的多重集之間的海林格距離,定義多尺度多重集值信息系統(tǒng)上對(duì)象的屬性值之間的相似度.

定義11設(shè)

為一個(gè)多尺度多重集值信息系統(tǒng),對(duì)于?x∈U,y∈U,在屬性aj的第k個(gè)尺度標(biāo)記下的相似度為

命題2定義11的相似性度量SIM滿足如下性質(zhì),對(duì)于?M∈M(Z),M1∈M(Z),M2∈M(Z),其中Z={z1,z2,…,zo},

1)SIM(M,M)=1,

2)SIM(M1,M2)=SIM(M2,M1),

3)SIM(M1,M2)=1?M1=M2.

證明1)和2)顯然成立,只需證明3).充分性的證明是顯然的,下面證明必要性.

若

SIM(M1,M2)=1,

設(shè)

則

于是

由H?lder不等式可知

又

故

由H?lder不等式等號(hào)成立條件可得

pi=qi,i=1,2,…,o,

即M1=M2.

證畢

命題3設(shè)

為一個(gè)多尺度多重集值信息系統(tǒng),對(duì)于?x∈U,y∈U,在屬性aj下的相似度關(guān)于尺度具有單調(diào)性,即對(duì)于k∈{1,2,…,I-1},有

其中

設(shè)

τ1∈{1,2,…,o+1},

τ2∈{1,2,…,o+1},

?

τl+1∈{1,2,…,o+1},

其中

1=τ1<τ2<…<τl<τl+1=o+1,

使得

其中

τγ≤λ<τγ+1,γ=1,2,…,l.

由此可得

由H?lder不等式進(jìn)一步可得

可知

故

得證

證畢

例4(續(xù)例3) 對(duì)于例3中的多尺度多重集值信息系統(tǒng)中的數(shù)據(jù),通過定義11給出的相似度,可以計(jì)算每個(gè)屬性在各個(gè)尺度標(biāo)記下的相似度矩陣,如表2～表7所示.

表2 屬性a1在第1個(gè)尺度標(biāo)記下的相似度矩陣Table 2 Similarity matrix of attribute a1 under the first scale

表3 屬性a1在第2個(gè)尺度標(biāo)記下的相似度矩陣Table 3 Similarity matrix of attribute a1 under the second scale

表4 屬性a2在第1個(gè)尺度標(biāo)記下的相似度矩陣Table 4 Similarity matrix of attribute a2 under the first scale

表5 屬性a2在第2個(gè)尺度標(biāo)記下的相似度矩陣Table 5 Similarity matrix of attribute a2under the second scale

表6 屬性a3在第1個(gè)尺度標(biāo)記下的相似度矩陣Table 6 Similarity matrix of attribute a3 under the first scale

表7 屬性a3在第2個(gè)尺度標(biāo)記下的相似度矩陣Table 7 Similarity matrix of attribute a3under the second scale

在一個(gè)多尺度多重集值信息系統(tǒng)S=(U,A)中,當(dāng)閾值α∈(0,1]時(shí),屬性aj在第k個(gè)尺度標(biāo)記下的相似關(guān)系定義為

例5(續(xù)例4) 當(dāng)閾值α=0.95時(shí),屬性a1在第1個(gè)尺度標(biāo)記下的相似關(guān)系:

屬性a1在第2個(gè)尺度標(biāo)記下的相似關(guān)系:

屬性a2在第1個(gè)尺度標(biāo)記下的相似關(guān)系:

屬性a2在第2個(gè)尺度標(biāo)記下的相似關(guān)系:

屬性a3在第1個(gè)尺度標(biāo)記下的相似關(guān)系:

屬性a3在第2個(gè)尺度標(biāo)記下的相似關(guān)系:

命題4設(shè)

為一個(gè)多尺度多重集值信息系統(tǒng),當(dāng)閾值α∈(0,1]時(shí),對(duì)于?aj∈A,k∈{1,2,…,I-1},

成立.

成立.由命題3可知,有

因此得

即

從而

證畢

其中

且

在一個(gè)多尺度多重集值信息系統(tǒng)S=(U,A)中,當(dāng)閾值α∈(0,1]時(shí),屬性子集B?A在第k個(gè)尺度標(biāo)記下的相似關(guān)系定義為

顯然

其中,

且

命題5設(shè)

為一個(gè)多尺度多重集值信息系統(tǒng),B?A,當(dāng)閾值α∈(0,1]時(shí),

從而對(duì)

有

又因?yàn)?/p>

則

所以

因此

又由于

證畢

類比定義9中定義在不完備信息系統(tǒng)的相似關(guān)系下的知識(shí)粗糙熵,本文在多尺度多重集值信息系統(tǒng)的相似關(guān)系下給出知識(shí)粗糙熵的定義.

定義12設(shè)

為一個(gè)多尺度多重集值信息系統(tǒng),B?A.當(dāng)閾值α∈(0,1]時(shí),對(duì)于k∈{1,2,…,I},屬性集B在第k個(gè)尺度標(biāo)記下的知識(shí)粗糙熵定義為

性質(zhì)3設(shè)

為一個(gè)多尺度多重集值信息系統(tǒng),B?A,C?A.當(dāng)閾值α∈(0,1]時(shí),對(duì)于k∈{1,2,…,I},若

則

Eα(Ck)≤Eα(Bk).

證明對(duì)于閾值α∈(0,1],k∈{1,2,…,I},若

則由定義7可知,對(duì)于?x∈U,有

于是

成立.由xlog2x在[1,+∞)有單調(diào)性,有

即

因此

Eα(Ck)≤Eα(Bk).

證畢

性質(zhì)3說明在閾值α∈(0,1]的情況下,對(duì)于每個(gè)尺度標(biāo)記,若兩個(gè)屬性集生成的覆蓋具有粗細(xì)關(guān)系,則兩個(gè)屬性集對(duì)應(yīng)的知識(shí)粗糙熵滿足對(duì)應(yīng)的大小關(guān)系.對(duì)應(yīng)于覆蓋越粗的屬性集,其知識(shí)粗糙熵越大.

推論1設(shè)

為一個(gè)多尺度多重集值信息系統(tǒng),B?A.當(dāng)閾值α∈(0,1]時(shí),對(duì)于k∈{1,2,…,I},則

Eα(Ak)≤Eα(Bk).

性質(zhì)4設(shè)

為一個(gè)多尺度多重集值信息系統(tǒng),B?A.當(dāng)閾值α∈(0,1]時(shí),對(duì)于k∈{1,2,…,I},則

當(dāng)且僅當(dāng)

Eα(Ak)=Eα(Bk).

證明先證必要性,對(duì)于閾值α∈(0,1]和k∈{1,2,…,I},若

則

由知識(shí)粗糙熵的定義可知

Eα(Ak)=Eα(Bk).

再證充分性.只需證明對(duì)于閾值α∈(0,1]和k∈{1,2,…,I},

若

Eα(Ak)=Eα(Bk),

則

對(duì)于閾值α∈(0,1]和k∈{1,2,…,I},由

Eα(Ak)=Eα(Bk)

和知識(shí)粗糙熵的定義可知

可化簡(jiǎn)為

因?yàn)?/p>

即對(duì)于?x∈U,有

從而相似類的基數(shù)滿足

由函數(shù)xlog2x在[1,+∞)上的單調(diào)性,可得

進(jìn)而有

否則

矛盾.又因?yàn)?/p>

故

得證

證畢

性質(zhì)5設(shè)

為一個(gè)多尺度多重集值信息系統(tǒng),B?A.當(dāng)閾值α∈(0,1]時(shí),則對(duì)于1≤k≤l≤I,有

Eα(Bk)≤Eα(Bl).

證明由命題5可知,對(duì)于閾值α∈(0,1]和1≤k≤l≤I,有

即

則由定義7可知,對(duì)于?x∈U,有

于是

成立.由xlog2x在[1,+∞)有單調(diào)性,故

即

因此

Eα(Bk)≤Eα(Bl)

成立.

證畢

性質(zhì)6設(shè)

為一個(gè)多尺度多重集值信息系統(tǒng),B?A.當(dāng)閾值α∈(0,1]時(shí),對(duì)于1≤k≤l≤I,

當(dāng)且僅當(dāng)

Eα(Bk)=Eα(Bl).

證明先證必要性.對(duì)于閾值α∈(0,1]和1≤k≤l≤I,若

則

由知識(shí)粗糙熵的定義可知

Eα(Bk)=Eα(Bl).

再證充分性.只需證明對(duì)于閾值α∈(0,1]和1≤k≤l≤I,若

Eα(Bk)=Eα(Bl),

則

對(duì)于閾值α∈(0,1]和1≤k≤l≤I,由

Eα(Bk)=Eα(Bl)

和知識(shí)粗糙熵的定義可知

可化簡(jiǎn)為

由命題5可知,對(duì)于1≤k≤l≤I,有

即對(duì)于?x∈U,有

從而

又由函數(shù)xlog2x在[1,+∞)上的單調(diào)性,可得

進(jìn)而有

否則

矛盾.又因?yàn)?/p>

故

得證

證畢

3 最優(yōu)尺度選擇和屬性約簡(jiǎn)

本節(jié)主要討論多尺度多重集值信息系統(tǒng)基于知識(shí)粗糙熵的熵最優(yōu)尺度選擇和熵約簡(jiǎn)的問題,首先給出多尺度多重集值信息系統(tǒng)中最優(yōu)尺度和熵最優(yōu)尺度的概念,再給出約簡(jiǎn)和熵約簡(jiǎn)的概念.

定義13設(shè)

為一個(gè)多尺度多重集值信息系統(tǒng),對(duì)于閾值α∈(0,1]和第k個(gè)尺度標(biāo)記(k∈{1,2,…,I}),若

則稱Sk關(guān)于S是α-協(xié)調(diào)的.若進(jìn)一步有

則稱k為S的α-最優(yōu)尺度.

定義14設(shè)

為一個(gè)多尺度多重集值信息系統(tǒng),對(duì)于閾值α∈(0,1]和第k個(gè)尺度標(biāo)記(k∈{1,2,…,I}),若

Eα(Ak)=Eα(A1),

則稱Sk關(guān)于S是α-熵協(xié)調(diào)的.若進(jìn)一步有

Eα(Ak+1)≠Eα(A1), k+1≤I,

則稱k為S的α-熵最優(yōu)尺度.

例6(續(xù)例5) 當(dāng)閾值α=0.95時(shí),

故

從而S2關(guān)于S是α-協(xié)調(diào)的.又由于

Eα(A1)=0, Eα(A2)=0,

即

Eα(A2)=Eα(A1),

因此S2關(guān)于S也是α-熵協(xié)調(diào)的.

當(dāng)閾值α′=0.8時(shí),

故

從而S2關(guān)于S不是α′-協(xié)調(diào)的.又由于

即

Eα′(A2)≠Eα′(A1),

因此S2關(guān)于S也不是α′-熵協(xié)調(diào)的.

綜上所述,當(dāng)閾值α=0.95時(shí),系統(tǒng)S的α-最優(yōu)尺度和α-熵最優(yōu)尺度都為2,但當(dāng)閾值α′=0.8時(shí),系統(tǒng)S的α′-最優(yōu)尺度和α′-熵最優(yōu)尺度都為1.

定理1設(shè)

為一個(gè)多尺度多重集值信息系統(tǒng),對(duì)于閾值α∈(0,1]和k∈{1,2,…,I},則Sk關(guān)于S是α-協(xié)調(diào)的當(dāng)且僅當(dāng)Sk關(guān)于S是α-熵協(xié)調(diào)的.

證明根據(jù)定義13,若Sk關(guān)于S是α-協(xié)調(diào)的,則

成立,從而

而由定義14和Sk關(guān)于S是α-熵協(xié)調(diào)的,可知

Eα(Ak)=Eα(A1).

因此,只需證明

是等價(jià)的.由性質(zhì)6可得兩者的等價(jià)性成立,即Sk關(guān)于S是α-協(xié)調(diào)的當(dāng)且僅當(dāng)Sk關(guān)于S是α-熵協(xié)調(diào)的.

證畢

定理1說明多尺度多重集值信息系統(tǒng)的α-協(xié)調(diào)和α-熵協(xié)調(diào)是等價(jià)的,由定理1可直接得到定理2.

定理2設(shè)

為一個(gè)多尺度多重集值信息系統(tǒng),對(duì)于閾值α∈(0,1]和k∈{1,2,…,I},則k是S的α-最優(yōu)尺度當(dāng)且僅當(dāng)k是S的α-熵最優(yōu)尺度.

定義15設(shè)

則稱B是S在α-最優(yōu)尺度k下的一個(gè)α-約簡(jiǎn).

定義16設(shè)

為一個(gè)多尺度多重集值信息系統(tǒng),對(duì)于閾值α∈(0,1]和S的α-熵最優(yōu)尺度k,當(dāng)B?A時(shí),若

Eα(Bk)=Eα(A1),

則稱B是S在α-熵最優(yōu)尺度k下的一個(gè)α-熵協(xié)調(diào)集.若進(jìn)一步對(duì)于?b∈B,都有

Eα(Bk-{bk})≠Eα(A1),

則稱B是S在α-熵最優(yōu)尺度k下的一個(gè)α-熵約簡(jiǎn).

例7(續(xù)例6) 當(dāng)閾值α=0.95時(shí),在α-最優(yōu)尺度2的情況下,

顯然有

同時(shí)

成立.因此在α-最優(yōu)尺度2下多尺度多重集值信息系統(tǒng)的α-約簡(jiǎn)為{a2,a3}和{a1,a3}.又因?yàn)?/p>

因此,在α-熵最優(yōu)尺度2下多尺度多重集值信息系統(tǒng)的α-熵約簡(jiǎn)為{a2,a3}和{a1,a3}.

定理3設(shè)

為一個(gè)多尺度多重集值信息系統(tǒng),對(duì)于閾值α,當(dāng)B?A時(shí),則B是S在α-最優(yōu)尺度k下的一個(gè)α-約簡(jiǎn)當(dāng)且僅當(dāng)B是S在α-熵最優(yōu)尺度k下的一個(gè)α-熵約簡(jiǎn).

證明先證必要性.由于B是S在α-最優(yōu)尺度k下的一個(gè)α-約簡(jiǎn),因此

且?b∈B,都有

對(duì)于閾值α和S的α-最優(yōu)尺度k,由α-最優(yōu)尺度的定義可知

從而

又由性質(zhì)4的證明可知,有

Eα(Bk)=Eα(Ak).

同時(shí)由定理2得k也是α-熵最優(yōu)尺度,從而

Eα(Ak)=Eα(A1),

因此

Eα(Bk)=Eα(A1).

若對(duì)于?b∈B,都有

則

由于k是α-最優(yōu)尺度,因此

即

由性質(zhì)4的逆否命題可知

Eα(Bk-{bk})≠Eα(Ak).

同時(shí)由k也是α-熵最優(yōu)尺度可知

Eα(Ak)=Eα(A1),

從而

Eα(Bk-{bk})≠Eα(A1).

故B是S在α-熵最優(yōu)尺度k下的一個(gè)α-熵約簡(jiǎn).

再證充分性.由于B是S在α-熵最優(yōu)尺度k下的一個(gè)α-熵約簡(jiǎn),因此

Eα(Bk)=Eα(A1),

且?b∈B,都有

Eα(Bk-{bk})≠Eα(A1).

對(duì)于閾值α和S的α-熵最優(yōu)尺度k,由α-熵最優(yōu)尺度的定義可知

Eα(Ak)=Eα(A1),

從而

Eα(Bk)=Eα(Ak).

又由性質(zhì)4的證明可知,有

同時(shí)由定理2得k也是α-最優(yōu)尺度,從而

因此

若對(duì)于?b∈B,都有

Eα(Bk-{bk})≠Eα(A1)

成立,由于k是α-熵最優(yōu)尺度,因此

Eα(Ak)=Eα(A1),

即

Eα(Bk-{bk})≠Eα(Ak).

又由性質(zhì)4的逆否命題可知

同時(shí)由k也是α-最優(yōu)尺度可知

從而

即

故B是S在α-最優(yōu)尺度k下的一個(gè)α-約簡(jiǎn).

證畢

定理3說明多尺度多重集值信息系統(tǒng)的α-約簡(jiǎn)和α-熵約簡(jiǎn)是等價(jià)的.

接下來,基于知識(shí)粗糙熵給出計(jì)算α-熵最優(yōu)尺度和α-熵約簡(jiǎn)的算法,算法1是基于知識(shí)粗糙熵計(jì)算α-熵最優(yōu)尺度的算法,算法2是基于知識(shí)粗糙熵計(jì)算α-熵約簡(jiǎn)的算法.兩種算法流程圖如圖1和圖2所示.

圖1 算法1流程圖Fig.1 Flow chart of Algorithm 1

圖2 算法2流程圖Fig.2 Flow chart of Algorithm 2

算法1基于知識(shí)粗糙熵的最優(yōu)尺度算法

輸入I個(gè)尺度的多尺度多重集值信息系統(tǒng)(U,A),閾值α∈(0,1]

輸出α-熵最優(yōu)尺度k*

1.初始化k*←1,k←1

2.whilek≠Ido

4.計(jì)算對(duì)象兩兩之間的相似性

5.end for

6. for eachx∈Udo

8.end for

9.求第k個(gè)尺度標(biāo)記下的知識(shí)粗糙熵Eα(Ak)

10.ifEα(Ak)>Eα(A1) then

11.k*←k-1

12.break

13. end if

14.k←k+1

15.end while

在算法1中,步驟3～5用于計(jì)算對(duì)象間的相似度,時(shí)間復(fù)雜度為O(mn2),其中m表示屬性個(gè)數(shù),n表示對(duì)象個(gè)數(shù).步驟6～8用于計(jì)算每個(gè)對(duì)象的相似類,時(shí)間復(fù)雜度為O(n).因?yàn)樗惴?最多需要考慮I個(gè)尺度,因此算法1的時(shí)間復(fù)雜度為O(Imn2),其中I表示系統(tǒng)的尺度標(biāo)記個(gè)數(shù).

算法2基于知識(shí)粗糙熵的屬性約簡(jiǎn)算法

輸入I個(gè)尺度的多尺度多重集值信息系統(tǒng)(U,A),閾值α∈(0,1],α-熵最優(yōu)尺度k

輸出α-熵約簡(jiǎn)B

1.求最細(xì)尺度標(biāo)記下知識(shí)粗糙熵Eα(A1)

2.初始化B←?,Ck←Ak

4.計(jì)算對(duì)象兩兩之間的相似性

5.end for

7. for eachx∈Udo

9.end for

11.end for

14.B←Ck

15.else

17.return 6

18.end if

即為O(m2n).所以算法2的時(shí)間復(fù)雜度為

O(mn2+m2n).

4 結(jié) 束 語

多尺度信息系統(tǒng)中的最優(yōu)尺度的選擇和基于最優(yōu)尺度的屬性約簡(jiǎn)是多尺度數(shù)據(jù)分析研究的關(guān)鍵問題,迄今尚未見到屬性取值為多重集且具有多個(gè)尺度的信息系統(tǒng)的數(shù)據(jù)分析研究.本文將多重集引入多尺度信息系統(tǒng),提出多尺度多重集值信息系統(tǒng)的概念,基于海林格距離的相似度在論域上構(gòu)造對(duì)應(yīng)于任一屬性子集的相似類,定義基于相似關(guān)系和基于知識(shí)粗糙熵的最優(yōu)尺度概念,并證明兩者是等價(jià)的,在最優(yōu)尺度的基礎(chǔ)上提出α-約簡(jiǎn)和α-熵約簡(jiǎn)的概念,并給出計(jì)算α-熵最優(yōu)尺度和α-熵約簡(jiǎn)算法.由于文中定義的相似度在處理尺度較細(xì)的屬性時(shí),相似度變化不均勻,影響模型的穩(wěn)定性和魯棒性,因此所能應(yīng)用的問題存在一定的局限性,在后續(xù)的研究中需進(jìn)一步改進(jìn).另外,多尺度多重集值決策系統(tǒng)的最優(yōu)尺度選擇和知識(shí)獲取是有待繼續(xù)探討的課題,包括廣義多尺度多重集值決策系統(tǒng)和不完備多尺度多重集值決策系統(tǒng)的知識(shí)獲取問題.