一种基于属性-值树的求核与约简方法

doi:10.3969/j.issn.1001-2400.2010.06.024

J4 ›› 2010, Vol. 37 ›› Issue (6): 1111-1118.doi: 10.3969/j.issn.1001-2400.2010.06.024

• Original Articles • Previous Articles Next Articles

Algorithm based attribute-value-tree for calculation of core and attribute reduction

WANG Xiao-fan^1,2;WANG Bao-shu¹;CHAI Hui-min¹

(1. School of Computer Science and Technology, Xidian Univ., Xi'an 710071， China;
2. School of Computer Sci. and Tech., Xi'an Univ. of Tech., Xi'an 710048， China)

Received:2010-05-19 Online:2010-12-20 Published:2011-01-22
Contact: WANG Xiao-fan E-mail:wangxfok@xaut.edu.cn

Abstract

Abstract:

In order to get attribute reduction or calculate the core of rough sets quickly, a new algorithm of attribute reduction and computing core is brought forward based on the attribute-value-tree model and its correctness is proved. The greatest advantage of the algorithm is that the time and space complexity are reduced efficiently by using the method of merging trees. The computational complexity of reduction is changed from O(|U||C|2) to O(|U||C|) where |U| and |C| are the numbers of objects and attributes.

Key words: rough sets, decision table, attribute reduction, attribute-value-tree

CLC Number:

TP14

WANG Xiao-fan;WANG Bao-shu;CHAI Hui-min. Algorithm based attribute-value-tree for calculation of core and attribute reduction[J].J4, 2010, 37(6): 1111-1118.

References

[1] Pawlak Z. Rough Sets:Theoretical Aspects of Reasoning about Data[M]. Boston: Kluwer Academic Publisher, 1991.
[2] Pawlak Z. Rough Set Approach to Multi-attribute Decision Analysis[J]. European Journal of Operational Research, 1994(1): 443-459.[3] Polkowski L, Skowron A. Rough Mereology: a New Paradigm for Approximate Reasoning[J]. International Joranal of Approximate Reasoning, 1997, 15(4): 333-365.
[4] 张文修, 吴伟志, 梁吉业, 等. 粗糙集理论与方法[M]. 北京: 科学出版社，2001.
[5] Wang Guoyin. Rough Set Theory and Knowledge Acquisition[M]. Xi'an: Xi'an Jiaotong University Press, 2001.
[6] Hu XiaoHua, Cercone N. Learning in Relational Databases: a Rough Set Approach[J]. Computational Intelligence, 1995,11(2): 323-337.
[7] Jelonek J. Rough Set Reduction of Attributes and Their Domains Forneural Networks[J]. Computational Intelligence, 1995,11(2):338-347.
[8] 杨明, 孙志辉. 改进的差别矩阵及其求核算法[J]. 复旦大学学报(自然科学版), 2004, 43(5):865-872.
Yang Ming, Sun Zhihui. Improvement of Discernibility Matrix and the Computation of a Core[J]. Journal of Fudan University(Natural Science), 2004, 43(5): 865-872.
[9] 叶东毅, 陈昭炯. 一个新的差别矩阵及其求核方法[J]. 电子学报, 2002, 30(7): 1086-1088.
Ye Dongyi, Chen Shaojiong. A New Discernibility Matrix and the Computation of a Core[J]. Acta electronic China, 2002, 30(7): 1086-1088.
[10] 王国胤,于洪,杨大春. 基于条件信息熵的决策表约简[J].计算机学报, 2002, 25(7): 759-766.
Wang Guoyin, Yu Hong, Yang Dachun. Decision Table Reduction Based on Conditional Information Entropy[J]. Chinese Journal of Computers, 2002, 25(7): 759-766.
[11] 聂红梅, 周家庆. 一个新的差别矩阵及其求核方法[J]. 四川大学学报(自然科学版), 2007, 44(2): 277-383.
Nie Hongmei, Zhou Jiaqing. A New Discernibility Matrix and the Computation of a Core[J]. Journal of Sichuan University(Natural Science Edition),2007,44(2):277-383.
[12] 刘振华,刘三阳,王珏. 基于信息量的一种属性约简算法[J]. 西安电子科技大学学报, 2003, 30(6): 835-838.
Liu Zhenhua, Liu Sanyang, Wang Jue. An Attribute Reduction Algorithm Based on the Information Quantity[J]. Journal of Xidian University(J), 2003, 30(6): 835-838.
[13] Xu E, Tong Shaocheng, Jiang Yueling, et al. A Method Based on Rough Set for Decision Making[C]//Fifth International Conference on Fuzzy Systems and Knowledge Discovery. Jinan: Shangdong University, 2008: 70-74.
[14] 苏健,高济. 粗糙决策支持方法[J]. 计算机学报，2003(6): 737-745.
Su Jian, Gao Ji. Rough Decision Support Method[J]. Chinese Journal of Computers, 2003(6): 737-745.
[15] Tsang E C C, Chen Degang, Daniel S, et al. Attributes Reduction Using Fuzzy Rough Sets[J]. Fuzzy Systems, 2008(16): 1130-1141.
[16] Zhao Ming. Data Description Based on Reduct Theory[D]. Beijing: Institute of Automation, Chinese Academy of Sciences, 2004.
[17] Han Suqing, Wang Jue. Second Attribute Algorithm Based on Tree Expression[J]. Journal of Computer Science & Technology, 2006,21(3),383-392.
[18] Zhao Min, Han Suqing, Wang Jue. Tree Expressions for Information System[J]. Journal of Computer Science & Technology, 2007,22(2),297-307.
[19] Quinlan J. Induction of Decisions Trees[J]. Machine Learning,1986(1): 81-106.
[20] 苗夺谦,李国道. 粗糙集理论算法与应用[M]. 北京：清华大学出版社，2008.

Algorithm based attribute-value-tree for calculation of core and attribute reduction

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 2

Metrics

Comments

Recommended 0

[1]	WANG Li-hong(1;2);WU Geng-feng(2). Attribute reduction of a decision table in algebra view and information view [J]. J4, 2005, 32(1): 156-160.
[2]	ZHANG Jian-jun1;ZHANG Jing-bo2. A noval rough set theory-based decision table discretization algorithm [J]. J4, 2004, 31(3): 469-472.