Porównanie własności heurystyk do wyznaczania reduktów minimalnych

• Autorzy: Korzeń M.
• Języki publikacji: PL

Abstrakty

PL

W pracy pokazano, że najważniejsze informacje o macierzy rozróżnialności można odtworzyć nie konstruując tej macierzy, a jedynie bazując na częstościach atrybutów. Takie podejście daje znaczny zysk obliczeniowy, rozkład pojedyńczego atrybutu można znaleźć w czasie proporcjonalnym do n.

EN

The minimal reiduct problem is NP-hard, therefore it can be solved exactly only for relatively small datasets. The paper presents comparison of different heuristic approaches to attribute, selection for building rough set reducts, based on cither discernibility matrix or information theoretical measures like entropy and Cini index. It has been shown theoretically and experimentally that entropy and Gini index work better if the reduct is later used for prediction of previously unseen cases, and the criterion based on the discernibility matrix tends to work better for learning functional relationships where generalisation is not an issue.

Słowa kluczowe

PL

redukt minimalny; redukt warunkowy; entropia; delta-indeks; heurystyka

EN

minimal reduct; entropy; Gini index; information gain

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2008
• Tom: nr 1 (Tom 13)
• Strony: 83--91
• Opis fizyczny: Bibliogr. 12 poz., rys., tab.

Twórcy

autor

Korzeń M.

• Politechnika Szczecińska, Wydział Informatyki

Bibliografia

• [1] Bazan J. Metody wnioskowań aproksymacyjnych dla syntezy algorytów decyzyjnych. Praca doktorska, Uniwersytet Warszawski 1999
• [2] Buzan J., Szczuka M., Wróblewski J. A new version of rough set exploration system. Third International Conference on Rough Sets and Current Trends in Computing RSCTC. Lecture Notes in Artificial Intelligence, Vol. 2475, s. 397-404, Springer-Verlag 2002.
• [3] Breiman L., Olshen H. A.. Friedman J. H., Stone C. J. Classification and Regression Trees. CRC Press 1984
• [4] Hettich S., Bay S. D. The UCI KDD Archive http://kdd.ics.ud.edu. Irvine, CA: University of California. Department of Information and Computer Science, 1999.
• [5] Jaroszewicz S., Korzeń M. Comparison of Information Theoretical Measures for Reduct Finding. W: Rutkowski L., Tadeusiewicz R., Zadeh L. A., Zurada J. (red.) ICAISC. Lecture Notes in Computer Science, Vol. 4029. s. 518-527, Springer 2006.
• [6] Komorowski J., Polkowski L., Skowron A. Rough sets: a tutorial, W: Pal S. K.. Skowron A. (red.), Rough-Fuzzy Hybridization: A New Method for Decision Making. Springer-Verlag 1998.
• [7] Koronacki J., Ćwik J. Statystyczne systemy uczące WNT 2005
• [8] Korzeń M., Jaroszewicz S. Finding Reducts Without Building the Discernibility Matrix. ISDA, s. 450-455. IEEE Computer Society 2005
• [9] Nguyen S. II., Nguyen H. S. Some efficient algorithms for rough set methods. Proceedings of the Conference of Information Processing and Management of Uncertainty in Knowledge-Based Systems 1PMU'96, s. 1451-1456. Granada, Spain. 1996.
• [10] Pawlak Z. Rough sets: Theoretical aspects of reasoning about data. Dordrecht: Kluwer 1991
• [11] Quinlan R. C4-5: Programs for Machine Learning. Morgan Kaufmann 1993
• [12] Zhang J., Wang J., Li D., He H., Sun J. A New Heuristic Reduct Alghorithm Base on Rough Sets Theory. Lecture Notes in Computer Sciences, Vol. 2762, s. 247-253, Springer 2003.