【正文】 是一個很粗的粒，如何用語言進行推理判斷，這就是詞計算。信息處 理是有層次的，其研究領(lǐng)域涉及抽象的信息處理、人腦中的信息處理及計算機中的信息處理。對于不同的應(yīng)用還需考慮其問題的特定及限制。人類智能的一個公認特點，就是人們能從極不相同的粒上觀察和分析同一問題。且在許多實際問題中也不要求精確解，或者獲取精確信息的代價不菲， 粒計算可以 提高效率和降低代價。 它是通過不可區(qū)分關(guān)系為不完全和不充分信息的處理提供了一套系統(tǒng)的方法。由于這個理論未包含處理不精確或不確定原始數(shù)據(jù)的機制，所以與概率論、模糊數(shù)學(xué)和證據(jù)理論等其他處理不確定或不精確問題的理論有很強的互補性。首先 ，介紹了粒計算思想理論體系的新穎性以及獨特性 —— 以孤立點挖掘為例。 首先介紹了粒計算的相關(guān)理論知識；然后介紹了覆蓋廣義粗糙集的研究背景，分析了 國內(nèi)外研究現(xiàn)狀；最后介紹了本文的研究意義、目標(biāo)、方法和主要內(nèi)容 以 及創(chuàng)新點。 第五章為基于覆蓋粒計算的分類準(zhǔn)確性研究。以孤立點挖掘為例， 在粒 計算的思想理論背景下， 給出了孤立點挖掘 總 的指導(dǎo)原則和具體實施的流程圖，為孤立點挖掘算法 的 選擇、改進和創(chuàng)新提供了實際的參考價值 ，將會對孤立點的挖掘產(chǎn)生 一定 深遠的影響 ?，F(xiàn)在，它再一次成為信息科學(xué)里的一個活躍分支，并在數(shù)據(jù)挖掘領(lǐng)域里受到越來越廣泛的關(guān)注。相同地，諸如欺詐、入侵、疾病暴發(fā)和異常的實驗結(jié)果等都可以被認為是 造成 孤立點的 例子 。例如，由于人為失誤、設(shè)備誤差或者數(shù)據(jù)本身具有噪音導(dǎo)致所記錄的度量值不正確?；蛘弋?dāng)使用回歸模型時，孤立點會相對的遠離模型 的 預(yù)測值。但是考慮到數(shù)據(jù)集可能有不同的密度區(qū)域，因此當(dāng)一個點所在的區(qū)域的密度明顯低于它的大多數(shù)鄰居的時候，它可以被歸為孤立點。因此，選擇最優(yōu)?；潭仁橇Ｓ嬎銛?shù)據(jù)挖掘的關(guān)鍵。 我們換個角度來考慮孤立點檢測的方法。在信息科學(xué)快速發(fā)展的背景下，它將對孤立點的挖掘產(chǎn)生深遠的影響。 17 第 三 章 覆蓋 粒計算 在基于粗糙集的動態(tài)信息系統(tǒng) 規(guī)則挖掘中的應(yīng)用 在動態(tài)信息系統(tǒng)中，采用粗糙集方法來挖掘系統(tǒng)中潛在的規(guī)則。 預(yù)備知識 一個信息系統(tǒng) S 表示為一個四元組： { , , , }S U A V f? ，其中 U 是對象的集合，即論域； A 是屬性集（ A CN D? ， CN 為條件屬性集， D 為決策屬性集）；aaAVV??，aV 表示 a 的 值域； :f U A V??是一個信息函數(shù)。記39。 39。39。D 為差異信息系統(tǒng)的條件屬性和決策屬性。39。()card D d? ()dn? （ 差異決策表有 m 行 n列，決策屬性 d 列 ） ，構(gòu)造 ?? 上 第 p 行的 辨識矩陣 , ( 1)( ) [ ]i j m nM p w ??? ， 其中如果第 三 章 覆蓋粒計算在基于粗糙集的動態(tài)信息系統(tǒng)規(guī)則挖 掘中的應(yīng)用 19 39。 因此，對于 動態(tài)信息系統(tǒng)的狀態(tài)序列 ? 中 決策表 存在著 一致或不一致 這個問題， 隨著時間和場景的變化， 就 會 有 引起 差異信息系統(tǒng) ji?? 中不一致的因素 包含引起 構(gòu)成 差異信息系統(tǒng) ji?? 的兩個決策信息表中的不一致 的 因素的并 ，那么 ji?? 中可能 會產(chǎn)生新的不一致因素 。 39。 39。而 在 差異條件屬性 39。39。證畢！ 例 39。39。( ) 1icard Y ? 的 39。39。i i jY Y X? 并且 {}iX X X?? ；否則 39。D 構(gòu)成的劃分按每個類所含記錄多少降序排列為 1 2 N{ , ,..., }Y Y Y Y? （ 39。 12. . . ( ) . . .a b e s s??? ? ? ? ? ? ? ? ? ?，定義 決 策 規(guī) 則 的 覆 蓋 廣 度 為39。重要度表明了屬性對于決策分類能力的貢獻程度。()[]D i ju ?= ( ) ( )[ ] [ ]D i D juu。 39。 39。e 是對決策屬性 e 變化趨勢的描述， 39。記 39。 但由于 客觀世界的不確 定 性問題通常表現(xiàn)為易變性和過程性，傳統(tǒng)的 粗糙 集很難體現(xiàn) 出 不確 定 性的變化過程和變化趨勢 ， 即 在信息系統(tǒng)中體現(xiàn)為 屬性隨著時間的推移而不斷地變化 [82, 83]。 對于孤立點挖掘而言， ?；^點是孤立點挖掘方法 的 選擇、改進和創(chuàng)新的切入點，它的引入使得人們對孤立點挖掘的研究更廣泛 和更 集中 即不斷的將新的粒化方法引入到孤立點挖掘中和只將挖掘任務(wù)放在?；乃枷肷线M行考慮 ，這樣一方面使得挖掘算法得到不斷改進和創(chuàng)新，另一方面 又 可以避免許多不必要的重復(fù)勞動。同時，對高層次的粒結(jié)構(gòu)的認識可以防止人們對相同、相似理論和方法的重復(fù)發(fā)現(xiàn)和發(fā)明，避免浪費精力 。他們由突發(fā)事件、人為因素或環(huán)境 原因 等所引起的，所以我們需要不同的實施過程將它們分離出來。 討論 在數(shù)據(jù)挖掘中，粒計算有著廣泛的應(yīng)用 [7880]。 (3) 基于偏差的孤立點檢測方法 [71, 72] 我們也可以通過比較一組數(shù)據(jù)的主要特征來檢測孤立點。孤立點就是這些不能夠很好擬合這個第二章 粒計算的獨特魅力 13 模型的數(shù)據(jù)對象。例如，假定一個男性特別的高， 當(dāng)他獨自一人 時 ，沒有人與之形成對比，他沒有什么特別之處。特別在檢測孤立點的過第二章 粒計算的獨特魅力 12 程中，如何選擇一個合適的檢測方法沒有一個普遍的準(zhǔn)則 ， 而且 就 孤立點目前研究的熱點和未來的發(fā)展 來說 [77]，挖掘 任務(wù) 會 變得 非常 困難 。換句話說，孤立點本身在 諸如入侵檢測等事件中有著特殊的意義，它可以表示入侵的異常行為。 第六章為總結(jié)與展望。 本章針對 差異信息系統(tǒng)構(gòu)造過程中會引起新的不一致這個問題， 利用覆蓋粒計算相關(guān)理論提出了一種 新的 能消除 這種 不一致因素的公理化方法。 以上提出的研究方法和技術(shù)路線是在前人對覆蓋廣義粗糙集理論和應(yīng)用以及相應(yīng)領(lǐng)域 研究基礎(chǔ)上的再探索。就應(yīng)用方面而言，覆蓋廣義粗糙集理論已應(yīng)用于沖突分析 [37]、信息檢索 [64]等領(lǐng)域。這樣，所有具有相同描述的事物構(gòu)成一個等價類，而所有的等價類構(gòu)成所考慮事物的一個劃分。不同領(lǐng)域的人都希望能從復(fù)雜的數(shù)據(jù)中得到自己所需要的知識，因此數(shù)據(jù)挖掘這門學(xué)科就應(yīng)運而生了。 粒計算的實質(zhì) [4]就是通過選擇合適的粒度，來尋找一種較好的、近似的解決方案，從而降低問題求解的難度。 總之，如何定義粒 （?；?以及如何選擇合適的粒度是粒計算解決問題的首要任第 一 章 緒 論 6 務(wù) [6, 9]。 基本 問題 [7, 10, 15]包括：如何定義粒、層次及分層結(jié)構(gòu)的內(nèi)在屬性、外在屬性和環(huán)境屬性；如何定義它們的關(guān)系；如何準(zhǔn)確表達它們的關(guān)系；如何實現(xiàn)它們的關(guān)聯(lián)和切花；如何使它們的綜合功能最大化。另外許多學(xué)者也在研究粒計算，并將各種相關(guān)理論用于粒計算，有鄰域系統(tǒng)粒計算 、信息熵粒計算、概念格粒計算、覆蓋粒計算 、進化粒模型、基于 相容粒度空間 的粒計算 模型 以及各模型相互交叉整合的模型方法等 ， 在許多領(lǐng)域中 得以 實現(xiàn)或應(yīng)用 。對復(fù)雜問題的全面理解通常是多視角的，從每一個視角著眼的理解又是多層次的。相反，若干個低層次的?？梢越M合成一個高層次的粒。較高層次為較低層次提供背景和約束。粒的環(huán) 境屬性是指粒對外部環(huán)境變化的應(yīng)對情況，對其內(nèi)在屬性和外在屬性的保 持與調(diào)整以及對外部環(huán)境的影響和回應(yīng)。 (2) 粒計算的目標(biāo) 粒計算之所以新且獨特，并不完全在于一組具體的方法和策略，而在于提出一個統(tǒng)一的框架，對這些方法和策略進行全面的理解及綜合。這樣的方法可以提高效率、降低成本。其二是系統(tǒng)性：粒計算的結(jié)構(gòu) 提供了對所解決 的問題多視角、多層次的理解、概括和操作。其一是一致性：現(xiàn)實世界充滿了結(jié)構(gòu)和層次，它們體現(xiàn)在各種自然系統(tǒng)、社會系統(tǒng)和人工系統(tǒng)之中。 Associatedconflict。 三、 在 面向分類法準(zhǔn)確 性 （單標(biāo)簽 和 多標(biāo)簽數(shù)據(jù)集） 的研究 中， 利用拓撲覆蓋鄰域理論，給出 了 尋找覆蓋系統(tǒng)上 重疊 元素的相關(guān)公理化 方法 。 它覆蓋了所有和粒度相關(guān)的理論、方法和技術(shù)，主要用于對不確定、不準(zhǔn)確、不完整信息的處理，對大規(guī)模海量的數(shù)據(jù)和對復(fù)雜問題的求解 。實驗 結(jié)果表明， 在保持時間復(fù)雜度不變的情況下，利用改進的規(guī)則挖掘算法 ，通過消除不一致因素而獲得的規(guī)則 能 更全面和更大程度地反映條件屬性值變化與決策變化趨勢之間的內(nèi)在聯(lián)系。 Covering。人們對粒計算的描述是建立在對它的直覺認識上的：粒計算是研究基于多層次粒結(jié)構(gòu)的思維方法、問題求解方法、信息處理模式及其相關(guān)理論、技術(shù)和工具的學(xué)科 。因果推理是找出原因與結(jié)果之間的必然聯(lián)系。其五是有效性：用粒計算指導(dǎo)的思維模式和行為方式將復(fù)雜問題分解成若干小問題。將粒計算作為一個獨立的學(xué)科研究可以防止這種不必要的重復(fù)勞動。所有的粒 都具有內(nèi)在屬性、外在屬性和環(huán)境屬性。 每個層次都具有內(nèi)在屬性、外在屬性、環(huán)境屬性，同一層次的粒屬性共同體現(xiàn)本層次特性。 (c) 分層結(jié)構(gòu) 分層結(jié)構(gòu)由若干個層次組成，層次間的遞進反映了由表及里、由抽象到具體、由粗糙到細致、由籠統(tǒng)到具體的變化。粒結(jié)構(gòu)包括三個要素，即粒的內(nèi)在結(jié)構(gòu)、粒的結(jié)構(gòu)、粒的總體結(jié)構(gòu)，它是多層次和多個分層結(jié)構(gòu)的結(jié)合 。 其二是 商空間理論：商空間理論把概念用子集表示，不同粒的概念體現(xiàn)為不同粒的子集，一簇概念構(gòu)成空間的一個劃分 —— 商空間，不同的概念簇就構(gòu)成了不同的商空間。計算模式是方法論的具體表現(xiàn)形式。 粒計算的信息處理強調(diào)以計算機為主體的信息處理與以人為主體的信息處理的差別。人們能在不同粒的世界上進行問題求解，且能夠很快地從一個粒世界跳轉(zhuǎn)到另一個粒世界，往返自如，毫無困難。 覆蓋廣義粗糙集 理論 定義 [17] 設(shè) U 是非空有限論域， P 是 U 上的一簇子集 且 PU? ， 對于任意第 一 章 緒 論 7 12,P P P? ， 如果 12PP?? ， 那么 P 為 U 的一個 劃分 。通常，人們用一組屬性來描述事物，不可區(qū)分關(guān)系就是由這些事物相應(yīng)的屬性值來定義的。 而隨著粗糙集理論得到廣泛的應(yīng)用以來 ， 為使該理論能有更大的應(yīng)用空間， 人們對 Pawlak 粗糙集理論進行了許多有意義的推廣，如將等價關(guān)系放寬為相容 關(guān)系 [19]、相似關(guān)系 [20]、一般二元關(guān)系 [21]；與模糊理論結(jié)合，將粗糙集理論推廣到模糊粗糙集理論 [22]和廣義模糊粗糙集理論 [23]；將經(jīng)典粗糙集模型推廣到變精度粗糙集模型 [24]；從等價關(guān)系等同于劃分這個角度出發(fā)， Zakowski 把劃分放寬為覆蓋 [25],將 Pawlak 粗第 一 章 緒 論 8 糙集理論推廣到覆蓋廣義粗糙集理論。 其次，在粒計算思想理論體系下，利用覆蓋相關(guān)理論分別對基于粗糙集的動態(tài)信息系統(tǒng)規(guī)則挖掘、關(guān)聯(lián)沖突分析、分類準(zhǔn)確率三個方面進行獨立研究。 第二章為 粒計算 的獨特魅力。 在 面向分類法準(zhǔn)確 性 （單標(biāo)簽 和 多標(biāo)簽數(shù)據(jù)集）的研究中，本章 利用拓撲覆蓋 鄰域理論，給出了 一種新的 尋找覆蓋系統(tǒng)上重 疊 元素的相關(guān)的公理化 方法 。 引言 孤立點也即異常點 [65]，是指數(shù)據(jù)集中不符合一般模型的那些對象 ，即和其他數(shù)據(jù)有著不同的性質(zhì)。孤立點挖掘之所以有著廣泛的應(yīng)用，是與其所在的實際領(lǐng)域里的特殊性決定，諸如入侵檢測、市場營銷和醫(yī)療等領(lǐng)域。 (2) 自然變異 在統(tǒng)計知識的背景下，一些諸如正太分布等模型可以用來模擬許多數(shù)據(jù)集 的分布 。一般情況下都會刪除這些孤立點，因為他們不能提供有用的信息，相反他們會降 低 數(shù)據(jù)分析的質(zhì)量。 (2) 基于距離的孤立點檢測方法 [69, 70] 目前 ，許多孤立點檢測的方法都是基于距離的。 (5) 基于聚類的孤立點檢測方法 [75, 76] 聚類分析和孤立點檢測有不同的目標(biāo)。另外，當(dāng)?；某潭纫阎獣r，?；姆椒ㄖ苯記Q定了粒化的效率 。粒計算新穎和獨特的原因 不完全 在于 提供具體的方法和策略， 而在于 提出了 一個統(tǒng)一的框架， 對 這些方法和策略進行 全面 理解及綜合 。 圖 是 基于粒計算的孤立點挖掘的統(tǒng)一過程框架圖，它是粒計算思想應(yīng)用到孤立點挖掘中的 很好 體現(xiàn)，其中有陰影部分是背景知識 ： 第二章 粒計算的獨特魅力 15 圖 孤立點挖據(jù)的統(tǒng)一實施過程 小結(jié) 對于粒計算而言，其思想 和 理論在孤立點挖掘上得到了充分的體現(xiàn)。對于這類問題，由于信息系統(tǒng)的不一致性以及 差異 信息系統(tǒng)構(gòu)造過程中的不確定性和差異性，規(guī)則挖掘的結(jié)果不甚理想 ： 在粒計算的思想理論背景下， 本章 將 覆蓋相關(guān)理論 運用到規(guī)則挖掘中 ，提出了一種消除引起差異信息系統(tǒng)規(guī) 則挖掘中不一致因素的方法。由于單個信息系統(tǒng)無法描述信息第 三 章 覆蓋粒計算在基于粗糙集的動態(tài)信息系統(tǒng)規(guī)則挖 掘中的應(yīng)用 18 和信息量隨時間和場景的變化 的狀態(tài) ，文獻 [84]中給出了信息變換函數(shù) :f T S ???的概念，函數(shù)的定義域是時間和場景的區(qū)域，其中 時間序列集合為 12{ , ,...}T t t? ，場景集合為 12{ , ,...}S s s? ， 狀態(tài)序列集1 1 2 2{ , ,...}t s t s? ? ??，每個iits?都 是一個決策表且論域、條件屬性、決策屬性均相同，屬性值隨著時間和場景的變化而變化。 39。 39。39。 由粗糙集理論可以得出，若信息系統(tǒng)iits?