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

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

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

王晓帆^1,2;王宝树¹;柴慧敏¹

(1. 西安电子科技大学计算机学院，陕西西安 710071；
2. 西安理工大学计算机学院，陕西西安 710048)

收稿日期:2010-05-19 出版日期:2010-12-20 发布日期:2011-01-22
作者简介:王晓帆(1976-)，男，讲师，西安电子科技大学博士研究生，E-mail: wangxfok@xaut.edu.cn．
基金资助:
国家部委预研基金资助项目(51315080202)

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

摘要/Abstract

摘要：

为快速计算粗糙集的一个属性约简与核，提出一种基于属性-值树模型的改进约简与求核算法，并证明了算法的完备性．该算法充分利用树型结构，引进树的合并方法，使得计算复杂度从O(|U||C|2)降低为O(|U||C|)，提高了计算效率(其中|U|和|C|分别代表对象个数和属性个数)．

关键词: 粗糙集, 决策表, 属性约简, 属性-值树

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

中图分类号:

TP14

王晓帆;王宝树;柴慧敏. 一种基于属性-值树的求核与约简方法[J]. J4, 2010, 37(6): 1111-1118.

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.

参考文献

[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)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

Metrics

本文评价

推荐阅读 0

[1]	王立宏(1;2);吴耿峰(2). 决策表属性约简的代数观和信息观分析[J]. J4, 2005, 32(1): 156-160.
[2]	张建军1;张静波2. 一种新的基于粗糙集理论的决策表离散化算法[J]. J4, 2004, 31(3): 469-472.
[3]	刘振华;刘三阳;王珏. 基于信息量的一种属性约简算法[J]. J4, 2003, 30(6): 0-0.
[4]	王珏;刘三阳;张杰;刘振华. 多值RS理论中的属性约简算法[J]. J4, 2003, 30(2): 277-280.
[5]	李艾华;张玉祥;屈梁生. 改进的决策树生成算法在电路板故障诊断中的应用[J]. J4, 1999, 26(5): 579-584.