F-粗糙集不确定性的度量及粗糙集算法的优化

摘要

粗糙集理论是一种行之有效的数学工具，可以处理不精确、含糊和不完整信息。在数据挖掘、机器学习和模式识别等领域，粗糙集理论广泛应用于分类和特征选择（属性约简）。属性约简的方法包括正域、差别矩阵和差别函数、信息熵以及属性重要度等等。
　　本研究的第一个要点是F-粗糙集不确定性的度量。F-粗糙集是一种针对信息表簇或决策表簇的新的粗糙集模型。本文利用F-粗糙集模型中上、下近似的思想，定义了不确定性概念漂移的一些度量，包括概念的上、下近似漂移量，概念的上、下近似偶合度等，并初步探讨了它们的性质。第二个要点是属性约简算法的优化。在各式各样的粗糙集约简算法里划分占去了大量时间。同时，比较操作主导了划分过程。早期的采用蛮力运算策略的约简算法，在划分时需要很多时间来执行比较操作。这在约简大型决策表时是不可接受的。本文提出了一种哈希划分的方法，可以高效解决划分问题同时大幅减少比较运算的次数。本文使用哈希划分改善了决策表划分，并且和以往论文中常常采用的基于排序的划分方法做了详尽对比。通过哈希划分，耗时的比较运算明显减少，因而，很多粗糙集算法的运算效率得以提升。实验表明此方法适合于获取正域、决策表核属性、基于正域的Pawlak约简以及基于属性重要度矩阵的并行约简。本文的另一个亮点是对大数据的测试。不少声称测试了大数据的文章仅测试了10万条以下的决策表的表现。本文不仅加入了百万条数据集的测试结果，还人工合成了一张近40000000条数据、总容量为3.2GB的数据表然后进行了约简测试。最后，哈希划分同样可以改善并行约简。并行约简可以获取决策表的近似约简，实验表明加入了哈希划分的新算法优于原有算法的表现。

目录

摘要

1 绪论

1．1 课题的研究背景及意义

1．2 粗糙集不确定性的度量研究现状

1．3 粗糙集约简研究现状

1．4 论文的主要内容及创新

1．5 论文的工作安排

2 粗糙集和并行约简

2．1 粗糙集

2．2 F-粗糙集

2．3 粗糙集约简

2．4 并行约简

2．5 本章小结

3 F-粗糙集不确定性度量

3．1 概念外延漂移度量

3．2 举例

3．3 本章小结

4 哈希划分加速粗糙集属性约简

4．1 哈希函数的确定

4．2 哈希划分决策表

4．3 例题

4．4 哈希划分中实例比较次数的分布率的统计数据及其分析

4．5 基于排序的划分方法

4．6 QPHP实验

4．7 哈希和非哈希算法在划分上的比较

4．8 本章小结

5 哈希划分在粗糙集算法中的应用

5．1 哈希划分应用于正域

5．1．1 PRHP(Positive Region with Hashing Partitioning)性能分析

5．1．2 PRHP实验

5．2 哈希划分用于核属性

5．2．1 CAHP(Core Acquisition with Hashing Partitioning)性能分析

5．2．2 CAHP实验

5．3 基于属性重要度的贪婪策略Pawlak约简

5．3．1 GPRAS(Greedy Pawlak Reduct with Attribute Significance)性能分析

5．3．2 GPRAS实验

5．4 啥希划分用于并行约简

5．4．1 PRH(Parallel Reduct with Hash)性能分析

5．4．2 PRH实验

5．5 本章小结

6．总结与展望

6．1 研究总结

6．2 研究展望

参考文献

攻读学位期间取得的研究成果

致谢

声明

浙江师范大学学位论文诚信承诺书