資源描述：
《增量式屬性約簡更新算法研究》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在學術(shù)論文-天天文庫。
1、廈門大學碩士學位論文增量式屬性約簡更新算法研究姓名：賴桃桃申請學位級別：碩士專業(yè)：計算機軟件與理論指導教師：馮少榮20090501摘要粗糙集理論由波蘭科學家Z．Pawlak于1982年提出的一種處理模糊和不確定知識的數(shù)學工具。粗糙集理論建立在論域中的不可分辨關系之上，用上、下近似來描述概念，不依賴于所需處理的數(shù)據(jù)集合之外的任何先驗信息，就能對不精確、不確定、不完整的數(shù)據(jù)信息進行有效的處理。近年來，粗糙集理論在不少領域如數(shù)據(jù)挖掘、人工智能、模式識別、決策分析取得了很多成功的應用。屬性約簡是粗糙集理論的核心問題之一，化簡冗余屬性，可以
2、大大提高數(shù)據(jù)處理的效率。因此研究更為有效、時間復雜性更低的約簡算法成為粗糙集理論研究的重點。而很多屬性約簡都是從核開始的，求核成了屬性約簡求解的關鍵步驟，因而探索有效的求核方法具有重要的實用價值。已有的大多數(shù)屬性約簡算法主要考慮信息系統(tǒng)或決策表不變的情況，有關屬性約簡的增量式更新算法報道不多。然而現(xiàn)實世界數(shù)據(jù)是動態(tài)產(chǎn)生的，信息系統(tǒng)或決策表中的對象在不斷變化，已得到的屬性約簡可能不再有效，這就需要對屬性約簡進行動態(tài)修改。核求解算法也有同樣的問題。本文的主要工作如下：1．分析發(fā)現(xiàn)楊明教授給出的改進的差別矩陣中存在不必要的計算，為此提出
3、了改進的差別矩陣定義及求核方法；在此基礎上提出一種基于改進差別矩陣的核增量式更新算法，主要考慮對象動態(tài)增加情況下核的更新問題。2．在一種基于差別矩陣的屬性核快速更新算法——FUAC(afastupdatingalgorithmforcomputingallattributescorebasedondiscernibilitymatrix)的基礎上提出了一種改進算法，主要考慮對象動態(tài)刪除情況下核的更新問題。3．分析已有的屬性約簡增量式更新算法，發(fā)現(xiàn)它具有較高的時間和空間復雜度；在1的基礎上提出了一種近線性時間、空間復雜度的高效屬性約
4、簡增量式更新算法。關鍵詞：粗糙集；屬性約簡；核AbstractRoughSettheoryisamathematicstoolforprocessingvagueandimprecisionknowledge，whichisproposedbyPolandscientistZ．Pawlakin1982．Roughsettheoryisbasedontheindiscemibilityrelationthatdescribesindistinguishableobjectsandcallbeapproachedbytwoaccura
5、tesets，thelowerandupperapproximation．NotneedingotherinformationthistheoryCananalyzeandprocesstheimprecise，uncertainandincompletedataproblems．Inrecentyears，roughsetstheoryhasbeensuccessfullyimplementedinDataMining，ArtificialIntelligence，PatternRecognition，decisionanaly
6、sis，etc．Attributereductionisoneofmaintopicsinroughsettheory．ThereductionofattributesCanhighlyenhancetheefficiencyofdataprocessingbyremovingredundantconditionalattributes．Sotostudymoreeffectivealgorithmstogetthebetterattributereductionandtodecreasethetimecomplexitybeco
7、mesanimportantpointinroughsettheory．Computingcoreisoneofimportantpartsofattributesreductionbecausemanyattributesreductionalgorithmsbegincore，SOexploringeffectivecomputingcorealgorithmhasanimportantpracticalvalue．Manyexistingalgorithmsmainlyaimatthecaseofstationaryinfo
8、rmationsystemordecisiontable，verylittleworkhasbeendoneinupdatingofanattributereduction．Thegotattributereductioncouldbenolong
