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

宋茂林， 吳偉志,2

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

粒計(jì)算(granular computing，GrC)是智能信息處理領(lǐng)域中大規(guī)模復(fù)雜問題求解的有效范式，它模擬人類思考問題的自然模式，是專門研究基于粒結(jié)構(gòu)的思維方式、問題求解方法、信息處理模式的理論、方法、技術(shù)和工具的學(xué)科[1].粒計(jì)算的基本思想是在問題求解過程中從不同角度、不同層次上對現(xiàn)實(shí)問題進(jìn)行描述、推理與求解.它以粒(granule)為基本計(jì)算單位，以處理大規(guī)模復(fù)雜數(shù)據(jù)集和信息等建立有效的計(jì)算模型為目標(biāo)，以近似滿意解替代傳統(tǒng)的精確解使計(jì)算和決策更加高效.粒計(jì)算主要研究粒的構(gòu)造、解釋、表示、最優(yōu)粒度的選擇以及用規(guī)則形式所描述的粒與粒之間關(guān)系等[2-3].目前粒計(jì)算已成為智能信息處理領(lǐng)域一個非?；钴S的研究方向，并且有望為大數(shù)據(jù)挖掘提供一條極具前途的嶄新途徑[1-2，4].

在眾多粒計(jì)算研究方法中，粗糙集數(shù)據(jù)分析對粒計(jì)算研究的推動和發(fā)展起著重要的作用.粗糙集數(shù)據(jù)分析中的典型數(shù)據(jù)描述結(jié)構(gòu)稱為信息系統(tǒng)(information system)[5]，又稱為信息表或?qū)ο?屬性值表[3,6]，原始的Pawlak粗糙集理論利用數(shù)據(jù)樣本集上的等價(jià)類來描述“?！?，用等價(jià)關(guān)系所誘導(dǎo)的劃分來?；瘮?shù)據(jù)的樣本空間，用“?！贝鏄颖緦?shù)據(jù)進(jìn)行處理，并通過計(jì)算所定義的約簡(使得矛盾樣本集不改變的極小屬性集合)對數(shù)據(jù)集進(jìn)行特征提取，最終獲取聚類或分類規(guī)則或排序決策[5,7].傳統(tǒng)的粗糙集數(shù)據(jù)分析所處理的信息系統(tǒng)中的每個對象在每個屬性中只取唯一的值，這樣的系統(tǒng)稱為單尺度信息系統(tǒng)[6-8]，但在很多實(shí)際生活的數(shù)據(jù)處理中，人們要在多粒度或者多尺度環(huán)境下進(jìn)行問題求解和決策[3].因此，單一粒度或單一尺度框架下的知識表示與數(shù)據(jù)處理方法已遠(yuǎn)遠(yuǎn)不能滿足實(shí)際應(yīng)用的需求[1,3].近年來，“多粒度”環(huán)境下的數(shù)據(jù)建模成為粒計(jì)算研究的重要方向[1,3,9-15].在基于粗糙集的多粒度數(shù)據(jù)分析建模中，主要有從屬性選擇可以引起多粒度的角度提出的多?；植诩?multi-granulation rough set)模型[9-10]和從對象的鄰域半徑的大小可以引起多粒度的角度提出的多粒度鄰域粗糙集(multi-granularity neighborhood rough set)模型[11-12].另一方面，Wu等[13]認(rèn)為對象的屬性取值的多尺度是引起論域的多粒度?；囊粋€重要原因，為此提出了多尺度粗糙集數(shù)據(jù)分析的粒計(jì)算模型.數(shù)據(jù)的描述結(jié)構(gòu)稱為多尺度信息系統(tǒng)(multi-scale information system)(又稱為多粒度標(biāo)記信息系統(tǒng)[14])，這個數(shù)據(jù)處理模型被文獻(xiàn)稱為Wu-Leung模型[15].

多尺度粗糙集數(shù)據(jù)分析的主要思想是，根據(jù)決策目標(biāo)對每個屬性選擇一個合適的尺度或者粒度構(gòu)成一個新的單尺度信息系統(tǒng)，然后在保持相同目標(biāo)約束的前提下進(jìn)行屬性約簡(特征選擇)、決策規(guī)則提取及相應(yīng)的不確定性分析[6-8,13].因此，保持某種性質(zhì)(可以是定性的也可以是定量的)不變意義下選擇最粗的尺度標(biāo)記(稱為最優(yōu)尺度選擇或最優(yōu)粒度選擇)成為多尺度決策數(shù)據(jù)中知識獲取的一個關(guān)鍵問題[3,6-8,13-16].近年來，最優(yōu)尺度選擇成為多尺度粗糙集數(shù)據(jù)分析的一個主要方向，并取得了很多研究成果[14-29].

迄今為止，關(guān)于多尺度決策系統(tǒng)中最優(yōu)尺度選擇的研究所針對數(shù)據(jù)系統(tǒng)的決策屬性大多數(shù)是單尺度的，文獻(xiàn)[30]首次提出了決策是多尺度信息系統(tǒng)的最優(yōu)尺度選擇問題，給出了協(xié)調(diào)的決策是多尺度的完備信息系統(tǒng)的最優(yōu)尺度選擇方法.現(xiàn)實(shí)生活中存在大量缺省或信息不完整的數(shù)據(jù)，在粗糙集數(shù)據(jù)分析中稱為不完備信息系統(tǒng)[31-32].針對不完備數(shù)據(jù)，Wu等[14,33]提出了不完備多尺度決策系統(tǒng)的最優(yōu)尺度選擇和決策規(guī)則提取方法.本文中，筆者結(jié)合文獻(xiàn)[30]和文獻(xiàn)[28-29]，討論決策是多尺度的廣義不完備信息系統(tǒng)(簡稱決策多尺度不完備信息系統(tǒng))的最優(yōu)尺度選擇問題.

1 預(yù)備知識

設(shè)U是非空論域，對于A?U，A在U中的補(bǔ)集記為～A，即～A={x∈U|x?A}.本節(jié)簡介下文要用到的一些基本概念與知識.

1.1 不完備信息系統(tǒng)

一個信息系統(tǒng)[5]為一個二元組(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的值域.

若一個信息系統(tǒng)(U,A)中的某些屬性值是缺省的或未知的，則稱該系統(tǒng)為不完備信息系統(tǒng)[31]，用符號“*”表示未知值或缺省值，即如果a(x)=*，那么就認(rèn)為對象x在屬性a上的值是未知的.

對于給定的一個不完備信息系統(tǒng)(U,A)，B?A，記

RB={(x,y)∈U×U|?a∈B,a(x)=a(y)或a(x)=*或a(y)=*}.

顯然，RB是自反和對稱的，即RB是相似關(guān)系，但一般是非傳遞的[14,31],記:

SB(x)={y∈U|(x,y)∈RB}，x∈U.

SB(x)稱為對象x關(guān)于RB的相似類，記U/RB={SB(x)|x∈U}.

設(shè)(U,A)是一個不完備信息系統(tǒng)，B?A，X?U，X關(guān)于RB的下近似與上近似定義如下[31]：

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

Rd={(x,y)∈U×U|d(x)=d(y)}.

它將U劃分成互不相交的決策類：

U/Rd={D1,D2,…,Dr}，

其中Dj={x∈U|d(x)=j}，j∈Vd={1,2,…,r}.

稱決策系統(tǒng)S=(U,C∪j5i0abt0b)是不完備的[32]，若(U,C)是一個不完備信息系統(tǒng).對于不完備決策系統(tǒng)S=(U,C∪j5i0abt0b)，如果RC?Rd，那么稱系統(tǒng)S=(U,C∪j5i0abt0b)是協(xié)調(diào)的，否則稱S是不協(xié)調(diào)的[31].

1.2 廣義不完備多尺度信息系統(tǒng)與尺度組合

在一個傳統(tǒng)的信息系統(tǒng)(U,A)中，每一個對象x∈U在一個屬性a∈A上只取唯一確定的值，這樣的一個信息系統(tǒng)稱為單尺度信息系統(tǒng)，又稱為單粒度標(biāo)記信息系統(tǒng)[3].若信息系統(tǒng)(U,A)中每一個對象在同一個屬性上，根據(jù)不同的尺度標(biāo)記層面可以取不同的值，則(U,A)是一個多尺度信息系統(tǒng)[13]或多粒度標(biāo)記信息系統(tǒng)[14].Wu等在文獻(xiàn)[13]中首次提出了多尺度信息系統(tǒng)的概念.

定義1[13]稱S=(U,A)為一個多尺度信息系統(tǒng)或多粒度標(biāo)記信息系統(tǒng)，其中，U={x1,x2,…,xn}為非空有限對象集，稱為論域，A={a1,a2,…,am}為非空有限屬性集，且每個屬性aj∈A是一個多尺度屬性，即對于U中的同一對象，屬性aj在不同的尺度上可以取不同的值.

假設(shè)所有的屬性都有I個相同的等級尺度，則一個多尺度信息系統(tǒng)可以表示為

上述系統(tǒng)中假設(shè)不同屬性有相同的尺度標(biāo)記個數(shù)，但在實(shí)際生活中，各個屬性的尺度標(biāo)記個數(shù)可能不一樣，針對這種情形，Li等在文獻(xiàn)[15]中提出了一種基于不同屬性可以取不同尺度標(biāo)記個數(shù)的多尺度信息系統(tǒng)，稱之為廣義多尺度信息系統(tǒng)[7-8,14].

定義2[7,15]稱(U,A)是一個(廣義)多尺度信息系統(tǒng)，其中U={x1,x2,…,xn}是一個非空有限對象集，稱為論域，A={a1,a2,…,am}是一個非空有限屬性集，且每個屬性都是多尺度屬性.假設(shè)屬性aj有Ij個尺度標(biāo)記，則一個多尺度信息系統(tǒng)可以表示為

其中k=1,2,…,Ij-1，x∈U，j=1,2,…,m.

可以驗(yàn)證，(L,?)是一個偏序集，即?是L上的一個偏序關(guān)系(自反、傳遞和反對稱的關(guān)系).若進(jìn)一步定義

則(L,?,∧,∨)是一個有界格，顯然它是一個完備格，其中最小元是(1,1,…,1)，最大元是(I1,I2,…,Im)，并且

K1?K2?K1∧K2=K1?K1∨K2=K2.

對于B?A和K=(l1,l2,…,lm)∈L，記K在屬性子集B上的限制為KB，并記LB={KB|K∈L }，即LB是子多尺度信息系統(tǒng)(U,B)的尺度組合全體.

對于B?A和K=(l1,l2,…,lm)∈L，記：

RBK={(x,y)∈U×U|?al∈BKB,al(x)=al(y)或al(x)=*或al(y)=*},

則RBK是不完備多尺度信息系統(tǒng)S在尺度標(biāo)記層面K=(l1,l2,…,lm)上由屬性集B導(dǎo)出的一個相似關(guān)系[14]，特別地，對于a∈A，記RaK=R{a}K.令

SBK(x)={y∈U|(x,y)∈RBK}，x∈U.

SBK(x)稱為對象x關(guān)于BK的相似類[14].記

U/RBK={SBK(x)|x∈U}，

則U/RBK構(gòu)成了U的一個覆蓋.

定義5[14]設(shè)U為非空集，A與B是U的2個覆蓋，若對于任意A∈A ，存在B∈B使得A?B，則稱A比B細(xì)或B比A 粗，記作A?B.

1)K1?K2?RBK1?RBK2；

2)K1?K2?SBK1(x)?SBK2(x),?x∈U；

3)K1?K2?U/RBK1?U/RBK2；

4)B?C?A?RBK?RCK,?K∈L；

對于X?U,B?A,K∈L ，X關(guān)于RBK的下近似和上近似定義如下:

2 決策多尺度不完備信息系統(tǒng)

本節(jié)介紹具有多尺度決策屬性的廣義多尺度信息系統(tǒng)的相關(guān)概念.

這樣的一個系統(tǒng)可以表示為

若d被固定在第t個尺度，則S退化為具有單尺度決策屬性的廣義不完備多尺度決策系統(tǒng)，記

dt+1(x)=ht,t+1(dt(x))，x∈U，

稱ht,t+1為決策屬性d的信息粒度變換，如圖1所示給出由決策屬性d所對應(yīng)的粒度變換關(guān)系.

圖1 決策屬性的信息粒度變換

表1 尺度變換過程

Q1?Q2?Q1∧Q2=Q1?Q1∨Q2=Q2.

Rdt={(x,y)∈U×U|dt(x)=dt(y)}，

則Rdt是U上的一個等價(jià)關(guān)系，它將U劃分成互不相交的決策類：

U/Rdt={[x]dt|x∈U}，

其中 [x]dt={y∈U|dt(x)=dt(y)}={y∈U|(x,y)∈Rdt}.

1)t1≤t2?Rdt1?Rdt2，

2)t1≤t2?[x]dt1?[x]dt2，x∈U，

3)t1≤t2?U/Rdt1?U/Rdt2.

3 決策多尺度不完備信息系統(tǒng)的最優(yōu)尺度選擇

在多尺度決策系統(tǒng)知識獲取中，從系統(tǒng)中提取決策規(guī)則之前，首先要選擇保持某個或者某些量(或者性質(zhì))不變的一個合適的尺度(稱為最優(yōu)尺度)，它對應(yīng)于一個決策表，然后在所選的尺度所對應(yīng)的決策系統(tǒng)上繼續(xù)進(jìn)行保持相應(yīng)量不變的屬性約簡，包括系統(tǒng)約簡和局部約簡，最終得到蘊(yùn)含在系統(tǒng)中的決策規(guī)則.因此，最優(yōu)尺度選擇是多尺度決策系統(tǒng)知識獲取的關(guān)鍵問題.Huang等在文獻(xiàn)[30]討論了決策多尺度完備信息系統(tǒng)的最優(yōu)尺度選擇問題，沿著文獻(xiàn)[30]的思路，以下討論決策多尺度不完備信息系統(tǒng)的最優(yōu)尺度選擇問題.

證由SQ2=(U,CK2∪{dt2})是協(xié)調(diào)的可知，RCK2?Rdt2.因?yàn)镼1?Q2，從而K1?K2且t2≤t1，從而分別由定理1和定理4得，RCK1?RCK2且Rdt2?Rdt1，于是

RCK1?RCK2?Rdt2?Rdt1.

即SQ1=(U,CK1∪{dt1})是協(xié)調(diào)的.

證由定理5和定義11即得.

1)若SK是協(xié)調(diào)的，則S是協(xié)調(diào)的；

2)若存在t∈{1,2,…,N}使得SK關(guān)于決策屬性dt是協(xié)調(diào)的，則SK是協(xié)調(diào)的，從而S也是協(xié)調(diào)的.

證由定義10、定義11和定理1即得.

1) 若對于任意t′∈{1,2,3,…,N}，滿足t′

2) 若對于任意K′∈L，滿足KK′，則SK′,t=(U,CK′∪{dt})是不協(xié)調(diào)的，則稱Q=(l1,l2,…,lm,t)為S的一個最優(yōu)尺度選擇.

表2 一個決策多尺度不完備信息系統(tǒng)

L1=(1,1)，L2=(2,1)，L3=(3,1)，L4=(1,2)，L5=(2,2)，L6=(3,2).

圖2 尺度選擇的格結(jié)構(gòu)

經(jīng)計(jì)算

U/Rd1={{x1,x2},{x3,x4,x5},{x6},{x7},{x8}}，

U/Rd2={{x1,x2,x7},{x3,x4,x5,x6,x8}}.

U/RCL1={{x1,x2},{x3,x4,x5},{x6},{x7},{x8}}，

U/RCL2={{x1,x2},{x3,x4,x5},{x6},{x7},{x8}}，

U/RCL3={{x1,x2},{x3,x4,x5},{x6},{x7,x8}}，

U/RCL4={{x1,x2,x3},{x3,x4,x5},{x3,x6},{x7},{x8}}，

U/RCL5={{x1,x2,x3.x4,x5},{x3,x6},{x7},{x8}}，

U/RCL6={{x1,x2,x3,x4,x5},{x3,x6},{x7,x8}}.

4 結(jié) 論

最優(yōu)尺度選擇是多尺度信息系統(tǒng)與多尺度決策系統(tǒng)的知識表示與知識獲取的一個關(guān)鍵問題.迄今為止，對于決策屬性是多尺度的多尺度信息系統(tǒng)的研究成果還很少，初步研究了決策屬性是多尺度的廣義不完備多尺度信息系統(tǒng)(簡稱決策多尺度不完備信息系統(tǒng))的最優(yōu)尺度選擇問題.引進(jìn)了決策多尺度不完備信息系統(tǒng)的尺度選擇的概念，給出了尺度選擇的一些基本性質(zhì)，定義了協(xié)調(diào)的決策多尺度不完備信息系統(tǒng)的最優(yōu)尺度選擇概念，并用示例解釋了最優(yōu)尺度選擇的計(jì)算.這樣的一個最優(yōu)尺度選擇所對應(yīng)的協(xié)調(diào)決策表主要被用于提取蘊(yùn)含在系統(tǒng)中具有較好泛化能力的確定性規(guī)則集，因此本文成果是進(jìn)一步從相應(yīng)數(shù)據(jù)集進(jìn)行決策規(guī)則提取的基礎(chǔ)性工作.今后將進(jìn)一步研究不協(xié)調(diào)的決策屬性是多尺度的各種多尺度信息系統(tǒng)的最優(yōu)尺度選擇及相應(yīng)的知識發(fā)現(xiàn)問題.