覆蓋粒計(jì)算及其應(yīng)用研究 碩士學(xué)位論文

《覆蓋粒計(jì)算及其應(yīng)用研究 碩士學(xué)位論文》由會(huì)員分享，可在線閱讀，更多相關(guān)《覆蓋粒計(jì)算及其應(yīng)用研究 碩士學(xué)位論文（73頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 學(xué)校代碼 10345 研究類(lèi)型 應(yīng)用基礎(chǔ)研究 碩 士 學(xué) 位 論 文 題 目: 覆蓋粒計(jì)算及其應(yīng)用研究 Research on the Covering and Its Application Based on Granular Computing Research on the Covering and Its Application Based on Granular Computing Thes

2、is Submitted to Zhejiang Normal University for the degree of Master of Engineering By Shuang Liu (Computer Software and Theory) Thesis Supervisor: Professor Jiyi Wang June, 2011 摘 要 覆蓋粒計(jì)算及其應(yīng)用研究 摘 要 粒計(jì)算是研究基于多層次粒結(jié)構(gòu)的思維方法、問(wèn)題求解方法、信息處理模式及其相關(guān)理論、技術(shù)和工具的學(xué)科。它覆蓋了所有和粒度相關(guān)的理論、方法和技術(shù)，

3、主要用于對(duì)不確定、不準(zhǔn)確、不完整信息的處理，對(duì)大規(guī)模海量的數(shù)據(jù)和對(duì)復(fù)雜問(wèn)題的求解。粗糙集作為粒計(jì)算的一個(gè)重要分支，在理論和應(yīng)用上不斷取得豐碩成果的同時(shí)，也得到了廣泛有意義的推廣。而覆蓋廣義粗糙集理論是Pawlak粗糙集理論在劃分基礎(chǔ)上推廣到覆蓋建立起來(lái)的，它是研究與覆蓋相關(guān)的理論體系及其應(yīng)用，由于它是在粗糙集理論上的關(guān)系推廣，有關(guān)粗糙集的一些理論和應(yīng)用并不一定在覆蓋廣義粗糙集下適用。因此，本文的主要內(nèi)容是在粒計(jì)算思想理論背景下，研究與覆蓋相關(guān)的理論及其應(yīng)用。具體研究工作如下： 一、在面向基于粗糙集理論的動(dòng)態(tài)信息系統(tǒng)規(guī)則挖掘的研究中，利用覆蓋粒計(jì)算相關(guān)理論提出了一種能消除引起差異信息系統(tǒng)規(guī)則挖

4、掘中不一致因素的公理化方法。實(shí)驗(yàn)結(jié)果表明，在保持時(shí)間復(fù)雜度不變的情況下，利用改進(jìn)的規(guī)則挖掘算法，通過(guò)消除不一致因素而獲得的規(guī)則能更全面和更大程度地反映條件屬性值變化與決策變化趨勢(shì)之間的內(nèi)在聯(lián)系。 二、在面向沖突分析的研究中，在粒計(jì)算思想理論背景下，首次提出了“關(guān)聯(lián)沖突”的概念。利用覆蓋沖突分析策略,通過(guò)“服務(wù)—資源”實(shí)例建立了關(guān)聯(lián)沖突分析的合理泛化模型，討論了關(guān)聯(lián)沖突過(guò)程中所可能引發(fā)異常的階段，并對(duì)不同階段引發(fā)的異常進(jìn)行了詳細(xì)的分析，給出了具體的解決方案,從而完善了各個(gè)領(lǐng)域沖突的解決。 三、在面向分類(lèi)法準(zhǔn)確性（單標(biāo)簽和多標(biāo)簽數(shù)據(jù)集）的研究中，利用拓?fù)涓采w鄰域理論，給出了尋找覆蓋系統(tǒng)上重疊元

5、素的相關(guān)公理化方法。在粒計(jì)算的思維體系背景下，以實(shí)例輔證，給出了獨(dú)立于數(shù)據(jù)標(biāo)簽和不同理想分類(lèi)結(jié)果假設(shè)（一種假設(shè)為劃分，另一種假設(shè)為覆蓋）的評(píng)價(jià)分類(lèi)法準(zhǔn)確性的統(tǒng)一范式，為提高和評(píng)估分類(lèi)法準(zhǔn)確性的計(jì)算提供了重要的參考意義。 最后，文章是在同一個(gè)思想理論背景下，討論了基于覆蓋的相關(guān)理論和應(yīng)用。以上研究工作是覆蓋廣義粗糙集的理論及其應(yīng)用的補(bǔ)充和發(fā)展，充分的體現(xiàn)出了粒計(jì)算背景下知識(shí)發(fā)現(xiàn)理論和方法的獨(dú)特性，具有重要的理論意義及潛在的應(yīng)用價(jià)值。 關(guān)鍵詞：粒計(jì)算；覆蓋；動(dòng)態(tài)信息系統(tǒng)；規(guī)則挖掘；關(guān)聯(lián)沖突；分類(lèi) 61 ABSTRACT RESEARCH ON THE COVERING

6、 AND ITS APPLICATION BASED ON GRANULAR COMPUTING ABSTRACT Granular computing (GrC) is viewed as an interdisciplinary study of computation in nature, society and science, characterized by structured thinking, structured problem solving and structured information processing with an underlying

7、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, imprecise and incomplete information and seek resolutions from the large-scale massive dataset or complicated prob

8、lem. 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 covering is the one that partition’s Pawlak rough set theory is extended into covering’s. It focuses on the

9、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 make research on covering theories and its applications under background of GrC, whose content is shown as

10、 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 difference information system is proposed under the background of covering theory based on granular comp

11、uting. 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 algorithm under the same time complexity through this pre-process approach. Secondly, for the conflict anal

12、ysis, 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 argue that this model of associated-conflict analysis, given by the example of service-resource, will pr

13、ovide 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 the accuracy used to evaluate different classification methods, using topological covering based on

14、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 also discussed to illustrate the accuracy in different classification situations. This unified par

15、adigm 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 under the same theory background, and it can be treated as supplement and development of generalized

16、 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 the future. KEY WORDS: GrC; Covering; Dynamic Information System; Rules Mining; Associate

17、d-conflict; Classification 目 錄 目 錄 摘 要 I ABSTRACT III 目 錄 V 第一章 緒 論 1 1.1粒計(jì)算 1 1.1.1粒計(jì)算提出背景 1 1.1.2粒計(jì)算任務(wù)和目標(biāo) 2 1.1.3粒計(jì)算基本要素和理論構(gòu)成 2 1.1.4粒計(jì)算研究方向與方法 5 1.1.5粒計(jì)算基本思想和實(shí)質(zhì) 6 1.2覆蓋廣義粗糙集理論 6 1.2.1覆蓋廣義粗糙集的研究背景 7 1.2.2覆蓋廣義粗糙集的國(guó)內(nèi)外研究現(xiàn)狀 8 1.3本文研究的意義、目標(biāo)、方法和主要內(nèi)容以及創(chuàng)新點(diǎn) 8 1.3.1本文研究的意義 8

18、1.3.2本文研究的目標(biāo) 8 1.3.3本文研究的方法 9 1.3.4本文研究的主要內(nèi)容以及創(chuàng)新點(diǎn) 9 第二章 粒計(jì)算的獨(dú)特魅力 11 ——以孤立點(diǎn)挖掘?yàn)槔?11 2.1引言 11 2.2引起孤立點(diǎn)的原因 12 2.3孤立點(diǎn)挖掘方法的思想描述 12 2.4討論 13 2.5小結(jié) 15 第三章 覆蓋粒計(jì)算在基于粗糙集的動(dòng)態(tài)信息系統(tǒng)規(guī)則挖掘中的應(yīng)用 17 3.1引言 17 3.2預(yù)備知識(shí) 17 3.3規(guī)則挖掘 19 3.3.1動(dòng)態(tài)信息系統(tǒng)中不一致性的辨識(shí)和消除 19 3.2.2規(guī)則挖掘算法 20 3.4實(shí)例分析 22 3.5小結(jié) 24

19、 第四章 基于覆蓋粒計(jì)算的關(guān)聯(lián)沖突分析 26 4.1引言 26 4.2預(yù)備知識(shí) 27 4.3粒計(jì)算背景下的相關(guān)工作 27 4.4粒計(jì)算視角下的關(guān)聯(lián)沖突 29 4.4.1關(guān)聯(lián)沖突定義 30 4.4.2關(guān)聯(lián)沖突分析建模 30 4.5討論 37 4.6小結(jié) 39 第五章 基于覆蓋粒計(jì)算的分類(lèi)準(zhǔn)確性研究 40 5.1引言 40 5.2預(yù)備知識(shí) 41 5.3討論 42 5.3.1理想分類(lèi)結(jié)果假設(shè)為劃分 42 5.3.2理想分類(lèi)結(jié)果假設(shè)為覆蓋 44 5.4粒計(jì)算視角下的分類(lèi)準(zhǔn)確性統(tǒng)一范式 45 5.5多標(biāo)簽數(shù)據(jù)分類(lèi)準(zhǔn)確性探究 47 5.6小結(jié) 50 第六章 總結(jié)

20、與展望 52 6.1總結(jié) 52 6.2展望 53 參考文獻(xiàn) 54 攻讀碩士學(xué)位期間取得的研究成果 61 致 謝 62 浙江師范大學(xué)學(xué)位論文獨(dú)創(chuàng)性聲明 63 學(xué)位論文使用授權(quán)聲明 63 第一章 緒 論 第一章 緒 論 1.1粒計(jì)算 粒計(jì)算（Granular Computing, GrC）是一門(mén)飛速發(fā)展的新學(xué)科，它是由美國(guó)學(xué)者T.Y.Lin于1997年提出的[1]。短短十幾年的發(fā)展已經(jīng)見(jiàn)證了它對(duì)科學(xué)特別是計(jì)算機(jī)科學(xué)的作用和影響。諸多國(guó)內(nèi)外學(xué)者就粒計(jì)算的基本理論和方法做了大量的工作[2-12]。但為粒計(jì)算下一個(gè)正式的、精確的、能夠廣為接受的定義

21、仍然是一件困難的事情。人們對(duì)粒計(jì)算的描述是建立在對(duì)它的直覺(jué)認(rèn)識(shí)上的：粒計(jì)算是研究基于多層次粒結(jié)構(gòu)的思維方法、問(wèn)題求解方法、信息處理模式及其相關(guān)理論、技術(shù)和工具的學(xué)科。作為軟計(jì)算科學(xué)的一個(gè)重要分支，它覆蓋了所有和粒度相關(guān)的理論、方法和技術(shù)，主要用于對(duì)不確定、不準(zhǔn)確、不完整信息的處理，對(duì)大規(guī)模海量的數(shù)據(jù)和對(duì)復(fù)雜問(wèn)題的求解，正逐漸成為人工智能研究領(lǐng)域的熱點(diǎn)之一。 1.1.1粒計(jì)算提出背景 研究粒計(jì)算有許多原因。其一是一致性：現(xiàn)實(shí)世界充滿了結(jié)構(gòu)和層次，它們體現(xiàn)在各種自然系統(tǒng)、社會(huì)系統(tǒng)和人工系統(tǒng)之中。因此，人們對(duì)現(xiàn)實(shí)世界的感知、理解、解釋和表示也是有結(jié)構(gòu)、分層次的。Zadeh將人類(lèi)的認(rèn)知能力概括為：

22、?；⒔M織和因果推理[13]。?；菍⒁粋€(gè)整體分割成部分，每個(gè)部分是擁有相同、相似性質(zhì)的個(gè)體的集合。組織是將松散的個(gè)體聯(lián)系在一起，形成有著內(nèi)在聯(lián)系的整體。因果推理是找出原因與結(jié)果之間的必然聯(lián)系。粒計(jì)算模型應(yīng)該能描述這三種能力。因而粒計(jì)算的結(jié)構(gòu)和現(xiàn)實(shí)世界的結(jié)構(gòu)、人們的思維模式及行為方式是一致的。其二是系統(tǒng)性：粒計(jì)算的結(jié)構(gòu)提供了對(duì)所解決的問(wèn)題多視角、多層次的理解、概括和操作。作為一個(gè)整體，粒計(jì)算提供的思維模式和行為方式是系統(tǒng)的、完整的。其三是簡(jiǎn)化性：粒計(jì)算是提倡對(duì)問(wèn)題進(jìn)行不同層次的抽象和處理。在抽象過(guò)程中，可以只重視主要特性而忽略不相關(guān)的細(xì)節(jié)，從而達(dá)到對(duì)問(wèn)題的簡(jiǎn)化。其四是靈活性：粒計(jì)算的結(jié)構(gòu)允許人

23、們?cè)诓煌臅r(shí)間、不同的情況下，將注意力集中在不同的層次及層與層之間的自然過(guò)渡上，縮放和轉(zhuǎn)承是靈活多變的。其五是有效性：用粒計(jì)算指導(dǎo)的思維模式和行為方式將復(fù)雜問(wèn)題分解成若干小問(wèn)題。這種分而治之的方法是非常實(shí)用的，可以運(yùn)用到不同的領(lǐng)域。其六是經(jīng)濟(jì)性：粒計(jì)算尋求在不同粒度上的近似解。這樣的方法可以提高效率、降低成本。其七是容忍性：通過(guò)使用不同信息粒度，粒計(jì)算可以容忍不確定、不完全或有噪音的信息，從而獲得具有魯棒性的解決方案。 1.1.2粒計(jì)算任務(wù)和目標(biāo) 粒計(jì)算的形成綜合了許多學(xué)科的科研成果[14]，它的理論建立在對(duì)各個(gè)領(lǐng)域的共性進(jìn)行概括、總結(jié)和整理之上，形成了對(duì)問(wèn)題求解的普遍適用的原理、方法和策

24、略。在過(guò)去的若干年中，許多學(xué)者對(duì)粒計(jì)算的具體模式和方法進(jìn)行了研究。同時(shí)和粒計(jì)算原理相似的研究還在不斷地出現(xiàn)，只是在不同的領(lǐng)域中運(yùn)用了略微不同的名詞和術(shù)語(yǔ)。將粒計(jì)算作為一個(gè)獨(dú)立的學(xué)科研究可以防止這種不必要的重復(fù)勞動(dòng)。 (1) 粒計(jì)算的任務(wù) 作為一個(gè)新興的研究領(lǐng)域，粒計(jì)算是一門(mén)關(guān)于問(wèn)題求解的藝術(shù)。它有著兩項(xiàng)特殊的任務(wù)：其一是從各個(gè)不同的領(lǐng)域中概括出它們的共性，不考慮它們低層次上的差異，從而提煉出抽象的、高層次的、綜合的認(rèn)識(shí)；其二是將特定領(lǐng)域中隱含的結(jié)構(gòu)明確化，以期總結(jié)出獨(dú)立于具體領(lǐng)域的普遍原理。 (2) 粒計(jì)算的目標(biāo) 粒計(jì)算之所以新且獨(dú)特，并不完全在于一組具體的方法和策略，而在于提

25、出一個(gè)統(tǒng)一的框架，對(duì)這些方法和策略進(jìn)行全面的理解及綜合。通過(guò)對(duì)粒計(jì)算的研究試圖達(dá)到以下目標(biāo)：將隱式的結(jié)構(gòu)顯式化；將不明顯的原理明顯化；將特定領(lǐng)域的特殊原理普遍化；將下意識(shí)的行為變成有意識(shí)的行為。 1.1.3粒計(jì)算基本要素和理論構(gòu)成 (1) 粒計(jì)算的基本要素[14, 15] (a) 粒 粒是粒計(jì)算的初始概念，是粒計(jì)算研究對(duì)象的單位，是求解問(wèn)題的基本單位，等同于數(shù)據(jù)庫(kù)中的記錄，集合中的元素或子集。我們稱(chēng)最小的、不可分或不需要再分解的粒為基本粒，即最低層次的粒稱(chēng)為基本粒，它可以是模糊的，也可以是精確的。 粒具有雙重身份，它可以是某個(gè)整體中相對(duì)獨(dú)立的一個(gè)部分，也可以是一些粒共同組

26、成的一個(gè)粒。所有的粒都具有內(nèi)在屬性、外在屬性和環(huán)境屬性。當(dāng)粒作為整體時(shí)，所要考慮的是粒的內(nèi)在屬性，內(nèi)在屬性由粒所擁有的元素決定。當(dāng)粒作為部分時(shí)，所要考慮的是粒的外在屬性，由于具有外在屬性，粒就能夠被人們直接認(rèn)識(shí)。粒的環(huán)境屬性是指粒對(duì)外部環(huán)境變化的應(yīng)對(duì)情況，對(duì)其內(nèi)在屬性和外在屬性的保持與調(diào)整以及對(duì)外部環(huán)境的影響和回應(yīng)。粒的雙重身份決定了它的內(nèi)在屬性通常需要強(qiáng)調(diào)其它所包含的細(xì)小個(gè)體的不同特性，是對(duì)它內(nèi)部各個(gè)基本組成成分性質(zhì)的描述，而其外在屬性則是強(qiáng)調(diào)把它作為一個(gè)整體時(shí)所體現(xiàn)出的綜合特性。 (b) 層次 粒存在于特定的層次中，人們?cè)诹Ｓ?jì)算的不同層次中研究不同類(lèi)型的粒，這些粒之間是有聯(lián)系的

27、，同一層次的粒與粒之間可以是相交的關(guān)系也可以是層疊的關(guān)系，它們是該層次上研究的主體。層次中每一個(gè)粒表述了一個(gè)特定的?；^點(diǎn)。所有的?；^點(diǎn)相互補(bǔ)充、相互呼應(yīng)，完整表達(dá)了在這個(gè)層次上對(duì)同一個(gè)問(wèn)題的描述。每個(gè)層次都具有內(nèi)在屬性、外在屬性、環(huán)境屬性，同一層次的粒屬性共同體現(xiàn)本層次特性。 在問(wèn)題求解中，選擇在最合適的粒度層次上產(chǎn)生對(duì)一個(gè)問(wèn)題的描述，能幫助更好更快地解決問(wèn)題。較高層次包含較低層次，或者由較低層次組成。較高層次為較低層次提供背景和約束。較高層次一般由較高集成度和較高結(jié)合力的粒組成。每一層次都存在一定程度的獨(dú)立性。任意兩層次之間的連接和交互是通過(guò)偏序關(guān)系的傳遞性和橋接原理來(lái)表示和體

28、現(xiàn)的。粒計(jì)算模型的主要作用是能夠在不同粒度層次上進(jìn)行問(wèn)題求解，使不同粒度層次上的解能夠進(jìn)行相互轉(zhuǎn)化。 (c) 分層結(jié)構(gòu) 分層結(jié)構(gòu)由若干個(gè)層次組成，層次間的遞進(jìn)反映了由表及里、由抽象到具體、由粗糙到細(xì)致、由籠統(tǒng)到具體的變化。這種遞進(jìn)是有序的，高層次會(huì)對(duì)低層次進(jìn)行約束，并為低層次的描述提供背景。一個(gè)高層次的粒可以分解為若干個(gè)低層次的粒。相反，若干個(gè)低層次的?？梢越M合成一個(gè)高層次的粒。低層次的粒為高層次的粒提供更詳細(xì)的描述或者更多的信息。另一個(gè)方面，高層次的粒將與本層次的不相關(guān)的細(xì)節(jié)忽略掉，為低層次的粒提供更粗粒度的描述。 (d) 粒結(jié)構(gòu) 在粒計(jì)算研究中強(qiáng)調(diào)的是全面、

29、整體的觀點(diǎn)，而不是局部、離散的觀點(diǎn)。若要達(dá)到該目標(biāo)，不僅要考慮一個(gè)分層結(jié)構(gòu)中的多個(gè)層次，還需要將多個(gè)分層結(jié)構(gòu)綜合考慮。粒結(jié)構(gòu)包括三個(gè)要素，即粒的內(nèi)在結(jié)構(gòu)、粒的結(jié)構(gòu)、粒的總體結(jié)構(gòu)，它是多層次和多個(gè)分層結(jié)構(gòu)的結(jié)合。 粒計(jì)算借助于其他學(xué)科的哲學(xué)思想和方法論，并將它們抽象成為與具體領(lǐng)域無(wú)關(guān)的方法和策略。它的獨(dú)特性體現(xiàn)在用系統(tǒng)的、結(jié)構(gòu)化的理解和方法來(lái)解決復(fù)雜問(wèn)題。對(duì)復(fù)雜問(wèn)題的全面理解通常是多視角的，從每一個(gè)視角著眼的理解又是多層次的。由此可以得出，粒計(jì)算的過(guò)程就是對(duì)復(fù)雜問(wèn)題的求解過(guò)程。它的結(jié)果表現(xiàn)為一個(gè)多視角、多層次的粒結(jié)構(gòu)。這個(gè)粒結(jié)構(gòu)是對(duì)復(fù)雜問(wèn)題的系統(tǒng)且近似的描述和解答。 (2) 粒計(jì)算的理論

30、構(gòu)成[7, 8] 目前，粒計(jì)算有3個(gè)主要理論以及其它一些非主流理論：其一是詞計(jì)算理論：人類(lèi)思考、判斷、推理主要是用語(yǔ)言，而語(yǔ)言是一個(gè)很粗的粒，如何用語(yǔ)言進(jìn)行推理判斷，這就是詞計(jì)算。其二是商空間理論：商空間理論把概念用子集表示，不同粒的概念體現(xiàn)為不同粒的子集，一簇概念構(gòu)成空間的一個(gè)劃分——商空間，不同的概念簇就構(gòu)成了不同的商空間。故粒計(jì)算，就是研究在給定知識(shí)基上的各種子集合之間的關(guān)系和轉(zhuǎn)換，以及對(duì)同一問(wèn)題取不同的適當(dāng)?shù)牧＃瑥膶?duì)不同的粒的研究中，綜合獲取對(duì)原問(wèn)題的了解。其三是粗糙集理論：粗糙集理論于1982年由Pawlak提出，它是一種刻劃不完整性、不確定性的數(shù)學(xué)工具，主要解決信息粒的近

31、似方面的問(wèn)題。另外許多學(xué)者也在研究粒計(jì)算，并將各種相關(guān)理論用于粒計(jì)算，有鄰域系統(tǒng)粒計(jì)算、信息熵粒計(jì)算、概念格粒計(jì)算、覆蓋粒計(jì)算、進(jìn)化粒模型、基于相容粒度空間的粒計(jì)算模型以及各模型相互交叉整合的模型方法等，在許多領(lǐng)域中得以實(shí)現(xiàn)或應(yīng)用。 1.1.4粒計(jì)算研究方向與方法 粒計(jì)算的形成和發(fā)展積累了多種思想、模型、范式、方法論、技術(shù)及工具。對(duì)粒計(jì)算的研究應(yīng)該著眼于三個(gè)觀點(diǎn)[2]：粒計(jì)算的哲學(xué)思想觀點(diǎn)、方法論觀點(diǎn)及計(jì)算模式觀點(diǎn)。從哲學(xué)思想觀點(diǎn)考慮，粒計(jì)算試圖將人類(lèi)的認(rèn)知方式抽象化、形式化，從而提煉出結(jié)構(gòu)化的思維模式，而結(jié)構(gòu)化的思維模式是人類(lèi)智能的重要體現(xiàn)，它對(duì)設(shè)計(jì)基于知識(shí)的信息系統(tǒng)有著非常重要的影響，

32、它有兩個(gè)基本假設(shè)：一個(gè)是所有問(wèn)題都可以視作是其內(nèi)在要素之間的網(wǎng)絡(luò)狀或分層結(jié)構(gòu)的關(guān)聯(lián)，另一個(gè)是所有的問(wèn)題都有著類(lèi)似的模式和特征；從方法論觀點(diǎn)考慮，粒計(jì)算著重研究系統(tǒng)化的方法和技術(shù)，將問(wèn)題求解的過(guò)程規(guī)范為結(jié)構(gòu)化的、自上而下的逐步求精過(guò)程；從計(jì)算模式觀點(diǎn)考慮，粒計(jì)算關(guān)注于結(jié)構(gòu)化的信息處理。信息處理是有層次的，其研究領(lǐng)域涉及抽象的信息處理、人腦中的信息處理及計(jì)算機(jī)中的信息處理。計(jì)算模式是方法論的具體表現(xiàn)形式。在計(jì)算機(jī)學(xué)科中，人們通常將興趣集中在基于計(jì)算機(jī)的信息處理模型上，并將其獨(dú)立出來(lái)進(jìn)行分析。 粒計(jì)算的哲學(xué)研究基于粒結(jié)構(gòu)的思維方式?；締?wèn)題[7, 10, 15]包括：如何定義粒、層次及分層結(jié)構(gòu)的內(nèi)

33、在屬性、外在屬性和環(huán)境屬性；如何定義它們的關(guān)系；如何準(zhǔn)確表達(dá)它們的關(guān)系；如何實(shí)現(xiàn)它們的關(guān)聯(lián)和切花；如何使它們的綜合功能最大化。哲學(xué)層面的研究是抽象的，同時(shí)又是方法論和計(jì)算模式的前提和保障。 粒計(jì)算的方法論致力于將粒計(jì)算哲學(xué)思想具體到問(wèn)題求解的方法、技術(shù)和工具的研究和開(kāi)發(fā)中去。需要考慮到粒計(jì)算方法的有效性、可靠性、準(zhǔn)確性、簡(jiǎn)便性、計(jì)算成本和價(jià)值。對(duì)于不同的應(yīng)用還需考慮其問(wèn)題的特定及限制。 粒計(jì)算的信息處理強(qiáng)調(diào)以計(jì)算機(jī)為主體的信息處理與以人為主體的信息處理的差別。一方面，以計(jì)算機(jī)為主體的信息處理依靠人來(lái)制定、設(shè)計(jì)、實(shí)施和優(yōu)化；另一方面，計(jì)算機(jī)的信息處理也促進(jìn)方法論的研究。粒計(jì)算的哲學(xué)思想和方法

34、論的完善為計(jì)算機(jī)的信息處理實(shí)踐提供了可以依據(jù)的準(zhǔn)繩和保障，計(jì)算機(jī)的信息處理實(shí)踐反過(guò)來(lái)也會(huì)促進(jìn)對(duì)粒計(jì)算哲學(xué)思想和方法論的研究，成為支持粒計(jì)算哲學(xué)思想的有力證據(jù)和改善粒計(jì)算方法論的原動(dòng)力。 總之，如何定義粒（粒化）以及如何選擇合適的粒度是粒計(jì)算解決問(wèn)題的首要任務(wù)[6, 9]。 1.1.5粒計(jì)算基本思想和實(shí)質(zhì) 粒計(jì)算從不同粒層次上研究問(wèn)題，從人類(lèi)求解問(wèn)題的經(jīng)驗(yàn)方法中提取基本原理如粒、層次、等級(jí)。從人類(lèi)思考和求解問(wèn)題上看，“人類(lèi)以粒的觀點(diǎn)看世界”，“人們觀察、衡量、概括和推理的實(shí)體都是?！盵16]。當(dāng)人們面對(duì)復(fù)雜的、難于準(zhǔn)確把握的問(wèn)題時(shí)由于能力有限，通常不是采用系統(tǒng)、精確的方法去追求問(wèn)題的最優(yōu)解

35、，而是通過(guò)逐步嘗試的辦法達(dá)到有限的、合理的目標(biāo)，也就是采用由粗到細(xì)、不斷求精的多粒度分析法，避免復(fù)雜的計(jì)算，從而獲得足夠滿足的解，使得原來(lái)看似非多項(xiàng)式的難解問(wèn)題迎刃而解。人類(lèi)智能的一個(gè)公認(rèn)特點(diǎn)，就是人們能從極不相同的粒上觀察和分析同一問(wèn)題。人們能在不同粒的世界上進(jìn)行問(wèn)題求解，且能夠很快地從一個(gè)粒世界跳轉(zhuǎn)到另一個(gè)粒世界，往返自如，毫無(wú)困難。這種處理不同粒世界的能力，正是人類(lèi)問(wèn)題求解的強(qiáng)有力的表現(xiàn)，這也正是粒計(jì)算的基本思想[4]。粒計(jì)算方法是人工智能領(lǐng)域中的一種新理念和新方法，它覆蓋了所有和粒度相關(guān)的理論、方法和技術(shù)，在可以容忍的程度內(nèi)，主要用于對(duì)不確定、不準(zhǔn)確、不完整信息的處理，對(duì)大規(guī)模海量的數(shù)

36、據(jù)和對(duì)復(fù)雜問(wèn)題的求解，使其達(dá)到可處理性、魯棒性、小代價(jià)和諧調(diào)性。粒計(jì)算的實(shí)質(zhì)[4]就是通過(guò)選擇合適的粒度，來(lái)尋找一種較好的、近似的解決方案，從而降低問(wèn)題求解的難度。 而事實(shí)上，從真實(shí)世界上看，許多自然系統(tǒng)、社會(huì)系統(tǒng)、人工系統(tǒng)都是基于層次的，粒計(jì)算可以真實(shí)自然地表示這類(lèi)系統(tǒng)。從簡(jiǎn)化問(wèn)題上看，多層系統(tǒng)的不同層次關(guān)注不同的粒特征，粒計(jì)算忽略了不必要和不相關(guān)的細(xì)節(jié)，只關(guān)注適當(dāng)層次，從而簡(jiǎn)化了問(wèn)題。從實(shí)用角度上看，許多問(wèn)題是不完整的、不確定的，或者含有模糊信息，很難區(qū)分元素，只能認(rèn)為是粒。且在許多實(shí)際問(wèn)題中也不要求精確解，或者獲取精確信息的代價(jià)不菲，粒計(jì)算可以提高效率和降低代價(jià)。 1.2覆蓋廣義粗糙

37、集理論 定義1.1[17] 設(shè)是非空有限論域，是上的一簇子集且，對(duì)于任意，如果，那么為的一個(gè)劃分。 定義1.2[33] 設(shè)是非空有限論域，是上的一簇子集，如果中任一子集非空且，則為的一個(gè)覆蓋。 1.2.1覆蓋廣義粗糙集的研究背景 隨著計(jì)算機(jī)及網(wǎng)絡(luò)的日益普及，豐富的數(shù)據(jù)與貧乏的知識(shí)之間的矛盾日漸突出。不同領(lǐng)域的人都希望能從復(fù)雜的數(shù)據(jù)中得到自己所需要的知識(shí)，因此數(shù)據(jù)挖掘這門(mén)學(xué)科就應(yīng)運(yùn)而生了。該學(xué)科涉及分類(lèi)、概念形成和數(shù)據(jù)分析。這些都需要對(duì)不完全和不充分的信息進(jìn)行處理，圍繞這個(gè)問(wèn)題產(chǎn)生了許多理論，如模糊理論、神經(jīng)網(wǎng)絡(luò)、商空間理論、詞計(jì)算、粗糙集理論等。而其中的粗糙集理論[17]于

38、20世紀(jì)80年代提出以來(lái)，無(wú)論從理論上還是從應(yīng)用上都取得了豐碩的成果，尤其在數(shù)據(jù)挖掘領(lǐng)域里[18]。它是通過(guò)不可區(qū)分關(guān)系為不完全和不充分信息的處理提供了一套系統(tǒng)的方法。通常，人們用一組屬性來(lái)描述事物，不可區(qū)分關(guān)系就是由這些事物相應(yīng)的屬性值來(lái)定義的。如果兩個(gè)事物對(duì)于這組屬性的屬性值相等，也就是說(shuō)具有相同的描述，就認(rèn)為它們是不可區(qū)分的。從集合中關(guān)系這個(gè)角度來(lái)看，這種不可區(qū)分關(guān)系實(shí)際上就是等價(jià)關(guān)系。這樣，所有具有相同描述的事物構(gòu)成一個(gè)等價(jià)類(lèi)，而所有的等價(jià)類(lèi)構(gòu)成所考慮事物的一個(gè)劃分。在粗糙集理論中，這些等價(jià)類(lèi)又稱(chēng)為初等集，若干個(gè)初等集的并稱(chēng)為確定。利用這個(gè)劃分，任意的事物的集合可以用兩個(gè)確定集來(lái)上下逼

39、近，這兩個(gè)確定集分別是該事物集合的上近似和下近似。它無(wú)需提供問(wèn)題所需處理的數(shù)據(jù)集合之外的任何先驗(yàn)信息，對(duì)問(wèn)題的不確定性的描述或處理是比較客觀的。由于這個(gè)理論未包含處理不精確或不確定原始數(shù)據(jù)的機(jī)制，所以與概率論、模糊數(shù)學(xué)和證據(jù)理論等其他處理不確定或不精確問(wèn)題的理論有很強(qiáng)的互補(bǔ)性。 而隨著粗糙集理論得到廣泛的應(yīng)用以來(lái)，為使該理論能有更大的應(yīng)用空間，人們對(duì)Pawlak粗糙集理論進(jìn)行了許多有意義的推廣，如將等價(jià)關(guān)系放寬為相容關(guān)系[19]、相似關(guān)系[20]、一般二元關(guān)系[21]；與模糊理論結(jié)合，將粗糙集理論推廣到模糊粗糙集理論[22]和廣義模糊粗糙集理論[23]；將經(jīng)典粗糙集模型推廣到變精度粗

40、糙集模型[24]；從等價(jià)關(guān)系等同于劃分這個(gè)角度出發(fā)，Zakowski把劃分放寬為覆蓋[25],將Pawlak粗糙集理論推廣到覆蓋廣義粗糙集理論。 1.2.2覆蓋廣義粗糙集的國(guó)內(nèi)外研究現(xiàn)狀 然而，自從Pawlak粗糙集理論被推廣到覆蓋廣義粗糙集理論之后，國(guó)內(nèi)外學(xué)者對(duì)其做了大量的研究。文獻(xiàn)[26-53, 54-58]對(duì)覆蓋廣義粗糙集理論進(jìn)行了深入研究，其中文獻(xiàn)[30]討論了覆蓋廣義粗糙集的近似算子，文獻(xiàn)[29]主要研究覆蓋上下近似運(yùn)算分別成為Kuratowski閉包和內(nèi)部運(yùn)算的充分必要條件，文獻(xiàn)[27-28]主要研究了覆蓋廣義粗糙集中一階集合運(yùn)算，文獻(xiàn)[26]主要結(jié)合形式概念分析來(lái)研究

41、覆蓋廣義粗糙集，文獻(xiàn)[31, 53]討論了廣義粗糙集理論的代數(shù)結(jié)構(gòu)，文獻(xiàn)[49, 57]對(duì)基于關(guān)系的廣義粗糙集進(jìn)行了研究，文獻(xiàn)[33, 43, 44, 54, 56]對(duì)在覆蓋廣義粗糙集理論下的約簡(jiǎn)和不確定性度量進(jìn)行了研究，文獻(xiàn)[34-36, 39, 41-42, 45-48, 51, 58]對(duì)覆蓋廣義粗糙集理論中的上下近似運(yùn)算進(jìn)行了公理化的研究，文獻(xiàn)[38, 40, 52]分別對(duì)覆蓋廣義粗糙模糊集和拓?fù)湎嚓P(guān)性質(zhì)進(jìn)行了研究，而文獻(xiàn)[60-63]對(duì)變精度的覆蓋廣義粗糙集理論及其模型進(jìn)行了研究，以及其他的一些有關(guān)覆蓋廣義粗糙集理論的研究和總結(jié)[32, 50, 55, 59]。就應(yīng)用方面而言，覆蓋廣義

42、粗糙集理論已應(yīng)用于沖突分析[37]、信息檢索[64]等領(lǐng)域。 1.3本文研究的意義、目標(biāo)、方法和主要內(nèi)容以及創(chuàng)新點(diǎn) 1.3.1本文研究的意義 由于覆蓋廣義粗糙集理論是將Pawlak粗糙集理論在劃分基礎(chǔ)上推廣到覆蓋而建立起來(lái)的，而覆蓋廣義粗糙集理論主要研究與覆蓋相關(guān)的理論體系及應(yīng)用，所以 有關(guān)粗糙集一些理論和應(yīng)用并不一定在覆蓋廣義粗糙集下適用，那么在粒計(jì)算思想理論背景下研究覆蓋廣義粗糙集的相關(guān)理論和應(yīng)用就顯的十分有意義。 1.3.2本文研究的目標(biāo) 雖然覆蓋廣義粗糙集有了一定的理論基礎(chǔ)和應(yīng)用領(lǐng)域，但與粗糙集相比，需要不斷豐富其理論基礎(chǔ)和應(yīng)用領(lǐng)域，而繼續(xù)建立覆蓋近似運(yùn)算

43、公理化理論體系、覆蓋約簡(jiǎn)及近似性度量和不斷尋求覆蓋廣義粗糙集的適用方向是進(jìn)一步研究的具體目標(biāo)，本文旨在對(duì)覆蓋廣義粗糙集的應(yīng)用基礎(chǔ)進(jìn)行研究。 1.3.3本文研究的方法、技術(shù)路線及可行性分析 本文將采用由淺入深、并行開(kāi)展的研究方法。首先，介紹了粒計(jì)算思想理論體系的新穎性以及獨(dú)特性——以孤立點(diǎn)挖掘?yàn)槔?。其次，在粒?jì)算思想理論體系下，利用覆蓋相關(guān)理論分別對(duì)基于粗糙集的動(dòng)態(tài)信息系統(tǒng)規(guī)則挖掘、關(guān)聯(lián)沖突分析、分類(lèi)準(zhǔn)確率三個(gè)方面進(jìn)行獨(dú)立研究。 (1) 在基于粗糙集的動(dòng)態(tài)信息系統(tǒng)規(guī)則挖掘中的應(yīng)用研究中，主要利用條件屬性和決策屬性的交叉一致性來(lái)尋找引起差異信息系統(tǒng)中的不一致因素，然后利用改進(jìn)的規(guī)則挖掘算

44、法通過(guò)實(shí)驗(yàn)對(duì)比來(lái)實(shí)現(xiàn)。 (2) 在面向沖突分析的研究中，將沖突看作是在不同結(jié)構(gòu)層上的?；^(guò)程，提出關(guān)聯(lián)沖突的概念，給出其形式化的定義，然后并對(duì)其進(jìn)行分析和建模，最后給出關(guān)聯(lián)沖突過(guò)程中所可能引發(fā)異常的階段，將對(duì)不同階段引發(fā)的異常進(jìn)行詳細(xì)的分析 (3) 在面向分類(lèi)準(zhǔn)確性研究中，利用拓?fù)涓采w鄰域理論來(lái)尋找覆蓋系統(tǒng)上重疊元素，然后在粒計(jì)算的思維體系背景下，以實(shí)例輔證，采用折中方式給出獨(dú)立于數(shù)據(jù)標(biāo)簽和理想分類(lèi)結(jié)果假設(shè)的評(píng)價(jià)分類(lèi)法準(zhǔn)確性的統(tǒng)一范式。 以上提出的研究方法和技術(shù)路線是在前人對(duì)覆蓋廣義粗糙集理論和應(yīng)用以及相應(yīng)領(lǐng)域研究基礎(chǔ)上的再探索。雖然涉及領(lǐng)域比較寬泛，但都是在粒計(jì)算背景下研究的與

45、覆蓋相關(guān)的理論和應(yīng)用，所以本文實(shí)施和所采用的技術(shù)路線是可行的。 1.3.4本文研究的主要內(nèi)容以及創(chuàng)新點(diǎn) 本文主要是在粒計(jì)算的思想理論背景下研究與覆蓋相關(guān)的理論及其應(yīng)用。具體包括以下六章內(nèi)容： 第一章為緒論。首先介紹了粒計(jì)算的相關(guān)理論知識(shí)；然后介紹了覆蓋廣義粗糙集的研究背景，分析了國(guó)內(nèi)外研究現(xiàn)狀；最后介紹了本文的研究意義、目標(biāo)、方法和主要內(nèi)容以及創(chuàng)新點(diǎn)。 第二章為粒計(jì)算的獨(dú)特魅力。本章主要討論了粒計(jì)算的新穎性和獨(dú)特性——以孤立點(diǎn)挖掘?yàn)槔?，?chuàng)新性地給出了孤立點(diǎn)挖掘總的指導(dǎo)原則和具體實(shí)施的流程圖，為孤立點(diǎn)挖掘算法的選擇、改進(jìn)和創(chuàng)新提供了實(shí)際的參考價(jià)值，以此來(lái)揭示粒計(jì)算的獨(dú)特思

46、維模式和研究方法，進(jìn)而體現(xiàn)本文的寫(xiě)作意圖即受粒計(jì)算思想與理論的影響，獲取與覆蓋相關(guān)的創(chuàng)新思想來(lái)源。 第三章為覆蓋粒計(jì)算在基于粗糙集的動(dòng)態(tài)信息系統(tǒng)規(guī)則挖掘中的應(yīng)用研究。本章針對(duì)差異信息系統(tǒng)構(gòu)造過(guò)程中會(huì)引起新的不一致這個(gè)問(wèn)題，利用覆蓋粒計(jì)算相關(guān)理論提出了一種新的能消除這種不一致因素的公理化方法。實(shí)驗(yàn)結(jié)果表明，在保持時(shí)間復(fù)雜度不變的情況下，利用改進(jìn)的規(guī)則挖掘算法，通過(guò)消除不一致因素而獲得的規(guī)則更全面和更大程度地反映了條件屬性值變化與決策變化趨勢(shì)之間的內(nèi)在聯(lián)系。 第四章為基于覆蓋粒計(jì)算的關(guān)聯(lián)沖突分析。本章在粒計(jì)算思想理論背景下，首次提出了“關(guān)聯(lián)沖突”的概念，利用覆蓋沖突分析策略,通

47、過(guò)“服務(wù)——資源”實(shí)例建立了關(guān)聯(lián)沖突分析的合理泛化模型，討論了關(guān)聯(lián)沖突過(guò)程中所可能引發(fā)異常的階段，并對(duì)不同階段引發(fā)的異常進(jìn)行了詳細(xì)的分析，給出了具體的解決方案。 第五章為基于覆蓋粒計(jì)算的分類(lèi)準(zhǔn)確性研究。在面向分類(lèi)法準(zhǔn)確性（單標(biāo)簽和多標(biāo)簽數(shù)據(jù)集）的研究中，本章利用拓?fù)涓采w鄰域理論，給出了一種新的尋找覆蓋系統(tǒng)上重疊元素的相關(guān)的公理化方法。在粒計(jì)算的思維體系背景下，以實(shí)例輔證，創(chuàng)新性地給出了獨(dú)立于數(shù)據(jù)標(biāo)簽和理想分類(lèi)結(jié)果假設(shè)（一種假設(shè)為劃分，另一種假設(shè)為覆蓋）的評(píng)價(jià)分類(lèi)法準(zhǔn)確性的統(tǒng)一范式。需要說(shuō)明的是，本章對(duì)于分類(lèi)法準(zhǔn)確性統(tǒng)一范式的給出采取的折中處理方式值得借鑒。 第六章為總結(jié)與展

48、望。文章在同一個(gè)思想理論背景下，討論了基于覆蓋的相關(guān)理論和應(yīng)用，它是覆蓋廣義粗糙集的理論及其應(yīng)用的補(bǔ)充和發(fā)展，并且更體現(xiàn)出了粒計(jì)算背景下知識(shí)發(fā)現(xiàn)理論和方法的獨(dú)特性，具有重要的理論意義及潛在的應(yīng)用價(jià)值，同時(shí)對(duì)該領(lǐng)域理論和應(yīng)用研究的發(fā)展方向提出了新的展望。 此外，本文收錄了一些該領(lǐng)域內(nèi)最新的研究成果，以期能為科研工作者認(rèn)識(shí)和深入研究提供便利。 第二章 粒計(jì)算的獨(dú)特魅力 第二章 粒計(jì)算的獨(dú)特魅力 ——以孤立點(diǎn)挖掘?yàn)槔? 本章主要討論粒計(jì)算的新穎性和獨(dú)特性，以此來(lái)揭示粒計(jì)算的獨(dú)特思維模式和研究方法，

49、從中體現(xiàn)出本文的寫(xiě)作意圖，在粒計(jì)算思想理論背景下的覆蓋理論及其研究的問(wèn)題即受粒計(jì)算思想與理論的影響，獲取與覆蓋相關(guān)的創(chuàng)新思想來(lái)源。以孤立點(diǎn)挖掘?yàn)槔诹Ｓ?jì)算的思想理論背景下，給出了孤立點(diǎn)挖掘總的指導(dǎo)原則和具體實(shí)施的流程圖，為孤立點(diǎn)挖掘算法的選擇、改進(jìn)和創(chuàng)新提供了實(shí)際的參考價(jià)值，將會(huì)對(duì)孤立點(diǎn)的挖掘產(chǎn)生一定深遠(yuǎn)的影響。 2.1引言 孤立點(diǎn)也即異常點(diǎn)[65]，是指數(shù)據(jù)集中不符合一般模型的那些對(duì)象，即和其他數(shù)據(jù)有著不同的性質(zhì)。對(duì)于某些度量而言，這些對(duì)象與數(shù)據(jù)集中的其他數(shù)據(jù)有著顯著的不同。目前，針對(duì)不同的數(shù)據(jù)挖掘任務(wù)和挖掘背景，一些數(shù)據(jù)挖掘算法盡量去減少孤立點(diǎn)帶來(lái)的影響或者甚至是從數(shù)據(jù)集中消除他

50、們，然而，這可能會(huì)導(dǎo)致一些重要的隱秘信息的缺失。換句話說(shuō)，孤立點(diǎn)本身在諸如入侵檢測(cè)等事件中有著特殊的意義，它可以表示入侵的異常行為。因此，孤立點(diǎn)的檢測(cè)和分析（即孤立點(diǎn)挖掘）在數(shù)據(jù)挖掘中就顯得非常重要。一般，孤立點(diǎn)挖掘問(wèn)題可以看作兩個(gè)子問(wèn)題：一個(gè)是在給定的數(shù)據(jù)集中定義一個(gè)什么樣的數(shù)據(jù)可以被認(rèn)為是孤立點(diǎn)或不一致的；另一個(gè)是找到一個(gè)有效的方法去挖掘這些定義的孤立點(diǎn)。 在過(guò)去的一個(gè)多世紀(jì)里，人們對(duì)孤立點(diǎn)的研究經(jīng)歷了幾個(gè)興衰交替?，F(xiàn)在，它再一次成為信息科學(xué)里的一個(gè)活躍分支，并在數(shù)據(jù)挖掘領(lǐng)域里受到越來(lái)越廣泛的關(guān)注。孤立點(diǎn)挖掘之所以有著廣泛的應(yīng)用，是與其所在的實(shí)際領(lǐng)域里的特殊性決定，諸如入侵檢測(cè)、市場(chǎng)營(yíng)銷(xiāo)

51、和醫(yī)療等領(lǐng)域。孤立點(diǎn)的引起是有一些原因的[66]，同時(shí)相應(yīng)的也有一些檢測(cè)或挖掘孤立點(diǎn)的方法[67-76]。然而，每種方法總是存在著不可避免的缺點(diǎn)或者略勢(shì)，沒(méi)有一個(gè)普遍有效的方法來(lái)檢查數(shù)據(jù)集中的孤立點(diǎn)[77]。特別在檢測(cè)孤立點(diǎn)的過(guò)程中，如何選擇一個(gè)合適的檢測(cè)方法沒(méi)有一個(gè)普遍的準(zhǔn)則，而且就孤立點(diǎn)目前研究的熱點(diǎn)和未來(lái)的發(fā)展來(lái)說(shuō)[77]，挖掘任務(wù)會(huì)變得非常困難。因此，尋求一個(gè)適用于孤立點(diǎn)挖掘的總的指導(dǎo)原則就成為了最急需要解決的問(wèn)題。 2.2引起孤立點(diǎn)的原因 (1) 數(shù)據(jù)來(lái)自不同的類(lèi) 一個(gè)數(shù)據(jù)不同于其他數(shù)據(jù)，可能因?yàn)樗鼇?lái)自不同的類(lèi)或?qū)儆诓煌念?lèi)型。例如，一個(gè)在進(jìn)行信用卡欺詐的人可能

52、被歸為不合法的信用卡用戶而不是非法的用戶。相同地，諸如欺詐、入侵、疾病暴發(fā)和異常的實(shí)驗(yàn)結(jié)果等都可以被認(rèn)為是造成孤立點(diǎn)的例子。 (2) 自然變異 在統(tǒng)計(jì)知識(shí)的背景下，一些諸如正太分布等模型可以用來(lái)模擬許多數(shù)據(jù)集的分布。隨著數(shù)據(jù)點(diǎn)離正太分布的中心距離的增加，該點(diǎn)出現(xiàn)的可能性就會(huì)急劇地減少。換句話說(shuō)，對(duì)于大多數(shù)點(diǎn)來(lái)說(shuō)，離中心（平均對(duì)象）越近，不同于這個(gè)平均對(duì)象的可能性就越小。例如，假定一個(gè)男性特別的高，當(dāng)他獨(dú)自一人時(shí)，沒(méi)有人與之形成對(duì)比，他沒(méi)有什么特別之處。但是一旦于其他人在高度上做比較時(shí)，他就是一個(gè)孤立點(diǎn)，在這群人里他是一個(gè)高度上的極值。通常這些極值點(diǎn)或沒(méi)有任何變異的點(diǎn)作為孤立點(diǎn)是非常有意

53、思的。 (3) 數(shù)據(jù)度量和收集導(dǎo)致的誤差 在數(shù)據(jù)收集和度量的過(guò)程中，所導(dǎo)致的誤差是引起孤立點(diǎn)的另一個(gè)根源。例如，由于人為失誤、設(shè)備誤差或者數(shù)據(jù)本身具有噪音導(dǎo)致所記錄的度量值不正確。一般情況下都會(huì)刪除這些孤立點(diǎn)，因?yàn)樗麄儾荒芴峁┯杏玫男畔?，相反他們?huì)降低數(shù)據(jù)分析的質(zhì)量。但這些數(shù)據(jù)能反映出一些有用的信息，例如誤差的根源是人為、設(shè)備還是其他的原因造成的等。 2.3孤立點(diǎn)挖掘方法的思想描述 (1) 基于統(tǒng)計(jì)模型的孤立點(diǎn)檢測(cè)方法[67, 68] 許多檢測(cè)技術(shù)首先都會(huì)構(gòu)造一個(gè)數(shù)據(jù)模型。孤立點(diǎn)就是這些不能夠很好擬合這個(gè)模型的數(shù)據(jù)對(duì)象。例如，數(shù)據(jù)的分布模型可以通過(guò)估計(jì)概率分布的參

54、數(shù)來(lái)構(gòu)造。如果一個(gè)數(shù)據(jù)對(duì)象不能夠很好的擬合這個(gè)模型，它可能不服從這個(gè)分布，那它就是孤立點(diǎn)。如果模型是簇的集合，那么孤立點(diǎn)會(huì)明顯的不屬于任何簇?；蛘弋?dāng)使用回歸模型時(shí)，孤立點(diǎn)會(huì)相對(duì)的遠(yuǎn)離模型的預(yù)測(cè)值。 (2) 基于距離的孤立點(diǎn)檢測(cè)方法[69, 70] 目前，許多孤立點(diǎn)檢測(cè)的方法都是基于距離的。孤立點(diǎn)就是遠(yuǎn)離大多數(shù)點(diǎn)的點(diǎn)。當(dāng)數(shù)據(jù)分散在二維或三維的圖中時(shí)，我們可以通過(guò)基于距離的方法，用肉眼或簡(jiǎn)單方法分辨出哪些點(diǎn)是孤立點(diǎn)。 (3) 基于偏差的孤立點(diǎn)檢測(cè)方法[71, 72] 我們也可以通過(guò)比較一組數(shù)據(jù)的主要特征來(lái)檢測(cè)孤立點(diǎn)。根據(jù)問(wèn)題的要求，可以事先給定數(shù)據(jù)所對(duì)應(yīng)的一些特征，那么孤立點(diǎn)就是這

55、些不能像特征所描述的那樣的點(diǎn)。 (4) 基于密度的孤立點(diǎn)檢測(cè)方法[73, 74] 數(shù)據(jù)分布的密度估計(jì)是相對(duì)可以通過(guò)計(jì)算得到的，尤其是對(duì)數(shù)據(jù)之間存在距離的點(diǎn)來(lái)說(shuō)。那些處于低密度的數(shù)據(jù)點(diǎn)相對(duì)地遠(yuǎn)離他們的鄰居可以被認(rèn)為是孤立點(diǎn)。但是考慮到數(shù)據(jù)集可能有不同的密度區(qū)域，因此當(dāng)一個(gè)點(diǎn)所在的區(qū)域的密度明顯低于它的大多數(shù)鄰居的時(shí)候，它可以被歸為孤立點(diǎn)。 (5) 基于聚類(lèi)的孤立點(diǎn)檢測(cè)方法[75, 76] 聚類(lèi)分析和孤立點(diǎn)檢測(cè)有不同的目標(biāo)。聚類(lèi)分析通常被用于發(fā)現(xiàn)強(qiáng)相關(guān)的對(duì)象，而孤立點(diǎn)檢測(cè)則被用來(lái)發(fā)現(xiàn)那些和強(qiáng)相關(guān)的對(duì)象沒(méi)有關(guān)系的對(duì)象。顯然，聚類(lèi)可以用于孤立點(diǎn)檢測(cè)。 2.4討論 在數(shù)據(jù)

56、挖掘中，粒計(jì)算有著廣泛的應(yīng)用[78-80]。數(shù)據(jù)的?；?，尤其是復(fù)雜數(shù)據(jù)的?；?，是基于粒計(jì)算的數(shù)據(jù)挖掘的必要前提。?；某潭戎苯佑绊憯?shù)據(jù)挖掘的效率和計(jì)算復(fù)雜度。既要避免粒度過(guò)粗而造成求解失敗，又要避免粒度過(guò)細(xì)造成信息的冗余而導(dǎo)致求解效率低下。因此，選擇最優(yōu)粒化程度是粒計(jì)算數(shù)據(jù)挖掘的關(guān)鍵。另外，當(dāng)?；某潭纫阎獣r(shí)，?；姆椒ㄖ苯記Q定了?；男?。 孤立點(diǎn)挖掘是一個(gè)將孤立點(diǎn)從數(shù)據(jù)集中分離出來(lái)的過(guò)程。通過(guò)對(duì)引起孤立點(diǎn)的原因進(jìn)行分析，我們發(fā)現(xiàn)孤立點(diǎn)大都是各種情況里的不尋常的對(duì)象。他們由突發(fā)事件、人為因素或環(huán)境原因等所引起的，所以我們需要不同的實(shí)施過(guò)程將它們分離出來(lái)。事實(shí)上，從粒計(jì)算的觀點(diǎn)來(lái)看，分離的過(guò)

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

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

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

60、現(xiàn)。在對(duì)孤立點(diǎn)挖掘方法的分析和概括的基礎(chǔ)上，總結(jié)出了獨(dú)立于方法之上的方法論原則（?；笇?dǎo)原則），使得孤立點(diǎn)挖掘的著手點(diǎn)集中在?；乃枷肷?，避免了許多重復(fù)性的工作和不必要的麻煩，這是粒計(jì)算任務(wù)和目標(biāo)的體現(xiàn)。而孤立點(diǎn)挖掘的統(tǒng)一實(shí)施過(guò)程流程圖體現(xiàn)了粒計(jì)算的其他方面：挖掘過(guò)程本身是有先后順序之分，因此是具有一定層次性；而挖掘過(guò)程中，粒度大小的選擇即合適層次上的?；?，以獲取?；瓌t用以選擇、創(chuàng)新和改進(jìn)挖掘方法；由于粒度大小選擇上原因?qū)е峦诰蚪Y(jié)果不是很滿意，需要調(diào)節(jié)粒度，因此，這是一個(gè)循環(huán)反復(fù)的過(guò)程（體現(xiàn)出了分層結(jié)構(gòu)以及粒結(jié)構(gòu)），其間需要粒計(jì)算理論注入其中以求對(duì)所要解決的問(wèn)題選擇合理的層次和粒度。 對(duì)于

61、孤立點(diǎn)挖掘而言，?；^點(diǎn)是孤立點(diǎn)挖掘方法的選擇、改進(jìn)和創(chuàng)新的切入點(diǎn)，它的引入使得人們對(duì)孤立點(diǎn)挖掘的研究更廣泛和更集中即不斷的將新的?；椒ㄒ氲焦铝Ⅻc(diǎn)挖掘中和只將挖掘任務(wù)放在?；乃枷肷线M(jìn)行考慮，這樣一方面使得挖掘算法得到不斷改進(jìn)和創(chuàng)新，另一方面又可以避免許多不必要的重復(fù)勞動(dòng)。而孤立點(diǎn)挖掘統(tǒng)一實(shí)施過(guò)程圖的引入，使得孤立點(diǎn)挖掘任務(wù)的實(shí)施更一致化、明了化和細(xì)致化，尤其面對(duì)復(fù)雜數(shù)據(jù)諸如數(shù)據(jù)流、高維數(shù)據(jù)集和Web數(shù)據(jù)等中的孤立點(diǎn)挖掘時(shí)，該過(guò)程圖更能體現(xiàn)其優(yōu)勢(shì)所在，而且粒計(jì)算本身就具有其獨(dú)特的處理復(fù)雜數(shù)據(jù)的能力。 最后對(duì)于二者而言，基于粒計(jì)算的孤立點(diǎn)挖掘?qū)?huì)給孤立點(diǎn)挖掘的研究和分析提供一種新的策略和模

62、式，它將對(duì)孤立點(diǎn)的挖掘產(chǎn)生深遠(yuǎn)的影響。而將粒計(jì)算思想理論應(yīng)用于孤立點(diǎn)挖掘，全面體現(xiàn)了粒計(jì)算獨(dú)特的思維模式和研究方法，顯示出了它的獨(dú)特性和新穎性，更體現(xiàn)出了本文的寫(xiě)作意圖，將在粒計(jì)算的思想理論背景下研究與覆蓋相關(guān)的理論及其應(yīng)用即受粒計(jì)算思想與理論的影響，獲取與覆蓋相關(guān)的創(chuàng)新思想來(lái)源。 第三章 覆蓋粒計(jì)算在基于粗糙集的動(dòng)態(tài)信息系統(tǒng)規(guī)則挖掘中的應(yīng)用 第三章 覆蓋粒計(jì)算在基于粗糙集的動(dòng)態(tài)信息系統(tǒng)規(guī)則挖掘中的應(yīng)用 在動(dòng)態(tài)信息系統(tǒng)中，采用粗糙集方法來(lái)挖掘系統(tǒng)中潛在的規(guī)則。對(duì)于這類(lèi)問(wèn)題，由于信息系統(tǒng)的不一致性以及差異信息系統(tǒng)構(gòu)造過(guò)程中的不確定性和差異性，規(guī)則挖掘的結(jié)果不甚理

63、想：在粒計(jì)算的思想理論背景下，本章將覆蓋相關(guān)理論運(yùn)用到規(guī)則挖掘中，提出了一種消除引起差異信息系統(tǒng)規(guī)則挖掘中不一致因素的方法。實(shí)驗(yàn)結(jié)果表明，在保持時(shí)間復(fù)雜度不變的情況下，利用改進(jìn)的規(guī)則挖掘算法，通過(guò)消除不一致因素而獲得的規(guī)則將能更全面和更大程度地反映條件屬性值變化與決策變化趨勢(shì)之間的內(nèi)在聯(lián)系。 3.1引言 粗糙集方法是一種用于處理不確定性和模糊性數(shù)據(jù)的數(shù)學(xué)工具[17, 81]。但由于客觀世界的不確定性問(wèn)題通常表現(xiàn)為易變性和過(guò)程性，傳統(tǒng)的粗糙集很難體現(xiàn)出不確定性的變化過(guò)程和變化趨勢(shì)，即在信息系統(tǒng)中體現(xiàn)為屬性隨著時(shí)間的推移而不斷地變化[82, 83]。在決策信息系統(tǒng)中，利用粗糙集理論建立屬性

64、值隨時(shí)間和場(chǎng)景變化的動(dòng)態(tài)信息系統(tǒng)模型[84]，可以挖掘出條件屬性值變化與決策屬性值變化之間存在的內(nèi)在聯(lián)系?？墒怯捎趧?dòng)態(tài)信息系統(tǒng)構(gòu)造過(guò)程中會(huì)產(chǎn)生新的不一致性[85]，使得從差異信息系統(tǒng)上獲得的決策規(guī)則不甚理想。為了能獲得理想的決策規(guī)則，本文給出了一種能消除引起差異信息系統(tǒng)不一致因素的方法，并給出了改進(jìn)的基于粗糙集的啟發(fā)式規(guī)則挖掘算法，最終使決策規(guī)則能更好更全面的反應(yīng)條件屬性值的變化與決策變化趨勢(shì)之間的關(guān)系。 3.2預(yù)備知識(shí) 一個(gè)信息系統(tǒng)表示為一個(gè)四元組：，其中是對(duì)象的集合，即論域；是屬性集（，為條件屬性集，為決策屬性集）；，表示的值域；是一個(gè)信息函數(shù)。由于單個(gè)信息系統(tǒng)無(wú)法描述信息

65、和信息量隨時(shí)間和場(chǎng)景的變化的狀態(tài)，文獻(xiàn)[84]中給出了信息變換函數(shù)的概念，函數(shù)的定義域是時(shí)間和場(chǎng)景的區(qū)域，其中時(shí)間序列集合為，場(chǎng)景集合為，狀態(tài)序列集，每個(gè)都是一個(gè)決策表且論域、條件屬性、決策屬性均相同，屬性值隨著時(shí)間和場(chǎng)景的變化而變化。有： 定義3.1 動(dòng)態(tài)信息系統(tǒng)為狀態(tài)序列。 抽取信息系統(tǒng)和（），稱(chēng)為條件屬性值差異，其中表示對(duì)象個(gè)體（）關(guān)于屬性（）在時(shí)刻場(chǎng)景下的屬性值，條件屬性值差異描述了條件屬性值的變化量。記，其中是對(duì)條件屬性值的差異描述，的屬性值為的屬性值差異。 而稱(chēng)為決策變化趨勢(shì)，其中，描述了相同的對(duì)象個(gè)體的決策值從變化到。若兩個(gè)不同個(gè)體具有相同的變化趨勢(shì)=，當(dāng)

66、且僅當(dāng)和同時(shí)成立。記，是對(duì)決策屬性變化趨勢(shì)的描述，的屬性值為的決策變化趨勢(shì)。 定義3.2 差異信息系統(tǒng)為，其中，，，，、為差異信息系統(tǒng)的條件屬性和決策屬性。 由粗糙集理論可以得出，若信息系統(tǒng)和關(guān)于決策屬性的等價(jià)類(lèi)記為：和，差異信息系統(tǒng)中關(guān)于決策屬性的等價(jià)類(lèi)記為：，則有=。特殊的，當(dāng)時(shí)，此時(shí)的差異信息系統(tǒng)被稱(chēng)為相鄰差異信息系統(tǒng)。則有下面定義： 定義3.3 在差異信息系統(tǒng)中，對(duì)任意的屬性，的重要度定義為，式中：，表示的正域[81]。重要度表明了屬性對(duì)于決策分類(lèi)能力的貢獻(xiàn)程度。 定義3.4 設(shè)，，（差異決策表有行列，決策屬性列），構(gòu)造上第行的辨識(shí)矩陣，其中如果，則；否則。 定義3.5 設(shè)從差異信息系統(tǒng)上獲取的決策規(guī)則集為[86]，規(guī)則表示形式為，定義決策規(guī)則的覆蓋廣度為，其中為上滿足該決策規(guī)則的記錄數(shù)；決策規(guī)則的準(zhǔn)確率為，其中、分別為上滿足該決策規(guī)則前件和后件的記錄數(shù)。 從中可以看出，通過(guò)某個(gè)挖掘算法得到的決策規(guī)則，其覆蓋廣度與準(zhǔn)確率并不成正比，即在同樣的時(shí)間復(fù)雜度下，一個(gè)改進(jìn)的挖掘算法得到的挖掘規(guī)則，其覆蓋廣度和準(zhǔn)確率都必須同時(shí)增大，因此決策規(guī)則更準(zhǔn)確并且覆蓋記錄也就更