一种提高K近邻分类的新方法

摘要:KNN算法是数据挖掘技术中比较常用的分类算法。但是,当样本容量较大以及特征属性较多时, KNN 算法分类精度和效率将大大降低。该文将主分量分析(PCA)与粗糙集理论(RS)应用于样本特征提取中,首先采用PCA对输入向量进行甄别,应用粗糙集理论约简与分类无关或关系不大的向量。然后利用模拟退火算法实现随机属性子集选择,组合K 近邻分类器,最后利用简单投票方法,对多重K近邻分类器进行组合输出,有效地改进了K近邻法的分类精度和效率。

关键词:主分量分析;粗糙集;模拟退火;k近邻;组合模型

中图分类号:TP393文献标识码:A文章编号:1009-3044(2010)08-1989-03

A New Method to Scale Up Effect of K-Nearest-Neighbor

RU Qiang-xi1, LIU Yong2

(1.Department of Mathematics and Physics Teaching,Luoyang Institute of Science and Technology, Luoyang 471023, China;2.Department of Mathematics and Physics Teaching,Luoyang Institute of Science and Technology, Luoyang 471023, China)

Abstract: The k-Nearest-Neighbor(KNN) algorithm has been widely used in data mining areas. But, When the samples become more and more large and characteristic attributes become more and more numerous, then KNN algorithm becomes much lower. A improved KNN algorithm PRMKNN is proposed in the paper ,which first applies Principle Component Analysis(PCA)and rough set theory(RS)torealize feature extraction, We use PCA on selecting the input vector,and use RS on reducing the inessential factors for classification ,then simulation annealing algorithm is used to generate random subset of attributes, and with the simple voting method, the outputs of the multiple KNN classifiers are combined. The method can improve the classification precision and efficiency effectively.

Key words: principle component analysis; rough set; simulated annealing; k-Nearest-Neighbor; combination model

数据分类属于模式分类的一个分支。它旨在生成一个分类函数或分类模型,由该模型把数据库的数据项映射到某一给定类别中。目前机器学习、专家系统、统计学和神经生物学相关领域的研究者提出了许多分类方法,如决策树算法、关联规则算法、贝叶斯算法、神经网络算法、遗传算法、k最近邻算法、基于案例的推理算法等。

kNN是一种无参数消极分类方法,属于最近邻分类方法的一种推广。K近邻算法从测试样本点x开始生长,不断地扩大区域,直到包含进k个训练样本点为止,并且把测试样本点x的类别归为这最近的k个训练样本点中出现频率最大的类别。

由于kNN算法的简单有效性,目前得到了较为广泛的应用。但是,当样本容量较大以及特征属性较多,并且,如果属性集包含不相关属性或弱相关属性, 那么分类精度和分类效率将大大降低。经过研究发现,如果在使用 KNN 算法之前对样本的属性进行约简,删除那些对分类结果影响较小的属性,则可以用KNN 算法得到更好的分类效果。

目前在特征向量的降维方法中,主分量分析方法(PCA)是主要的一种方法。近年来,粗糙集(Rough Set,RS)理论也已经从理论研究过渡到了应用研究,已经有不少应用于模式识别中。因此,本文首先将主分量分析(PCA)和粗糙集理论(RS)应用到传统KNN算法中,约简与分类无关或关系不大的特征向量,然后利用模拟退火算法实现随机属性子集选择,组合K 近邻分类器,最后利用简单投票方法,对多重K近邻分类器的输出进行组合输出。实验表明,该算法有效改进了K近邻法的分类精度和效率。

1 相关知识介绍

1.1 PCA和RS联合特征提取

PCA是一种统计方法,其在分析中主要利用了所分析对象的内在的统计特征。因而通过PCA变换使得提取的分类特征更加明显,使其能量向某些相对分量集中,增强随机矢量总体的确定性,分类效果也可更好。如何选择主分量用作分类的特征一直是 PCA 方法的研究重点,虽然能用K-L变换优化,但不能适应所有的分类目标。而RS 恰好可以对待分类的特征属性进行适当的约简,提取最小核用于分类,这样可使提取到的特征向量是最佳分类向量。

具体算法如下:

对一有限的集合T,包括了有N个类:

每个类都由n维实值模式组成。由于PCA是种无监督的方法,而从T中可以得到一个分类模式集的矩阵:X=[x1,x2,…,xN]

应用PCA可以得到一个n*n的变换核Wkl,如果选择前m(m

由以上表述可以知道:在这一步,由Y表达的矩阵已经是原始矩阵的离散化表示。即Y已经是经过计算得到的N*m大小的矩阵,用Yd 表示,从Yd得到T的目标分类为DTm,也就是得到一个m维决策表。

已知一个供决策用的属性集,可以应用RS理论的约简方法,提取出对分类起重要关键作用的属性。那么,如果能使DTm计算得出最终的r(r的大小由分类类别决定)维的分类属性集Xfuture,reduct用于后续的处理(如分类),则分类属性应该是最佳的。

现在由于由DTm 计算出的Xfuture,reduct代表了待分类的最佳属性集,则DTm 由Yd的相关经选择的属性组成。每个属性标示了相应的目标分类。相应的,从投影得到的Y 中包含了已经选择的分类属性集Xfuture,reduct,并且得到了约简后供决策用的的DTf,r实值表。这样,从最初的属性集T中提取到了对于分类起关键的决定性作用的属性集Xfuture,reduct。

由以上处理过程,就分别利用RS与PCA完成了对待分类属性集的投影与约简操作。最终试验结果表明,此分类属性集就是在分类中起决定作用的分类属性集。

1.2 模拟退火算法

模拟退火算法的名字来源于金属重结晶的退火过程。首先将固体加温至充分高,再让其徐徐冷却,重结晶。退火算法可以应用于最优解的搜索,它将搜索最优解的过程模拟为退火的过程,系统的初始状态就是问题的初始解,最终状态就是最后得到的最优解。在退火过程,也就是查找最优解的过程中,温度不断降低,不断找到一个新的解,如果这个解优于先前找到的解,那么接受这个解;如果这个解劣于先前的解,那么以一个概率P接受这个解,P的定义如下:,其中ΔE为当前解于前一个解的差,即ΔE=E(i+1)-E(i),T(i)为当前温度,k为Boltzmann常数。

对最优解的评价函数可以采用准确性度量,准确性度量就是测试当前选择的特征组合的分类效果。模拟退火算法使用在特征选择中,最终所选择的特征组合就是一个最优解,我们的任务就是通过模拟退火算法寻找这样一个最优特征组合。

SA算法应用于特征选择时的算法过程如下:

1) 随机选择一个特征作为最优解。

2) 执行m次迭代:a) 随机剩余的特征子集中选择一个特征;b) 通过目标函数评价当前选择的特征子集;c) 计算ΔE=[E(Y(i+1))-E(Y(i))];

如果 ΔE

如果连续s次ΔE>0,退出迭代,算法结束。

1.3 组合分类器

组合分类器的方法有很多,通常分为投票法、非投票法等。投票法是组合分类器最常使用的方法,它起源于贝叶斯学习理论。贝叶斯学习理论规定为了取得最大的预测精度,在假设空间使用所有可容许的方法而不是只使用一种学习方法,对每种方法利用投票法给出权重。

尽管有很多对组合分类模型的研究,但对KNN分类器的组合研究却不多。 Hansen和Salamonnz表明在简单的投票中,如果各个模型有独立的错误,那么整体错误就会随着分类器数目的增加单调减少。Ali和Pazzani的实验证明具有不相关错误的模型的组合能有意义地减少整体的错误。选择不同的属性就是试图强迫分类器产生不同的和不相关的错误。

2 基于模拟退火的组合K近邻算法 PRMKNN

2.1 KNN分类算法

KNN算法的基本思想是最相近的数据样本应该属于同一个类别(一种连续的假设)。在预先选择好距离度量标准后,计算出待分类样本最近的k个距离最近的训练集内数据样本,然后再根据这k个样本所属类别的多数决策待分类样本的类别

KNN算法一般分为四个步骤:1) 选择一个合适的距离度量标准;2) 通过选定的距离度量标准找出待分类样本的k个近邻;3) 找出这k个近邻中类别占多数的类别;4) 将待分类样本判定为该类别。

为了找出待分类样本的k个近邻,必须要搜索数据库并进行计算,而这也是KNN算法效率的瓶颈所在。我们通常采用欧氏距离来确定样本的相似性,欧氏距离的计算公式为:

其中X=(x1,x2,…xn)和Y=(y1,y2,…,yn)代表两个样本数据,n为样本特征属性的个数。

2.2 改进的KNN 分类算法PRMKNN

输入:训练数据集D={(xi,yi),1 ≤i ≤n} ,其中xi是第 i 个样本的条件属性, yi是第 i个样本的类别属性,新样本为 X,距离函数为d。

输出:待分类样本 X 的类别属性Y。

步骤1:利用PCA和RS,联合提取训练样本数据集的属约特征;

步骤2:按训练样本的约简结果对待分类样本数据 X 的属性进行约简;

步骤3:利用模拟退火算法进行特征选择,如果采用N个组合分类器,则将模拟退火算法迭代N次,生成N个随机属性子集。

步骤4:根据约简后的训练样本和模拟退火算法生成N个随机属性子集,来对测试样本做k-近邻分类。

步骤5:利用简单投票方法,对多重KNN分类器的输出进行组合。统计每个类别出现的次数,将出现次数最多的类别确定为待分类样本数据 X 的类别 Y。

2.3 KNN与PRMKNN分类效果比较

本次我们用来比较两者分类效果数据源来自www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets里的australian。在这个数据库中,包含2个类,共计690个带标签的样本,每个样本包含14个特征。在690个样本中随机挑选150个一类样本作第一类训练样本,随机挑选150个第二类样本作为第二类训练样本,然后从剩下的样本中再随机挑选80个样本(其中40个第一类和40个第二类)作为待测样本

利用KNN算法进行分类时,分别取K= 5、8、9进行分类,平均分类正确率为:61.08%;

利用PRMKNN算法进行分类时,首先利PCA和RS联合提取训练样本数据集的属性特征,然后让M(分类器的数目)分别取1-9,K分别取2―8进行分类,平均分类正确率为:78.51%

实验结果表明,K与M 的取值都影响分类正确率,为了提高分类正确率,可以反复实验选出最恰当的K与M。本实验中取M=3,K=7可以取得较好的分类效果。当M=3,K=7时 10次实验的平均正确率为: 86.58%

可以看出,改进的KNN算法PRMKNN较原始的KNN有更好的分类效果,特别是选定恰当的K和M后。

3 结束语

K-近邻(KNN)算法以其简单、有效和高鲁棒性而被广泛地应用于机器学习与数据挖掘领域解决分类问题。它是一种典型的消极学习方法,在训练阶段仅仅存储所有的训练实例,所有的计算都延迟到分类阶段进行。因此当样本数据的特征属性的数量较多、样本的容量较大时,如果属性集包含不相关属性或弱相关属性,分类的时间代价很大,分类的效果不是很好。本文提出的KNN的改进算法PRMKNN在对新样本数据进行分类之前,先利用PCA和RS联合提取训练数据集的特征,删除那些对样本的决策影响很小或者是根本没有影响的冗余属性,然后利用模拟退火算法实现随机属性子集选择,组合K 近邻分类器,最后利用简单投票方法,对多重近邻分类器进行组合输出。实验表明,改进KNN分类算法PRMKNN有效提高了分类的效率和精度。

参考文献:

[1] 代六玲,黄河燕,陈肇雄.中文文本分类征抽取方法的比较研究[J].中文信息学报,2004,18(1):26232.

[2] Oh K S, Aghbari Z, Kim P K. Fast k-NN search with self-organizing maps[J].Proc.of 5th Int. Conf. on Image and Video Retrieval, July 2002.

[3] 张冬玲.基于粗糙集理论的属性约简算法的实现[J].计算机应用,2006(2):78.

[4] 郑宏珍,刘洋,战德臣.基于数据挖掘的组合近邻模型算法[J].计算机工程,2007,33(3):48250.

[5] Skalak D B. Prototype Selection for Composite Nearest Classifiers[D].University of Massachusetts Amherst,1997.

[6] 刘素华.基于遗传算法和模拟退火算法的特征选择方法[J].计算机工程,2005(16):157.

[7] 高尚.模拟退火算法中的退火策略研究[J].航空计算技术,2002,32(4):20-22,26.

[8] Alpaydin E. Voting over Multiple Condensed Nearest Neighbors[J].Artificial Intelligence Review,1997,11(2):115-132.

[9] Yeung K Y, Ruzzo W L. Principal Component analysis for clustering gene expression data. In Computer Science and Engineering,Box 352350 University of Washington,Seattle,WA98195,USA., 2001,17(92001):763-774.

[10] 王克奇.基于模拟退火算法和最近邻分类其识别率的特征选择方法[J].自动化技术与应用,2007(1).

[11] Bondugula R, Duzlevski O, Xu Dong. Profiles and Fuzzy k nearest neighbor algorithm for protein secondary structure prediction. Asia Pacific Bioinformatics Conference,2005:85-94.