吳偉志

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

從不同的粒度(granularity)上觀察、 分析與解決同一問題, 是人類智能的特點之一。 粒計算(Granular computing, GrC)是Lin在分析Zadeh的信息粒度(information granularity)[1]基礎上于1997年首次提出的[2], 它模擬人類思考問題的自然模式, 以粒(granule)為基本計算單位, 以處理大規(guī)模復雜數(shù)據(jù)集和信息等建立有效的計算模型為目標。 后來, Lin[3]和Yao[4]分別對粒計算研究的一些基本問題進行了闡述。 我國張鈸院士和張鈴教授提出的商空間理論[5]被公認為粒計算的另一個重要模型, 該理論明確指出“在問題求解研究中, 人類智能的一個公認特點, 就是人們能從極不相同的粒度上觀察和分析同一問題?！?粒計算主要研究粒的構造、 解釋、 表示、 在有不同尺度或粒度空間研究粒計算問題時, 還要考慮最優(yōu)尺度或粒度的選擇, 以及存在于粒之間的粒IF-THEN規(guī)則的提取和相關的理論與算法等。 目前, 粒計算已成為人工智能領域和大數(shù)據(jù)處理的重要方法[6-7]。

迄今為止,已經(jīng)提出了很多涉及具體應用背景的粒計算模型和方法,而在眾多粒計算研究方法中,粗糙集(rough set)[8]和形式概念分析(Formal concept analysis, FCA)[9]對粒計算研究的推動和發(fā)展起著重要的作用并取得了很多重要成果[10-17]。

粗糙集數(shù)據(jù)分析和形式概念分析的數(shù)據(jù)表示形式是屬性-對象值表, 分別稱為信息系統(tǒng)和形式背景。傳統(tǒng)的粗糙集數(shù)據(jù)分析和形式概念分析所呈現(xiàn)出的對象-屬性值表中大都是取單一屬性值的, 即對于系統(tǒng)中的每一個對象和所對應的每一個屬性,只取唯一的一個值,這樣的信息系統(tǒng)或形式背景反映的是固定尺度下的對象信息,我們稱為單尺度信息系統(tǒng)(也稱單粒度標記信息系統(tǒng))和單尺度形式背景。 事實上,單一粒度框架下的知識表示與數(shù)據(jù)處理方法已遠遠不能滿足實際應用的需求。例如,在對地理信息系統(tǒng)中的空間遙感數(shù)據(jù)(數(shù)據(jù)以某些光譜波段反射的灰度值進行標記)分析中,對于同一個地表物(觀察對象),隨著觀測的距離或分辨率不同,地表物會呈現(xiàn)出具有不同層次物理意義的對象,如某一地表物根據(jù)觀測距離或分辨率的不同,可能分別呈現(xiàn)出陸地、植被、莊稼地、玉米地等。 又比如,對于地圖上我國的某一地方,根據(jù)行政區(qū)域的不同粒度層次(如村、鄉(xiāng)、縣、地級市、省自治區(qū)等級別),其所屬地分別給予不同的區(qū)域標記。 總之,在多粒度標記數(shù)據(jù)模型下,同一批數(shù)據(jù)可以被標記為不同的尺度或粒度層次,人們可以根據(jù)需要在不同的尺度或粒度層面上處理和分析數(shù)據(jù)。 因而“多尺度”或者“多粒度”近幾年來成為粒計算研究的重要方向。

在基于粗糙集的多粒度數(shù)據(jù)表示與分析建模研究中,我們認為應該從引起多粒度的原因著手。本文主要介紹近幾年在粗糙集數(shù)據(jù)分析中的幾種多粒度知識表示和數(shù)據(jù)處理模型,并對相關問題的研究進行分析和展望。

1 相關的基礎知識

設U是非空論域,對于X?U,X在U中的補集記為～X,即～X={x∈U|x?X}。 本節(jié)簡要介紹后面要用到的一些基本概念與知識。

1.1 信息系統(tǒng)與近似集

定義1[8]一個信息系統(tǒng)是一個二元組(U,AT),其中U是一個非空有限對象集,稱為論域;AT是一個非空有限屬性集,對于任意的a∈AT,滿足a:U→Va,即a(x)∈Va,x∈U,其中Va={a(x)|x∈U}稱為a的值域。

對于一個給定的信息系統(tǒng)(U,AT),A?AT,記:

RA={(x,y)∈U×U|?a∈A,a(x)=a(y)}

顯然,RA是論域U上的等價關系,稱為不可分辨關系,它能導出U上的一個劃分

U/RA={[x]A|x∈U}。

其中[x]A={y∈U|(x,y)∈RA}稱為對象x關于RA-等價類。

設(U,AT)是一個信息系統(tǒng),A?AT,X?U,X關于RA的下近似和上近似定義如下:

其中|X|表示集合X的基數(shù)。X關于RA的粗糙度定義如下:

ρRA(X)=1-αRA(X)。

定義2[8]一個決策表(也稱為決策系統(tǒng))是一個二元組S=(U,C∪iqa0uy0),其中(U,C)是信息系統(tǒng),C是條件屬性集,d?C為決策屬性,d:U→Vd,Vd是屬性d的值域。 定義

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

U/Rd是由Rd生成的劃分,它將U?；蓻Q策類。若RC?Rd,則稱決策表(U,C∪e0c0guo)是協(xié)調(diào)的,否則稱它是不協(xié)調(diào)的。

對于B?C,記

?B(x)={d(y)|y∈[x]B},x∈U

?B(x)稱為x關于B在(U,C∪ogcc0ac)中的廣義決策值,?B稱為B在(U,C∪0a0emoe)中的廣義決策函數(shù)。顯然,(U,C∪uygoia0)是協(xié)調(diào)的當且僅當對于任意x∈U有|?C(x)|=1。

若信息系統(tǒng)(U,AT)中某些對象在某個屬性的值是缺省的(其中的缺省值常用*表示),則稱此信息系統(tǒng)是不完備信息系統(tǒng),對于A?AT,記:

RA={(x,y)∈U×U|?a∈A,a(x)=a(y),或a(x)=*,或a(y)=*}。

此時,RA是U上相似關系,它能導出U上的一個覆蓋U/RA={SA(x)|x∈U},其中

SA(x)={y∈U|(x,y)∈RA}

稱為對象x關于RA的相似類。 稱決策表S=(U,C∪cuomy0i)是不完備的,若(U,C)是不完備信息系統(tǒng)。類似地也可以通過相似關系定義集合的下近似和上近似。

通過粗糙集屬性約簡方法,根據(jù)決策類關于由條件屬性集導出關系的下近似和上近似,可以分別獲得蘊含在決策系統(tǒng)中的確定性決策規(guī)則和可能性決策規(guī)則[8]。

1.2 粒計算中的基本概念和研究內(nèi)容

盡管目前粒計算研究中沒有統(tǒng)一的數(shù)學形式化的理論描述,但是有一些基本概念在粒計算研究領域中已經(jīng)被普遍接受,它們是“?！焙汀傲；?granulation)”。

定義3在論域中具有相同或相似性質(zhì)的對象構成的集合稱為一個粒,粒有時也稱為信息粒。

粒是粒計算模型中的最小計算單位。在某些特定的數(shù)據(jù)分析中,粒不能再進行分解。 但是，這是一個相對的概念,在一個粒度層面上不能分解,但在更細或者更小粒度層面上還可以進行再分解。

定義4構造信息粒的過程稱為粒化。

粒是粒計算知識表示和問題求解的基本計算單元,通過?；捎闪＝M成的對于論域的劃分或覆蓋。

信息系統(tǒng)中由某個屬性子集導出一個對象的等價類或相似類就是粗糙集數(shù)據(jù)分析中的一個粒,每一個屬性子集將論域?；梢粋€劃分或覆蓋。

2 多粒度粗糙集數(shù)據(jù)分析模型

要研究多粒度知識表示與知識獲取問題,首先要弄清楚造成多粒度的原因是什么。迄今為止,文獻報道的有3種原因引起多粒度,相應地有3種粗糙集數(shù)據(jù)分析模型:

多粒化粗糙集(multi-granulation rough set)模型[18-20]:該模型是由Qian等[18]首先提出的,主要思想認為多粒度是由屬性選擇引起的,該模型根據(jù)信息系統(tǒng)中多個屬性子集(論域中的多個二元關系或者多個劃分或者多個覆蓋)構成知識多粒度空間,由屬性的并或交的選擇對概念進行近似和對論域進行?；?對應地有樂觀粗糙集模型和悲觀粗糙集模型。

多粒度鄰域粗糙集(multi-granularity neighborhood rough set)模型[21-23]:該模型以Hu等[24]提出的鄰域粗糙集模型為基礎,該模型認為對象的鄰域半徑的大小能夠引起多粒度,這個模型主要針對連續(xù)屬性值的數(shù)據(jù)或者信息系統(tǒng),其主要思想是根據(jù)對象鄰域半徑的大小來對論域進行?；?然后選擇合適的粒度進行聚類或者分類。

多尺度信息系統(tǒng)的粗糙集數(shù)據(jù)分析模型[25]:該模型是由Wu和Leung[25]首次提出,認為對象的屬性取值可以引起多粒度,數(shù)據(jù)表示形式稱為多尺度信息系統(tǒng)(multi-scale information system),又稱為多粒度標記信息系統(tǒng)(multi-granular labeled information system),并將傳統(tǒng)信息系統(tǒng)視作單粒度標記信息系統(tǒng)。 其數(shù)據(jù)處理的主要思想是根據(jù)決策目標對每一個屬性選擇合適的尺度構成一個新的單尺度信息系統(tǒng),然后在保持相同目標約束的前提下進行屬性約簡和決策規(guī)則提取。

下面我們分別介紹這幾種多粒度粗糙集數(shù)據(jù)分析模型,并對它們進行研究展望。

2.1 多粒化粗糙集模型

多?；植诩瘮?shù)據(jù)分析主要思想來源于投票決策機制中,若有m個專家進行投票決策,樂觀的決策是只要其中一個專家表示贊同決策就獲得通過,悲觀的決策是只有全部m個專家都表示贊同決策才能獲得通過。 將這個思想延伸到粗糙集數(shù)據(jù)分析中分別得到樂觀粗糙集和悲觀粗糙集模型。

稱為X關于R的樂觀多?；植诩倪吔?。X關于R的樂觀多?；植诩凭榷x如下:

定義X關于R的樂觀多粒化粗糙集的粗糙度為

稱為X關于R的悲觀多?；植诩倪吔?。X關于R的悲觀多?；植诩凭榷x如下:

常愛蘭知道這樣的事后又將周小羽綁起來打了一頓，從那時開始，周小羽每天放學回家就上樓，然后直到他們叫他來幫忙時才下來?？墒翘焯爝@樣按時上樓的情況并沒有讓老師罷手，老師還是過個三五天就帶消息來，說周小羽的作業(yè)這次又是沒有完成。

定義X關于R的悲觀多?；植诩拇植诙葹?/p>

注1由于U上的等價關系與U上的劃分是一一對應的,因此,定義5和定義6中等價關系簇R={R1,R2,…,Rm}可以被U上的m個劃分來替代。相應地,x的Ri等價類[x]Ri要換成第i個劃分中包含x的集合(等價類)。在具體應用上,設(U,AT)是信息系統(tǒng),P1,P2,…,Pm是AT的m個屬性子集簇,對于每一個屬性子集可以按照1.1節(jié)的方法定義U上的一個等價關系,因此,定義5和定義6中等價關系R={R1,R2,…,Rm}也可以用屬性子集簇{P1,P2,…,Pm}替代,具體見文獻[18-20]。

在理論層面上,多粒化粗糙集有很多拓展模型,比如可以將等價關系推廣成非等價關系得到雙論域多?；植诩Ｐ偷萚26-28]。 將由等價關系所對應的劃分拓展成覆蓋，則可以得到多粒化覆蓋粗糙集模型[29-31]。 更一般地,將經(jīng)典二元關系拓展到模糊關系，則可以得到多?；：植诩Ｐ?甚至將軟集或區(qū)間集與多粒化進行組合得到多?；洿植诩Ｐ秃投嗔；瘏^(qū)間粗糙集模型等[32-39]。另外,多粒化粗糙集模型下的多值邏輯方法也取得了重要進展[40]。將多粒化粗糙集和概念認知結(jié)合是一個很有意義的工作,并取得了一些重要進展[41-43]。

在具體應用上,各種信息系統(tǒng)和決策表在多粒化粗糙集模型下的粗糙近似、約簡(包括系統(tǒng)約簡和局部約簡)、規(guī)則提取、代價敏感分析方面等取得了一些重要研究成果。 將完備信息系統(tǒng)拓展成不完備信息系統(tǒng)、序信息系統(tǒng)、模糊信息系統(tǒng)、區(qū)間值信息系統(tǒng)、形式背景等,用多?；植诩椒ㄑ芯窟@些拓展數(shù)據(jù)表中的信息粒表示、知識約簡、規(guī)則提取、知識動態(tài)更新等仍是值得進一步研究的問題[44-49]。

在多?；植诩Ｐ图捌鋺醚芯恐?不確定性分析及度量研究是一個重要的問題。 這方面的研究主要是針對不同的不確定性問題引入不同的度量或測度,如概率不確定性、模糊性、信息熵、證據(jù)理論中的信任度與似然度,以及包含度等[50-57]。

從本質(zhì)上說,這類“多粒度”是通過多個屬性選擇不同的合成方式而獲得的。 當然,也有人認為這種樂觀和悲觀的定義粗糙近似的方式過于極端，可以采取更加折中的方式定義。

2.2 多粒度鄰域粗糙集模型

多粒度鄰域粗糙集模型的主要思想將鄰域粗糙集中的“鄰域”或者“距離”動態(tài)地用多個鄰域或者多個距離作為“多粒度”對論域進行?；?根據(jù)決策或者分類任務選擇合適的距離進行決策。

定義7[21-24]設(U,AT)是一個完備信息系統(tǒng),對于任意x∈U和屬性子集A?AT,x在屬性子集A上鄰域δA(x)定義如下:

δA(x)={y∈U|ΔA(x,y)≤δ}。

1)ΔA(x,y)≥0;

2)ΔA(x,y)=0當且僅當x=y;

3)ΔA(x,y)=ΔA(y,x);

4)ΔA(x,z)≤ΔA(x,y)+ΔA(y,z)。

需要指出的是，這里的ΔA一般是通過對象在屬性子集A上取值計算得到的,比如若A={a1,a2,…,aN}?AT,則可以定義Minkowsky距離:

其中p≥1。當然,不同的屬性上也可以選擇不同類型的距離函數(shù),在不同屬性上合成U上的距離函數(shù)時也可以取加權和等。

定義9[21-22]設(U,AT)是一個完備信息系統(tǒng),Γ={δ1,δ2,…,δt}，δk>0,k=1,2,…,t，記

定義9將不同的鄰域半徑δ1,δ2,…,δt作為“粒度”定義多粒度粗糙近似集。在具體應用中,若粒度半徑δ1,δ2,…,δt是事先確定的,則在決策表中如何選擇合適的粒度對決策或分類的泛化最強是一個值得研究的問題。當然,若δ1,δ2,…,δt不是事先給定的,則在數(shù)據(jù)集中訓練泛化能力好的粒度是一個比較重要的問題，比如,文獻[21-22]將不同鄰域或距離度量作為多粒度對論域進行?；?在泛化性能優(yōu)化的框架下提出了最大鄰域粒間隔的粒度選擇和組合方法。

多粒度鄰域粗糙集數(shù)據(jù)分析可以拓展到各種復雜的信息系統(tǒng)與決策表中的特征選擇、約簡、規(guī)則提取,包括動態(tài)數(shù)據(jù)挖掘等[58-62]。 另外,在不同的屬性值域中如何訓練或者選擇合適的距離函數(shù)也是一個值得研究的問題。在多粒度鄰域粗糙集模型的應用研究中,不確定性分析及度量研究也是一個重要的問題[63],比如針對不同的不確定性問題可以引入不同的度量或測度。

多粒度鄰域粗糙集模型應用限制是數(shù)據(jù)類型必須是實數(shù)值的或者可以轉(zhuǎn)化為實數(shù)值的屬性數(shù)據(jù)。

2.3 多尺度信息系統(tǒng)的粗糙集數(shù)據(jù)分析模型

在傳統(tǒng)粗糙集數(shù)據(jù)分析的信息系統(tǒng)(U,AT)中,每一個對象xi在屬性aj上只取一個確定的值,這是單尺度標記信息系統(tǒng)。 若信息系統(tǒng)(U,AT)中每一個對象在同一個屬性上根據(jù)不同的尺度標記層面可以取不同的值,則(U,AT)是一個多尺度(標記)信息系統(tǒng)。 Wu和Leung在文獻[25]中首次提出了多尺度信息系統(tǒng)的概念。

定義10[25]稱(U,AT)是一個多尺度信息系統(tǒng),其中U={x1,x2,…,xn}是一個非空有限對象集,稱為論域,AT={a1,a2,…,am}是一個非空有限屬性集,且每一個屬性都是多尺度屬性。

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

對于k∈{1,2,…,I},記

其中k=1,2,…,I。

這樣的多尺度信息系統(tǒng)和多尺度決策系統(tǒng)的粗糙集數(shù)據(jù)分析模型稱為Wu-Leung模型[64]。

例1[25]表1給出了一個多尺度決策系統(tǒng)

其中

U={x1,x2,…,x12},

C={a1,a2,a3,a4},

每個屬性有3個粒度層面的標記,其中“E”，“G”，“F”，“B”，“S”，“M”，“L”，“Y”，“N”分別表示“優(yōu)”、“良”、“中”、“差”、“小”、“中等”、“大”、“是”、“否”。 這樣的一個系統(tǒng)可以分解成3個決策表,見表2～4。

表1 一個具有3個粒度層面標記的多尺度決策系統(tǒng)Tab.1 A multi-scale decision system with three levels of granulation

表2 表1的第一個粒度層面標記下的決策表Tab.2 The decision table with the first level of granulation of Table 1

表3 表1的第二個粒度層面標記下的決策表Tab.3 The decision table with the second level of granulation of Table 1

表4 表1的第三個粒度層面標記下的決策表Tab.4 The decision table with the third level of granulation of Table 1

表5 一個廣義多尺度決策系統(tǒng)Tab.5 A generalized multi-scale decision system

在Wu-Leung模型中,相當于將決策系統(tǒng)的條件部分看成I個尺度,在保持某種性質(zhì)(可以是定性的也可以是定量的)一致的意義下選擇最粗的尺度標記(也稱為最優(yōu)尺度選擇)成為在多尺度決策系統(tǒng)中提取決策規(guī)則前的一個關鍵問題[25, 65-69]。 當然,這樣得到的最優(yōu)尺度我們稱為系統(tǒng)的最優(yōu)尺度(它們對應一個決策表),但是在實際問題中,有時為了獲得某一個對象所對應的泛化能力強的決策規(guī)則時,則只須計算關于決策在保持某種性質(zhì)(可以是定性的也可以是定量的)一致意義下的選擇最粗尺度標記即可,此時獲得的最優(yōu)尺度稱為該對象的局部最優(yōu)尺度[70-71]。Wu等人研究了在多粒度標記框架下的其他數(shù)據(jù)類型的信息粒度表示和最優(yōu)粒度的選擇問題,包括不完備多尺度信息系統(tǒng)、不完備序信息系統(tǒng)等[72-74]。 Gu和Wu[75-77]還給出了協(xié)調(diào)的和不協(xié)調(diào)的多尺度標記決策系統(tǒng)中知識獲取的算法。

由于以上多粒度標記信息系統(tǒng)都有一個共同的假設,即系統(tǒng)中所有的屬性都具有相同的粒度標記個數(shù),而實際生活中人們可能面對不同的屬性具有不同的粒度標記個數(shù)的數(shù)據(jù)處理問題。針對這種情形,Li和Hu在文獻[64]和文獻[78]中提出了一種推廣的多粒度標記數(shù)據(jù)分析模型(有時稱為廣義多尺度信息系統(tǒng))。

定義12[64]稱(U,AT)是一個廣義多尺度信息系統(tǒng),其中U={x1,x2,…,xn}是一個非空有限對象集,稱為論域,AT={a1,a2,…,am}是一個非空有限屬性集,且每一個屬性都是多尺度屬性。假設屬性aj有Ij個等級粒度,則一個多尺度信息系統(tǒng)可以表示為:

例2表5(是表1將第4列刪除得到的)給出了一個多尺度決策系統(tǒng)

其中

U={x1,x2,…,x12},

C={a1,a2,a3,a4},

其中a1有2個粒度層面的標記,其余屬性有3個粒度層面的標記。

對于這樣的一個多尺度決策系統(tǒng),顯然不能用例1的方法簡單地將它分解成3個粒度層面的子表(a1只有2個粒度層面的標記),針對這樣的系統(tǒng),Li和Hu在文獻[64]中引入尺度組合的概念用于解決多尺度決策系統(tǒng)的尺度選擇問題。

定義14[64]對于廣義多尺度信息系統(tǒng)(U,AT),若屬性aj∈AT，取第lj個尺度標記(1≤lj≤Ij),j=1,2,…,m,并記K=(l1,l2,…,lm),則稱K=(l1,l2,…,lm)為系統(tǒng)S=(U,AT)的一個尺度組合,記(U,AT)的尺度組合全體為L。

對于A?AT和K=(l1,l2,…,lm)∈L,記K在屬性子集A上的限制為KA,定義

RAK={(x,y)∈U×U|?al∈AKA,al(x)=al(y)}，

則RAK是多尺度信息系統(tǒng)S在尺度組合K=(l1,l2,…,lm)下由屬性集A導出的一個等價關系,特別地,對于a∈AT,記RaK=R{a}K。記

[x]AK={y∈U|(x,y)∈RAK},x∈U。

[x]AK稱為對象x關于AK的等價類。記

U/RAK={[x]AK|x∈U},

則U/RAK={[x]AK|x∈U}構成了U的一個劃分。

類似于單尺度決策系統(tǒng)有各種各樣意義下的屬性約簡問題,探索多尺度決策系統(tǒng)在不同物理意義下的最優(yōu)尺度組合選擇(包括系統(tǒng)最優(yōu)尺度組合選擇和局部最優(yōu)尺度組合選擇)是多尺度決策系統(tǒng)中知識表示和知識獲取的重要問題。當然,各種復雜數(shù)據(jù)類型在不同粒度或尺度下的決策規(guī)則提取、不確定性分析及其算法等仍是值得進一步研究的問題。

3 結(jié) 語

粒計算是大數(shù)據(jù)分析與知識發(fā)現(xiàn)的一個重要工具,近幾年來,多粒度成為粒計算研究的一個重要方向。本文從形成多粒度的原因出發(fā),對多?；植诩Ｐ?、多粒度鄰域粗糙集模型、多尺度信息系統(tǒng)的粗糙集數(shù)據(jù)分析模型等目前相對而言比較流行的3種多粒度粗糙集數(shù)據(jù)分析模型研究進行了回顧,并對這些模型進一步進行理論與應用研究作了初步探討。 需要指出的是,本文只是對一些重要出版機構中的文獻進行了有選擇地討論,未對所提煉的方向與問題展開詳細論述,希望能對相關研究領域給出一些基本輪廓,

當然,引起多粒度的原因并非只有這3種形式,比如,在全國、省自治區(qū)、地區(qū)(地級市)、縣、鄉(xiāng)鎮(zhèn)等不同級別的道路交通地圖中,從粗粒度到細粒度的道路圖變換顯示中會有不斷地“增加”一些級別比較低的道路,而從細粒度到粗粒度的道路圖變換顯示中又會不斷地“刪除”一些級別比較低的道路。 因此,與“并”和“交”模式不同,“增加”與“刪除”是另外一種引起多粒度的原因。 針對類似數(shù)據(jù)形式如何建立多粒度計算模型是值得考慮的問題。