article

Approximate entropy reducts

Author:

Dominik ŞlȩzakAuthors Info & Claims

Fundamenta Informaticae, Volume 53, Issue 3,4

Pages 365 - 390

Published: 30 May 2002 Publication History

Abstract

We use information entropy measure to extend the rough set based notion of a reduct. We introduce the Approximate Entropy Reduction Principle (AERP). It states that any simplification (reduction of attributes) in the decision model, which approximately preserves its conditional entropy (the measure of inconsistency of defining decision by conditional attributes) should be performed to decrease its prior entropy (the measure of the model's complexity). We show NP-hardness of optimization tasks concerning application of various modifications of AERP to data analysis.

References

[1]

{1} Agrawal, R., Mannila, H., Srikant, R., Toivonen, H., Verkamo, A.I.: Fast discovery of assocation rules. In: V.M. Fayad, G. Piatetsky Shapiro, P. Smyth, R. Uthurusamy (eds): Advances in Knowledge Discovery and Data Mining. AAAI/MIT Press (1996) pp. 307-328.]]

Digital Library

[2]

{2} An, A., Cercone, N.: Rule quality measures for rule induction systems: Description and evaluation. Computational Intelligence 17/3 (2001) pp. 409-424.]]

[3]

{3} Bazan, J.G., Nguyen, H.S., Nguyen, S.H, Synak, P., Wróblewski, J.: Rough Set Algorithms in Classification Problem. In: {18} (2000) pp. 49-88.]]

Digital Library

[4]

{4} Duentsch, I., Gediga, G.: Uncertainty measures of rough set prediction. Artificial Intelligence 106 (1998) pp. 77-107.]]

Digital Library

[5]

{5} Gallager, R.G.: Information Theory and Reliable Communication. Wiley (1968).]]

Digital Library

[6]

{6} Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to The Theory of NP-Completeness. Freeman and Company (1979).]]

Digital Library

[7]

{7} Kapur, J.N., Kesavan, H.K.: Entropy Optimization Principles with Applications. Academic Press (1992).]]

[8]

{8} Komorowski, J., Pawlak, Z., Polkowski, L., Skowron, A.: Rough sets: A tutorial. In: S.K. Pal, A. Skowron (eds): Rough Fuzzy Hybridization - A New Trend in Decision Making. Springer Verlag (1999) pp. 3-98.]]

[9]

{9} Kloesgen, W., Zytkow, J.M. (eds): Handbook of Data Mining and Knowledge Discovery. Oxford University Press (2002).]]

Digital Library

[10]

{10} Li, M., Vitanyi, P.: An Introduction to Kolmogorov Complexity and Its Applications. Springer Verlag (1997).]]

Digital Library

[11]

{11} Mitchell, T.: Machine Learning. Mc Graw Hill (1998).]]

[12]

{12} Pawlak, Z.: Information Systems: Theoretical Foundations (In Polish). WNT (1983).]]

[13]

{13} Pawlak, Z.: Rough sets - Theoretical aspects of reasoning about data. Kluwer (1991).]]

Digital Library

[14]

{14} Pawlak, Z., Skowron, A.: Rough membership functions. In: Advances in the Dempster Shafer Theory of Evidence. Wiley (1994) pp. 251-271.]]

Digital Library

[15]

{15} Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann (1988).]]

Digital Library

[16]

{16} Polkowski, L.: Rough Sets: Mathematical Foundations. Phisica Verlag (2002).]]

Digital Library

[17]

{17} Polkowski, L., Skowron, A. (eds): Rough Sets in Knowledge Discovery. Physica Verlag (1998), parts 1, 2.]]

Digital Library

[18]

{18} Polkowski, L., Tsumoto, S., Lin, T.Y. (eds): Rough Set Methods and Applications: New Developments in Knowledge Discovery in Information Systems. Physica Verlag (2000).]]

Digital Library

[19]

{19} Provost. F., Fawcett, T., Kohavi, R.: The case against accuracy estimation for comparing induction algorithms. In: Proc. of IMLC'98. Madison, WI (1998).]]

Digital Library

[20]

{20} Rissanen J.: Minimum-description-length principle. In: S. Kotz, N.L. Johnson (eds), Encyclopedia of Statistical Sciences. Wiley (1985) pp. 523-527.]]

[21]

{21} Shannon, C.E.: A mathematical theory of communication. Bell System Technical Journal 27 (1948) pp. 379-423, 623-656.]]

[22]

{22} Shenoy, P.P.: Conditional Independence in Valuation-based Systems. International Journal of Approximate Reasoning 10 (1994) pp. 203-234.]]

[23]

{23} Skowron, A.: Extracting laws from decision tables. Computational Intelligence 11/2 (1995) pp. 371-388.]]

[24]

{24} Skowron, A., Rauszer, C.: The discernibility matrices and functions in information systems. In: R. Slowinski (ed.): Intelligent Decision Support. Handbook of Applications and Advances of the Rough Set Theory. Kluwer (1992) pp. 311-362.]]

[25]

{25} Slezak, D.: Approximate reducts in decision tables. In: Proc. of IPMU'96. Granada, Spain (1996) 3, pp. 1159-1164.]]

[26]

{26} Slezak, D.: Rough Set Reduct Networks. In: Proc. of RSSC'97. Durham, NC (1997) 3 pp. 77-80.]]

[27]

{27} Slezak, D.: Decomposition and Synthesis of Decision Tables with Respect to Generalized Decision Functions. In: S.K. Pal, A. Skowron (eds): Rough Fuzzy Hybridization A New Trend in Decision Making. Springer Verlag (1999) pp. 110-135.]]

[28]

{28} Slezak, D.: Various approaches to reasoning with frequency-based decision reducts: a survey. In: {18} (2000) pp. 235-285.]]

Digital Library

[29]

{29} Slezak, D.: Normalized decision functions and measures for inconsistent decision tables analysis. Fundamenta Informaticae 44/3 (2000) pp. 291-319.]]

[30]

{30} Slezak, D.: Approximate decision reducts (in Polish). Ph.D. thesis, Institute of Mathematics, Warsaw University (2001).]]

[31]

{31} Slezak D.: Approximate Bayesian Networks. In: B. Bouchon-Meunier, J. Gutierrez-Rios, L. Magdalena, R.R. Yager (eds), Technologies for Contructing Intelligent Systems 2: Tools. Springer Verlag (2002) pp. 313-326.]]

Digital Library

[32]

{32} Slezak, D., Wróblewski, J.: Application of Normalized Decision Measures to the New Case Classification. In: Proc. of RSCTC'2000. Banff, Canada (2000) pp. 515-522.]]

Digital Library

[33]

{33} Slezak, D., Wróblewski, J.: Order-based genetic algorithms for the search of approximate entropy reducts. In: Proc. of RSFDGrC'2003. Chongqing, China (2003).]]

Digital Library

[34]

{34} Wróblewski, J.: Theoretical Foundations of Order-Based Genetic Algorithms. Fundamenta Informaticae 28/3-4 (1996) pp. 423-430.]]

Digital Library

[35]

{35} Wróblewski, J.: Adaptive methods of object classification (in Polish). Ph.D. thesis, Institute of Mathematics, Warsaw University (2001).]]

[36]

{36} Ziarko, W.: Variable Precision Rough Set Model. Journal of Computer and System Sciences 40 (1993) pp. 39 59.]]

Digital Library

Cited By

Chen YYang XLi JWang PQian Y(2022)Fusing attribute reduction acceleratorsInformation Sciences: an International Journal10.1016/j.ins.2021.12.047587:C(354-370)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1016/j.ins.2021.12.047
Shu WQian WXie Y(2022)Incremental neighborhood entropy-based feature selection for mixed-type data under the variation of feature setApplied Intelligence10.1007/s10489-021-02526-952:5(4792-4806)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s10489-021-02526-9
He JQu LWang ZChen YLuo DWen C(2022)Attribute reduction in an incomplete categorical decision information system based on fuzzy rough setsArtificial Intelligence Review10.1007/s10462-021-10117-w55:7(5313-5348)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s10462-021-10117-w
Show More Cited By

Index Terms

Approximate entropy reducts
1. Security and privacy
  1. Cryptography
    1. Mathematical foundations of cryptography
2. Theory of computation
  1. Computational complexity and cryptography
    1. Communication complexity

Recommendations

Approximate Entropy Reducts

We use information entropy measure to extend the rough set based notion of a reduct. We introduce the Approximate Entropy Reduction Principle (AERP). It states that any simplification (reduction of attributes) in the decision model, which approximately ...
Some properties of Rényi entropy and Rényi entropy rate

In this paper, we define the conditional Renyi entropy and show that the so-called chain rule holds for the Renyi entropy. Then, we introduce a relation for the rate of Renyi entropy and use it to derive the rate of the Renyi entropy for an irreducible-...
Conditional Tsallis Entropy
Abstract
In this paper, the conditional Tsallis entropy is defined on the basis of the conditional Renyi entropy. Regarding the fact that Renyi entropy is the monotonically increasing function of Tsallis entropy, a relationship has also been ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Fundamenta Informaticae

Fundamenta Informaticae Volume 53, Issue 3,4

May 2002

196 pages

ISSN:0169-2968

Issue’s Table of Contents

Publisher

IOS Press

Netherlands

Publication History

Published: 30 May 2002

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

89
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen YYang XLi JWang PQian Y(2022)Fusing attribute reduction acceleratorsInformation Sciences: an International Journal10.1016/j.ins.2021.12.047587:C(354-370)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1016/j.ins.2021.12.047
Shu WQian WXie Y(2022)Incremental neighborhood entropy-based feature selection for mixed-type data under the variation of feature setApplied Intelligence10.1007/s10489-021-02526-952:5(4792-4806)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s10489-021-02526-9
He JQu LWang ZChen YLuo DWen C(2022)Attribute reduction in an incomplete categorical decision information system based on fuzzy rough setsArtificial Intelligence Review10.1007/s10462-021-10117-w55:7(5313-5348)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s10462-021-10117-w
Yang YChen DZhang XJi Z(2022)Covering rough set-based incremental feature selection for mixed decision systemSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-021-06687-026:6(2651-2669)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s00500-021-06687-0
Shi YQi HMu XHou M(2021)Adjustable Fuzzy Rough ReductionComputational Intelligence and Neuroscience10.1155/2021/55137222021Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1155/2021/5513722
Choromański MGrześ THońko P(2020)Breadth search strategies for finding minimal reducts: towards hardware implementationNeural Computing and Applications10.1007/s00521-020-04833-732:18(14801-14816)Online publication date: 1-Sep-2020
https://dl.acm.org/doi/10.1007/s00521-020-04833-7
Ma XYao Y(2018)Three-way decision perspectives on class-specific attribute reductsInformation Sciences: an International Journal10.1016/j.ins.2018.03.049450:C(227-245)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1016/j.ins.2018.03.049
Wang CHe QShao MXu YHu Q(2017)A unified information measure for general binary relationsKnowledge-Based Systems10.1016/j.knosys.2017.07.017135:C(18-28)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1016/j.knosys.2017.07.017
Zhang XMiao D(2017)Three-way attribute reductsInternational Journal of Approximate Reasoning10.1016/j.ijar.2017.06.00888:C(401-434)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1016/j.ijar.2017.06.008
Tan AWu WTao Y(2017)A set-cover-based approach for the test-cost-sensitive attribute reduction problemSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-016-2173-321:20(6159-6173)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1007/s00500-016-2173-3
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents