k近邻分类算法.doc

k近邻分类算法
k近邻分类算法
k近邻分类算法
第2章k-近邻算法(kNN)
引言
本章介绍kNN算法的基本理论以及如何使用距离测量的方法分类物品。其次，将使用python从文本文件中导入并解析数据，然后，当存在许多数据来源时，如何避免计算距离时可能碰到的一些常见的错识。
2.1k—近邻算法概述
k—近邻(kNearestNeighbors)算法采用测量不同特征之间的距离方法进行分类。它的工作原理是：存在一个样本数据集合,并且样本集中每个数据都存在标签，即我们知道样本每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据的分类标签。一般来说,我们只选择样本数据集中前k个最相似的数据,这就是k—近邻算法中k的出处，通常k是不大于20的整数。最后,选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
k—近邻算法的优点是精度高,对异常值不敏感，无数据输入假定；缺点是计算复杂度高、空间复杂度高.适用于数值和离散型数据。
2.1。1准备知识：使用python导入数据
首先，创建名为kNN.py的python模块，然后添加下面代码：
fromnumpyimport＊#引入科学计算包importoperator＃经典python函数库。运算符模块。
＃创建数据集defcreateDataSet(）:group=array([[1。0，1。1]，［1。0,1。0],[0，0]，［0，0。1]])labels=['A',’A'，'B'，'B’］returngroup，labels
测试:>>>importkNN
>>〉group，labels=kNN。createDataSet()
注意：要将kNN.py文件放到Python27文件夹下,否则提示找不到文件。
2。2。2实施kNN算法
使用k-近邻算法将每组数据划分到某个类中,其伪代码如下：
对未知类别属性的数据集中的每个点依次执行以下操作:
计算已知类别数据集中的点与当前点之间的距离；
按照距离递增交序排序;
选取与当前点距离最小的k个点；
确定前k个点所在类别的出现频率；
返回前k个点出现频率最高的类别作为当前点的预测分类.
用欧氏距离公式，计算两个向量点xA和xB之间的距离：

例如，点（0,0)与（1，2）之间的距离计算为：

python函数classify(）程序如下所示：
#算法核心＃inX：用于分类的输入向量。即将对其进行分类。#dataSet：训练样本集＃labels:标签向量defclassfy0(inX，dataSet，labels，k)：＃距离计算
#得到数组的行数。即知道有几个训练数据dataSetSize=dataSet。shape［0］
#用欧氏距离公式计算距离diffMat=tile(inX，（dataSetSize，1）)-dataSet#将inX扩展为4行2列的向量，两个矩阵相减
sqDiffMat=diffMat*＊2＃平方
sqDistances=sqDiffMat。sum(axis=1）#asis=1是按行相加
distances=sqDistances＊＊0。5＃开方
sortedDistIndicies=distances。argsort()#升序排列#选择距离最小的k个点。classCount={}foriinrange(k）:voteIlabel=labels[sortedDistIndicies[i］]classCount［voteIlabel]=classCount。get(voteIlabel，0）+1＃排序，降序sortedClassCount=sorted（classCount.iteritems（)，key=operator。itemgetter（1),reverse=True）returnsortedClassCount[0］[0]
测试：〉〉〉kNN。classify0([0，0］,group，labels,3）
2。2示例：使用k—近邻算法改进约会网站的配对结果
在约会网站上使用k—近邻算法的步骤:
1.收集数据：提供文本文件。
2.准备数据:使用python解析文本文件.
3。分析数据：使用Matplotlib画二维扩散图。
4.训练算法：此步骤不适用于k—近邻算法。
5.测试算法：使用部分数据作为测试样本。测试样本与非测试样本的区别在于：测试样本是已经完成分类的数据，如果预没分类与实际类别不同，则标记为一个error。
6.使用算法：产生简单的命令行程序，然后可以输入一些特征数据以判断对方是否为自己喜欢的类型。
2。2。1准备数据：从文本文件中解析数据
将数据存放到文本文件，每一个样本数据占据一行。首先，必须将特处理数据改变为分类器