不完备决策表属性约简和求核算法

《不完备决策表属性约简和求核算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、不完备决策袁属性约简和求核算法专业名称：计算机软件与理论申请人：章晨光指导教师：徐章艳教授论文答辩委员会主席：委员：不完备决策表属性约简和求核算法研究生姓名：章晨光导师姓名：徐章艳专业：计算机软件与理论研究方向：数据挖掘年级：2011级摘要㈣㈣㈣㈣㈣Y2585640现在在全世界范围掀起了一股股Ⅱ浪潮，例如云计算和物联网的兴起、移动通信服务进入了4G时代、大数据时代的到来等。这些IT革命使人类的工作生活更加便捷和轻松。特别是大数据时代，现在要处理的数据都已经到PB级别，这也加大了数据处理的难度。粗糙集是一个优秀的数学工具，尤其在处理不精确、不完备、不一致数据表现突出。粗糙集理论

2、是人工智能与模式识别共同研究所得到重要研究成果之一。粗糙集的最大特点是不要任何先验知识，不需要其他额外数据信息就可以达到处理数据的目的。属性约简和求核一直都是粗糙集理论的热门研究重心之一。属性约简的目的是在不改变原始数据背后的隐藏规则和数据关系的前提下，尽可能化简原始数据。属性约简又划分成无核属性约简和有核属性约简。无核属性约简是根据某些模型或者启发信息来进行约简。有核属性约简则是要先在计算核属性的基础上，然后在进行约简。其实，核属性是所有属性约简的交集。因此，求核是非常有意义的研究课题之一。同时，如今关于粗糙集的属性约简和求核的探讨多半是作用在完备决策表中。在实际情况中，由

3、于数据丢失、信息不确定或者噪声数据影响，使得信息系统中存在空值或者遗漏信息。然而以往的经典的属性约简和求核方法已经不适用于这种情况。这也导致了研究不完备决策表的属性约简与求核是一种新的趋势。王国胤教授针对不完备信息系统制定了容差关系、限制容差关系、相似关系等。各国学者则使用了正区域、矩阵、信息量、知识粒度等方式来计算不完备决策表的属性约简和求核。本文首先简单介绍了粗糙集的发展历程及相关概念，然后针对不完备决策表先后使用冲突域和限制容差关系来求解属性约简和属性。下面将从三个方面论述本文的研究工作：(1)在不完备决策表中的首先用分步计数的方法求出容差类，这比之前给出的算法更加高效

4、且易于理解。通过自己给出的冲突域的定义结合矩阵思想构造出布尔冲突矩阵的模型，然后通过矩阵的逻辑运算和属性重要度的定义，逐个找出约简后的属性。这样的方法相比以往的差别矩阵的属性约简方法是一种创新的方法，在时间效率也有不错提高。其中新设计的算法时间复杂度为max{O(1KlIcllU1)，D(IC12IPOSc(D)llu1))，空间复杂度为D(1C12lPOSc(D)IIU1)。(2)在关于核属性研究时，首先给出了冲突域的定义和在冲突域下的决策表的核属性判断方法。通过相比于普通正区域，冲突域可以减少元素决策值的比较次数，这样在算法效率上有所加强。在此之前，在计算容差类时用了链式

5、基数排序的方法，这一步大大降低了算法的时间复杂度。该求核算法的时间复杂度为O(IKIICl2IUI)，而总空间复杂度为o(IuI)。(3)在研究不完备决策表时，通常是用容差关系建立模型，但是容差关系在对象划分上不够精准。通过研究限制容差关系发现利用它划分的限制容差类更加精细与合理，可以方便核属性的计算。所以构造出基于限制容差关系的二进制差别矩阵，通过该矩阵来求核。该方法的时间复杂度D(ICIlu12)，空间复杂度降到D(1cIIUll‰1)。关键字：不完备决策表；属性约简；核属性；冲突域；限制容差关系IIAlgorithmforAttributeReductionandCom

6、putingCoreinIncompleteDecisionTableName：ZhangChenguangTutor：XuZhangyanMajor：ComputerSoftwareandTheoryResearchArea：DataMiningGrade：201AbstractNowdays，wavesofITareraisedintheworldfieldonebyone，justlikecloudcomputingandtheIntemetofThingsspringup，mobilecommunicationservicesgoto4Gtimes，bigdatati

7、mesiscomingandSOon．．TheseITrevolutionsmakehumans’livesandworksmoreeasyandconvinent．Espicallythebigdatatimes，theprocesseddatahavebeenuptolevelofPB，SOitmakesprocessdatamorehard．Roughsetisamathmatictoolwhichisusedtoprocesstheuncertain，imprecise，inconsistent