基于粗糙集的增量属性约简机理与算法研究

发布时间：2018-10-26 18:09

【摘要】：在大数据时代,计算机技术的飞速发展使得人类所收集的数据普遍呈现规模的海量性、表示的高维性、类型的混杂性以及时空的动态性等特征。如何高效地从这种数据中去除冗余以及不相关的属性,以解决学习算法的“维数灾难”问题并提高学习算法的性能,一直是机器学习领域的热点课题之一。经典粗糙集属性约简以保持条件属性与决策标签之间的一致性为出发点,实现了对符号数据中冗余属性的有效去除。为了处理不同类型甚至混杂的高维数据,经典粗糙集被拓展到更广义的模型。然而,当面对大规模以及动态数据时,现有粗糙集属性约简算法常常耗费大量的计算时间,甚至在某些软硬件环境下由于内存溢出而无法执行。为了克服这些问题,本文基于推广的粗糙集模型从增量的角度对符号型、实值型以及混杂型的高维海量动态数据展开属性约简增量机制的研究。主要研究成果和创新点如下:(1)设计了主动样本选择的机制,永久性地过滤了无用样本。对有用样本,通过研究属性约简的增量过程,揭示了如何从当前约简中删去冗余属性和加入有信息量的属性到当前约简。通过融合主动样本选择的机制和属性约简的增量过程,设计了经典粗糙集属性约简的增量算法,实验验证了该算法处理符号型动态数据的时间和空间的高效性。(2)用两个布尔向量刻画了变精度粗糙集属性约简,利用极小元素构造了变精度粗糙集属性约简算法。当有新样本加入时,基于辨识矩阵中极小元素的增量计算,研究了变精度粗糙集属性约简的增量过程,揭示了如何从当前约简中删去冗余属性以及加入有信息量的属性到当前约简。基于这一增量过程设计了变精度粗糙集属性约简的增量算法。数值实验验证了该增量算法的有效性和高效性。(3)用相对辨识关系刻画了一般模糊粗糙集模型的属性核心以及约简,设计了基于相对辨识关系的模糊粗糙集属性约简算法。基于相对辨识关系的增量计算,研究了属性增加和删去的准则,设计了两个模糊粗糙集属性约简的增量过程:1)每次有样本子集加入时,执行属性约简的增量计算,当不再有样本子集加入时,即获得整个数据集的约简;2)每次有样本子集加入时,仅增量计算相对辨识关系,当不再有子集加入时,即可得整个数据集的相对辨识关系,基于该相对辨识关系可得整个数据集的约简。其中,过程一更适合动态数据,而过程二更适合大规模数据。实验表明在不退化分类性能的前提下,这两个增量过程都加速了模糊粗糙集属性约简的获取,且过程二在处理大规模数据时表现出了更高效的性能。(4)分别对于符号属性和数值属性定义了辨识关系以刻画它们相对于决策标签的区分能力,用辨识关系的并集构造了依赖函数以度量混合属性与决策标签之间的一致性,通过在小的波动范围内保持该依赖函数不变定义了混合数据的属性约简。用相对辨识关系刻画了混合数据的属性约简,设计了相应的约简算法。当有多个样本加入混合数据时,基于相对辨识关系的增量计算,研究了混合数据属性约简的增量机制,提出了混合数据属性约简的增量算法。实验表明,所提混合数据属性约简能有效处理混合数据,实现了符号属性和数值属性之间的相互替换,且所提增量算法加速了混合数据属性约简的获取。(5)为了从含缺省值、符号值、实值等属性的混杂数据中选择有信息量的属性子集,我们引入相对辨识关系刻画了覆盖粗糙集的属性核心与约简,利用相对辨识关系设计了混杂数据的约简算法。基于相对辨识关系的增量计算,研究了属性增加和删去的准则,设计了两个覆盖粗糙集属性约简的增量过程:1)每次有样本子集加入时,增量计算一个覆盖约简,当不再有子集加入时,就得到该混杂数据的覆盖约简;2)每次有样本子集加入时,仅增量计算相对辨识关系,当不再有子集加入时,就得到该混杂数据的相对辨识关系,基于该相对辨识关系从空集开始计算混杂数据的覆盖约简。实验表明,这两个增量过程极大减少了计算一个覆盖约简的运行时间,且第二个增量过程更加高效。
[Abstract]:......
【学位授予单位】：华北电力大学(北京)
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP18
，

本文编号：2296547