Abstract
The paper addresses the problem of computing reducts in decision tables where attributes are assigned costs. Computing reducts has been an interesting issue as the reducts may be successfully applied in further analyses of the decision table. In systems where attribute are assigned costs, the problem of reduct generation may be reformulated to that of finding reducts satisfying some additional constraints, in particular reducts of minimal attribute costs. The constraints allow to incorporate external preference into the system and, additionally, simplify the problem of interpreting the obtained results, since the number of reducts of minimal costs, as opposed to the number of all existing reducts, is usually very small. This paper introduces a new algorithm for generating all reducts of minimal costs, called minimal cost reducts or cheapest reducts. The practical behaviour of this algorithm has been tested in numerous experiments with real-life data sets, the results of which are reported here.
Preview
Unable to display preview. Download preview PDF.
References
Bazan J., Skowron A. & Synak P.: ‘Dynamic Reducts as a Tool for Extracting Laws from Decision Tables’, In: Methodologies for Intelligent Systems. Proceedings of the 8th International Symposium ISMIS’94, Charlotte, NG, LNAI Vol. 869, Springer-Verlag (1994), 346–355.
Boros E., Hammer P. L., Ibaraki T. & Kogan A.: ‘Logical Analysis of Numerical Data’, Mathematical Programming, Vol. 79 (1997), 163–190.
Kryszkiewicz M. & Rybiński H.: ‘Finding Reducts in Composed Information Systems’, Fundamenta Informaticae Vol. 2, No 2/3, (1996), 183–196.
Nguyen, H. S. & Skowron A.: ‘Quantization of Real Value Attributes. Rough Set and Boolean Reasoning Approaches’, In: Proceedings of the Second Annual Join Conference on Information Sciences, September/October 1995, Wrightsville Beach, NC (1995), 34–37.
Orlowska M. & Orłowski M.: ‘Maintenance of Knowledge in Dynamic Information Systems’, In: Słowinski R., (ed.), Intelligent Decision Support. Handbook of Applications and Advances of the Rough Set Theory, Kluwer Academic Publishers, Dordrecht, (1992), 315–330.
Padberg, M. W.: ‘Covering, packing and knapsack problems’, Annuals of Discrete Mathematics, Vol. 4, (1979), 265–278.
Pawlak Z.: Rough Sets. Theoretical Aspects of Reasoning About Data, Kluwer Academic Publishers, Dordrecht, (1991).
Romański S.: ‘Operations on Families of Sets for Exhausive Search Given a Monotonic Function’, In: Beeri, C., Smith, J.W., Dayal, U., (eds), Proceedings of the 3rd International Conference on Data and Knowledge Bases, Jerusalem, Israel, (1988), 28–30.
Skowron A. & Rauszer C.: ‘The Discernibility Matrices and Functions in Information Systems’, In: Słowinski R., (ed.), Intelligent Decision Support. Handbook of Applications and Advances of the Rough Set Theory, Kluwer Academic Publishers, Dordrecht, (1992), 331–362.
Skowron A. & Polkowski L. ‘Decision Algorithms: A Survey of Rough Set-Theoretic Methods’, Fundamenta Informaticae, Vol. 30, No. 3/4, (1997), 345–358.
Ślężak D.: ‘Searching for Frequential Reducts in Decision Tables with Uncertain Objects’, In: Polkowski L., Skowron A., (eds), Proceedings of the First International Conference RSCTC’98, Warsaw, June 1998, Springer-Verlag, Berlin (1998), 52–59.
Słowinski R. & Stefanowski J.: ‘Rough-Set Reasoning about Uncertain Data’, Fundamenta Informaticae, Vol. 27, No. 2/3, (1996), 229–244.
Susmaga R.: ‘Computation of Shortest Reducts’, Foundations of Computing and Decision Sciences Poznań, Poland, Vol. 23, No. 2, (1998), 119–137.
Susmaga, R.: ‘Effective Tests for Inclusion Minimality in Reduct Generation’, Foundations of Computing and Decision Sciences, Poznań, Poland, (to appear).
Tannhäuser M.: Efficient Reduct Computation (in Polish), M. Sc. Thesis, Institute of Mathematics, Warsaw University, Warsaw, Poland, (1994).
Wróblewski J.: ‘Covering with Reducts—A Fast Algorithm for Rule Generation’, In: Polkowski L., Skowron A., (eds), Proceedings of the First International Conference on Rough Sets and Current Trends in Computing, Warsaw 1998, Springer-Verlag, Berlin (1998), 402–407.
Ziarko W.: ‘Variable Precision Rough Set Model’, Journal of Computer and System Sciences, Vol. 46, No. 1, (1993), 39–59.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Susmaga, R. (1999). Computation of minimal cost reducts. In: Raś, Z.W., Skowron, A. (eds) Foundations of Intelligent Systems. ISMIS 1999. Lecture Notes in Computer Science, vol 1609. Springer, Berlin, Heidelberg . https://doi.org/10.1007/BFb0095132
Download citation
DOI: https://doi.org/10.1007/BFb0095132
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65965-5
Online ISBN: 978-3-540-48828-6
eBook Packages: Springer Book Archive