不完备信息系统的增量式约简算法

针对经典粗糙集模型在处理不完备、动态数据方面的不足,通过分析容差关系模型,引入先验概率在知识估计中的方法,给出了一种基于区分矩阵的增量式属性约简算法.以属性重要度为启发信息,对区分矩阵的构造过程进行改进,仅需简单的矩阵运算就可以得到约简结果.最后通过示例分析处理增量式数据的算法复杂度有效,算法正确可行.

一种增量式约简方法求解最小顶点覆盖问题

最小顶点覆盖问题是一个应用很广泛的NP难题,针对该问题给出一种增量式属性约简方法。首先将最小顶点覆盖问题转换为一个决策表的最小属性约简问题;利用增量式属性约简思想,随着图中边数的增多,提出一种更新最小顶点覆盖的增量式属性约简算法;该算法时间复杂度低于计算整个图的最小顶点覆盖的时间复杂度,同时针对大规模图问题,可随着边的增加动态更新最小顶点覆盖,因此降低了属性约简的方法求解最小顶点覆盖问题的运行时间。实验结果表明了该算法的可行性和有效性。

基于标记可辨识矩阵的增量式属性约简算法

针对现有增量式属性约简算法中存在的约简传承性差以及不完备现象,提出基于标记可辨识矩阵的增量式属性约简算法.本文首先定义了标记函数,对样本之间的可辨识性进行分类,并将之引入一个新的可辨识矩阵,在新增样本时,结合标记信息可以快速识别可辨识矩阵元素集的异动,获得强传承性的约简超集,在此基础上,设计与标记可辨识矩阵匹配的必要矩阵,用以快速判断并删除冗余属性,确保约简的完备性.理论分析以及实验测试表明,本算法具有约简传承性强,约简集完备等特点,具有较强的实用性.

基于不一致邻域的批增量式属性约简

经典粗糙集仅能处理离散性数据,而邻域粗糙集通过运用距离函数解决了此局限性。基于此,提出一种信息观下批增量式属性约简算法。分析批量增加样本后新样本集下条件熵的变化机制,给出条件熵的计算公式;通过公式得出新加入样本的不一致邻域引起条件熵的变化,当新增样本加入到原样本集后,只需找到新增样本集的不一致邻域,与新增样本集一起进行约简,对原约简集进行冗余剔除,得到最终约简。该算法避免了有重复的约简,大大减少了计算量。将该算法应用到UCI数据集以及某单位的科技人才流动绩效评价指标体系中进行实验,实验结果验证了该算法的有效性和高效性。

基于改进区分矩阵的决策表增量式属性约简

针对属性在不断增加的决策表,为了快速准确地计算出属性约简,提出一种增量式属性约简算法。以正域为约简的标准,利用贪心算法思想,以属性区分能力为选择标准,逐渐构造近似的属性约简,从中删减掉不必要的属性,最终得到属性约简。经复杂度分析与实验数据测试,证明该算法的复杂度低并且约简结果准确。

基于区分矩阵的增量式属性约简

定义了属性和属性集的区分矩阵以及区分矩阵的运算,表明了属性集的区分矩阵与论域按属性集的分类是1-1对应的,因此,区分矩阵代表了属性集的分类。以区分矩阵作为属性约简的标准,以属性对分类的贡献率作为贪心选择的次序,建立了一种针对无目标信息系统的属性约简以及增量式属性约简方法。该算法降低了处理增量式数据的复杂度,并且只涉及到矩阵的加法、非负矩阵转化为0-1矩阵、判断矩阵相等的运算,便于用计算机语言编程计算。

区间值决策表的正域增量式属性约简算法

实际应用中存在大量动态增加的区间型数据,若采用传统的非增量正域属性约简方法进行约简,则需要对更新后的区间值数据集的正域约简进行重新计算,导致属性约简的计算效率大大降低。针对上述问题,提出区间值决策表的正域增量属性约简方法。首先,给出区间值决策表正域约简的相关概念;然后,讨论并证明单增量和组增量的正域更新机制,提出区间值决策表的正域单增量和组增量属性约简算法;最后,通过8组UCI数据集进行实验。当8组数据集的数据量由60%增加至100%时,传统非增量属性约简算法在8组数据集中的约简耗时分别为36.59s、72.35s、69.83s、154.29s、80.66s、1498.11s、4124.14s和809.65s,单增量属性约简算法的约简耗时分别为19.05s、46.54s、26.98s、26.12s、34.02s、1270.87s、1598.78s和408.65s,组增量属性约简算法的约简耗时分别为6.39s、15.66s、3.44s、15.06s、8.02s、167.12s、180.88s和61.04s。实验结果表明,提出的区间值决策表的正域增量式属性约简算法具有高效性。

基于二进制区分矩阵的增量式属性约简算法

增量式属性约简算法是动态数据挖掘技术的重要研究内容。为降低区分矩阵的存储空间,结合二进制区分矩阵便于计算以及形象直观的优点,给出一种压缩二进制区分矩阵的方法。将二进制区分矩阵的存储空间从|C|+1列简化成3列。通过动态更新二进制区分矩阵实现增量式求核,并以核为出发点,提出一种的增量式属性约简算法。通过实例计算及仿真实验验证了该算法的有效性。

基于粗集理论的属性约简关键技术概述

本文从静态属性约简和动态属性约简两个方面对基于粗集理论的属性约简关键技术进行了归纳总结,静态属性约简算法有基于信息熵、基于正域及基于辨识矩阵的约简算法,同智能计算方法结合的动态属性约简算法有并行属性约简、基于粒计算的属性约简及增量式属性约简等。指出今后属性约简的发展方向是在大数据时代下同智能算法、并行计算、云计算等技术融合发展的趋势。

一种处理部分标记数据的粗糙集属性约简算法

属性约简是粗糙集理论中重要的研究内容之一,是数据挖掘中知识获取的关键步骤。Pawlak粗糙集约简的对象一般是有标记的决策表或者是无标记的信息表。而在很多现实问题中有标记数据很有限,更多的是无标记数据,即半监督数据。为此,结合半监督协同学习理论,提出了处理半监督数据的属性约简算法。该算法首先在有标记数据上构造两个差异性较大的约简来构造基分类器;然后在无标记数据上交互协同学习,扩大有标记数据集,获得质量更好的约简,构造性能更好的分类器,该过程迭代进行,从而实现利用无标记数据提高有标记数据的约简质量,最终获得质量较好的属性约简。UCI数据集上的实验分析表明,该算法是有效且可行的。

RS理论在机床热补偿误差系统中的应用

本文主要以机床热补偿误差系统为应用背景,利用粗糙集理论中属性约简算法为理论支持,采用C++数据库管理系统,得到机床热补偿误差系统的温度测点优化结果。