More Web Proxy on the site http://driver.im/

research-article

Discernibility matrix based incremental attribute reduction for dynamic data

Authors:

Yijun SunAuthors Info & Claims

Knowledge-Based Systems, Volume 140, Issue C

Pages 142 - 157

https://doi.org/10.1016/j.knosys.2017.10.033

Published: 15 January 2018 Publication History

Abstract

Dynamic data, in which the values of objects vary over time, are ubiquitous in real applications. Although researchers have developed a few incremental attribute reduction algorithms to process dynamic data, the reducts obtained by these algorithms are usually not optimal. To overcome this deficiency, in this paper, we propose a discernibility matrix based incremental attribute reduction algorithm, through which all reducts, including the optimal reduct, of dynamic data can be incrementally acquired. Moreover, to enhance the efficiency of the discernibility matrix based incremental attribute reduction algorithm, another incremental attribute reduction algorithm is developed based on the discernibility matrix of a compact decision table. Theoretical analyses and experimental results indicate that the latter algorithm requires much less time to find reducts than the former, and that the same reducts can be output by both.

References

[1]

D.G. Chen, C.Z. Wang, Q.H. Hu, A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets, Inf. Sci. (Ny), 177 (2007) 3500-3518.

Digital Library

[2]

D.G. Chen, Y.Y. Yang, Z. Dong, An incremental algorithm for attribute reduction with variableprecision rough sets, Appl. Soft. Comput., 45 (2016) 129-149.

Digital Library

[3]

S. Guan, S. Li, Incremental learning with respect to new incoming input attributes, Neural Process. Lett., 14 (2001) 241-260.

Digital Library

[4]

F. Hu, G.Y. Wang, H. Huang, Y. Wu, Incremental attribute reduction based on elementary sets, 2005.

[5]

Q.H. Hu, Z.X. Xie, D.R. Yu, Hybrid attribute reduction based on a novel fuzzyrough model and information granulation, Pattern Recognit., 40 (2007) 3509-3521.

Digital Library

[6]

Q.H. Hu, J.F. Liu, D.R. Yu, Mixed feature selection based on granulation and approximation, Knowl. Based Syst., 21 (2008) 294-304.

Digital Library

[7]

Y.G. Jing, T.R. Li, J.F. Huang, An incremental attribute reduction approach based on knowledge granularity under the attribute generalization, Int. J. Approx. Reason., 76 (2016) 80-95.

Digital Library

[8]

S.Y. Li, T.R. Li, D. Liu, Incremental updating approximations in dominance-based rough sets approach under the variation of the attribute set, Knowl. Based Syst., 40 (2013) 17-26.

Digital Library

[9]

T.R. Li, D. Ruan, W. Geert, J. Song, Y. Xu, A rough sets based characteristic relation approach for dynamic attribute generalization in data mining, Knowl. Based Syst., 20 (2007) 485-494.

Digital Library

[10]

J.Y. Liang, K.S. Chin, C.Y. Dang, C.M. Yam, Richid, a new method for measuring uncertainty and fuzziness in rough set theory, Int. J. Gen. Syst., 31 (2002) 331-342.

[11]

J.Y. Liang, Z.Z. Shi, D.Y. Li, M.J. Wierman, The information entropy, rough entropy and knowledge granulation in incomplete information table, Int. J. Gen. Syst., 35 (2006) 641-654.

[12]

J.Y. Liang, W. Wei, Y.H. Qian, An incremental approach to computation of a core based on conditional entropy, Syst. Eng.-Theor. Pract., 28 (2008) 81-89.

[13]

J.Y. Liang, J.H. Wang, Y.H. Qian, A new measure of uncertainty based on knowledge granulation for rough sets, Inf. Sci. (Ny), 179 (2009) 458-470.

Digital Library

[14]

J.Y. Liang, F. Wang, C.Y. Dang, Y.H. Qian, A group incremental approach to feature selection applying rough set technique, IEEE Trans. Knowl. Data Eng., 26 (2014) 294-308.

Digital Library

[15]

D. Liu, T.R. Li, D. Ruan, W.L. Zou, An incremental approach for inducing knowledge from dynamic information systems, Fundam. Inf., 94 (2009) 245-260.

Digital Library

[16]

D. Liu, T.R. Li, D. Ruan, J.B. Zhang, Incremental learning optimization on knowledge discovery in dynamic business intelligent systems, J. Global Optim., 51 (2011) 325-344.

Digital Library

[17]

D. Liu, T.R. Li, J.B. Zhang, A rough set-based incremental approach for learning knowledge in dynamic incomplete information systems, Int. J. Approx. Reason., 55 (2014) 1764-1786.

Digital Library

[18]

G.L. Liu, Z. Hua, Z.H. Chen, A general reduction algorithm for relation decision systems and its applications, Knowl. Based Syst., 119 (2017) 87-93.

Digital Library

[19]

Z.T. Liu, An incremental arithmetic for the smallest reduction of attributes, Chin. J. Electron., 27 (1999) 96-98.

[20]

J.S. Mi, W.Z. Wu, W.X. Zhang, Knowledge reducts based on variable precision rough set theory, Syst. Eng.-Theor. Pract., 24 (2004) 76-82.

[21]

Z. Pawlak, Rough Sets: Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Boston, 1991.

Digital Library

[22]

Z. Pawlak, A. Sknwron, Rough sets and boolean reasoning, Inf. Sci. (Ny), 177 (2007) 41-73.

[23]

Z. Pawlak, A. Skowron, Rudiments of rough sets, Inf. Sci. (Ny), 177 (2007) 3-27.

[24]

Y.H. Qian, J.Y. Liang, Combination entropy and combination granulation in incomplete information system, Lect. Notes Comput. Sci., 4062 (2006) 184-190.

Digital Library

[25]

Y.H. Qian, J.Y. Liang, Combination entropy and combination granulation in rough set theory, Int. J. Uncertainty, Fuzziness Knowl.-Based Syst., 16 (2008) 179-193.

[26]

Y.H. Qian, J.Y. Liang, W. Pedrycz, Positive approximation: an accelerator for attribute reduction in rough set theory, Artif. Intell., 174 (2010) 597-618.

Digital Library

[27]

C.E. Shannon, The mathematical theory of communication, Bell Syst. Techn. J., 27 (1948) 373-423.

[28]

W.H. Shu, H. Shen, Updating attribute reduction in incomplete decision systems with the variation of attribute set, Int. J. Approx. Reason., 55 (2014) 867-884.

Digital Library

[29]

W.H. Shu, H. Shen, Incremental feature selection based on rough set in dynamic incomplete data, Pattern Recognit., 47 (2014) 3890-3906.

[30]

W.H. Shu, W.B. Qian, An incremental approach to attribute reduction from dynamic incomplete decision systems in rough set theory, Data Knowl. Eng., 100 (2015) 116-132.

Digital Library

[31]

R.W. Swiniarski, A. Skowron, Rough set methods in feature selection and recognition, Pattern Recognit. Lett., 24 (2003) 833-849.

Digital Library

[32]

S.H. Teng, M. Lu, A.F. Yang, J. Zhang, Y.J. Nian, M. He, Efficient attribute reduction from the viewpoint of discernibility, Inf. Sci. (Ny), 326 (2016) 297-314.

Digital Library

[33]

C.Z. Wang, Y.L. Qi, M.W. Shao, Q.H. Hu, D.G. Chen, Y.H. Qian, Y.J. Lin, A fitting model for feature selection with fuzzy rough sets, IEEE Trans. Fuzzy Syst., 25 (2016) 741-753.

[34]

C.Z. Wang, M.W. Shao, Q. He, Y.H. Qian, Y.L. Qi, Feature subset selection based on fuzzy neighborhood rough sets, Knowl. Based Syst., 111 (2016) 173-179.

Digital Library

[35]

F. Wang, J.Y. Liang, C.Y. Dang, Attribute reduction for dynamic data sets, Appl. Soft Comput., 13 (2013) 676-689.

Digital Library

[36]

F. Wang, J.Y. Liang, Y.H. Qian, Attribute reduction: a dimension incremental strategy, Knowl. Based Syst., 39 (2013) 95-108.

Digital Library

[37]

G.Y. Wang, H. Yu, D.C. Yang, Decision table reduction based on conditional information entropy, Chin. J. Comput., 25 (2002) 759-766.

[38]

W. Wei, J.Y. Liang, Y.H. Qian, F. Wang, An attribute reduction approach and its accelerated version for hybrid data, IEEE ICCI (2009) 167-173.

[39]

W. Wei, J.Y. Liang, J.H. Wang, Y.H. Qian, Decision-relative discernibility matrixes in the sense of entropies, Int. J. Gen. Syst., 42 (2013) 721-738.

[40]

W. Wei, J.H. Wang, J.Y. Liang, X. Mi, C.Y. Dang, Compacted decision tables based attribute reduction, Knowl.Based Syst., 86 (2015) 261-277.

Digital Library

[41]

W. Wei, J.B. Cui, J.Y. Liang, J.H. Wang, Fuzzy rough approximations for set-valued data, Inf. Sci. (Ny), 360 (2016) 181-201.

Digital Library

[42]

J. Xie, X.F. Shen, H.F. Liu, Research on an incremental attribute reduction based on relative positive region, J. Comput. Inf. Syst., 9 (2013) 6621-6628.

[43]

Y.T. Xu, L.S. Wang, R.Y. Zhang, A dynamic attribute reduction algorithm based on 01 integer programming, Knowl. Based Syst., 24 (2011) 1341-1347.

Digital Library

[44]

M. Yang, An incremental updating algorithm of the computation of a core based on the improved discernibility matrix, Chin. J. Comput., 29 (2006) 407-413.

[45]

M. Yang, An incremental updating algorithm for attribute reduction based on improved discernibility matrix, Chin. J. Comput., 30 (2007) 815-822.

[46]

Y.Y. Yao, Y. Zhao, Attribute reduction in decision-theoretic rough set models, Inf. Sci. (Ny), 178 (2008) 3356-3373.

Digital Library

[47]

Y.Y. Yao, Y. Zhao, Discernibility matrix simplification for constructing attribute reducts, Inf. Sci. (Ny), 179 (2009) 867-882.

Digital Library

[48]

J.B. Zhang, T.R. Li, D. Ruan, D. Liu, Rough sets based matrix approaches with dynamic attribute variation in set-valued information systems, Int. J. Approx. Reason., 53 (2012) 620-635.

Digital Library

Cited By

Zhao JWu DZhou YLiang JWei WLi Y(2024)Rough set Theory-Based group incremental approach to feature selectionInformation Sciences: an International Journal10.1016/j.ins.2024.120733675:COnline publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1016/j.ins.2024.120733
Xu WYang YDing YChen XLv X(2024)Incremental feature selection approach to multi-dimensional variation based on matrix dominance conditional entropy for ordered data setApplied Intelligence10.1007/s10489-024-05411-354:6(4890-4910)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s10489-024-05411-3
Liang BLu Z(2023)Attribute reduction algorithm based on combined distance in clusteringJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-22266645:1(1481-1496)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.3233/JIFS-222666
Show More Cited By

Recommendations

An incremental algorithm for attribute reduction with variable precision rough sets

Display Omitted Two Boolean row vectors are introduced to characterize the disdernibility matrix and reduct.Rather than the whole discernibility matrix, minimal elements are incrementally computed.The attribute reduction process is studied to reveal how ...
An Efficient Algorithm for Attribute Reduction Based on Discernibility Matrix
ICBMI '11: Proceedings of the 2011 International Conference on Intelligent Computation and Bio-Medical Instrumentation

A definition for reducing discernibility matrix is provided, and a reduction relative of discernibility set is analyzed to reduce the time complexity of attribute reduction algorithm based on traditional matrix. Use iterative idea to select the ...
Incremental reduction methods based on granular ball neighborhood rough sets and attribute grouping
Abstract
In the framework of rough sets, incremental algorithms can effectively reduce repetitive computations for dynamic datasets by discovering the update principles of relevant knowledge. Considering the variations in attribute sets, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Knowledge-Based Systems

Knowledge-Based Systems Volume 140, Issue C

January 2018

214 pages

ISSN:0950-7051

Issue’s Table of Contents

Copyright © Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 15 January 2018

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhao JWu DZhou YLiang JWei WLi Y(2024)Rough set Theory-Based group incremental approach to feature selectionInformation Sciences: an International Journal10.1016/j.ins.2024.120733675:COnline publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1016/j.ins.2024.120733
Xu WYang YDing YChen XLv X(2024)Incremental feature selection approach to multi-dimensional variation based on matrix dominance conditional entropy for ordered data setApplied Intelligence10.1007/s10489-024-05411-354:6(4890-4910)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s10489-024-05411-3
Liang BLu Z(2023)Attribute reduction algorithm based on combined distance in clusteringJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-22266645:1(1481-1496)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.3233/JIFS-222666
Xu WYang Y(2023)Matrix-based feature selection approach using conditional entropy for ordered data set with time-evolving featuresKnowledge-Based Systems10.1016/j.knosys.2023.110947279:COnline publication date: 4-Nov-2023
https://dl.acm.org/doi/10.1016/j.knosys.2023.110947
Zhang XHuang XXu W(2023)Matrix-based multi-granulation fusion approach for dynamic updating of knowledge in multi-source informationKnowledge-Based Systems10.1016/j.knosys.2023.110257262:COnline publication date: 28-Feb-2023
https://dl.acm.org/doi/10.1016/j.knosys.2023.110257
Xu JXin PZhang Y(2023)Three-way neighborhood based stream computing for incomplete hybrid information systemKnowledge-Based Systems10.1016/j.knosys.2022.110232262:COnline publication date: 28-Feb-2023
https://dl.acm.org/doi/10.1016/j.knosys.2022.110232
Yang LQin KSang BFu C(2023)A novel incremental attribute reduction by using quantitative dominance-based neighborhood self-informationKnowledge-Based Systems10.1016/j.knosys.2022.110200261:COnline publication date: 15-Feb-2023
https://dl.acm.org/doi/10.1016/j.knosys.2022.110200
Zhang XLi J(2023)Incremental feature selection approach to interval-valued fuzzy decision information systems based on λ-fuzzy similarity self-informationInformation Sciences: an International Journal10.1016/j.ins.2023.01.058625:C(593-619)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1016/j.ins.2023.01.058
Zhang SLiu KXu TYang XZhang A(2023)A meta-heuristic feature selection algorithm combining random sampling accelerator and ensemble using data perturbationApplied Intelligence10.1007/s10489-023-05123-053:24(29781-29798)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1007/s10489-023-05123-0
Shu WYu JChen TQian W(2023)Neighbourhood discernibility degree-based semisupervised feature selection for partially labelled mixed-type data with granular ballApplied Intelligence10.1007/s10489-023-04657-753:19(22467-22487)Online publication date: 29-Jun-2023
https://dl.acm.org/doi/10.1007/s10489-023-04657-7
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents