A Novel Weighted Distance KNN Algorithm Based on Instances Condensing

Abstract:

As a nonparametric classification algorithm, K-Nearest Neighbor (KNN) is very efficient and can be easily realized. However, for large dataset, the computational demands for classifying instances using KNN can be expensive. A way to solve this problem is through the condensing approach. It means we remove instances that will bring computational burden but do not contribute to better classification accuracy. This paper proposes a novel weighted distance KNN algorithm based on instances condensing algorithm. The proposed idea is to extract some representative instances and take the processed result as a new training sample set. Meanwhile, use the distance-weighted WDKNN algorithm to improve the prediction accuracy, our experiments show that the proposed strategy can dramatically shorten the time consumption compared with the traditional KNN. On average, the speedup ratios improve 90% while classification accuracy only has 2% decreases.

• Periodical: Applied Mechanics and Materials (Volumes 701-702)
• Pages: 8-12
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.701-702.8
• Online since: December 2014
• Authors: Gang Tao*, Yong Gang Yan, Jiao Zou, Jun Liu
• Keywords: Center Vector, Instances Condensing, KNN, Machining, WDKNNC Algorithm

References

[1] Cover T. Hart, P. nearest neighbor pattern classification, IEEE Transactions on Information Theory, Vol. 13 (1967), pp.21-27.

DOI: 10.1109/tit.1967.1053964

[2] V. Vaidehi, S. Vasuhi, Person Authentication using Face Recognition, in Proc. Proceedings of the world congress on engineering and computer science, San Francisco(2013), pp.321-319.

[3] G. Toker, O. Kirmemis, Text Categorization using k Nearest Neighbor Classification, M.S. thesis, Dept. Computer Engineering., Middle East Technical University., Turkey, (2006).

[4] F. Bajramovie et. al, A Comparison of Nearest Neighbor Search Algorithms for Generic Object Recognition, ACIVS, Vol. 4179 (2006), pp.186-1197.

[5] Gleb Beliakov, Gang Li, Improving the speed and stability of the k-Nearest Neighbors method, Pattern Recognition Letters. Vol. 33 (2012), pp.1296-1301.

DOI: 10.1016/j.patrec.2012.02.016

[6] E Alpaydin, Voting Over Multiple Condensed Nearest Neighbors, Artificial Intelligent Review Vol. 11 (1997) , pp.115-132.

DOI: 10.1007/978-94-017-2053-3_4

[7] WANG Zhuang, HU Wei-dong, YU Wen-xian, ZHUANG Zhao wen, A Quick k-Nearest Neighbor Classification Algorithm Based on Near Neighbor Searching, Systems Engineering and Electronics , Vol. 24 (2002), pp.100-102.

DOI: 10.1109/icmlc.2003.1260141

[8] Jianping Gou Taisong Xiong and Yin Kuang. A Novel Weighted Voting for K-Nearest Neighbor Rule [J]. Journal of computers, Vol. 6 (2011), pp.5-7.

DOI: 10.4304/jcp.6.5.833-840

[9] G. Guo, H. Wang, D. Bell, KNN Model based Approach in Classification, in On The Move to Meaningful Internet , Vol. 2888(2003), pp.986-996.

DOI: 10.1007/978-3-540-39964-3_62