Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
International Journal of Machine Learning and Cybernetics
Published in: International Journal of Machine Learning and Cybernetics 9/2019

19-09-2018 | Original Article

Accelerating incremental attribute reduction algorithm by compacting a decision table

Authors: Wei Wei, Peng Song, Jiye Liang, Xiaoying Wu

Published in: International Journal of Machine Learning and Cybernetics | Issue 9/2019

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The evolution of object sets over time is ubiquitous in dynamic data. To acquire reducts for this type of data, researchers have proposed many incremental attribute reduction algorithms based on discernibility matrices. Although all reducts of an updated decision table can be obtained using these algorithms, their high computation time is a critical issue. To address this issue, we first construct three new types of discernibility matrices by compacting a decision table to eliminate redundant entries in the discernibility matrices of the original decision table. We then demonstrate that the set of reducts obtained from the compacted decision table are the same as those acquired from the original decision table. Extensive experiments have demonstrated that an incremental attribute reduction algorithm based on a compacted decision table can significantly accelerate attribute reduction for dynamic data with changing object sets while the acquired reducts are identical to those obtained using existing algorithms.
previous article A projection-based approach to software quality evaluation from the users’ perspectives
next article A bibliometric overview of International Journal of Machine Learning and Cybernetics between 2010 and 2017

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Show more products
Literature
1.
Bang WC, Zeungnam B (1999) New incremental learning algorithm in the framework of rough set theory. Int J Fuzzy Syst 1(1):25–36MathSciNet
2.
Chan C (1998) A rough set approach to attribute generalization in data mining. Inf Sci 107(1–4):177–194MathSciNet
3.
Chen HM, Li TR, Qiao SJ, Ruan D (2010) A rough set based dynamic maintenance approach for approximations in coarsening and refining attribute values. Int J Intell Syst 25:1005–1026CrossRefMATH
4.
Chen HM, Li TR, Ruan D (2013) A rough-set based incremental approach for updating approximations under dynamic maintenance environments. IEEE Trans Knowl Data Eng 25(2):274–284CrossRef
5.
Deng TQ, Yang CD, Wang XF (2012) A reduct derived from feature selection. Pattern Recogn Lett 33:1638–1646CrossRef
6.
Guan S, Li S (2001) Incremental learning with respect to new incoming input attributes. Neural Process Lett 14(3):241–260CrossRefMATH
7.
Chengxiang Hu, Liu Shixi, Liu Guoxiu (2017) Matrix-based approaches for dynamic updating approximations in multigranulation rough sets. Knowl Based Syst 122:51–63CrossRef
8.
Hu F, Wang GY, Huang H, Wu Y (2005) Incremental attribute reduction based on elementary sets. In: Proceeding of the 10th international conference on rough sets, fuzzy sets, data mining and granular computing, Regina, Canada, in: LNCS, vol 3641, pp 185–193
9.
Jing YG, Li TR, Luo C, Horng SJ, Wang GY, Yu Z (2016) An incremental approach for attribute reduction based on knowledge granularity. Knowl Based Syst 104:24–38CrossRef
10.
Jing YG, Li TR, Huang JF, Zhang YY (2016) An incremental attribute reduction approach based on knowledge granularity under the attribute generalization. Int J Approx Reason 76:80–95MathSciNetCrossRefMATH
11.
Jing YG, Li TR, Fujita H, Yu Z, Wang B (2017) An incremental attribute reduction approach based on knowledge granularity with a multi-granulation view. Inf Sci 411:23–38MathSciNetCrossRef
12.
Lang GM, Miao DQ, Cai MJ, Zhang ZF (2017) Incremental approaches for updating reducts in dynamic covering information systems. Knowl Based Syst 134:85–104CrossRef
13.
14.
Li JH, Mei CL, Lv YJ (2011) Knowledge reduction in decision formal contexts. Knowl Based Syst 24:709–715CrossRefMATH
15.
Li JH, Mei CL, Lv YJ (2013) Incomplete decision contexts: approximate concept construction, rule acquisition and knowledge reduction. Int J Approx Reason 54(1):149–165MathSciNetCrossRefMATH
16.
17.
Li SY, Li TR, Liu D (2013) Incremental updating approximations in dominance-based rough sets approach under the variation of the attribute set. Knowl Based Syst 40:17–26CrossRef
18.
Li TR, Ruan D, Geert W, Song J, Xu Y (2007) A rough sets based characteristic relation approach for dynamic attribute generalization in data mining. Knowl Based Syst 20(5):485–494CrossRef
19.
20.
Liang JY, Chin KS, Dang CY, Yam Richid CM (2002) A new method for measuring uncertainty and fuzziness in rough set theory. Int J Gen Syst 31(4):331–342MathSciNetCrossRefMATH
21.
Liang JY, Shi ZZ, Li DY, Wierman MJ (2006) The information entropy, rough entropy and knowledge granulation in incomplete information table. Int J Gen Syst 35(6):641–654MathSciNetCrossRefMATH
22.
Liang JY, Wang F, Dang CY, Qian YH (2014) A group incremental approach to feature selection applying rough set technique. IEEE Trans Knowl Data Eng 26(2):294–308CrossRef
23.
Liu D, Li TR, Ruan D, Zou WL (2009) An incremental approach for inducing knowledge from dynamic information systems. Fundam Inf 94(2):245–260MathSciNetMATH
24.
Liu D, Li TR, Ruan D, Zhang JB (2011) Incremental learning optimization on knowledge discovery in dynamic business intelligent systems. J Glob Optim 51:325–344MathSciNetCrossRefMATH
25.
Liu D, Li TR, Zhang JB (2014) A rough set-based incremental approach for learning knowledge in dynamic incomplete information systems. Int J Approx Reason 55:1764–1786MathSciNetCrossRefMATH
26.
Liu ZT (1999) An incremental arithmetic for the smallest reduction of attributes. Chin J Electron 27(11):96–98
27.
Orlowska M, Orlowski M (1992) Maintenance of knowledge in dynamic information systems. In: Slowinski R (ed) Intelligent decision support: handbook of applications and advances of the rough set theory. Kluwer Academic Publishers, South Holland, pp 315–330CrossRef
28.
Pawlak Z (1991) Rough sets: theoretical aspects of reasoning about data. Kluwer Academic Publishers, BostonCrossRefMATH
29.
30.
31.
Qian YH, Liang JY (2008) Combination entropy and combination granulation in rough set theory. Int J Uncertain Fuzziness Knowl Based Syst 16(2):179–193MathSciNetCrossRefMATH
32.
Shan N, Ziarko W (1995) Data-based acquisition and incremental modification of classification rules. Comput Intell 11(2):357–370CrossRef
33.
Shannon CE (1948) The mathematical theory of communication. Bell Syst Tech J 27(3, 4):373–423MathSciNet
34.
Shu WH, Shen H (2014) Updating attribute reduction in incomplete decision systems with the variation of attribute set. Int J Approx Reason 55:867–884MathSciNetCrossRefMATH
35.
Shu WH, Shen H (2014) Incremental feature selection based on rough set in dynamic incomplete data. Pattern Recogn 47:3890–3906CrossRef
36.
Skowron A, Rauszer C (1992) The discernibility matrices and functions in information systems. In: Slowinski R (ed) Intelligent decision support: handbook of applications and advances of the rough sets theory. Kluwer, Dordrecht
37.
Wang F, Liang JY, Dang CY (2013) Attribute reduction for dynamic data sets. Appl Soft Comput 13:676–689CrossRef
38.
Wang F, Liang JY, Qian YH (2013) Attribute reduction: a dimension incremental strategy. Knowl Based Syst 39:95–108CrossRef
39.
Wang GY, Yu H, Yang DC (2002) Decision table reduction based on conditional information entropy. Chin J Comput 25(7):759–766MathSciNet
40.
Wang J, Wang J (2001) Reduction algorithms based on discernibility matrix: the ordered attributes method. J Comput Sci Technol 16(6):489–504MathSciNetCrossRefMATH
41.
42.
Wei W, Liang JY, Wang JH, Qian YH (2013) Decision-relative discernibility matrixes in the sense of entropies. Int J Gen Syst 42(7):721–738MathSciNetCrossRefMATH
43.
Wei W, Wang JH, Liang JY, Mi X, Dang CY (2015) Compacted decision tables based attribute reduction. Knowl Based Syst 86:261–277CrossRef
44.
45.
Xie XJ, Qin XL (2018) A novel incremental attribute reduction approach for dynamic incomplete decision systems. Int J Approx Reason 93:443–462MathSciNetCrossRefMATH
46.
Xu WH, Guo YT (2016) Generalized multigranulation double-quantitative decision-theoretic rough set. Knowl Based Syst 105:190–205CrossRef
47.
Xu WH, Yu JH (2017) A novel approach to information fusion in multi-source datasets: a granular computing viewpoint. Inf Sci 378:410–423CrossRef
48.
Xu YT, Wang LS, Zhang RY (2011) A dynamic attribute reduction algorithm based on 0–1 integer programming. Knowl Based Syst 24:1341–1347CrossRef
49.
Yang M (2006) An incremental updating algorithm of the computation of a core based on the improved discernibility matrix. Chin J Comput 29(3):407–413
50.
Yang XB, Qi Y, Yu HL, Song XN, Yang JY (2014) Updating multigranulation rough approximations with increasing of granular structures. Knowl Based Syst 64:59–69CrossRef
51.
Ju HR, Yang XB, Song XN, Qi YS (2014) Dynamic updating multigranulation fuzzy rough set: approximations and reducts. Int J Mach Learn Cybern 5:981–990CrossRef
52.
53.
Zhang JB, Li TR, Ruan D, Liu D (2012) Rough sets based matrix approaches with dynamic attribute variation in set-valued information systems. Int J Approx Reason 53:620–635MathSciNetCrossRefMATH
Metadata
Title
Accelerating incremental attribute reduction algorithm by compacting a decision table
Authors
Wei Wei
Peng Song
Jiye Liang
Xiaoying Wu
Publication date
19-09-2018
Publisher
Springer Berlin Heidelberg
Published in
International Journal of Machine Learning and Cybernetics / Issue 9/2019
Print ISSN: 1868-8071
Electronic ISSN: 1868-808X
DOI
https://doi.org/10.1007/s13042-018-0874-x

Other articles of this Issue 9/2019

International Journal of Machine Learning and Cybernetics 9/2019 Go to the issue

Original Article

State of health prediction for lithium-ion batteries using multiple-view feature fusion and support vector regression ensemble

Original Article

Digital hardware realization of a novel adaptive ink drop spread operator and its application in modeling and classification and on-chip training

Original Article

Initial-training-free online sequential extreme learning machine based adaptive engine air–fuel ratio control

Original Article

Attribute-oriented cognitive concept learning strategy: a multi-level method

Original Article

Granulation selection and decision making with multigranulation rough set over two universes

Original Article

A bibliometric overview of International Journal of Machine Learning and Cybernetics between 2010 and 2017