鄭嘉文 ,吳偉志,2* ,包 菡 ,譚安輝,2

（1.浙江海洋大學(xué)數(shù)理與信息學(xué)院，舟山，316022；2.浙江省海洋大數(shù)據(jù)挖掘與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，浙江海洋大學(xué)，舟山，316022）

粒計(jì)算模擬人類思考問(wèn)題的自然模式，是知識(shí)表示和問(wèn)題求解的重要工具之一，已成為大數(shù)據(jù)與智能信息處理領(lǐng)域的一個(gè)重要研究方向［1-5］.

在眾多的粒計(jì)算模型中，粗糙集數(shù)據(jù)分析在推動(dòng)與發(fā)展粒計(jì)算研究中發(fā)揮了重要作用.粗糙集數(shù)據(jù)分析中處理的數(shù)據(jù)集稱為信息系統(tǒng)［6］，又稱為信息表或?qū)ο?屬性值表.原始的Pawlak 粗糙集理論利用信息系統(tǒng)給出數(shù)據(jù)集的訓(xùn)練樣本上的等價(jià)類描述“粒度”，用等價(jià)關(guān)系誘導(dǎo)的劃分來(lái)?；瘮?shù)據(jù)的樣本空間，用“?！贝鏄颖緦?duì)數(shù)據(jù)進(jìn)行處理，并通過(guò)計(jì)算所定義的約簡(jiǎn)（使得矛盾樣本集不改變的極小特征（屬性）集合）對(duì)數(shù)據(jù)集進(jìn)行特征提取，最終獲取聚類或分類規(guī)則或排序決策.

傳統(tǒng)的粗糙集數(shù)據(jù)分析呈現(xiàn)的信息系統(tǒng)中每個(gè)對(duì)象與對(duì)應(yīng)的屬性只取惟一的一個(gè)值，這樣的信息系統(tǒng)反映的是固定尺度下的對(duì)象信息，稱為單尺度信息系統(tǒng).在實(shí)際生活中人們可能要在不同粒度或尺度下對(duì)同一對(duì)象在同一屬性或變量下對(duì)系統(tǒng)中的數(shù)據(jù)進(jìn)行分析.為此，Wu and Leung［7］提出多尺度數(shù)據(jù)的粒計(jì)算分析模型，數(shù)據(jù)表的表示形式稱為多尺度信息系統(tǒng)，又稱多尺度信息表，這個(gè)數(shù)據(jù)處理模型稱為Wu-Leung 模型［8］.這種數(shù)據(jù)處理的主要思想是：根據(jù)決策目標(biāo)對(duì)所有屬性選擇同一層面的尺度或者粒度構(gòu)成一個(gè)新的單尺度信息系統(tǒng)，然后在保持相同目標(biāo)約束的前提下進(jìn)行屬性約簡(jiǎn)（特征選擇）、決策規(guī)則提取及相應(yīng)的不確定性分析.在這個(gè)模型中在保持某種性質(zhì)（可以是定性的，也可以是定量的）一致的意義下選擇最粗的尺度標(biāo)記（稱為最優(yōu)尺度選擇或最優(yōu)粒度選擇）成為在多尺度決策數(shù)據(jù)中提取決策規(guī)則前的一個(gè)關(guān)鍵問(wèn)題，因此，近年來(lái)多尺度決策信息系統(tǒng)的最優(yōu)尺度選擇研究成為多尺度數(shù)據(jù)分析的熱點(diǎn)問(wèn)題并取得了很多成果［8-24］.

眾所周知，由Shannon［25］定義的熵給出了系統(tǒng)結(jié)構(gòu)的不確定性度量，可以用于描述各種不確定性環(huán)境下的信息內(nèi)容.這種信息熵也已經(jīng)成為刻畫粗糙集數(shù)據(jù)分析中信息系統(tǒng)的知識(shí)不確定性的一種重要工具［25-31］.迄今為止，將信息熵引入多尺度信息系統(tǒng)的知識(shí)表示與知識(shí)獲取問(wèn)題中的不確定性研究幾乎還是空白，本文首次將Shannon 定義的熵用于多尺度信息系統(tǒng)中的最優(yōu)尺度選擇問(wèn)題，主要討論基于熵的最優(yōu)尺度選擇與傳統(tǒng)的最優(yōu)尺度選擇之間的關(guān)系.

1 相關(guān)的基礎(chǔ)知識(shí)

設(shè)U是非空集合，U的子集全體記為P(U)，對(duì)于X∈P(U)用～X表示X在U中的補(bǔ)集，即：

1.1 信息表與近似集信息系統(tǒng)（有時(shí)稱為信息表、數(shù)據(jù)表、對(duì)象屬性值系統(tǒng)、知識(shí)表示系統(tǒng)等）的概念為對(duì)象屬性值的表示提供了方便的工具.

定義1一個(gè)信息系統(tǒng)為一個(gè)二元組(U，A)，其中U={x1，x2，…，xn}為一個(gè)非空有限對(duì)象集，稱為論域，A={a1，a2，…，am}為一個(gè)非空有限屬性集，使得?a∈A，滿足a：U→Va，即a(x) ∈Va，x∈U，其中Va={a(x)|x∈U}稱為a的值域.

對(duì)于任意非空子集B?A，記RB={(x，y)∈U×U|a(x)=a(y)，?a∈B}.RB稱為由屬性B導(dǎo)出的不可分辨關(guān)系，它將U?；癁椴豢蓞^(qū)分集合其中[x]B是對(duì)象x∈U關(guān)于屬性B的等價(jià)類，即[x]B={y∈U|(x，y) ∈RB}.

從粒計(jì)算的角度來(lái)看，等價(jià)類[x]B是由屬性集B確定的不可分辨元素組成的粒，屬性集B將U?；癁椴幌嘟坏牧Ｗ錟/RB，它們是近似U的任意子集的基本元素（信息粒）.

決策系統(tǒng)，也稱為決策信息系統(tǒng)，是一個(gè)二元組S=(U，C∪syggg00)，其中(U，C)是一個(gè)信息系統(tǒng)，C稱為條件屬性集，d?C是一個(gè)特殊的屬性，稱為決策屬性，可以看作映射d：U→Vd.不失一般性，假設(shè)Vd={1，2，…，r}，由決策屬性d確定U上的等價(jià)關(guān)系：

它可以把U劃分成不相交的決策類：

如果RC?Rd，那么稱決策系統(tǒng)S=(U，C∪syggg00)是協(xié)調(diào)的，否則稱S是不協(xié)調(diào)的.

1.2 劃分與信息熵

定義2設(shè)U為一個(gè)非空有限集合，X={X1，X2，…，Xt}是U上的一個(gè)劃分.X 的信息熵記為H(X)，定義如下：

注1對(duì)于信息系統(tǒng)(U，A)，若B?A且X 是由等價(jià)關(guān)系RB產(chǎn)生的劃分，則用H(B)來(lái)代替H(X).

命題1［27］設(shè)(U，A)為一個(gè)信息系統(tǒng)，且B，C?A.若RB=RC，則H(B)=H(C).

命題2［27］設(shè)(U，A) 為一個(gè)信息系統(tǒng)且B，C?A.若RB?RC且H(B)=H(C)，則RB=RC.

定義3設(shè)U為一個(gè)非空有限集合，X 和Y 是U上的兩個(gè)劃分.若?X∈X，?Y∈Y，使得X?Y，則稱X 細(xì)于Y，或稱Y 粗于X，記為另外，若進(jìn)一步?X∈X，?Y∈Y，使得X?Y，則稱X 嚴(yán)格細(xì)于Y，記為X ?Y.

命題3［28］設(shè)U為一個(gè)非空有限集合，X={X1，X2，…，Xt}，Y={Y1，Y2，…，Yl}是U上的兩個(gè)劃分，若則H(X) ≥H(Y).

定義4設(shè)U為一個(gè)非空有限集合，X={X1，X2，…，Xt}，Y={Y1，Y2，…，Yl}是U上的兩個(gè)劃分.劃分Y 相對(duì)于劃分X 的條件熵記為H(Y |X)，定義如下：

注2對(duì)于信息系統(tǒng)(U，A)，若B，C?A且Y和X 是分別由等價(jià)關(guān)系RB和RC產(chǎn)生的劃分，則用H(B|C)來(lái)代替H(Y |X).

命題4設(shè)U為一個(gè)非空有限集合，X，Y，Z是U上的三個(gè)劃分，則：

2 多尺度信息系統(tǒng)和多尺度決策系統(tǒng)

本節(jié)回顧多尺度信息系統(tǒng)和多尺度決策系統(tǒng)的概念.

在Pawlak 信息系統(tǒng)中，對(duì)象的特征是每個(gè)屬性都有一個(gè)惟一的值.而在許多實(shí)際應(yīng)用中，一個(gè)對(duì)象在同一屬性下根據(jù)不同的尺度標(biāo)記層面可能具有不同的值.

定義5［7］稱二元組S=(U，A)為一個(gè)多尺度信息系統(tǒng)，其中U={x1，x2，…，xn}為一個(gè)非空有限對(duì)象集，稱為論域，A={a1，a2，…，am}為一個(gè)非空有限屬性集，每個(gè)aj∈A都是多尺度屬性，即對(duì)于U中的每個(gè)對(duì)象xi，屬性值aj(xi)可以在不同尺度上呈現(xiàn)不同的值.

若多尺度決策系統(tǒng)S在第一個(gè)（最細(xì)）尺度下的決策系統(tǒng)

是協(xié)調(diào)的，則稱S是協(xié)調(diào)的，否則稱S是不協(xié)調(diào)的.

3 基于信息熵的多尺度信息系統(tǒng)的最優(yōu)尺度選擇

本節(jié)給出多尺度信息系統(tǒng)和協(xié)調(diào)多尺度決策系統(tǒng)中最優(yōu)尺度與熵最優(yōu)尺度的概念，并論證兩者是等價(jià)關(guān)系.而在不協(xié)調(diào)多尺度決策系統(tǒng)中，運(yùn)用廣義決策和熵廣義決策建立信息熵與最優(yōu)尺度之間的關(guān)系，并證明廣義決策最優(yōu)尺度和熵廣義決策最優(yōu)尺度之間是等價(jià)關(guān)系.

3.1 多尺度信息系統(tǒng)中的最優(yōu)尺度選擇

定義7設(shè)：為一個(gè)具有I個(gè)尺度的多尺度信息系統(tǒng)，k∈{1，2，…，I}，則：

（1）若RAk=RA1，則稱Sk=(U，Ak)關(guān)于S是協(xié)調(diào)的.若Sk關(guān)于S是協(xié)調(diào)的，且Sk+1（若k+1≤I）關(guān)于S是不協(xié)調(diào)的，則k稱為S的最優(yōu)尺度.

（2）若H(Ak)=H(A1)，則稱Sk=(U，Ak)關(guān)于S是熵協(xié)調(diào)的.若Sk關(guān)于S是熵協(xié)調(diào)的，且Sk+1（若k+1≤I）關(guān)于S不是熵協(xié)調(diào)的，則k稱為S的熵最優(yōu)尺度.

定理1設(shè)：為一個(gè)具有I個(gè)尺度的多尺度信息系統(tǒng)，k∈{1，2，…，I}，則：

（1）Sk關(guān)于S是協(xié)調(diào)的當(dāng)且僅當(dāng)Sk關(guān)于S是熵協(xié)調(diào)的；

（2）k是S的最優(yōu)尺度當(dāng)且僅當(dāng)k是S的熵最優(yōu)尺度.

例1表1 為一個(gè)具有三個(gè)尺度和兩個(gè)屬性的多尺度信息系統(tǒng).

其中U={x1，x2，…，x6}，A={a1，a2}，E 表示非常好，G 表示好，F(xiàn) 表示一般，B 表示差，S 表示小，M 表示中，L 表示大.

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

因?yàn)镠(A2)=H(A1)，所以S2關(guān)于S是協(xié)調(diào)的，而H(A3) ＜H(A2)，所以k=2 是S的熵最優(yōu)尺度.又因?yàn)镽A1=RA2≠RA3，顯然k=2 又是S的最優(yōu)尺度.

3.2 協(xié)調(diào)多尺度決策系統(tǒng)中的最優(yōu)尺度選擇

對(duì)于一個(gè)協(xié)調(diào)多尺度決策系統(tǒng)：

為一個(gè)具有I個(gè)尺度的協(xié)調(diào)多尺度決策系統(tǒng)，k∈{1，2，…，I}.若Sk是協(xié)調(diào)的且Sk+1（若k+1≤I）是不協(xié)調(diào)的，則稱k為S的最優(yōu)尺度.

根據(jù)定義8 可以看到，協(xié)調(diào)多尺度決策系統(tǒng)的最優(yōu)尺度是多尺度系統(tǒng)中進(jìn)行決策或分類的最優(yōu)尺度.k為最優(yōu)尺度當(dāng)且僅當(dāng)k是使得Sk是協(xié)調(diào)決策系統(tǒng)的最大值.

定義9設(shè)：

為一個(gè)具有I個(gè)尺度的協(xié)調(diào)多尺度決策系統(tǒng)，k∈{1，2，…，I}.若H(d|Ck)=H(d|C1)，則稱Sk=(U，Ck∪syggg00)關(guān)于S是熵協(xié)調(diào)的.若Sk關(guān)于S是熵協(xié)調(diào)的，且Sk+（1若k+1≤I）關(guān)于S不是熵協(xié)調(diào)的，則稱k是S的熵最優(yōu)尺度.

定理3設(shè)：

為一個(gè)具有I個(gè)尺度的協(xié)調(diào)多尺度決策系統(tǒng)，k∈{1，2，…，I}，則：

（1）Sk是協(xié)調(diào)的當(dāng)且僅當(dāng)Sk關(guān)于S是熵協(xié)調(diào)的；

（2）k是S的最優(yōu)尺度當(dāng)且僅當(dāng)k是S的熵最優(yōu)尺度.

證 明

（1）設(shè)Ck，C1和d在U上的劃分分別為：

U/RCk={X1,X2,…,Xt}

U/RC1={Y1,Y2,…,Yl}

U/Rd={Z1,Z2,…,Zr}

這與H(d|Ck)=H(d|C1)矛盾，所以Sk是協(xié)調(diào)的.

（2）由（1）即得.

定理4設(shè)：

為一個(gè)具有I個(gè)尺度的協(xié)調(diào)多尺度決策系統(tǒng)，k∈{1，2，…，I}.則k是S的最優(yōu)尺度當(dāng)且僅當(dāng)以下條件成立：

（1）H(d|Ck)=0.

（2）H(d|Ck+1) ＞0（若k+1≤I）.

證 明由定理3 即得.

例2表2 為一個(gè)具有三個(gè)尺度和兩個(gè)屬性的多尺度決策系統(tǒng)：

其中，U={x1，x2，…，x8}，C={a1，a2}，G 表示好，F(xiàn) 表示一般，B 表示差，S 表示小，L 表示大.

表2 一個(gè)多尺度決策系統(tǒng)Table 2 A multi-scale decision system

因?yàn)镠(d|C2)=H(d|C1)=0，所以S2關(guān)于S是熵協(xié)調(diào)的，而H(d|C3) ＞0，因此k=2 是S的熵最優(yōu)尺度.又因?yàn)镽C2?Rd，RC3?Rd，因此k=2 也是S的最優(yōu)尺度.

3.3 不協(xié)調(diào)多尺度決策系統(tǒng)的最優(yōu)尺度選擇

則：

（2）若H(d|Ck)=H(d|C1)，則稱Sk關(guān)于S是熵協(xié)調(diào)的.若Sk關(guān)于S是熵協(xié)調(diào)的，而Sk+1（如果k+1≤I）關(guān)于S不是熵協(xié)調(diào)的，則k稱為S的熵最優(yōu)尺度.

在具有I個(gè)尺度的不協(xié)調(diào)多尺度決策系統(tǒng)中，對(duì)于k∈{1，2，…，I}，

是不協(xié)調(diào)決策系統(tǒng).顯然，Sk關(guān)于S是廣義決策協(xié)調(diào)的當(dāng)且僅當(dāng)Sk保持與第一個(gè)尺度（最細(xì)尺度）下決策系統(tǒng)S1具有相同的廣義決策值.k是S的廣義決策最優(yōu)尺度當(dāng)且僅當(dāng)k是使得Sk保持與S1有相同的廣義決策值的最大數(shù).

例3表3 為一個(gè)具有兩個(gè)尺度和兩個(gè)屬性的多尺度決策系統(tǒng)：

其中U={x1，x2，…，x8}，C={a1，a2}，B 表示差，F(xiàn) 表示一般，G 表示好，Y 表示是，N 表示否.

表3 一個(gè)多尺度決策系統(tǒng)Table 3 A multi-scale decision table

因?yàn)镠(d|C2) ≠H(d|C1)，所以k=1 是S的熵最優(yōu)尺度.由表可知1，…，8，所以k=2 是S的廣義決策最優(yōu)尺度.由此，在不協(xié)調(diào)多尺度決策系統(tǒng)中，廣義決策最優(yōu)尺度與熵最優(yōu)尺度是不等價(jià)的.

定理5設(shè)：

為具有I個(gè)尺度的不協(xié)調(diào)多尺度決策系統(tǒng)，k∈{1，2，…，I}，則：

(1)Sk關(guān)于S是廣義決策協(xié)調(diào)的當(dāng)且僅當(dāng)Sk關(guān)于S是廣義決策熵協(xié)調(diào)的；

（2）k是S的廣義決策最優(yōu)尺度當(dāng)且僅當(dāng)k是S的廣義決策熵最優(yōu)尺度.

證 明（1）記：

則S?是一個(gè)協(xié)調(diào)的多尺度決策系統(tǒng).又記=是協(xié)調(diào)的決策系統(tǒng)，因此Sk關(guān)于不協(xié)調(diào)多尺度決策系統(tǒng)S是廣義決策協(xié)調(diào)的當(dāng)且僅當(dāng)關(guān)于協(xié)調(diào)多尺度決策系統(tǒng)S?是協(xié)調(diào)的，由定理3 知，結(jié)論（1）成立.

（2）由（1）可得.

定理6設(shè)：

為一個(gè)具有I個(gè)尺度的不協(xié)調(diào)多尺度決策系統(tǒng)，對(duì)于k∈{1，2，…，I}，則k是S的廣義決策最優(yōu)尺度當(dāng)且僅當(dāng)以下條件成立：

4 總結(jié)

多尺度信息系統(tǒng)與多尺度決策系統(tǒng)的最優(yōu)尺度選擇問(wèn)題是多尺度數(shù)據(jù)分析的一個(gè)關(guān)鍵問(wèn)題.本文用信息熵討論多尺度信息系統(tǒng)的最優(yōu)尺度選擇問(wèn)題，定義多尺度信息系統(tǒng)、協(xié)調(diào)多尺度決策系統(tǒng)、不協(xié)調(diào)多尺度決策系統(tǒng)基于信息熵的最優(yōu)尺度概念，證明在多尺度信息系統(tǒng)和協(xié)調(diào)多尺度決策系統(tǒng)中熵最優(yōu)尺度與傳統(tǒng)最優(yōu)尺度是等價(jià)的，但在不協(xié)調(diào)多尺度決策系統(tǒng)中兩者是不等價(jià)的.在不協(xié)調(diào)多尺度決策系統(tǒng)中，廣義決策最優(yōu)尺度與廣義決策熵最優(yōu)尺度是等價(jià)的.這為進(jìn)一步基于信息熵的多尺度數(shù)據(jù)的知識(shí)獲取奠定了理論基礎(chǔ)，下一步將進(jìn)一步研究各種復(fù)雜多尺度信息系統(tǒng)基于信息熵的最優(yōu)尺度選擇與知識(shí)獲取問(wèn)題.