第44卷 第1期2005年 1月中山大学学报(自然科学版)
ACTA SCIENTIARUM NATURALIUM UNIVERSITATIS SUNYATSENIVol144 No11
Jan1 2005
基于SVM的特征加权KNN算法
陈振洲1,2,李 磊1,姚正安2
(1.中山大学软件研究所,广东广州510275;2.中山大学数学与计算科学学院,广东广州510275)
X
摘 要:作为一种非参数的分类算法,K_近邻(KNN)算法是非常有效和容易实现的。它已经广泛应用于分
类、回归和模式识别等。在应用KNN算法解决问题的时候,要注意两个方面的问题)))样本权重和特征权重。利用SVM来确定特征的权重,提出了基于SVM的特征加权算法(FWKNN,featureweightedKNN)。实验表明,在一定的条件下,FWKNN能够极大地提高分类准确率。
关键词:支持向量机;K_近邻算法;距离加权;特征加权
-6579(2005)01-0017-04中图分类号:TP30116 文献标识码:A 文章编号:0529
Cover和Hart[1]提出的最近邻法已经成为一种非常有效的非参数分类算法。最近邻法是一种消极(lazy)学习法)))学习过程只是简单地存储已知的
训练数据;当遇到新的查询样本时,一系列相似的样本被取出,并用来分类新的查询样本。
对于最优的K值,KNN分类器提供了很好的分类性能。可以看出,如果K无限大,KNN分类规则就变成了Bayes最优分类规则[2]。对KNN算法的一个明显的改进是对K个近邻的贡献加权(距离加权KNN算法)[3],将较大的权值赋给较近的近邻)))它对训练数据中的噪声有很好的健壮性,而且当给定足够大的训练集合时也非常有效。
应用KNN算法的一个实践问题是,样本的距离是根据样本的所有特征(属性)计算的。在这些特征中,有些特征与分类是强相关的;有些特征与分类是弱相关的;还有一些特征(可能是大部分)与分类不相关。这样近邻间的距离会被大量的不相关特征所支配,这钟情况也称为维度灾难(curseofdimensionality),最近邻方法对这个问题特别敏感。
本文利用新的机器学习算法SVM来解决KNN算法所面临的维度灾难问题。虽然SVM的提出主要是解决分类和回归问题,但是SVM实际上可以给出数据样本特征的相对权重,这就为我们在KNN算法中利用SVM解决维度灾难问题提供了一个很好的方法。
本文的组织如下:第1节主要介绍KNN;第2节介绍支持向量机(SVM);第3节主要研究基于
X收稿日期:2004-03-05
SVM的特征加权KNN(FWKNN)算法;第4节是实验结果和分析;最后是结语。
1 K_近邻(KNN)算法
KNN算法假定所有的样本对应于n维空间Rn中的点,一个样本的最近邻是根据标准的欧氏距离定义的。任意的样本x表示为特征向量x=(x1,x2,,,xm),xi表示样本x的第i个特征的值。那么,2个样本xi和xj的距离定义为d(xi,xj),其中:
d(xi,xj)=
l=1
E(xi-l
xlj)2
在最近邻学习中,目标函数可以是离散值(分类问题),也可以是连续值(回归问题),本文主要讨论目标函数为离散值(分类问题)的问题)))f:RyV,其中V={v1,,,vs}。KNN算法的返回值f (xq)就是对f(xq)的估计,它就是距离xq最近的k个训练样本中最普遍的f值,其中:
f (xq)zargmaxvIV
k
n
i=1
ED(v,f(xi)),
D(a,b)=1,若a=bD(a,b)=0,否则
对KNN算法的一个明显的改进是对K个近邻的贡献加权(距离加权KNN算法),将较大的权值赋给较近的近邻(样本距离越近,相似度越高,贡献也就越大),一般是根据与每个近邻的距离xq平方的倒数加权这个距离的贡献:
基金项目:广东省工业攻关计划项目(2004B10101004)
),男,;E
( 自然科 学版 ) ACASEqIT CIN'ARUM NATRUAUUM UVE玎AnSSNYArE N【RS U NIS Vo.4N1】4 o. Jn2o a.05 基于SM的特征加权K N算法 VN 陈振 洲一,李 磊...
一种基于特征加权的KNN文本分类算法_专业资料。KNN文本分类算法是一种简单、有效、非参数的分类方法。针对传统的KNN文本分类算法的不足,出现了很多改进的KNN算法。但...
基于SVM的特征加权KNN算法 暂无评价 4页 免费 基于兴趣点凸包和SVM加权反... ...xxxx 一种基于SVM的加权似然比融合算法魏振华, 江雪峰 (华北电力大学 摘 控制...
2010年4月 电 脑 学 习 第2期 一种基于特征加权的 KNN 文本分类算法* 赵俊杰** 摘 盛剑锋*** 陶新民*** 要:KNN 文本分类算法是一种简单、 有效、 非...
基于指纹识别特征选择的改进加权KNN算法_互联网_IT/计算机_专业资料。文章编号 :1007—1423(2014)02—0027—03 DOI:10.3969/j.issn.10文章...
基于SVM的特征加权KNN算... 4页 免费 基于SVM_KNN算法的特色数... 5页 2...29 No. 5 May 2012 SVM 的混合协同过滤推荐算法 * 基于 KNN1a 1b 2 吕成...
基于KNN图的空间离群点挖掘... 4页 1财富值 基于SVM的特征加权KNN算法 4页 ...一种基于加权KNN的大数据集下离群检测算法王茜杨正宽 (重庆大学计算机学院 重庆...
基于SVM—KNN的文本分类算法及其分析_专业资料。通过实验对SVM、KNN文本分类算法进行了深入探讨。基于KNN和SVM算法,提出了一种SVM.KNN算法。该算法结合KNN和SVM两种分...
非平衡语料下改进的SVM-KNN算法_专业资料。结合SVM和KNN方法改进而成的SVM—KNN分类器,较SVM在准确度上有较大提高.但在处理非平衡语料时,性能反而不如SVM分类器....
基于KNN和SVM算法,提出了一种SVM.KNN算法。该算法结合KNN和SVM两种分类器,并通过分类预测概率的反馈和修正来提高分类器性能。在CWTl00G中文网页分 类测试系统中,对...
热门文档