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

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

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

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

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

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

定義1一個信息系統(tǒng)為一個二元組(U，A)，其中U={x1，x2，…，xn}為一個非空有限對象集，稱為論域，A={a1，a2，…，am}為一個非空有限屬性集，使得?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導出的不可分辨關(guān)系，它將U?；癁椴豢蓞^(qū)分集合其中[x]B是對象x∈U關(guān)于屬性B的等價類，即[x]B={y∈U|(x，y) ∈RB}.

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

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

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

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

1.2 劃分與信息熵

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

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

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

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

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

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

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

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

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

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

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

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

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

若多尺度決策系統(tǒng)S在第一個（最細）尺度下的決策系統(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)尺度的概念，并論證兩者是等價關(guān)系.而在不協(xié)調(diào)多尺度決策系統(tǒng)中，運用廣義決策和熵廣義決策建立信息熵與最優(yōu)尺度之間的關(guān)系，并證明廣義決策最優(yōu)尺度和熵廣義決策最優(yōu)尺度之間是等價關(guān)系.

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

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

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

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

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

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

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

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

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

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

為一個具有I個尺度的協(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)中進行決策或分類的最優(yōu)尺度.k為最優(yōu)尺度當且僅當k是使得Sk是協(xié)調(diào)決策系統(tǒng)的最大值.

定義9設(shè)：

為一個具有I個尺度的協(xié)調(diào)多尺度決策系統(tǒng)，k∈{1，2，…，I}.若H(d|Ck)=H(d|C1)，則稱Sk=(U，Ck∪8easuos)關(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è)：

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

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

（2）k是S的最優(yōu)尺度當且僅當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è)：

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

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

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

證 明由定理3 即得.

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

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

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

因為H(d|C2)=H(d|C1)=0，所以S2關(guān)于S是熵協(xié)調(diào)的，而H(d|C3) ＞0，因此k=2 是S的熵最優(yōu)尺度.又因為RC2?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個尺度的不協(xié)調(diào)多尺度決策系統(tǒng)中，對于k∈{1，2，…，I}，

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

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

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

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

因為H(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)尺度是不等價的.

定理5設(shè)：

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

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

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

證 明（1）記：

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

（2）由（1）可得.

定理6設(shè)：

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

4 總結(jié)

多尺度信息系統(tǒng)與多尺度決策系統(tǒng)的最優(yōu)尺度選擇問題是多尺度數(shù)據(jù)分析的一個關(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)尺度是等價的，但在不協(xié)調(diào)多尺度決策系統(tǒng)中兩者是不等價的.在不協(xié)調(diào)多尺度決策系統(tǒng)中，廣義決策最優(yōu)尺度與廣義決策熵最優(yōu)尺度是等價的.這為進一步基于信息熵的多尺度數(shù)據(jù)的知識獲取奠定了理論基礎(chǔ)，下一步將進一步研究各種復雜多尺度信息系統(tǒng)基于信息熵的最優(yōu)尺度選擇與知識獲取問題.