基于粒計算的不確定性分析

苗奪謙，胡聲丹

(1.同濟大學(xué) 計算機科學(xué)與技術(shù)系，上海 201804； 2.同濟大學(xué) 嵌入式系統(tǒng)與服務(wù)計算教育部重點實驗室,上海 201804)

不確定性(uncertainty)是自然界普遍存在的現(xiàn)象,如：玻爾曾指出“不確定性和模糊性是量子世界所固有的”;美籍?dāng)?shù)學(xué)家曼德博針對“英國海岸線有多長”這一問題,給出的答案是“不確定的”;美國氣象學(xué)家洛侖茲總結(jié)提出“蝴蝶效應(yīng)”以說明系統(tǒng)對初值的敏感性;德國物理學(xué)家海森堡提出的“不確定性原理”等。

不確定性也是人類認知過程中普遍存在的現(xiàn)象,當(dāng)人們用概念、符號、語言、模型等來描述客觀世界時,獲得的認知具有不完備性或模糊性。同時,不同認知主體受生活經(jīng)歷、知識水平、價值觀念、思維方式、興趣愛好等諸多因素的影響,其認知結(jié)構(gòu)是不同的,所以在感受、認知的過程中,對同一事物的認知是存在差異的。

作為計算機科學(xué)的前沿領(lǐng)域,人工智能目標之一是使機器具有人類的智能,并能像人類一樣對客觀世界進行感知、認知、推理及決策。然而,客觀系統(tǒng)存在隨機性,人類認知存在模糊性,并且現(xiàn)有知識常常是不完整、不一致的,這一切都要求人工智能對不確定性問題展開深入研究,探索其度量、推理和決策的方法[1]。人工智能領(lǐng)域多年來對不確定性問題的探索推動了粒計算理論的興起和發(fā)展。粒計算是一種新的計算范式,它以多粒度的表示、問題求解方法、信息處理模式等為研究對象,屬于人類較高層次認知機理研究的范疇[2]。由于其抽象了人類以多層次、多視角處理問題時所表現(xiàn)出全局觀和近似求解能力,粒計算逐漸成為不確定性問題求解的重要理論。在過去的30年中先后涌現(xiàn)出基于模糊集[3]的詞計算[4]、粗糙集[5]、商空間[6]、云模型[1]等經(jīng)典粒計算理論模型,粒計算的應(yīng)用領(lǐng)域包括大數(shù)據(jù)分析與挖掘、知識發(fā)現(xiàn)、模式識別、聚類分析、復(fù)雜問題求解等。

1 粒計算理論

1.1 粒計算的發(fā)展歷程

美國數(shù)學(xué)家、控制論專家L.A.Zadeh教授指出，Cantor集合論為了達到精確和嚴格的目的,將思維過程絕對化,而現(xiàn)實世界中復(fù)雜事物不可能絕對精確,存在著大量模糊現(xiàn)象。于是在1965年提出模糊集合論,其主要思想是使用“隸屬函數(shù)”對“屬于”或“不屬于”之間的過渡狀態(tài)進行量化,對經(jīng)典集合論進行推廣。

在模糊集的基礎(chǔ)上,Zadeh于1979年首次提出并討論了模糊信息粒度化問題[7]。他認為，信息粒的概念存在于很多領(lǐng)域中,如自動機與系統(tǒng)論中的“分解與劃分”、區(qū)間分析里的“區(qū)間數(shù)運算”等。美國Stanford大學(xué)J.R. Hobbs教授于1985年,發(fā)表了題為“Granularity”的論文[8],討論了粒的分解與合并,提出了產(chǎn)生不同大小粒的模型和方法。1996年,T.Y. Lin教授在加州大學(xué)伯克利分校訪問時,向Zadeh提出了“Granular Computing”(粒計算,縮寫為GrC)的研究,至此,粒計算一詞正式誕生。隨后,他發(fā)表了關(guān)于粒計算的論文[9],討論了二元關(guān)系下的粒計算模型,論述了粒結(jié)構(gòu)、粒表示、粒應(yīng)用等方面的問題。1996年,Zadeh提出“詞計算理論”[4],標志著模糊粒度化理論的誕生。在Lin的工作基礎(chǔ)上,加拿大里賈納大學(xué)的Y. Y. Yao教授于1999年提出了基于鄰域系統(tǒng)的粒度計算模型,對粒度計算進行了研究[10],并將它應(yīng)用于知識挖掘等領(lǐng)域,建立概念之間的IF-THEN規(guī)則與粒度集合之間的包含關(guān)系,提出利用由所有劃分構(gòu)成的格求解一致分類問題,為知識挖掘提供了新方法和視角。

在國內(nèi),張鈸院士和張鈴教授于1990年提出了基于商空間的粒度計算模型[6]。商空間理論用商集表示不同的粒度層次,建立不同粒度世界之間的保真、保假原理。該理論通過觀察當(dāng)前粒度空間是否可解,來決定是否進入更細、更深的粒度空間,將不同粗細的粒世界上的粒的解組合成原問題的解,并提出一種商粒度空間上的多粒度表示法,構(gòu)建多粒度的分層遞階商空間結(jié)構(gòu)。20世紀末,李德毅院士在概率論和模糊數(shù)學(xué)理論基礎(chǔ)上,提出了云模型,通過賦予樣本點以隨機確定度來統(tǒng)一刻畫概念中的隨機性、模糊性及其關(guān)聯(lián)性。基于云模型的云變換可以實現(xiàn)不同粒度層次上概念的合成和分解,是一種可變粒計算[1]。進入21世紀后,粒計算的研究在國內(nèi)受到越來越多學(xué)者的關(guān)注。劉清教授在他的專著中闡述了信息粒度及其計算,并將粒度計算的方法成功應(yīng)用于醫(yī)療診斷專家系統(tǒng)[11];苗奪謙教授在研究粗糙集理論時引入信息論,開創(chuàng)性研究了知識的信息表示與信息度量,提出了知識的信息熵、條件熵和互信息等概念,分析討論了知識的不確定性(粗糙性)與信息熵之間的關(guān)系[12-14],并用粒計算的概念闡述了對不確定性的研究[15];王國胤教授等探討了模糊集、粗糙集、商空間理論模型及其他擴展粒計算模型中知識的不確定問題[16];梁吉業(yè)教授等研究了信息系統(tǒng)中信息粒的刻畫和表示,建立了信息粒度與熵之間的互補關(guān)系[17];吳偉志教授等討論了概念格中的粒度結(jié)構(gòu),并應(yīng)用到形式概念分析中[18]。近年來,國內(nèi)學(xué)者張燕平[19]、錢宇華[20]、李天瑞[21]、張賢勇[22]等關(guān)于粒計算研究的論文相繼發(fā)表。

1.2 粒計算主要模型

張鈸院士、張鈴教授指出“人類智能的一個公認特點,就是人們能從極不相同的粒度上觀察和分析同一問題。人們不僅能在不同的粒度世界上進行問題的求解,而且能夠很快地從一個粒度世界跳到另一個粒度世界,往返自如,毫無困難”[6]。粒計算正是反映了人類這種多層次、多視角的處理問題方式,逐漸成為不確定性問題求解的重要理論。粒計算的基本模型如圖1所示,包括粒結(jié)構(gòu)、粒層、粒子三部分,從不同視角看待問題可以構(gòu)建不同的粒結(jié)構(gòu),一個粒結(jié)構(gòu)由多個粒層構(gòu)成,每個粒層又由多個粒子構(gòu)成,不同粒層的粒子可以通過粗化或細化進行轉(zhuǎn)換。

圖1 粒計算基本模型Fig.1 A basic model of granular computing

粒計算理論的代表模型有模糊集、粗糙集、商空間、三支決策和云模型等。其中,基于模糊集的詞計算模型側(cè)重于信息的模糊?；?以處理計算對象的不確定性為主要目標,而粗糙集、商空間、三支決策、云模型則側(cè)重于不同粒度上復(fù)雜問題的不確定性,以復(fù)雜問題的多粒度計算為主要目標。

1)模糊集模型

模糊集合論是通過計算對象關(guān)于集合的隸屬程度來近似描述不確定性,反映了集合邊界的不分明性。

經(jīng)典模糊集(也稱為一型模糊集)中隸屬度μA(x)(0≤μA(x)≤1)反應(yīng)了對象x屬于模糊集A的程度。隸屬度越小,說明x屬于A的程度越低;隸屬度越大,說明x屬于A的程度越高。當(dāng)μA(x)={0,1}時,模糊集退化為經(jīng)典的精確集。該模型中隸屬度值是精確唯一的,后續(xù)研究中出現(xiàn)了對經(jīng)典模糊集的各種擴展模型,如區(qū)間值模糊集、直覺模糊集、二型模糊集、Vague集、勾股模糊集等。

對信息的模糊粒化,使得計算機能夠在不精確以及部分精確的環(huán)境下給出合理的決策成為可能。隨著模糊集理論的不斷發(fā)展完善,以模糊邏輯和信息?；癁榛A(chǔ)的模糊信息粒化理論能進一步發(fā)展,并為詞計算的發(fā)展提供了前提條件。

2)粗糙集模型

粗糙集理論[5]由波蘭科學(xué)院院士Pawlak于1982年提出,它是一種處理不精確、不一致和不確定性知識的數(shù)學(xué)工具。粗糙集模型的基本思想是利用不可分辨關(guān)系(等價關(guān)系)構(gòu)成對象的等價類,所有的等價類構(gòu)成論域的劃分,從而建立一個近似空間。對于任意概念(集合),可以利用近似空間中的一對精確概念(集合)(下近似集和上近似集)來表示,從而建立概念(集合)的邊界定義。

定義1設(shè)信息系統(tǒng)IS=(U,A,V,f)中,對?X?U,R?A,概念X關(guān)于知識R的下近似和上近似分別定義為:

則X的R正域、負域和邊界域分別為:

即X的R正域由那些根據(jù)知識R判斷肯定屬于X的元素組成;負域由那些根據(jù)知識R判斷肯定不屬于X的元素組成;邊界域由那些根據(jù)知識R既不能判斷肯定屬于X、又不能判斷肯定不屬于X的元素組成。

經(jīng)典粗糙集模型定義在等價關(guān)系的基礎(chǔ)之上,針對只包含符號型數(shù)據(jù)的完備信息系統(tǒng),使用精確的集合進行概念的表示及知識的獲取。但在實際問題求解過程中,等價關(guān)系、符號數(shù)據(jù)、完備系統(tǒng)、精確的上下近似集等要求過于嚴苛,眾多學(xué)者對經(jīng)典粗糙集進行擴展,提出了適應(yīng)不同問題的擴展粗糙集模型,包括粗糙模糊集和模糊粗糙集[23],層次粗糙集[24]、多粒度粗糙集[20]、多尺度粗糙集[25]等。

3)商空間模型

我國學(xué)者張鈸院士和張玲教授在研究問題求解時,獨立地提出了商空間理論[6],將不同的粒度世界與數(shù)學(xué)上的商集概念統(tǒng)一起來。根據(jù)研究目的的不同,商空間理論對同一問題可以構(gòu)造不同的商空間,從而得到原問題不同角度、不同層次的解,最后綜合這些解構(gòu)成原問題的解。

商空間理論中,由等價關(guān)系產(chǎn)生論域X的不同商集[X]及其對應(yīng)的商空間([X],[f],[T])構(gòu)成了原問題(X,f,T)的不同粒度世界。分層遞階商空間鏈可以表示問題的不同粒度空間,利用商空間的保真、保假原理,建立不同粒度空間之間的聯(lián)系,在不同的粒度世界上進行推理,從而簡化問題和加快問題求解的速度。

對商空間理論進行的推廣,包括引入模糊等價關(guān)系[26]、模糊相容關(guān)系[27]等。

4)三支決策模型

三支決策是在傳統(tǒng)的“接受”、“拒絕”二支決策選項基礎(chǔ)上加入“不承諾”選項,可以有效地規(guī)避對象認知不確定情況下誤接受或誤拒絕所造成的損失。同時,對不承諾項的再研究,可細化對決策對象的認知粒度,進而提高決策的準確性[28]。

加拿大學(xué)者Y. Y. Yao教授將三支決策思想引入到概率粗糙集中,提出決策粗糙集模型,該模型使用一對閾值(α,β)(0≤β<α≤1)來決定正域、負域和邊界域,并將正域、負域和邊界域分別解釋為接受、拒絕和不承諾3種決策。其中,閾值的選取是關(guān)鍵,可以由損失函數(shù)λ決定,而λ的大小由實驗或?qū)＜医o出。

近年來,越來越多的學(xué)者研究和拓展了三支決策理論、方法,并將其應(yīng)用到多個研究領(lǐng)域,如三支決策空間[29]、決策規(guī)則沖突[30]、流計算[31]、屬性約簡[32]、情感分類[33]等。

5)云模型

云模型是由我國學(xué)者李德毅院士在概率論和模糊數(shù)學(xué)理論基礎(chǔ)上,提出的定性定量轉(zhuǎn)換的認知模型[1],它可以實現(xiàn)定性概念與定量數(shù)值之間的雙向轉(zhuǎn)換。云模型通過賦予樣本點隨機確定度來統(tǒng)一刻畫概念的隨機性、模糊性及其關(guān)聯(lián)性,利用期望、熵、超熵3個數(shù)字特征來整體表征一個定性概念,并通過正向云發(fā)生器、逆向云發(fā)生器算法形成定性概念與其定量表示之間的不確定性轉(zhuǎn)換。

云模型中云滴x對定性概念C的確定度μ(x)是具有穩(wěn)定傾向的隨機數(shù),是論域U到區(qū)間[0,1]上的概率分布,而不是一個固定的數(shù)值。云滴的確定度可以理解為云滴能夠代表該定性概念的程度。云滴出現(xiàn)的概率越大,云滴的確定度越大,則云滴對概念的貢獻越大。

云變換是通過高斯混合模型和逆向云發(fā)生器,對樣本數(shù)據(jù)的分布進行擬合,抽取形成不同粒度的多個概念,隨著粒度的提升,細粒度的概念可以通過概念爬升形成新的更大粒度的概念?；谠颇Ｐ偷牧Ｓ嬎惚举|(zhì)上是基于概率統(tǒng)計的方法實現(xiàn)粒計算和可變粒計算。

2 粒計算理論與不確定性分析

對不確定性問題的研究,主要包括不確定性問題的描述、不確定性的度量、不確定性推理等。針對模糊集、粗糙集、商空間、三支決策、云模型5個粒計算理論模型,不確定性研究的主要內(nèi)容概括起來如表1所示。

表1 粒計算主要模型與不確定性研究內(nèi)容Tab.1 Research contents in some granular computing models

其中,在粗糙集理論中,將知識視為關(guān)于論域的劃分,且知識是有粒度的。概念的不確定性用概念相對于知識的上下近似集合來描述;對概念、知識的不確定性度量方式有代數(shù)方法下定義的精度[34]:

粗糙度[34]:

ρR(X)=1-αR(X),

信息方法下定義的粗糙熵[35]:

知識Q相對于知識P的條件熵[13]:

H(Q|P)=

互信息[13]:

I(P;Q)=H(Q)-H(Q|P),

互補熵[36]、Rough熵[36]等;使用從條件集到?jīng)Q策集的IF-THEN規(guī)則進行不確定性推理,以獲取知識。

3 基于粗糙集模型的不確定性分析

粒計算研究內(nèi)容主要包括：問題的?；?即如何構(gòu)建粒的結(jié)構(gòu);粒的度量,即如何衡量粒子的“大小”或“粗細”;粒算子,即基于粒與粒之間的關(guān)系,如何構(gòu)造粒的運算、粒的轉(zhuǎn)換等[2]。在粗糙集背景下,從粒的表示、粒的度量、粒的關(guān)系及轉(zhuǎn)換、屬性約簡與規(guī)則提取等方面分析不確定性。

3.1 多粒度

經(jīng)典粗糙集理論中,論域中的任意概念可以用等價類[x]R近似表示,每個等價類被看成一個知識粒,粒內(nèi)部的各元素間具有不可分辨關(guān)系,所有的知識粒形成論域的一個劃分。使用一個屬性集對全域進行等價劃分形成信息粒,由這些信息粒構(gòu)成的模型被稱為單粒度粗糙集模型。

以單粒度粗糙集模型為基礎(chǔ)的多粒度粗糙集模型可以發(fā)掘不同粒度之間的關(guān)系,對單粒度的信息進行融合,進而在多粒度下進行約簡與知識獲取,引起了眾多學(xué)者的關(guān)注。其中苗奪謙、馮琴榮等[24]在分析人類先驗知識結(jié)構(gòu)化特點之后,從屬性值域出發(fā),將每個屬性擴展成一個概念層次樹,提出了一個粗糙集的擴展模型,即層次粗糙集模型,并應(yīng)用于層次決策規(guī)則挖掘?；趯哟未植诩Ｐ?錢進[37]等提出了大數(shù)據(jù)下層次決策規(guī)則并行計算模型,用于大數(shù)據(jù)背景下不同層次決策規(guī)則的挖掘。苗奪謙、張賢勇等[22]提出雙量化粗糙集模型,對概率粗糙集和程度粗糙集進行了擴展,并從粒計算角度分析了4種剖分區(qū)域的特點,研究了基于邏輯或的雙量化粗糙集模型的屬性約簡、基于重要度準確率的粒構(gòu)造和屬性約簡[38]。錢宇華等[20]分析了在多源信息系統(tǒng)、高維特征數(shù)據(jù)集、多智能體等應(yīng)用中單粒度粗糙數(shù)據(jù)分析方法的局限性,提出了基于“求同存異”策略的樂觀多粒度粗糙集和基于“求同排異”策略的悲觀多粒度粗糙集,苗奪謙、劉財輝等提出了多粒度覆蓋粗糙集[39]、多粒度覆蓋粗糙模糊集[40]。此外,典型的多粒度粗糙集模型還有吳偉志等提出的多尺度粗糙集[25]。

3.2 粒的度量

粗糙集理論中,等價類是信息系統(tǒng)的基本知識粒,知識粒度是知識粒的一種平均度量,反映了知識的分類能力,粒度越細,分類能力越強。苗奪謙、范世棟等[15]給出了知識庫中知識粒的度量,并從知識粒度:

知識分辨度:

Dis(R)=1-GD(R),

知識熵:

的關(guān)系上研究了粗糙集的不確定性。馮琴榮、苗奪謙等在文獻[41]中定義了知識的劃分粒度

來度量知識的分類能力。

不同粒層的知識粒度之間存在粗細關(guān)系,知識粒度隨知識劃分能力的增強而減小,而同一粒層下知識的分辨能力與粒度存在互補關(guān)系,而知識熵隨知識粒度的減小而單調(diào)遞增。事實上,知識的劃分粒度可以看成是期望粒度,是對知識導(dǎo)出的劃分中各劃分粒“平均”長度的一種度量,它的值越小,表明劃分粒的平均長度越短,論域中劃分粒的個數(shù)就越多,即該知識能區(qū)分開的對象就越多,因此分類能力也就越強,不確定性越小。

關(guān)于知識粒度,劉財輝等在文獻[42]中對幾種度量方法進行了比較研究,詳細分析了它們之間的聯(lián)系與區(qū)別。

3.3 粒的關(guān)系

粗糙集模型中,從不同角度、不同層次看待對象集、屬性集、屬性值集,能形成不同的粒結(jié)構(gòu)、粒層及粒子,不同層的粒子之間存在粗細關(guān)系。

1)屬性集變化與粒度的關(guān)系

定義2設(shè)P,Q是論域U上的兩個等價關(guān)系,且U/P={X1,X2,…,Xn},U/Q={Y1,Y2,…,Ym},如果對任意Xi∈P,存在Yj∈Q,使得Xi?Yj,稱U/P是比U/Q更細的劃分,記為P?Q。

若P?Q,則有GD(P)≤GD(Q),Dis(P)≥Dis(Q),H(P)≥H(Q),E(P)≤E(Q)成立。

通過改變屬性集中屬性的個數(shù)也會引起粒度的變化,若屬性集P，Q滿足P?Q,即在屬性集P上增加屬性得到屬性集Q,則由知識Q形成的劃分更細,劃分空間中的粒子個數(shù)增加,粒子變細,知識粒度變小,即GD(P)≥GD(Q)成立。

以UCI數(shù)據(jù)集Molecular Biology (Splice)(3190個對象,60個條件屬性)為例,當(dāng)屬性集R屬性編號分別為{1},{1,2},…，{1,2,…,10}時,知識劃分的不確定性與屬性集之間的變化關(guān)系如圖2所示,即說明了隨著屬性集R屬性的增加,知識的劃分越細,粒子越細,知識粒度GD(R)越小,分辨度Dis(R)越大,知識熵H(R)越大,知識的劃分粒度E(R)越小,不確定程度越小。

圖2 屬性集屬性個數(shù)與知識劃分不確定性Fig.2 Relations between the number of attributes and uncertainty of knowlege

2)屬性值變化與粒度的關(guān)系

層次粗糙集模型[24]中,屬性在不同概念層具有不同的值域,屬性值域的變化也會引起粒度的變化。

針對文獻[24]數(shù)據(jù)表,選取屬性集R={education-level},基于屬性集的不同概念層,數(shù)據(jù)的劃分U/R及不確性度量結(jié)果如表2所示。

表2 屬性集概念層與知識劃分不確定性Tab.2 Relations between the concept hierarchies of attributes and uncertainty of knowledge

從表2可以看出,對于某個屬性集,其值域越細,該概念層對應(yīng)的等價關(guān)系劃分能力越強,粒子越細,知識粒度越小,不確定性越小。

3.4 知識約簡與規(guī)則提取

粗糙集理論的一個重要任務(wù)是在決策表中獲取知識,而這種知識通常是用規(guī)則形式表示的,決策表的每一行即確定一條決策規(guī)則,而利用決策表信息提取規(guī)則并進行智能處理之前,需要利用某一標準對信息系統(tǒng)進行知識約簡[43]。

知識約簡是指刪除條件屬性集中冗余的屬性或?qū)傩灾岛?能保持原始決策表條件屬性與決策屬性之間的依賴關(guān)系,即約簡后的屬性子集是對論域的劃分空間保持不變的前提下的最粗劃分。約簡算法可以通過刪除冗余屬性或添加重要屬性進行,其中添加屬性的方式是從信息系統(tǒng)的核開始,按照一定的啟發(fā)信息獲取屬性約簡[44]。

從粒計算的角度看,條件屬性的增加或刪除會改變?？臻g的知識粒度,刪除屬性時知識粒度會增大,而添加屬性時知識粒度會減小,如圖3所示。屬性約簡的過程本質(zhì)上是根據(jù)知識的變化不斷改變粒層和粒子結(jié)構(gòu)的過程,直至得到?jīng)Q策劃分空間U/D的最大近似劃分。

圖3 粒層與屬性集變化關(guān)系Fig.3 Relations between granule level and attributes

決策表中,可以從不同粒層上提取規(guī)則,由于粒度的不確定性會引起決策規(guī)則的不確定。決策規(guī)則C→xD不確定性即反映所表達知識的真實性,其度量方式有確定性因子Cer(C→xD)和覆蓋因子Cov(C→xD)[45]。

4 結(jié) 語

不確定性是一種普遍存在的現(xiàn)象,廣泛存在于自然科學(xué)和社會科學(xué)領(lǐng)域。粒計算是一種新的計算范式,是研究基于多層次粒結(jié)構(gòu)的思維方式、問題求解方法、信息處理模式及其相關(guān)理論、技術(shù)和工具的學(xué)科,由于其反應(yīng)了人類處理具有多層次、多視角問題時體現(xiàn)的全局觀和近似求解能力,粒計算逐漸成為不確定性問題求解的重要理論。

雖然粒計算針對不確定性問題在理論模型、應(yīng)用方面取得了大量研究成果,但還存在以下問題有待深入研究:能否或者如何整合模糊集、粗糙集、商空間、云模型等模型的優(yōu)點,構(gòu)建統(tǒng)一的粒計算模型?針對問題空間,如何構(gòu)建合理的粒結(jié)構(gòu)、粒層、粒子,并在問題求解時,在多粒度空間下選取最合適的粒度?不同粒層的粒子轉(zhuǎn)換算子如何構(gòu)造,以及粒轉(zhuǎn)換過程中的不確定性如何度量?