knn-伪代码与实现过程

knn特点

优点：精度高，对异常值不明感，无数据输入嘉定

缺点：计算复杂度高，空间复杂度高

适用范围：数值型和标称型

knn算法的伪代码

1、计算已知类别数据集中的点与当前之间的距离

2、按照距离递增次序排序

3、选取与当前点距离最6，小的k个点

4、确定前k个点所在的类别的出现频率

5、返回前k个点出现频率最高的类别作为当前点的预测分类

示例：knn最近邻算法改进约会网站的匹配记录

1、收集数据：提供文本文件

　　*做数据归一化

2、准备数据：python解析数据：包括数据录入与调用knn算法

3、分析数据：使用matplotlib画二位散点图

4、训练算法：此步骤不适用k-nn算法

5、测试算法：使用海伦通的部分数据作为测试样本；测试样本和非测试样本的区别在于：测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记错误。

　　*归一化处理特征（改造分类可以使用的特征值）

　　*计算测试向量的数量（决定了那些数据用测试，哪些用于训练样本），然后输入到原始的knn分类器函数classfy0中，最后计算错误率，并输出

6、使用算法：产生raw_input，输入一些所获得的某个特殊值，产生二位散点图，并用颜色标记方法进行处理

7、注意：涉及到数值归一化问题，knn的缺点是无法给出任何数据的基础结构信息，新词我们无法知晓平均示例样本和典型实例样本具有什么特征，但概率测量方法可以处理分类问题。

手写系统示例：

1、收集数据：提取文件

2、准备数据：编写函数classfy0(),将图片转换为分类器使用的list格式

　*将二进制图形举证转化为1*1024的向量

　*打开文件，循环文件前32行，并将每行的头32个字符值存放在Numpy中

3、分析数据：在python命令提示符中检查数据，确保符合要求

　　*获取目录内容

　　*从文件名解析数字分类，主要是匹配训练集的向量相似性

4、训练数据：knn不适合

5、测试数据：编写函数使用提供的部分数据及作为测试样本，测试样本和费测试样本的区别在于测试样本是已经完成的分为类数据，如果预测分类和实际类别不同，则标记为一个错误

6、使用算法：

巴特西