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

苗奪謙，胡聲丹

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

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

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

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

1 粒計算理論

1.1 粒計算的發展歷程

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

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

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

1.2 粒計算主要模型

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

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

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

1)模糊集模型

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

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

對信息的模糊粒化,使得計算機能夠在不精確以及部分精確的環境下給出合理的決策成為可能。隨著模糊集理論的不斷發展完善,以模糊邏輯和信息粒化為基礎的模糊信息粒化理論能進一步發展,并為詞計算的發展提供了前提條件。

2)粗糙集模型

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

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

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

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

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

3)商空間模型

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

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

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

4)三支決策模型

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

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

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

5)云模型

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

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

云變換是通過高斯混合模型和逆向云發生器,對樣本數據的分布進行擬合,抽取形成不同粒度的多個概念,隨著粒度的提升,細粒度的概念可以通過概念爬升形成新的更大粒度的概念。基于云模型的粒計算本質上是基于概率統計的方法實現粒計算和可變粒計算。

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

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

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

其中,在粗糙集理論中,將知識視為關于論域的劃分,且知識是有粒度的。概念的不確定性用概念相對于知識的上下近似集合來描述;對概念、知識的不確定性度量方式有代數方法下定義的精度[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]等;使用從條件集到決策集的IF-THEN規則進行不確定性推理,以獲取知識。

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

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

3.1 多粒度

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

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

3.2 粒的度量

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

知識分辨度:

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

知識熵:

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

來度量知識的分類能力。

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

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

3.3 粒的關系

粗糙集模型中,從不同角度、不同層次看待對象集、屬性集、屬性值集,能形成不同的粒結構、粒層及粒子,不同層的粒子之間存在粗細關系。

1)屬性集變化與粒度的關系

定義2設P,Q是論域U上的兩個等價關系,且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)成立。

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

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

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

2)屬性值變化與粒度的關系

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

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

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

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

3.4 知識約簡與規則提取

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

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

從粒計算的角度看,條件屬性的增加或刪除會改變粒空間的知識粒度,刪除屬性時知識粒度會增大,而添加屬性時知識粒度會減小,如圖3所示。屬性約簡的過程本質上是根據知識的變化不斷改變粒層和粒子結構的過程,直至得到決策劃分空間U/D的最大近似劃分。

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

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

4 結 語

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

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