skip to main content
10.1145/2448556.2448646acmconferencesArticle/Chapter ViewAbstractPublication PagesicuimcConference Proceedingsconference-collections
research-article

Reducing overfitting of AdaBoost by clustering-based pruning of hard examples

Published:17 January 2013Publication History

ABSTRACT

In order to solve the problem of overfitting in AdaBoost, we propose a novel AdaBoost algorithm using K-means clustering. AdaBoost is known as an effective method for improving the performance of base classifiers both theoretically and empirically. However, previous studies have shown that AdaBoost is prone to overfitting in overlapped classes. In order to overcome the overfitting problem of AdaBoost, the proposed method uses K-means clustering to remove hard-to-learn samples that exist on overlapped region. Since the proposed method does not consider hard-to-learn samples, it suffers less from the overfitting problem compared to conventional AdaBoost. Both synthetic and real world data were tested to confirm the validity of the proposed method.

References

  1. Freund, Y. and Schapire, R. E. 1997. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55, 1 (Mar. 1997), 119--139. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. Schapire, R. E. 1999. Improved boosting algorithms using confidence-rated predictions. Journal of Machine Learning, 37, 3 (Dec. 1999), 297--336. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. Drucker, H. Cortes, C. Jackel, L. D. LeCun, Y. and Vapnik, V. 1994. Boosting and other ensemble methods. Journal of Neural Computation, 6, 6 (Nov. 1994), 1289--1301. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. Jiang, W. 2000. Does boosting overfit: views from an exact solution. Technical Report. Department of Statistics, Northwestern University.Google ScholarGoogle Scholar
  5. Ratsch, G. Onoda, T. and Muller, K. R. 2001, Soft margins for AdaBoost. Journal of Machine Learning, 42, 3 (Mar. 2001), 287--320. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. Dietterich, T. G. 2000. An experimental comparison of three methods for constructing ensembles of decision trees: bagging, boosting, and randomization. Journal of Machine Learning, 40, 2 (Aug. 2000), 139--157. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. Martinez, G. Sanchez-Martinez, A. Hernandez-Lobato, D. and Suarez, A. 2008. Class-switching neural network ensembles. Journal of Neurocomputing. 71, (Aug. 2008), 2521--2528. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. Gao, Y. and Gao, F. 2010. Edited adaBoost by weighted kNN. Neurocomputing, 73, 16--18 (October, 2010), 3079--3088. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. Cao, J. Kwong, S. and Wang, R. 2012. A noise-detection based AdaBoost algorithm for mislabeled data. Pattern Recognition, 45, 12 (December, 2012), 4451--4465. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. Vezhnevets, A. and Barinova, O. 2007. Avoiding boosting overfitting by removing confusing samples. In Proceedings of the 18th European Conference on Machine Learning (The Warsaw, The Poland, September 17--21, 2007). 430--441. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. MacQueen, J. B. 1967. Some methods for classification and analysis of multivariate observations. In Proceedings of the fifth Berkeley Symposium on Mathematical Statistics and Probability (The California, The USA, June 21-July 18, 1965 and December 27, 1965-January 7, 1966). 281--297.Google ScholarGoogle Scholar
  12. Mahalanobis, P. C. 1936. On the generalized distance in statistics. In Proceedings of the National Institute of Sciences (The India, April 16, 1936). 49--55.Google ScholarGoogle Scholar
  13. Blake, C. L. and Merz, C. J. 1998. UCI repository of machine learning databases.Google ScholarGoogle Scholar

Index Terms

  1. Reducing overfitting of AdaBoost by clustering-based pruning of hard examples

        Recommendations

        Comments

        Login options

        Check if you have access through your login credentials or your institution to get full access on this article.

        Sign in
        • Published in

          cover image ACM Conferences
          ICUIMC '13: Proceedings of the 7th International Conference on Ubiquitous Information Management and Communication
          January 2013
          772 pages
          ISBN:9781450319584
          DOI:10.1145/2448556

          Copyright © 2013 ACM

          Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

          Publisher

          Association for Computing Machinery

          New York, NY, United States

          Publication History

          • Published: 17 January 2013

          Permissions

          Request permissions about this article.

          Request Permissions

          Check for updates

          Qualifiers

          • research-article

          Acceptance Rates

          Overall Acceptance Rate251of941submissions,27%

        PDF Format

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader