对KNN算法的优化.doc

中国地质大学课程报告

课程名称：数据挖掘
指导老师：蒋良孝
学生学号：20131003701
学生班级：086131
学生姓名：刘卫

对KNN算法的优化
k-近邻算法概述
k-近邻(k Nearest Neighbors)算法采用测量不同特征之间的距离方法进行分类 。它的工作原理是：存在一个样本数据集合，并且样本集中每个数据都存在标签，即我们知道样本每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的奇数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
k-近邻算法的优点是精度高，对异常值不敏感，无数据输入假定；缺点是计算复杂度高、空间复杂度高。适用于数值和标称型数据。
使用 k-近邻算法将每组数据划分到某个类中，其伪代码如下：
对未知类别属性的数据集中的每个点依次执行以下操作：
计算已知类别数据集中的点与当前点之间的距离；
按照距离递增交序排序；
选取与当前点距离最小的k个点；
确定前k个点所在类别的出现频率；
返回前k个点出现频率最高的类别作为当前点的预测分类。

提出问题：
1.我在上机用KNN算法做实验时，发现k值只能凭经验选取， 而且不同的k值所产生的测试结果正确率相差很大。如右图 所示，当k值取3的时候待测元组就属于三角形而当k值取5的时候待测元组属于正方形，最极端的情况k取值为所有训练样本的元组数n时，那就是正方形和三角形哪个多取哪个了。

2.对于所要预测的值为离散类型数据时，是将这k个训练数据中哪个类别的训练数据占多数，待测分类元祖就属于哪个类别；对于预测值为连续型时，结果取k个训练数据的平均值。但这里明显k个点到待测元组的距离是不同的，距离近的肯定更有参考价值，而这里却把这k个点的价值等同看待，不合情理。

分析问题：
不管是问题1还是问题2，都与原算法将这k个最近点等同看待了这个原因相关，若是设置一个量化关系，把离得近的训练数据点对结果的权值由1/k调高，把离得远的训练数据点对结果的权值由1/k调低，是不是能优化此算法的效果呢。
解决问题：
现在我们来根据距离的不同给这k个点来设置不同的权值（距离越大权值越小，距离越小权值越大。K个点的权值之和为1.）设此k个点与待测元组的距离分别为：d1，d2，......，dk。这k个距离的和S=d1+d2+......+dk。虽然d1/s+d2/s+......+dk/s=1，注意绝对不能直接把d1/s，d2/s，......，dk/s作为权值赋给这k个训练数据，因为如果这样就表示距离越小权值越小了，与我们想要的结果相反；那既然相反，那么我把此结果求一下倒数不就可以表示距离越小权值越大了吗。这样：将d1/s，d2/s，......，dk/s求倒得s/d1，s/d2，......，s/dk。再令S’=s/d1+s/d2+，......，s/dk。此时（s/d1）/s’+（s/d2)/s’+,......,(s/dk)/s’=1,这样即可将（s/d1）/s’,（s/d2)/s’,......,(s/dk)/s分别直接赋给这k个训练数据点所占的权值q1，q2,......，qk了。

经过以上的改进便可以实现距离越小权重越大，距离越大权重越小了。那么这些权值究竟如何影响结果呢？看以下阐述：
对于预测值为连续型数据时：此k个训练元组的值分别乘以他们的权重再相加即可得到待测元组的值。
对于预测值为离散型数据时：若这k个训练元组中有一个或多个元组属于某一个类，那么将这几个元组的权值相加的和作为他们所属类的权值，最后待测元祖取值为权值总和最大的类。

实验结论：
打开weka后导入天气的数据首先用IBK(knn)算法，try了一个结果最好的k=3的值得到以下结果：

然后换上经过改进后的算法得到以下结果：

经过交叉验证的结果比较后者预测准确率64.2857%优于前者57.1429%，而且后者在多次改变k值的情况下准确率也没有明显变化。
3