改进的KNN算法

2024-05-20

改进的KNN算法（精选7篇）

改进的KNN算法篇1

搜索引擎技术的出现虽然给人们检索信息带来了方便,但是大部分的检索机制只是对查询关键词的简单匹配,因此反馈给用户的结果往往不是用户所需要的信息。通常用户输入的查询关键词很短,例如只输入“计算机”这个词,搜索引擎会返回很多结果,其中包含计算机等级考试或培训、计算机硬件销售、计算机学科等多类别的信息。80%的用户通常只对前一、两页中的返回结果感兴趣,往往会忽略后面页中的有价值信息,并不能很好地满足用户的查询需要[1]。因此网页分类技术逐渐发展起来。网页分类技术能够自动对网页进行类别划分,在用户检索时帮助用户快速地进行信息的类别定位,从而提高检索的效率。网页自动分类技术是Web信息检索中的重要内容之一,成为当前信息检索领域的研究热点。

网页分类中的经典算法包括类中心法、Naive-Bayes法、支持向量机(Support Vector Machine,简称SVM)、K-近邻算法(K-Nearest Neighbor,简称KNN)算法等。CMU的Yim Yang等人通过实验证明KNN算法是应用于网页分类最有效的方法[2]。KNN算法具有训练时间短,分类精度高的优点,但是也存在着一定程度的缺陷。它是典型的懒惰分类算法,对于分类所需的时间都推迟到分类时才进行,由于缺少了训练过程,所有的学习过程都集中在与整个数据集计算比较上,当训练数据集比较大时,计算开销很大,不适用于在线的实时分类。并且该算法对样本的分布情况比较敏感,样本分布不均匀会造成分类准确率的下降。本文将研究KNN的数据集优化策略,提出一种生成代表样本的方法。

1 KNN算法

1.1 KNN算法简介

经实验论证,在VSM模型下,KNN被认为是分类性能最好的分类算法[2]。有别以于其他分类算法,KNN算法不需要在训练过程中对分类器进行学习和训练,它能够对测试文档向量直接进行分类计算。算法步骤如下[2,3]:

(1)根据特征项集合重新描述训练文本向量;

(2)在新文本到达后,对新文本分词,并进行向量表示;

(3)计算训练集中所有样本与新文本的相似度,选出与新文本最相似的K个文本,相似度计算公式如下:undefined

(4)在新文本的K个邻居中,根据公式(2)[3]依次计算新文本相对于每类的权重:

undefined

其中,undefined为新文本的特征向量; Sim(undefined,undefinedi)为相似度计算公式,而y(undefinedi,Cj)为类别属性函数,即:如果di属于类Cj,那么函数值为1,否则为0,bj为预先计算得到的Cj的最优截尾阈值;

(5) 比较类的权重,将文本分到权重最大的那个类别中。

分析KNN的分类过程可知:(1)这些步骤大部分都集中在分类时进行,要遍历整个训练样本空间,分类法的效率取决于已知样本数据集的规模,对于庞大的数据集,显然计算量是巨大的,算法的执行效率比较低,不适用于海量数据的Web文档在线分类;(2) KNN的精度也依赖于K值的大小,目前的做法通常是人工指定一个经验值,从一定程度上带来了偏差;(3)在实际应用中,样本分布存在多峰分布[4]情况,因此同类样本之间的距离可能会大于不同类样本之间的距离;样本的分布往往不够紧密,很多样本处于类别的边界,容易造成错分情况;标准KNN算法的分类决策只统计临近样本的个数,这在很多情况下不够精确[4],因此样本的分布情况也影响了KNN的分类性能。

1.2 相关工作

针对这些不足之处,许多研究者都提出了改进措施:为了解决样本分布对KNN造成的影响,中科院的S Tan提出了一种适应性的KNN改进算法[5],对样本数差异较大的类别,设定不同的K值,减少了算法对样本分布的依赖性;为了提高分类精度,北京大学的L Baoli提出的方法是在比较两个样本的相似度时,对重要度较高的属性进行加权,加权的值为该维特征的权值,从而提高了类别的可标识度[6];为了提高KNN的分类效率,同济大学的张高胤等提出了动态生成代表样本法[7],选取样本集中的代表样本作为训练样本,从而减少训练样本集数量,但是该算法需要设定一个阈值,同类别的样本在这个阈值之间动态调整,生成代表样本。

2 代表样本集生成策略

2.1 代表样本

通过分析可知,庞大的数据集是造成KNN分类速度慢的主要原因,为此引入了代表样本[4,8]的概念。代表样本是从样本集合中选出一些最能代表类别特性的样本作为代表样本,用这些样本来代替样本集中的所有样本,在分类时只比较待分类样本与这些代表样本的相似程度,减少了分类时的计算规模。因此生成代表样本是解决KNN效率问题的有效途径。

常见的代表样本生成策略是假设同类的样本相似度最大,把同类的样本划分为一组,[4]。在每一类的中心选一个代表样本,代表样本的个数等于类别数。然而实际并非如此,样本常常存在多峰分布的情况假设训练样本集D在二维向量空间中的分布如图1所示,相同符号表示的文档属于同一类别,多峰分布导致了同一类别中的样本可能集中分布于几个不同的区域,如图2所示,若采用上述方法,黑点所代表的类的代表中心点则为方框图形所表示的样本A,而对黑点所表示的样本而言,最具有类别代表性的样本为B和C。可见,在选择代表样本时,不能只根据相似度大小或是所属类别对样本集合进行简单的划分,而是要根据他们的分布情况,综合相似度和类别属性这两个方面来决定如何生成代表样本。

本文将介绍一种代表样本生成策略。在选择代表样本时,所遵循的原则是让代表样本被尽可能多的同类样本所包围,在代表样本所代表的区域内尽可能多的包含同类样本。本文假设每个样本只属于一个类别。下面给出策略描述。

2.2 代表样本法

为了便于下文描述,首先给出样本的属性设定:

Sxy:表示文档dx与文档dy的相似度;

Ri:表示文档di可以代表的样本的个数,i是文档di的序号;

sample(i):表示di的代表样本;

r(i):表示样本di的代表相似度,即di所代表区域的最大半径;

Bji:表示样本dj与代表样本di所代表区域的区域边界相似度,Bji=Sji-r(i)。

训练过程如下:

首先,对训练样本集D,利用公式(1)计算其中所有样本之间的相似度,建立相似度矩阵M,并给每个样本d设定代表度初值Ri=1,表示每个样本都可以代表自己;初始化样本的sample属性为空,设集合D’是D经过分组划分为若干子集后组成的集合,如D’={{d1,d2},{d3,d4,d5},……}等。集合DR表示生成的代表样本集合,初始化D’={},DR={}。

其次,对标记sample(i)为null的所有属于类别C的样本di,利用公式(3)(4)求得每个样本di与其他样本(包括代表区域)的代表相似度r(i)。利用公式(5)计算所有样本di的代表度,从di中选取代表度最大的样本dc作为代表样本,增加到代表样本集合DR中,并把满足条件dj∈C,sample(dj)=null,Sij>r(i)的所有样本dj的代表属性设置为sample(dj)=i,然后把这些样本dj添加到集合D’中同时从集合D中删除。重复这个过程,直到D为空。

r(i)=max(Six,Biy’),∀dx∉C,dx∈D,dy’∈DR (3)

Biy’=Siy’-r(y’) (4)

undefined(其中i≠j) (5)

分类过程:

当一个新的待分类的样本d到来时,只需计算该样本与DR中代表样本的相似度,若相似度大于某个代表样本的代表相似度r(i),则把该样本归入该类,否则按照公式(4)计算与所有代表样本的区域边界相似度Bid。选择Bid最大值对应的代表样本di,把测试样本归入到di的类别中,样本d的类别即可确定。

2.3 算法描述

训练算法:

(1)对初始训练集D,计算样本间的相似度,生成相似度矩阵M[Sxy], 设定集合D’表示由若干个代表子集组成的集合,集合DR表示代表样本集合,初始化D’={},DR={};

(2)对所有样本di,初始化Ri=1,sample(di)=null,r(i)=0;

(3) 对任意di ∈D,且di∈C,if(sample(di)==null),则

对∀dk∉D ,dk∉C, m1=max(Sik);

对∀dk∈DR,dk∉C,计算Bik=Sik-r(k), m2=max(Bik);

(4)求得 r(i)=max(m1,m2);

(5)∀ dj∈D, dj∈C,若Sij>Li,则Ri++;

(6)Rc=max(Ri),dc=undefined,D=D-{dc},初始化一个集合A,A={dc},DR =DR+{dc}。对满足条件的(4)中的dj,sample(dj)=c,D=D-{dj}, A=A+{dj} ,D’=D’+{A};

(7)循环(2)-(5),直到D={}。

分类算法:

对待分类的新文档d:

(1)代表集合DR={d1,d2……dn},计算d与B中的代表样本的相似度{S1,S2,……Sn},n是代表样本的个数, 初始化F={};

(2)对每一个Si,

如果Si

否则,计算d到每一个样本区域边界的距离Si-r(i),F=F+{Si-r(i)};

(3)如果d未被标记,则对F中的每一个元素x,undefined,把d归入到dc所在的类别。

3 实验验证与分析

分类性能的指标采用查准率(precision)和查全率(recall)来表示,查准率是所有判断的文本类别与人工分类结果吻合的文本所占的比率,用p表示,查全率是人工分类结果应有的文本中分类系统吻合的文本所占的比率,用r表示。其数学公式表示如下其数学公式表示如下:

undefined

其中a是属于该类并被正确分类样本数,b是属于该类但被错分的样本数,c是不属于该类但被错分到该类的样本数。考虑查准率和查全率,计算综合分类率undefined[4]。

实验运行环境为P4 2.3G处理器,程序使用Java语言编写,Eclipse作为编译运行平台。实验选取了YQ-CCT-2006-03中文网页集的600个网页作为训练集,400个网页作为测试集,选取了教育、计算机、军事、法治、财经和体育几个主题作为实验的类别主题,结合向量空间模型和特征选取算法,在本文提出的代表样本法基础实现了KNN分类器,进行了实验,并与传统的KNN算法进行比较,记录分类结果,并分别计算准确率、查准率和F1对网页数量的加权平均值。实验结果见下表。

从实验结果来看,本文所提出的代表样本法在查准率和查全率上与传统的KNN算法的分类性能相当,查准率和查全率略有降低,F1值降低了约3%,但从分类时间上看,该算法比传统的KNN的分类时间缩短了40%左右。这是由于代表表样本法由于在训练过程中生成了数量比较少的代表样本集,分类时的计算都集中在代表样本空间上进行,大大缩短了分类时间。从训练规模上看,测试样本数越多,分类的性能越好,而分类时间越长。由于代表样本的数量也是算法自动生成的,整个实验过程都不需要人为估计K值的大小,从一定程度上降低了经验值带来的误差。

4 结束语

本文提出了一种对KNN训练集的优化方法-代表样本法,并给出了详细的算法描述。实验证明,该算法与传统的KNN算法相比,虽然查准率和查全率略微下降,但是分类时间大大缩短了,提高了网页的分类效率,适合对分类效率和即时性要求比较高的情况,能够满足Web在线文档分类的需要,而在分类的查准率和查全率上比传统KNN稍显不足。下一步的工作将集中到训练样本集的增量优化上。

摘要：针对KNN算法懒惰分类和效率不高的特点,将训练数据集进行优化,提取有代表性的训练样本作为代表样本,用其代替整个训练集进行相似度比较。实验结果表明,使用代表样本集的分类性能与传统KNN算法的性能相当,缩短了分类时间,提高了分类效率,并且不需要估计K值,减少了人工估计值的偏差。

关键词：网页分类,KNN,代表样本,数据集优化,相似度

参考文献

[1]Craig Silverstein,Monika Henzinger.Analysis of a Very Large Web Search Engine Query Log.SIGIR Forum,1999.

[2]Yang Y,Li X.Are-examination of text categorization method.In:Proceedings of ACMSIGIR Conference on Research and Devel-opment in Information Retrieval,1999.

[3]冯是聪,张志刚,李晓明.一种中文网页自动分类方法的实现及应用.计算机工程,2004,30(5)

[4]刘斌,黄铁军,程军等.一种新的基于统计的自动文本分类方法.中文信息学报,2002,16(6)

[5]S Tan.An effective refinement strategy for KNN text classifier.Expert Systems with Applications,2006Elsevier.

[6]L Baoli,L Qin,Y Shiwen.An Adaptive k-Nearest Neighbor Text Categorization Strategy ACMTransactions on Asian Language In-formation Processing(TALIP),2004,3(4).

[7]张高胤,谭成翔,汪海航.基于K-近邻算法的网页自动分类系统的研究及实现.计算机技术与发展,2007,17(1).

[8]华北,曹先彬.基于代表样本动态生成的中文网页分类.计算机应用,2006,26(10).

改进的KNN算法篇2

随着互联网上文本信息的快速增长, 文本分类技术已经成为Web数据挖掘的关键技术。目前常用的文本分类算法包括支持向量机 (SVM) 、k近邻 (kNN) 、决策树、线性最小二乘法估计 (LLSF) 和贝叶斯分类算法 (Bayes) 等。相关研究证明, kNN算法是向量空间模型下最好的分类算法之一。

虽然kNN算法是一种效果较好的分类算法, 但是kNN算法也存在两个缺陷:

(1) 计算开销较大

传统的k近邻方法其实并没有训练阶段, 对每一个测试文本进行分类都需要计算该测试文本与所有训练文本的距离, 其计算量随着训练文本集的增大线性增加。显然传统kNN算法的计算开销较大, 分类的速度较慢。

(2) 边界文本分类误差较大

kNN算法对边界文本分类误差较大的是因为边界处训练文本分布不均。如图1所示。图1是美国卡耐基-梅隆大学 (Carnegie Mellon University) 一个关于kNN二值分类问题的演示程序效果截图, 左边为应该得到的分类效果, 右边为实际的分类效果。可以看出左部分中两个用虚线标出区域边界的测试文本分布不均, 右部分相应的区域畸变较大, 也就是说其分类误差较大。

1 改进kNN算法

本文提出的改进kNN算法通过中心文本模型和排除算法提高kNN算法的分类速度, 通过对边界文本多k值分类提高kNN算法对边界文本的分类精度, 下面具体阐述改进kNN算法的相关内容。

1.1 中心文本向量模型

中心文本向量主要思想是在每一类训练文本中, 计算出一个中心文本向量和相应的统计信息来描述整个训练文本集。这样在对测试文本分类时只需要计算测试文本到中心文本的距离, 再采用“排除算法”排除测试文本不可能属于的类别, 从而大大减少kNN算法的计算开销。

每一类训练文本都可以看作一系列分布在圆形区域中的点, 计算每类训练文本的中心文本向量取各维特征词权值的算术平均值, 如公式1所示:

其中N为该类训练文本总数, m为特征向量维数。

需要统计的信息有两个:区域半径R和类别标签Class。区域半径为同类所有训练文本到该类的中心文本向量距离的最大值dimax。至此对每一类训练文本都可以得出一个统计值

1.2 排除算法

排除算法用于对测试文本x分类时判断x不可能属于的类别, 其主要目的是为了克服中心文本向量模型的分类误差。排除算法基本思想是:当测试文本x到类别i所有训练文本的最小距离比到另一类的平均距离还要大的时候, x属于类别i的可能性为0。也就是说, 同时满足下面两个条件时, 测试文本不属于类别i, 即排除类别i的两个必要条件:

(1) x不处于圆形区域ρi内;

(2) 若测试文本x到类别i的最小距离rimax比到另外一个类别j的中心向量距离rj还大时, 则测试文本不可能属于这个类i, 可以排除该类别;

为了验证排除算法的有效性, 以二值分类为例进行分析:如果测试文本x到类别1所有训练文本的最小距离r1max比到类别2所有训练文本的平均距离r2还要大的时候 (如图2所示) , 使用原始kNN算法得到的k个近邻肯定绝大多数属于类别2。根据kNN算法, 测试文本必然被分到类别2。

排类算法描述如下:

首先计算该测试文本x到所有类中心文本向量的距离{r1, r2…rn}和与每类训练文本的最小距离, 计算方法如公式2:

然后依次判断每个类别是否同时满足两个必要条件, 若同时满足则排除该类别, 反之将该类别作为候选类别 (即:x可能属于该类别) 。

1.3 边界文本多k值分类

边界文本多k值分类的基本思想是:对处于分类边界的测试文本x, 使用一组多个较小的k值进行分类, 然后利用这一组小k值分类的结果, 判定边界测试文本的类别, 从而达到提高边界文本的分类精度的目的。

1.3.1 边界文本多k值分类

首先选择一组m个 (m为奇数) 较小的k值 (如k=2, 3, 4) ;然后分别确定当k=2, 3, 4时的x的分类结果;最后使用公式3把x分到权值最大的类别。

其中y (x, cj) 表示选取x属于类别j的权值, y (cj, a) 表示当k=a时, 测试文本x是否属于类别j, 取值如公式4。

1.3.2 算法有效性分析

基于VSM模型的基本理论:相同类别的文本在空间距离上较其余类别的文本相近。根据图3所示, 分类误差的原因也可以表述为:k值选取过大, 由于边界密度不均, 包含了较多错误种类别的训练文本, 所以造成了误差。此时如果选取较小的k值将优先包含正确类别的训练文本, 从而得到正确的分类结果。

由图3可以看出, 当k=6时 (实际k的取值可能大的多) , 由于类别1的边界处训练文本密度较大, 测试文本x的6个近邻中有4个属于类别1, 原始kNN会将测试文本 (图3中黑色的圆, 属于类别2) 错误的分到类别1, 而减小了k值后, k=2, 3, 4时x都会被正确的分到类别2。

1.3.3 边界测试文本的判定方法

当测试文本x一定数目 (a个, a一般不大) 的近邻都为相同的类别时, 认为其处于某类别中心;反之, 当其a个近邻属于两个或两个以上的不同类别时, 认为其处于分类别界。

1.4 分类算法描述

2 实验结果和分析

语料库采用北大举行的全国SEWM (Search Engine and Web Mining) 竞赛的标准语料库, 版本号为CCT2002-V1.1YQ-WEBBENCH-V1.1。该语料库共分为人文与艺术、商业与经济等11个类别, 通过对语料库中的文本进行整理, 实验选用了4849篇文档作为训练文本, 3830篇作为测试文本。实验采用D F与C H I结合的特征降维算法, 降维后的特征空间由19112个特征词构成。通过测试当k=20时, 取得较好的分类结果, 选取k=20时改进kNN算法和kNN算法的分类结果如图4所示。

实验结果表明k N N和改进k N N算法的微指标准确率分别达到81.5%和87.6%, 而改进kNN算法的分类时间仅是kNN算法的35.6%, 如表1所示。

通过对数据的进一步分析可以发现:被kNN算法错误分类的测试文本共691篇, 其中有370篇被判定为边界文本, 而改进kNN算法能够对这370篇边界分类错误中的258篇正确分类, 占边界分类错误的69.7%。

通过对实验结果的分析, 可以发现以下三点:

(1) 改进kNN算法和kNN算法的最优k值相同。这说明在使用排除算法进行类别决策的时候, 被排除的类别中的训练文本与测试文本的距离较远, 也就是说测试文本的k个近邻中, 没有或者只包含了极少数的被排除类别的训练文本。可见排除算法可以在提高kNN算法的效率的同时, 不对算法的精度造成太大的影响;

(2) 边界分类错误占kNN分类错误的53.5%, 改进kNN算法能够对69.7%的边界分类错误进行正确的分类。可见边界文本分类误差是kNN算法误差的重要原因, 本文设计的边界文本多k值分类算法能够有效提高边界测试文本的分类精度。

(3) 改进kNN算法的分类时间仅仅是kNN算法的35.6%, 可见通过中心文本模型能够有效提高k N N算法的分类效率。

3 结论

实验结果表明, 本文设计的改进kNN算法利用中心文本模型和排除算法在提高了kNN算法效率的同时, 没有对kNN算法的分类效率造成太大的影响。并且改进kNN算法通过边界文本多k值分类算法, 有效提高了kNN算法对边界文本的分类精度。

摘要：kNN算法是一种简单、有效的文本分类方法, 并在文本分类中得到广泛的应用。但是kNN计算开销较大, 而且对处于分类边界的测试文本分类精度较低。本文针对kNN算法的缺陷, 采用中心文本向量模型和排除算法提高了kNN算法的效率, 并且提出了边界文本多k值分类算法提高了边界文本分类的准确率。实验结果表明改进的kNN算法具有较好的性能。

关键词：kNN,边界文本,排除算法

参考文献

[1]Yang Yiming, and Liu Xin.A re-examination of text categorization methods.Proceedings of the 22nd ACM International Conference on Research and Development in Information Retrieval (SIGIR-99) .1999.

[2]HeJ, TanAH, TanCL.A comparative study on Chinese text categorization methods.In Proceedings of the International Work-shop on Text and Web Mining.Singapore Melbourne.2000.

[3]Gongde Guo, Hui Wang, David Bell, etc.kNN Model-Based Approach in Classification.

[4]张庆国, 张宏伟, 张君玉.一种基于k最近邻的快速文本分类方法.中国科学院研究生院学报.2005.

[5]李荣陆, 胡运发.基于密度的kNN文本分类器训练样本裁剪方法.计算机研究与发展.2004.

改进的KNN算法篇3

最简单的视频转码技术就是先对视频完全解码再重新进行编码,然而这种方法并未充分利用已编码的码流信息,因此转码效率很低。目前,国内外很多学者开展了许多快速转码研究工作。Wang等人[7]利用AVS的帧内预测模式预测H.264/A VC中的帧内预测模式,跳过H.264/A VC帧内预测模式过程以降低编码复杂度。Shang等人[8]将AVS标准中帧间编码宏块的分割模式信息直接映射到H.264/AVC编码过程中每个宏块的分割模式,从而大幅度提升了转码速度。Wang等人[9]利用AVS解码过程中的模式和运动矢量实现快速高效的转码。这些方法很好地利用了AVS码流中的一些信息来加速转码,但是没有结合编码H.264/AVC码率后的信息进一步提高转码后视频质量,因此仍有进一步提升的空间。此外,有些研究工作在视频转码中引入了机器学习的理论,Gerardo等人[10]假设H.264/AVC的宏块编码模式决定过程与MPEG-2中运动补偿残差的分布具有线性关系,利用MPEG-2运动补偿残差的分布与H.264/AVC宏块编码模式之间的相关性,利用机器学习的方法加速转码过程。这种方法的缺陷是在转码过程中会增加训练时间,在一定程度上会增加转码的复杂度。

本文充分利用了AVS码流中的各种码流信息,同时为解决机器学习算法在转码过程中需要耗费大量训练时间的问题,提出了一种基于改进型机器学习的AVS到H.264/AVC快速转码方法,旨在保证H.264/AVC压缩效率的前提下降低转码的复杂度。

1 AVS到H.264/AVC转码分析及动机

H.264/AVC中每个宏块(Macro Block,MB)编码会遍历宏块分割模式16×16、16×8、8×16和8×8,以及亚宏块分割模式8×8、8×4、4×8和4×4,这两种分割模式分别如图1a和图1b所示。该方法自适应地根据视频内容选择合适的分割模式,从而获得较好的编码性能,但是一个宏块需要重复编码8次,因此复杂度非常高。AVS为了在尽量保证视频质量的前提下降低编码过程的复杂度,每个宏块只采用了16×16、16×8、8×16和8×8四种分割模式。

为了探索AVS和H.264/AVC模式之间的相关性,本文测试了4种情况下模式的命中率,命中率表示事件A中的像素数目与事件B中像素数目的比值,并做了如下规定:

1) AVS码流中某宏块解码得出的模式为16×16分割模式,且H.264/AVC最终编码使用的分割模式也为16×16,该事件记为A;

2) AVS码流中某宏块解码得出的模式为16×8分割模式,且H.264/AVC最终编码使用的分割模式也为16×8,该事件记为B;

3) AVS码流中某宏块解码得出的模式为8×16分割模式,且H.264/AVC最终编码使用的分割模式也为8×16,该事件记为C;

4) AVS码流中某宏块解码得出的模式为8×8分割模式,且H.264/AVC最终编码使用的分割模式也为8×8或者8×4、4×8、4×4,该事件记为D。为了验证上述4个事件的命中率,本文测试了Party Scene、Book Arrival和Johnny3个序列分别在量化参数(Quantization Parameter,QP)为28和32两种情况下的命中率,具体测试结果如图2所示。

从图2可以发现,事件A、B、C和D的命中率一般都小于60%,只有Book Arrival和Johnny两个序列事件A的命中率在80%～85%之间。上述实验结果说明AVS的分割模式和H.264/AVC的分割模式并不是一一对应关系,尽管可以使用这种分割模式映射的方式加速转码过程,但是这会造成编码效率降低。传统的方法是先解码AVS码流,然后再使用H.264/AVC编码器编码,尽管该方法编码性能好,但是编码复杂度高,不适合实时性要求高的场合。

2 基于改进KNN算法的快速转码方法

为了降低AVS转码H.264/AVC过程的复杂度,同时保持较好的转码性能,本文提出了一种基于改进的K最邻近结点算法(K-Nearest Neighbor Algorithm,KNN)[11]的快速AVS到H.264/A VC转码方法。所提出的方法包括两个部分,分别为统计阶段和转码阶段。在统计阶段,提取了统计帧的AVS码流中编码块的分割模式及相应的运动矢量信息作为特征值,然后编码帧的待编码块编码时根据相同特征值在统计帧中寻找特征最匹配的M个模式,由于M个模式中可能存在重复,因此将M个模式中不重复的模式结合AVS码流中的分割模式一起执行率失真优化(Rate Distortion Optimization,RDO)[12]过程,从而加速转码过程。

为了提高特征的有效性,本文将待转码帧分为统计帧和快速编码帧两类。选择N帧为一个编码组,且N帧中前L帧为统计帧,其余N-L帧为快速转码帧。统计帧不进行快速转码,先使用传统的AVS解码器解码码流再使用H.264/AVC编码器编码,在该过程中提取宏块编码采用分割模式对应的特征数据,该过程对应于图3中的统计阶段。快速编码帧使用本文提出算法快速转码,首先使用AVS解码码流中的数据得到特征数据,然后根据该特征数据在统计帧中的特征数据中利用KNN方法寻找M个最接近的特征数据,并将其对应的统计帧中的分割模式和AVS码流中的分割模式一起构成备选模式列表,然后该列表中每个模式执行RDO,从而避免全遍历方式选择最佳的分割模式。图3是上述所述方法工作原理示意图。

2.1 特征提取

根据编码原理可以,若某个宏块运动越剧烈,则很可能使用较小的块编码,若某个宏块运动越缓慢,则很可能使用较大的块编码。而宏块的运动矢量(Motion Vector,MV)反映了当前块的运动情况,因此,本文探索了MV与转码中最终使用的分割模式之间的相关性。本文选取AVS码流中某个宏块分为16×16、2个16×8和2个8×16分割模式时对应8×8块之间的方差作为5个特征,并构成一维矢量F。

式中:Vm,16×16表示16×16内4个8×8块MV之间的方差;Um,16×8表示16×8分割中上方块内2个8×8块MV之间的方差;Dm,16×8表示16×8分割中下方块内2个8×8块MV之间的方差;Lm,8×16表示8×16分割中左方块内2个8×8块MV之间的方差;Rm,8×16表示8×16分割中右方块内2个8×8块MV之间的方差。

2.2 特征提取改进KNN算法的快速AVS到H.264/AVC转码

本文提出方法根据AVS的码流分割模式信息结合改进的KNN方法确定可能成为最佳宏块分割模式的列表,取代原有所有模式全遍历的方式,然后每种模式执行RDO,选择率失真代价(Rate Distortion Cost,RDCost)最小的模式作为最佳宏块分割模式。传统的KNN算法根据训练样本集中与新样本距离最近的K个样本,并根据这K个样本所属类别判断新样本的属性。本文中根据KNN算法选择K个样本后,并不是直接判断其属性,而且选择K个样本对应的所有属性。

本文提出的基于改进KNN算法的快速转码方法的具体方法如下:

步骤1,从AVS码流解码一个宏块,判断当前帧的标号frame＿poc是否为0,若是转向步骤4,否则转向步骤2。

步骤2,判断当前帧的标号frame＿poc是否能被N整除,若是转向步骤6,否则转向步骤3。

步骤3,构建特征矢量Vector2,然后在前面frame＿poc能被N整除帧中所有的Vectorl中利用KNN算法选择M个与Vector2最接近的Vectorl,并将M个Vectorl对应的不重复模式构建最可能成为最佳宏块分割模式的分割模式列表,具体该构建方法如下,第一个模式为AVS解码信息中当前块编码使用的分割模式,随后的所有模式根据在M个模式中占的比例由大到小排列。

步骤4,若当前帧标号frame＿poc能被N整除或者等于0,则遍历H.264/AVC所有发宏块分割模式编码一个宏块,否则使用粗略分割模式列表中的模式编码一个宏块,选择当前宏块最佳的分割模式并转向步骤5。

步骤5,判断当前宏块是否为最后一个宏块,若是,则结束,否则转向步骤1。

步骤6,构建跟Vector2具有相同属性的特征矢量Vector1,并保存,然后转向步骤4。

3实验结果与分析

为了验证本文提出算法的有效性,将它与传统级联式转码器以及文献[8]中的算法进行对比实验。使用的AVS参考软件为rm52j＿r1,H.264/AVC参考软件为JM18,使用了6个不同分辨率不同场景的视频测试序列,分别是PartyScene,RaceHorses,Johnny,FourPeople,BookArrival和Leavelaptop。在仿真实验中,图像编码格式为IPPP,帧率为30 f/s(帧/秒),测试每个序列100帧。rm52j＿r1参考软件的量化参数为QP=28,最大搜索范围为16,帧率为30 f/s,参考帧为2帧。M选取不同值时的测试结果如图4所示。最终的实验结果使用节省时间(Time Saving,TS)和码率增加(DBR)两个指标衡量算法性能,具体的计算如下

式中:Tori表示传统级联转码器所花费的时间;Tφ表示对比方法(提出的方法和文献[8]方法)所花费的时间。

式中:Rori表示传统级联转码器的码率;Rφ表示对比方法(提出的方法和文献[8]方法)的码率。

从图4a和图4b可以发现,针对同一M,不同序列节省时间量和比特率增加量差别很大,这是由于不同序列具有不同的属性。针对同一序列不同M的情况下,当M小于等于5时,随着M值的增大,预测得到的备选模式列表中的模式数目增多,造成编码复杂度增大,编码效率也随着增大。当M大于等于10时,尽管M值逐渐增大,但是备选模式列表中得到的不重复模式数目并没有显著增加,导致节省时间量和比特率增加量基本不变。

综合考虑分类精度和转码复杂度,本文中N取10,M取值为5。在H.264/AVC编码中,JM18参考软件的量化参数(Quantization Parameter,QP)分别为24、28、32、36,最大搜索范围为16,帧率为30 f/s,参考帧为2帧,本文提出方法与级联方式转码器的对比结果以及文献[8]方法与级联方式转码器的对比结果如表1所示。

由表1实验结果可以得出,本文提出算法与传统级联转码器算法相比,在比特率平均增加4.89%的情况下,转码时间降低了约56%,文献[8]方法与传统级联转码器算法相比,在比特率平均增加18.23%的情况下,转码时间降低了约77%。尽管文献[8]方法的方法能得到更好地降低转码过程的复杂度,但是其码率大幅增长,使得编码效率显著降低。虽然本文提出算法对转码过程复杂度的优化程度没有文献[8]方法好,但是并未引起码率显著增加。并且本文中M是可以选择的,当M更小时,将会导致转码过程的复杂度降低更多。

4 结论

由于视频从AVS标准转码成H.264/AVC标准具有很大的应用前景,目前研究主要通过AVS和H.264/AVC之间模式映射的关系减少转码复杂度,但是这两种标准采用技术不同会导致宏块采用的分割模式不同,这会降低转码后视频的压缩效率。为了解决上述问题,本文提出一种粗略确定宏块分割模式的快速转码方法。该方法利用AVS的码流中宏块分割模式,并结合改进的KNN方法确定最优可能成为最佳宏块分割模式的列表,从而避免遍历所有分割模式。大量的实验结果证明,与传统级联方式的转码方法相比,本文提出的算法在比特率增加4.89%的情况下,转码时间降低了约56%。

尽管本文提出方法可以降低转码过程的复杂度,但是由于考虑的因素较少,导致模式预测并不十分准确,还可以通过考虑运动矢量大小、待编码块复杂度等因素进一步提高模式预测精度。

摘要：尽管音视频编码标准(Audio and Video Coding Standdard,AVS)的编码性能可以与H.264相媲美,但是H.264的应用范围更加广泛,因此视频由AVS标准转码成H.264标准具有很大的应用前景。目前,主流的转码方法是将AVS的分块模式与H.264的分块模式映射的方式降低转码复杂度,但是技术之间的差异导致这两种标准之间的分块模式并不是一一映射的关系,因此会导致编码效率大幅度降低。提出一种基于改进KNN(K最邻近节点)算法的AVS到H.264/AVC快速转码方法。充分利用了AVS码流中的各种信息,通过改进的KNN算法建立了中间信息和H.264分块模式之间的映射模型。根据AVS中运动矢量信息的差异自适应确定H.264可能的分块模式,实验结果表明上述问题得到有效解决,该算法在保证H.264编码效率的前提下大幅降低了转码复杂度。

关键词：音视频编码标准,H.264/AVC,快速转码,K最邻近结点算法

参考文献

[1]TANG Q.NASIOPOULOS P.Efficient motion re-estimation with rate-distortion optimization for MPEG—2 to H.264/AVC transcoding[J].IEEE Trans.Circuits Syst.Video Technol.,2010,20(2):262-274.

[2]AHMAD I,WEI X H,SUN Y,et al.Video transcoding:an overview of various techniques and research issues[J].IEEE Trans.Circuits Syst.Video Technol.,2005,7(5):793-804.

[3]WIEGAND T,SULLIVAN G J,BJONTEGAARD G,et al.Overview of the H.264/AVC video coding standard[J].IEEE Trans.Circuits Syst.Video Technol.,2003,13(7):560-576.

[4]FAN L,MA S W,WU F.Overview of AVS video standard[C]//Proc.IEEE International Conference on Multimedia and Expo.[S.1.]:IEEE Press,2004:423-426.

[5]SULLIVAN G J,OHM J R.HAN W J,et al.Overview of the High Efficiency Video Coding(HEVC)standard[J].IEEE Trans.Circuits Syst.Video Technol.,2012,22(7):1649-1668.

[6]YU L,YI F.DONG J,et al.Overview of AVS-video:tools,performance and complexity[C]//Proc.IEEE visual Communication and Image Processing.Beijing:IEEE Press,2005:12-15.

[7]WANG Z H.GAO W.ZHAO D B,et al.A fast intra mode decision algorithm for AVS to H.264 transcoding[C]//Proc.IEEE International Conference on Multimedia&Expe.Toronto:IEEE Press,2006:61-64.

[8]尚凯,张万绪.AVS-H.264视频转码快速算法[J].计算机工程,2010,36(12):234-244.

[9]WANG Z H,JI X Y,GAO W,et al.Effective algorithms for fast transcoding of AVS to H.264/AVC in the spatial domain[J].Multimedia Tools and Applications,2007,35(2):175-202.

[10]FERNANDEZ G,CUENCA P,BARBOSA L O,et al.Very low complexity MPEG-2 to H.264 transcoding using machine learning[C]//Proc.14th Annual ACM International Conference on Multimedia.Santa Barbara:ACM Press,2006:931-940.

[11]ZHANG B.Reliable classification of vehicle types based on cascade classifier ensembles[J].IEEE Trans.Intelligent Transportation Systems,2013,14(1):322-332.

改进的KNN算法篇4

关键词：特征加权,K最近邻,文本分类,特征选取

1 引言

KNN文本分类算法的基本思想是根据传统的向量空间模型,文本内容被形式化为特征空间中的加权特征向量,即D=D(T1,W1;T2,W2;…;Tn,Wn)[1]。对于一个测试文本,计算其与训练样本集中每个文本的相似度,找出K个最相似的文本,根据加权距离和判断测试文本所属的类别。KNN算法是一种优秀的分类算法,但KNN算法同样存在着不足:一是对于高维文本向量样本规模较大时,算法的时间和空间复杂度较高,其时间复杂度为O(n*m),n为VSM空间特征维数,m为样本集大小;二是当新待分类样本到来时,每次都要计算其与所有训练样本的距离(或相似度),这就大大降低了算法的效率[2]。

针对传统的KNN文本分类算法的不足,出现了很多改进的KNN算法,目前主要通过两种途径来减小KNN算法的计算量。一种是通过对高维文本向量进行降维处理,采用的方法主要有:基于潜在语义分析的方法(LSA)[3]、基于特征向量聚合的方法[4]、基于特征选择的方法等[5]。另一种加快KNN算法分类速度的改进办法就是通过使用小样本库代替原来的大样本库进行分类。这类方法一般是在原来的训练样本库中选取一些代表样本作为新的训练样本,或删除除原来的训练样本库中的某些样本,将剩下的样本作为新的训练样本库,从而达到减小训练样本库的目的。这种途径最主要的方法有Hart的Condensing算法、WilSon的Editing算法和H.V.Jagadish的iDistance算法。

KNN分类算法以及改进的KNN分类算法大多数是建立在样本选择的基础上,即以损失分类精度换取分类速度。本文提出一种基于特征加权的KNN改进算法(KNN-FW),该算法考虑各维特征对模式分类贡献的不同,给不同的特征赋予不同的权值,提高重要特征的作用,从而提高了算法的分类精度。

2 基于特征加权的KNN文本分类算法

2.1 基本思想

KNN算法认为各维特征对分类的贡献是相同的,而事实上,构成样本特征矢量的各维特征来自不同的样本,存在量纲差异,精度及可靠性也可能不同,而且所选择的特征集也未必适合于模式的分类。鉴于此,将探讨一种改进的K最近邻算法,该算法考虑各维特征对模式分类的不同贡献,以便获得更有效的分类效果。

设一个给定的测试样本为t,特征为f,定义在特征f上的最近邻算法为KBag(f,t,k),该函数计算测试样本t在特征f权值上最近的K个邻居。然后对每一个类别进行K次投票,因此每一特征维度上就有K次的投票机会。测试样本的类别由这些特征上的K次投票结果综合决定。

2.2 特征选取

构成文本的词汇,数量是相当大的,因此表示文本的向量空间的维数也相当大,可以达到几万维,因此需要进行维数压缩的工作。目前对文档特征所采用的特征子集选取算法一般是构造一个评价函数,对特征集中的每一个特征进行独立的评估,这样每个特征都获得一个评估分,然后对所有的特征按照评估分的大小排序,选取预定数目的最佳特征作为结果的特征子集。一般采用的评估函数有信息增益[6]、互信息[7]、期望交叉熵[8]、χ2统计[9]、文本证据权、文档频次[10]和几率比等。针对论文抄袭检测问题,实验表明采用信息增益评估函数效果较好[11]。

权重的计算采用TFIDF公式,其中TF是特征项在文本中的绝对频率,而IDF表示特征项在文本中的文本内频数。不过纯粹选取权重值最大的前N个特征词汇作为训练样本特征库的方法,往往存在训练样本“不可描述”的问题,即部分训练文本不包含任何选取出的特征项。改进方法是在每个训练类别中抽取权重值最大的一定数量的词汇共同构成训练样本特征库,这样调整后训练文本特征库对于每个训练类别文档都能实现充分描述。每个训练类别抽取特征词的数量可以根据需要的总体特征维数决定。特征数也不是越多越好,有时特征数太多反而会影响分类的精度。在实验时发现特征数在1000~1500时,效果较好,这时对于每个训练类别抽取权重值最大的前200个词汇,稍加筛选共同构成训练样本特征库。

2.3 特征权值的确定

采用ReliefF算法来确定特征的权值。基本的Relief算法[12]是Kira和Rendell在1992年提出的,仅适用于训练样本是两类的情况。1994年Kononemko[13]扩展了Relief算法,得到ReliefF算法,RelliefF可以解决多类样本分类问题。

设X=邀x1,x2,…,xn妖是待分类的对象全体,其中xi=邀xi1,xi2,…,xiN妖表示第i个样本的N个特征值。对于任意的一个样本xi,首先找出R个与xi同类的最近邻样本hj,j=1,2,…,R,然后在每一个与xi不同类的子集中找出R个最近邻的样本mij,j=1,2,…R,l≠class(xj)设diff_hit是N×1的矩阵,表示hj与xi在特征上的差异,对于特征权重,表示为:

设diff_miss是N×1的矩阵,表示mij与xi在特征上的差异。对于特征权重,表示为:

P(l)为第l类出现的概率,可以用第l类的样本数比上数据集中的总数。若用λ表示各维特征的权值,λ是N×1的矩阵,则ReliefF算法中λ由下式更新:

如此重复若干次,就可以得到特征集中每一个特征的权值。

2.4 KNNFW文本分类算法流程

KNNFW文本分类算法流程和传统KNN文本分类方法流程差不多,主要的区别在于特征词的权重不同以及分类算法不同。KNNFW文本分类算法流程如图1所示。

文本的预处理包括分词和去除停用词等,预处理后在初步选取特征词的基础上进一步进行特征加权计算,根据加权的结果进行训练和分类,其中具体分类算法的实现如下:

输入:t测试样本,k最近邻个数。

输出:测试样本的类别。

(1)初始化阶段,对于每一个类别c设置投票结果为零,vote[c]=0。

(2)对于每一个特征f,计算每一个特征的k个邻居,Bag=kBag(f,t,k)。

(3)对于每一个类别c,分别计算它们的投票结果:

(4)最后判断各类投票结果vote[c]中的最大值,将最大值所对应类别作为测试样本t的类别ct。

其中count(c,Bag)函数计算特征f的k个邻居中类别为c的个数,W[f]为特征f的权值。

3 实验结果与分析

3.1 实验结果

为了验证算法的有效性和正确性,选取了2287个文本文件,共14个类别,包括:计算机、医药、经济、环境、军事、艺术、体育、教育、交通、政治、建筑、金融、宗教和电子商务等,作为训练集,并从中选取一部分作为测试集。训练样本、测试样本的分布情况如表1。

由于样本数和类别都不多,特征词取1500,特征初步选取策略采用信息增益评估函数,采用ReliefF算法来进一步确定特征的权值,K值取35。KNN和基于KNNFW两种文本分类法对比实验结果如表2。

3.2 基本结论

由以上实验结果可以看出,传统KNN文本分类法查准率和查全率都较低;而采用基于特征加权的KNN文本分类算法大大提高了查准率和查全率。同时,在每个训练类别中抽取权重值最大的一定数量的词汇共同构成训练样本特征库,可以避免由于训练样本分布不均匀而影响分类效果。另外,特征词的数量和K值的大小对实验结果有一定影响,但由于没有固定计算公式,因此只有通过实验确定较为合适的特征词数与K值。

4 结束语

KNN价格预测模型的研究与改进篇5

K-最近邻算法 (k-nearest neighbors, KNN) 出现在20世纪50年代早期, 是一个优秀的分类算法。在价格预测模型中主要利用它进行数值预测, 价格是一种典型的数值型数据。

利用KNN算法进行价格预测的基本原理是:接收一个待预测的新数据项, 然后将其与一组样本集中的数据项进行比较, 从中找出与待预测数据项最为接近的K个数据项, 并对其求均值以得到最终的预测结果。

在整个预测模型中首先从待预测商品上提取特征, 将这些特征转换到向量空间, 然后利用KNN算法进行预测, 最后得到预测价格, 如图1所示。

KNN价格预测模型由三部分组成:特征提取、搜索最近邻居、产生预测结果。

1.1 商品特征提取

价格预测中的关键工作是确定哪些商品特征是重要的, 以及如何将它们组合在一起。比如, 在笔记本电脑价格中, 内存容量对价格的影响显然要比颜色大很多。还有一些商品的特征对价格没有影响, 那么这些特征忽略不计。

本文采用向量空间模型 (Vector Space Model, VSM) , 将商品转化为由若干个特征组成的空间形式 (t1, t2, ..., tk) , tk就是本文上述的商品特征信息。确定了特征之后, 再将各个特征在商品上被赋予的数值填充到向量空间中。

最终一个商品dj的数学表示形式为:wj (w1j, w2j, ..., wkj, ..., w│T│j) , 其中wkj表示特征tk在商品dj上的值, │T│表示特征向量的维数。以笔记本电脑为例, 其向量空间模型如表1所示。

表1中CPU特征的取值单位是GHz, 二级Cache特征的取值单位是MB, 内存特征的取值单位是MB, 硬盘特征的取值单位是GB, OS特征的取值1-5分别表示DOS, Linux, XP, Vista, Win7。

1.2 搜索最近邻居

当商品表示为特征向量后, 两件商品之间的相似程度可以通过空间中这两个向量的几何关系来度量。设有两个特征向量X= (x1, x2, ..., x│T│) 和Y= (y1, y2, ..., y│T│) , 则其相似度采用欧几里德距离来表示。如公式 (1) 所示:

1.3 产生预测结果

产生预测的基本过程是:对待预测的特征向量与数据集中的所有特征向量, 调用公式 (1) , 并将结果排序, 将距离最近的结果排在前端, 然后对其中的前K项结果的价格求平均值, 这个值就是最终的预测价格。

上述产生预测的基本过程有一个不足是:在产生预测结果时, K个最近邻居是被同等对待的, 即对K个最近邻求平均值。实际上, 距离较近的邻居对预测结果上应该有更高的贡献值。一种补偿办法是根据距离的远近, 为每个近邻赋予相应的权重, 即较近的近邻比较远的近邻权重值大。

将距离转换为权重的方法有很多, 但是在选择转换方法时需要注意:较近的近邻应被赋予较大的权重, 随着距离的增加, 稍远的近邻的权重不能衰减过快, 还需保证权重值不能为0。

利用高斯函数将距离转换为权重, 该函数在距离为0的时候所得的权重值为1, 并且权重值会随着距离的增加而减少, 但始终不会跌至0, 如图2所示。

加权KNN算法与传统KNN算法在执行过程上大致相同, 最重要的区别在于:加权KNN并不是对K个最近邻简单地求平均值, 而是通过每个最近邻乘以相应权重, 然后将所得到的结果累加, 并除以所有权重值的和, 如公式2所示。

公式 (2) 中P表示最终的预测结果。

2 KNN价格预测模型的不足

如果商品所有特征都在同一值域范围内, 则利用公式 (2) 计算出的距离值是有意义的。但是实际情况并没有这么理想。

表2中CPU特征的取值单位是GHz, 二级Cache特征的取值单位是MB, 内存特征的取值单位是MB, 硬盘特征的取值单位是GB, OS特征的取值1-5分别表示DOS, Linux, XP, Vista, Win7。

如表2所示, 商品特征的值域有的在0-10之间, 有的在100-400之间, 有的甚至达到了4000以上, 显然商品所有特征都不在同一值域, 如图3所示。把这样的数据送入KNN价格预测模型, 观察预测结果发现:不在同一值域的商品特征对距离计算产生的影响是显著的, 较大值域的特征 (如内存、硬盘) 在计算距离的过程中使得预测模型忽略了其它小值域的特征 (如CPU、二级Cache) 。事实上, 这些被忽略的特征对价格的决定有着至关重要的作用, 这样的情况降低了模型的预测准确度。

另外, 假如在商品中引入颜色这一特征, 并且其余的商品特征都一样, 显然颜色对价格的影响是微小的, 但是在价格预测模型计算距离时, 算法会认为它们是不同的, 这也会导致模型的预测准确度大大降低。

3 改进的KNN价格预测模型

针对KNN价格预测模型的不足, 本文提出特征缩放法对商品特征值进行归一化处理, 使所有特征都在一个值域范围内, 从而提高KNN价格模型的预测准确度。

特征缩放法是将每个维上的特征值乘以一个该维度上的常数, 例如在内存特征值上乘以1/4000。对那些与价格预测无紧密关系的特征值使其缩减到0, 如图4所示。

改进后的KNN预测模型首先从待预测商品上提取特征, 其次运用特征缩放法将这些特征约束到同一值域, 并转换到向量空间, 然后利用加权KNN算法进行预测, 最后得到预测价格, 如图5所示。

4 实验数据和实验结果

本文用C#实现了改进的KNN价格预测系统, 样本数据是自行收集一年, 共计6大厂商生产的10多个品牌的笔记本电脑销售数据。分别在未改进的KNN价格预测模型和改进的价格预测模型上进行实验, 预测对象是某厂商近期发布的但还未上市的4款笔记本电脑。当厂商的这4款笔记本上市后, 将预测结果与实际的市场价进行对比分析, 实验分析结果如表3所示。

表3中, 准确度表示预测价格与实际市场价格的接近程度, 误差率表示在一定K值下, 算法把不相似商品误作为最近邻的概率。

5 结束语

本文对KNN价格预测模型进行了分析研究, 总结其存在的不足, 并提出了一种改进的KNN价格预测模型, 有效地解决了商品不同特征在值域不同时的价格预测问题。实验表明, 本文对KNN价格预测模型的改进是有益的, 提高了其预测的准确度。

参考文献

[1]BENDER W, GRUHLD, MORIMOTO N, et al.Technique for DataHiding[J].IBM Systems Journal, 1996, 35 (3/4) :313-335.

[2]IWERKS GS, SAMET H, SMITH K.Continuous k-nearest NeighborQueries For Continuously Moving Points With Updates[C]//Proc.of VLDB.2003.

[3]徐燕, 李锦涛, 王斌, 等.基于区分类别能力的高性能特征选择方法[J].软件学报, 2008 (1) .

[4]陆微微, 刘晶.一种提高K-近邻算法效率的新算法[J].计算机工程与应用, 2008 (4) .

改进的KNN算法篇6

由于k NN算法[1]思想简单、分类效果好, 在文本分类中有着广泛的应用。使用k NN算法时, 首先要计算测试文本与所有训练文本的相似度, 根据文本间的相似度, 寻找出测试文本的k个近邻文本。因此, k NN算法存在缺陷:处理相似性计算的计算开销巨大, 尤其当特征空间的维数特别高、训练集非常大的时候。

投影寻踪 (projeetion pursuit, PP) [2]是一种探索性数据分析方法。它通过某种组合, 将高维数据投影到低维 (一至三维) 子空间上, 并通过极大 (小) 化某个投影指标, 寻找出能反映原高维数据结构或特征的投影, 在低维空间上对数据结构进行分析, 以达到研究和分析高维数据的目的。

以往投影寻踪在文本分类的应用中, 主要是通过数据分析的方法对文本特征进行降维处理。本文提出的优化策略在特征降维的基础上, 基于一个简单的原理:空间中邻近的点映射到某一方向上也是邻近的。通过投影的方法对原始训练集进行缩减, 从而大大降低了计算开销。从两方面着手对k NN文本分类算法进行加速优化。

首先, 通过遗传算法挑选出若干个最优的投影方向;其次, 把文本投影到各一维的投影方向上, 寻找出各方向上测试文本可能的近邻文本, 由各方向所有可能的近邻文本组成最终的查询集, 从而缩减训练集的规模;最后, 在低维的投影空间中计算测试文本的k近邻, 从而达到特征降维的目的。实验表明, 通过选择适当的参数, 优化后的k NN算法在保证分类精度的同时, 有效提高了算法的效率。

1 相关研究

如何降低k NN算法的计算复杂度, 目前已经提出了众多改进方法, 这些方法可以归为以下三类:

1.1 基于特征降维的改进

为了清理噪声数据, 降低计算开销, 需要对样本进行特征降维, 特征降维方法分为特征选择和特征抽取。特征选择的关键是选择特征评估函数, 目前比较常用的特征评估函数包括:文档频率 (DF) 、互信息 (MI) 、信息增益 (IG) 、统计 (CHI) 等。Gupta等[3]使用粗糙集方法为文本分类进行特征选择;宋枫溪等[4]提出了低损降维, 其降维效果与互信息、χ2统计相当, 并优于文档频率。

常用的特征抽取方法包括:主成份分析 (PCA) 、Fishe线性判别分析、潜在语义分析 (LSA) 和投影寻踪 (PP) 等。钟将等[5]使用潜在语义分析方法对文本特征空间进行降维处理。廖海波等[6]通过投影寻踪的方法, 把高维空间的数据投影到低维空间, 进行特征维数约简。

1.2 基于缩减训练样本的改进。

较小的训练集意味着更少的相似度计算开销。优化方法分为两类:一是对训练文本进行剪裁以减小训练集规模;二是在原训练集中选取或生成一些代表样本, 代替原训练样本。李荣陆等[7]针对类偏斜问题提出基于密度的剪裁方法。周勇等[8]提出一种基于聚类中心改进的k NN算法, 通过聚类算法把训练集分簇, 计算每个簇的中心点, 代表本簇的训练样本。Jiang J Y[9]通过模糊相似度计算把样本分簇, 寻找测试样本的k近邻时, 只在与其隶属度大于某一阈值的簇中进行计算。

1.3 基于k近邻搜索方法的改进。

此类方法通过加快寻找k近邻的速度来对k NN算法进行优化。Guo等[10]通过在训练集上构建多个类似索引结构的k NN模型簇, 提高算法效率。邓箴等[11]利用模拟退火改进k NN算法中查找k近邻的过程并取得良好效果。

空间中邻近的点映射到某个方向上也是邻近的。因此, 当寻找某一测试样本点的k近邻点时, 大多数无关的点就可以被忽略掉, 这大大降低了计算开销。正是利用这一点对传统k NN算法进行优化。

2 基于投影寻踪的k NN算法的加速策略

2.1 k NN文本分类算法简介

k NN算法对一篇测试文本dx进行分类的过程是:首先计算dx与训练文本集中每个文本的相似度, 相似度一般采用余弦相似度度量, 依据相似度找到最相似的k个训练文本, 把这k个文本的类别作为dx的候选类别;然后把相似度作为k近邻文本所属类别的权重, 将各类中近邻文本的类权重之和作为该类别和测试文本的相似度, 再把测试文本dx归到权重最大的类别中。

测试文本dx和训练文本di的相似度计算公式为

式 (1) 中, M为特征向量维数, w为特征权重。

测试文本dx和类cj的权重计算公式为

式 (2) 中, y (di, cj) 是类别属性函数, 当di属于cj时, y (di, cj) =1;当di不属于cj时, y (di, cj) =0。

分类决策函数为

2.2 投影寻踪及其算法描述

投影寻踪最早是由Kruskal于20世纪70年代初提出的, 是用来分析和处理高维观测数据, 尤其是非正态非线性高维数据的一种新兴统计方法。投影寻踪模型中三个基本的概念:线性投影、投影指标和最优化投影方向。

2.2.1 线性投影

线性投影是对高维数据进行投影降维的手段。利用线性投影将M维向量空间中的数据映射到m维投影空间后, 在投影空间中, 数据点的个数不变, 但维数由M维降低为m维, 投影寻踪方法正是利用线性投影研究数据在低维空间的散布特征, 从而找到其在高维空间的结构特征。

式 (4) 中, d代表文本特征向量, a代表投影的方向向量。

2.2.2 投影指标

投影指标是用于衡量投影到低维空间上的数据是否有意义的目标函数。

随机变量X在投影方向A上的投影指标表示为Q (FA) , 实际上Q是一个m维空间上的泛函, 将空间函数转变成某一确定的数值, 也可表示称Q (AX) 。在使用优化算法优化投影指标时, 投影指标即为目标函数, 其具体形式视不同需求而定。

在文本分类中, 希望:局部上, 投影点要密集, 凝聚成若干个类;整体上, 投影点要散开, 类与类之间要尽可能的分离。

本文参照文献[12]构造投影指标如下

以各类一维投影数据均值作为类中心的度量, 以标准差作为类内离差的度量。求得max Q (Z) , 使得投影点局部密集, 整体分散。

式 (6) 中, E (Z (i) ) 是第i (i=1, 2) 类投影的均值。

式 (7) 中, Zj (i) 是第i类 (i=1, 2) 对应文本的投影值, n1+n2=n, n为训练文本数。

需要注意的是:训练是针对单个类别进行的, 也就是说, 把属于该类的文本看成正例, 其他文本全部看作为负例, 为各类计算出一个最优的投影方向。

2.2.3 投影方向

原始空间中有无数的单位向量, 但并不是所有方向都适合作为投影方向。我们应该选择那些能够有效代表原始空间的方向, 尽可能的保留原始信息。

2.3 分类工作流程

不同的投影方向反映着不同的数据结构特征, 所谓最佳投影方向是能够最大可能体现高维数据的某类特征结构的方向, 从信息论角度而言, 最佳投影方向是对数据信息利用最充分, 信息损失量最小的方向, 优化投影方向归根到底是找出某种意义下好的投影指标。

算法1确定最优投影方向

根据定义的投影指标Q (Z) , 采用遗传算法优化投影方向a, 算法步骤如下:

(1) M维原向量空间中, 随机选出m组 (m为训练集中类别数) 初始投影方向aj (1≤j≤m) , aj= (aj1, aj2, …, aj M) , ‖aj‖=1。

(2) 根据公式 (4) 分别计算出m组投影方向上n个文本的投影值Zi (i=1, 2, …, n) 。

(3) 根据公式 (6) 计算中心离差B (Z) , 公式 (7) 计算类内离差D (Z) , 根据公式 (5) 分别计算m组投影方向对应的投影指标Q (Z) 。

(4) 将各投影方向按照其对应的投影指标Q (Z) 升序排列, 选取前m/2组投影方向进行交叉操作, 前0.01m组投影方向进行变异操作。得到m+m/2+0.01m组投影方向, 计算新产生投影方向的投影指标, 并按升序排序。

(5) 取步骤 (4) 中得出的前m组投影方向, 从骤 (2) 开始循环计算。

(6) 直到投影指标不再增加时, 算法收敛, 从中选出投影指标最大的方向即为最佳投影方向。

得出最优投影方向后, 把各文本向其作投影, 在各一维投影方向上计算测试文本可能的近邻, 并最终得到缩减后的查询集。优化的k NN算法由算法2给出。

算法2优化的k NN分类算法

(1) 使用算法1取得最优的m个投影方向。

(2) 训练文本di (1≤i≤n) 向m个最优投影方向分别作投影, 并根据公式 (1) 计算文本di (1≤i≤n) 在各最优投影方向上的投影值Z1 (i) , Z2 (i) , …, Zm (i) , 其对应在投影空间S中可表示成 (Z1 (i) , Z2 (i) , …, Zm (i) ) 。

(3) 为每个投影方向建立一个索引表。索引表中的数据按照文本在此方向上的投影值升序排列。

(4) 同理, 计算测试文本dx在各最优投影方向上投影值。

(5) 查找各投影方向的索引表, 使用二分查找算法, 找出测试文本dx对应各方向上k'个近邻。例如第j (1≤j≤m) 个方向上k’近邻Lj={dj1, dj2, …, djk’}。总共m个投影方向, 所以测试文本dx所有可能近邻集合为L,

(6) 在查询集L上执行k NN分类算法。首先, 在投影空间S中寻找测试文本dx的k个近邻。其次, 在原向量空间中根据找到的k个近邻的类别, 使用式 (2) 、式 (3) 判定dx的类别。

3 实验结果与分析

实验采用中科院ICTCLAS分词系统对文本进行分词处理, 采用χ2特征选择选出500个特征词, 采用优化后的k NN分类器对测试文本集进行分类。

3.1 数据集及评价指标

采用复旦大学中文语料库作为实验数据集。语料库包含9个类别, 如表1所示。

对文本分类效果进行评估标准有查准率, 查全率。两者反映了分类质量的两个不同方面。

F1值是考察查准率和召回率的综合指标;

Macro-F1表示m个类别F1值得平均值。

3.2 参数设置及算法复杂度分析

为了实验描述方便, 经本文优化后的算法为PPk NN算法, 该算法中k'的选取尤为关键, k'选取的过小会造成近邻点的漏选, k'选取的过大会使得分类时间过长, 当k'增加到一定程度时, PPk NN算法的精度与k NN分类精度相同。图2、图3分别验证了取不同k、k'值时, 算法的Macro-F1值及算法执行时间的变化情况。

由图2可知, k'越大代表原向量空间中越多真正的近邻文本被包含在集合L中, 所以算法的Macro-F1值会随着k'的递增而递增。

与传统k NN算法类似, 算法随着k的递增, Macro-F1会先增加后降低, 而随着k'的增大, 这种变化趋势会越来越缓慢。实验数据显示, 当k'≥60时, PPk NN算法的Macro-F1值近似于传统k NN的Macro-F1值。

设t (x) 表示一组x维的样本相似度计算的时间开销。则传统k NN算法时间复杂度O (k NN) =nt (M) , n表示训练文本数。M表示原向量空间中文本的维度。

改进后PPk NN算法的时间复杂度Ο (PkΝΝ) =mk't (m) +kt (M) , mk'表示m个方向上测试文本的所有可能的近邻数。等式右侧前半部分表示在投影空间中寻找测试样本的mk'个可能近邻所需的时间开销;等式右侧后半部分则表示在原向量空间中, 使用公式 (2) 判定测试文本类别的时间开销。

由于k, m, k'<<n, M, 所以优化后PPk NN算法的时间复杂度要远小于传统k NN算法。

由图3可以看出, 算法执行时间随着k的递增而急剧增加;此外之外算法执行时间还会轻微收到k'的影响。由于t (m) <<t (M) , 所以算法执行时间主要还是依赖于参数k。

3.3 实验对比及分析

实验对比了传统k NN分类算法及两种改进的加速k NN算法与本文提出的优化算法的Macro-F1值和执行时间两项性能指标。两种改进算法分别是:样本裁剪k NN算法[7]和LSI降维k NN算法[5]。样本裁剪k NN算法的加速思想是:对类中心区域高密度文本进行裁剪, 降低区域密度, 从而缩减训练集。LSI降维k NN算法则是通过潜在语义分析的思想对文本进行降维处理。两种改进算法分别代表了两种传统k NN算法的加速策略。

对比实验中, 首先对参数进行了优化设定。样本裁剪k NN算法中参数Min Pts设置为15, Low Pts设置为10。PPk NN算法中, k'设置为30。

由图4可以看出, 传统k NN算法的Macro-F1值最高, 其次为文本算法PPk NN。其它两种改进算法的精度损失要比PPk NN算法大。实验数据显示, k值设置为30时, PPk NN算法的F1值降低约0.7%, 其他两种改进算法分别降低约1.1%和1.6%。

图5显示了四种算法随k值增加, 分类执行时间的变化情况。由图可知, PPk NN算法的加速效果明显高于其他改进算法。当k取值为30时, PPk NN算法与传统k NN算法的加速比达到21.8, 由此可知, 本文提出的优化算法加速效果要明显优于以往的加速算法。

4 结束语

针对传统k NN算法分类效率低下的缺陷, 提出了一种应用投影的方法缩减训练集规模及特征降维处理的优化策略。实验数据显示, 通过选取适当的参数, 本文提出的优化策略可以有效提高k NN算法的分类效率, 并且当数据集规模越大、特征空间维度越高时, 加速效果越优。

PPk NN算法虽然加速效果显著, 但仍存在一些有待完善之处。首先, PPk NN算法通过结合训练集缩减和降维来提高算法效率, 牺牲了一部分分类的精度。其次, PPk NN算法中存在多参数设置问题。如何更好的设置各参数, 使得分类精度与加速效果达到一个最优平衡点是下一步研究的重点问题。

参考文献

改进的KNN算法篇7

关键词：多维度数据,模糊测度,k近邻,证据理论

1 引言

k-近邻(k-nearest neighbor,KNN)算法是一种基于实例的学习分类方法,以其简单、有效和高鲁棒性而被广泛地应用在机器学习与数据挖掘领域[1]。广大学者从不同的方向对KNN算法提出了3类改进[2]:①寻找更加实际的距离函数代替常规的欧氏距离;②搜索更加合理的k值取代指定大小的k值;③应用更加精确的概率估测方法取代简单的投票机制。但是KNN算法假设每个样本属性维度的作用相同, 当多维度样本集合包含有许多不相关维度属性时,样本边界的模糊性会导致集合元素隶属关系的不确定,此时KNN分类学习过程难以取得理想的分类效果。

D-S证据理论(Dempster-Shafer Theory)使用一个问题的概率来推导一个相关问题的概率,能够处理由于知识的不准确引起的不确定性, 是对贝叶斯理论的扩展[3]。与概率推理等相比,D-S证据理论在不确定性的表示和融合方面更为灵活,规则形式直观、简洁,因此在许多领域得到广泛应用[4,5,6,7]。D-S证据理论也存在许多不足, 如非单调性、证据推理组合条件要求组合证据条件独立、证据基本概率指派确定的主观性,D-S证据理论缺点限制了它的使用范围[8]。

模糊测度(Fuzzy Measure,FM)以更广泛的单调性取代概率测度的可加性,更符合人们日常推断活动[9]。模糊测度提供了一个对不确定性特征信息进行描述的框架,对有价值的不确定性信息变量进行量化,以便进行相关期望值的计算,从而提供更多用于模式识别、分类、决策支持等的信息[10]。Liginlal利用FM提高不确定信息的表示,将其用于产品创新辅助决策[11];Govindaraju利用FM优化图像识别中分类精确度[12];Graves利用FM更好地确定样本分类边界,优化神经网络分类效果[13]。

D-S理论可以提供关于模糊测度和不确定变量之间关联的信息, 对模糊测度和变量之间关联的可能性进行特征描述[14]。本文提出基于模糊测度的KNN(Fuzzy Measure KNN,FM-KNN)模型,通过构建D-S证据理论模糊测度函数,解决D-S证据理论不具备单调性等缺点;再利用证据模糊测度函数加强对不确定特征信息的推断量化,从而提高多维度数据的分类效果。

2 证据理论和模糊测度

2.1 D-S证据理论

如果集函数m:2Θ→[0,1]满足: $m (\emptyset) = 0, \sum_{A \subseteq Θ} m (A) = 1$ ,则称m为框架Θ上的基本信任分配(BPA),其中m(A)是A的基本可信数。它体现了D-S理论对于不确定性的量度,即信任的分配方式。对于子集A⊆Θ,其信任函数定义为: $B e l (A) = \sum_{B \subseteq A} m (B)$ 。似然度函数定义为: $Ρ l (A) = \sum_{B \cap A \neq \emptyset} m (B)$ 。对每一个事实A,信任区间[Bel(A),Pl(A)]表示对A的信任程度,并可根据BPA的基本概率分配函数直接计算得到A的信任程度,从而完成对不确定性知识的处理。在很多的应用中需要对多个集函数mass进行组合,称为Dempster组合规则。对于两个信任函数m1和m2组合公式表示为:

$\begin{array}{l} (m_{1} \oplus m_{2}) (\emptyset) = 0 (1) \\ (m_{1} \oplus m_{2}) (A) = \frac{\sum_{B \cap C = A \neq \emptyset} m_{1} (B) m_{2} (C)}{\sum_{B \cap C = \emptyset} m_{1} (B) m_{2} (C)} (2) \end{array}$

2.2 模糊测度

设g是(X,V)上的模糊测度,(X,V,g)模糊测度空间。模糊测度是一个单调而且归一化的集合函数。它将概率测度中的可加性条件替换为单调性条件。当使用模糊测度表示不确定变量的信息时,g(E)可以认为是V在集合E中的置信度。典型的模糊测度就是一个概率测度,因此模糊测度可以表示为:

$\begin{array}{l} g ({x_{i}}) = p_{i} (3) \\ g (E) = \sum_{x_{i} \in E} g ({x_{i}}) (4) \end{array}$

3 基于模糊测度的KNN算法(FM-KNN)

3.1 算法思想

D-S证据理论采用半可加性原则,不具备单调性。针对这些问题,本文通过引入模糊测度改进D-S证据理论,形成新的相加性测度,保证证据合成的准确性和不确定性度量,符合证据基本可信数的要求。本算法设计流程:首先通过建立证据理论模糊测度函数,再利用置信测度和似然测度确定各分类命题的BPA,然后利用证据组合理论在域上将每条证据的BPA进行组合,得到最终的分类信度确定分类规则(图1)。

3.2 相关符号定义

①假设一个训练样本矩阵P×N,P表示特征向量的维度,N表示特征向量的数量;

②Χ={xi=(xi1,…,xiP)|i=1,…,N}表示训练样本集合;

③Ω={C1,…,CM}表示包括M个类的集合;对于每一个xi使用Li∈{1,…,M}作为一个类标记,用于表示属于Ω中某一类的信度置信度;

④xs表示利用训练集合中约束条件得到的新样本。对xs分类就是把样本划分到Ω中的某个类,xs∈Cq,q=1,…,M;

⑤Φs表示利用KNN算法xs,根据距离测度得到的分类集合;

⑥对于X的子集定义m(Bi)称为基本元素,q是基本元素的数量。

3.3 算法步骤

Step 1:证据理论模糊测度函数的基本信任分配m:

初始化g(E)=0,i=1

g(E)=g(E)+δi

其中 (1) if Bi⊆E then δi=m(Bi)

(2) if Bi∩E=∅ then δi=0

i=i+1

如果i<=q,转到Step 2;否则,停止。

得出证据理论模糊测度信任结构:

$g (E) = \sum_{i = 1}^{q} m (B_{i}) \frac{| B_{i} \cap E |}{| B_{i} |} (5)$

建立满足模糊测度约束的似然测度和置信测度。置信测度确定对命题成立的最小不确定性支持程度,似然测度用于确定不否定命题的程度。

似然测度Plm: $Ρ l_{m} (A) = \sum_{i, B_{i} \cap A \neq \emptyset} m (B_{i}) (6)$

置信测度Belm: $B e l_{m} (A) = \sum_{i, B_{i} \subset A} m (B_{i}) (7)$

Step 2: 对于分类模式通过证据模糊测度的假设支持信度,确定相应的归属类。dq表示隶属与同一个类的向量x,x(i)之间的平均距离:

$\begin{array}{l} d (x, x^{(i)}) = (x - x^{(i)})^{t} \sum_{i = 1}^{q} (x - x^{(i)}), \\ 1 \leq q \leq Μ, 1 \leq i \leq n (8) \end{array}$

建立先验函数:

$φ_{q} (d) = \exp (- d^{2} / d_{q}) (9)$

Step 3:对任意的xi∈Φs,Li=q可以视为支持信任xs属于Cq的证据,但是这并不能提供足够的置信度。通过证据模糊测度函数进行估计,以解决样本数据类的分布密度,以及先验概率不确定的问题。利用(6)、(7),通过与Cq类中的临近点的距离进行比较,确定xi是否属于xs. 根据基本可信任分配(BPA)对假设进行表示,对任意的xi∈Φs,

$\begin{array}{l} m^{s, i} ({C_{q}}) = φ_{q} (d^{s, i}) (10) \\ m^{s, i} (Ω) = 1 - m^{s, i} ({C_{q}}) (11) \end{array}$

Step 4:对于每一个xs,BPA依靠类的标记以及到xs距离进行定义。对于Φs的两个元素xi和xj属于同一个类Cq,利用证据组合公式(2)有ms(i,j)=ms,i⊕ms,j,对多个BPA进行组合得到:

$m_{q}^{s} = \underset{x^{i} \in Φ_{q}^{s}}{\oplus} m^{s, i} (12)$

利用式(12)对Step 3中的BPA(10)、(11)进行组合计算,进一步得到:

$\begin{array}{l} m_{q}^{s} ({C_{q}}) = 1 - \prod_{x^{i} \in Φ_{q}^{s}} (1 - m^{s, i} ({C_{q}})) (13) \\ m_{q}^{s} (Ω) = \prod_{x^{i} \in Φ_{q}^{s}} (1 - m^{s, i} (Ω)) (14) \end{array}$

Step 5:进一步联合每一个类msq的BPA,由式(12)得到BPA公式: $m^{s} = \oplus_{q = 1}^{Μ} m_{q}^{s}$ ,代入(13)、(14)进行计算得到:

$\begin{array}{l} m^{s} ({C_{q}}) = \frac{m_{q}^{s} ({C_{q}}) \prod_{r \neq q} m_{r}^{s} (Ω)}{\sum_{q = 1}^{Μ} m_{q}^{s} ({C_{q}}) \prod_{r \neq q} m_{r}^{s} (Ω) + \prod_{q = 1}^{Μ} m_{q}^{s} (Ω)}, \\ q = 1, \dots, Μ (15) \\ m^{s} ({Ω}) = \frac{\prod_{q = 1}^{Μ} m_{q}^{s} (Ω)}{\sum_{q = 1}^{Μ} m_{q}^{s} ({C_{q}}) \prod_{r \neq q} m_{r}^{s} (Ω) + \prod_{q = 1}^{Μ} m_{q}^{s} (Ω)} (16) \end{array}$

Step 6:得到类的每个关联的信任函数ms类集函数,Bels表示命题成立的最小的不确定性函数;Pls表示对命题的信任程度成立的不确定性度量。FM-KNN分类中xs的可信度表示为:

$\begin{array}{l} B e l^{s} ({C_{q}}) = m^{s} ({C_{q}}) (17) \\ Ρ l^{s} ({C_{q}}) = m^{s} ({C_{q}}) + m^{s} (Ω) (18) \end{array}$

Step 7:利用建立的分类似然值(17)和置信值(18),可以得到FM-KNN算法的分类规则C:

$C (x^{s}) = \arg \max_{p} m^{s} ({C_{p}})$

C(xs)表示应该归属于xs的标记。

4 实例分析

4.1 实验数据

本文使用常用测试数据集UCI机器学习数据库[17]作为实验数据。为保证实验数据具有一定代表性,我们选取了4个样本数和特征向量的维数均不同数据库(数据特征见表1)。

4.2 实验与结果评价

本文仿真实验过程:对数据集S,把S随机的分成SD训练集和ST测试集两个子集。对集合S的每一个数据,我们先使用SD作为训练集合,ST作为测试集称为P1;再对两个集合进行调换称为P2进行重复实验。对于P1和P2两种实验,计算平均错误率Avg. 算法对比选择了KNN,基于投票KNN(voting-KNN,V-KNN)[16],基于距离权重KNN(distance-weighted KNN,DW-KNN)[17],与FM-KNN进行对比。

实验分析及说明:① 对于Iris样本几种算法分类效果错误率接近。当数据的属性维度较少时,样本的维度彼此不会表现太多的不确定性,分类模式的信息特征更容易确定。FM-KNN分类错误率低于普通KNN算法,但比DW-KNN要差一点,对于非多维数据FM-KNN不是最优选择。

② 对于多维度的Glass和Ecoli样本,FM-KNN有效性非常显著,错误率低于其他算法。类似其他基于实例的学习算法,KNN采用相似度测量使用欧氏距离或者是余弦距离和内积,对属性维度比较敏感。当维度属性彼此没有相关性,找到的“近邻”就不是真正的“近邻”。即判断近邻的距离度量不涉及向量特征之间的关系,这使得距离的计算不精确,从而影响分类的精度。

③ Pima样本,由于分类样本只有两类,虽然样本维度属性多,但是模式识别相对简单,算法分类效果差异并不显著,FM-KNN优于其他算法。

FM-KNN算法改善分类性能的好坏依赖于具体数据库和具体特征,但对于多维度属性的样本数据表现出较好的分类效果。

5 结论

本文提出了基于模糊测度的k-邻近分类算法,该算法利用模糊测度优点解决了证据理论非单调性等不足,通过对多维度属性中的不确定信息的量化处理,提高k-邻近分类效果。实验证明,该算法不仅可以有效的处理多维度属性数据,还可以处理多类别的数据分类,具有良好的实用性。

【改进的KNN算法】推荐阅读：

改进的FFT算法05-10

改进的TSP算法05-23

改进的DSM算法06-14

改进的粒子群算法07-05

改进的图像修复算法07-09

改进的SIFT算法10-30

改进的禁忌搜索算法11-13