基于属性重要度并行约简算法的优化*

南京大学学报(自然科学版) ›› 2012, Vol. 48 ›› Issue (4): 376–382.

基于属性重要度并行约简算法的优化*

陈林，邓大勇**，闰电勋

出版日期:2015-06-19 发布日期:2015-06-19
作者简介: (浙江师范大学数理信息学院，金华，321004)
基金资助:
浙江省教育厅基金(Y200805421)

Optimization of parallel reducts algorithm based on attribute significance

Chen Lin，Deng Da-Yong ,Yan Dian Xun

Online:2015-06-19 Published:2015-06-19
About author: (College of Mathematics，Physics and Information Engineering Zhejiang Normal University,
Jinhua, 321004，China)

摘要/Abstract

摘要： 针对约简长度和时间效率两方面问题，提出了一种基于属性重要度并行约简的优化算法.该算法通过对每个子表赋权值，并在所建立的属性重要度矩阵中选择权值之和最大的列所对应的属性作为约简属性，所得到的约简即为并行约简.最后，通过UCI机器学习数据库中的几个实例验证了改进后算法的正确性和有效性.

Abstract: In this paper, we propose an optimization parallel reducts algorithm based on attribute significance for the time efficiency and the length of parallel reducts.The first to do in the optimization algorithm is the same as the original algorithm; we should establish the matrix of attribute significance，every clement in a row denotes the attribute significance of various conditional attributes in the same decision sulrtable; every clement in a column denotes the attribute significance of a conditional attribute in various decision sulrtables.The idea of the original algorithm is as follows，we obtain the set of core attributes which every elements in a column arc bigger than zero in the matrix of attribute significance at first，then we obtain the rest of attributes in parallel reducts through the modified matrix of attribute significance, of which the number of nonzero elements in a column is the most，then add the attribute to the parallel reduct，we don’t add attributes until each clement in the modified matrix of attribute significance is zero.The way of selecting conditional attributes is objective, and we may ignore the size of attribute
significance. In addition, we don’t consider the characteristics of the data. From the characteristics of the data and the process of attribute selection, we assign weights to each sulrtable and improve the way of selecting conditional attributes.The innovation of the algorithm is that we assign weights to each sulrtable and select an clement from the set of condition attributes in the modified matrix of attribute significance, of which the sum of column is maximal，and then add the clement to the parallel reduct.The more efficiency and the shorter length of the obtained parallel reducts arc demonstrated by several classical databases from the UCl repository. At last, we use the 10-fold cross-validation to test the accuracy of algorithms; the experimental results show that the accuracy of the improved
algorithm is higher than the original algorithm.

陈林，邓大勇**，闰电勋
. 基于属性重要度并行约简算法的优化*[J]. 南京大学学报(自然科学版), 2012, 48(4): 376–382.

Chen Lin，Deng Da-Yong ,Yan Dian Xun
. Optimization of parallel reducts algorithm based on attribute significance
[J]. Journal of Nanjing University(Natural Sciences), 2012, 48(4): 376–382.

参考文献

[1]Pawlak Z. Rough sets; Theoretical aspects of reasoning about data. Dordrecht:Kluwer Aca- demic Publishers，1991，229.
[2]Liu Q.Rough sets and rough reasoning.Be jing:Science Publishing,2001,254.(刘清Rough集及Rough推理.北京:科学出版社，2001,254)
[3]Deng D Y，Huang H K. A new discernibility matrix and function. Wang G Y，James F P, Andrzej S, et al. Rough sets and knowledge
technology. Springer-Verlag, 2006，114一121.
[4]Deng D Y. Research on data reduction based on rough sets and extension of rough set models. Doctoral Dissertation. Beijing; Beijing Jiaotong
University, 2007.(邓大勇.基于粗糙集的数据约简粗糙集扩展模型的研究.博士论文.北京:北京交通大学，2007).
[5]Liu Z T.An incremental arithmetic for the smallest reduction of attributes. Acta Electroni- ca Sinica, 1999, 27(11):96-98.(刘宗田.属
胜最小约简的增量式算法.电子学报，1999, 27 (11):96一98).
[6]Wang J，Wang J. Reduction algorithms based on discernibility matrix;The order attributes method. Journal of Computer Science and Tech-
nology, 200，16(6):489一504.
[7]Zheng Z, Wang G Y，W Y. A rough set and rule tree based incremental knowledge acquisi- tion algorithm. Fundamcnta lnformaticae-Spe-
cial Issue on the 9^th international Conference on Rough Sets, Fuzzy Sets, Data Mining and Granular Computing, 2003，59:299一313.
[8]Kryszkicwicz M，R ybinski H. Finding reducts in composed information systems. Proceedings 0f International Workshop on Rough Sets and
Knowledge Discovery, Springer-Verlag, 1993 259一268.
[9]Deng D Y. Attribute reduction among decision tables by voting. Proceedings of 2008 IEEE in- ternational Conference of Granular Computing, 2008，183一187.
[10]Bazan G J. A comparison of dynamic non-dy- namic rough set methods for extracting laws from decision tables. Polkowski I.，Skowron A.
Rough Sets in Knowledge Discovery 1:Method- ology and Applications, Heidelberg; Physicx Verlag, 1998，321一365.
[11]Bazan G J，Nguyen H S, Synak，P，et al. Rough set algorithms in classification problem. Polkowski L,Tsumoto S, Lin T Y. Rough Set
Methods and Applications. Heidelberg; Physi- ca-Verlag, 2000，49一88.
[12]Deng D Y，Wang J Y，Li X J. Parallel reducts in a series of decision subsystems. Proceedings of the 2^nd International Joint Conference on
Computational Sciences and Optimization,2009,2:377~380
[13]Deng D Y. Comparison of parallel reducts and dynamic reducts in theory. Computer Science, 2009，36(8A):176一178.
[14]Deng D Y. Parallel reducts and its properties. Proceedings of 2009 IEEE International Confer ence on Granular Computing, 2009:121一125
[15]Deng D Y.(F,e)-Parallel reducts in a series of decision subsystems. Proceedings of the 3rd In- ternational Joint Conference on Computational
Sciences and Optimization, 2010，2:372一376.
[16]Deng D Y，Yan D X, Wang J Y. Parallel re- ducts based on attribute significance. Proceed- ings of the 5^thinternational Conference of Rough
Set and Knowledge Technology. Lecture Notes in Computer Science. Springer-Verlag, 2010，6401:336一343.
[17]http://archive. ics. uci. edu/ml/
[18]Yin X R，Shang L. Extension model of rough sets under incomplete information systems. Journal of Nanjing University(Natural Sci-
ences), 2006, 42(4); 337-341.(尹旭口，商琳.不完备信息系统中Rough集的扩充模型. 南京大学学报(自然科学)，2006, 42(4); 337一341).

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed