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

Computer & Automation | 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
- Frontiers of Information Technology & Electronic Engineering Vol. 14, Issue 6, Pages: 407-416(2013)
- 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：
- DOI：10.1631/jzus.C1200303
  CLC： TP391
- Received：24 October 2012，
  
  Revised：2013-;5-13，
  
  Published：2013-06
- Accepted：
Scan QR Code
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：

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 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

Learning robust principal components from L1-norm maximization

Related Author

Ding-cheng FENG

Feng CHEN

Wen-li XU

Related Institution

Tsinghua National Laboratory for Information Science and Technology, Tsinghua University

Department of Automation, Tsinghua University

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰

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

DOI：10.1631/jzus.C1200303

摘要

Abstract

关键词

Keywords

references