Abstract
In this chapter we propose a new method of solving the attribute reduction problem. Our method is different to the classical approach using the so-called discernibility function and its CNF into DNF transformation. We have proved that the problem is equivalent to very efficient unate complementation algorithm. That is why we propose new algorithm based on recursive execution of the procedure, which at every step of recursion selects the splitting variable and then calculates the cofactors with respect to the selected variables (Shannon expansion procedure). The recursion continues until at each leaf of the recursion tree the easily computable rules for complement process can be applied. The recursion process creates a binary tree so that the final result is obtained merging the results in the subtrees. The final matrix represents all the minimal reducts of a decision table or all the minimal dependence sets of input variables, respectively. According to the results of computer tests, better results can be achieved by application of our method in combination with the classical method.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abdullah, S., Golafshan, L., Nazri, M.Z.A.: Re-heat simulated annealing algorithm for rough set attribute reduction. International Journal of the Physical Sciences 6(8), 2083–2089 (2011), doi:10.5897/IJPS11.218
Bazan, J., Nguyen, H.S., Nguyen, S.H., Synak, P., Wróblewski, J.: Rough set algorithms in classification problem. In: Rough Set Methods and Applications: New Developments in Knowledge Discovery in Information Systems, vol. 56, pp. 49–88. Physica-Verlag, Heidelberg (2000), doi:10.1007/978-3-7908-1840-6_3
Borowik, G., Łuba, T.: Attribute reduction based on the complementation of boolean functions. In: 1st Australian Conference on the Applications of Systems Engineering, ACASE 2012, Sydney, Australia, pp. 58–59 (2012) (electronic document)
Borowik, G., Łuba, T., Zydek, D.: Features reduction using logic minimization techniques. International Journal of Electronics and Telecommunications 58(1), 71–76 (2012), doi:10.2478/v10177-012-0010-x
Brayton, R.K., Hachtel, G.D., McMullen, C.T., Sangiovanni-Vincentelli, A.: Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers (1984)
Brzozowski, J.A., Łuba, T.: Decomposition of boolean functions specified by cubes. Journal of Multi-Valued Logic & Soft Computing 9, 377–417 (2003)
Dash, R., Dash, R., Mishra, D.: A hybridized rough-PCA approach of attribute reduction for high dimensional data set. European Journal of Scientific Research 44(1), 29–38 (2010)
Feixiang, Z., Yingjun, Z., Li, Z.: An efficient attribute reduction in decision information systems. In: International Conference on Computer Science and Software Engineering, Wuhan, Hubei, pp. 466–469 (2008), doi:10.1109/CSSE.2008.1090
Grzenda, M.: Prediction-oriented dimensionality reduction of industrial data sets. In: Mehrotra, K.G., Mohan, C.K., Oh, J.C., Varshney, P.K., Ali, M. (eds.) IEA/AIE 2011, Part I. LNCS, vol. 6703, pp. 232–241. Springer, Heidelberg (2011)
Hedar, A.R., Wang, J., Fukushima, M.: Tabu search for attribute reduction in rough set theory. Journal of Soft Computing – A Fusion of Foundations, Methodologies and Applications 12(9), 909–918 (2008), doi:10.1007/s00500-007-0260-1
Jensen, R., Shen, Q.: Semantics-preserving dimensionality reduction: Rough and fuzzy-rough based approaches. IEEE Transactions on Knowledge and Data Engineering 16, 1457–1471 (2004), doi:10.1109/TKDE.2004.96
Jing, S., She, K.: Heterogeneous attribute reduction in noisy system based on a generalized neighborhood rough sets model. World Academy of Science, Engineering and Technology 75, 1067–1072 (2011)
Kalyani, P., Karnan, M.: A new implementation of attribute reduction using quick relative reduct algorithm. International Journal of Internet Computing 1(1), 99–102 (2011)
Kryszkiewicz, M., Cichoń, 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)
Kryszkiewicz, M., Lasek, P.: FUN: Fast discovery of minimal sets of attributes functionally determining a decision attribute. In: Peters, J.F., Skowron, A., Rybiński, H. (eds.) Transactions on Rough Sets IX. LNCS, vol. 5390, pp. 76–95. Springer, Heidelberg (2008)
Lewandowski, J., Rawski, M., Rybiński, H.: Application of parallel decomposition for creation of reduced feed-forward neural networks. In: Kryszkiewicz, M., Peters, J.F., Rybiński, H., Skowron, A. (eds.) RSEISP 2007. LNCS (LNAI), vol. 4585, pp. 564–573. Springer, Heidelberg (2007)
Lin, T.Y., Yao, Y.Y., Zadeh, L.A. (eds.): Data mining, rough sets and granular computing. Physica-Verlag GmbH, Heidelberg (2002)
Łuba, T., Lasocki, R.: On unknown attribute values in functional dependencies. In: Proceedings of The Third International Workshop on Rough Sets and Soft Computing, San Jose, pp. 490–497 (1994)
Łuba, T., Lasocki, R., Rybnik, J.: An implementation of decomposition algorithm and its application in information systems analysis and logic synthesis. In: Ziarko, W. (ed.) Rough Sets, Fuzzy Sets and Knowledge Discovery. Workshops in Computing Series, pp. 458–465. Springer (1994)
Łuba, T., Rybnik, J.: Rough sets and some aspects in logic synthesis. In: Słowiński, R. (ed.) Intelligent Decision Support – Handbook of Application and Advances of the Rough Sets Theory. Kluwer Academic Publishers (1992)
Nguyen, D., Nguyen, X.: A new method to attribute reduction of decision systems with covering rough sets. Georgian Electronic Scientific Journal: Computer Science and Telecommunications 1(24), 24–31 (2010)
Pawlak, Z.: Rough Sets. Theoretical Aspects of Reasoning about Data. Kluwer Academic Publishers (1991)
Pei, X., Wang, Y.: An approximate approach to attribute reduction. International Journal of Information Technology 12(4), 128–135 (2006)
Rawski, M., Borowik, G., Łuba, T., Tomaszewicz, P., Falkowski, B.J.: Logic synthesis strategy for FPGAs with embedded memory blocks. Electrical Review 86(11a), 94–101 (2010)
Selvaraj, H., Sapiecha, P., Rawski, M., Łuba, T.: Functional decomposition – the value and implication for both neural networks and digital designing. International Journal of Computational Intelligence and Applications 6(1), 123–138 (2006), doi:10.1142/S1469026806001782
Skowron, A., Rauszer, C.: The discernibility matrices and functions in information systems. In: Słowiński, R. (ed.) Intelligent Decision Support – Handbook of Application and Advances of the Rough Sets Theory. Kluwer Academic Publishers (1992)
Słowiński, R., Sharif, E.: Rough sets analysis of experience in surgical practice. In: Rough Sets: State of The Art and Perspectives, Poznań-Kiekrz (1992)
Wang, C., Ou, F.: An attribute reduction algorithm based on conditional entropy and frequency of attributes. In: Proceedings of the 2008 International Conference on Intelligent Computation Technology and Automation, ICICTA 2008, vol. 1, pp. 752–756. IEEE Computer Society, Washington, DC (2008), doi:10.1109/ICICTA.2008.95
Yao, Y., Zhao, Y.: Attribute reduction in decision-theoretic rough set models. Information Sciences 178(17), 3356–3373 (2008), doi:10.1016/j.ins.2008.05.010
ROSE2 – Rough Sets Data Explorer, http://idss.cs.put.poznan.pl/site/rose.html
ROSETTA – A Rough Set Toolkit for Analysis of Data, http://www.lcb.uu.se/tools/rosetta/
RSES – Rough Set Exploration System, http://logic.mimuw.edu.pl/~rses/
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Borowik, G., Łuba, T. (2014). Fast Algorithm of Attribute Reduction Based on the Complementation of Boolean Function. In: Klempous, R., Nikodem, J., Jacak, W., Chaczko, Z. (eds) Advanced Methods and Applications in Computational Intelligence. Topics in Intelligent Engineering and Informatics, vol 6. Springer, Heidelberg. https://doi.org/10.1007/978-3-319-01436-4_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-01436-4_2
Publisher Name: Springer, Heidelberg
Print ISBN: 978-3-319-01435-7
Online ISBN: 978-3-319-01436-4
eBook Packages: EngineeringEngineering (R0)