基于改进的FP树的快速属性约简算法.pdf

1522010,46(35)
Computer Engineering and Applications计算机工程与应用
基于改进的FP树的快速属性约筒算法
黄丽宇,徐章艳,钱文彬,杨炳儒2
HUANG Li-yu, XU Zhang-yan', QIAN Wen-bin, YANG Bing-ru
广西师范大学计算机科学与信息工程学院,广西桂林541004
2.北京科技大学信息、工程学院,北京100083
School of Computer Science and Information Engineering, Guangxi Normal University, Guilin, Guangxi 541004, China
2. School of Information Engineering, University of Science and Technology Beijing, Beijing 100083, China
HUANG Li-yu, XU Zhang-yan, QIAN Wen-bin, et al. Quick feature reduction algorithm based on improved frequent pat-
tern tree. Computer Engineering and Applications, 2010, 46(35): 152-155.
Abstract: In the feature reduction algorithms designed by the discernibility matrix idea, since there are lots of repeat and un
necessary elements in the discernibility matrix, which not only cost a mass of memory space, but also waste plenty of com
puter time in feature reduction. In order to improve the efficiency of such feature reduction algorithm, by considering the
idea of FP tree, a novel data structure IFP Tree(improved frequent pattern tree ) is proposed, which can get rid of the repeat
elements and unnecessary elements in the discernibility matrix completely. In this way, it can not only reduce a great deal of
memory space, but also enhance the efficiency of feature reduction algorithm greatly. Then, a new quick and efficient feature
reduction algorithm is designed based on IFP tree. Finally, an example is used to illustrate the validity of the new algorithm
Key words rough set; discernibility matrix; feature reduction; improved frequent pattern tree
摘要:在用差别矩阵思想设计的属性约简算法中,由于差别矩阵存在大量重复和无用的差别元素,不仅占用大量的存儒空间,
而且浪费属性约简的计算时间。为提高这种属性约简算法的效率,结合FP树(频繁模式树)的思想,给出一种新型的数据结构
改进的FP树( IEP Tree)。改进的FP树可以完全删除差别矩阵中所有重复的差别元素,也可以完全删除无用的差别元素。
不但减少了大量的存储空间,还大大提高了属性約简算法的效率。用FP树设计一种新的快遠属性约简算法。实例说明了该算
法的有效性。
关键词:粗糙集;差别矩阵;属性约简;改进的FP树
DOl:10.3778jis.1002-8331,2010.35,044文章编号:1002-8331(2010)35-0152-04文献标识码:A中图分类号:TP18;TP311
1引言
等价的。为此文献[9]构造出一个新的差別矩阵,并证明了由
Pawlak教授提出的粗糙集( Rough Set)是一种新的处理该新差別矩阼得到的属性约简与基于正区域的属性约简是
模糊、不确定知识的数学理论。目前,该理论正被广泛地应致的,其算法的时间和空间复杂度分別为OC?POS-(D)
用于机器学习、决策分析、过程控制、模式以別和数括挖掘等O( CIU POS(DD。由新差别矩阵设计基于正区域的属性约
领域,已成为人エ智能领域最具潜力的新兴技术之ー。属性简算法是一种很好的思路,因为这种设计思想直观简洁。但
约简是粗糙集理论中重要的研究内容,其中基于正区域的属是存储差别矩阵需要较大的存储空问,对于大规模数据集的
性约简是最常用的属性约简之
处理,这种设计方法并不理想。由于差别矩阵中存在大量的
已有许多文献通过设计启发信息给出了较好的基于正重复差别元素,而这些重复的差別元素既占用存储空间,又在
区域的属性约简算法。 Skowron提出的差别矩阵( discern-计算属性约简时浪费时间,因此,若能不生成这些重复的元素
ibility matrix)e为属性约简提供了很好的思路。这种思路因则可以大大提高属性约简算法的效率。基于这种思想,文献
其简洁直观而得到了广大研究者的关注。但文献[8]指出基于[10-12]引入简化决策表和区分对象对的概念,设计了一种新的
正区域的属性约简与基于 Skowron差別矩阵的属性约简是不算法,该算法去掉了差別矩阵中由等价类产生的部分重复差别
基金项日:国家自然科学基金( thc National Natural Scicncc Foundation of China undcr Grant No.60463003):ア广西省教育厅科研基金(No.200626);
广西师大博士启动基金资助课题:广西壮族自治区教育厅研究生科研创新项目
作者简介:黄丽宇(1980-),女,倾土研究生,研究方向为粗糙集理论及应用,数据挖掘;徐章艳(1972-),男,博士:,副教授,研究方向模糊集,粗糙
集,数据挖掘;钱文彬(1984-),男,硕上研究生,研究方向为粗糙集理论及应用,数据挖掘;杨炳儒(1943-),男,教授,博上生导师,研究
方向为数据挖捕,人工智能,柔性建模
收将口期:275年基修回日期:20002