论文部分内容阅读
粗糙集理论(rough set theory)于1982年由波兰学者Pawlak教授提出,它是一种高效分析和处理不精确、不确定、不一致信息的软计算方法。属性约简是粗糙集理论的研究热点内容之一,一直受到众多学者的广泛关注。基于启发式的正域约简算法是属性约简经典算法之一,即保证信息系统在约简前后正域不变,从而保持确定性规则不变。由于海量数据的激增,人们对信息时效性的需求变得愈加强烈。现有启发式正域约简算法面临效率低下等问题。因此,众多学者对其进行了大量、深入的研究。启发式属性约简算法的运行效率主要由数据集的对象尺度和属性尺度两个方面影响。在粗糙集理论中,由特定二元关系信息粒化可以得到数据集的一簇信息粒,每个信息粒中的信息为不可分辨的。不仅如此,也可以将具有相同特性的属性看作为一个信息粒。从对象尺度和属性尺度出发,在对约简结果不产生影响的情况下,对信息粒进行收缩(zoom out)或膨胀(zoom in),使得数据集维度减小,算法效率得到提升。本文从多尺度粒化的角度出发,针对对象尺度粒化和属性尺度粒化两个方面对启发式正域约简算法进行优化,分别提出了集值信息系统的快速正域约简算法、一种多尺度属性粒策略的快速正域约简算法和不完备信息系统的快速正域约简算法,主要研究工作如下:(1)针对集值信息系统正域约简算法在大规模数据集下的运行效率低下问题,提出一种基于启发式的集值信息系统快速正域约简算法。通过研究属性和对象在约简过程中对算法运行效率产生的影响,在集值信息系统中引入属性无关性和属性重要度保序性的相关定义,介绍了使得算法运行效率提升的相关定理、快速算法和应用实例。最后,通过实验对提出算法的有效性进行分析和验证。实验结果表明提出算法的运行效率优于原始算法的运行效率。(2)针对启发式正域约简算法在大规模数据集下的运行效率低下问题,提出一种基于多尺度属性粒策略的快速正域约简算法。通过研究属性粒产生正域之间的关系,定义了多尺度属性粒的概念。该方法无需求取核属性集合,每轮迭代将多尺度属性粒加入到候选属性集合中,使得候选属性集合的分类能力趋向于原始特征的分类能力更快,迭代次数减少。算法通过去冗余过程,保证了约简结果的正确性。最后,通过实验对提出算法的运行效率进行比较和分析,实验结果表明提出算法更高效。(3)针对不完备信息系统正域约简算法在大规模数据集下的运行效率低下问题,提出一种基于不完备信息系统的快速正域约简算法。该算法打破传统启发式算法思想,在启发式搜索过程中,通过判断条件属性相对于决策属性产生正域间的关系,向候选属性集合中增加一个或两个属性,使得算法整体迭代次数减少,并且该算法无需求取核属性集合,在每轮迭代过程中删除候选属性集合产生的正域,算法效率得到有效提升。最后,通过和现有高效算法运行时间的对比和分析,实验结果表明提出算法更高效。