1、中国地质大学课程报告课程名称：数据挖掘指导老师：蒋良孝学生学号：20131003701学生班级：086131学生姓名：刘卫1对 KNN 算法的优化k-近邻算法概述k-近邻(k Nearest Neighbors)算法采用测量不同特征之间的距离方法进行分类 。它的工作原理是：存在一个样本数据集合，并且样本集中每个数据都存在标签，即我们知道样本每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据的分类标签。一般来说，我们只选择样本数据集中前 k 个最相似的数据，这就是 k-近邻算法中 k 的出处，通常 k 是不
2、大于 20 的奇数。最后，选择 k 个最相似数据中出现次数最多的分类，作为新数据的分类。k-近邻算法的优点是精度高，对异常值不敏感，无数据输入假定；缺点是计算复杂度高、空间复杂度高。适用于数值和标称型数据。使用 k-近邻算法将每组数据划分到某个类中，其伪代码如下：对未知类别属性的数据集中的每个点依次执行以下操作：计算已知类别数据集中的点与当前点之间的距离；按照距离递增交序排序；选取与当前点距离最小的 k 个点；确定前 k 个点所在类别的出现频率；返回前 k 个点出现频率最高的类别作为当前点的预测分类。提出问题：1.我在上机用 KNN 算法做实验时，发现 k 值只能凭经验选取， 而且不同的 k
3、值所产生的测试结果正确率相差很大。如右图 所示，当 k 值取 3 的时候待测元组就属于三角形而当 k 值取 5 的时候待测元组属于正方形，最极端的情况 k 取值为所有训练样本的元组数 n 时，那就是正方形和三角形哪个多取哪个了。2.对于所要预测的值为离散类型数据时，是将这 k 个训练数据中哪个类别的训练数据占多数，待测分类元祖就属于哪个类别；对于预测值为连续型时，结果取 k 个训练数据的平均值。但这里明显 k 个点到待测元组的距离是不同的，距离近的肯定更有参考价值，而这里却把这 k 个点的价值等同看待，不合情理。2分析问题：不管是问题 1 还是问题 2，都与原算法将这 k 个最近点等同看待了这
4、个原因相关，若是设置一个量化关系，把离得近的训练数据点对结果的权值由 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 个训练数据，因为如果这样就表示距离越小权值越小了，与我们想要的结果相反；那既然相反
5、，那么我把此结果求一下倒数不就可以表示距离越小权值越大了吗。这样：将 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 的值得到以下结果：3然后换上经过改进后的算法得到以下结果：经过交叉验证的结果比较后者预测准确率 64.2857%优于前者 57.1429%，而且后者在多次改变 k 值的情况下准确率也没有明显变化。
