基于熵的多尺度決策系統的最優尺度選擇

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

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

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

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

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

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

1 相關的基礎知識

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

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

定義1一個信息系統為一個二元組(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導出的不可分辨關系，它將U?；癁椴豢蓞^分集合其中[x]B是對象x∈U關于屬性B的等價類，即[x]B={y∈U|(x，y) ∈RB}.

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

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

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

如果RC?Rd，那么稱決策系統S=(U，C∪g0gggggg)是協調的，否則稱S是不協調的.

1.2 劃分與信息熵

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

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

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

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

定義3設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］設U為一個非空有限集合，X={X1，X2，…，Xt}，Y={Y1，Y2，…，Yl}是U上的兩個劃分，若則H(X) ≥H(Y).

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

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

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

2 多尺度信息系統和多尺度決策系統

本節回顧多尺度信息系統和多尺度決策系統的概念.

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

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

若多尺度決策系統S在第一個（最細）尺度下的決策系統

是協調的，則稱S是協調的，否則稱S是不協調的.

3 基于信息熵的多尺度信息系統的最優尺度選擇

本節給出多尺度信息系統和協調多尺度決策系統中最優尺度與熵最優尺度的概念，并論證兩者是等價關系.而在不協調多尺度決策系統中，運用廣義決策和熵廣義決策建立信息熵與最優尺度之間的關系，并證明廣義決策最優尺度和熵廣義決策最優尺度之間是等價關系.

3.1 多尺度信息系統中的最優尺度選擇

定義7設：為一個具有I個尺度的多尺度信息系統，k∈{1，2，…，I}，則：

（1）若RAk=RA1，則稱Sk=(U，Ak)關于S是協調的.若Sk關于S是協調的，且Sk+1（若k+1≤I）關于S是不協調的，則k稱為S的最優尺度.

（2）若H(Ak)=H(A1)，則稱Sk=(U，Ak)關于S是熵協調的.若Sk關于S是熵協調的，且Sk+1（若k+1≤I）關于S不是熵協調的，則k稱為S的熵最優尺度.

定理1設：為一個具有I個尺度的多尺度信息系統，k∈{1，2，…，I}，則：

（1）Sk關于S是協調的當且僅當Sk關于S是熵協調的；

（2）k是S的最優尺度當且僅當k是S的熵最優尺度.

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

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

表1 一個多尺度信息系統Table 1 A multi-scale information system

因為H(A2)=H(A1)，所以S2關于S是協調的，而H(A3) ＜H(A2)，所以k=2 是S的熵最優尺度.又因為RA1=RA2≠RA3，顯然k=2 又是S的最優尺度.

3.2 協調多尺度決策系統中的最優尺度選擇

對于一個協調多尺度決策系統：

為一個具有I個尺度的協調多尺度決策系統，k∈{1，2，…，I}.若Sk是協調的且Sk+1（若k+1≤I）是不協調的，則稱k為S的最優尺度.

根據定義8 可以看到，協調多尺度決策系統的最優尺度是多尺度系統中進行決策或分類的最優尺度.k為最優尺度當且僅當k是使得Sk是協調決策系統的最大值.

定義9設：

為一個具有I個尺度的協調多尺度決策系統，k∈{1，2，…，I}.若H(d|Ck)=H(d|C1)，則稱Sk=(U，Ck∪g0gggggg)關于S是熵協調的.若Sk關于S是熵協調的，且Sk+（1若k+1≤I）關于S不是熵協調的，則稱k是S的熵最優尺度.

定理3設：

為一個具有I個尺度的協調多尺度決策系統，k∈{1，2，…，I}，則：

（1）Sk是協調的當且僅當Sk關于S是熵協調的；

（2）k是S的最優尺度當且僅當k是S的熵最優尺度.

證 明

（1）設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是協調的.

（2）由（1）即得.

定理4設：

為一個具有I個尺度的協調多尺度決策系統，k∈{1，2，…，I}.則k是S的最優尺度當且僅當以下條件成立：

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

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

證 明由定理3 即得.

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

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

表2 一個多尺度決策系統Table 2 A multi-scale decision system

因為H(d|C2)=H(d|C1)=0，所以S2關于S是熵協調的，而H(d|C3) ＞0，因此k=2 是S的熵最優尺度.又因為RC2?Rd，RC3?Rd，因此k=2 也是S的最優尺度.

3.3 不協調多尺度決策系統的最優尺度選擇

則：

（2）若H(d|Ck)=H(d|C1)，則稱Sk關于S是熵協調的.若Sk關于S是熵協調的，而Sk+1（如果k+1≤I）關于S不是熵協調的，則k稱為S的熵最優尺度.

在具有I個尺度的不協調多尺度決策系統中，對于k∈{1，2，…，I}，

是不協調決策系統.顯然，Sk關于S是廣義決策協調的當且僅當Sk保持與第一個尺度（最細尺度）下決策系統S1具有相同的廣義決策值.k是S的廣義決策最優尺度當且僅當k是使得Sk保持與S1有相同的廣義決策值的最大數.

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

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

表3 一個多尺度決策系統Table 3 A multi-scale decision table

因為H(d|C2) ≠H(d|C1)，所以k=1 是S的熵最優尺度.由表可知1，…，8，所以k=2 是S的廣義決策最優尺度.由此，在不協調多尺度決策系統中，廣義決策最優尺度與熵最優尺度是不等價的.

定理5設：

為具有I個尺度的不協調多尺度決策系統，k∈{1，2，…，I}，則：

(1)Sk關于S是廣義決策協調的當且僅當Sk關于S是廣義決策熵協調的；

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

證 明（1）記：

則S?是一個協調的多尺度決策系統.又記=是協調的決策系統，因此Sk關于不協調多尺度決策系統S是廣義決策協調的當且僅當關于協調多尺度決策系統S?是協調的，由定理3 知，結論（1）成立.

（2）由（1）可得.

定理6設：

為一個具有I個尺度的不協調多尺度決策系統，對于k∈{1，2，…，I}，則k是S的廣義決策最優尺度當且僅當以下條件成立：

4 總結

多尺度信息系統與多尺度決策系統的最優尺度選擇問題是多尺度數據分析的一個關鍵問題.本文用信息熵討論多尺度信息系統的最優尺度選擇問題，定義多尺度信息系統、協調多尺度決策系統、不協調多尺度決策系統基于信息熵的最優尺度概念，證明在多尺度信息系統和協調多尺度決策系統中熵最優尺度與傳統最優尺度是等價的，但在不協調多尺度決策系統中兩者是不等價的.在不協調多尺度決策系統中，廣義決策最優尺度與廣義決策熵最優尺度是等價的.這為進一步基于信息熵的多尺度數據的知識獲取奠定了理論基礎，下一步將進一步研究各種復雜多尺度信息系統基于信息熵的最優尺度選擇與知識獲取問題.