Accelerated <italic style="font-style: italic">k</italic>-nearest neighbors algorithm based on principal component analysis for text categorization

Min DU; Xing-shu CHEN

doi:10.1631/jzus.C1200303

Your Location：

Home >

Browse articles >

Accelerated k-nearest neighbors algorithm based on principal component analysis for text categorization

计算机与自动化 | Updated：2022-12-09

- Accelerated k-nearest neighbors algorithm based on principal component analysis for text categorization
- Accelerated k-nearest neighbors algorithm based on principal component analysis for text categorization
- 信息与电子工程前沿（英文） 2013年14卷第6期页码：407-416
- Affiliations：
  
  School of Computer Science, Sichuan University, Chengdu 610065, China
- Author bio：
  
  [ "Min DU, E-mail: doingscu@gmail.com" ]
  Xing-shu CHEN, E-mail: chenxsh@scu.edu.cn
- Funds：
  
  Project (No. 2012BAH18B05) supported by the National Key Technology R&D Program of China
- DOI：10.1631/jzus.C1200303
  中图分类号： TP391
- 收稿：2012-10-24，
  
  修回：2013-;5-13，
  
  纸质出版：2013-06
- Accepted：
Scan QR Code
Accelerated k-nearest neighbors algorithm based on principal component analysis for text categorization[J]. 信息与电子工程前沿（英文）, 2013,14(6):407-416.

Min DU, Xing-shu CHEN. Accelerated k-nearest neighbors algorithm based on principal component analysis for text categorization[J]. Frontiers of Information Technology & Electronic Engineering, 2013, 14(6): 407-416.
Accelerated k-nearest neighbors algorithm based on principal component analysis for text categorization[J]. 信息与电子工程前沿（英文）, 2013,14(6):407-416. DOI： 10.1631/jzus.C1200303.

Min DU, Xing-shu CHEN. Accelerated k-nearest neighbors algorithm based on principal component analysis for text categorization[J]. Frontiers of Information Technology & Electronic Engineering, 2013, 14(6): 407-416. DOI： 10.1631/jzus.C1200303.

摘要

Abstract

Text categorization is a significant technique to manage the surging text data on the Internet. The

-nearest neighbors (kNN) algorithm is an effective

but not efficient

classification model for text categorization. In this paper

we propose an effective strategy to accelerate the standard kNN

based on a simple principle: usually

near points in space are also near when they are projected into a direction

which means that distant points in the projection direction are also distant in the original space. Using the proposed strategy

most of the irrelevant points can be removed when searching for the

-nearest neighbors of a query point

which greatly decreases the computation cost. Experimental results show that the proposed strategy greatly improves the time performance of the standard kNN

with little degradation in accuracy. Specifically

it is superior in applications that have large and high-dimensional datasets.

关键词

Keywords

references

Z. Aghbari . . Array-index: a plug & search K nearest neighbors method for high-dimensional data . . Data Knowl. Eng. , , 2005 . . 52 ( ( 3 ): ): 333 - - 352 . . DOI: 10.1016/j.datak.2004.06.015 http://doi.org/10.1016/j.datak.2004.06.015 . .

E.H. Chen , , , Y.G. Lin , , , H. Xiong , , , Q.M. Luo , , , H.P. Ma . . Exploiting probabilistic topic models to improve text categorization under class imbalance . . Inf. Process. Manag. , , 2011 . . 47 ( ( 2 ): ): 202 - - 214 . . DOI: 10.1016/j.ipm.2010.07.003 http://doi.org/10.1016/j.ipm.2010.07.003 . .

K. Coussement , , , D. van den Poel . . Integrating the voice of customers through call center emails into a decision support system for churn prediction . . Inf. Manag. , , 2008 . . 45 ( ( 3 ): ): 164 - - 174 . . DOI: 10.1016/j.im.2008.01.005 http://doi.org/10.1016/j.im.2008.01.005 . .

A.F. de Souza , , , F. Pedroni , , , E. Oliveira , , , P.M. Ciarelli , , , W.F. Henrique , , , L. Veronese , , , C. Badue . . Automated multi-label text categorization with VG-RAM weightless neural networks . . Neurocomputing , , 2009 . . 72 ( ( 10-12 ): ): 2209 - - 2217 . . DOI: 10.1016/j.neucom.2008.06.028 http://doi.org/10.1016/j.neucom.2008.06.028 . .

J. He , , , A.H. Tan , , , C.L. Tan . . On machine learning methods for Chinese document categorization . . Appl. Intell. , , 2003 . . 18 ( ( 3 ): ): 311 - - 322 . . DOI: 10.1023/A:1023202221875 http://doi.org/10.1023/A:1023202221875 . .

H.V. Jagadish , , , B.C. Ooi , , , K.L. Tan , , , C. Yu , , , R. Zhang . . iDistance: an adaptive B + -tree based indexing method for nearest neighbor search . . ACM Trans. Database Syst. , , 2005 . . 30 ( ( 2 ): ): 364 - - 397 . . DOI: 10.1145/1071610.1071612 http://doi.org/10.1145/1071610.1071612 . .

J.Y. Jiang , , , S.C. Tsai , , , S.J. Lee . . FSKNN: multi-label text categorization based on fuzzy similarity and k nearest neighbors . . Expert Syst. Appl. , , 2012 . . 39 ( ( 3 ): ): 2813 - - 2821 . . DOI: 10.1016/j.eswa.2011.08.141 http://doi.org/10.1016/j.eswa.2011.08.141 . .

S.Y. Jiang , , , G.S. Pang , , , M.L. Wu , , , L.M. Kuang . . An improved K -nearest-neighbor algorithm for text categorization . . Expert Syst. Appl. , , 2012 . . 39 ( ( 1 ): ): 1503 - - 1509 . . DOI: 10.1016/j.eswa.2011.08.040 http://doi.org/10.1016/j.eswa.2011.08.040 . .

L.H. Lee , , , D. Isa , , , W.O. Choo , , , W.Y. Chue . . High relevance keyword extraction facility for Bayesian text classification on different domains of varying characteristic . . Expert Syst. Appl. , , 2012 . . 39 ( ( 1 ): ): 1147 - - 1155 . . DOI: 10.1016/j.eswa.2011.07.116 http://doi.org/10.1016/j.eswa.2011.07.116 . .

B. Liu . . Web Data Mining , , 2nd Ed : : Berlin, Heidelberg Springer , , 2011 . . p.217 . .

Y.Q. Miao , , , M. Kamel . . Pairwise optimized Rocchio algorithm for text categorization . . Pattern Recogn. Lett. , , 2011 . . 32 ( ( 2 ): ): 375 - - 382 . . DOI: 10.1016/j.patrec.2010.09.018 http://doi.org/10.1016/j.patrec.2010.09.018 . .

X.G. Qi , , , B.D. Davison . . Web page classification: features and algorithms . . ACM Comput. Surv. , , 2009 . . 41 ( ( 2 ): ): 12 - - 42 . . DOI: 10.1145/1459352.1459357 http://doi.org/10.1145/1459352.1459357 . .

W. Shang , , , H. Huang , , , H. Zhu , , , Y. Lin , , , Y. Qu , , , Z. Wang . . A novel feature selection algorithm for text categorization . . Expert Syst. Appl. , , 2007 . . 33 ( ( 1 ): ): 1 - - 5 . . DOI: 10.1016/j.eswa.2006.04.001 http://doi.org/10.1016/j.eswa.2006.04.001 . .

B.K. Wang , , , Y.F. Huang , , , W.X. Yang , , , X. Li . . Short text classification based on strong feature thesaurus . . J. Zhejiang Univ.-Sci C (Comput. & Electron.) , , 2012 . . 13 ( ( 9 ): ): 649 - - 659 . . DOI: 10.1631/jzus.C1100373 http://doi.org/10.1631/jzus.C1100373 . .

S.G. Wang , , , D.Y. Li , , , X.L. Song , , , Y.J. Wei , , , H.X. Li . . A feature selection method based on improved Fisher's discriminant ratio for text sentiment classification . . Expert Syst. Appl. , , 2011 . . 38 ( ( 7 ): ): 8696 - - 8702 . . DOI: 10.1016/j.eswa.2011.01.077 http://doi.org/10.1016/j.eswa.2011.01.077 . .

Y. Wang , , , Z.O. Wang . . A Fast KNN Algorithm for Text Categorization . . Proc. 6th Int. Conf. on Machine Learning and Cybernetics , , 2007 . . p.3436 - - 3441 . . DOI: 10.1109/ICMLC.2007.4370742 http://doi.org/10.1109/ICMLC.2007.4370742 . .

X. Zhang , , , H. Huang , , , K. Zhang . . KNN Text Categorization Algorithm Based on Semantic Centre . . Proc. Int. Conf. on Information Technology and Computer Science , , 2009 . . p.249 - - 252 . . DOI: 10.1109/ITCS.2009.57 http://doi.org/10.1109/ITCS.2009.57 . .

B. Zhou , , , Y.Y. Yao , , , J. Luo . . A Three-Way Decision Approach to Email Spam Filtering . . Proc. 23rd Canadian Conf. on Artificial Intelligence , , 2010 . . p.28 - - 39 . . DOI: 10.1007/978-3-642-13059-5_6 http://doi.org/10.1007/978-3-642-13059-5_6 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

Learning robust principal components from L1-norm maximization

Accelerated k-nearest neighbors algorithm based on principal component analysis for text categorization

Accelerated k-nearest neighbors algorithm based on principal component analysis for text categorization

DOI：10.1631/jzus.C1200303

摘要

Abstract

关键词

Keywords

references