机器学习-KNN近邻算法

参看文章：

《机器学习-周志华》

《机器学习实战-Peter Harrington》

《统计学习方法-李航》

算法介绍：

k近邻学习是一种常用的监督学习方法，其工作机制如下，给定测试样本，基于某种距离度量（曼哈顿距离、欧氏距离、切比雪夫距离、Lp距离、Minkowski距离）找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息来进行预测。

argmax(f(x))是使得 f(x)取得最大值所对应的变量点x

投票法：

在分类任务中使用，选择k个样本出现最多的类别标记作为预测结果

平均法：

在回归任务中使用，即将k个样本的实值输出标记的平均值作为预测结果

距离权重法：

称为k近邻算法的优化算法，为每个点的距离增加一个权重，使得距离近的点可以得到更大的权重，既可用于加权平均又可用于加权投票。

优缺点：

优点：

1.理论成熟，思想简单，既可以用来做分类又可以做回归

2.训练时间复杂度为O(n)；无数据输入假定；

3.可用于数值型数据和离散型数据；

4.对异常值不敏感

缺点：

1.计算复杂度高，因无显示的训练过程

2.对k值、距离敏感，不同k值与距离计算方法可能结果不同

3.无法给出任何数据的基础结构信息

最近邻分类器（k = 1）

错误率（暂未看懂）

实现方法：

1. 传统法代码：

 

 1 #-*- coding: utf-8 -*-
 2 import numpy as np  3 import operator  4  5 def createDataSet():  6 #创建数据集，包含样本group，标签labels  7 group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])  8 labels = ['A', 'A', 'B', 'B']  9 return group, labels 10 11 def classify0(inX, dataSet, labels, k): 12 #shape[0]返回数据集的行数，shape[1]返回数据集的列数 13 dataSetSize = dataSet.shape[0] 14 #tile(array,(a,b)，把array按a行，b列进行复制，a,b为1时维持原行数或列数 15 diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet 16 sqDiffMat = diffMat**2 17 #sum(axis = 1)对行求和，sum(aixs = 0)对列求和 18 sqDistances = sqDiffMat.sum(axis=1) 19 distances = sqDistances**0.5 20 ''' 21  argsort(x)升序排序，argsort(-x)降序排序，argsort(x, axis=0)按列排序，返回的是原数组从小到大排序的下标值 22  np.argsort(x, axis=1)按行排序；默认按列排序 23 ''' 24 sortedDistIndicies = distances.argsort() 25 classCount = {} 26 for i in range(k): 27 voteIlabel = labels[sortedDistIndicies[i]] 28 classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1 29 # sorted(iterable, cam = None, key = None, reverse = True/False)，True按倒序排列，False按升序排列 30 #items() 方法以列表返回可遍历的(键, 值) 元组数组， 31 # key = operator.itemgetter(1)根据字典的值进行排序 32 # key = operator.itemgetter(0)根据字典的键进行排序 33 sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) 34 #返回次数最多的类别 35 return sortedClassCount[0][0] 36 37 if __name__ == "__main__": 38 group, labels = createDataSet() 39 y = classify0([0, 0], group, labels, 3) 40 print(y)

 

2. kd树