Impact of Instance Selection on kNN-Based Text Categorization
2
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
With the increasing use of the Internet and electronic documents, automatic text categorization becomesimperative. Several machine learning algorithms have been proposed for text categorization. The k-nearestneighbor algorithm (kNN) is known to be one of the best state of the art classifiers when used for textcategorization. However, kNN suffers from limitations such as high computation when classifying newinstances. Instance selection techniques have emerged as highly competitive methods to improve kNNthrough data reduction. However previous works have evaluated those approaches only on structured datasets. In addition, their performance has not been examined over the text categorization domain where thedimensionality and size of the dataset is very high. Motivated by these observations, this paper investigatesand analyzes the impact of instance selection on kNN-based text categorization in terms of various aspectssuch as classification accuracy, classification efficiency, and data reduction.
Abstract
With the increasing use of the Internet and electronic documents, automatic text categorization becomesimperative. Several machine learning algorithms have been proposed for text categorization. The k-nearestneighbor algorithm (kNN) is known to be one of the best state of the art classifiers when used for textcategorization. However, kNN suffers from limitations such as high computation when classifying newinstances. Instance selection techniques have emerged as highly competitive methods to improve kNNthrough data reduction. However previous works have evaluated those approaches only on structured datasets. In addition, their performance has not been examined over the text categorization domain where thedimensionality and size of the dataset is very high. Motivated by these observations, this paper investigatesand analyzes the impact of instance selection on kNN-based text categorization in terms of various aspectssuch as classification accuracy, classification efficiency, and data reduction.
참고문헌 (39)
- F. Sebastiani, "Machine learning in automated text categorization", ACM Computing Surveys, 34(1), pp.1~47 (2002)[DOI]
- T. Songbo, "An effective refinement strategy for KNN text classifier", Expert Systems with Applications, 30(2), pp.290~298 (2006)[DOI]
- S. Garcia, "Prototype selection for nearest neighbor classification: Taxonomy and empirical study", IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(3), pp.317~435 (2012)
- J. Bien, "Prototype selection for interpretable classification", Annals of Applied Statistics Journal, 5(4), pp.2403~2424 (2011)[DOI]
- J. A. Olvera-Lopez, "A review of instance selection methods", Artificial Intelligence Review, 34(2), pp.133~143 (2010)[DOI]
- T. Liu, "New algorithms for efficient high dimensional nonparametric classification", Journal of Machine Learning Research, 7, pp.1135~1158 (2006)
- C. F. Tsai, "Evolutionary instance selection for text classification", Journal of Systems and Software, 90, pp.104~113 (2014)[DOI]
- F. Barigou, "A new term weighting scheme for text categorization", International Journal of Intelligent Systems Technologies and Applications, 14(3, pp.4) (2015), 256~272
- H. Zhou, "A feature selection approach based on term distributions", SpringerPlus, 5 (2016)
- M. Grochowski, "Comparison of instance selection algorithms II. Results and comments", Proceedings of the 7th International Conference on Artificial Intelligence and Soft Computing, pp.580~585 (2004)
- N. Jankowski, "Comparison of Instance Selection Algorithms I. Algorithms survey", Proceedings of the 7th International Conference on Artificial Intelligence and Soft Computing, pp.598~603 (2004)
- H. Brighton, "Advances in instance selection for instance-based learning algorithms", Data Mining and Knowledge Discovery, 6(2), pp.153~172 (2002)[DOI]
- I. Triguero, "A taxonomy and experimental study on prototype generation for nearest neighbor classification", IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 42(1), pp.86~100 (2012)[DOI]
- T. Cover amd P. Hart, "Nearest neighbor pattern classification", IEEE Transactions on Information Theory, 13(1), pp.21~27 (1967)[DOI]
- G. L. Libralon, "Pre-processing for noise detection in gene expression classification data", Journal of the Brazilian Computer Society, 15(1), pp.3~11 (2009)[DOI]
- A. Arnaiz-Gonzalez, "Instance selection for regression: adapting DROP", Neurocomputing, 201, pp.66~81 (2016)[DOI]
- M. B. Stojanovic, "A methodology for training set instance selection using mutual information in time series prediction", Neurocomputing, 141, pp.236~245 (2014)[DOI]
- P. Hart, "The condensed nearest neighbor rule", IEEE Transactions on Information Theory, 14(3), pp.515~516 (1968)[DOI]
- G. Gates, "The reduced nearest neighbor rule", IEEE Transactions on Information Theory, 18(3), pp.431~433 (1972)[DOI]
- G. Ritter, "An algorithm for a selective nearest neighbor decision rule", IEEE Transactions on Information Theory, 21(6), pp.665~669 (1975)[DOI]
- I. Tomek, "Two modifications of CNN", IEEE Transactions on Systems, Man, and Cybernetics, 6(6), pp.769~772 (1976)
- V. Devi, "An incremental prototype set building technique", Pattern Recognition, 35(2), pp.505~513 (2002)[DOI]
- J. Riquelme, "Finding representative patterns with ordered projections", Pattern Recognition, 36(4), pp.1009~1018 (2003)[DOI]
- F. Angiulli, "Fast condensed nearest neighbor rule", Proceedings of the 22d International Conference on Machine Learning, pp.25~325 (2005)
- D. L. Wilson, "Asymptotic properties of nearest neighbor rules using edited data", IEEE Transactions on Systems, Man, and Cybernetics, 2(3), pp.408~421 (1972)
- K. Hattori, "A new edited k-nearest neighbor rule in the pattern classification problem", Pattern Recognition, 33(3), pp.521~528 (2000)[DOI]
- J. S. Sanchez, "Prototype selection for the nearest neighbor rule through proximity graphs", Pattern Recognition Letters, 18(6), pp.507~513 (1997)[DOI]
- D. Aha, "Instance-based learning algorithms", Machine Learning, 6(1), pp.37~66 (1991)
- D. Randall Wilson, "Reduction techniques for instance-based learning algorithms", Machine Learning, 38(3), pp.257~286 (2000)[DOI]
- H. Brighton, "Advances in instance selection for instance-based learning algorithms", Data Mining and Knowledge Discovery, 6(2), pp.153~172 (2002)[DOI]
- J. Derrac, "A survey on evolutionary instance selection and generation", International Journal of Applied Metaheuristic Computing, 1(1), pp.60~92 (2010)[DOI]
- E. Leyva, "Knowledge-based instance selection: a compromise between efficiency and versatility", Knowledge-Based Systems, 47, pp.65~76 (2013)[DOI]
- J. R. Cano, "Using evolutionary algorithms as instance selection for data reduction in KDD: an experimental study", IEEE Transactions on Evolutionary Computation, 7(6), pp.561~575 (2003)[DOI]
- S. Garcia, "A memetic algorithm for evolutionary prototype selection: a scaling up approach", Pattern Recognition, 8(41), pp.2693~2709 (2008)
- J. R. Cano, "Stratification for scaling up evolutionary prototype selection", Pattern Recognition Letters, 26(7), pp.953~963 (2005)[DOI]
- C. Garcia-Osorio, "Democratic instance selection: a linear complexity instance selection algorithm based on classifier ensemble concepts", Artificial Intelligence, 174(5, pp.6) (2010), 410~441
- I. Triguero, "MRPR: a MapReduce solution for prototype reduction in big data classification", Neurocomputing, 150, pp.331~345 (2015)[DOI]
- M. F. Porter, "An algorithm for suffix stripping", Program, 14(3), pp.130~137 (1980)[DOI]
- Y. Yang, "A comparative study on feature selection in text categorization", Proceedings of the 14th International Conference on Machine Learning, pp.412~420 (1997)