覆蓋粒計算及其應用研究 碩士學位論文

1、學校代碼 10345 研究類型 應用基礎研究碩 士 學 位 論 文 題 目: 覆蓋粒計算及其應用研究 research on the covering and its application based on granular computing research on the covering and its applicationbased on granular computingthesis submitted tozhejiang normal universityfor the degree ofmaster of engineeringbyshuang liu(computer

2、software and theory)thesis supervisor: professor jiyi wangjune, 2011覆蓋粒計算及其應用研究摘 要粒計算是研究基于多層次粒結構的思維方法、問題求解方法、信息處理模式及其相關理論、技術和工具的學科。它覆蓋了所有和粒度相關的理論、方法和技術，主要用于對不確定、不準確、不完整信息的處理，對大規(guī)模海量的數據和對復雜問題的求解。粗糙集作為粒計算的一個重要分支，在理論和應用上不斷取得豐碩成果的同時，也得到了廣泛有意義的推廣。而覆蓋廣義粗糙集理論是pawlak粗糙集理論在劃分基礎上推廣到覆蓋建立起來的，它是研究與覆蓋相關的理論體系及其應用，由

3、于它是在粗糙集理論上的關系推廣，有關粗糙集的一些理論和應用并不一定在覆蓋廣義粗糙集下適用。因此，本文的主要內容是在粒計算思想理論背景下，研究與覆蓋相關的理論及其應用。具體研究工作如下：一、在面向基于粗糙集理論的動態(tài)信息系統(tǒng)規(guī)則挖掘的研究中，利用覆蓋粒計算相關理論提出了一種能消除引起差異信息系統(tǒng)規(guī)則挖掘中不一致因素的公理化方法。實驗結果表明，在保持時間復雜度不變的情況下，利用改進的規(guī)則挖掘算法，通過消除不一致因素而獲得的規(guī)則能更全面和更大程度地反映條件屬性值變化與決策變化趨勢之間的內在聯(lián)系。二、在面向沖突分析的研究中，在粒計算思想理論背景下，首次提出了“關聯(lián)沖突”的概念。利用覆蓋沖突分析策略,通

4、過“服務資源”實例建立了關聯(lián)沖突分析的合理泛化模型，討論了關聯(lián)沖突過程中所可能引發(fā)異常的階段，并對不同階段引發(fā)的異常進行了詳細的分析，給出了具體的解決方案,從而完善了各個領域沖突的解決。三、在面向分類法準確性（單標簽和多標簽數據集）的研究中，利用拓撲覆蓋鄰域理論，給出了尋找覆蓋系統(tǒng)上重疊元素的相關公理化方法。在粒計算的思維體系背景下，以實例輔證，給出了獨立于數據標簽和不同理想分類結果假設（一種假設為劃分，另一種假設為覆蓋）的評價分類法準確性的統(tǒng)一范式，為提高和評估分類法準確性的計算提供了重要的參考意義。最后，文章是在同一個思想理論背景下，討論了基于覆蓋的相關理論和應用。以上研究工作是覆蓋廣義粗

5、糙集的理論及其應用的補充和發(fā)展，充分的體現(xiàn)出了粒計算背景下知識發(fā)現(xiàn)理論和方法的獨特性，具有重要的理論意義及潛在的應用價值。 關鍵詞：粒計算；覆蓋；動態(tài)信息系統(tǒng)；規(guī)則挖掘；關聯(lián)沖突；分類research on the covering and its application based on granular computingabstractgranular computing (grc) is viewed as an interdisciplinary study of computation in nature, society and science, characterized by

6、 structured thinking, structured problem solving and structured information processing with an underlying notion of multiple levels of granulation. it consists of all the theories, methodologies, techniques and tools related to the granularity, which is mainly used to deal with uncertainty, imprecis

7、e and incomplete information and seek resolutions from the large-scale massive dataset or complicated problem. rough set, as a very important branch of grc, is being improving and perfecting on theory and application as well as is being extending widely and significantly. generalized rough set on co

8、vering is the one that partitions pawlak rough set theory is extended into coverings. it focuses on the study of covering, so that many theories and applications in the pawlak rough set are not tenable and suitable in the generalized rough set on covering. therefore, this dissertation will mainly ma

9、ke research on covering theories and its applications under background of grc, whose content is shown as follows:first of all, for the rules mining based on rough set theory in dynamic information system, a pre-process approach to eliminate the elements that cause inconsistence of rules mining in di

10、fference information system is proposed under the background of covering theory based on granular computing. experiment shows that relationship between the changes of condition attributes values and trend of decision-making can be fully reflected as much as possible by a modified rules mining algori

11、thm under the same time complexity through this pre-process approach.secondly, for the conflict analysis, associated-conflict is firstly introduced in the perspective of grc, and a reasonable and comprehensive approach to its analysis, using covering based on granular computing, is outlined. we argu

12、e that this model of associated-conflict analysis, given by the example of service-resource, will provide more profound insight for the conflict resolution in different fields.thirdly, for the accuracy of classification method on single label dataset or multi label dataset, a unified paradigm for th

13、e accuracy used to evaluate different classification methods, using topological covering based on grc, is presented, independent on number of data labels and different assumptions of ideal classification result(one assumption is partition, the other is covering). and some corresponding examples are

14、also discussed to illustrate the accuracy in different classification situations. this unified paradigm will provide important reference value for the evaluation and improvement of accuracy of classification method.in brief, this paper discusses theories and applications related to the covering unde

15、r the same theory background, and it can be treated as supplement and development of generalized rough set on covering. and it reflects the specificity on theories, methodologies, techniques and tools of knowledge discovery under the background of grc, with significant referred and applied value in

16、the future. key words: grc; covering; dynamic information system; rules mining; associated-conflict; classification目 錄摘 要iabstractiii目 錄v第一章 緒 論11.1粒計算11.1.1粒計算提出背景11.1.2粒計算任務和目標21.1.3粒計算基本要素和理論構成21.1.4粒計算研究方向與方法51.1.5粒計算基本思想和實質61.2覆蓋廣義粗糙集理論61.2.1覆蓋廣義粗糙集的研究背景71.2.2覆蓋廣義粗糙集的國內外研究現(xiàn)狀81.3本文研究的意義、目標、方法和主要

17、內容以及創(chuàng)新點81.3.1本文研究的意義81.3.2本文研究的目標81.3.3本文研究的方法91.3.4本文研究的主要內容以及創(chuàng)新點9第二章 粒計算的獨特魅力11 以孤立點挖掘為例112.1引言112.2引起孤立點的原因122.3孤立點挖掘方法的思想描述122.4討論132.5小結15第三章 覆蓋粒計算在基于粗糙集的動態(tài)信息系統(tǒng)規(guī)則挖掘中的應用173.1引言173.2預備知識173.3規(guī)則挖掘193.3.1動態(tài)信息系統(tǒng)中不一致性的辨識和消除193.2.2規(guī)則挖掘算法203.4實例分析223.5小結24第四章 基于覆蓋粒計算的關聯(lián)沖突分析264.1引言264.2預備知識274.3粒計算背景下的相

18、關工作274.4粒計算視角下的關聯(lián)沖突294.4.1關聯(lián)沖突定義304.4.2關聯(lián)沖突分析建模304.5討論374.6小結39第五章 基于覆蓋粒計算的分類準確性研究405.1引言405.2預備知識415.3討論425.3.1理想分類結果假設為劃分425.3.2理想分類結果假設為覆蓋445.4粒計算視角下的分類準確性統(tǒng)一范式455.5多標簽數據分類準確性探究475.6小結50第六章 總結與展望526.1總結526.2展望53參考文獻54攻讀碩士學位期間取得的研究成果61致 謝62浙江師范大學學位論文獨創(chuàng)性聲明63學位論文使用授權聲明63第一章 緒 論1.1粒計算 粒計算（granular com

19、puting, grc）是一門飛速發(fā)展的新學科，它是由美國學者t.y.lin于1997年提出的1。短短十幾年的發(fā)展已經見證了它對科學特別是計算機科學的作用和影響。諸多國內外學者就粒計算的基本理論和方法做了大量的工作2-12。但為粒計算下一個正式的、精確的、能夠廣為接受的定義仍然是一件困難的事情。人們對粒計算的描述是建立在對它的直覺認識上的：粒計算是研究基于多層次粒結構的思維方法、問題求解方法、信息處理模式及其相關理論、技術和工具的學科。作為軟計算科學的一個重要分支，它覆蓋了所有和粒度相關的理論、方法和技術，主要用于對不確定、不準確、不完整信息的處理，對大規(guī)模海量的數據和對復雜問題的求解，正逐漸

20、成為人工智能研究領域的熱點之一。1.1.1粒計算提出背景研究粒計算有許多原因。其一是一致性：現(xiàn)實世界充滿了結構和層次，它們體現(xiàn)在各種自然系統(tǒng)、社會系統(tǒng)和人工系統(tǒng)之中。因此，人們對現(xiàn)實世界的感知、理解、解釋和表示也是有結構、分層次的。zadeh將人類的認知能力概括為：粒化、組織和因果推理13。?；菍⒁粋€整體分割成部分，每個部分是擁有相同、相似性質的個體的集合。組織是將松散的個體聯(lián)系在一起，形成有著內在聯(lián)系的整體。因果推理是找出原因與結果之間的必然聯(lián)系。粒計算模型應該能描述這三種能力。因而粒計算的結構和現(xiàn)實世界的結構、人們的思維模式及行為方式是一致的。其二是系統(tǒng)性：粒計算的結構提供了對所解決的問

21、題多視角、多層次的理解、概括和操作。作為一個整體，粒計算提供的思維模式和行為方式是系統(tǒng)的、完整的。其三是簡化性：粒計算是提倡對問題進行不同層次的抽象和處理。在抽象過程中，可以只重視主要特性而忽略不相關的細節(jié)，從而達到對問題的簡化。其四是靈活性：粒計算的結構允許人們在不同的時間、不同的情況下，將注意力集中在不同的層次及層與層之間的自然過渡上，縮放和轉承是靈活多變的。其五是有效性：用粒計算指導的思維模式和行為方式將復雜問題分解成若干小問題。這種分而治之的方法是非常實用的，可以運用到不同的領域。其六是經濟性：粒計算尋求在不同粒度上的近似解。這樣的方法可以提高效率、降低成本。其七是容忍性：通過使用不同

22、信息粒度，粒計算可以容忍不確定、不完全或有噪音的信息，從而獲得具有魯棒性的解決方案。1.1.2粒計算任務和目標粒計算的形成綜合了許多學科的科研成果14，它的理論建立在對各個領域的共性進行概括、總結和整理之上，形成了對問題求解的普遍適用的原理、方法和策略。在過去的若干年中，許多學者對粒計算的具體模式和方法進行了研究。同時和粒計算原理相似的研究還在不斷地出現(xiàn)，只是在不同的領域中運用了略微不同的名詞和術語。將粒計算作為一個獨立的學科研究可以防止這種不必要的重復勞動。 (1) 粒計算的任務作為一個新興的研究領域，粒計算是一門關于問題求解的藝術。它有著兩項特殊的任務：其一是從各個不同的領域中概括出它們的

23、共性，不考慮它們低層次上的差異，從而提煉出抽象的、高層次的、綜合的認識；其二是將特定領域中隱含的結構明確化，以期總結出獨立于具體領域的普遍原理。 (2) 粒計算的目標粒計算之所以新且獨特，并不完全在于一組具體的方法和策略，而在于提出一個統(tǒng)一的框架，對這些方法和策略進行全面的理解及綜合。通過對粒計算的研究試圖達到以下目標：將隱式的結構顯式化；將不明顯的原理明顯化；將特定領域的特殊原理普遍化；將下意識的行為變成有意識的行為。1.1.3粒計算基本要素和理論構成 (1) 粒計算的基本要素14, 15 (a) 粒粒是粒計算的初始概念，是粒計算研究對象的單位，是求解問題的基本單位，等同于數據庫中的記錄，集

24、合中的元素或子集。我們稱最小的、不可分或不需要再分解的粒為基本粒，即最低層次的粒稱為基本粒，它可以是模糊的，也可以是精確的。粒具有雙重身份，它可以是某個整體中相對獨立的一個部分，也可以是一些粒共同組成的一個粒。所有的粒都具有內在屬性、外在屬性和環(huán)境屬性。當粒作為整體時，所要考慮的是粒的內在屬性，內在屬性由粒所擁有的元素決定。當粒作為部分時，所要考慮的是粒的外在屬性，由于具有外在屬性，粒就能夠被人們直接認識。粒的環(huán)境屬性是指粒對外部環(huán)境變化的應對情況，對其內在屬性和外在屬性的保持與調整以及對外部環(huán)境的影響和回應。粒的雙重身份決定了它的內在屬性通常需要強調其它所包含的細小個體的不同特性，是對它內部

25、各個基本組成成分性質的描述，而其外在屬性則是強調把它作為一個整體時所體現(xiàn)出的綜合特性。 (b) 層次粒存在于特定的層次中，人們在粒計算的不同層次中研究不同類型的粒，這些粒之間是有聯(lián)系的，同一層次的粒與粒之間可以是相交的關系也可以是層疊的關系，它們是該層次上研究的主體。層次中每一個粒表述了一個特定的?；^點。所有的?；^點相互補充、相互呼應，完整表達了在這個層次上對同一個問題的描述。每個層次都具有內在屬性、外在屬性、環(huán)境屬性，同一層次的粒屬性共同體現(xiàn)本層次特性。 在問題求解中，選擇在最合適的粒度層次上產生對一個問題的描述，能幫助更好更快地解決問題。較高層次包含較低層次，或者由較低層次組成。較高層

26、次為較低層次提供背景和約束。較高層次一般由較高集成度和較高結合力的粒組成。每一層次都存在一定程度的獨立性。任意兩層次之間的連接和交互是通過偏序關系的傳遞性和橋接原理來表示和體現(xiàn)的。粒計算模型的主要作用是能夠在不同粒度層次上進行問題求解，使不同粒度層次上的解能夠進行相互轉化。 (c) 分層結構 分層結構由若干個層次組成，層次間的遞進反映了由表及里、由抽象到具體、由粗糙到細致、由籠統(tǒng)到具體的變化。這種遞進是有序的，高層次會對低層次進行約束，并為低層次的描述提供背景。一個高層次的粒可以分解為若干個低層次的粒。相反，若干個低層次的?？梢越M合成一個高層次的粒。低層次的粒為高層次的粒提供更詳細的描述或者更

27、多的信息。另一個方面，高層次的粒將與本層次的不相關的細節(jié)忽略掉，為低層次的粒提供更粗粒度的描述。 (d) 粒結構在粒計算研究中強調的是全面、整體的觀點，而不是局部、離散的觀點。若要達到該目標，不僅要考慮一個分層結構中的多個層次，還需要將多個分層結構綜合考慮。粒結構包括三個要素，即粒的內在結構、粒的結構、粒的總體結構，它是多層次和多個分層結構的結合。粒計算借助于其他學科的哲學思想和方法論，并將它們抽象成為與具體領域無關的方法和策略。它的獨特性體現(xiàn)在用系統(tǒng)的、結構化的理解和方法來解決復雜問題。對復雜問題的全面理解通常是多視角的，從每一個視角著眼的理解又是多層次的。由此可以得出，粒計算的過程就是對復

28、雜問題的求解過程。它的結果表現(xiàn)為一個多視角、多層次的粒結構。這個粒結構是對復雜問題的系統(tǒng)且近似的描述和解答。 (2) 粒計算的理論構成7, 8 目前，粒計算有3個主要理論以及其它一些非主流理論：其一是詞計算理論：人類思考、判斷、推理主要是用語言，而語言是一個很粗的粒，如何用語言進行推理判斷，這就是詞計算。其二是商空間理論：商空間理論把概念用子集表示，不同粒的概念體現(xiàn)為不同粒的子集，一簇概念構成空間的一個劃分商空間，不同的概念簇就構成了不同的商空間。故粒計算，就是研究在給定知識基上的各種子集合之間的關系和轉換，以及對同一問題取不同的適當的粒，從對不同的粒的研究中，綜合獲取對原問題的了解。其三是粗

29、糙集理論：粗糙集理論于1982年由pawlak提出，它是一種刻劃不完整性、不確定性的數學工具，主要解決信息粒的近似方面的問題。另外許多學者也在研究粒計算，并將各種相關理論用于粒計算，有鄰域系統(tǒng)粒計算、信息熵粒計算、概念格粒計算、覆蓋粒計算、進化粒模型、基于相容粒度空間的粒計算模型以及各模型相互交叉整合的模型方法等，在許多領域中得以實現(xiàn)或應用。1.1.4粒計算研究方向與方法粒計算的形成和發(fā)展積累了多種思想、模型、范式、方法論、技術及工具。對粒計算的研究應該著眼于三個觀點2：粒計算的哲學思想觀點、方法論觀點及計算模式觀點。從哲學思想觀點考慮，粒計算試圖將人類的認知方式抽象化、形式化，從而提煉出結構

30、化的思維模式，而結構化的思維模式是人類智能的重要體現(xiàn)，它對設計基于知識的信息系統(tǒng)有著非常重要的影響，它有兩個基本假設：一個是所有問題都可以視作是其內在要素之間的網絡狀或分層結構的關聯(lián)，另一個是所有的問題都有著類似的模式和特征；從方法論觀點考慮，粒計算著重研究系統(tǒng)化的方法和技術，將問題求解的過程規(guī)范為結構化的、自上而下的逐步求精過程；從計算模式觀點考慮，粒計算關注于結構化的信息處理。信息處理是有層次的，其研究領域涉及抽象的信息處理、人腦中的信息處理及計算機中的信息處理。計算模式是方法論的具體表現(xiàn)形式。在計算機學科中，人們通常將興趣集中在基于計算機的信息處理模型上，并將其獨立出來進行分析。粒計算的

31、哲學研究基于粒結構的思維方式。基本問題7, 10, 15包括：如何定義粒、層次及分層結構的內在屬性、外在屬性和環(huán)境屬性；如何定義它們的關系；如何準確表達它們的關系；如何實現(xiàn)它們的關聯(lián)和切花；如何使它們的綜合功能最大化。哲學層面的研究是抽象的，同時又是方法論和計算模式的前提和保障。粒計算的方法論致力于將粒計算哲學思想具體到問題求解的方法、技術和工具的研究和開發(fā)中去。需要考慮到粒計算方法的有效性、可靠性、準確性、簡便性、計算成本和價值。對于不同的應用還需考慮其問題的特定及限制。粒計算的信息處理強調以計算機為主體的信息處理與以人為主體的信息處理的差別。一方面，以計算機為主體的信息處理依靠人來制定、設

32、計、實施和優(yōu)化；另一方面，計算機的信息處理也促進方法論的研究。粒計算的哲學思想和方法論的完善為計算機的信息處理實踐提供了可以依據的準繩和保障，計算機的信息處理實踐反過來也會促進對粒計算哲學思想和方法論的研究，成為支持粒計算哲學思想的有力證據和改善粒計算方法論的原動力?？傊绾味x粒（?；┮约叭绾芜x擇合適的粒度是粒計算解決問題的首要任務6, 9。1.1.5粒計算基本思想和實質粒計算從不同粒層次上研究問題，從人類求解問題的經驗方法中提取基本原理如粒、層次、等級。從人類思考和求解問題上看，“人類以粒的觀點看世界”，“人們觀察、衡量、概括和推理的實體都是?！?6。當人們面對復雜的、難于準確把握的問

33、題時由于能力有限，通常不是采用系統(tǒng)、精確的方法去追求問題的最優(yōu)解，而是通過逐步嘗試的辦法達到有限的、合理的目標，也就是采用由粗到細、不斷求精的多粒度分析法，避免復雜的計算，從而獲得足夠滿足的解，使得原來看似非多項式的難解問題迎刃而解。人類智能的一個公認特點，就是人們能從極不相同的粒上觀察和分析同一問題。人們能在不同粒的世界上進行問題求解，且能夠很快地從一個粒世界跳轉到另一個粒世界，往返自如，毫無困難。這種處理不同粒世界的能力，正是人類問題求解的強有力的表現(xiàn)，這也正是粒計算的基本思想4。粒計算方法是人工智能領域中的一種新理念和新方法，它覆蓋了所有和粒度相關的理論、方法和技術，在可以容忍的程度內，

34、主要用于對不確定、不準確、不完整信息的處理，對大規(guī)模海量的數據和對復雜問題的求解，使其達到可處理性、魯棒性、小代價和諧調性。粒計算的實質4就是通過選擇合適的粒度，來尋找一種較好的、近似的解決方案，從而降低問題求解的難度。而事實上，從真實世界上看，許多自然系統(tǒng)、社會系統(tǒng)、人工系統(tǒng)都是基于層次的，粒計算可以真實自然地表示這類系統(tǒng)。從簡化問題上看，多層系統(tǒng)的不同層次關注不同的粒特征，粒計算忽略了不必要和不相關的細節(jié)，只關注適當層次，從而簡化了問題。從實用角度上看，許多問題是不完整的、不確定的，或者含有模糊信息，很難區(qū)分元素，只能認為是粒。且在許多實際問題中也不要求精確解，或者獲取精確信息的代價不菲，

35、粒計算可以提高效率和降低代價。1.2覆蓋廣義粗糙集理論定義1.117 設是非空有限論域，是上的一簇子集且，對于任意，如果，那么為的一個劃分。定義1.233 設是非空有限論域，是上的一簇子集，如果中任一子集非空且，則為的一個覆蓋。1.2.1覆蓋廣義粗糙集的研究背景隨著計算機及網絡的日益普及，豐富的數據與貧乏的知識之間的矛盾日漸突出。不同領域的人都希望能從復雜的數據中得到自己所需要的知識，因此數據挖掘這門學科就應運而生了。該學科涉及分類、概念形成和數據分析。這些都需要對不完全和不充分的信息進行處理，圍繞這個問題產生了許多理論，如模糊理論、神經網絡、商空間理論、詞計算、粗糙集理論等。而其中的粗糙集理

36、論17于20世紀80年代提出以來，無論從理論上還是從應用上都取得了豐碩的成果，尤其在數據挖掘領域里18。它是通過不可區(qū)分關系為不完全和不充分信息的處理提供了一套系統(tǒng)的方法。通常，人們用一組屬性來描述事物，不可區(qū)分關系就是由這些事物相應的屬性值來定義的。如果兩個事物對于這組屬性的屬性值相等，也就是說具有相同的描述，就認為它們是不可區(qū)分的。從集合中關系這個角度來看，這種不可區(qū)分關系實際上就是等價關系。這樣，所有具有相同描述的事物構成一個等價類，而所有的等價類構成所考慮事物的一個劃分。在粗糙集理論中，這些等價類又稱為初等集，若干個初等集的并稱為確定。利用這個劃分，任意的事物的集合可以用兩個確定集來上

37、下逼近，這兩個確定集分別是該事物集合的上近似和下近似。它無需提供問題所需處理的數據集合之外的任何先驗信息，對問題的不確定性的描述或處理是比較客觀的。由于這個理論未包含處理不精確或不確定原始數據的機制，所以與概率論、模糊數學和證據理論等其他處理不確定或不精確問題的理論有很強的互補性。 而隨著粗糙集理論得到廣泛的應用以來，為使該理論能有更大的應用空間，人們對pawlak粗糙集理論進行了許多有意義的推廣，如將等價關系放寬為相容關系19、相似關系20、一般二元關系21；與模糊理論結合，將粗糙集理論推廣到模糊粗糙集理論22和廣義模糊粗糙集理論23；將經典粗糙集模型推廣到變精度粗糙集模型24；從等價關系等

38、同于劃分這個角度出發(fā)，zakowski把劃分放寬為覆蓋25,將pawlak粗糙集理論推廣到覆蓋廣義粗糙集理論。1.2.2覆蓋廣義粗糙集的國內外研究現(xiàn)狀 然而，自從pawlak粗糙集理論被推廣到覆蓋廣義粗糙集理論之后，國內外學者對其做了大量的研究。文獻26-53, 54-58對覆蓋廣義粗糙集理論進行了深入研究，其中文獻30討論了覆蓋廣義粗糙集的近似算子，文獻29主要研究覆蓋上下近似運算分別成為kuratowski閉包和內部運算的充分必要條件，文獻27-28主要研究了覆蓋廣義粗糙集中一階集合運算，文獻26主要結合形式概念分析來研究覆蓋廣義粗糙集，文獻31, 53討論了廣義粗糙集理論的代數結構，文獻

39、49, 57對基于關系的廣義粗糙集進行了研究，文獻33, 43, 44, 54, 56對在覆蓋廣義粗糙集理論下的約簡和不確定性度量進行了研究，文獻34-36, 39, 41-42, 45-48, 51, 58對覆蓋廣義粗糙集理論中的上下近似運算進行了公理化的研究，文獻38, 40, 52分別對覆蓋廣義粗糙模糊集和拓撲相關性質進行了研究，而文獻60-63對變精度的覆蓋廣義粗糙集理論及其模型進行了研究，以及其他的一些有關覆蓋廣義粗糙集理論的研究和總結32, 50, 55, 59。就應用方面而言，覆蓋廣義粗糙集理論已應用于沖突分析37、信息檢索64等領域。1.3本文研究的意義、目標、方法和主要內容以

40、及創(chuàng)新點1.3.1本文研究的意義 由于覆蓋廣義粗糙集理論是將pawlak粗糙集理論在劃分基礎上推廣到覆蓋而建立起來的，而覆蓋廣義粗糙集理論主要研究與覆蓋相關的理論體系及應用，所以有關粗糙集一些理論和應用并不一定在覆蓋廣義粗糙集下適用，那么在粒計算思想理論背景下研究覆蓋廣義粗糙集的相關理論和應用就顯的十分有意義。1.3.2本文研究的目標 雖然覆蓋廣義粗糙集有了一定的理論基礎和應用領域，但與粗糙集相比，需要不斷豐富其理論基礎和應用領域，而繼續(xù)建立覆蓋近似運算公理化理論體系、覆蓋約簡及近似性度量和不斷尋求覆蓋廣義粗糙集的適用方向是進一步研究的具體目標，本文旨在對覆蓋廣義粗糙集的應用基礎進行研究。1.

41、3.3本文研究的方法、技術路線及可行性分析本文將采用由淺入深、并行開展的研究方法。首先，介紹了粒計算思想理論體系的新穎性以及獨特性以孤立點挖掘為例。其次，在粒計算思想理論體系下，利用覆蓋相關理論分別對基于粗糙集的動態(tài)信息系統(tǒng)規(guī)則挖掘、關聯(lián)沖突分析、分類準確率三個方面進行獨立研究。 (1) 在基于粗糙集的動態(tài)信息系統(tǒng)規(guī)則挖掘中的應用研究中，主要利用條件屬性和決策屬性的交叉一致性來尋找引起差異信息系統(tǒng)中的不一致因素，然后利用改進的規(guī)則挖掘算法通過實驗對比來實現(xiàn)。(2) 在面向沖突分析的研究中，將沖突看作是在不同結構層上的?；^程，提出關聯(lián)沖突的概念，給出其形式化的定義，然后并對其進行分析和建模，最

42、后給出關聯(lián)沖突過程中所可能引發(fā)異常的階段，將對不同階段引發(fā)的異常進行詳細的分析(3) 在面向分類準確性研究中，利用拓撲覆蓋鄰域理論來尋找覆蓋系統(tǒng)上重疊元素，然后在粒計算的思維體系背景下，以實例輔證，采用折中方式給出獨立于數據標簽和理想分類結果假設的評價分類法準確性的統(tǒng)一范式。 以上提出的研究方法和技術路線是在前人對覆蓋廣義粗糙集理論和應用以及相應領域研究基礎上的再探索。雖然涉及領域比較寬泛，但都是在粒計算背景下研究的與覆蓋相關的理論和應用，所以本文實施和所采用的技術路線是可行的。1.3.4本文研究的主要內容以及創(chuàng)新點本文主要是在粒計算的思想理論背景下研究與覆蓋相關的理論及其應用。具體包括以下六

43、章內容： 第一章為緒論。首先介紹了粒計算的相關理論知識；然后介紹了覆蓋廣義粗糙集的研究背景，分析了國內外研究現(xiàn)狀；最后介紹了本文的研究意義、目標、方法和主要內容以及創(chuàng)新點。 第二章為粒計算的獨特魅力。本章主要討論了粒計算的新穎性和獨特性以孤立點挖掘為例，創(chuàng)新性地給出了孤立點挖掘總的指導原則和具體實施的流程圖，為孤立點挖掘算法的選擇、改進和創(chuàng)新提供了實際的參考價值，以此來揭示粒計算的獨特思維模式和研究方法，進而體現(xiàn)本文的寫作意圖即受粒計算思想與理論的影響，獲取與覆蓋相關的創(chuàng)新思想來源。 第三章為覆蓋粒計算在基于粗糙集的動態(tài)信息系統(tǒng)規(guī)則挖掘中的應用研究。本章針對差異信息系統(tǒng)構造過程中會引起新的不一

44、致這個問題，利用覆蓋粒計算相關理論提出了一種新的能消除這種不一致因素的公理化方法。實驗結果表明，在保持時間復雜度不變的情況下，利用改進的規(guī)則挖掘算法，通過消除不一致因素而獲得的規(guī)則更全面和更大程度地反映了條件屬性值變化與決策變化趨勢之間的內在聯(lián)系。 第四章為基于覆蓋粒計算的關聯(lián)沖突分析。本章在粒計算思想理論背景下，首次提出了“關聯(lián)沖突”的概念，利用覆蓋沖突分析策略,通過“服務資源”實例建立了關聯(lián)沖突分析的合理泛化模型，討論了關聯(lián)沖突過程中所可能引發(fā)異常的階段，并對不同階段引發(fā)的異常進行了詳細的分析，給出了具體的解決方案。 第五章為基于覆蓋粒計算的分類準確性研究。在面向分類法準確性（單標簽和多標

45、簽數據集）的研究中，本章利用拓撲覆蓋鄰域理論，給出了一種新的尋找覆蓋系統(tǒng)上重疊元素的相關的公理化方法。在粒計算的思維體系背景下，以實例輔證，創(chuàng)新性地給出了獨立于數據標簽和理想分類結果假設（一種假設為劃分，另一種假設為覆蓋）的評價分類法準確性的統(tǒng)一范式。需要說明的是，本章對于分類法準確性統(tǒng)一范式的給出采取的折中處理方式值得借鑒。 第六章為總結與展望。文章在同一個思想理論背景下，討論了基于覆蓋的相關理論和應用，它是覆蓋廣義粗糙集的理論及其應用的補充和發(fā)展，并且更體現(xiàn)出了粒計算背景下知識發(fā)現(xiàn)理論和方法的獨特性，具有重要的理論意義及潛在的應用價值，同時對該領域理論和應用研究的發(fā)展方向提出了新的展望。

46、此外，本文收錄了一些該領域內最新的研究成果，以期能為科研工作者認識和深入研究提供便利。第二章 粒計算的獨特魅力 以孤立點挖掘為例 本章主要討論粒計算的新穎性和獨特性，以此來揭示粒計算的獨特思維模式和研究方法，從中體現(xiàn)出本文的寫作意圖，在粒計算思想理論背景下的覆蓋理論及其研究的問題即受粒計算思想與理論的影響，獲取與覆蓋相關的創(chuàng)新思想來源。以孤立點挖掘為例，在粒計算的思想理論背景下，給出了孤立點挖掘總的指導原則和具體實施的流程圖，為孤立點挖掘算法的選擇、改進和創(chuàng)新提供了實際的參考價值，將會對孤立點的挖掘產生一定深遠的影響。2.1引言孤立點也即異常點65，是指數據集中不符合一般模型的那些對象，即和其

47、他數據有著不同的性質。對于某些度量而言，這些對象與數據集中的其他數據有著顯著的不同。目前，針對不同的數據挖掘任務和挖掘背景，一些數據挖掘算法盡量去減少孤立點帶來的影響或者甚至是從數據集中消除他們，然而，這可能會導致一些重要的隱秘信息的缺失。換句話說，孤立點本身在諸如入侵檢測等事件中有著特殊的意義，它可以表示入侵的異常行為。因此，孤立點的檢測和分析（即孤立點挖掘）在數據挖掘中就顯得非常重要。一般，孤立點挖掘問題可以看作兩個子問題：一個是在給定的數據集中定義一個什么樣的數據可以被認為是孤立點或不一致的；另一個是找到一個有效的方法去挖掘這些定義的孤立點。在過去的一個多世紀里，人們對孤立點的研究經歷了

48、幾個興衰交替?，F(xiàn)在，它再一次成為信息科學里的一個活躍分支，并在數據挖掘領域里受到越來越廣泛的關注。孤立點挖掘之所以有著廣泛的應用，是與其所在的實際領域里的特殊性決定，諸如入侵檢測、市場營銷和醫(yī)療等領域。孤立點的引起是有一些原因的66，同時相應的也有一些檢測或挖掘孤立點的方法67-76。然而，每種方法總是存在著不可避免的缺點或者略勢，沒有一個普遍有效的方法來檢查數據集中的孤立點77。特別在檢測孤立點的過程中，如何選擇一個合適的檢測方法沒有一個普遍的準則，而且就孤立點目前研究的熱點和未來的發(fā)展來說77，挖掘任務會變得非常困難。因此，尋求一個適用于孤立點挖掘的總的指導原則就成為了最急需要解決的問題。

49、2.2引起孤立點的原因 (1) 數據來自不同的類 一個數據不同于其他數據，可能因為它來自不同的類或屬于不同的類型。例如，一個在進行信用卡欺詐的人可能被歸為不合法的信用卡用戶而不是非法的用戶。相同地，諸如欺詐、入侵、疾病暴發(fā)和異常的實驗結果等都可以被認為是造成孤立點的例子。 (2) 自然變異在統(tǒng)計知識的背景下，一些諸如正太分布等模型可以用來模擬許多數據集的分布。隨著數據點離正太分布的中心距離的增加，該點出現(xiàn)的可能性就會急劇地減少。換句話說，對于大多數點來說，離中心（平均對象）越近，不同于這個平均對象的可能性就越小。例如，假定一個男性特別的高，當他獨自一人時，沒有人與之形成對比，他沒有什么特別之處

50、。但是一旦于其他人在高度上做比較時，他就是一個孤立點，在這群人里他是一個高度上的極值。通常這些極值點或沒有任何變異的點作為孤立點是非常有意思的。 (3) 數據度量和收集導致的誤差 在數據收集和度量的過程中，所導致的誤差是引起孤立點的另一個根源。例如，由于人為失誤、設備誤差或者數據本身具有噪音導致所記錄的度量值不正確。一般情況下都會刪除這些孤立點，因為他們不能提供有用的信息，相反他們會降低數據分析的質量。但這些數據能反映出一些有用的信息，例如誤差的根源是人為、設備還是其他的原因造成的等。2.3孤立點挖掘方法的思想描述 (1) 基于統(tǒng)計模型的孤立點檢測方法67, 68許多檢測技術首先都會構造一個數

51、據模型。孤立點就是這些不能夠很好擬合這個模型的數據對象。例如，數據的分布模型可以通過估計概率分布的參數來構造。如果一個數據對象不能夠很好的擬合這個模型，它可能不服從這個分布，那它就是孤立點。如果模型是簇的集合，那么孤立點會明顯的不屬于任何簇。或者當使用回歸模型時，孤立點會相對的遠離模型的預測值。 (2) 基于距離的孤立點檢測方法69, 70目前，許多孤立點檢測的方法都是基于距離的。孤立點就是遠離大多數點的點。當數據分散在二維或三維的圖中時，我們可以通過基于距離的方法，用肉眼或簡單方法分辨出哪些點是孤立點。 (3) 基于偏差的孤立點檢測方法71, 72我們也可以通過比較一組數據的主要特征來檢測孤

52、立點。根據問題的要求，可以事先給定數據所對應的一些特征，那么孤立點就是這些不能像特征所描述的那樣的點。 (4) 基于密度的孤立點檢測方法73, 74數據分布的密度估計是相對可以通過計算得到的，尤其是對數據之間存在距離的點來說。那些處于低密度的數據點相對地遠離他們的鄰居可以被認為是孤立點。但是考慮到數據集可能有不同的密度區(qū)域，因此當一個點所在的區(qū)域的密度明顯低于它的大多數鄰居的時候，它可以被歸為孤立點。 (5) 基于聚類的孤立點檢測方法75, 76聚類分析和孤立點檢測有不同的目標。聚類分析通常被用于發(fā)現(xiàn)強相關的對象，而孤立點檢測則被用來發(fā)現(xiàn)那些和強相關的對象沒有關系的對象。顯然，聚類可以用于孤立

53、點檢測。2.4討論 在數據挖掘中，粒計算有著廣泛的應用78-80。數據的粒化，尤其是復雜數據的粒化，是基于粒計算的數據挖掘的必要前提。?；某潭戎苯佑绊憯祿诰虻男屎陀嬎銖碗s度。既要避免粒度過粗而造成求解失敗，又要避免粒度過細造成信息的冗余而導致求解效率低下。因此，選擇最優(yōu)?；潭仁橇Ｓ嬎銛祿诰虻年P鍵。另外，當?；某潭纫阎獣r，?；姆椒ㄖ苯記Q定了?；男省９铝Ⅻc挖掘是一個將孤立點從數據集中分離出來的過程。通過對引起孤立點的原因進行分析，我們發(fā)現(xiàn)孤立點大都是各種情況里的不尋常的對象。他們由突發(fā)事件、人為因素或環(huán)境原因等所引起的，所以我們需要不同的實施過程將它們分離出來。事實上，從粒計算的

54、觀點來看，分離的過程就是?；倪^程，并且上面所列出的孤立點的檢測方法都是基于?；枷氲?。正如zadeh所認為13的：人類的認知能力概括為粒化、組織和因果推理，人們對孤立點挖據方法的設計正是人類認知能力尤其?；芰Φ姆磻?，基于距離、密度和聚類的孤立點檢測方法可以看作為基于空間?；姆椒ǎ诮y(tǒng)計模型和偏離的孤立點檢測方法可以被看作為基于模糊匹配信息的?；椒?。而且分離的思想與粒度有著非常近的關聯(lián)，在不同的?；缴希ㄟ^使用一些特殊的方法或策略，我們可以選擇合適的粒度來縮小孤立點的檢測范圍，這樣就可以提高孤立點挖掘的效率并降低挖掘的時間復雜度，尤其對大數據集中的孤立點挖掘來說效果和意義更

55、明顯。 我們換個角度來考慮孤立點檢測的方法。粒計算新穎和獨特的原因不完全在于提供具體的方法和策略，而在于提出了一個統(tǒng)一的框架，對這些方法和策略進行全面理解及綜合。如果我們通過粒結構將知識和系統(tǒng)合為一體。由此產生的結果是，人們能將普遍適用的粒計算哲學有意識地運用到各自面對的問題中去，從而對問題進行更有效的求解。同時，對高層次的粒結構的認識可以防止人們對相同、相似理論和方法的重復發(fā)現(xiàn)和發(fā)明，避免浪費精力。因此，將粒計算的新穎和獨特之處運用到孤立點挖掘中，有如下指導原則：通過對引起孤立點原因和孤立點檢測方法的分析，結合粒計算的觀點，從方法本身的高層粒結構出發(fā)，獨立于檢測方法的孤立點挖掘總的指導原則是

56、粒化觀點，同時表明了在選擇合理的粒度之前，它在孤立點挖掘中扮演著非常重要的角色，根據不同的檢測目標，有著不同的?；瓌t。而且?；^點是一種新的求解系統(tǒng)，它是孤立點檢測過程中首先并且唯一開始著手的思想。換句話說，對孤立點檢測方法的選擇、改進和創(chuàng)新，它提供了統(tǒng)一的、正面的和有效的說明。在信息科學快速發(fā)展的背景下，它將對孤立點的挖掘產生深遠的影響。圖2.1是基于粒計算的孤立點挖掘的統(tǒng)一過程框架圖，它是粒計算思想應用到孤立點挖掘中的很好體現(xiàn)，其中有陰影部分是背景知識：圖2.1 孤立點挖據的統(tǒng)一實施過程2.5小結 對于粒計算而言，其思想和理論在孤立點挖掘上得到了充分的體現(xiàn)。在對孤立點挖掘方法的分析和概括

57、的基礎上，總結出了獨立于方法之上的方法論原則（?；笇г瓌t），使得孤立點挖掘的著手點集中在?；乃枷肷希苊饬嗽S多重復性的工作和不必要的麻煩，這是粒計算任務和目標的體現(xiàn)。而孤立點挖掘的統(tǒng)一實施過程流程圖體現(xiàn)了粒計算的其他方面：挖掘過程本身是有先后順序之分，因此是具有一定層次性；而挖掘過程中，粒度大小的選擇即合適層次上的?；垣@取?；瓌t用以選擇、創(chuàng)新和改進挖掘方法；由于粒度大小選擇上原因導致挖掘結果不是很滿意，需要調節(jié)粒度，因此，這是一個循環(huán)反復的過程（體現(xiàn)出了分層結構以及粒結構），其間需要粒計算理論注入其中以求對所要解決的問題選擇合理的層次和粒度。對于孤立點挖掘而言，?；^點是孤立點挖掘方法的選擇、改進和創(chuàng)新的切入點，它的引入使得人們對孤立點挖掘的研究更廣泛和更集中即不斷的將新