试论增量式属性约简更新算法研究

《试论增量式属性约简更新算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、厦门大学硕士学位论文增量式属性约简更新算法研究姓名：赖桃桃申请学位级别：硕士专业：计算机软件与理论指导教师：冯少荣20090501摘要粗糙集理论由波兰科学家Z．Pawlak于1982年提出的一种处理模糊和不确定知识的数学工具。粗糙集理论建立在论域中的不可分辨关系之上，用上、下近似来描述概念，不依赖于所需处理的数据集合之外的任何先验信息，就能对不精确、不确定、不完整的数据信息进行有效的处理。近年来，粗糙集理论在不少领域如数据挖掘、人工智能、模式识别、决策分析取得了很多成功的应用。属性约简是粗糙集理论的核心问题之一

2、，化简冗余属性，可以大大提高数据处理的效率。因此研究更为有效、时间复杂性更低的约简算法成为粗糙集理论研究的重点。而很多属性约简都是从核开始的，求核成了属性约简求解的关键步骤，因而探索有效的求核方法具有重要的实用价值。已有的大多数属性约简算法主要考虑信息系统或决策表不变的情况，有关属性约简的增量式更新算法报道不多。然而现实世界数据是动态产生的，信息系统或决策表中的对象在不断变化，已得到的属性约简可能不再有效，这就需要对属性约简进行动态修改。核求解算法也有同样的问题。本文的主要工作如下：1．分析发现杨明教授给出的改

3、进的差别矩阵中存在不必要的计算，为此提出了改进的差别矩阵定义及求核方法；在此基础上提出一种基于改进差别矩阵的核增量式更新算法，主要考虑对象动态增加情况下核的更新问题。2．在一种基于差别矩阵的属性核快速更新算法——FUAC(afastupdatingalgorithmforcomputingallattributescorebasedondiscernibilitymatrix)的基础上提出了一种改进算法，主要考虑对象动态删除情况下核的更新问题。3．分析已有的属性约简增量式更新算法，发现它具有较高的时间和空间复杂

4、度；在1的基础上提出了一种近线性时间、空间复杂度的高效属性约简增量式更新算法。关键词：粗糙集；属性约简；核AbstractRoughSettheoryisamathematicstoolforprocessingvagueandimprecisionknowledge，whichisproposedbyPolandscientistZ．Pawlakin1982．Roughsettheoryisbasedontheindiscemibilityrelationthatdescribesindistinguisha

5、bleobjectsandcallbeapproachedbytwoaccuratesets，thelowerandupperapproximation．NotneedingotherinformationthistheoryCananalyzeandprocesstheimprecise，uncertainandincompletedataproblems．Inrecentyears，roughsetstheoryhasbeensuccessfullyimplementedinDataMining，Artif

6、icialIntelligence，PatternRecognition，decisionanalysis，etc．Attributereductionisoneofmaintopicsinroughsettheory．ThereductionofattributesCanhighlyenhancetheefficiencyofdataprocessingbyremovingredundantconditionalattributes．Sotostudymoreeffectivealgorithmstogett

7、hebetterattributereductionandtodecreasethetimecomplexitybecomesanimportantpointinroughsettheory．Computingcoreisoneofimportantpartsofattributesreductionbecausemanyattributesreductionalgorithmsbegincore，SOexploringeffectivecomputingcorealgorithmhasanimportantp

8、racticalvalue．Manyexistingalgorithmsmainlyaimatthecaseofstationaryinformationsystemordecisiontable，verylittleworkhasbeendoneinupdatingofanattributereduction．Thegotattributereductioncouldbenolong