基于幂树的决策表最小属性约简*

南京大学学报(自然科学版) ›› 2012, Vol. 48 ›› Issue (2): 164–171.

基于幂树的决策表最小属性约简*

陈玉明**，吴克寿，孙金华

出版日期:2015-05-22 发布日期:2015-05-22
作者简介: (厦门理工学院计算机科学与技术系，厦门，361024)
基金资助:
国家自然科学基金(61103246, 61075056, 60903203)

Minimal attribute reduction based on power set tree in decision table

Chen Yu-Ming ,Wu Ke- Shou，Sun Jin -Hua

Online:2015-05-22 Published:2015-05-22
About author: (Department of Computer Science and Technology, Xiamen University of Technology,Xiamcn, 361024，China)

摘要/Abstract

摘要： 粗糙集理论是一种新的处理不精确、不完全与不一致数据的数学理论工具，决策表属性约简是粗糙集理论研究的核心内容之一针对决策表最小属性约简穷举算法时间复杂度较高问题，从改变决
策表属性约简问题的知识表示入手，在决策表中引入树的表示方式，定义幂树表示约简问题空间，给出了旋转和回溯两种剪枝搜索方法.进一步针对决策表提出了基于幂树的最小属性约简完备性算法，该算
法在幂树空间中进行穷举搜索，同时采用了旋转和回溯剪枝策略，提高了完备性算法的搜索效率，分析了算法的时间与空间复杂度，指出了完备性最小属性约简算法复杂度的指数级别特点.理论分析和实例
表明该方法是有效可行的.

Abstract: Rough set theory is a new mathematical tool to deal with imprecise, incomplete and inconsistent data. Attribute reduction in decision table is one of the core problems in rough set theory. As we know, the time
complexity of exhaustive search is high for complete minimal attribute reduction in decision table. From the change of knowledge representations for the attribute reduction problem, the new knowledge representation called power set
tree is introduced.The power set tree is an inclined tree displaying all the possible nodes of problem space. Based on the power set tree, the rotation pruning operator and backtracking pruning operator for answering the minimal
reduction question are proposed. Furthermore, a new complete algorithm to minimal attribute reduction problem based on power set tree is proposed in decision table.The new algorithm is also an exhaustive method，but using the
rotation pruning operator and backtracking pruning operator to improve its search efficiency. And the new algorithm is a complete method which can guarantee to find a minimal reduction.The time and space complexities of the
algorithm are also analyzed. And points out that the time and space complexities of complete attribute reduction algorithm show the exponent of growth. Finally, theoretical analysis and an example show that the reduction
method is efficient and feasible.

陈玉明**，吴克寿，孙金华. 基于幂树的决策表最小属性约简*
[J]. 南京大学学报(自然科学版), 2012, 48(2): 164–171.

Chen Yu-Ming ,Wu Ke- Shou，Sun Jin -Hua
. Minimal attribute reduction based on power set tree in decision table
[J]. Journal of Nanjing University(Natural Sciences), 2012, 48(2): 164–171.

参考文献

[1]Pawlak Z. Rough sets, International Journal of Computer and Information Science, 1982，11 (5):341一356.
[2]Skowron A，Rauszcr C. Intelligent decisior support:Handbook of applications and advances of the rough set theory. Dordrecht:Kluwer Ac ademic Publishers, 1992，471.
[3]ryszkiewicz M. Comparative studies of alter- native type of knowledge reduction in inconsis- tent systems,International Journal of Intelligcnt Svstems, 2001，16(1):10}一120.
[4]Wang L，Qiu T R，He N, et al. A method for feature selection hased on rough sets and ant colonyoptimization algorithm. Journal of Nan jing University(Natural Sciences),2010，46
(5): 487~493.(土璐，邱桃荣，何妞等. 基于粗糙集和蚁群优化算法的特征选择方法. 南京大学学报(自然科学)，2010, 46(5): 487~493)
[5]Xie J Y，Li N，Qiao Z R. Feature subset selec tion algorithms for incomplete decision systems based on neighborhood rough sets. Journal of Nanjing University(Natural Sciences)，2011，
47 (7): 383-390.(谢娟英，李楠，乔子茵. 基于邻域粗糙集的不完整决策系统特征选择算法.南京大学学报(自然科学)，2011, 47(7); 383一390).
[6]Miao D Q, Hu G R. A heuristic algorithm for reduction of knowledge. Journal of Computer Research and Development，1999，36(6): 681-684.(苗夺谦，胡桂荣.知识约简的一种启发式算法.计算机研究与发展，1999, 36 (6):681一684).
[7]Miao D Q, Wang J. An information representa- lion of the concepts and operations in rough set theory. Journal of Software, 1999，10(2): 113-116.苗夺谦，土环.粗糙集理论中概念与运算的信息表示.软件学报，1999, 10 (2):113一116.
[8]Liu S H，Sheng Q J，W B, et al. Research on efficient algorithms for rough set methods. Chi- nese Journal of Computers, 2003，26(5): 524~529.(刘少辉，盛球戮，吴斌等.Rough集理论高效算法的研究.计算机学报，2003，26 (5):524一629.
[9]Wang J，Wang J. Reduction algorithms based on discemibility matrix;The order attributes method. Journal of Computer Science and Tech- nology, 2001，16(6):489一504.
[10]Liang J Y，Qu K S, Xu Z B. Reduction of at- tribute in information systems. Systems Engi- necring-Theory and Practice, 2001，21 (12); 76~80.(梁吉业，曲开社，徐宗木.信息系统的属性约简.系统工程理论与实践，2001，21(12):76一80).
[11]Ma J M, Zhang W X, Zhu C H, information quantity-based attribute reduction in ordered in formation svstems. Svstems Engineering- Theory and Practice, 2010，30(9):1679一
1683.(马建敏，张文修，朱朝晖.基于信息量的序信息系统的属性约简.系统工程理论与实践，2010，30(9):1679一1683).
[12]Xu Z Y，Liu Z P. A quick attribute reduction algorithm with complexity of max{O(lCl lUl)，O(lCl 2U/C)}.Chinese Journal of Comput- ers, 2006, 29(3): 391~399.
(徐章艳，刘作鹏.一个复杂度为max{O(lCl l Ul)，O(lCl2l lU/Cl)}的快速属性约简算法.计算机学报，2006，29 (3):391一399).
[13]Liu Y，Xiong R，Chu J. Quick attribute redur tion algorithm with hash. Chinese Journal of Computers, 2009，32 (8):1493一1499.(刘勇，熊蓉，褚健.Hash快速属性约简算法. 计算机学报，2009, 32(8): 1493~1499).
[14]Skowron A，R auszer C.The discernibility ma- trices and functions in information systems. Fundamcnta lnformaticae, 1991，15(2): 331一362.
[15]Srarzyk J，Nelson D E, Sturtz K. Reduct gen eration in information system. Bulletin of Inter national Rough Set Society, 1998，3(1一2)
[16]Chen Y M，Miao D Q. Searching algorithm for attribute reduction based on power graph. Chi- nese Journal of Computers，2009，32(8): 1486~1492.(陈玉明，苗夺谦.基于幂图的属胜约简搜索式算法.计算机学报，2009, 32 (8):1486一1492).
19一22.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed