Abstract
We continue our research on decision bireducts. For a decision system \(\mathbb{A}\) = (U,A ∪ {d}), a decision bireduct is a pair (B,X), where B ⊆ A is a subset of attributes discerning all pairs of objects in X ⊆ U with different values on the decision attribute d, and where B and X cannot be, respectively, reduced and extended. We report some new results related to NP-hardness of extraction of optimal decision bireducts, heuristics aimed at searching for sub-optimal decision bireducts, and applications of decision bireducts to stream data mining.
This research was partly supported by the Polish National Science Centre (NCN) grants 2011/01/B/ST6/03867 and 2012/05/B/ST6/03215.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Świniarski, R.W., Skowron, A.: Rough Set Methods in Feature Selection and Recognition. Pattern Recognition Letters 24(6), 833–849 (2003)
Ślęzak, D.: Approximate Entropy Reducts. Fundamenta Informaticae 53(3-4), 365–390 (2002)
Abeel, T., Helleputte, T., de Peer, Y.V., Dupont, P., Saeys, Y.: Robust Biomarker Identification for Cancer Diagnosis with Ensemble Feature Selection Methods. Bioinformatics 26(3), 392–398 (2010)
Ślęzak, D.: Approximation Reducts in Decision Tables. In: Proc. of IPMU 1996, vol. 3, pp. 1159–1164 (1996)
Ślęzak, D., Janusz, A.: Ensembles of Bireducts: Towards Robust Classification and Simple Representation. In: Kim, T.-H., Adeli, H., Ślęzak, D., Sandnes, F.E., Song, X., Chung, K.-I., Arnett, K.P. (eds.) FGIT 2011. LNCS, vol. 7105, pp. 64–77. Springer, Heidelberg (2011)
Stawicki, S., Widz, S.: Decision Bireducts and Approximate Decision Reducts: Comparison of Two Approaches to Attribute Subset Ensemble Construction. In: Proc. of FedCSIS 2012, pp. 331–338. IEEE Computer Society (2012)
Bazan, J.G., Nguyen, H.S., Nguyen, S.H., Synak, P., Wróblewski, J.: Rough Set Algorithms in Classification Problem. In: Polkowski, L., Tsumoto, S., Lin, T.Y. (eds.) Rough Set Methods and Applications: New Developments in Knowledge Discovery in Information Systems. STUD FUZZ, vol. 56, pp. 49–88. Physica-Verlag, Heidelberg (2000)
Widz, S., Ślęzak, D.: Approximation Degrees in Decision Reduct-based MRI Segmentation. In: Proc. of FBIT 2007, pp. 431–436. IEEE Computer Society (2007)
Pawlak, Z., Skowron, A.: Rudiments of Rough Sets. Information Sciences 177(1), 3–27 (2007)
Mac Parthaláin, N., Jensen, R.: Simultaneous Feature And Instance Selection Using Fuzzy-Rough Bireducts. In: Proc. of FUZZ IEEE 2013 (2013)
Moshkov, M.J., Piliszczuk, M., Zielosko, B.: Partial Covers, Reducts and Decision Rules in Rough Sets – Theory and Applications. SCI, vol. 145. Springer, Heidelberg (2008)
Nguyen, S.H., Nguyen, H.S.: Pattern Extraction from Data. Fundamenta Informaticae 34(1-2), 129–144 (1998)
Ślęzak, D.: Normalized Decision Functions and Measures for Inconsistent Decision Tables Analysis. Fundamenta Informaticae 44(3), 291–319 (2000)
Sarawagi, S., Thomas, S., Agrawal, R.: Integrating Association Rule Mining with Relational Database Systems: Alternatives and Implications. Data Min. Knowl. Discov. 4(2/3), 89–125 (2000)
Kowalski, M., Stawicki, S.: SQL-based Heuristics for Selected KDD Tasks over Large Data Sets. In: Proc. of FedCSIS 2012, pp. 303–310. IEEE Computer Society (2012)
Nguyen, H.S.: Approximate Boolean Reasoning: Foundations and Applications in Data Mining. In: Peters, J.F., Skowron, A. (eds.) Transactions on Rough Sets V. LNCS, vol. 4100, pp. 334–506. Springer, Heidelberg (2006)
Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations. Springer (1998)
Janusz, A., Ślęzak, D.: Utilization of Attribute Clustering Methods for Scalable Computation of Reducts from High-Dimensional Data. In: Proc. of FedCSIS 2012, pp. 295–302. IEEE Computer Society (2012)
Janusz, A., Stawicki, S.: Applications of Approximate Reducts to the Feature Selection Problem. In: Yao, J., Ramanna, S., Wang, G., Suraj, Z. (eds.) RSKT 2011. LNCS, vol. 6954, pp. 45–50. Springer, Heidelberg (2011)
Janusz, A., Ślęzak, D., Nguyen, H.S.: Unsupervised Similarity Learning from Textual Data. Fundam. Inform. 119(3-4), 319–336 (2012)
Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.K.: Learnability and the Vapnik-Chervonenkis Dimension. J. ACM 36(4), 929–965 (1989)
Aggarwal, C.C. (ed.): Data Streams – Models and Algorithms. Advances in Database Systems, vol. 31. Springer (2007)
Zhang, T., Ramakrishnan, R., Livny, M.: BIRCH: An Efficient Data Clustering Method for Very Large Databases. In: Proc. of SIGMOD 1996, pp. 103–114. ACM Press (1996)
Ślęzak, D., Kowalski, M., Eastwood, V., Wróblewski, J.: Methods and Systems for Database Organization. US Patent 8,266,147 B2 (2012)
Havens, T.C., Bezdek, J.C.: A New Formulation of the coVAT Algorithm for Visual Assessment of Clustering Tendency in Rectangular Data. Int. J. Intell. Syst. 27(6), 590–612 (2012)
Słowiński, R., Greco, S., Matarazzo, B.: Dominance-Based Rough Set Approach to Reasoning About Ordinal Data. In: Kryszkiewicz, M., Peters, J.F., Rybiński, H., Skowron, A. (eds.) RSEISP 2007. LNCS (LNAI), vol. 4585, pp. 5–11. Springer, Heidelberg (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Stawicki, S., Ślęzak, D. (2013). Recent Advances in Decision Bireducts: Complexity, Heuristics and Streams. In: Lingras, P., Wolski, M., Cornelis, C., Mitra, S., Wasilewski, P. (eds) Rough Sets and Knowledge Technology. RSKT 2013. Lecture Notes in Computer Science(), vol 8171. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41299-8_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-41299-8_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41298-1
Online ISBN: 978-3-642-41299-8
eBook Packages: Computer ScienceComputer Science (R0)