Effectiveness of Decomposition Algorithms for Multi-class Classification Problems

• Autorzy: Waldemar Wołyński

Warianty tytułu

Efektywność algorytmów dekompozycyjnych wieloklasowych zagadnień klasyfikacyjnych

• Języki publikacji: EN

Abstrakty

EN

The problem of predicting of the class (group, population) label is called classification, discrimination, or supervised learning. The set of labels consists of K>2 elements in the case of the multi-class problems and of K=2 elements in the two-class (binary) problems. Since the two-class problems are much easier to solve, than the multi-class problems (furthermore, some classification algorithms may apply in the two-class case only) many authors propose to reduce a multi-class classification problem to a set of binary classification problems. Orthogonal to the decomposition problem is the problem of subject classifying which is described by the labels assigned by each binary classifiers. In this paper different decomposition algorithms and both well-known and new methods of combining the information from binary classifiers will be compared. Results of these comparisons are pointing explicitly, that apart from simplifying procedures we are also getting the significant improvement in the quality of classification, especially for the "unstable" classification procedures such as classification trees or neural networks. Hence these methods may be recognized as the techniques of boosting classifiers. (original abstract)

Problem predykcji etykiety klasy (grupy, populacji) na podstawie obserwacji wektora cech jest nazywany klasyfikacją, analizą dyskryminacyjną lub uczeniem się pod nadzorem. Zbiór etykiet składa się z K>2 elementów w przypadku zagadnie wieloklasowych oraz z K=2 elementów w przypadku zagadnie dwuklasowych (binarnych). Ponieważ zagadnienia dwuklasowe są z reguły o wiele prostsze od zagadnie wieloklasowych (co więcej, niektóre algorytmy klasyfikacyjne dają się zastosować jedynie w przypadku dwuklasowym) wielu autorów proponuje dekompozycje zagadnie wieloklasowych do zagadnie binarnych. Do szczególnie znanych algorytmów tego typu należą: one-per-class (OPC). pairwise coupling (PWC) oraz error-correcting output codes (ECOC). Dualnym do zagadnienia dekompozycji jest zagadnienie łączenia informacji uzyskanych z klasyfikatorów binarnych. Klasyczne algorytmy bazują na minimalizacji odległości Hamminga, technice głosowania lub sumowania prawdopodobieństw a posteriori. W pracy porównano różne algorytmy dekompozycyjne oraz zarówno klasyczne jak i nowe metody łączenia informacji z klasyfikatorów binarnych. Wyniki tych porównań wskazują jednoznacznie, że zwłaszcza w przypadku niestabilnych" procedur klasyfikacyjnych takich jak drzewa klasyfikacyjne czy sieci neuronowe, poza uproszczeniem samych procedur uzyskujemy równie znaczną poprawę jakości klasyfikacji. Stąd metody te zaliczyć można do technik wzmacniania klasyfikatorów. (abstrakt oryginalny)

Słowa kluczowe

EN

Algorithmic effectiveness; Discriminant analysis; Classification; Statistical methods

PL

Efektywność algorytmów; Analiza dyskryminacyjna; Klasyfikacja; Metody statystyczne

• Czasopismo: Acta Universitatis Lodziensis. Folia Oeconomica
• Rocznik: 2010
• Tom: 235 Multivariate Statistical Analysis
• Strony: 205--213

Twórcy

autor

Waldemar Wołyński

• Adam Mickiewicz Uniwersity in Poznań, Poland, doktorant

Bibliografia

• Dietterich T.G., Bakiri G. (1995), Solving multi-class learning problems via error-correcting output codes, Journal of Artificial Intelligence Research, 2, 263-286.
• Dillon W.R., Goldstein, M. (1984), Multivariate Analysis Methods and Applications, Wiley.
• Friedman J.H. (1996), Another approach to polychotomous classification. Technical report, Stanford Univ.
• Hastie T., Tibshirani R. (1998), Classification by pairwise coupling, The Annals of Statistics, 26, 451-471.
• van der Heijden F., Duin R.P.W., de Ridder D., Tax D.M.J. (2004), Classification, Parameter Estimation and State Estimation: A Engineering Approach Using Matlab, Wiley.
• Jassem W. (1997), Polish phonetical balanced and frequency-weighted word list, Speech and Language Technology, l, 71-99.
• Jelonek J., Stefanowski J. (1998), Experiments on solving multiclass learning problems by n2-classifier, In Proceedings of the 10th European Conference on Machine Learning (ECML-98), Chemnitz, Germany, 172-177.
• Johnson R.A., and Wichern D.W. (1982), Applied Multivariate Statistical Analysis, Prentice-Hall, Inc.
• Krzyśko M., Wołyński W. (2008), New variants of pairwise classification, European Journal of Operational Research, doi: 10.1016/j.ejor.2008.11.009.
• Merz C. J., Murphy P.M. (1998), UCI repository of machine learning databases. Machine-readable data repository, http://wvw.ics.uci.edu/~mlearn/mlrepository.html, Irvine, CA: University of California, Department of Information and Computer Science.
• Mojirsheibani M. (2002), A comparison study of some combined classifiers, Commun. Statist. - Simula., 31, 245-260.
• Moreira M., Mayoraz E. (1998), Improved pairwise coupling classification with correcting classifiers, In Proceedings of the l0th European Conference on Machine Learning (ECML-98), Chemnitz, Germany, 160-171.
• Price D., Knerr S., Personnaz L., Dreyfus G. (1995), Pairwise neural network classifiers with probabilistic outputs, In Advances in Neural Information Processing Systems 7 (NIPS-94), The MIT Press, 1109-1116.

Identyfikatory

DOI

11089/354