改进的k_nn快速分类算法

改进的k-nn快速分类算法

桑应宾，刘琼荪SANGYing-bin，LIUQiong-sun

重庆大学数理学院，重庆400044

CollegeofMathematicsandPhysics，ChongqingUniversity，Chongqing400044，ChinaE-mail：sangyingbin@163.com

SANGYing-bin，LIUQiong-sun.Improvedk-nearestneighborclassificationalgorithm.ComputerEngineeringandAppli－

（11）：cations，2009，45145-146.Abstract：Inordertoovercomethedisadvantagesoftraditionalk-nn，thispaperusestwoalgorithmsofclassificationandcluster－

ingtoproposesanimprovedk-nnclassificationalgorithm.Experimentsshowthatthisalgorithmcanspeedupwhenithasafeweffectsinaccuracy.

Keywords：clusteringalgorithm；K-means；classificationalgorithm；k-nearestneighbor摘要：针对传统的k-近邻（k-nn）方法的缺点，将聚类中的K均值和分类中的k近邻算法有机结合，提出了一种改进的k-nn快速分类算法。实验表明该算法在影响分类效果不大的情况下能达到快速分类的目的。关键词：聚类算法；分类算法；K均值；k近邻

文章编号：（2009）DOI：10.3778/j.issn.1002-8331.2009.11.0441002－833111-0145-02

数据挖掘是用于大规模数据处理的一种新的思维方法和技术手段，它是在现实生活中数据量呈指数级不断增长，和以数据库技术为核心的信息技术逐渐成熟的背景下应运产生的一种技术。数据挖掘可以帮助用户发现隐藏在大型数据库中的知识和有用信息。它融合了人工智能（artificialin－、统计（statistics）、机器学习（machinelearning）、模telligence）

式识别（patternrecognition）和数据库等多种学科的理论、方企业、政府、科研及体育等多种不同法与技术，已经在商业、类型的组织机构和领域中获得了非常广泛地应用。几种典型的数据挖掘方法的研究是关联规则、分类、聚类、预测、Web挖掘等[1]。

聚类（clustering）是一种无监督的学习，是指在没有训练数据样本的情况下，依据数据对象自身的相似性将一组对象划分成一系列有意义的子集的描述性任务[2]。通过制定数据对象的相似性度量标准，使得同一组内的数据有较高的相似度，不同组中的相似度较低。一般不同的相似度量标准就有不同的聚类结果。常用的聚类方法一般有基于模型的、密度的、划分的、层次的、网格的及混合的方法等[1]。

分类（classification）是一种有监督的学习，是指从一组已知类别的数据中发现分类规则，以此预测新的数据类别[3]。常用的分类方法主要有决策树、神经网络、遗传算法、支持向量机等。

本文综合考虑了聚类和分类方法的特点，提出了改进的k-近邻快速分类算法，可达到快速分类的目的。

m

文献标识码：A中图分类号：TP391

1K-均值聚类算法

为了得到K-均值算法建立在误差平方和准则基础之上[4]，

最优结果，首先要先选定一些代表点作为初始聚类中心，然后再用K-均值算法将其余的点化分到各类别中去。假设样本集

…，（K算法步骤[5]：

（1）选取K个初始聚类中心：…，（右上脚码为寻z1，z2，zK，找聚类中心的迭代次数）；

（2）将其余的数据归类：取样本xi，若有|xi-zl|<|xi-zl（其|中i=1，…，…，，则xi∈Sj，2，N，l=1，2，K，l≠j，m是迭代次数）Sj是聚类中心为zj的样本集合；

（3）计算新的聚类中心：zjnj为该类Sj所含的样本数；

（4）如果zj=zj

m

m+1

m

m+1

m

m

m

m

1

1

1

=1

nj

（其中j=1，…，，2，K）Σx

x∈S，其中j=1，…，则程序结束，否则令2，K，

（2）。m=m+1转到步骤

该算法的计算复杂度为O（NdKm），其中N表示样本容量，

迭代次数d表示样本维数，K表示类别数量，m表示迭代次数，

远少于样本容量。通过实例验证可发现，选择不同的初始聚类中心，将决定不同的聚类结果，从而导致聚类结果的不确定性，

现在许多学者研究所以初始聚类中心的选择就显得尤为重要。

作者简介：桑应宾（1980-），男，硕士研究生，主要研究方向：人工智能、支持向量机；刘琼荪（1956-），女，教授，主要研究方向：智能计算、数据挖掘、

应用统计。

收稿日期：2008-02-26修回日期：2008-05-061462009，45（11）ComputerEngineeringandApplications计算机工程与应用

（xi∈S）计算每一类别中的欧氏距离的最大值di，i的欧氏距离，

并求K出个类别的最大值d=max{di}。

…，i∈{1，2，K}

了很多改进的方法[6]，在此它不是本文研究的重点。

2k-近邻算法

（k-nearestneighbors）算法，简称k-nn。该方法最初k近邻

固定落入邻域中的样本是以特征向量x为中心的一个邻域里，

个数k（n）。通常采用如下方式实现：在一个合适的距离尺度下（常用的欧氏（Euclidean）距离），逐渐地增大包围x点的区域的体积，直到有k（n）个样本点落入该区域中。但这需要进行概率密度估计，其密度估计形式为：（n）/n赞（x，）pn=k

（n）V其中，（n）为该区域的体积。如果x点周围的样n为样本个数，V本点个数较少，那么相应的区域就会变得很大，即V（n）的值很赞大，（x，）的值变得很小。相反，如果x点周围的样本点个数较pn赞（n）的值较小，（x，）多，那么相应的区域就会变得较小，即Vpn的值变得很大。并且k（n）也会随n的增加而增加。由于k近邻法则进行概率估计密度时，存在两个缺点，一是估计密度的积分必须扩散到无穷大，二是计算上存在沉重的负担。因此，一些研究学者直接用k-nn算法进行分类，分类的原则是：在一定的

（n）个最近邻样本，并距离尺度下，考虑待识别样本x周围的k

将x归入到k（n）个最近邻中某一类样本最多的那个类别中去。

算法步骤：）对一个待分类的数据对象y，计算它与训练集R中的（1

每个数据对象的距离；

（2）找出待分数据对象y与训练集R中的数据对象距离最近的k个；

）依次统计出这k个数据对象的所属类别，找出包含最（3

多个数的类；

（4）将待分数据y划分到此类中；（5）重复以上步骤，直到所有待分数据分类结束；

k-nn是一种非常简单有效的分类方法[7]。但k-nn算法最大的缺点是每一次都要进行全局搜索，计算的复杂性大，速度慢。搜索每一个训练样本点，找出距离最近的那一个，每个距离的计算复杂度为O（r），其中r为样本维数。因此，总的计算复杂度为O（rTN），其中T代表待识别数据个数，N表示样本容量。本文研究的改进k-nn分类算法克服了该缺点。

③将每一个类别的聚类中心和其类别中的点之间的距离均除以l×d，其中l取足够大，以使各个类别所形成的区域足够小。

（n1，…，），④选取k满足条件k≤minn2，nkk取整数。

假设未知类别数据{ys}，⑤未知数据类别的判断：s=1，2，…，T。则根据k-近邻方法只须计算数据ys到各个聚类中心（…，之间的距离ds，如果min（ds）x2，K）=ds则可以判断jj=1，

1≤j≤K

ys∈Si类。

例如，假设ys和xj聚类中心为二维数据，只有两个类别算法说明如图1所示。S1、S2，

ysÁysx2S2x1ÁS2ÁS1S1（a）传统的k-近邻方法图1

（b）改进的k-近邻方法传统和改进的k-近邻方法

通过将类别S1、（S2中的点xj到聚类中心xj的距离dx）jxj，j，（d=max（d1，）），则图1（a）变化为图1（b），则j=1，2缩小ld倍d2

显而易见，判断ys属于S2是很自然的了。改进的k-近邻算法在分类阶段中其计算复杂度仅为（rTK），比传统的k-近邻算法复杂度O（rTN）要小得多，因为O

一般K<4实验结果与分析4.1实验结果

本文采用了三组数据集，选取的是UCI数据库（http：//archive.

）上的Iris、ics.uci.edu/ml/datasets.htmlbreast-cancer和cancerda－

类别为三类，测量ta等三组数据集。其中Iris选用150组数据，

指标有4个，其中120个数据用来建模，30个数据用来测试。

类别为两类，测量指标有10个，breast-cancer选用683组数据，

其中500个数据用来建模型，183个数据用来测试。cancerdata选用499组数据，类别为两类，测量指标有10个，其中400个数据用来建模，99个数据用来测试。本文提出的算法与传统的

以下实验结果是在Matlab7.0.1软件平台k-nn算法进行了比较，

上实现的，运行平台是256M内存，Celeron2.8GHz以及WinXpSever。运行结果如表1所示。

表1

运行结果

数据集

算法本文算法传统k-nn算法

Iris

准确度（）时间/s/%0.93330.9667

0.04700.4370

breastcancer11

0.17210.934

cancerdata0.92930.8788

0.1254.797

3改进的分类算法

本文提出的改进分类算法主要是将K-均值和k-近邻两

种方法相结合，首先是用K-均值对未知类别的数据进行聚类，然后再用k-近邻对未知类别的数据进行预测判断。并对传统的k-近邻方法进行了改进，在对判别准确率影响不大的前提下，大大减少了计算量，提高运算速度。

算法步骤：（1）运用K-均值的方法将数据集进行聚类R={x1，…，x2，得到R=S1∪S2∪…∪S（其表示数据集用符xN}，R分为K类，K号S1，…，）；S2，SK表示

（2）用改进的k-近邻方法对未知数据进行分类：

（1）中S1，…，…，计①统计步骤S2，SK的数据个数n1，n2，nK，算各个类别的聚类中心xi=1

ni

…，）。2，KΣx（i=1，

x∈Sj

准确度（）时间/s准确度（）时间/s/%/%

4.2实验分析

从4.1节的实验结果可以看出，运用改进的k-nn分类算法

对判别准确度影响不是很大，而其运行时间明显比传统的k-nn

（下转161页）

②计算各个类别中的聚类中心xi到其所属类别中的点xi

郑继明，俞佳：基于小波变换和支持向量机的音频分类2009，45（11）161

的音频分类结果精度均较好。使用db4小波和sym8小波变换的语音/非语音平均分类精度比使用Haar小波和bior4.4小波

使变换的平均精度要稍微高点，分别达到了90%和89.4444%；

用上述4种小波变换得到的音乐/环境音的分类精度都比较高，依次为95.2%、但是对纯语音/带背景音95.6%、94.8%和95.6%；乐的语音分类精度都相对较低，分别只有81.2%、83%、81.6667%和84%。

4.2特征有效性分析

为了验证本文提出的新特征的有效性，设计如下实验：将比较常用的MFCC、静音比和带宽均值组成基本音频特征集（Bset）；本文提出的小波熵、低帧能量比、基音变化率和等基音频率比例4个新特征组成新特征集（Nset）。为了验证本文选取的特征集的有效性，本文将去除新特征集后的识别率和加入了新特征集后的识别率进行了比较分析，使用的是db4小波，实验结果如表2所示。

表2

类别S/非SM/EPS/SWM

提出了一种基于小波变换和支持向量机容的音频检索的关键。

（SVM）的音频特征提取和分类的方法，用于纯语音、音乐、带背

低帧能景音乐的语音以及环境音的分类，并且评估了小波熵、

量比、基音变化率和等基音频率比例4个新音频特征集合在

文中提出音频特征SVM分类器上的分类效果。实验结果表明，

可以达到较高的分类精度，但是这种方法对纯语音/带背景音乐的语音分类精度不是很理想，以后将从以下两个方面进行改进：研究更加有效的音频特征；设计新的支持向量机使分类效果更好。

参考文献：

[1]WoldE，BlumT，KeislarD，etal.Content-basedclassification，search

（3）：1996，327-36.andretrievalofaudio[J].IEEEMultimedia，[2]LiuZ，HuangJ，WangY，etal.Audiofeatureextractionandanalysis

forsceneclassification[C]//IEEESignalProcessingSociety1997

WorkshoponMultimediaSignalProcessing，NewJersey，USA，1997：23-25.

[3]FooteJ.Content-basedretrievalofmusicandaudio[C]//KuoCC

ProceedingsofJ.MultimediaStorageandArchivingSystemsII，

SPIE，1997，3229：138-147.清华大学出版社，[4]刘明才.小波分析及其应用[M].北京：2005.

费树岷，陈丽娟.基于小波子空间、支持向量机和模糊积分的[5]杨欣，

（2）：信号多类分类算法[J].信息与控制，2007，36211-216.

KrishnanS，RaahemifarK.Contentbasedaudioclassifi－[6]EsmailiS，

cationandretrievalusingjointtime-frequencyanalysis[C]//Pro－ceedingsoftheIEEEInternationalConferenceonAcoustics，（ICASSP’），Speech，andSignalProcessing042004，5：17-21.

陈毅松，孙正兴，等.基于隐马尔可夫模型的音频自动分类[J].[7]卢坚，软件学报，（8）：2002，131593-1597.吴文虎，郑方，等.基于支持向量机的语音识别研究[C]//第六[8]苏毅，

届全国人机语音通讯学术会议，深圳，2001：223-226.高志，余啸海.Matlab小波分析工具箱原理与应用[M].北京：[9]董长虹，

国防工业出版社，2004.

特征有效性分析实验结果（%）

Bset73.88898578.9

Bset+Nset（+16.1111）90

（+10.6）95.6（+4.1）83

从实验结果可以看出：基本特征集对于这4类音频的识别

具有一定的有效性和准确性；加入新特征集后，对这4类的识别精度都有大幅度的提高，分别提高了16.1111%、10.6%和原4.1%。其中对语音和非语音的识别精度提高的幅度最明显，因是语音和非语音结构差别较大，这4个特征可以有效的刻画语音和非语音的结构特征差别。全特征集的识别精度分别达到了90%、说明了本文选取的特征集合理、有效。95.6%和83%，

5结论

音频特征提取是音频分类的基础，而音频分类又是基于内

（上接146页）

算法有很大的提高。并且通过实例验证还发现，本文算法中的第一步，初始聚类中心的选取对分类结果影响不大；第二步k（k≤min（n1，…，））的选择在允许取值的范围内对最终分n2，nk类结果的影响也不大，运行结果比较稳定。

择方面作一些改进，从而提高分类的效果。

参考文献：

刘芳，刘静，等.智能数据挖掘与知识发现[M].西安：西安电[1]焦李成，

子科技大学出版社，2006.

陈宁，周龙骧，等.数据挖掘技术及应用[M].北京：科学出版[2]陈安，

社，2006.

袁方，刘海博.用聚类-分类模式解决聚类问题[J].广西师范[3]周志勇，

大学学报，（2）：2007，25127-130.

张学工.模式识别[M].北京：清华大学出版社，2000.[4]边肇祺，

刘振全.一种新的确定K-均值算法初始聚类中心的方法[J].[5]王汉芝，

天津科技大学学报，（14）：2005，2076-79.

[6]KrishmaK，MurtyMN.GeneticK-meansalgorithm[J].IEEETrans

（1）：onSystem，Man，andCybernetics：PartB，1999，596-100.胡卫东，郁文贤，等.一种基于近邻搜索的快速k-近邻分类算[7]王壮，

法[J].系统工程与电子技术，（4）.2002，24

5结语

为了减少k-近邻算法的计算量，提出了一种快速分类算

法，但该算法仅是一个近似算法，但它克服了k近邻算法收敛速度慢的不足，有效提高了运行速度。并且改进后的方法对准确度也没有很大影响，又减弱了初始聚类中心的选择和k近邻中的k的选取对结果的影响。

所用的数据集要用到空间中的欧氏距离进行计算，而对于定性指标数据集不适宜。下一步的工作应该考虑其他的距离度量，将模式识别的应用范围扩大。另外还可以在近邻的指标选