KNN模型论文（精选7篇）
KNN模型论文 第1篇
随着Internet网络的高速发展, 网络安全问题得到了越来越多的重视。而入侵检测系统 (intrusion detection systems, IDS) 作为能主动发现攻击事件的安全屏障[1], 近几年已成为愈来愈多学者专家的研究热点。传统的入侵检测方法大多基于数据挖掘及机器学习方法, 并且, 大都可以转化为相应的分类问题来解决。例如有人将传统的神经网络[2]和支持向量机算法[3]应用在入侵检测领域, 得到了较好的检测效果。然而在实际应用中, 网络连接数据有规模巨大和实时不断增加的两大特点, 传统的分类算法将很难完全适用。
针对连接数据规模巨大的特点, 文献[4]提出了数据的分片 (分割) 机制, 其核心思想是将高速海量数据分割成不同部分并分配给分布的独立检测节点并行处理。在此基础上, 元学习[5,6]、协作贝叶斯学习[7]等并行学习算法, 都将得以应用到例如信用卡[8,9]、网络[10]等异常检测中。刘衍衍[11]等人将并行学习的神经网络算法应用于大规模的入侵检测中, 而Filino[12]等人则使用了一种遗传集成技术, 均取得了不错的效果。
然而以上的分布式算法大多属于静态方法, 而在入侵检测领域, 算法的增量学习能力是非常重要的。这是由于首先, 在实际中新类型的攻击不断增加, 很难一次获得足够描述整个数据分布的数据集。而入侵检测系统不可能等到获得了足够多的训练样本后再投入使用。其次, 每次都在新增数据和原有数据上重新建立模型将耗费大量的时间和存储空间, 无法满足实际的应用[13]。
2相关工作
2.1传统KNN算法
KNN算法是一种简单而有效的分类算法。它的基本思想是:使用一种距离度量计算待分类样本与所有训练样本之间的距离, 找到距离待分类样本最近的k个近邻;然后根据这k个近邻所属的类别进行多数投票来确定待分类样本的类别[14]。
KNN算法在许多应用领域均取得了成功。Liao[15]等人在入侵检测领域中使用KNN算法, Li等人[16]则提出了一种KNN主动学习的入侵检测算法。然而, 传统的KNN是一种懒散型的学习方法。由于对每个新样本进行分类时, 它都要计算新样本与所有训练样本之间的距离, 这导致KNN算法在分类新样本时效率低下[14]。显然无法直接适用于对实时性要求比较高的入侵检测领域。
2.2KNN模型算法
KNN模型算法 (简记KNNModel) 是Guo[14]等人提出的一种改进的KNN算法, 大大提高了传统KNN算法的预测效率。
KNNModel算法的基本思想是:给定一个相似性度量, 以每个训练样本为圆心, 向外扩展成一个区域, 使这个区域覆盖最多的同类点, 而不覆盖任何异类点。然后选择覆盖最多点的区域, 以四元组<Cls (di) , Sim (di) , Num (di) , Rep (di) >形式保存下来形成一个模型簇, 其中Cls (di) 表示该模型簇中数据点的类别;Sim (di) 表示该模型簇的半径, 即最远点到圆心di的距离;Num (di) 表示该模型簇覆盖点的数量;Rep (di) 则为圆心di本身。算法重复迭代多次, 直至所有的训练样本至少被一个模型簇所覆盖。这样, 只需保存这些模型簇待到分类新数据的时候使用即可。
可见, KNNModel算法在训练样本上构建多个模型簇来代替整个训练样本集, 并保存这些模型簇用于分类新数据。它成功地对数据进行了约简, 因而在保证分类精度的同时, 大大提高了分类新数据的效率。然而, 在许多应用领域, 数据每天都在增加, 传统的KNNModel算法仍需保存所有的数据以重新建立新模型, 耗时耗力, 无法满足实际应用的需要。
2. 3增量的KNNModel算法的基本思想
鉴于传统的KNNModel存在的缺陷, 我们提出了一种基于KNNModel的增量学习方法, 它通过对KNNModel产生的模型簇引进“层”的概念, 对新增数据建立不同“层”的新模型簇的方式对原有模型进行优化, 达到增量学习的效果。
当一个模型簇覆盖了过多的错分样本时, 说明这个模型簇在某些区域是不够准确的。IKNNModel算法提出了一种层的概念, 不直接对原有模型簇进行修正, 而通过建立新模型簇对原有模型进行优化, 见图1所示。
图1中有方形和三角形两类新样本点, 原有的模型簇old中包含了过多的错分点, 显然在边界处不够准确。而在新样本基础上构建的新模型簇new在交叉区域则更加准确。因此我们用新模型簇覆盖旧模型簇的错分区域, 使得原有模型能够得到通过增量学习不断地修正。
与传统KNNModel算法不同的是, IKNNModel算法是以<Cls (di) , Sim (di) , Num (di) , Rep (di) , Lay (di) >.
来保存模型簇 (简记O (di) ) , 其中Lay (di) 表示模型簇di 的层值。
在原始数据集上建立的模型簇的层值均设为0。在每次增量步中, 若原有模型簇覆盖了一定量的错分样本, 则层值保持不变, 否则层值增一。这样在预测新数据时, 若新数据被多个模型簇所覆盖, 则选择层值最高的模型簇的分类结果。
3基于IKNNModel的分布式入侵检测算法
在现代入侵检测领域, 随着互联网的快速发展, 网络的规模和传输速度急剧增长, 如何在海量数据中进行快速地数据挖掘成为一大难题。目前, 分布式入侵检测系统[17]已成为该研究领域的一个热点。U C Davis的DIDS[17], DrIDS[18], 以及Purdue大学提出的AAFID[19]等是分布式入侵检测系统的一些实例。在此基础上, 各种的集成学习算法都可以被应用于分布式入侵检测领域, 在降低了训练时间的同时保证了系统的分类精度。刘[11]等人将并行学习的神经网络算法应用于大规模的入侵检测中, 而Filino[12]等人则使用了一种遗传集成技术, 均取得了不错的效果。
然而, 以上的方法大多属于静态分类算法。在入侵检测领域, 数据连续不断地增加, IKNNModel算法实现了基于KNNModel的增量学习, 并缩短了KNNModel建立模型的时间。于是我们将IKNNModel算法与分布式学习算法相结合, 实现了一种基于增量KNN模型的分布式入侵检测架构。
分布式并行入侵检测的一般步骤是:将捕获的数据按一定的分割算法分给各个节点计算机;各节点计算机同时并行学习;将各节点计算机的运算结果加以合并[11]。
在分割算法上, 本文采取了一种随机分割方法[11], 即将样本数据随机地平分为不相交的子集。这种方法降低了计算复杂度, 并使得各个结点获得相同数量的样本, 发挥出了并行计算的优势。然而这种分割算法在一定程度上破坏了数据的完整性, 加剧了少数数据的不平衡性, 这个局限在实验中得到体现, 这也是我们下一步工作的重点。而在合并策略上, 我们采用了大多数投票的机制, 进一步降低了计算复杂度。
具体算法框架如图2所示, 在训练阶段, 首先将得到的原始训练数据随机平分成互不相交的k个子集交由k个节点计算机, 然后这k个节点计算机同时在这k个子集上分别训练出一个KNN模型, 记为KNNModeli (i=1, 2, k) 。每当有新增数据到达时, 将新增数据再随机地分成互不相交的k个子集, 交由对应的节点计算机上的IKNNModelj (j-1, 2, , k) 算法并行地进行增量学习。这样, 在测试阶段如图3所示, 当未知标签的新样本到达时, 将样本交由每个节点计算机, 通过各自的IKNNModel算法得到k个结果, 再用投票的策略将他们融合起来, 就可以得到这个新样本的预测类别。
分布式入侵检测算法实现如下:
Step 1. 将原始训练数据集随机分成k个子集{S1, S2, , Sk}, 分送k个不同的节点, 在每个Si子集上分别建立k个KNNModel-i 模型, i=1, 2, , k;
Step 2. 将每次得到的新增训练样本随机分成k个子集{Z1, Z2, , Zk}, 每个子集Zi交给对应的KNNModel-i进行增量学习得到:
IKNNModel-i模型, i=1, 2, , k;
Step 3. 对于待分类数据, 得到k个IKNNModel的预测结果;
Step 4. 用得到的k个IKNNModel使用
多数投票策略进行集成预测, 输出最终预测结果。
4实验与结果分析
实验采用KDD CUP’99[20]入侵检测数据集, 完整的训练数据集包含4 999 000条连接记录, 每条记录由42个属性组成, 其中最后一个属性描述该条记录是正常连接还是某种入侵行为, 整个入侵检测数据总共包括37种入侵行为, 这些入侵行为被分成4大类:probe, denial of service (DOS) , user.To-root (u2R) 和remote.to.1ocal (R2L) 。对应关系如下所示:
Probe:{portsweep, mscan, saint, satan, ipsweep, nmap}
DOS:{udpstorm, smurf, pod, land, processtable, warezmaster, apache2, mailbomb, Neptune, back, teardrop}
U2R:{httptunnel, ftp_write, sqlattack, xterm, multihop, buffer_overflow, perl, loadmodule, rootkit, ps}
R2L:{guerr_passwd, phf, snmpguess, named, imap, snmpgetattack, xlock, sendmail, xsnoop, worm}
从10%训练子集“kddcup.data_10_percent_corrected”中随机的抽取了18417条记录作为训练样本, 其中由于U2R类的连接记录过少, 本文抽取了“kddcup.data_10_percent_corrected”中全部的52条U2R类样本加入训练集中。
训练集中各类分布情况如下:normal:6634;dos:10827;u2r:52;r2l:396;probe:508。
测试数据则从KDD CUP’99提供的总共311029条记录的用于测试的数据集“corrected”中随机抽取了5486条样本组成测试集。
测试集中各类分布情况如下:normal:1999;dos:2608;u2r:15;r2l:89;probe:775。
为了在相同的实验环境中进行比较, 我们设计的算法已嵌入到开源软件WEKA[21]中。另外, 实验采用的计算机配置如下:CPU:Pentium (R) D CPU 2.80GHZ;内存: 504MB;操作系统:Windows XP;运行环境:JCreator Pro。实验中的所有数据均是在上述配置的计算机上运行取得。
实验中, 对所抽取的实验数据集 (训练集, 测试集) 统一使用WEKA自带的“WEKA.filters.unsupervised.attribute.Normalize”方法进行标准化处理, 同时针对训练集中u2r和r2l这两类数据过少的不平衡数据情况, 采取了一种类似于过抽样[22]的方法。即在训练基础分类器以及每次增量训练过程中, 都将全部的u2r和r2l类型的数据分给各个分类器训练, 以保证这两类数据在每个分类器中的完整性。
[实验1]在实验中, 为了模拟增量过程。将整个数据集随机地分成6份, 每份有3070个数据。其中第一份作为基础训练集, 平分5份交由KNNModel算法建立5个KNN初始模型;剩下五份作为增量数据, 每一份在对应的KNN初始模型上进行增量学习, 实验结果见表1和表2。
表1中, KNNModel的训练时间取5个KNNModel中最大的那个训练时间。测试时间为5个KNNModel中最大的那个测试时间加上融合的时间。从表1可以看出, 在基础训练集上, KNNModel较支持向量机 (SVM) , 决策树方法 (J48) 无论在训练, 测试时间上还是在测试精度上都没有太大的优势。
表2为各分类器在整个数据集上的表现, 其中iKNNModel为在KNNModel基础上经过并行增量学习及集成融合后的分类结果。其他分类器的表现均为直接在整个训练集上建立分类模型的表现。
其中iKNNModel的训练时间为在基础训练集上建立KNNModel的时间加上增量学习的时间。
对比表1, 从表2可以看出, 本文提出的增量学习算法及分布式入侵检测架构, 从一定程度上, 改善了KNNModel的分类性能。在训练时间要低于SVM和J48, 并且在精度上也可以同SVM和J48媲美。然而算法的预测时间较大, 这是由于随着不断地增量学习, iKNNModel算法建立的模型簇的数量也在不断地增加, 从而影响了预测的时间。
可见, 本文提出的分布式增量学习算法在保证相对较高的检测率的同时, 在训练时间上远小于SVM算法, 同时也低于J48算法, 较适合于数据海量增加的入侵检测等领域。
5结束语
本文提出一个基于KNNModel的增量学习方法, 并在此基础上构建一个分布式的网络入侵检测系统, 由于该系统具有分布式, 增量学习的特点, 特别适用于数据海量增加的应用领域。在KDD CUP’1999数据集上的实验结果表明了本方法的可行性。然而, 本方法对u2r和r2l的检测率仍然不高。这是由于, 这两类样本属于不平衡数据。尽管实验中对这两类数据进行了一些处理, 然而本文算法中采取的随机分割方法, 更加加剧了少量数据的不平衡性。另外, 随着不断地增量学习, iKNNModel建立的模型簇的数量也会不断地增加。在增量步数过多以后将生成过多的模型簇, 从而影响了预测时间。因此, 对生成的模型簇进行适当的合并和剪辑, 以降低模型簇的数量, 显的十分必要, 这与对不平衡数据的处理是我们下一步的研究重点。
本课题得到福建省自然科学基金No.2007J0016和教育部留学回国人员基金 (教外司留[2008]890号) 的资助。
摘要：网络异常检测技术是网络安全领域的热点问题。目前存在的异常检测算法大多属于静态分类算法, 并未充分考虑到实际应用领域中海量数据不断增加的问题。本文提出了一种基于增量KNN模型的分布式入侵检测架构, 它首先将少量的训练集均匀分配到各个节点上建立初始KNN模型, 然后再将新增的数据分割成小块数据交由各个节点并行地进行增量学习, 即对各节点的原有模型进行调整、优化, 最后通过模型融合得到较为鲁棒的检测效果, 在KDDCUP’99数据集上的实验结果验证了本方法的有效性。
一种基于KNN的文本分类算法 第2篇
一般的文本分类方法中文本的表示都是以向量的形式存在的,但是这些文本向量在空间里的分布情况究竟如何呢。目前很少分类方法会涉及到,然而有研究指出文本向量在空间中的分布是遵循一定规律的,即同类的文本向量大多数分布在同一空间区域里,而不同类的文本向量一般会分布在不同的区域里。所以本文通过引进一种基于分布域的快速KNN分类方法,并对其中的相似度算法进行改进,使得文本分类不仅在效率上有很大的提高,同时在准确度上也有所提升。与传统的KNN算法相比较,改进后的算法通过计算每个类的分布域和待分类文本向量的空间位置,从而除去相差较大的类别,只需要计算较少的文本类中的文本与目标文本的相似度,即可以判断其类别。
1 相关知识介绍
1.1向量空间模型
向量空间模型(VSM)是文档表示的一种方法,把对文本内容的处理简化为向量空间中的向量运算,并且它以空间上的相似度表达语义的相似度,直观易懂。在该模型中,文档(d)空间被映射为一个特征向量V(d)=(t1,W1(d)),ti,Wi(d),tn,Wn(d)),其中ti(i=1,2,,n)为一列互不相同的词条项,Wi(d)为ti在d中的权值,一般被定义为ti在d中出现的频率tfi(d)的函数,即Wi(d)=β(tfi(d))。在文本分类中常用的词条权值计算方法有对数函数,布尔函数和TFIDF(词频-逆向文本频率)函数等。其中TFIDF最常用,即β(tfi(d))=tfi(d)log(N/ni),其中N为所有文档数目,ni为含有词条ti的文档数目,由公式可以看出此函数综合考虑了词在单个文档和整个文档库中的权值。
1.2基于KNN的文本分类方法
KNN算法的基本思想是:如果一个待测文本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个文本类,那么此文本即属于这个类别。
KNN算法的具体步骤如下:[2]
1)将待测的文本表示成特征向量d。
2)计算d与样本集S中每个文本向量的相似度(常以欧式距离或者余弦距离来表示),选取与向量d相似度最大的k个样本向量作为d的最近邻文本。本文选择的相似度计算方法为:
Wli表示文档d1中第i个特征项的权重,δ为两文本向量内积与相同特征项个数的和。
3)文本向量d属于类别Cj的权重计算方法为:
sim(di,d)代表d与其k个最近邻文本中样本di的相似度,φ(di,Cj)的取值为1或者0,即:如果di∈Cj,则φ(di,Cj)=1,反之则φ(di,Cj)=0。
4)最后比较计算出的权重W(d,Cj),待分类样本d属于W(d,Cj)值最大的那个文本类别。
2 改进的KNN文本分类方法
2.1 改进的KNN算法
1)对于空间中文本向量的分布情况,首先介绍一下分布域的概念:[2]
在文本向量空间中,非空子空间U称为文本类C的分布域,如果U满足条件:能将类C中的文本向量全部包含在内。
改进算法的步骤:
(1)计算出每个类的分布域;
(2)计算出待测文本向量d在样本向量空间中的位置;
(3)计算出d位于哪些类的分布域之外,在计算d的K个最近邻向量时,排
除与这些类中所有向量之间的距离计算,然后根据新相似度算法以及公式(2)判定d的所属类别。(4)
(4)算法结束。
2)分布域的计算方法
训练样本的有限性以及噪音数据的存在,导致在计算分布域时只能给出近似值,影响了改进算法的分类准确率,不过在实际的操作中,这种误差的存在是不足以影响改进算法的可用性的,故而可以忽略掉。
计算分布域:[2]
设全体样本集中文本向量集合T,分布在样本空间V中,其中共有n个文本类,分别用C1,C2,CiCn表示;类Ci的中心向量表示为O(Ci)。用U(O(Ci),r)表示样本向量的分布空间,其中以O(Ci)为中心、r为半径。由E(U(O(Ci),r))来表示分布在该空间中的文本向量集合。由大量的实验数据[2]表明文本向量集T的空间分布有如下的规律:Ci中的大部分向量聚集在O(Ci)的周围,即比其它类中的向量与O(Ci)的距离近。也就是说随着r的减小,E(U(O(Ci),r))中的属于类Ci的文本向量比率会变高,反之则会变低。
据上述说明,我们采用如下方式来计算各类别的近似分布域值:设定阈值t(0
这里采用的r的计算算法为:
字母含义:M里存放的是按照与O(C)之间距离升序排列的训练样本集C内各向量,N是C中的向量个数,Num(i)代表D中落在U(O(C),r)空间中的个数,dist(di,O(C)代表di与O(C)之间的距离。
3 实验结果
本文就算法进行实验,分别考察了改进前与改进后算法在效率和准确率方面的性能。实验数据以搜狗互联网语料库为样本语料库,共采用了4900篇文档,其中训练文档3500篇,测试1400篇。涵盖了文化、IT、财经、教育等7个类别。生成文本向量时,特征加权算法采用的是TFIDF,特征向量维数为500,K值取30,权重判定公式(2)中相似度函数取sim(di,d)即公式(1)。改进算法的效率、准确率均和传统KNN做比较,实验结果数据如下:
表1为改进算法前。
表2为改进算法后。
表3为改进算法后(但相似度算法不变)。
由表可知,就本文所改进的KNN算法,较传统的KNN算法准确率平均低约2个百分点,但是效率较前者能提高将近一倍的时间,其中相似度算法的改进帮助新算法提高了将近2个百分点的准确率。故而本着实用的态度这种准确率的小小损失是允许的。
4 总结
本文提出了一种KNN快速分类算法。根据文本向量在空间的分布特点,计算出各类的分布域,在寻找待分类文本向量的K最近邻时,确定了待测样本的大致范围,减少了对样本集的搜索计算,从而大大提高了KNN的效率,并改进了相似度的算法,使得准确率也有所提高。
参考文献
[1]刘慧,杨宏光.应用于中文文本分类的改进KNN算法[J].科苑观察,2010(8).
KNN模型论文 第3篇
KNN分类算法是一种易于理解和实现的算法, 其基本思想是在训练样本中找到测试样本的k个最近邻, 然后根据这k个最近邻的类别来决定测试样本的类别;KNN分类是一种基于要求的或懒惰的学习方法, 它存放所有的训练样本, 直到测试样本需要分类时才建立分类, 由于现在的计算机有强大的计算性能, KNN算法的较差的时间性能已不在是太大的问题;但是, 训练样本分布的不均匀性也会造成分类准确率的下降。
本文提出了一种基于相对距离的KNN算法, 在计算测试样本与训练样本之间的距离时, 利用相对距离进行计算。实验结果显示削弱了训练样本分布的不均匀性对分类性能的影响, 提高了分类的准确率。
1 训练样本分布不均对分类结果的影响
KNN方法实际上是一种基于类比的学习方法, 这就要求训练样本中样本必须具有代表性, 这种代表性不仅应该体现在样本间的距离 (或相似度) 上, 还应该体现在样本分布的均匀性上。为了描述方便, 下面我们以二维空间两种分类为例, 看一下训练样本的分布密度对KNN分类器分类结果的影响。从图1我们可以看到KNN方法存在以下问题。在类边界区域, 训练样本分布的不均匀性可能会造成测试样本类别的误判。在图1中, 我们可以直观地看到测试样本应该属于类2, 但是由于类1比类2的分布密度要大, 这样当我们选测试样本的7个最近邻来判别它的类别时, 分类器就出现了误判, 如果k值更大些, 则误判更为明显。而在实际设计分类器的时候, 由于一些类别比另一些类别的训练样本更容易获得, 往往会造成训练样本分布的不均匀, 而且, 即使训练样本在各个类中的数目基本接近, 由于其所占区域大小的不同, 也会造成训练样本分布的不均匀。
针对训练样本分布不均时KNN分类算法中容易出现误判的问题, 本文提出基于相对距离的KNN算法。其基本思想是:首先计算训练集各个类的1-最近邻距离均值;然后对测试样本利用相对距离进行KNN分类。
2 基于相对距离的KNN算法
2.1 相关概念
为便于描述, 我们引入以下一些概念:
给定一个样本集D={X1, …, XL}, 其中Xi∈Rn, i=1, …, L;设样本共有Class Num个类;设Ci表示第i类中的所有样本的集合, 且Ci∩Cj=Φ (i, j=1, …, Class Num) , 样本集也可表示为:D=C1∪C2∪…∪Cr。
定义1两个样本间的距离, 设数据集D有m个属性, 其数据库模式为R (A1, A2, …, Am) , X (x1, x2, …, xm) 和Y (y1, y2, …, ym) 分别为数据集D中的两个样本, 则X与Y的距离度量公式为:
一般来说, 我们习惯使用欧几里德距离, 即取ρ=2。
定义2设Dist (X, Y) 代表样本集D中两个样本X和Y间的距离, 则测试样本中第i类的1-最近邻距离均值为:
Ki为Ci中的样本个数, Y为Xj的最近邻。
定义3设Dist (X, Y) 代表样本集D中两个样本X和Y间的距离, 测试样本X和训练样本Y之间的相对距离为:
在执行这三部分之前, 首先分别对训练样本集和测试集进行规范化, 规范化的目的主要是避免由于属性值域不同而影响样本距离的计算, 进而影响分类的结果。
2.2 算法描述
2.2.1 训练样本和测试样本的规范化
处理方法:样本规范化操作可在样本数据库中直接利用SQL语句完成:
(1) 利用select语句求出每个属性的最大值 (Max函数) 、最小值 (Min函数) , (2) 利用update语句修改每个属性的值。设样本X的第i维属性值为X[i], Max[i]、Min[i]为第i维属性上的最大值、最小值, 则利用公式:更新原属性值, 其值域为[0, 1]。
2.2.2 求训练样本集中每个类别的1-最近邻距离均值
每个类别的1-最近邻距离均值反映了类中样本的紧密程度, 其值与样本的分布密度成反比例关系。
输入:规范化后的训练样本集D={X1, X2, …, Xn1}, n1为训练样本的个数;类别数Class Num。
输出:每个类别的1-最近邻距离均值, 放在数组Avg Dist中, Avg Dist[i] (i=1, 2, …, Class Num) 表示第i类的1-最近邻距离均值。
算法描述:
2.2.3 对测试样本P采用相对距离进行KNN分类
输入:待分类样本P。
输出:P的类别。
算法描述:
算法2.2
2.3 算法分析
(1) 求训练样本1-最近邻距离均值的时间复杂度为O (n12/2) , 其中, n1为训练样本的个数。 (2) 对样本进行分类的时间复杂度为O (n1) , 其中, n1为训练样本的个数。 (3) 对测试样本集进行分类, 计算算法的准确率的时间复杂度为O (n1*n2) , 其中, n1为训练样本的个数, n2为测试样本的个数。
3 实验结果
为验证本文提出的基于相对距离的KNN分类算法的正确性和有效性, 实验在著名的iris数据上进行, iris数据是来自于UCI[46]上的开放数据, 通常用来验证分类算法。实验环境如下:计算机配置:CPU 2.4GHz, 256MHz内存, 硬盘60G, 操作系统:Microsoft Windows XP, 开发软件:Delphi 6.0, Microsoft SQL Server 2000。
实验表明, 改进的KNN分类算法能提高分类的准确率。
4 结束语
尽管基于相对距离的KNN方法改善了样本分部不均带来的误分类问题, 提高了KNN分类器的准确率, 但是仍有一些地方需要进行探讨和改进。该算法仅适用于训练样本分布不均且边界较为明显的情况;在计算类内最近邻距离均值时是采用1-最近邻均距离值还是K-最近邻距离均值, K为何值效果最佳等需要进一步研究。
参考文献
[1]杨建良, 王永成.基于KNN与自动检索的迭代近邻法在自动分类中的应用[J].情报学报, 2004, 23 (2) :137-141.
[2]李永平, 程莉, 叶卫国.基于隐含语义的KNN文本分类研究[J].计算机工程与应用, 2004, 40 (6) :71-73.
[3]Chawla NV, Japkowicz N, Kotcz A.Editorial:Special issue on learning from imbalanced data sets.Sigkdd Explorations Newsletters, 2004, 6 (1) :1-6.
[4]赵秦怡, 王丽珍, 顾应龙.基于邻接图的空间分类算法的改进[J].计算机应用研究, 2004 (9) :115-117.
[5]L.Wang, K.Xie, T.Chen, X.Ma.Efficient discovery of multilevel spatial association rule using partition.Information and Software Technology (IST) .Volume 47, Issue 13:829-840, October2005.
[6]Y.Yang, C.G.Chute.An example-based mapping method for text categorization and retrieval.ACM Trans on Information Systems, 1994, 12 (3) :252-277.
[7]A Fuzzy K-Nearest Neighbor Algorithm.Review and Critical Analysis.Matthew Kerwin (.9813085234.) .17-Nov-2005.
[8]李荣陆, 胡运发.基于密度的kNN文本分类器训练样本裁剪方法[J].计算机研究与发展, 2004, 41 (4) :539-546.
[9]Chenyi Xia, Hongjun Lu, Beng Chin Ooi, Jing Hu:GORDER:An Efficient Method for KNN Join Processing, VLDB2004:756-767.
KNN模型论文 第4篇
随着物联网的发展, 位置服务 (LPS) 受到人们越来越多的关注, 对移动目标定位方法的研究也随之深入。针对室内复杂环境的定位技术一直是研究的难点。目前, RFID定位技术[1]以其非接触、非视距、高灵敏度和低成本的优点, 正在成为室内定位系统的优选技术, 受到了更多的关注。目前, 出现了许多利用RFID进行定位的定位系统, 如LANDMARC[2]、Spot On[3]、BVIRE等。K-最近邻算法 (KNN) 作为常用的定位算法, 通过比较目标节点信号强度值 (RSSI) 与各个参考节点信号强度值 (RSSI) 的相对大小, 计算目标节点的坐标。由于RSSI容易受环境中温度和噪声的影响, 在选择K个参考节点时常常会包含那些偏离目标节点较远的参考节点, 对定位精度造成很大影响。本文针对K-最近邻算法存在的这些问题提出一种改进方法, 首先利用传感器信息建立网络协助, 确定目标节点所在的区域, 计算目标节点的初步坐标, 最后利用Taylor级数展开方法对坐标迭代, 得到目标节点的精确位置, 提高定位精度。
1 K-最近邻定位算法
在公式 (1) 中Ei表示第i个参考节点与目标节点之间的距离大小, Ei越小表示距离越近, 。通过比较Ei值的大小, 将K个离目标节点最近的参考节点 (即最近邻节点) 放入同一集合, 并定义K个最近邻节点的权值为
则目标节点的位置坐标表示为
在公式 (3) 中, 表示第i参考节点的坐标, 。
2 改进KNN算法
2.1 利用传感器建立网络协助
首先利用传感器信息将环境区域划分为多个分区。在初始化阶段中, 首先在静态环境 (没有定位目标和噪声的干扰) 下, 通过传感节点建立静态表 (即在静态环境下传感节点与其它传感节点之间的平均信号强度) , 并存储静态RSSI值。当待定位的目标节点在传感网络覆盖区域内时, 传感节点之间的RSSI值会出现波动。当无待定位目标节点时, RSSI会出现3~5d Bm的波动;当有目标节点时, RSSI值在18~20d Bm之间波动。所以根据RSSI值的波动值大小确定有效链路。如果某一链路的RSSI波动值大于18d Bm值, 表示该链路为一个有效的链路[4]。
定位阶段利用交叉方法确定待定位目标节点所在分区, 当某一分区内存在多条有效链路, 则表示待定位目标节点在该分区内。通过对每个分区分配权值, 权值越大则越靠近待定位目标节点。对所有交点的权值取平均值来计算定位节点的位置。
假设传感器网格有c个分区, 每分区的权值Wi, 对于所有分区的权值可以表示为一组, 则Wi表示为:
其中, 和表示第i个分区内有效链路交叉点的动态RSSI, Z表示为链路交叉点集合, Wi值最大的分区则是目标节点所在分区。当确定在某一分区时只激活该区域内的参考节点, 选择分区内利用KNN算法选取k个参考节点作为定位节点, 剔除远离目标节点的参考节点, 在分区内取k个最邻近参考节点就可以利用公式 (3) 计算待定位节点的位置, 可得到初始估计位置。
2.2 Taylor级数展开法
假设参考节点与目标节点的距离为di, 可得到参考节点与目标节点之间实际距离和估计距离之间的差值如式:
根据 (3) 计算出的定位节点坐标作为初始值, 将式 (5) 在点处用Taylor级数展开并只保留到一阶偏导数项, 得下式
为使公式整洁, 上式 (6) 中后两项的Fi表示。当测量距离与估计距离之间距离差为足够小时说明估计点准确, 于是可将 (6) 式写成矩阵形式:
3 实验验证
通过图2可以看到, 在同样环境下, 使用最近邻居算法定位的平均估计误差是1.34m, 最大平均估计误差是2.2m;使用本文改进算法定位的平均估计误差是0.95m, 最大平均估计误差是1.8m。同时对位于边界的 ( (1) (2) (3) ) 节点的两种定位方法误差进行对比, 可以看出, 本文提出的算法跟最近邻算法相比在边界定位方面同样具有很好的效果。而通过图3可以看到, 对比LANDMARC系统的最近邻算法和本方法可以发现, 统计误差小于1m, 仅用KNN算法的累积误差概率为82.5%, 而本文提出的方法为89.2%, 由此看出后者具有较好的定位精度。之后还对两种算法的计算效率进行了对比, 利用KNN定位算法和本文提出的定位算法计算100个目标节点, 各自所需时间如图4所示
从图4可以看出本文提出的改进算法比典型的KNN算法在计算时间明显减少很多, 而且参考节点数目越多, 效果越显著。实验结果表明, KNN算法通过计算目标节点的最近邻节点数目进行定位, 参考节点越多, 计算花费时间越多, 而本文提出的改进方法利用建立传感网络协助, 这样就减少要计算的参考节点数目, 进而减少了所需计算时间, 提高了算法的效率。
4 结束语
本文基于最近邻定位算法, 提出了一种改进算法, 直接消除了远离目标节点的参考节点, 缩小了k值的选取范围, 克服了随机误差, 减少了算法的计算量, 并对边界定位具有很好的效果。本文的测试是在实验室的环境下模拟真实的环境中进行的, 贴近实际应用的室内环境。实测表明本文提出的改进算法精度在1.5m以内, 定位的最大误差减小, 且平均精度较之原算法有了很大的提高。
参考文献
[1]李程, 钱松荣.射频识别动态定位方法[J].通信学报, 2013, 34 (04) :144-148.
[2]秦爽.参数化多维标度定位方法研究[D].成都:电子科技大学, 2013.
[3]SANSANAYUTHT, SUKSOMPONG P, CHAREONLARPNOPPARUT C, et al.RFID 2D-localization improvement using modified LANDMARC with linear MMSE estimation[C].Communications and Information Technologies (ISCIT) , 2013 13th International Symposium on.IEEE, 2013:133-137.
[4]朱剑, 赵海, 张希元等.基于LQI量度的无线链路质量评估模型[J].东北大学学报:自然科学版, 2008, 29 (09) :1262-1265.
KNN模型论文 第5篇
KNN是最著名的模式识别统计学方法之一[1],凭借着在分类过程中优良的健壮性、稳定性及实现方法的简单性,成为国内外学者的研究热点。其主要特点可以概括为第一,根据样本所有的特征值来计算样本间的距离,减少了类别特征选择不当造成的不利影响,可以最大程度地减少分类过程中的误差项;第二,KNN的分类判断过程不依赖对基础数据的严格假设,能适应任何情况[2,3]。但是,由于KNN本质上是一种基于实例的懒惰学习方法,极易受个体特征值干扰,分类时会出现一些明显的弱点:一是KNN的分类性能受到训练样本分布情况的影响较大。这是因为KNN的距离机制是以样本的特征值为参数的,一旦数据分布不均匀,大类别样本就会占有密度优势,从而导致其包含的特征参数出现频率也随之提升。然而在实际应用中,不同的特征参数对分类的影响力是不相同的,即特征参数出现频率的高低与分类相关度强弱关联不大。因此,当数据分布倾斜现象严重时,KNN分类性能可能较差。二是KNN相似性的计算过程均是在分类时才开始进行,而分类过程又需要逐个计算待分样本与训练集每个样本的距离,如果距离机制的定义过于繁琐,对于海量数据,算法的时间效率会非常低。综合上述,距离机制是KNN性能的关键,研究KNN的距离机制,在保证分类速度的同时,提高分类的准确性具有重要的理论意义和应用价值。近年来学者们就如何提高KNN的分类性能提出了许多针对距离机制的改进算法,这些方法主要是基于粗糙集理论[4]、PAC算法[5]和神经网络理论[6]等。文献[7]提出一种基于相同特征值信息熵的类可信度计算方法(Entropy-KNN),以提高分类准确率,其距离机制只考虑同一属性下相同的特征参数,利用信息熵的大小确定特征参数对分类的重要性,却忽略相关性,即省略了特征参数针对分类的一些极端情况,大多数情况下会导致样本间距离比实际要小,但由于该算法最终的分类判断是通过类可信度综合考虑各类邻近样本点个数和待分样本与相似样本间的类别平均距离两重因素,因而算法的准确率较高;文献[8]首先把条件属性的信息增益值作为裁剪特征维数的依据,简约特征属性,然后根据保留下来的条件属性的相关度大小,为其赋予相应的权重,最后仍采用欧式距离机制计算样本间的距离。这种方法的分类性能较好,原因在于其充分考虑了条件属性相关度与权重内在的联系。其不足之处在于如果样本特征维数裁剪过多,势必会引起分类准确率下降,同时由于信息增益、欧式距离机制的计算过程相对繁琐,该方法的分类计算量也相对较大。
本文在上述研究的基础上,针对KNN分类准确率和样本规模、特征维数之间的关系,引入信息学中熵理论,提出了一种采用特征参数类相关度差异优化距离的方法。改进的距离优化方法将类相关度的概念延伸至每个特征参数,认为分类过程与每个特征参数都存在不同程度的关联,并将此方法与KNN规则结合,通过新的距离定义从根本上保证KNN分类的准确性及效率。利用UCI数据库中Adult数据集、Abalone数据集进行实验,仿真结果显示改进算法在分类效率上与目前其他KNN算法相当,准确性则明显优于其他算法。
2 KNN算法
KNN分类算法的主要思想是:先计算待分类样本与已知类别的训练样本之间的距离,找到距离与待分类样本数据最近的k个邻居;再根据这些邻居所属的类别来判断待分类样本数据的类别。如果待分类样本数据的k个邻居都属于一个类别,那么待分类样本也属于这个类别[8]。否则,以k个邻居中占多数的类别来确定待分类样本就属于哪个类别。对于离散型数据集,KNN算法主要采用统计特征参数个数作为距离,然后加权平均的方法,对于数值型数据集,主要采用马氏距离来确定样本的距离,其计算公式为
undefinedundefined
式(1)中undefined和undefined代表两个样本数据,n为样本特征属性个数。
作为一种有监督的机器学习的非参数方法,KNN分类器在分类方面效率高,使用简便。但是该算法的一个明显的弱点是其分类效率受到训练样本分布情况的影响较大,当数据分布倾斜现象严重时,其分类性能可能变得很差。体现在KNN距离机制是由样本的所有特征属性按照相同度量确定的,这就很可能直接影响分类的有效性和准确性。
3 类相关度差异优化距离的KNN改进算法
3.1 特征参数类相关度差异优化距离机制
(1)特征参数ti对分类的相关度undefined的定义。设X是训练样本集,它包含了n个不同类别的样本,这些类别分别用C1,C2,Λ,Cr,Λ,Cn表示,样本记为undefined。设Xi具有q个特征属性undefined, Ap具有v个特征参数undefined,undefined记为具有特征参数ti样本的个数,undefined记为特征参数ti在Cr类样本中出现的次数,则特征参数ti的类相关度(期望信息)为
undefined
其中,undefined为具有特征参数ti样本的概率,undefined为特征参数ti在Cr中出现的概率;undefined熵值体现了特征参数ti对样本隶属的期望值,是特征参数ti对分类作用的不确定性的度量,e(ti)越小,ti对分类的作用越大。当undefined时,e(ti)0,ti对样本隶属类r完全确定。以e(ti)为主体,当e(ti)=0时,undefined值无意义,即特征参数ti对样本隶属类r明确,与样本的分布无关联。
(3)样本间的距离undefined的定义。
undefined
undefined
其中,Xundefined是样本Xi特征参数相关性的转化,Xundefined是样本Xj特征参数相关性的转化,将特征参数类相关度值替代马氏距离机制中原数据的特征,并赋予相应的权重值以计算样本间的相似程度。由于特征参数相似性是分类训练器中潜在的关联关系,它的存在可以减少样本间的距离的计算误差。因而,类相关度能有效地度量样本间特征的相似程度,进而最大程度地提取与待分样本相似的近邻样本,从而得到正确的分类结果。
3.2 特征参数类相关度优化距离的K最近邻改进算法
针对引言中KNN算法分类准确性和效率的弱点,采用一种新的数据预处理机制改进算法,将3.1提出的特征参数类相关度概念引入KNN分类。大量的研究表明,训练数据的类别如果不再细分的话,类别数不是很多,特征参数的重复率也较高,尤其对于一些常用的数据更是如此。如果使用降维方法对数据进行相似度计算,总会因为数据向量维数偏低或维数不适中而丢失过多的,甚至是重要的特征信息,从而影响分类效果。基于此因素考量,改进算法仍采用传统KNN算法中将训练集样本与待分样本的所有特征属性值均作为相似度计算参数的模式,主要通过优化距离机制,从根本上保证KNN分类的准确性及效率。
采用类相关度优化距离的KNN改进算法的实现:
4 实验与分析
为了验证特征参数类相关度优化距离-KNN改进算法的有效性及准确性,同时为了保证实验数据具有一定的代表性,选用以下2个人工实验数据集:由Ronny Kohavi and Barry Becker提供的Categorical型Adult数据集;由Sam Waugh提供的Real型Abalone数据集,其描述情况均由UCI数据库www.ics.uci.edu提供。表1具体给出了Adult数据和Abalone数据的具体描述。
4.1 有效性对比实验
所有实验在Adult、Abalone数据集上进行。实验分两种情况①小样本训练集数据的情况;②大规模训练集数据的情况。KNN算法中K是非常重要的参数之一。为了确定参数K,同时也为了保证实验的有效性,按传统加权-KNN、马氏距离-KNN进行K值选择实验。随机抽取Adult(训练样本Train1=3000,测试样本Test1=1000),Abalone(训练样本Train2=1000,测试样本Test2=200)进行验证。对Adult数据集,当K=15时,加权-KNN取得最高准确率,当K>25后,分类效果大幅度下降;对Abalone数据集,当K=10时,马氏距离-KNN取得最高准确率,当K>20后,分类效果不佳。分析认为,由于所用Train1中最小样本类别中的样本数量为25,Train2中最小样本类别中的样本数量为20,当K>25(Adult数据集)、K>20(Abalone数据集),KNN算法找到的近邻样本中错误类别的训练集样本居多,造成噪声过多从而影响分类效果的降低。同时,由于KNN具有趋强弃弱的缺点,较大的K值也容易导致样本被错分到样本较多的类别中去,因此设置 K=15(Adult数据集),K=10(Abalone数据集)进行有效性对比实验。图1,图2显示了考察训练集大小对分类性能影响的趋势。
实验结果分析与说明如下:①对于多维度的Adult数据集,基于分类相关度距离机制-KNN算法的有效性非常明显,错误率远远低于其他算法。主要原因在于加权-KNN的相似度计算对属性维度比较敏感,当维度属性彼此没有相关性,找到的“近邻”就不是真正的“近邻”,即判断近邻的距离度量不涉及特征参数之间的关系,这使得距离的计算不精确,从而影响分类的精度。而Entropy-KNN的距离度量只关联相同特征参数对分类的重要性,这也造成了距离的计算值比实际值要小,使得分类性能下降;②对于维度偏低的Abalone数据集,虽然样本的维度彼此不会表现出太多的不确定性,分类模式的特征参数也相对容易确定,但由于马氏距离-KNN及Entropy-KNN的模式识别方式相对单一,使得样本间分类相似性的效果并不明显,而基于分类相关度距离机制-KNN算法不依赖于数据的具体特征参数,因此其性能仍优于马氏距离-KNN及Entropy-KNN两种算法。
4.2 分类相关性能对比
分类效果评估指标使用常用的差准率、查全率以及F1测试值:
查准率=分类的正确样本数/实际样本数
查全率=分类的正确样本数/应有样本数
undefined
从表1及表2的对比实验结果可以看出,采用类相关性优化距离机制-KNN改进算法较传统加权-KNN、马氏距离-KNN分类效率(时间复杂度都属于平方级)相当,别但综合指标F1大约有0.6%～0.8%左右的上升,分类准确率也有明显的上升,可以认为类相关性优化距离机制-KNN的分类效果已接近或者达到支持向量机SVM算法的效果。
5 结束语
分类的准确性和效率是KNN算法的两个核心内容。本文在样本距离机制方面进行了研究,提出了一种采用类相关度优化距离的改进KNN分类算法。算法在对待分样本进行分类前,先对特征参数进行预处理操作,即首先根据各特征参数的相关度值进行特征参数向量化处理,然后由相关度计算其值,建立不同特征参数间针对分类所产生的不同影响程度的内在模型。仿真实验表明,该算法在保证KNN分类效率的同时,大幅度提高了分类的准确性。采用类相关度优化距离的KNN算法解决了样本分类性能的瓶颈,根据训练集训练样本的不同分布状况构造合适的分类相关度成为了影响分类效果的重要因素,提高了算法在小样本、样本分布不均等环境下的适应能力。
参考文献
[1]Yang Y.An evaluation of statistical approaches to text categorization[J].Information Retrieval,1999,1(1):76-88
[2]Vries A D,Mamoulis N,Nes N,et al.Efficient KNN search on vertically decomposed data[C]∥Proceedings of the2002ACMSIGMOD International Conference on Management of Data,Madison,Wisconsin.Madison:ACMPress,2002:322-333
[3]Joachims T.Text Categorization with Support Vector Machines:Learning with Many Relevant Features//Proc of the10th European Conference on Machine Learning.Chemnitz,Germany,1998:137-142]
[4]Pawlak Z.Rough sets[J].International Journal of Computer Information Science,1982,11(5):341-356
[5]Martinez A M,Kak AC.PCAversus LDA[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,23(2):228-233
[6]王煜,张明,王正鸥等.用于文本分类的改进KNN算法[J].计算机工程与应用,2007,43(13):159-166
[7]童先群,周忠眉.基于属性值信息熵的KNN改进算法[J].计算机工程与应用,2010,46(3):115-117
KNN模型论文 第6篇
1、KNN算法
近邻法 (nearest neighbor, NN) 是在模式识别中广泛使用的分类方法。KNN (K nearest neighbor, KNN) 是最近邻法的一个推广。其基本思想是:首先产生训练集, 然后以训练集的分类为基础, 对测试集每个样本寻找K个近邻。
在训练集中, 每个例子x都被表示为特征向量
判断近邻就是使用欧氏距离测试两个例子之间的距离, 数值越小表明相似性越大, 反之说明相似性越小。
K近邻算法比较简单, 但当文本训练集较大时, 计算量较大, 大大降低了了分类效率。另外K的取值很难确定, 需要经过不断实验才能得到合适的取值。
2、粗糙集概述
粗糙集理论是有波兰华沙理工大学教授Z.Pawlak于1982年提出的。粗糙集方法可以去掉冗余属性, 进行属性约简, 还可以用决策规则集合的形式表示最重要属性和特定分类之间的所有重要关系。把该理论应用在文本分类的训练阶段, 用粗糙集的属性约简算法实现规则的提取。
(1) 信息系统粗糙集理论研究的对象是一个由多值属性集合描述的对象集合信息系统。一个信息系统S是一个四元组:S= (U, A, V, f) 其中:
U是对象的集合即论域, 如:U={e1, e2, ..., en};
A是属性的有限集合, 如:A={a1, a2, ..., am};
V是属性值的集合V=∪a∈AVa, 而Va是属性a∈A的属性值域, 表示属性a的范围;如:a1={e1}, a2={e2}, a3={e3, e4}。则V={a1, a2, a3}={e1, e2, e3, e4};
f:UAV的映射, 称为信息函数, 它指定U中每一个对象x的属性值。如:f (e1, a1) =1, 表示对象e1在属性a1处的值为1。
(2) 不可分辨关系与决策表的定义不可分辨关系:对于某个属性子集BAR=U*U, 如果IND (B) ={ (x, y) β (x, y) ∈U2, Pb∈ (b (x) =b (y) ) }, 则称IND (B) 为一个等价关系。
决策表:决策表就是信息系统S= (U, A, V, f) , A=C∪D是属性集合, C是条件属性, D是决策属性, 且D不为空。在文本数据的决策表中, C是特征项的集合, D是文本类别的集合。C和D的等价关系IND (C) 和IND (D) 的等价类分别称为条件类和决策类在文本的规则分类中, 从文本中提取的关键词向量用做规则的前提条件, 文本所属的类别用做规则的决策。
(3) 决策表的属性约简决策表属性约简的目标就是从条件属性集合中找到必要的条件属性, 使得在这些条件属性中形成的相对于决策属性的分类和所有条件属性所形成的相当于决策属性的分类相一致。
决策表属性约简的步骤为:从决策表中消去某些列;去掉重复的行;消除掉属性的冗余值。
3、基于粗糙集的KNN的分类模型
本模型如图1给出了分类过程, 包括粗糙集的预处理和KNN分类两部分。分类包括:输入Web文本的训练集合测试集, 然后进行文本预处理和分词, 经过特征选择和权值的离散化, 构造决策表, 把粗糙集作为预处理, 对决策表的属性约简, 然后再用KNN进行分类。把粗糙集作为KNN方法的前端处理器, 可以减少KNN的输入量, 节省了计算时间, 同时一定程度上也避免了训练模型的过拟合现象, 尽管这样, 分类性能并没有降低。
通过实验验证了该方法在准确率和查全率明显提高;而且极大降低了算法的计算量, 分类效率大大提高了。
参考文献
[1]旺建华.中文文本分类技术研究[D].吉林大学.2007.
[2]白凡.改进的K近邻算法在网页文本分类中的应用[D].安徽大学.2010.
KNN模型论文 第7篇
KNN算法首先找到与待分类样本距离最近的K个近邻邻居,然后根据这K个邻居的类别,采用多数投票表决的决策规则确定待分类样本所属类别[8]。然而,实际分类当中,由于不同的样本数据分布呈现不规则性以及数据分布的复杂性,可能导致使用经典KNN算法时出现样本被错误分类的情况,进而导致分类器性能下降[9]。针对上述造成KNN算法分类精度下降的问题,不少学者提出了相关改进方法。李陆荣,等在文献[10]中提出了一种基于密度的KNN分类器训练样本裁剪方法,降低KNN算法的计算量的同时使样本的分布尽量均匀,但是删减训练样本会损失一部分分类信息,不利于提高分类精度;文献[11]中就KNN分类器类倾斜现象展开研究,提出了一种处理类倾斜问题的方法,取得较好的分类效果;沈志斌,等人针对经典KNN算法具有趋强弃弱的特点,对经典KNN算法进行了改进[12];刘海峰,等在传统KNN算法中引入权重系数对高密度类别样本的重要程度进行抑制[13]。但是上述这些算法研究的侧重点只放在不同类的类间倾斜度问题上,而实际上同一个类内部样本数据的分布情况也在某种程度上影响着分类器的性能。
现针对分类时存在类间偏斜和类内样本数据分布密度不均匀的现象展开讨论,并在此基础上提出基于决策域内局部密度的改进KNN算法,最后应用UCI标准数据集对该算法进行测试,结果表明,该算法能够提高分类器的分类性能,该算法可行。
1 KNN算法及样本分布对KNN算法的影响
1.1 经典KNN算法
给定训练数据集为
式中(xl,ωj)表示一组样本对,xl=(xl1,xl2,…,xl N)T是第l组训练样本,为N(N>1)维欧式特征空间的一个向量;ωj是样本xl的类别。
当出现待分类样本y=(y1,y2,…,yN)T时,首先计算该样本与各训练样本之间的相似度函数sim(y,xl),N维欧式空间通常使用欧氏距离来构成相似度函数[14,15]。接着找出与待分类样本相似度最大的k个样本,最后将未知类别样本y的类别class(y)决定为k个近邻样本类别较多的那一类,即
式中j=1,2,…,C,I(xl,ωj)是类别属性函数,当xl∈ωj时I(xl,ωj)=1,否则I(xl,ωj)=0。
1.2 样本分布对KNN算法分类结果的影响
KNN方法基于类比学习,在基于统计的模式识别中非常有效,对于未知和非正态分布的数据分类准确度较好,具有鲁棒性、概念清晰等优点。不过,K近邻算法的分类效率受样本的分布情况影响较大,当样本数据分布较复杂时,KNN算法的误分率会随之增加。
1.2.1 类偏斜对分类结果的影响
在分类问题中,类偏斜问题是指某些类的样本要比其他类的样本多[16]。AAAI及ICML会议分别在2000年及2003年设立了专题研讨会来研究数据集偏斜问题。这些研讨会及其后的e-mail讨论(email discussion)、信息查找请求(information seekingrequests)专题研讨说明类偏斜问题无时不在、无处不在[17]。
在类偏斜问题中,通常所说的正例为小类、少数类或稀有类,而负例为大类、多数类或普通类。训练数据集出现类偏斜问题时分类器将被大类控制,忽略小类,从而导致分类器性能恶化。该问题在实际应用中普遍存在,如在(信用卡、保险)欺骗检测、入侵检测、风险管理、医疗诊断P监控、油轮漏油检测、文本过滤等问题中比较普遍。在许多领域,类偏斜问题是内在的。有些领域如连续e-mail讨论,由于隐私问题很难收集到数据,从而导致“人工”偏斜问题。
1.2.2 决策区域内各类的局部密度对分类结果的影响
训练样本的分布不平衡还体现在各类的局部密度不一致上。文献[10—13]就KNN算法具有趋强弃弱的缺点,对大数量和高密度类别样本造成的数据倾斜现象所导致的KNN错分类进行了分析,提出了相应的KNN改进方法。但是上述文章中所提到的改进算法仅以每一类的样本数据作为整体进行数量与密度的讨论,它们的前提是假设每个类中样本分布是均匀的,即各类的样本分布密度是常数。在实际中,由于获取训练样本时技术、环境等方面的限制,训练样本的分布往往是不均匀的,这种不均匀既体现在不同类的样本数量不均衡上,又体现在同一类中数据分布密度不一致上。因此,每一类的样本分布密度并非常数,也就是说在每个类的不同区域内的密度是不同的。图1是一个二维空间的二分类问题。可以看到,本应分别属于类别2和类别1的待分类样本X和Y,由于两种类别分别在X和Y的近邻决策区域内的密度不同,产生了大密度占优的现象,使得X和Y的类别被错分。
2 基于决策域内局部密度的改进KNN算法(PD-KNN)
2.1 决策域范围内局部密度与密度补偿系数计算
这里的决策域是指待分类测试样本的k个近邻样本所组成的区域。某一类别在决策域内的局部密度可以用该类在决策域内形成的类超球体中单位区域的平均样本数来表示。
假设测试样本为yi,其k个近邻所决定的N(N>1)维超球体决策域为
式中xfathest是到测试样本yi距离最远的近邻点。
测试样本yi的近邻样本中所有属于类别ωj的样本组成的集合表示为
Sij={xl|xl∈ωj,xl∈Train且xl∈Ψ(yi,k)}。
设FD(Sij)和NH(Sij)分别表示集合Sij中所有样本向量各最大分量值、最小分量值所分别组成的向量,则ωj类在测试样本yi的决策域Ψ(yi,k)形成的类超球体的半径可以表示为
若集合Sij的近邻样本数为num(Sij)。那么,类别ωj在决策域Ψ(yi,k)内的密度为
由于各类别在决策域内局部密度一般不同,因此,为削减局部高密度类别在KNN算法决策阶段占优的情况,给出局部密度补偿系数τij,引入该系数意在将待分类测试样本决策域内局部密度较小的类赋予偏大的密度补偿系数,而对于那些决策域内局部密度较大的类别赋予偏小的密度补偿系数。所以,从上述引入密度补偿系数的目的可知,密度补偿系数应是类局部密度本身的单调不增函数。本文规定各类的局部密度的补偿系数计算如下
式中ρj-是训练数据集上类别ωj的平均全局密度,其计算方法与局部密度计算相似。特别地,局部密度为0时,补偿系数记为1。
同时,考虑到类间倾斜度的存在,引入倾斜度平衡因子
式中num(ωj)为训练数据集中属于类别ωj的训练样本的个数。
2.2 基于决策域内局部密度的改进算法
基于决策域内局部密度的KNN改进算法步骤如下所示。
输入训练样本集Train、测试样本集Test={y1,y2,y3,…,ym};
输出各测试样本的类别。
(1)计算各类别在训练数据集上的平均全局密度(ρ1-,ρ2-,ρ3-,…,ρC-)和训练数据集中各类的样本个数[num(ω1),num(ω2),num(ω3),…,num(ωC)];
(2)计算测试样本yi到每个训练样本的相似度sim(xl,yi),xl∈Train。并找到和测试样本yi相似度最大的k个近邻样本;
(3)在测试样本yi的k近邻决策域Ψ(yi,k)内,计算各类别的局部密度
(4)根据步骤(3)计算出来的局部密度,计算决策域Ψ(yi,k)内各类关于局部密度的补偿系数τij和各类的倾斜度平衡因子ζij;j=1,2,…,C;
(5)计算测试样本yi的判别函数class(yi),确定测试样本类别
(6)判断测试样本是否已全部分类,若是,则算法结束,输出测试样本类别;否则转步骤(2)。
3 实验与结果分析
为了验证基于决策域内局部密度的KNN算法的性能,本文选择经典K近邻算法(KNN)[1]、加权K近邻算法(WKNN)[18]和基于全局密度的K近邻算法(GD-KNN)[12]这三种算法作为实验比对对象。其中,采用欧氏距离构成各个算法中样本间的相似度的度量。同时,为了使实验结果更具有说服力,通过对不同的K值进行实验,选取对于经典KNN算法具有最好分类准确度的K值,其他三种算法取相同的K值。
3.1 实验数据
实验数据集选自UCI国际通用测试数据库,UCI数据库是一个专门用于测试分类、聚类算法的国际通用机器学习数据库,表1列出了实验所用到的数据集及其相关的统计信息。由于样本间相似度的度量采用欧氏距离,因此,为消除各属性取值区间及范围的不同对分类结果的影响,实验所用数据集均经过了单位标准化处理,使每个样本都是属性取值在[0,1]区间的单位向量。
3.2 实验结果
采用3-折交叉验证方法进行实验。将数据集随机分成3个子集,每次任取其中的2个子集构成训练数据集,剩下的1个子集便是测试数据集,总共进行3次测试,实验结果取三次分类实验结果的平均值。表2是四种分类器在实验数据集上的分类准确度。
为了避免单独采用分类准确度评价分类器性能带来的片面性,文中同时采用召回率和F-measure值两个指标进行分类器性能评价。其中,F-measure定义为:
式中,P是分类精确率,R是召回率,β是调整参数,即调整精确率和召回率在F-measure指标中所占比重。通常β=1,这时评价指标F-measure为
即F1-measure。表3和表4分别列出了四种分类器在各实验数据集上的召回率和F1-measure值。
从表2可以看到,在类别分布均匀的Iris数据集上,四种分类器的分类准确度效果相当。而在类别分布不均匀的Balance、Haberman、Wine数据集上,基于决策域内局部密度的KNN分类器(PD-KNN)分类效果好于其他三种算法。与此同时,由于GD-KNN算法仅考虑了各个目标分类的平均密度而忽略了目标分类内训练数据分布的不均匀性,因此,在一些数据分布复杂的数据集上,如Ecoli数据集,GD-KNN分类器的分类准确度大幅下降。这表明利用GD-KNN算法进行分类时,仅考虑类间倾斜度、获取样本信息不完全容易造成样本的错误分类,当类别分布较复杂时,分类结果甚至可能出现恶化,因此该算法具有一定的局限性。
表3和表4的实验结果显示,PD-KNN分类器的召回率和F1-measure值总体高于其他三种分类器。其中,在四种分类器的召回率指标方面,PD-KNN分类器在各数据集上的召回率均大于90%,在某些数据集上召回率达到1,较其他三种分类器召回率提高2%—5%;而在F1-measure指标上,PD-KNN分类器的F1-measure指标与经典KNN分类器、加权KNN分类器相比均提高0.7%左右,与GD-KNN分类器相比提高5.35%。
4 结论
