文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 基于SVM的特征加权KNN算法
侵权投诉

基于SVM的特征加权KNN算法

第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

第1页

你可能喜欢

  • KNN算法
  • SVM分类
  • 贝叶斯算法
  • 支持向量机原理
  • 支持向量机算法
  • 算法研究
  • 粒子群优化算法

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email