knn算法实现 - ZhouXuyan/notes GitHub Wiki
k-近邻（kNN, k-NearestNeighbor）算法是有监督学习中的一种基本分类与回归方法，我们这里只讨论分类问题中的 k-近邻算法。
k 近邻算法的输入为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类。k 近邻算法假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其 k 个最近邻的训练实例的类别，通过多数表决等方式进行预测。因此，k近邻算法不具有显式的学习过程。
k 近邻算法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。 k值的选择、距离度量以及分类决策规则是k近邻算法的三个基本要素。
KNN 原理
KNN 工作原理
1.假设有一个带有标签的样本数据集（训练样本集），其中包含每条数据与所属分类的对应关系。
2.输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较。
3.计算新数据与样本数据集中每条数据的距离。
4.对求得的所有距离进行排序（从小到大，越小表示越相似）。
5.取前 k （k 一般小于等于 20 ）个样本数据对应的分类标签。
6.求 k 个数据中出现次数最多的分类标签作为新数据的分类。
KNN 开发流程
收集数据：任何方法
准备数据：距离计算所需要的数值，最好是结构化的数据格式
分析数据：任何方法
训练算法：此步骤不适用于 k-近邻算法
测试算法：计算错误率
使用算法：输入样本数据和结构化的输出结果，然后运行 k-近邻算法判断输入数据分类属于哪个分类，最后对计算出的分类执行后续处理
KNN 算法特点
优点：精度高、对异常值不敏感、无数据输入假定
缺点：计算复杂度高、空间复杂度高
适用数据范围：数值型和标称型
kNN 算法伪代码：
对于每一个在数据集中的数据点：
1.计算目标的数据点（需要分类的数据点）与该数据点的距离
2.将距离排序：从小到大
3.选取前K个最短距离
4.选取这K个中最多的分类类别
5.返回该类别来作为目标数据点的预测值
算法实现
def classify0(inX, dataSet, labels, k):
#inX: 用于分类的输入向量
#dataSet: 输入的训练样本集
#labels: 标签向量
#k: 选择最近邻居的数目
#注意：labels元素数目和dataSet行数相同；程序使用欧式距离公式.
dataSetSize = dataSet.shape[0]#取训练样本集的数量
diffMat = tile(inX, (dataSetSize, 1)) - dataSet#把输入的向量复制成矩阵，与训练样本相减
sqDiffMat = diffMat ** 2
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances ** 0.5#求输入向量到全部训练数据的距离
sortedDistIndicies = distances.argsort()#根据距离排序从小到大的排序，返回对应的索引位置；argsort() 是将x中的元素从小到大排列，提取其对应的index（索引），然后输出。
classCount = {}#选择距离最小的k个点
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]]#选择距离最小的k个点的label
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1#如该label未出现，则先将该label频率设为0；将该label已经出现的频率加1
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)#将classCount按其中label出现的频率排序
return sortedClassCount[0][0]#返回出现频率最高的label