一、算法简介

k-近邻算法(K-NearestNeighbor,简称KNN)是1967年由Cover T和Hart P提供的一种基本分类方法，数据挖掘分类技术中最简单的方法之一。KNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则样本也属于这个类别，并具有这个类别上样本的特性。

如上图所示，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例是2/3,绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。

二、原理

1、距离公式：

欧氏距离:欧几里得距离或欧几里得度量是欧几里得空间中两点之间“普通”（即直线）距离。使用这个距离，欧式空间成为度量空间。相关联的范数成为欧几里得范数。较早的文献称之为毕达哥拉斯度量。

二维空间公式：
$\rho=\sqrt[]{(x_{2}-x_{1})^2+(y_{2}-y_{1})^2},其中，\rho为点(x_{2},y_{2})与点(x_{1},y_{1})之间的欧式距离$
$|x|=\sqrt[]{x_{2}^2+y_{2}^2},其中|x|为点(x_{2},y_{2})到原点的欧氏距离。$
三维空间的公式：
$\rho=\sqrt[]{(x_{2}-x_{1})^2+(y_{2}-y_{1})^2+(z_{2}-z_{1})^2},$
$|x|=\sqrt[]{{x_{2}^2+y_{2}^2+z_{2}^2}}$
n维空间的公式
$d(x,y):=\sqrt[]{(x_{1}-y_{1})^2+(x_{2}-y_{2})^2+...+(x_{n}-y_{n})^2}=\sqrt[]{\sum_{i=1}^{n}(x_{i}-y_{i})^2}$

2、算法说明

通俗地讲，就是计算一个点与样本空间所有点之间的距离，取出与该点最近的k个点，然后统计这k个点里面所属分类比例最大的，则该点就属于这个占比最大的分类。

一般流程：

收集数据：可以使用爬虫进行数据的收集，也可以使用第三方提供的免费或收费的数据。
准备数据：可以使用python解析，预处理数据
分析数据：可以使用很多方法对数据进行分析，例如使用Matplotlib将数据可视化。
特征工程：标准化，KNN数据需要进行标准化
进行算法流程：得出预测结果，计算准确率
使用算法：准确率在可接受的范围，就可以运行K-近邻算法进行分类

三、实战分析

1、约会网站配对效果判定

1.1背景

海伦女士一直使用在线约会网站寻找适合自己的约会对象，尽管约会网站会推荐不同的选择，但是她并不是喜欢每一个人，经过一番总结，她发现自己交往过的人可以进行如下分类：

不喜欢的人(didntLike)
魅力一般的人(smallDoses)
极具魅力的人(largeDoses)
经过一段时间的数据收集，她把这些数据放在文本文件datingTestSet.txt中，每个样本占据一行，总共有1000行。
数据特征：
每年获得的飞行常客里程数
玩视频游戏所消耗时间百分比
每周消费的冰激凌公升数

数据集

1.2准备数据：数据解析

给出的数据包括了特征值与分类标签向量，我们先将数据处理一下，将特征值与分类标签分开：

# -*- coding: UTF-8 -*-
import matplotlib.pyplot as plt
import matplotlib.lines as mlines
import numpy as np
import operator
def dataset():
    """
    打开并解析文件，对数据进行分类:
    1代表不喜欢
    2代表魅力一般
    3代表极具魅力
    :return:
    """
    #numpy矩阵的形式

    #打开文件
    fr = open('../../数据集/机器学习/分类算法/海伦约会/datingTestSet.txt')
    #读取文件的所有内容
    arrayOne = fr.readlines()
    #得到文件行数
    numoflines = len(arrayOne)
    #返回numpy矩阵，解析完成的数据：numoflines
    returnMat = np.zeros((numoflines,3))
    #返回分类标签向量
    classLabelVector = []
    #行的索引
    index = 0
    for line in arrayOne:
        # s.strip(rm)，当rm空时,默认删除空白符(包括'\n','\r','\t',' ')
        line = line.strip()
        # 使用s.split(str="",num=string,cout(str))将字符串根据'\t'分隔符进行切片。
        listFromLine = line.split('\t')
        # 将数据前三列提取出来,存放到returnMat的NumPy矩阵中,也就是特征矩阵
        returnMat[index,:] = listFromLine[0:3]#每三个赋值给矩阵的每一行
        if listFromLine[-1] == 'didntLike':
            classLabelVector.append(1)
        elif listFromLine[-1] == 'smallDoses':
            classLabelVector.append(2)
        elif listFromLine[-1] == 'largeDoses':
            classLabelVector.append(3)
        index += 1

    return returnMat,classLabelVector

if __name__ == "__main__":
    returnMat,classLabelVector = dataset()
    print(returnMat)
    print(classLabelVector)

1.3 分析数据：数据可视化

简单的处理一下数据之后，我们对数据进行可视化,看一下特征之间的关系，

def showdatas(x,y):
    """
    数据可视化
    :return:
    """

    fig = plt.figure(figsize=(15,15))
    #第一张散点图显示视频游戏与飞机里程数占比关系
    ax1 = fig.add_subplot(2,2,1)
    colors = []
    #设置图例
    didntLike = mlines.Line2D([], [], color='black', marker='.',markersize=6, label='didntLike')
    smallDoses = mlines.Line2D([], [], color='orange', marker='.',markersize=6, label='smallDoses')
    largeDoses = mlines.Line2D([], [], color='red', marker='.',markersize=6, label='largeDoses')
    for i in y:
        if i == 1:
            colors.append('black')
        if i == 2:
            colors.append('orange')
        if i == 3:
            colors.append('red')
    ax1.scatter(x=x[:,0],y=x[:,1],color=colors,s=15)
    ax1.set_title('每年获得的飞行常客里程数与玩视频游戏所消耗时间占比')
    ax1.set_xlabel('每年获得的飞行常客里程数')
    ax1.set_ylabel('玩视频游戏所消耗时间占比')
    # 添加图例
    ax1.legend(handles=[didntLike,smallDoses,largeDoses])

    #第二张散点图显示视频游戏与冰激凌之间的关系

    ax2 = fig.add_subplot(2,2,2)
    ax2.scatter(x=x[:,1],y = x[:,2],color=colors,s=15)
    ax2.set_title('视频游戏消耗时间与每周消费的冰激凌公升数')
    ax2.set_xlabel('玩视频游戏消耗时间')
    ax2.set_ylabel('每周消费的冰激凌公升数')
    # 添加图例
    ax2.legend(handles=[didntLike,smallDoses,largeDoses])
    # plt.show()
    # print(colors)

    #第三张散点图显示飞机里程数与冰激凌公升数的关系
    ax3 = fig.add_subplot(2,2,3)
    ax3.scatter(x = x[:,0],y = x[:,2],color=colors,s = 15)
    ax3.set_title('每年飞机飞行里程数与每周消费的冰激凌公升数')
    ax3.set_xlabel('每年获得的飞行常客里程数')
    ax3.set_ylabel('每周消费的冰激凌公升数')
    # 添加图例
    ax3.legend(handles=[didntLike, smallDoses, largeDoses])
    plt.show()
    return None

通过图像进行简单的分析我们发现，如果考虑玩游戏消耗时间占比与每年获得的飞行常客里程数的话，感觉海伦喜欢有生活质量的男人，毕竟能经常飞，还有时间玩游戏，并且占有一定时间比例，大概率是一个生活悠闲，追求质量的人。

1.4、数据归一化

通过1.1我们发现数字差值比较大的属性对计算结果的影响比较大，为了消除这种不同取值范围的特征值影响过大的问题，我们通常采用的方法是将数值归一化，如将取值范围处理为[0,1]之间，前提是我们认为这三种特征是同等重要的。

归一化的计算公式：
$x = \frac{x- min}{max-min}$

def autoNorm(x):
    """
    数据归一化
    newValue = (oldValue - min) / (max - min)
    :param x:
    :return:
    """
    #这边还可以做一些改进，筛掉一些数据
    #获得数据的最小值
    minvals = x.min(0)
    maxvals = x.max(0)
    #最大值和最小值的范围
    ranges = maxvals - minvals
    #shape（x）返回x的矩阵行列数
    normx = np.zeros(np.shape(x))
    #返回x的行数
    m = x.shape[0]
    #原始值减去最小值
    normx = x - np.tile(minvals,(m,1))
    #除以最大和最小值的差，得到归一化的数据
    normx = normx / np.tile(ranges,(m,1))
    #返回归一化数据结果，数据范围，最小值
    return normx,ranges,minvals

if __name__ == "__main__":
    returnMat,classLabelVector = dataset()
    normx, ranges, minvals = autoNorm(returnMat)
    # classifyDataset(normx,classLabelVector)
    # showdatas(returnMat,classLabelVector)
    print(normx)

归一化后的结果

1.5 测试算法

将数据进行归一化后，我们先将数据集划分出测试集与训练集，然后进行测试算法的工作，这里我们选择90%的数据为训练集，10%的数据为测试集，

def classify(x_data,y_data,labels,k):
    """
    Knn算法，分类器
    x_data：训练集
    y_data:测试集
    labels:分类标签
    k：选取的分类区域
    :return:
    """
    #返回训练集的行数
    xdatasize = y_data.shape[0]
    #将测试集在行列上进行复制，并减去训练集
    diffMat = np.tile(x_data,(xdatasize,1)) - y_data
    #求特征矩阵差的平方
    sqdiffMat = diffMat**2
    #平方求和
    sqDistance = sqdiffMat.sum(axis=1)
    #开方计算距离
    distance = sqDistance ** 0.5
    #返回距离从小到大排序后的索引值
    sortedDistance = distance.argsort()
    #定一个记录类别次数的字典
    classified = {}
    #将排序后的类别记录
    for i in range(k):
        #选出前k个元素的类别
        votedlabels = labels[sortedDistance[i]]
        # dict.get(key,default=None),字典的get()方法,返回指定键的值,如果值不在字典中返回默认值。
        # 计算类别次数
        classified[votedlabels] = classified.get(votedlabels,0) + 1
    # python3中用items()替换python2中的iteritems()
    # key=operator.itemgetter(1)根据字典的值进行排序
    # key=operator.itemgetter(0)根据字典的键进行排序
    # reverse降序排序字典
    sortedCounts = sorted(classified.items(), key=operator.itemgetter(1), reverse=True)
    #第一个存放的就是出现次数最多的类别
    return sortedCounts[0][0]


def classifyDataset(normx,labels):
    """
    划分测试集与训练集
    将训练集的10%划分为测试集
    :return:
    """
    alpha = 0.1
    #获得归一化后数据集的行数
    m = normx.shape[0]
    #10%的数据为测试集
    numtest = int (m * alpha)
    #分类错误计数
    errorcount = 0.0

    #调用算法 进行分类
    for i in range(numtest):
        # 前numtest为测试集，后m-numtest为训练
        classfyresult = classify(normx[i,:],normx[numtest:m,:],labels[numtest:m],4)
        print("分类结果:%d\t真实类别:%d" % (classfyresult,labels[i]))
        if (classfyresult != labels[i]):
            errorcount += 1
    print("错误率为：%f%%" % (errorcount / float(numtest)* 100))

    return None
if __name__ == "__main__":
    returnMat,classLabelVector = dataset()
    normx, ranges, minvals = autoNorm(returnMat)
    classifyDataset(normx,classLabelVector)
    # showdatas(returnMat,classLabelVector)
    # print(normx)

运行结果

通过上图的运行结果我们发现，错误率为4%，这是一个相当不错的结果。如果改变alpha与k值，错误率随着变脸值的变化而变化。大家可以下去试一下。

2、预测一个人签到的地方（Kaggle比赛项目）

这个比赛是由facebook与kaggle联合举行的一场比赛，目的是预测一个人想签到哪个地方，为了比赛的目的，Facebook创建了一个人工世界，由10万×10公里的正方形中的100000个地方组成，对于给定的一组坐标，我们的任务是返回最可能的位置的排名列表，数据被制作成类似于来自移动设备的位置信号，从而更具真实性。
首先，我们来看一下数据，

数据相对较大，有几百万行，这里只展示一小部分。
第二个案例我们将不再把算法的具体步骤写出来，sklearn有专门封装好的KNN算法，我们只需要调用一下，改变一下参数即可

数据预处理
先导入一下需要用到的包，

import pandas as pd
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler

1、数据量问题
一方面数据量过大，另一方面，有些数据值较小，研究价值不大，我们将这部分数据进行删除。

def knn():
    """
    knn预测分类
    :return:
    """
    # 读取数据
    data = pd.read_csv('../../数据集/机器学习/分类算法/facebook-v-predicting-check-ins/train.csv')
    print(data.count(axis=0)) 
    # 数据预处理
    #缩小数据范围
    data = data.query(" x > 0.25 & x < 1.25 & y > 2.5 &y < 2.75")
    print(data.count(axis=0))
if __name__ == "__main__":
    knn()

我们看一下结果：

也就是说原先由29118021条数据，经过处理后，数据有62594条。
2、时间处理
这里的时间是时间戳，我们将其转成标准格式，并分割，以此添加一些特征值，

def knn():
    """
    knn预测分类
    :return:
    """
    # 读取数据
    data = pd.read_csv('../../数据集/机器学习/分类算法/facebook-v-predicting-check-ins/train.csv')
    #print(data.count(axis=0))

    # 数据预处理
    #1、缩小数据范围
    data = data.query(" x > 0.25 & x < 1.25 & y > 2.5 &y < 2.75")
    # print(data.count(axis=0))
    #2、处理时间数据
    data['time'] = pd.to_datetime(data['time'], unit='s')
    #把日期格式转换成  字典格式
    time_value = pd.DatetimeIndex(data['time'])
    # print(time_value)
    #3、增加分割的日期数据
    data['day'] = time_value.day
    data['hour']= time_value.hour
    data['weekday'] = time_value.weekday
    print(data.head())
if __name__ == "__main__":
    knn()

处理完之后可以发现，多出了day,hour,weekday等几列数据。
3、删除一些没用的数据
经过上面时间处理之后，time这一列已经变成了三列(day,hour,weekday)数据，time时间戳的数据就用不到了，我们可以将它删掉，

def knn():
    """
    knn预测分类
    :return:
    """
    # 读取数据
    data = pd.read_csv('../../数据集/机器学习/分类算法/facebook-v-predicting-check-ins/train.csv')
    # print(data.count(axis=0))

    # 数据预处理
    #1、缩小数据范围
    data = data.query(" x > 0.25 & x < 1.25 & y > 2.5 &y < 2.75")
    # print(data.count(axis=0))
    #2、处理时间数据
    data['time'] = pd.to_datetime(data['time'], unit='s')
    #把日期格式转换成  字典格式
    time_value = pd.DatetimeIndex(data['time'])
    # print(time_value)
    #3、增加分割的日期数据
    data['day'] = time_value.day
    data['hour']= time_value.hour
    data['weekday'] = time_value.weekday
    # print(data.head())

    #4、删除没用的数据
    data = data.drop(['time'],axis=1)
    print(data.head())
if __name__ == "__main__":
    knn()

5、筛选掉不符合条件的值
这里我们将签到次数少于3次的筛掉。

def knn():
    """
    knn预测分类
    :return:
    """
    # 读取数据
    data = pd.read_csv('../../数据集/机器学习/分类算法/facebook-v-predicting-check-ins/train.csv')
    # print(data.count(axis=0))

    # 数据预处理
    #1、缩小数据范围
    data = data.query(" x > 0.25 & x < 1.25 & y > 2.5 &y < 2.75")
    # print(data.count(axis=0))
    #2、处理时间数据
    data['time'] = pd.to_datetime(data['time'], unit='s')
    #把日期格式转换成  字典格式
    time_value = pd.DatetimeIndex(data['time'])
    # print(time_value)
    #3、增加分割的日期数据
    data['day'] = time_value.day
    data['hour']= time_value.hour
    data['weekday'] = time_value.weekday
    # print(data.head())

    #4、删除没用的数据
    data = data.drop(['time'],axis=1)
    # print(data.head())
    #5、将签到位置少于n个用户的删除
    place_count = data.groupby('place_id').count()
    print(place_count)
    tf = place_count[place_count.row_id > 3].reset_index()
    data = data[data['place_id'].isin(tf.place_id)]
    print(data)
if __name__ == "__main__":
    knn()

上面是根据条件筛选的结果，下面是删掉数据后的结果。
6、取特征值与目标值，并分割测试集与训练集

def knn():
    """
    knn预测分类
    :return:
    """
    # 读取数据
    data = pd.read_csv('../../数据集/机器学习/分类算法/facebook-v-predicting-check-ins/train.csv')
    # print(data.count(axis=0))

    # 数据预处理
    #1、缩小数据范围
    data = data.query(" x > 0.25 & x < 1.25 & y > 2.5 &y < 2.75")
    # print(data.count(axis=0))
    #2、处理时间数据
    data['time'] = pd.to_datetime(data['time'], unit='s')
    #把日期格式转换成  字典格式
    time_value = pd.DatetimeIndex(data['time'])
    # print(time_value)
    #3、增加分割的日期数据
    data['day'] = time_value.day
    data['hour']= time_value.hour
    data['weekday'] = time_value.weekday
    # print(data.head())

    #4、删除没用的数据
    data = data.drop(['time'],axis=1)
    # print(data.head())
    #5、将签到位置少于n个用户的删除
    place_count = data.groupby('place_id').count()
    # print(place_count)
    tf = place_count[place_count.row_id > 3].reset_index()
    data = data[data['place_id'].isin(tf.place_id)]
    # print(data)
    #
    #取出数据当中的特征值和目标值
    y=data['place_id']
    x=data.drop(['place_id'],axis=1)
    x=data.drop(['row_id'],axis=1)
    #
    #进行数据集的分割
    x_train,x_test,y_train,y_test=train_test_split(x,y,test_size=0.25)
if __name__ == "__main__":
    knn()

这里没有把分割后的测试集与训练集展示出来，有兴趣的同学可以输出看一下。
7、特征标准化
特征归一化与特征标准化是特征预处理的重要方法，目的是降低某特征值过大对结果的影响，特征标准化是KNN算法最常用的特征处理方法，它将原始特征值处理为服从均值为0，方差为1的正态分布。

标准化公式：
$x' = \frac{x - mean}{\sigma} ,这里mean是指每一列的平均值，\sigma是标准差$
$var = \frac{(x_{1}-mean)^2+(x_{2}-mean)^2+...+(x_{n}-mean)^2}{n}$
$\sigma = \sqrt{var}$
关于特征标准化，sklearn中封装有标准化的API，scikit-learn.preprocessing.StandardScaler,我们直接调用就可以，

def knn():
    """
    knn预测分类
    :return:
    """
    # 读取数据
    data = pd.read_csv('../../数据集/机器学习/分类算法/facebook-v-predicting-check-ins/train.csv')
    # print(data.count(axis=0))

    # 数据预处理
    #1、缩小数据范围
    data = data.query(" x > 0.25 & x < 1.25 & y > 2.5 &y < 2.75")
    # print(data.count(axis=0))
    #2、处理时间数据
    data['time'] = pd.to_datetime(data['time'], unit='s')
    #把日期格式转换成  字典格式
    time_value = pd.DatetimeIndex(data['time'])
    # print(time_value)
    #3、增加分割的日期数据
    data['day'] = time_value.day
    data['hour']= time_value.hour
    data['weekday'] = time_value.weekday
    # print(data.head())

    #4、删除没用的数据
    data = data.drop(['time'],axis=1)
    # print(data.head())
    #5、将签到位置少于n个用户的删除
    place_count = data.groupby('place_id').count()
    # print(place_count)
    tf = place_count[place_count.row_id > 3].reset_index()
    data = data[data['place_id'].isin(tf.place_id)]
    # print(data)
    #
    #取出数据当中的特征值和目标值
    y=data['place_id']
    x=data.drop(['place_id'],axis=1)
    x=data.drop(['row_id'],axis=1)
    #
    #进行数据集的分割
    x_train,x_test,y_train,y_test=train_test_split(x,y,test_size=0.25)

    # 特征工程(标准化)
    std=StandardScaler()

    # 对测试集和训练集的特征值进行标准化
    x_train = std.fit_transform(x_train)
    x_test = std.fit_transform(x_test)
    print(x_train)
    print(x_test)
if __name__ == "__main__":
    knn()

8、进行算法流程，得出预测结果和准确率
KNN算法在sklearn提供的sklearn.neighbors.KNeighborsClassifier(n_neighbors=5,algorithm='auto')中，

参数	说明
n_neighbors，int,可选（默认=5）	k_neighbors查询默认使用的邻居数
algorithm，{'auto','ball_tree','kd_tree','brute'}	'ball_tree'将会使用BallTree,'kd_tree'将使用KDTree.'auto'将尝试根据传递给fit方法的值来决定最适合的算法。（不同实现方式影响效率）

我们来看一下测试结果，

def knn():
    """
    knn预测分类
    :return:
    """
    # 读取数据
    data = pd.read_csv('../../数据集/机器学习/分类算法/facebook-v-predicting-check-ins/train.csv')
    # print(data.count(axis=0))

    # 数据预处理
    #1、缩小数据范围
    data = data.query(" x > 0.25 & x < 1.25 & y > 2.5 &y < 2.75")
    # print(data.count(axis=0))
    #2、处理时间数据
    data['time'] = pd.to_datetime(data['time'], unit='s')
    #把日期格式转换成  字典格式
    time_value = pd.DatetimeIndex(data['time'])
    # print(time_value)
    #3、增加分割的日期数据
    data['day'] = time_value.day
    data['hour']= time_value.hour
    data['weekday'] = time_value.weekday
    # print(data.head())

    #4、删除没用的数据
    data = data.drop(['time'],axis=1)
    # print(data.head())
    #5、将签到位置少于n个用户的删除
    place_count = data.groupby('place_id').count()
    # print(place_count)
    tf = place_count[place_count.row_id > 3].reset_index()
    data = data[data['place_id'].isin(tf.place_id)]
    # print(data)
    #
    #取出数据当中的特征值和目标值
    y=data['place_id']
    x=data.drop(['place_id'],axis=1)
    x=data.drop(['row_id'],axis=1)
    #
    #进行数据集的分割
    x_train,x_test,y_train,y_test=train_test_split(x,y,test_size=0.25)

    # 特征工程(标准化)
    std=StandardScaler()

    # 对测试集和训练集的特征值进行标准化
    x_train = std.fit_transform(x_train)
    x_test = std.fit_transform(x_test)


    # 进行算法流程
    knn = KNeighborsClassifier(n_neighbors=7)

    #fit predict  score
    knn.fit(x_train,y_train)

    #得出预测结果
    y_predict = knn.predict(x_test)
    print("预测的目标签到位置为：",y_predict)

    #得出准确率
    print("预测的准确率：",knn.score(x_test,y_test))
    return None

if __name__ == "__main__":
    knn()

预测结果是62.8%，结果并不是很理想，还有很多可以改进的地方，比如数据集的筛选可以重新设置一下，n_neighbors可以设置为5...等等，大家可以下去试一下。KNN算法的实例分析到这里就结束了，最后我们总结一下KNN算法的优缺点。

四、算法总结

1、优点

简单，易于理解，易于实现，无需估计参数，无需训练
适合对稀有事件进行分类
特别适合于多分类（对象具有多个类别标签），KNN比SVM的表现要好。
可用于数值型数据和离散型数据
对异常值不敏感
2、缺点
计算复杂性高，空间复杂性高
样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）
一般数值很大的时候不用这个，计算量太大；但是单个样本又不能太少，否则容易发生误分
最大的缺点是无法给出数据的内在含义
KNN算法到这里就讲完了，文中的第一个案例是参考的非常优秀的博主Jack-Cui : http://blog.csdn.net/c406495762的博客，有兴趣的同学可以看一下。
接下来的这段时间，主要是更新机器学习的算法，希望有兴趣的同学可以关注评论，一起学习。

机器学习(四)：K-近邻(KNN)算法原理及案例分析