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

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

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

粒計(jì)算模擬人類思考問題的自然模式，是知識表示和問題求解的重要工具之一，已成為大數(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)的劃分來?；瘮?shù)據(jù)的樣本空間，用“?！贝鏄颖緦?shù)據(jù)進(jìn)行處理，并通過計(jì)算所定義的約簡（使得矛盾樣本集不改變的極小特征（屬性）集合）對數(shù)據(jù)集進(jìn)行特征提取，最終獲取聚類或分類規(guī)則或排序決策.

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

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

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

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

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

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

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

從粒計(jì)算的角度來看，等價(jià)類[x]B是由屬性集B確定的不可分辨元素組成的粒，屬性集B將U粒化為不相交的粒族U/RB，它們是近似U的任意子集的基本元素（信息粒）.

決策系統(tǒng)，也稱為決策信息系統(tǒng)，是一個(gè)二元組S=(U，C∪j5i0abt0b)，其中(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∪j5i0abt0b)是協(xié)調(diào)的，否則稱S是不協(xié)調(diào)的.

1.2 劃分與信息熵

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

注1對于信息系統(tǒng)(U，A)，若B?A且X 是由等價(jià)關(guān)系RB產(chǎn)生的劃分，則用H(B)來代替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 相對于劃分X 的條件熵記為H(Y |X)，定義如下：

注2對于信息系統(tǒng)(U，A)，若B，C?A且Y和X 是分別由等價(jià)關(guān)系RB和RC產(chǎn)生的劃分，則用H(B|C)來代替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)中，對象的特征是每個(gè)屬性都有一個(gè)惟一的值.而在許多實(shí)際應(yīng)用中，一個(gè)對象在同一屬性下根據(jù)不同的尺度標(biāo)記層面可能具有不同的值.

定義5［7］稱二元組S=(U，A)為一個(gè)多尺度信息系統(tǒng)，其中U={x1，x2，…，xn}為一個(gè)非空有限對象集，稱為論域，A={a1，a2，…，am}為一個(gè)非空有限屬性集，每個(gè)aj∈A都是多尺度屬性，即對于U中的每個(gè)對象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)尺度選擇

對于一個(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∪j5i0abt0b)關(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)中，對于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)，對于k∈{1，2，…，I}，則k是S的廣義決策最優(yōu)尺度當(dāng)且僅當(dāng)以下條件成立：

4 總結(jié)

多尺度信息系統(tǒng)與多尺度決策系統(tǒng)的最優(yōu)尺度選擇問題是多尺度數(shù)據(jù)分析的一個(gè)關(guān)鍵問題.本文用信息熵討論多尺度信息系統(tǒng)的最優(yōu)尺度選擇問題，定義多尺度信息系統(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ù)的知識獲取奠定了理論基礎(chǔ)，下一步將進(jìn)一步研究各種復(fù)雜多尺度信息系統(tǒng)基于信息熵的最優(yōu)尺度選擇與知識獲取問題.