A Fast Text Categorization Approach Based on k-Nearest Neighbor

doi:10.7523/j.issn.2095-6134.2005.5.004

Abstract

Abstract:

k-Nearest Neighbor (k-NN) is one of the simplest and most effective algorithms for text categorizat ion. However, k-NN search requires intensive similarity computations, part icularly for large training set, the search of the whole set is unacceptable. Therefore, speeding-up k-NN search is a key for making k-NN categorizat ion useful in practice. In this paper a fast text categorization approach based on k-NN, which can classify textual documents quickly and efficiently on condition of searching in the very large training set is presented. Experiment shows that the new algorithm can greatly improve the performance.

Key words: text categorization, k-Nearest Neighbor(k-NN), multidimensional index, similarity retrieval

CLC Number:

TP391

ZHANG Qing-Guo, ZHANG Hong-Wei, ZHANG Jun-Yu. A Fast Text Categorization Approach Based on k-Nearest Neighbor[J]. , 2005, 22(5): 554-559.

References

[1] Yang Y,Liu X.A re-examination of text cat egorizat ionmethods.In: Proceedings of 22nd Annual Int ernational ACMSIGIR Conf erence on Researchand Development in Information Ret rieval (SIGIR.99).Berkeley: ACM Press,1999.42~ 49

[2] He J,Tan AH,Tan CL.A comparative study on Chinese text categorization methods.In: Proceedings of the Int ernational Workshop on Text andWeb Mining.Singapore: Melbourne,2000.24~ 35

[3] Cover TM,Hart PE.Nearest neighbor pattern classificat ion.IEEE Transactions on Inf ormation Theory,1968,IT-13: 21~ 27

[4] Hart PE.Condensed nearest neighbor rule.IEEE Transactions on Inf ormation Theory,1968,IT-14: 515~ 516

[5] Li RL,Hu YF.Noise reduction to text cat egorizat ion based on density for kNN.In: Proceeding of the Second Internat ional Conference onMachineLearning and Cybernetics.Xi.an,2003.3119~ 3124

[6] Hwang WJ,Wen KW.Fast kNN classificat ion algorithm based on part ial distance search.El ectronics Let ters,1998,34(21) : 2006~ 2063

[7] Baek SJ,Sung KM.Fast K-neares-t neighbour search algorithm for nonparametric classification.Electronics Lett ers,2000,36(21) : 1821~ 1822

[8] Grabowski S.Vot ing over multiple k-NN classif ier.TCSET.2002.2002.223~ 225

[9] Denoeux T.A k-nearest neighbor classif ication rule based on dempst er-shaf er theory.IEEE Trans on Systems,Man,and Cybernetics,1995,25(5) :804~ 813

[10] Wang Z,Hu WD,Yu WX,et al.Quick k-nearest neighbour classification algorithm based on near neighbour searching.Systems Engineering andElectronics,2002,24(4) : 100~ 102(in Chinese with English abstract)

[11] Zhang B,Srihari SN.A fast algorithm f inding k-nearest neighbors with non-metri c dissimilarity.In: Proceedings of the Eighth InternationalWorkshop on Front iers in Handwrit ing Recognit ion(IWFHR.02).2002

[12] http:PPiris.usc.eduPVision-NotesPbibliographyPpattern618.html

[13] Guttman A.R-trees: a dynamic index structure for spat ial searching.In: Proceedings of ACM S IGMOD.Boston,MA: ACM Press,1984.47~ 57

[14] Lin K,JagadishHV,Faloutsos C.The TV-tree: an index st ructure for high-dimensional dat a.VLDB Journal,1994,3: 517~ 542

[15] Robinson JT.The K-D-B-t ree: a search structure for large mult idimensional dynamic indexes.In: Proceedings of ACM SIGMOD Conf erence onManagement of Data.Ann Arbor: ACM Press,1981.10~ 18

[16] Feng YC,Cao K,Cao ZS.A mult idimensional index structure for fast similarity retrieval.Journal of Sof tware,2002,13 (8) : 1678 ~ 1685(inChinese with English abstract)

[10] 王壮,胡卫东,郁文贤,等.一种基于近邻搜索的快速k 近邻分类算法.系统工程与电子技术,2002,24(4) : 100~ 102

[16] 冯玉才,曹奎,曹忠升.一种支持快速相似检索的多维索引结构.软件学报,2002,13(8) : 1678~ 1685