- 相關(guān)推薦
淺談粒度計算
摘要：粒度是新近興起的人工智能研究領(lǐng)域的一個(gè)方向，本文簡(jiǎn)單介紹粒度計算的主要三個(gè)方法，以及之間的關(guān)系。 關(guān)鍵詞：粒度計算、模糊邏輯、商空間理論、粗糙集理論。 一．引言 人們在思考問(wèn)題時(shí)，或者是先從總體進(jìn)行觀(guān)察，然后再逐步深入地研究各個(gè)部分的情況；或先從各個(gè)方面對同一問(wèn)題進(jìn)行不同側面的了解，然后對它們進(jìn)行綜合；或是上面兩種方法的組合，即時(shí)而從各側面對事物進(jìn)行了解，然后進(jìn)行綜合觀(guān)察，時(shí)而綜合觀(guān)察后，對不甚了解的部分再進(jìn)行觀(guān)察……總之，根據需要從不同側面、不同角度反復對事物進(jìn)行了解、分析、綜合、推理.最后得出事物本質(zhì)的性質(zhì)和結論. 人工智能研究者對人類(lèi)這種能力進(jìn)行了深入地研究，并建立了各種形式化的模型.本文要介紹的粒度計算,就是對上述問(wèn)題的研究的一個(gè)方面. 人工智能最主要的目的是，為人類(lèi)的某些智能行為建立適當的形式化模型，以便利用計算機能再顯人的智能的部分功能。什么是人類(lèi)的最主要的智能，或者說(shuō)智能的最重要表現形式是什么。各家有不同的看法，如Simon等認為人的智能表現為，對問(wèn)題求解目標的搜索（Search）能力。比如學(xué)生在證明一道平面幾何題目時(shí)，進(jìn)行思考，“聰明的小孩”能很快地找到證明該結論的有關(guān)的定理性質(zhì)，并很快地應用上去，從而就得到證明�！皵祵W(xué)能力差的學(xué)?笨贍芏?椅餮埃?也壞膠鮮實(shí)畝ɡ硨托災剩?評慈迫ィ?艿貌壞街っ韉囊?歟籔awlak[P1]則認為人的智能表現為對事物（事件、行為、感知等）的分類(lèi)（Classification）能力。如平時(shí)我們說(shuō)某醫生本事大，就是這位醫生能從病人的癥狀中，正確地診斷出病人是患什么�。ǚ诸�(lèi)能力！分出患什么病來(lái)）等等。我們認為“人類(lèi)智能的公認特點(diǎn)，就是人們能從極不相同的粒度(Granularity)上觀(guān)察和分析同一問(wèn)題。人們不僅能在不同粒度的世界上進(jìn)行問(wèn)題求解，而且能夠很快地從一個(gè)粒度世界跳到另一個(gè)粒度的世界，往返自如，毫無(wú)困難。這種處理不同世界的能力，正是人類(lèi)問(wèn)題求解的強有力的表現”[ZH1]。還有很多不同的理解，人們正是從這些不同的理解分別建立各自的模型和相關(guān)的理論和方法。 粒度計算目前國際上有三個(gè)主要的模型和方法，下面簡(jiǎn)單進(jìn)行介紹。 二. 三種不同的模型 下面簡(jiǎn)單介紹有關(guān)“粒度計算”的三個(gè)不同的模型和方法。 什么是粒度，顧名思義，就是取不同大小的對象。也就是說(shuō)，將原來(lái)“粗粒度”的大對象分割為若干“細粒度”的小對象，或者把若干小對象合并成一個(gè)大的粗粒度對象，進(jìn)行研究。 最近Zadeh在[ZA1]-[ZA3]中,討論模糊信息粒度理論時(shí)，提出人類(lèi)認知的三個(gè)主要概念，即粒度(granulation)、組織(organization)、因果(causation)(粒度包括將全體分解為部分，組織包括從部分集成為全體，因果包括因果的關(guān)聯(lián)）。并進(jìn)一步提出粒度計算。他認為，粒度計算是一把大傘它覆蓋了所有有關(guān)粒度的理論、方法論、技術(shù)和工具的研究。指出：“粗略地說(shuō)，粒度計算是模糊信息粒度理論的超集，而粗糙集理論和區間計算是粒度數學(xué)的子集”。 Zadeh 的工作激起了學(xué)術(shù)界對粒度計算研究的興趣，Y.Y.Yao和他的合作者對粒度計算進(jìn)行了一系列的研究[Y1]-[Y3]并將它應用于數據挖掘等領(lǐng)域，其工作的要點(diǎn)是用決策邏輯語(yǔ)言(DL-語(yǔ)言)來(lái)描述集合的粒度(用滿(mǎn)足公式f元素的集合，來(lái)定義等價(jià)類(lèi)m(f))，建立概念之間的IF-THEN關(guān)系與粒度集合之間的包含關(guān)系的聯(lián)系，并提出利用由所有劃分構成的格，來(lái)求解一致分類(lèi)問(wèn)題。這些研究為知識挖掘提供了一些新的方法和角度。 按Zadeh粒度計算的定義,我們提出的商空間理論和Pawlak的粗糙集理論都屬于“粒度計算”范疇。 目前有關(guān)粒度計算的理論與方法，主要有三個(gè)。一是Zadeh的“詞計算理論”（Theory of Works Computing），一是Pawlak的“粗糙集理論”（Theory of Rough Set），另一個(gè)是我們提出的“商空間理論”（Theory of Quotient Space）。 下面簡(jiǎn)單介紹三者的內容： 1. 詞計算理論： Zadeh認為人類(lèi)在進(jìn)行思考、判斷、推理時(shí)主要是用語(yǔ)言進(jìn)行的，而語(yǔ)言是一個(gè)很粗的“粒度”，如我們說(shuō)“九寨溝的風(fēng)景很美”，其中“很美”這個(gè)詞就比較“龐統”，也就是說(shuō)其粒度很粗，如何利用語(yǔ)言進(jìn)行推理判斷，這就是要進(jìn)行“詞計算”，早在二十世紀六十年代Zadeh提出模糊集理論，就是“詞計算”的雛型。沿Zadeh的模糊集論的方向，用模糊數學(xué)的方法進(jìn)行有關(guān)粒度計算的方法和理論的研究，就構成“粒度計算”的一個(gè)非常重要的方法和方向。這也是人們比較熟悉的一個(gè)方法。 2. 粗糙集理論： 波蘭學(xué)者Pawlak[P1]在二十世紀八十年代，提出的粗糙集理論，他提出一個(gè)假設：人的智能(知識)就是一種分類(lèi)的能力，這個(gè)假設可能不是很完備，但卻非常精練。在此基礎上提出，概念可以用論域中的子集來(lái)表示，于是在論域中給定一組子集族，或說(shuō)給定一個(gè)劃分（所謂劃分，是指將X分成兩兩不相交的子集之并）。從數學(xué)上知道，給定X上的一個(gè)劃分，等價(jià)于在X上給定一個(gè)等價(jià)關(guān)系R。Pawlak稱(chēng)之為在論域上給定了一個(gè)知識基(X,R)。然后討論一個(gè)一般的概念x（X中的一個(gè)子集），如何用知識基中的知識來(lái)表示，就是用知識基中的集合的并來(lái)表示。對那些無(wú)法用(X,R)中的集合的并來(lái)表示的集合,他借用拓撲中的內核和閉包的概念,引入R-下近似R-(x)（相當于x的內核）和R-上近似R-(x)（相當于x的閉包），當R-(x)¹R-(x)時(shí),就稱(chēng)x為粗糙集.從而創(chuàng )立了“粗糙集理論”。目前粗糙集理論已被廣泛應用于各個(gè)領(lǐng)域，特別是數據挖掘領(lǐng)域，并獲得成功。 3.基于商空間的粒度計算. 我們認為概念可以用子集來(lái)表示,不同粒度的概念就體現為不同粒度的子集,一簇概念就構成空間的一個(gè)劃分----商空間(知識基),不同的概念簇就構成不同的商空間. 故粒度計算,就是研究在給定知識基上的各種子集合之間的關(guān)系和轉換.以及對同一問(wèn)題,取不同的適當的粒度,從對不同的粒度的研究中,綜合獲取對原問(wèn)題的了解.這種對粒度的理解與模糊集對粒度的理解不完全一樣. 下面簡(jiǎn)單介紹基于商空間的粒度計算。 3.1商空間模型下的推理模型 商空間的模型用一個(gè)三元組來(lái)表示，即(X,F,T),其中X是論域,F是屬性集,T是X上的拓撲結構.當我們取粗粒度時(shí),即給定一個(gè)等價(jià)關(guān)系R (或說(shuō)一個(gè)劃分),于是我們說(shuō)得到一個(gè)對應于R的商集記為[X],它對應于的三元組為([X],[F],[T]),稱(chēng)之為對應于R的商空間.商空間理論就是研究各商空間之間的關(guān)系、各商空間的合成、綜合、分解和在商空間中的推理。 在這個(gè)模型下,可建立對應的推理模型,并有如下的性質(zhì). A. 商空間模型中推理的“保假原理”（或“無(wú)解保持原理”）. B. 商空間模型中推理合成的“保真原理”. 所謂“保假原理”是指若一命題在粗粒度空間中是假的，則該命題在比它細的商空間中一定也無(wú)解。 所謂“保真原理”，是指，若命題在兩個(gè)較粗粒度的商空間中是真的，則（在一定條件下），在其合成的商空間中對應的問(wèn)題也是真的。 這兩個(gè)原理在商空間模型的推理中起到很重要的作用，如若我們要對一個(gè)問(wèn)題進(jìn)行求解，當問(wèn)題十分復雜時(shí)，常先進(jìn)行初步分析，即取一個(gè)較粗粒度商空間，將問(wèn)題化成在該空間上的對應的問(wèn)題，然后進(jìn)行求解，若得出該問(wèn)題在粗粒度空間中是無(wú)解，則由“保假原理”，立即得原問(wèn)題是無(wú)解的。因為粗粒度的空間規模小，故計算量也少，這樣我們就可以以很少的計算量得出所要的結果，達到“事半功倍”的目的。 同樣利用“保真原理”也可達到降低求解的復雜性目的，設在兩個(gè)較粗空間X1、X2上進(jìn)行求解,得出對應的問(wèn)題有解.利用“保真原理”可得，在其合成的空間X3上問(wèn)題也有解。設X1、X2的規模分別為s1、s2。因為一般情況下，X3的規模最大可達到s1s2。于是將原來(lái)要求解規模為s1s2空間中的問(wèn)題，化成求解規模分別為s1、s2的兩個(gè)空間中的問(wèn)題。即將復雜性從“相乘”降為“相加”。 四．商空間理論、粗糙集理論和模糊集理論之間的關(guān)系 4.1在模型上 三者都是描述人類(lèi)能按不同粒度來(lái)處理事物的能力的模型. 商空間理論、粗糙集理論認為概念可以用子集來(lái)表示，不同粒度的概念可以用不同大小的子集來(lái)表示，所有這些表示可以用等價(jià)關(guān)系來(lái)描述。 詞計算理論認為概念是用“詞”來(lái)表示，而描述“詞”的有效的方法就是模糊集理論。 4.2.研究的對象 商空間理論、粗糙集理論、詞理論都將所討論的對象的集合構成論域，但討論對象之間的關(guān)系時(shí)，卻各有不同。 粗糙集理論的原型估計是由關(guān)系數據庫抽象而得的，故其模型為(X,F)(其中X是論域,F是屬性集),即通過(guò)元素的不同屬性值，來(lái)描述元素之間的關(guān)系,并用元素按不同屬性進(jìn)行的分類(lèi)來(lái)表示不同的概念粒度。 商空間理論的原型是分層遞階方法，故其模型為(X,F,T)(其中X是論域,F是屬性集,T是X上的拓撲結構)即除了元素的屬性外，還引入元素之間的關(guān)系T（用拓撲來(lái)描述），從這個(gè)意義上來(lái)說(shuō),粗糙集理論是商空間理論的一個(gè)簡(jiǎn)單的特例。當然各自研究的著(zhù)重點(diǎn)和側重點(diǎn)不同。 當給定一個(gè)等價(jià)關(guān)系時(shí)，粗糙集理論認為是給定一個(gè)知識基，然后討論任給的一個(gè)概念（集合）在這個(gè)知識基上如何被表示為知識基上集合之并,以及之間的關(guān)系。粗糙集理論主要利用集合的基數(元素個(gè)數)之間的關(guān)系,來(lái)描述概念之間的隸屬關(guān)系，這樣在一定程度上與模糊集概念聯(lián)系起來(lái)。另外，粗糙集理論還討論如何利用屬性來(lái)最簡(jiǎn)單地表示所對應的知識基，這就是所謂“簡(jiǎn)約”問(wèn)題。但因模型缺乏描述元素之間的相互關(guān)系的手段，故很難提取有結構論域中有關(guān)結構所提供的信息。當然結構在一定意義下也可以看成是元素的某種屬性，但這種屬性是多元屬性(要用多元函數來(lái)表達)，一般不能表示為f(x),而要用f(x,y,..)表示,如距離要用d(x,y)表示. 商空間理論著(zhù)重點(diǎn)不同,它不是只針對給定的商空間(知識基)來(lái)討論知識的表達問(wèn)題,而是在所有可能的商空間中,找出最合適的商空間,利用從不同商空間(從不同角度)觀(guān)察同一問(wèn)題,以便得到對問(wèn)題不同角度的理解,最終綜合成對問(wèn)題總的理解(解).它的求解過(guò)程是在“由所有商空間組成的半序格”中運動(dòng)轉換的過(guò)程.故可看成是宏觀(guān)的粒度計算.而粗糙集理論是在給定的商空間中的運動(dòng),故可看成是微觀(guān)的粒度計算. 詞計算理論與商空間理論、粗糙集理論稍為不同,它主要研究(從粒度計算的觀(guān)點(diǎn)來(lái)看它)如何描述由詞界定的不同粒度的對象,它更擅長(cháng)描述由形容詞、副詞表達的不同粒度的概念,如非常好、很好、好、很不錯、還好,…等等. 因為這些詞有程度不同的差別,故在一定意義下,詞計算理論也給出了描述元素之間的關(guān)系,但只限于由屬性的強弱程度不同所形成的關(guān)系. 從理論上說(shuō),將商空間理論、粗糙集理論看成是“精確”的粒度計算,那么都可在其模型上引入模糊的概念,得模糊的商空間理論,和模糊的粗糙集理論. 在[ZH2]中我們證明：模糊的等價(jià)關(guān)系,等價(jià)于在某個(gè)商空間上的歸一等腰距離。即,可將它化成有結構的商空間。于是這三者都可統一地用多尺度的商空間理論來(lái)表示.如設商空間理論中原來(lái)的結構是一距離d1(x,y),這個(gè)d1是元素在空間”位置”關(guān)系的描述, 而由模糊概念引入的距離d2,可以看成是元素之間的屬性關(guān)系的描述. 屬性是對元素個(gè)體性質(zhì)的描述,而尺度是對元素之間關(guān)系的描述(當然也可看成是多元屬性). 若屬性值是取值于一個(gè)良序集上時(shí),多可用模糊集來(lái)描述. 將三者有機地結合起來(lái)，對粒度計算將有重大意義。 4.3. 結構的重要性 最后闡述在粒度計算中結構的重要性，在問(wèn)題求解時(shí)，人們多從一組前提出發(fā)，希望由它通過(guò)一系列的推導，得到結論。若將每個(gè)步驟用箭頭相連，則得到由前提到目標的一條有向路�；蚋话�，問(wèn)題求解可看成是在某有結構的空間中，求一條由前提到目標的有向路（或一條路徑），于是當空間的結構是拓撲空間時(shí)，關(guān)于問(wèn)題求解的解的存在性問(wèn)題，就等價(jià)于在空間中回答“前提與目標是否處在同一線(xiàn)連通成份中”。而求解問(wèn)題，就是在有解情況下，求從前提到目標的一條有向路徑。 利用商空間中粗空間對細空間的“保假性”，（即：若問(wèn)題在粗空間中無(wú)解，則在比它細的空間一定也無(wú)解）通過(guò)合理的分層遞階，可大大降低問(wèn)題求解的復雜性。 我們對常遇到的結構如：半序結構、距離結構以及一般拓撲結構，其對應的商空間的構成及不同商空間的綜合都給出有效的構造性的算法。 對什么情況下分層遞可以降低計算復雜性，能降低多少等，我們在[Z1]中也進(jìn)行了詳細地論述。 在[ZH3]中還把統計推斷方法引入商空間模型,為多層信息綜合、不確定推理、定性推理等，建立數學(xué)模型和相應算法,有效降低了計算復雜性。 有結構的模型在實(shí)際問(wèn)題求解中是經(jīng)常遇到的，如地理信息中其地理位置之間的關(guān)系就是一個(gè)距離結構；在數據倉庫中各數據之間的關(guān)系可用半序來(lái)描述，它也是一種結構；又在路徑規劃中對象所處空間的位置關(guān)系，就是一種距離的結構；在數據挖掘中的規則發(fā)現，所有的規則全體按其包含關(guān)系就構成半序結構等等。在這些有結構的對象中進(jìn)行問(wèn)題求解利用基于商空間理論的粒度計算將是很有效的。 商空間的方法與目前流行的“粗糙集”方法相同之處在于：都是利用等價(jià)類(lèi)來(lái)描述“粒度”,都是用“粒度”來(lái)描述概念。但討論的著(zhù)重點(diǎn)有所不同，我們的著(zhù)重點(diǎn)是研究不同粒度世界之間的互相轉換、互相依存的關(guān)系，是描述空間關(guān)系學(xué)的理論；而目前的粒度計算(如粗糙集理論等)主要是研究粒度的表示、刻劃和粒度與概念之間的依存關(guān)系。更主要的不同在于：我們的理論是在論域元素之間存在有拓撲關(guān)系的情況下進(jìn)行研究的，即論域是一個(gè)拓撲空間，而現在的粗糙集理論，其論域只是簡(jiǎn)單的點(diǎn)集，元素之間沒(méi)有拓撲關(guān)系(只是商集理論，而不是商空間理論)，故它們討論的是無(wú)結構的特殊情況。 另外，粗糙集是在給定的知識基上求解對應的問(wèn)題，如求集合的R-上近似和R-下近似，我們是在(X,T)中討論各商空間之間的關(guān)系，求相應的（各種意義下）上近似空間和下近似空間。從這個(gè)角度看，可以說(shuō)粗糙集是微觀(guān)的粒度計算，商空間理論是宏觀(guān)的粒度計算。這兩個(gè)理論都是建立在等價(jià)關(guān)系之上，所有可以將兩者結合起來(lái)。 Zadeh 所討論的粒度計算與Pawlak和我們所討論的粒度問(wèn)題又有些不同，他主要是討論粒度的表示問(wèn)題，他們認為人類(lèi)是用語(yǔ)言進(jìn)行各種思考和推理的，不同的詞就表示不同的粒度，那么如何表示它們呢？一般來(lái)說(shuō)用“語(yǔ)言”、“詞(word）”來(lái)表示的概念，牽涉到“詞計算”問(wèn)題。而詞計算，現在最流行的方法是“模糊數學(xué)”的方法，于是他得出的結論是：模糊數學(xué)應是粒度計算的主要工具之一。 依Zadeh的看法，Pawlak和我們討論的粒度是“清晰的粒度”，而他自己討論的是“模糊粒度”。 如何將模糊集的方法引入商空間理論中來(lái)，這可從幾方面著(zhù)手進(jìn)行，一是在論域X上引入模糊集；二是在結構T上引入模糊拓撲結構；三是對我們的核心概念等價(jià)關(guān)系，引入模糊概念。 以上簡(jiǎn)單介紹了商空間理論、詞計算理論、粗糙集等粒度計算方法之間的關(guān)系�？梢钥闯鲞@三個(gè)不同的粒度計算理論，從思考問(wèn)題的出發(fā)點(diǎn)和解決問(wèn)題的任務(wù)，都不盡相同，各有千秋。但是三者都有一個(gè)共同的特點(diǎn)，那就是都考慮到人類(lèi)智能中，有從不同粒度思考問(wèn)題的這一特點(diǎn)。如何將三者的優(yōu)點(diǎn)結合起來(lái)，形成更強有力的粒度計算的方法和理論，是今后一個(gè)重要的研究課題。一個(gè)明顯可進(jìn)行的研究是：將商空間理論與粗糙集方法相結合，或說(shuō)將粗糙集方法引入商空間理論中來(lái)，或說(shuō)在商空間理論中同時(shí)討論微觀(guān)的粒度計算問(wèn)題，將微觀(guān)和宏觀(guān)的粒度計算統一起來(lái)，構成一個(gè)更加完整的粒度計算理論和方法，將會(huì )更有效的。 [P1] Z. Pawlak, Rough Sets Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Dordrecht, Boston, London, 1991. [Y1] Y. Y. Yao, Granular Computing: basic issues and possible solutions. Proc. of fifth Joint Conference on Information Sciences, Vol.I, Atlantic City, New Jersey, USA, 2000:186-189. [Y2] Y.Y. Yao, and X. Li, Comparison of rough-set and interval-srt models for uncertain reasoning, Fundamental Informatics, 27,1996：289-298. [Y3] Y.Y. Yao and Ning Zhong, Granular Computing Using Information Table, in T.Y. Lin, Y.Y Yao, and L. A. Zadeh (editors) Data Miming, Rough Sets and Granular Computing, Physica-Verlag, 2000:102-124. [ZA1] L. A. Zadeh, Fuzzy logic=computing with words, IEEE Transactions on Fuzzy Systems, 4, 1996：103-111. [ZA2] L. A. Zadeh, Towards a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic, Fuzzy Sets and Systems, 19, 1997：111-127. [ZA3] L. A. Zadeh, Announcement of GrC, 1997, [ZH1] 張鈸，張鈴《問(wèn)題求解的理論及應用》,清華大學(xué)出版社,1990)（版. Bo Zhang and Ling Zhang, Theory and Application of Problem Solving, North-Holland, Elsevier Science Publishers B.V. 1992） [ZH2] 張鈴 張鈸 模糊商空間理論（模糊粒度計算方法）“軟件學(xué)報”，14（4）2003：770-776. [ZH3] Zhang Ling，Zhang Bo，Statistical Genetic Algorithm， Chinese Journal of Software Vol.8,No.5:335-344(張鈴,張鈸,統計遺傳算法《軟件學(xué)報》8(5),1997:335-344。【淺談粒度計算】相關(guān)文章：
淺談湖泊沉積物粒度的環(huán)境含義03-07
淺談?dòng)嬎銠C審計的運用03-22
淺談企業(yè)計算機輔助審計03-20
淺談?dòng)嬎銠C專(zhuān)業(yè)教學(xué)模式11-23
淺談道路勘測設計中計算機的工程計算03-01
淺談?dòng)嬎銠C輔助審計技術(shù)的應用03-24