【正文】 碩 士 學(xué) 位 論 文 題 目: 覆蓋粒計算及其應(yīng)用研究 Research on the Covering and Its Application Based on Granular Computing 覆蓋粒計算及其應(yīng)用研究摘 要粒計算是研究基于多層次粒結(jié)構(gòu)的思維方法、問題求解方法、信息處理模式及其相關(guān)理論、技術(shù)和工具的學(xué)科。它覆蓋了所有和粒度相關(guān)的理論、方法和技術(shù)，主要用于對不確定、不準(zhǔn)確、不完整信息的處理，對大規(guī)模海量的數(shù)據(jù)和對復(fù)雜問題的求解。粗糙集作為粒計算的一個重要分支，在理論和應(yīng)用上不斷取得豐碩成果的同時，也得到了廣泛有意義的推廣。而覆蓋廣義粗糙集理論是Pawlak粗糙集理論在劃分基礎(chǔ)上推廣到覆蓋建立起來的，它是研究與覆蓋相關(guān)的理論體系及其應(yīng)用，由于它是在粗糙集理論上的關(guān)系推廣，有關(guān)粗糙集的一些理論和應(yīng)用并不一定在覆蓋廣義粗糙集下適用。因此，本文的主要內(nèi)容是在粒計算思想理論背景下，研究與覆蓋相關(guān)的理論及其應(yīng)用。具體研究工作如下：一、在面向基于粗糙集理論的動態(tài)信息系統(tǒng)規(guī)則挖掘的研究中，利用覆蓋粒計算相關(guān)理論提出了一種能消除引起差異信息系統(tǒng)規(guī)則挖掘中不一致因素的公理化方法。實驗結(jié)果表明，在保持時間復(fù)雜度不變的情況下，利用改進的規(guī)則挖掘算法，通過消除不一致因素而獲得的規(guī)則能更全面和更大程度地反映條件屬性值變化與決策變化趨勢之間的內(nèi)在聯(lián)系。二、在面向沖突分析的研究中，在粒計算思想理論背景下，首次提出了“關(guān)聯(lián)沖突”的概念。利用覆蓋沖突分析策略,通過“服務(wù)—資源”實例建立了關(guān)聯(lián)沖突分析的合理泛化模型，討論了關(guān)聯(lián)沖突過程中所可能引發(fā)異常的階段，并對不同階段引發(fā)的異常進行了詳細的分析，給出了具體的解決方案,從而完善了各個領(lǐng)域沖突的解決。三、在面向分類法準(zhǔn)確性（單標(biāo)簽和多標(biāo)簽數(shù)據(jù)集）的研究中，利用拓撲覆蓋鄰域理論，給出了尋找覆蓋系統(tǒng)上重疊元素的相關(guān)公理化方法。在粒計算的思維體系背景下，以實例輔證，給出了獨立于數(shù)據(jù)標(biāo)簽和不同理想分類結(jié)果假設(shè)（一種假設(shè)為劃分，另一種假設(shè)為覆蓋）的評價分類法準(zhǔn)確性的統(tǒng)一范式，為提高和評估分類法準(zhǔn)確性的計算提供了重要的參考意義。最后，文章是在同一個思想理論背景下，討論了基于覆蓋的相關(guān)理論和應(yīng)用。以上研究工作是覆蓋廣義粗糙集的理論及其應(yīng)用的補充和發(fā)展，充分的體現(xiàn)出了粒計算背景下知識發(fā)現(xiàn)理論和方法的獨特性，具有重要的理論意義及潛在的應(yīng)用價值。 關(guān)鍵詞：粒計算；覆蓋；動態(tài)信息系統(tǒng)；規(guī)則挖掘；關(guān)聯(lián)沖突；分類RESEARCH ON THE COVERING AND ITS APPLICATION BASED ON GRANULAR COMPUTINGABSTRACTGranular puting (GrC) is viewed as an interdisciplinary study of putation in nature, society and science, characterized by 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, imprecise and inplete information and seek resolutions from the largescale massive dataset or plicated 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 covering is the one that partition’s Pawlak rough set theory is extended into covering’s. 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 make 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 preprocess 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 puting. Experiment shows that relationship between the changes of condition attributes values and trend of decisionmaking can be fully reflected as much as possible by a modified rules mining algorithm under the same time plexity through this preprocess approach.Secondly, for the conflict analysis, associatedconflict is firstly introduced in the perspective of GrC, and a reasonable and prehensive approach to its analysis, using covering based on granular puting, is outlined. We argue that this model of associatedconflict analysis, given by the example of serviceresource, 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 the 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 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 under 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 the future. KEY WORDS: GrC。 Covering。 Dynamic Information System。 Rules Mining。 Associatedconflict。 Classification目 錄摘 要 IABSTRACT III目 錄 V第一章 緒 論 1 1 1 2 2 5 6 6 7 目標(biāo)、方法和主要內(nèi)容以及創(chuàng)新點 8 8 8 9 9第二章 粒計算的獨特魅力 11 ——以孤立點挖掘為例 11 11 12 12 13 15第三章 覆蓋粒計算在基于粗糙集的動態(tài)信息系統(tǒng)規(guī)則挖掘中的應(yīng)用 17 17 17 19 19 20 22 24第四章 基于覆蓋粒計算的關(guān)聯(lián)沖突分析 26 26 27 27 29 30 30 37 39第五章 基于覆蓋粒計算的分類準(zhǔn)確性研究 40 40 41 42 42 44 45 47 50第六章 總結(jié)與展望 52 52 53參考文獻 54攻讀碩士學(xué)位期間取得的研究成果 61致 謝 62浙江師范大學(xué)學(xué)位論文獨創(chuàng)性聲明 63學(xué)位論文使用授權(quán)聲明 63第一章 緒 論 粒計算（Granular Computing, GrC）是一門飛速發(fā)展的新學(xué)科，[1]。短短十幾年的發(fā)展已經(jīng)見證了它對科學(xué)特別是計算機科學(xué)的作用和影響。諸多國內(nèi)外學(xué)者就粒計算的基本理論和方法做了大量的工作[212]。但為粒計算下一個正式的、精確的、能夠廣為接受的定義仍然是一件困難的事情。人們對粒計算的描述是建立在對它的直覺認識上的：粒計算是研究基于多層次粒結(jié)構(gòu)的思維方法、問題求解方法、信息處理模式及其相關(guān)理論、技術(shù)和工具的學(xué)科。作為軟計算科學(xué)的一個重要分支，它覆蓋了所有和粒度相關(guān)的理論、方法和技術(shù)，主要用于對不確定、不準(zhǔn)確、不完整信息的處理，對大規(guī)模海量的數(shù)據(jù)和對復(fù)雜問題的求解，正逐漸成為人工智能研究領(lǐng)域的熱點之一。研究粒計算有許多原因。其一是一致性：現(xiàn)實世界充滿了結(jié)構(gòu)和層次，它們體現(xiàn)在各種自然系統(tǒng)、社會系統(tǒng)和人工系統(tǒng)之中。因此，人們對現(xiàn)實世界的感知、理解、解釋和表示也是有結(jié)構(gòu)、分層次的。Zadeh將人類的認知能力概括為：?；?、組織和因果推理[13]。?；菍⒁粋€整體分割成部分，每個部分是擁有相同、相似性質(zhì)的個體的集合。組織是將松散的個體聯(lián)系在一起，形成有著內(nèi)在聯(lián)系的整體。因果推理是找出原因與結(jié)果之間的必然聯(lián)系。粒計算模型應(yīng)該能描述這三種能力。因而粒計算的結(jié)構(gòu)和現(xiàn)實世界的結(jié)構(gòu)、人們的思維模式及行為方式是一致的。其二是系統(tǒng)性：粒計算的結(jié)構(gòu)提供了對所解決的問題多視角、多層次的理解、概括和操作。作為一個整體，粒計算提供的思維模式和行為方式是系統(tǒng)的、完整的。其三是簡化性：粒計算是提倡對問題進行不同層次的抽象和處理。在抽象過程中，可以只重視主要特性而忽略不相關(guān)的細節(jié)，從而達到對問題的簡化。其四是靈活性：粒計算的結(jié)構(gòu)允許人們在不同的時間、不同的情況下，將注意力集中在不同的層次及層與層之間的自然過渡上，縮放和轉(zhuǎn)承是靈活多變的。其五是有效性：用粒計算指導(dǎo)的思維模式和行為方式將復(fù)雜問題分解成若干小問題。這種分而治之的方法是非常實用的，可以運用到不同的領(lǐng)域。其六是經(jīng)濟性：粒計算尋求在不同粒度上的近似解。這樣的方法可以提高效率、降低成本。其七是容忍性：通過使用不同信息粒度，粒計算可以容忍不確定、不完全或有噪音的信息，從而獲得具有魯棒性的解決方案。粒計算的形成綜合了許多學(xué)科的科研成果[14]，它的理論建立在對各個領(lǐng)域的共性進行概括、總結(jié)和整理之上，形成了對問題求解的普遍適用