chapter

FUN: Fast Discovery of Minimal Sets of Attributes Functionally Determining a Decision Attribute

Authors:

Marzena Kryszkiewicz,

Piotr LasekAuthors Info & Claims

Transactions on Rough Sets IX

December 2008

Pages 76 - 95

https://doi.org/10.1007/978-3-540-89876-4_5

Published: 18 December 2008 Publication History

Abstract

In this paper, we present our <em>Fun</em> algorithm for discovering minimal sets of conditional attributes functionally determining a given dependent attribute. In particular, the algorithm is capable of discovering Rough Sets certain, generalized decision, and membership distribution reducts. <em>Fun</em> can operate either on partitions of objects or alternatively on stripped partitions, which do not store singleton groups. It is capable of using functional dependencies occurring among conditional attributes for pruning candidate dependencies. In this paper, we offer further reduction of stripped partitions, which allows correct determination of minimal functional dependencies provided optional candidate pruning is not carried out. In the paper we consider six variants of <em>Fun</em>, including two new variants using reduced stripped partitions. We have carried out a number of experiments on benchmark data sets to test the efficiency of all variants of <em>Fun</em> . We have also tested the efficiency of the <em>Fun</em> 's variants against the Rosetta and RSES toolkits' algorithms computing all reducts and against <em>Tane</em>, which is one of the most efficient algorithms computing all minimal functional dependencies. The experiments prove that <em>Fun</em> is up to 3 orders of magnitude faster than the the Rosetta and RSES toolkits' algorithms and faster than <em>Tane</em> up to 30 times.

References

[1]

Agrawal, R., Mannila, H., Srikant, R., Toivonen, H., Verkamo, A.I.: Fast Discovery of Association Rules. In: Advances in KDD, pp. 307-328. AAAI,Menlo Park (1996).

[2]

Armstrong, W.W.: Dependency Structures of Data Based Relationships. In: Proceedings of IFIP Congress, Geneva, Switzerland, pp. 580-583 (1974).

[3]

Bazan, J., Skowron, A., Synak, P.: Dynamic Reducts as a Tool for Extracting Laws from Decision Tables. In: Ras, Z.W., Zemankova, M. (eds.) ISMIS 1994. LNCS (LNAI), vol. 869, pp. 346-355. Springer, Heidelberg (1994).

Digital Library

[4]

Bazan, J., Nguyen, H.S., Nguyen, S.H., Synak, P., Wroblewski, J.: Rough Set Algorithms in Classification Problem. In: Rough Set Methods and Applications, pp. 49-88. Physica-Verlag, Heidelberg (2000).

Digital Library

[5]

Bazan, J.G., Szczuka, M.S.: RSES and RSESlib - A Collection of Tools for Rough Set Computations. In: Rough Sets and Current Trends in Computing, pp. 106-113 (2000).

[6]

Huhtala, Y., Karkkainen, J., Porkka, P., Toivonen, H.: TANE: An Efficient Algorithm for Discovering Functional and Approximate Dependencies. The Computer Journal 42(2), 100-111 (1999).

[7]

Jelonek, J., Krawiec, K., Stefanowski, J.: Comparative study of feature subset selection techniques for machine learning tasks. In: Proceedings of IIS, Malbork, Poland, pp. 68-77 (1998).

[8]

Kryszkiewicz, M.: Algorytmy Redukcji Wiedzy w Systemach Informacyjnych, Ph.D. Thesis, Warsaw University of Technology (1994).

[9]

Kryszkiewicz, M.: Comparative Study of Alternative Types of Knowledge Reduction in Inconsistent Systems. Intl. Journal of Intelligent Systems 16(1), 105-120 (2001).

[10]

Kryszkiewicz, M.: Certain, Generalized Decision, and Membership Distribution Reducts versus Functional Dependencies in Incomplete Systems. In: Kryszkiewicz, M., Peters, J.F., Rybinski, H., Skowron, A. (eds.) RSEISP 2007. LNCS (LNAI), vol. 4585, pp. 162-174. Springer, Heidelberg (2007).

[11]

Kryszkiewicz, M., Cichon, K.: Towards Scalable Algorithms for Discovering Rough Set Reducts. In: Peters, J.F., Skowron, A., Grzymała-Busse, J.W., Kostek, B.z., Swiniarski, R.W., Szczuka, M.S. (eds.) Transactions on Rough Sets I. LNCS, vol. 3100, pp. 120-143. Springer, Heidelberg (2004).

[12]

Kryszkiewicz, M., Lasek, P.: Fast Discovery of Minimal Sets of Attributes Functionally Determining a Decision Attribute. In: Kryszkiewicz, M., Peters, J.F., Rybinski, H., Skowron, A. (eds.) RSEISP 2007. LNCS, vol. 4585, pp. 320-331. Springer, Heidelberg (2007).

[13]

Lin, T.Y.: Rough Set Theory in Very Large Databases. In: Proceedings of CESA IMACS, Lille, France, vol. 2, pp. 936-941 (1996).

[14]

Lopes, S., Petit, J.-M., Lakhal, L.: Efficient Discovery of Functional Dependencies and Armstrong Relations. In: Zaniolo, C., Grust, T., Scholl, M.H., Lockemann, P.C. (eds.) EDBT 2000. LNCS, vol. 1777, pp. 350-364. Springer, Heidelberg (2000).

Digital Library

[15]

Nguyen, S.H., Skowron, A., Synak, P., Wroblewski, J.: Knowledge Discovery in Databases: Rough Set Approach. In: Proceedings of IFSA, Prague, vol. 2, pp. 204- 209 (1997).

[16]

Ohrn, A.: Discernibility and Rough Sets in Medicine: Tools and Applications, PhD thesis, Department of Computer and Information Science, Norwegian University of Science and Technology, Trondheim, Norway. NTNU report 1999:133, IDI report 1999:14.

[17]

Pancerz, K., Suraj, Z.: Rough sets for discovering concurrent system models from data tables. In: Rough Computing: Theories, Technologies and Applications, pp. 239-268. Idea Group, Inc. (2007).

[18]

Pawlak, Z.: Rough Sets: Theoretical Aspects of Reasoning about Data, vol. 9. Kluwer Academic Publishers, Dordrecht (1991).

[19]

Pawlak, Z.: Concurrent versus sequential the rough sets perspective. Bulletin of the EATCS 48, 178-190 (1992).

[20]

Shan, N., Ziarko, W., Hamilton, H.J., Cercone, N.: Discovering Classification Knowledge in Databases Using Rough Sets. In: Proceedings of KDD, pp. 271-274 (1996).

[21]

Skowron, A.: Boolean Reasoning for Decision Rules Generation. In: Komorowski, J., Ras, Z.W. (eds.) ISMIS 1993. LNCS, vol. 689, pp. 295-305. Springer, Heidelberg (1993).

[22]

Skowron, A., Suraj, Z.: Discovery of Concurrent Data Models from Experimental Tables: A Rough Set Approach. In: Proceedings of KDD, Montreal, Canada, pp. 288-293 (1995).

[23]

Slezak, D.: Approximate Reducts in Decision Tables. In: Proceedings of IPMU, Granada, Spain, vol. 3, pp. 1159-1164 (1996).

[24]

Slezak, D.: Searching for Frequential Reducts in Decision Tables with Uncertain Objects. In: Polkowski, L., Skowron, A. (eds.) RSCTC 1998. LNCS, vol. 1424, pp. 52-59. Springer, Heidelberg (1998).

[25]

Slezak, D.: Association Reducts: Complexity and Heuristics. In: Greco, S., Hata, Y., Hirano, S., Inuiguchi, M., Miyamoto, S., Nguyen, H.S., Słlowinski, R. (eds.) RSCTC 2006. LNCS, vol. 4259, pp. 157-164. Springer, Heidelberg (2006).

[26]

Slowinski, R. (ed.): Intelligent Decision Support, Handbook of Applications and Advances of the Rough Sets Theory, vol. 11. Kluwer Academic Publishers, Dordrecht (1992).

Digital Library

[27]

Stepaniuk, J.: Approximation Spaces, Reducts and Representatives. In: Rough Sets in Data Mining and Knowledge Discovery. Springer, Berlin (1998).

[28]

Suraj, Z.: Rough Set Methods for the Synthesis and Analysis of Concurrent Processes. In: Rough set methods and applications. New developments in knowledge discovery in information systems (Studies in fuzziness and soft computing), pp. 379-488. Physica-Verlag, Heidelberg (2000).

[29]

Wroblewski, J.: Finding Minimal Reducts Using Genetic Algorithms. In: Proceedings of JCIS, Wrightsville Beach, NC, September/October 1995, pp. 186-189 (1995).

Cited By

Liu YZheng LXiu YYin HZhao SWang XChen HLi C(2020)Discernibility matrix based incremental feature selection on fused decision tablesInternational Journal of Approximate Reasoning10.1016/j.ijar.2019.11.010118:C(1-26)Online publication date: 1-Mar-2020
https://dl.acm.org/doi/10.1016/j.ijar.2019.11.010
Jing YLi THuang JZhang Y(2016)An incremental attribute reduction approach based on knowledge granularity under the attribute generalizationInternational Journal of Approximate Reasoning10.1016/j.ijar.2016.05.00176:C(80-95)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1016/j.ijar.2016.05.001
Liang JMi JWei WWang F(2013)An accelerator for attribute reduction based on perspective of objects and attributesKnowledge-Based Systems10.1016/j.knosys.2013.01.02744(90-100)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1016/j.knosys.2013.01.027
Show More Cited By

Recommendations

Approximations and reducts with covering generalized rough sets

The covering generalized rough sets are an improvement of traditional rough set model to deal with more complex practical problems which the traditional one cannot handle. It is well known that any generalization of traditional rough set theory should ...
Attribute reducts of multi-granulation information system
Abstract
In recent years, more and more methods and theories of multi-granulation information systems have been explored. However, there is very limited investigation on the attribute reducts of multi-granulation rough sets. Therefore, the main objective ...
A Method for Extracting Knowledge from Decision Tables in Terms of Functional Dependencies
Abstract
The problem of extracting knowledge from decision tables in terms of functional dependencies is one of the important problems in knowledge discovery and data mining. Based on some results in relational database, in this paper we propose ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide books

Transactions on Rough Sets IX

December 2008

750 pages

ISBN:9783540898757

Editors:
James F. Peters
Department of Electrical and Computer Engineering, University of Manitoba, Winnipeg, Canada R3T 5V6
,
Andrzej Skowron
Institute of Mathematics, Warsaw University, Warsaw, Poland 02-097
,
Henryk Rybiński
Institute of Computer Science, Warsaw University of Technology, Warsaw, Poland 00-665

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 18 December 2008

Author Tags

Qualifiers

Chapter

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu YZheng LXiu YYin HZhao SWang XChen HLi C(2020)Discernibility matrix based incremental feature selection on fused decision tablesInternational Journal of Approximate Reasoning10.1016/j.ijar.2019.11.010118:C(1-26)Online publication date: 1-Mar-2020
https://dl.acm.org/doi/10.1016/j.ijar.2019.11.010
Jing YLi THuang JZhang Y(2016)An incremental attribute reduction approach based on knowledge granularity under the attribute generalizationInternational Journal of Approximate Reasoning10.1016/j.ijar.2016.05.00176:C(80-95)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1016/j.ijar.2016.05.001
Liang JMi JWei WWang F(2013)An accelerator for attribute reduction based on perspective of objects and attributesKnowledge-Based Systems10.1016/j.knosys.2013.01.02744(90-100)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1016/j.knosys.2013.01.027
Wang FLiang JDang C(2013)Attribute reduction for dynamic data setsApplied Soft Computing10.1016/j.asoc.2012.07.01813:1(676-689)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1016/j.asoc.2012.07.018
Liang J(2011)Uncertainty and feature selection in rough set theoryProceedings of the 6th international conference on Rough sets and knowledge technology10.5555/2050461.2050464(8-15)Online publication date: 9-Oct-2011
https://dl.acm.org/doi/10.5555/2050461.2050464
Terlecki P(2010)On the relation between jumping emerging patterns and rough set theory with application to data classificationTransactions on rough sets XII10.5555/1880429.1880442(236-338)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1880429.1880442

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 Chapter

Media

Figures

Other

Tables

View Table of Contents