基于局部相关性的kNN分类算法

doi:10.16088/j.issn.1001-6600.2016.01.008

广西师范大学学报（自然科学版） ›› 2016, Vol. 34 ›› Issue (1): 52-58.doi: 10.16088/j.issn.1001-6600.2016.01.008

基于局部相关性的kNN分类算法

邓振云¹, 龚永红^1,2, 孙可¹, 张继连¹

1.广西师范大学广西多源信息挖掘与安全重点实验室,广西桂林541004;
2.桂林航天工业学院,广西桂林541004

收稿日期:2015-06-16 发布日期:2018-09-14
通讯作者: 张继连(1977—),男,广西桂林人,广西师范大学教授,博士。E-mail:jiliangzhang@sina.com;龚永红(1970—),女,广西永福人,桂林航天工业学院副教授。E-mail: zysjd2015@163.com
基金资助:
国家自然科学基金资助项目(61573270,61263035,61363009);国家973计划项目(2013CB329404);广西自然科学基金资助项目(2012GXNSFGA060004,2015GXNSFCB139011);中国博士后科学基金资助项目(2015M570837);广西多源信息挖掘与安全重点实验室开放基金资助项目(MIMS13-08)

A kNN Classification Algorithm Based on Local Correlation

DENG Zhenyun¹, GONG Yonghong^1,2, SUN Ke¹, ZHANG Jilian¹

1. Guangxi Key Lab of Multi-source Information Mining & Security,Guangxi Normal University,Guilin Guangxi 541004,China;
2. Guilin University of Aerospace Technology,Guilin Guangxi 541004,China

Received:2015-06-16 Published:2018-09-14

摘要/Abstract

摘要： kNN算法作为一种简单、有效的分类算法,在文本分类中得到广泛的应用。但是在k值(通常是固定的)的选取问题上通常是人为设定。为此,本文引入了重构和局部保持投影(locality preserving projections,LPP)技术用于最近邻分类,使得k值的选取是由样本间的相关性和拓扑结构决定。该算法利用l₁-范数稀疏编码方法使每个测试样本都由它的k(不固定)个最近邻样本来重构,同时通过LPP保持重构前后样本间的局部结构不变,不仅解决了k值的选取问题,并且避免了固定k值对分类的影响。实验结果表明,该方法的分类性能优于经典kNN算法。

关键词: kNN, 保局投影, 重构, 稀疏编码

Abstract: As a simple and effective classification algorithm, kNN algorithm is widely used in text classification. However, the k value (usually fixed) is usually set by users. For this purpose, the reconstruction and locality preserving projections (LPP) technology is introduced into the nearest neighbor classification, which makes the selection of the k value to be determined by the correlation between the samples and the topology structure. The algorithm uses l₁-norm sparse coding method to reconstruct the test sample by its k (not fixed) nearest neighbor samples and LPP keeps the local structure of the sample after the reconstruction, which not only solves the problem of choosing k value, but also avoids the influence of fixed k value on classification. Experimental results show that the classification performance of the proposed method is better than that of the classical kNN algorithm.

Key words: k-nearest neighbor, locality preserving projections, reconstruction, sparse coding

中图分类号:

TP181

邓振云, 龚永红, 孙可, 张继连. 基于局部相关性的kNN分类算法[J]. 广西师范大学学报（自然科学版）, 2016, 34(1): 52-58.

DENG Zhenyun, GONG Yonghong, SUN Ke, ZHANG Jilian. A kNN Classification Algorithm Based on Local Correlation[J]. Journal of Guangxi Normal University(Natural Science Edition), 2016, 34(1): 52-58.

参考文献

[1] 张著英,黄玉龙,王翰虎. 一个高效的KNN分类算法[J]. 计算机科学,2008,35(3):170-172.
[2] 李荣陆,胡运发. 基于密度的kNN文本分类器训练样本裁剪方法[J]. 计算机研究与发展,2004,41(4):539-545.
[3] 张孝飞,黄河燕. 一种采用聚类技术改进的KNN文本分类方法[J]. 模式识别与人工智能,2009,22(6):936-940.
[4] 陆广泉,谢扬才,刘星,等. 一种基于KNN的半监督分类改进算法[J]. 广西师范大学学报(自然科学版),2012,30(1):45-49. DOI: 10.16088/j.issn.1001-6600.2012.01.004.
[5] HAN Jiawei,KAMBER M. Data mining: concepts and techniques[M]. Waltham, MA: Morgan Kanfmann Publishers,2000.
[6] ZHANG Shichao.Cost-sensitive classification with respect to waiting cost[J]. Knowledge-Based Systems, 2010,23(5): 369-378. DOI: 10.1016/j.knosys.2010.01.008.
[7] LALL U,SHARMA A.A nearest neighbor bootstrap for resampling hydrologic time series[J].Water Resouarces Research,1996,32(3): 679-693. DOI: 10.1029/95WR02966.
[8] LIU Huawen,ZHANG Shichao.Noisy data elimination using mutual k-nearest neighbor for classification mining[J]. Journal of Systems and Software,2012,85(5): 1067-1074. DOI:10.1016/j.jss.2011.12.019.
[9] WU Xindong,ZHANG Chengqi,ZHANG Shichao.Database classification for multi-database mining[J]. Information Systems, 2005,30(1): 71-88. DOI:10.1016/j.is.2003.10.001.
[10] JENATTON R,GRAMFORT A,MICHEL V,et al. Multi-scale mining of fMRI data with hierarchical structured sparsity[J]. Siam Journal on Imaging Sciences,2012,5(3): 835-856. DOI:10.1137/110832380.
[11] ZHU Xiaofeng,HUANG Zi,SHEN Hengtao,et al. Dimentionality reduction by mixed-kernel canonical correlation analysis[J]. Pattern Recognition,2012,45(8): 3003-3016. DOI:10.1016/j.patcog.2012.02.007.
[12] ZHU Xiaofeng,HUANG Zi,CHENG Hong,et al.Sparse hashing for fast for fast multimedia search[J]. ACM Transaction on Information System,2013,31(2): 9. DOI:10.1145/2457465.2457469.
[13] KANG P,CHO S. Locally linear reconstruction for instance-based learning[J]. Pattern Recogntion,2008,41(11): 3507-3518. DOI: 10.1016/j.patcog. 2008.04.009.
[14] LIANG Jinjin,WU De.Sparse least square support vector machine with L1 norm[J]. Computer Engineering and Design,2014,35(1): 293-296,338.
[15] BOYD S. Alternating direction method of multipliers[EB/OL]. [2015-03-25]. http://stanford.edu/class/ee364b/lectures/admm_slides.pdf.
[16] CHANG C C,LIN C J.LIBSVM: A library for support vector machine[J]. ACM Transactions on Intelligent Systems and Technology,2011,2(3):27.DOI: 10.1145/1961189.1961199.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于局部相关性的kNN分类算法

A kNN Classification Algorithm Based on Local Correlation

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

Metrics

本文评价

推荐阅读 9

[1]	吴昊, 秦立春, 罗柳容. 基于提升度的KNN分类子的分类原则改良模型[J]. 广西师范大学学报（自然科学版）, 2019, 37(2): 75-81.
[2]	宗鸣, 龚永红, 文国秋, 程德波, 朱永华. 基于稀疏学习的kNN分类[J]. 广西师范大学学报（自然科学版）, 2016, 34(3): 39-45.
[3]	苏毅娟, 孙可, 邓振云, 尹科军. 基于LPP和l_2,1的KNN填充算法[J]. 广西师范大学学报（自然科学版）, 2015, 33(4): 55-62.
[4]	王峰, 靳小波, 于俊伟, 王贵财. V-最优直方图及其在车牌分类中的应用研究[J]. 广西师范大学学报（自然科学版）, 2013, 31(3): 138-143.
[5]	陆广泉, 谢扬才, 刘星, 张师超. 一种基于KNN的半监督分类改进算法[J]. 广西师范大学学报（自然科学版）, 2012, 30(1): 45-49.