基于布尔矩阵表示的粗糙集属性约简算法的改进及应用研究

摘要

粗糙集理论，作为数据挖掘的一种重要方法，是在20世纪90年代由波兰数学家Palawk给出的一种能够对不精确和不完备信息系统进行处理的数学工具。属性约简是粗糙集理论研究的重点内容，目前很多属性约简算法在处理规模较大的决策表时，时空代价太高。由于布尔矩阵便于存储和运算等优势，这就为研究基于布尔矩阵表示的属性约简算法奠定了基础。但是，已有的关于布尔矩阵表示的属性约简算法还存在着很多问题，如启发式信息选取不完备，约简结果不精确，不适用于大规模决策表等问题。针对这些问题本文提出了改进算法。
　　首先，因为已有的算法选取的启发式信息不完备，针对改进的基于布尔矩阵表示的属性约简算法没有考虑核属性在浓缩布尔矩阵时的重要性的不足。本文将属性重要性与改进的条件区分能力相结合，提出了基于核与改进的条件区分能力的属性约简算法，然后借助反向删除确保约简集的完备性。实例表明改进后的算法在条件区分能力上更加准确，并且使约简结果具有较强的完备性。
　　其次，针对已有算法在处理规模较大的决策表时，时间和空间复杂度太高，甚至有些算法不能处理规模较大的决策表。本文在改进算法的基础上继续改进，引进矩阵的初等行变换以及位图运算对布尔矩阵进行初步压缩，并在初步压缩前利用属性重要性对布尔矩阵各行进行快速排序，得到一种基于行变化与条件区分能力的属性约简算法，再利用Matlab编程实现该算法，然后把其应用于具体的实例中。实例表明该算法在确保约简结果更加准确的情况下，处理大规模决策表时复杂度大大降低。
　　最后，将改进后的基于行变换与条件区分能力的算法应用于大学生就业评价指标研究的实例中，得到了影响就业相关因素，并与其它方法进行了比较分析，实例表明改进后的算法具有很强的实用性。

目录

声明

中文摘要

英文摘要

目录

1绪论

1.1研究的背景及意义

1.2国内外研究现状

1.3本文的主要研究工作

2粗糙集理论与属性约简

2.1粗糙集的基础理论

2.2属性约简

2.3属性约简算法

2.4算法间的性能对比分析

2.5小结

3基于属性重要性与改进的条件能力的算法

3.1基于布尔矩阵表示的属性约简方法

3.2基于核与改进的条件区分能力的属性约简算法

3.3基于行变化与条件区分能力的属性约简算法

3.4小结

4属性约简改进算法在大学毕业生就业评价指标中的应用

4.1基于行变化与条件区分能力的约简算法实现过程

4.2应用实例

4.3小结

5总结与展望

5.1总结

5.2展望

致谢

参考文献

附录