1.算法原理

K近邻算法简称为KNN算法，属于监督学习中的一种分类算法，是最简单最基本的一种分类算法。算法基本原理如下：

1. 准备一个有标签的数据集（也就是已经预先分好类的数据）
2. 有一个未分类的数据，特征值和数据集中的数据相同
3. 计算该数据与数据集中每个数据间的距离（这个距离一般为欧式距离，也有其他的各种距离，依具体情况而定）
4. 将数据集中的数据根据距离远近进行排序
5. 选择与待分类数据最近的K个数据（一般小于20，这就是KNN算法名称的由来）
6. 统计这K个数据中分类标签出现最多的一种作为分类的标签

这里面有两个关键一个是距离的计算，一个是归一化。
因为数据如果不进行归一化直接计算距离的话，可能某一个属性的值会极大的影响结果，如年龄和收入，年龄一般在1至150之间，而收入可能从几千到数万，如果不归一化就计算距离的话，年龄这个维度的作用几乎就不存在了，基本上就是收入决定了最终的距离，显然并不符合我们的期望，因此在计算距离之前首先要进行归一化。

一般情况下，我们采用线性归一化：

y=(x-MinValue)/(MaxValue-MinValue)

其中，x、y分别为转换前、后的值，MaxValue、MinValue分别为样本的最大值和最小值，MaxValue-MinValue就是这些数据的极差。

两个数据间距离度量有很多方法，常见的有以下几种，以二维做例子，多维的类似：
曼哈顿距离：

曼哈顿距离 欧几里得距离（欧式距离）：也就是勾股定理中的斜边， 欧氏距离

闵可夫斯基距离，就是距离的一般化推广：

闵可夫斯基距离
r=1时，该公式就是曼哈顿距离；
r=2时，该公式就是欧式距离；

2.代码实现

根据《机器学习实战》第二章的内容，我把例子重新编写一遍，可以参考Github上的资源：k-近邻算法

实例 预测约会对象是否是喜欢的类型

海伦使用约会网站寻找约会对象。经过一段时间之后，她发现曾交往过三种类型的人:

• 不喜欢的人
• 魅力一般的人
• 极具魅力的人

她希望：

1. 工作日与魅力一般的人约会（一般喜欢）
2. 周末与极具魅力的人约会（很喜欢）
3. 不喜欢的人则直接排除掉（不喜欢）

现在她收集到了一些约会网站未曾记录的数据信息，这更有助于匹配对象的归类。
源数据是txt格式的，有1000行，根据约会对象进行分类，分为：一般喜欢，很喜欢，不喜欢三种类型，用数字1,2,3表示，源数据格式如下：

其中，第一列代表每年获得的飞行常客里程数，第二列代表玩视频游戏所占的时间百分比，第三列代表每周消费的冰激凌公升数，最后一列是预先分好的类别。
我把书中的代码用自己理解的方式重写了一遍，并加上了注释：

首先是读取文件函数

import numpy as np
import matplotlib
import matplotlib.pyplot as plt
import operator

'''把文件数据处理成矩阵'''
def file2matrix(filepath):
    file = open(filepath) # 读取文件
    lines = len(file.readlines()) # 获得文件的行数
    matrix = np.zeros((lines,3)) # 创建一个都为0的矩阵，相当于初始化,二维以上要两个括号
    index = 0 # 默认从第0行开始
    labelVector = [] # 存储每行的分类标签
    file = open(filepath)  # 读取文件
    for line in file.readlines(): # 注意,这里要用readlines()而不是readline(),否则只会读取第一行
        line = line.strip() # 去除头位的空格
        arr = line.split('\t') # 将一行的数据分割成三个数字
        matrix[index,:] = arr[:3] # 给第index行的数据赋值
        labelVector.append(int(arr[3])) # 第4个数字赋值给分类标签,并转成整数类型
        index+=1 # index递增1,处理下一行
    print("matrix:%s"%matrix)
    print("labelVector:%s"%labelVector)
    return matrix,labelVector

matrix,labelVector = file2matrix('datingTestSet2.txt') # 返回数据矩阵和分类标签

画散点图查看当前分类情况（这个因为是书上有的，其实对于算法的实现没有影响）

'''画散点图查看数据情况'''
fig = plt.figure() # matplotlib画图的第一步
ax1 = fig.add_subplot(1,1,1) # matplotlib画图一定要在subplot中，1,1,1代表row,col,num,表示生成row*col幅图片，画在第num幅图中
# 这个我也查了好久，才发现参数s代表散点大小，可选；参数c代表颜色列表，代表颜色序列，应该是根据标签中有三种值分成了三种颜色
ax1.scatter(matrix[:,0],matrix[:,1],s=15.0*np.array(labelVector),c=np.array(labelVector))
plt.show()

散点图

归一化函数

'''归一化函数'''
def normalize(np_data):
    minValue = np_data.min(0) # 这是numpy处理过后的数据才可以用这些函数,每列的最小值和最大值,min(1)每行的最小值
    maxValue = np_data.max(0)
    print("min=%s"%minValue)
    print("max=%s"%maxValue)
    ranges = maxValue-minValue # 极差
    normalizeData = np.zeros(np.shape(np_data)) # 初始化归一化矩阵，大小和原矩阵一致
    # 归一化方法
    rows = np_data.shape[0] # 获取行数
    print("rows=%s"%rows)
    # 把min重复成为rows行,1列的矩阵，这个rows*1的矩阵中的单位元素是min,因为min本身就是一个行向量，所以结果是一个rows行，3列的矩阵,元素为每列的最小值
    temp = np.tile(minValue,(rows,1))
    # 矩阵对应元素相除，如果都是整数则取商
    normalizeData = (np_data-temp)/np.tile(ranges,(rows,1)) # 这里range本身也是一个三列的行向量,扩展成rows行3列的矩阵，才可以进行除法运算
    # 返回归一化矩阵以及最小值行向量和极差行向量
    return normalizeData,ranges,minValue

normalizeData,ranges,minValue = normalize(matrix)
print("归一化后的矩阵：%s"%normalizeData)

KNN算法实现

'''KNN算法实现'''
'''对于每一个在数据集中的数据点：
    计算目标的数据点（需要分类的数据点）与该数据点的距离
    将距离排序：从小到大
    选取前K个最短距离
    选取这K个中最多的分类类别
    返回该类别来作为目标数据点的预测值'''
'''inX——输入的行向量，目的就是判断他所属的类别
   dataSet——归一化后的数据集
   labels——数据集的类别
   k——一共从多少个最近的数据中取标签'''
def KNN(inX,dataSet,labels,k):
    rows = dataSet.shape[0] # 数据集的行数
    temp = np.tile(inX,(rows,1)) # 将inX扩展成rows行3列的矩阵
    diffMat = (temp-dataSet)**2 # 差值的平方
    distance1 = diffMat.sum(axis=1) # 行向量相加
    distance1 = distance1**0.5 # 开方
    sortDistance = distance1.argsort() # argsort返回数值从小到大的索引值（数组索引0,1,2,3）

    classCount = {} # 记录每个类别的出现次数
    for i in range(k):
        label = labels[sortDistance[i]] # 获取类别的值
        classCount[label] = classCount.get(label,0)+1 # classCount若没有label的类别则默认次数为0
    # key关键字排序itemgetter（1）按照第一维度排序(0,1,2,3)
    myClass = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)  # 根据降序排序，最多的一个就是分类的类别,返回的是一个list
    return myClass[0][0] # 因为返回的是一个列表，而列表中的元素是字典转换成的元组，因此等于是二维数组，所以类别结果是myClass[0][0]

测试分类效果

'''测试分类效果'''
def test():
    ratio = 0.1 # 选择总数据的10%作为测试样本，剩下的900个就是原始数据
    ma,labelVector = file2matrix('datingTestSet2.txt') # 加载数据
    normalizeData,ranges,minValue = normalize(ma) # 归一化
    m = normalizeData.shape[0] # 获取行数
    numTest = int(m*ratio) # 测试样本数量
    errorCount = 0.0
    for i in range(numTest):
        vector = normalizeData[i,:]
        mat = normalizeData[numTest:m,:]
        label = labelVector[numTest:m]
        result = KNN(vector,mat,label,3)
        print("result=%s,real label=%s"%(result,labelVector[i]))
        if(result!=labelVector[i]):
            errorCount+=1
    print("错误数量为:%s"%errorCount)

test()

实际分类

'''实际分类'''
def classifyPerson():
    inX = np.array([8.5,400,0.85]) # 假设一个人的三个状态数据
    matrix,labelVector = file2matrix('datingTestSet2.txt') # 加载数据
    normalizeData,ranges,minValue = normalize(matrix) # 归一化
    inX = (inX-minValue)/ranges # 对需要预测的行向量进行归一化
    myClass = KNN(inX,matrix,labelVector,3)
    print("预测分类为：%s"%myClass)

classifyPerson()