K临近算法的改进与应用

K临近算法的改进与应用

陈启龙

关键字

K近邻算法、聚类、权值调整、分类

背景：应用传统K临近算法分类问题

最简单的分类器是将测试对象与训练数据相比较，若完全符合，则可进行分类，显然这种方法需要测试对象足够准确。而判别区域的方法来确定所属类别的方法无法准确的将域的交叉或重叠表达。前两者都有其明显的不足之处。相比之下，传统K近邻算法是将测试对象与训练数据相比较，若能在训练数据周围的特征空间内寻找K个值，大大减少了分类的难度。K近邻算法可以有效地将简洁数据进行分类，从而进行识别，可应用于近似识别等领域。现在常用于方面两个方面，数字扫描领域以及对于网站的数据分析。如图所示,书写的数字可表示为二进制代码，在通过K-近邻算法来测试出想要书写的数字，即可达到数字扫描的效果。

学科前景

在之后的发展之中，K近邻算法将变得更加精密，可以进行一些精细的扫描，可以将其运用至较精准进行图像近似补充或者将颜色、深浅与二维坐标结合进行简略的指纹识别和面部识别。在数据统计方面，改进K近邻算法可以将数据更加充分的处理，使统计变得更加准确、便捷。

推导分析：

1原始K近邻算法思想

K临近算法是最简单的机器学习算法之一，可应用于数据的分类。如上文所述，K近邻算法有很多用处。最原始的用处为即选取一点对其进行估值。为了判断一点的类别，可以在其周围选取多个点，将其中的点进行分类，对点的个数进行统计，其中最多的种类即可代表该点的类别。例如我们先取绿点A，其本应为红色或蓝色一种，需判断其应为红色还是蓝色。取其周围最近的K个值，当K等于3时，易观察出有两个红点和一个蓝点，取其种数即可得到绿色的点应归为红色；当K等于5时，易观察出有两个红点和三个蓝点，取其众数，即可得到绿色的点应归为蓝色

2原始K近邻算法内容

步骤一：首先先根据情况确定K值，一般K取在20以内。

步骤二：根据欧氏距离测算出测算点的距离，得出待分类数以及所有类别样本中距离测试点最近的K个样本。

欧氏距离：若测定二维空间的距离先进行建系，可测量出待测点坐标（x1,y1）以及坐标（x2,y2），则距离可以由以下公式求出。

0ρ=sqrt((x1-x2)^2+(y1-y2)^2)|x|=√(x2+y2)

曼哈顿距离：若测定二维空间的距离先进行建系，可测量出待测点坐标（x1,y1）以及坐标（x2,y2），即可得出|x|=|x1-x2|+|y1-y2|

这两种计算距离的方式均可在K-近邻算法中使用，虽然其计算距离的结果都不相同，所选数据会有一些改变，所以运用其中一种简单的计算方法即可。

步骤三：

输入：训练数据集D={(Xi,Yi),1≤i≤N}，其中Xi是第i个样本的条件属性，Yi是类别,新样本X，距离函数d。

输出:X的类别Y。fori=1toNdo计算X和Xi之间的距离d(Xi,X)；endfor对距离排序，得到d(X,Xi1)≤d(X,Xi2)≤…≤d(X,XiN)；选择前K个样本：S={(Xi1,Yi1)…(XiK,YiK)}；统计S中每个类别出现的次数，确定X的类别Y。

3近期对于K临近算法的改进

在近期中，有许多人都对K近邻算法有所改进，每种都有自己的优势，如林关成的隶间关系，乔玉龙、潘正祥与孙圣和的小波变换法。但大多都为异曲同工之妙，采用各种方法对于无效点进行筛选。在这些方法中，我认为王正欧与王晓晔提出的方法相较于其他方法更加便捷。于2005年，王正欧与王晓晔提出了关于K临近算法的改进，该方法运送多次计算样本间距离取中点的方法，并将其运算次数少的点舍去已达到对无效点进行的排除。乔玉龙、潘正祥与孙圣和的小波变换法运用了方差和小波域中的逼近系数，将其比较判断选出其中符合要求的数据。林关成的隶间关系法是找出k个近邻的点，再运用隶间关系对靠近的样本赋予模糊的隶间关系，对远离的样本赋予清晰地隶间关系，从而使每一个已知样本模糊化，达到预抽取样本的目的。

4近期对于K临近算法改进的步骤

步骤一：先选定测试点周围的K个样本（K的值一般不大于20）

步骤二：将每个样本作为一个独立的簇，搜索K个样本中两两距离最近的簇，将他们相结合，取其空间和数值的平均值

步骤三：持续进行该步骤直到每两个簇之间的距离大于定值δ，选取侧成次数小于d的点，将其舍去。

步骤四：运用K临近算法的加权计算，得到测试对象的准确值。

再运用该方法对这幅图进行分析，若K取3，可先计算两红点间距离，可得其结合点，计算结合点和胜于蓝点距离，发现大于δ将懒点舍去，可得到绿点应为红色。同理，若K取5，可计算两个较近点间的距离将其结合，在这种情况中只能同种颜色相结合，即蓝点结合蓝点，红点结合红点。可得到一个蓝色结合点、一个红色结合点和一个蓝色原始点，计算可得蓝色结合点与蓝色簇间距离小于δ，所以不再结合，可得绿点应为蓝色。这种计算方式对于这种归类算法有所帮助，但其更加适合计算平均距离。

总结与评定

从此可见传统的K近邻算法的优点即为他相较于的算法开来说，他可以将之前的算法苛刻的条件或是不很准确结果改变。但是它也有其弱点，比如其对于重叠的域很难计算，以及他无法主动舍弃点。改进算法不仅减少了测试对象的量，还将独立点去除，从而使算法变得准确。改进算法也具有其缺点，虽然其变得准确了，可计算量比之前的传统方法要大得多。所以我也想一种想法，这样不仅能帮助我们准确的筛选数据，还可以将步骤变得简洁明了。

步骤一：取一待测试点A，并确定定制d，以A为圆心

步骤二：分别以d、3d、5d……（2n-1）d为半径作圆，确保以2nd为半径内有K个数值以供分类

步骤三：计算所有上述K个点与待测点A的距离l，将l确定于（（2a-2）d,2ad），则将该点化为圆上一点，2ad的点将算为2a-1\2a+1各二分之一

步骤四：统计各个圆上的点数并将其点数除以2a-1取加权平均数，将这些加权平均进行筛选，舍弃其中小于定值P的加权平均数

步骤五：将所有剩余的加权平均数进行加和，从而算出测试点的数值。

我设计的这种方法只需计算个点到测试点的距离并进行比较即可达到筛选的目的，及解决了准确性的问题，也解决了速度上的问题，更加偏向于数据分析。

参考文献

1.K-最近邻分类技术的改进算法

2.一种改进的快速k-近邻算法

3.k-近邻算法的初步研究

4.机器学习（一）——K-近邻（KNN）算法