基于压缩树技术的属性约简算法研究

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

1、基于压缩树技术的属性约简算法研究研究生姓名：黄丽宇导师姓名：徐章艳专业：计算机软件与理论研究方向：数据挖掘年级：2007级摘要粗糙集理论是波兰数学家Z.Pawlak于1982年提出的一种分析不完整、不确定、不精确数据的有效的数学理论。它与其它处理不确定或不精确问题理论有着最为显著的区别，那就是不需要提供问题所需处理的数据集合之外的任何先验信息，就可以直接对数据进行分析和推理，从中发现其隐含的知识，揭示其潜在的规律。近年来，粗糙集理论在模式识别、机器学习等领域中取得良好的成果和广泛的应用。它作为一种较新的数据分析

2、与处理工具，已经越来越受到学术界的重视，其中的一个研究热点是有效算法的研究及应用。目前，主要有属性约简算法，决策规则提取算法，与粗糙集有关的神经网络和遗传算法等。其中，属性约简算法是粗糙集理论及应用的重要研究内容之一。到目前为止，已有许多学者通过设计启发信息，给出了较好的用差别矩阵设计基于正区域的属性约简算法，这种设计思想直观简洁。但是存储差别矩阵需要较大的存储空间，对于大规模数据集的处理，这种设计方法并不理想。并且，由于差别矩阵中存在大量的重复的和无用的差别元素，而这些重复的和无用的差别元素既占用存储空间，又

3、在计算属性约简时浪费时间。因此，若能不生成这些重复的元素，则可以大大提高属性约简算法的效率。本文对粗糙集理论的基本概念，目前各种属性约简算法及求所有属性约简算法进行了探讨与分析，指出现有算法的优点与不足。针对存在的问题和不足，以元素在简化差别矩阵中出现的频率作为启发式信息，设计出一种基于Skowron差别矩阵的高效属性约简算法。再提出了一种新的数据结构——压缩树(C_Tree)，然后用这种新型的数据结构设计出相应的算法，并通过实例和实验证明本文所提出的新算法的可行性与有效性。具体而言，主要研究工作如下：（1）简

4、述粗糙集理论及其发展现状，介绍属性约简及其算法与所有属性约简及其算法的研究现状，并分析其优缺点。同时，也介绍了粗糙集理论的基本概念。（2）从现有的基于差别矩阵的属性约简算法出发，以属性在简化差别矩阵中出现的频率作为启发式信息，设计出一种基于Skowron差别矩阵的高效属性约简算法。其时间和2空间复杂度分别降低到OCUOCUC(

5、

6、

7、

8、)+(

9、

10、

11、/

12、)和OU(

13、

14、)。并用实例说明了这个新算法的有效性和可行性。（3）结合FP树(频繁模式树)的思想，设计出一种新型的数据结构——压缩树(C_Tree)。在压缩树中，不

15、但可以完全删除差别矩阵中所有重复的差别元素，而且可以完全删除无用的差别元素。这样，不仅减少大量的存储空间，还可以大大提高属性约简算法的效率。（4）基于压缩树(C_Tree)，设计出快速的属性约简算法，该算法不用计算差别矩阵中大量的重复差别元素和无用差别元素，算法效率较高，尤其适用于大型数据库的处理。分析了算法在最坏情况下的时间复杂度和空间复杂度分别为max{(

16、OCU

17、

18、

19、),OCUCPOSDC(

20、

21、

22、/

23、

24、()/

25、)}和max{(

26、OUON

27、,(

28、

29、)}。其中

30、C

31、表示条件属性的个数，

32、U

33、C1表示决策表中对

34、象的个数，

35、N1

36、表示压缩树(C_Tree)中的节点数。用实例说明，并用实验证明了其有效性和可行性。（5）对于基于压缩树(C_Tree)求所有属性约简算法，该算法不用计算差别矩阵中大量的重复差别元素和无用差别元素，算法效率得到大大的提高。分析了该算法在最坏情况2下的时间复杂度和空间复杂度分别为max{(

37、OCU

38、

39、

40、),OCUCPOSDC(

41、

42、

43、/

44、

45、()/

46、)和Cmax{(

47、OUON

48、,(

49、1

50、)}。其中

51、C

52、表示条件属性的个数，

53、U

54、表示决策表中对象的个数，

55、N1

56、表示压缩树(C_Tree)中的节点数。用实

57、例说明该算法的有效性和可行性。本论文主要有以下创新点：（1）以属性在简化差别矩阵中出现的频率作为启发式信息，设计出一种基于Skowron2差别矩阵的高效属性约简算法，其时间和空间复杂度分别降低到OCUOCUC(

58、

59、

60、

61、)+(

62、

63、

64、/

65、)和OU(

66、

67、)。（2）指出了当前的用差别矩阵设计基于正区域的属性算法研究中，没有删除由不同等价类产生的重复差别元素，也不能删除所有无用的差别元素。从而影响了属性约简算法的效率。（3）针对本文提出的问题，结合FP树(频繁模式树)思想，设计出一种新型的数据结构——压缩树(C_Tree

68、)。用压缩树存储差别矩阵中的差别元素，不但可以完全删除差别矩阵中所有重复的差别元素，而且可以完全删除无用的差别元素。（4）利用压缩树，设计出一种快速的属性约简算法和一种高效的完备属性约简算法。本文所提出的新型数据结构以FP树(频繁模式树)构建思想理论为依据，提出新的求属性约简算法和求所有属性约简算法是在前人工作的基础上，解决现有算法存在的问题，使之更有效处理大型数据库。也从实例和实验结