Greedy Algorithm for Attribute Reduction

• Autorzy: Zielosko B. , Piliszczuk M.
• Języki publikacji: EN

Abstrakty

EN

In the paper the accuracy of greedy algorithm for construction of partial tests (superreducts) and partial decision rules is considered. Results of experiments with greedy algorithm are described.

Słowa kluczowe

EN

partial tests; partial reducts; partial decision rules; greedy algorithm

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 85, nr 1-4
• Strony: 549--561
• Opis fizyczny: bibliogr. 22 poz., tab., wykr.

Twórcy

autor

Zielosko B.

autor

Piliszczuk M.

• Institute of Computer Science University of Silesia 39 Będzińska St. 41-200 Sosnowiec, Poland,

Bibliografia

• [1] Chegis, I.A., Yablonskii, S.V.: Logical methods of electric circuit control. Trudy MIAN SSSR 51 (1958) 270-360 (in Russian).
• [2] Feige, U.: A threshold of Inn for approximating set cover (Preliminary version). In: Proceedings of 28th Annual ACM Symposium on the Theory of Computing (1996) 314-318.
• [3] Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. System Sci. 9 (1974) 256-278.
• [4] Lovasz, L.: On the ratio of optimal integral and fractional covers. Discrete Math. 13 (1975) 383-390.
• [5] Moshkov, M.Ju.: Conditional tests. Problems of Cybernetics 40. Edited by S.V.Yablonskii, Nauka Publishers, Moscow (1983) 131-170 (in Russian).
• [6] Moshkov, M.Ju., Piliszczuk, M., Zielosko, B.: On partial covers, reducts and decision rules. LNCS Transactions on Rough Sets, Springer-Verlag (to appear).
• [7] Newman, D.J., Hettich, S., Blake, C.L., Merz, C.J.: UCI Repository of machine learning databases http://www.ics.uci.edu/~mleam/MLRepository.html. University of California, Irvine, Department of Information and Computer Sciences (1998).
• [8] Nguyen, H.S., Ślęzak, D.: Approximate reducts and association rules - correspondence and complexity results. In: Proceedings of the Seventh International Workshop on Rough Sets, Fuzzy Sets, Data Mining, and Granular-Soft Computing. Yamaguchi, Japan. Lecture Notes in Artificial Intelligence 1711, Springer-Verlag (1999)137-145.
• [9] Nigmatullin, R.G.: Method of steepest descent in problems on cover. In: Memoirs of Symposium Problems of Precision and Efficiency of Computing Algorithms 5. Kiev, USSR (1969) 116-126 (in Russian).
• [10] Pawlak, Z.: Rough sets. International J. Comp. Inform. Science 11 (1982) 341-356.
• [11] Pawlak, Z.: Rough Sets - Theoretical Aspects of Reasoning about Data. Kluwer Academic Publishers, Dordrecht, Boston, London, 1991.
• [12] Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP. In: Proceedings of 29th Annual ACM Symposium on the Theory of Computing (1997) 475-484.
• [13] Skowron, A.: Rough sets in KDD. In: Proceedings of the 16-th World Computer Congress (IFIP'2000). Beijing, China (2000) 1-14.
• [14] Skowron, A., Rauszer, C: The discernibility matrices and functions in information systems. In: Słowiński, ~R. (Ed.), Intelligent Decision Support. Handbook of Applications and Advances of the Rough Set Theory. Kluwer Academic Publishers, Dordrecht, Boston, London (1992) 331-362.
• [15] Slavik, P.: A tight analysis of the greedy algorithm for set cover (extended abstract). In: Proceedings of 28th Annual ACM Symposium on the Theory of Computing (1996) 435-441.
• [16] Slavik, P.: Approximation algorithms for set cover and related problems. Ph.D. thesis. University of New York at Buffalo (1998).
• [17] Ślęzak, D.: Approximate reducts in decision tables. In: Proceedings of the Congress Information Processing and Management of Uncertainty in Knowledge-based Systems 3. Granada, Spain (1996) 1159-1164.
• [18] Ślęzak, D.: Normalized decision functions and measures for inconsistent decision tables analysis. Fundamenta Informaticae 44 (2000) 291-319.
• [19] Ślęzak, D.: Approximate entropy reducts. Fundamenta Informaticae 53 (2002) 365-390.
• [20] Ślęzak, D., Wróblewski, J.: Order-based genetic algorithms for the search of approximate entropy reducts. In: Proceedings of the International Conference Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing. Chongqing, China. Lecture Notes in Artificial Intelligence 2639, Springer-Verlag (2003) 308-311.
• [21] Wróblewski, J.: Ensembles of classifiers based on approximate reducts. Fundamenta Informaticae 47 (2001) 351-360.
• [22] Zhuravlev, Ju.L: On a class of partial Boolean functions. Discrete Analysis 2. Edited by Ju.I. Zhuravlev. IM SO AN USSR Publishers, Novosibirsk (1964) 23-27 (in Russian).