搜索
山东大学软件学院模式识别课程实验报告学号：201500301139姓名：修丙楠班级：15级软件二班实验题目：KNN实验学时：实验日期：2018.1.19实验目的：使用K-NN算法识别数字0-9，数据集来自MachineLearninginAction第二章。书中把来自UCI数据库的手写数据集简化成32像素x32像素的黑白图像，并且以01矩阵的方式存储在txt文件中。大约有训练样本2000个，测试样本900个。硬件环境：Processor:Intel(R)Core(TM)i5-7200UCPU@2.50GHz(4CPUs),~2.7GHz软件环境：Eclipse实验步骤与内容：实验一：实验要求：1.实现最基本的KNN算法，使用trainingDigits文件夹下的数据，对testDigits中的数据进行预测。（K赋值为1，使用欧氏距离，多数投票决定分类结果）2.改变K的值，并观察对正确率的影响。3.更改距离度量方式，更改投票方式（距离加权），分析错误率。实验步骤：1、（1）KNN分析：KNN的算法思想比较简单，对于每一个测试集样本，计算其与所有训练集样本间的欧氏距离，对所有结果进行排序，选取其中距离最小的k个样本，采用多数投票的方式确定该测试集样本所属的类型。（2）算法实现：·读文件：利用Java里提供的BufferedReader进行读文件操作，将读进来的样本以二维数组的形式存储·排序：选了冒泡排序的方法（因为写起来简单）·找出k近邻中出现次数最多的元素：用HashMap的key值存储每个元素出现的次数，最后返回key值最大的节点对应的元素。（3）代码运行结果为了比较K的值对结果的影响，测试取了1-20之间的数作为k值运行结果如下：图11-NN图22-NN图31~20-NN绘制表格如下：K值准确率（%）198.73298.52398.63498.52598.10698.20797.89897.46997.781097.891197.891297.781397.361497.571597.361697.571797.151897.361997.252097.25绘制散点图如下：可以看到，随着K值的增加，预测的准确率反而逐渐降低，这与理论上样本足够多，K值足够大，正确率会越好的想法冲突，可能是K值增大后噪声点增多？2、更改距离度量方式可以考虑采用曼哈顿距离进行距离度量更改投票方式：让离的越近的样本点的权重值越大。可以代用高斯模板进行度量。实验二：1、KNN应用场景：它的特点是完全跟着数据走，没有数学模型可言。需要一个特别容易解释的模型的时候。比如需要向用户解释原因的推荐算法。比如文字识别，面部识别；预测某人是否喜欢推荐电影（Netflix）；基因模式识别，比如用于检测某中年疾病；客户流失预测、欺诈侦测（更适合于稀有事件的分类问题）KNN应用场景：通常最近邻分类器使用于特征与目标类之间的关系为比较复杂的数字类型，或者说二者关系难以理解，但是相似类间特征总是相似。引用来源：://blog.csdn.net/qq_16365849/article/details/50649905、KD树KD树的思想上课学长有具体讲过Kd-树其实是K-dimensiontree的缩写，是对数据点在k维空间中划分的一种数据结构。其实，Kd-树是一种平衡二叉树，图示如下参考来源：://baike.baidu.com/item/kd-tree/2302515?fr=aladdin3、HashMap本次代码中有用到实验三：协同过滤关于协同过滤的一个最经典的例子就是看电影，有时候不知道哪一部电影是我们喜欢的或者评分比较高的，那么通常的做法就是问问周围的朋友，看看最近有什么好的电影推荐。在问的时候，都习惯于问跟自己口味差不多的朋友，这就是协同过滤的核心思想。协同过滤是在海量数据中挖掘出小部分与你品味类似的用户，在协同过滤中，这些用户成为邻居，然后根据他们喜欢的东西组织成一个排序的目录推荐给你。所以就有如下两个核心问题（1）如何确定一个用户是否与你有相似的品味？（2）如何将邻居们的喜好组织成一个排序目录？协同过滤算法的出现标志着推荐系统的产生，协同过滤算法包括基于用户和基于物品的协同过滤算法。2.协同过滤的核心要实现协同过滤，需要进行如下几个步骤（1）收集用户偏好（2）找到相似的用户或者物品（3）计算并推荐结论分析与体会：实验结果基本符合实验要求通过自己实现KNN算法（虽然这是机器学习算法里边最简单的），加深了对KNN算法思想的理解，之后针对于KD书以及HashhMap查阅资料，对这两种数据结构有了一定的了解（实验代码中有用到HashMap）