基于压缩树技术的属性约简算法分析

《基于压缩树技术的属性约简算法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、-引言1.课题背景及研究目的本课题的背景为国家自然科学基金项目：基于不完备决策表的高效知识获取算法的研究(项目编号：60963008)，以及广西教育厅研究生科研创新项目：基于压缩树与增量式属性约简算法的研究。其中，基于压缩树技术属性约简算法，是在基于正区域和基于差别矩阵的属性约简算法基础上，而在已有的基于差别矩阵的属性约简算法的时间复杂度和空间复杂度都还不是很理想，为此，我们以元素在简化差别矩阵中出现的频率作为启发式信息，设计出一种基于Skowron差别矩阵的高效属性约简算法。其时间和空间复杂度分别降低到O(

2、C

3、

4、U

5、)+O(

6、C

7、

8、U/C

9、)和O(

10、U

11、)。但是，在差别矩阵中还

12、存在大量的重复差别元素和无2用的差别元素，针对这种情况，结合FP树(频繁模式树)的思想，设计出一种新型的数据结构——压缩树(C_Tree)。在压缩树中，不但可以完全删除差别矩阵中所有重复的差别元素，而且可以完全删除无用的差别元素。这样，不仅减少大量的存储空间，还可以大大提高属性约简算法的效率，使其更能有效地应用于对海量数据库的处理。自从波兰科学家Palawk教授提出粗糙集理论后，这门理论作为一种处理不完备、不确定、不精确信息的数学工具，在人工智能和认知科学方面，特别是在智能信息处理方面，如知识的表达与推理、知识发现、知识获取、数据分析、决策分析、机器学习、过程控制等领域得到了广泛的

13、应用。在世界各地掀起了粗糙集理论研究和应用的热潮，使粗糙集理论取得了进一步的发展和丰富。在经典的粗糙集理论中，目前已有许多学者通过设计启发信息，给出了较好的基于正区域的属性约简算法，如刘少辉教授围绕正区域这个核心概念,提出了一种新的快速计算正区域的方法，在此基础上，他又提出了一种基于正区域的高效属性算法。Skowron提出的差别矩阵(discernibilitymatrix)为属性约简提供了很好的思路。这种思路因其简洁直观而得到了广大研究者的关注。但叶东毅教授曾经指出基于正区域的属性约简与基于Skowron差别矩阵的属性约简是不等价的。为此，徐章艳教授构造出一个新的差别矩阵，并证明

14、了由该新差别矩阵得到的属性约简与基于正区域的属性约简是一致的，由新差别矩阵设计基于正区域的属性约简算法是一种很好的思路，因为这种设计思想直观简洁。而已有的基于差别矩阵的属性约简算法的时间复杂度和空间复杂度都还不是很理想，为此，我们以元素在简化差别矩阵中出现的频率作为启发式信息，设计出一种基于Skowron差别矩阵的高效OCU+OC2UC和O(

15、U

16、)。但是，(

17、

18、

19、

20、)(

21、

22、

23、/

24、)属性约简算法。其时间和空间复杂度分别降低到存储差别矩阵需要较大的存储空间，对于大规模数据集的处理，这种设计方法并不理想。-------1-------由于差别矩阵中不仅仅存在大量的重复差别元素，还存在大

25、量的无用差别元素。而这些重复差别元素和无用差别元素既占用存储空间，又在计算属性约简时浪费时间。因此，如何删除差别矩阵中那些重复差别元素和无用差别元素，设计一种数据结构来仅仅存储那些少量有用的差别元素是一个值得研究的问题。更值得研究的是在此基础上求属性约简算法和求所有属性约简算法。国内外对这些算法有大量的研究，不过在现有的基于差别矩阵的属性约简算法中，还不能删除由不同等价类产生的重复差别元素，更不能删除所有无用的差别元素。经初步研究，我们认为，若不生成这些重复和无用的元素，则不但可以大大减少存储差别矩阵的空间，而且，在属性约简时，由于只需计算少量的有用元素，大大提高属性约简算法的效率

26、。因此，设计对差别矩阵的高效压缩技术，使其能应用于对海量数据库的处理，是一项具有重要意义的事；这样的研究工作也是具有重要的应用价值的。目前，已解决了上述问题并设计了较好的属性约简和求所有属性约简算法。在进一步的工作中，拟将本文提出的算法用于基于粗糙集的规则获取算法中，并将基于粗糙集的规则获取算法形成软件。1.论文的研究意义粗糙集理论由波兰著名科学家Pawlak于1982年创立，它能够很好地适应和处理不完备、不确定、不精确和含糊的信息（Incomplete,Uncertain,ImpreciseandVagueInformation）。与概率论，模糊集合等其它传统的数据分析工具不同，

27、粗糙集理论在定量分析和处理那些不确定和不完备的数据时，有着非常明显的优势。它通过近似集合概念来描述和表达系统中的含糊性和不精确性，这种表达方式更为客观。在粗糙集理论中，样本集合代表概念，属性集合能够在论域上定义一系列的基本概念，代表着一定的已经掌握的知识，从本质上来说，知识表现为基本概念集合。对任何新的概念而言，粗糙集理论利用已有的知识，即利用现有的基本概念来构造新概念的上、下近似集合。对新概念进行不同近似程度的表达和刻画。更值得一提的是：上、下近似集合的计算完全是针