1 背景

1.1 k近邻算法的概述

（1）k近邻算法的简介

k-近邻算法是属于一个非常有效且易于掌握的机器学习算法，简单的说就是采用测量不同特征值之间距离的方法对数据进行分类的一个算法。

（2）k近邻算法的工作原理

给定一个样本的集合，这里称为训练集，并且样本中每个数据都包含标签。对于新输入的一个不包含标签的数据，通过计算这个新的数据与每一个样本之间的距离，选取前k个，通常k小于20，以k个剧里最近的数据的标签中出现次数最多的标签作为该新加入的数据标签。

（3）k近邻算法的案例

当前统计了6部电影的接吻和打斗的镜头数，假设有一部未看过的电影，如何确定它是爱情片还是动作片呢？

电影名称	打斗镜头	接吻镜头	电影类型
California Man	3	104	爱情片
He‘s Not Really into Dudes	2	100	爱情片
Beautiful Woman	1	81	爱情片
Kevin Longblade	101	10	动作片
Robo Slayer 3000	99	5	动作片
Amped II	98	2	动作片
？	18	90	未知

根据knn算法的原理，我们可以求出，未知电影与每部电影之间的距离(这里采用欧式距离）

以California Man为例

>>>((3-18)**2+(104-90)**2)**(1/2)
20.518284528683193

电影名称	与未知i电影之间的距离
California Man	20.5
He‘s Not Really into Dudes	18.7
Beautiful Woman	19.2
Kevin Longblade	115.3
Robo Slayer 3000	117.4
Amped II	118.9

因此我们可以找到样本中前k个距离最近的电影，假设k=3，前三部电影均为爱情片，因此我们判定未知电影属于爱情片。

1.2 用python代码实现k近邻算法

（1）计算已知类别数据集中的每个点与当前点之间的距离

（2）按照距离递增次序排序

（3）选取与当前点距离最小的k个点

（4）确定前k个点所在类别出现的频率

（5）返回前k个点出现频率最高的类别作为当前点的预测分类

import numpy as np
import operator

def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = np.tile(inX, (dataSetSize,1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances**0.5
    sortedDistIndicies = distances.argsort()     
    classCount={}          
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

（6）案例

>>>group = np.array([[1, 1.1],
...                 [1, 1],
...                 [0, 0],
...                 [0, 0.1]])
>>>labels = ['A', 'A', 'B', 'B']
>>>classify0([0,0], group, labels, 3)
'B'

1.3 如何测试分类器

正常来说为了测试分类器给出来的分类效果，我们通常采用计算分类器的错误率对分类器的效果进行评判。也就是采用分类出错的次数除以分类的总次数。完美的分类器的错误率为0，而最差的分类器的错误率则为1。

2 使用kNN算法改进约会网站的匹配效果

2.1 案例介绍

朋友海伦在使用约会软件寻找约会对象的时候，尽管网站会推荐不同的人选，但并不是每一个人她都喜欢，具体可以分为以下三类：不喜欢的人，魅力一般的人，极具魅力的人。尽管发现了以上的规律，但是海伦依旧无法将网站推荐的人归到恰当的类别，因此海伦希望我们的分类软件能更好的帮助她将匹配到的对象分配到确切的分类中。

2.2 数据的准备

以下提供两种下载数据集的渠道：

《机器学习实战官方下载python2版本代码》

《202xxx的github下载python3版本代码》

数据存放在datingTestSet2.txt中，每个样本占一行，共1000行数据，主要包括了以下三个特征：

每年获得的飞行常客里程数，玩视频游戏所耗时间百分比，每周消费冰淇淋公升数

在数据输入到分类器之前，需要把数据转换成分类器可以识别的样式

def file2matrix(filename):
    fr = open(filename)
    numberOfLines = len(fr.readlines())         #get the number of lines in the file
    returnMat = np.zeros((numberOfLines,3))        #prepare matrix to return
    classLabelVector = []                       #prepare labels return   
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat,classLabelVector

使用file2matix读取到的特征数据(datingDataMat)如下

array([[4.0920000e+04, 8.3269760e+00, 9.5395200e-01],
        [1.4488000e+04, 7.1534690e+00, 1.6739040e+00],
        [2.6052000e+04, 1.4418710e+00, 8.0512400e-01],
        ...,
        [2.6575000e+04, 1.0650102e+01, 8.6662700e-01],
        [4.8111000e+04, 9.1345280e+00, 7.2804500e-01],
        [4.3757000e+04, 7.8826010e+00, 1.3324460e+00]]

标签数据(datingLabels)如下

[3,2,1,1,1,1,3,3,...,3,3,3]

2.3 数据分析：使用Matplotlib创建散点图

（1）玩视频游戏所耗时间百分比与每周消费冰淇淋公升数之间的相关关系图

import matplotlib
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:,0], datingDataMat[:,1], 15.0*np.array(datingDLabels), 15.0*np.array(datingDLabels))
plt.show()

其中，y轴为每周消费冰淇淋公升数，x轴为玩视频游戏所耗时间百分比

紫色为不喜欢，绿色为魅力一般，黄色为极具魅力

（2）飞行常客里程数与玩视频游戏所耗时间百分比之间的相关关系图

import matplotlib
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:,0], datingDataMat[:,1], 15.0*np.array(datingDLabels), 15.0*np.array(datingDLabels))
plt.show()

其中，y轴为玩视频游戏所耗时间百分比，x轴为飞行常客里程数

紫色为不喜欢，绿色为魅力一般，黄色为极具魅力

（3）飞行常客里程数与每周消费冰淇淋公升数之间的相关关系图

import matplotlib
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:,0], datingDataMat[:,2], 15.0*np.array(datingDLabels), 15.0*np.array(datingDLabels))
plt.show()

其中，y轴为每周消费冰淇淋公升数，x轴为飞行常客里程数

紫色为不喜欢，绿色为魅力一般，黄色为极具魅力

 2.4 数据准备：归一化数值

 由于通过欧式距离计算样本之间的距离时，对于飞行常客里程数来说，数量值巨大，会对结果影响的权重也会较大，而且远远大于其他两个特征，但是作为三个等权重之一，飞行常客里程数并不应该如此严重影响结果，例子如下

((0-67)**2+(20000-32000)**2+(1.1-0.1)**2)**1/2

	玩视频游戏所耗时间百分比	飞行常客里程数	每周消费冰淇淋公升数	样本分类
1	0.8	400	0.5	1
2	12	134000	0.9	3
3	0	20000	1.1	2
4	67	32000	0.1	2

通常我们在处理不同取值范围的特征时，常常采用归一化进行处理，将特征值映射到0-1或者-1到1之间，通过对（列中所有值-列中最小值）/（列中最大值-列中最小值）进行归一化特征

def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = np.zeros(np.shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - np.tile(minVals, (m,1))
    normDataSet = normDataSet/np.tile(ranges, (m,1))   #element wise divide
    return normDataSet, ranges, minVals

 2.5 测试算法：作为完整程序验证分类器

评估正确率是机器学习算法中非常重要的一个步骤，通常我们会只使用训练样本的90%用来训练分类器，剩下的10%用于测试分类器的正确率。为了不影响数据的随机性，我们需要随机选择10%数据。

（1）使用file2matrix函数导入数据样本

（2）使用autoNorm对数据进行归一化处理

（3）使用classify0对90%的数据进行训练，对10%的数据进行测试

（4）输出测试集中的错误率

def datingClassTest():
    hoRatio = 0.50      #hold out 10%
    datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')       #load data setfrom file
    normMat, ranges, minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]
    numTestVecs = int(m*hoRatio)
    errorCount = 0.0
    for i in range(numTestVecs):
        classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)
        print ("the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i]))
        if (classifierResult != datingLabels[i]): errorCount += 1.0
    print ("the total error rate is: %f" % (errorCount/float(numTestVecs))）
    print (errorCount)

最后得到分类器处理的约会数据集的错误率为2.4%，这是一个相当不错的结果，同样我们可以改变hoRatio的值，和k的值，检测错误率是否随着变量的变化而增加

 2.5 使用算法：构建完整可用的系统

通过上面的学习，我们尝试给海伦开发一套程序，通过在约会网站找到某个人的信息，输入到程序中，程序会给出海伦对对方的喜欢程度的预测值：不喜欢，魅力一般，极具魅力

import numpy as np
import operator

def file2matrix(filename):
    fr = open(filename)
    numberOfLines = len(fr.readlines())         #get the number of lines in the file
    returnMat = np.zeros((numberOfLines,3))        #prepare matrix to return
    classLabelVector = []                       #prepare labels return   
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat,classLabelVector

def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = np.zeros(np.shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - np.tile(minVals, (m,1))
    normDataSet = normDataSet/np.tile(ranges, (m,1))   #element wise divide
    return normDataSet, ranges, minVals

def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = np.tile(inX, (dataSetSize,1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances**0.5
    sortedDistIndicies = distances.argsort()     
    classCount={}          
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

def classifyPerson():
    resultList = ["not at all", "in small doses", "in large doses"]
    percentTats = float(input("percentage of time spent playing video games?"))
    ffMiles = float(input("ferquent fiter miles earned per year?"))
    iceCream = float(input("liters of ice ice crean consumed per year?"))
    datingDataMat,datingLabels = file2matrix('knn/datingTestSet2.txt')       #load data setfrom file
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = np.array([percentTats, ffMiles, iceCream])


    classifierResult = classify0((inArr-minVals)/ranges, normMat, datingLabels,3)
    print ("You will probably like this person:", resultList[classifierResult-1])

if __name__ == "__main__":
    classifyPerson()#10    10000    0.5

输入测试数据：

percentage of time spent playing video games?10
ferquent fiter miles earned per year?10000
liters of ice ice crean consumed per year?0.5
You will probably like this person: not at all

3 使用kNN算法制作手写识别系统

3.1 案例介绍

以下案例以数字0-9的分类为例，简述如何采用k近邻算法对手写数字进行识别。

 通常手写输入的数字都是图片格式，我们需要将图片转换成knn算法可以识别的结构化数据，简单来说就是读取图片中的像素点，像素点值通常在0-255之间，0为黑色，255为白色，因此可以将值大于250的像素点标记为1，其余标记为0，手写数字1可以用以下数据集表示：

1	1	1	1	1	1	1	1	1	1
1	1	1	1	0	0	0	1	1	1
1	1	1	1	0	0	0	1	1	1
1	1	1	1	0	0	1	1	1	1
1	1	1	1	0	0	1	1	1	1
1	1	1	1	0	0	1	1	1	1
1	1	1	1	0	0	1	1	1	1
1	1	1	1	0	0	1	1	1	1
1	1	1	0	0	0	0	1	1	1
1	1	1	1	1	1	1	1	1	1

3.2 数据准备：将图像转换为测试向量

 以下提供两种下载数据集的渠道：

《机器学习实战官方下载python2版本代码》

《202xxx的github下载python3版本代码》

数据集存放在digits.zip中，其中用1代表手写的区域，用0代表空白区域

（大佬们，中秋快乐！！！） 

 通过img2vector函数对数据进行读取，并且返回数组

def img2vector(filename):
    returnVect = np.zeros((1,1024))
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0,32*i+j] = int(lineStr[j])
    return returnVect

3.3 测试算法，使用kNN识别手写数字

（1）使用listdir读取trainingDigits目录下所有文件作为训练数据

（2）使用listdir读取testDigits目录下所有文件作为测试数据

（3）将训练数据与测试数据喂入knn算法中

def handwritingClassTest():
    hwLabels = []
    trainingFileList = listdir('trainingDigits')           #load the training set
    m = len(trainingFileList)
    trainingMat = np.zeros((m,1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)
    testFileList = listdir('testDigits')        #iterate through the test set
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
        classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        print ("the classifier came back with: %d, the real answer is: %d"% (classifierResult, classNumStr))
        if (classifierResult != classNumStr): errorCount += 1.0
    print ("\nthe total number of errors is: %d" % errorCount)
    print ("\nthe total error rate is: %f" % (errorCount/float(mTest)))

输出训练结果，错误率为1.1628%，通过改变k值与训练样本都会使得错误率发生变化。

the classifier came back with: 7, the real answer is: 7
the classifier came back with: 7, the real answer is: 7
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 0, the real answer is: 0
the classifier came back with: 0, the real answer is: 0
the classifier came back with: 4, the real answer is: 4
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 7, the real answer is: 7
the classifier came back with: 7, the real answer is: 7
the classifier came back with: 1, the real answer is: 1
the classifier came back with: 5, the real answer is: 5
the classifier came back with: 4, the real answer is: 4
the classifier came back with: 3, the real answer is: 3
the classifier came back with: 3, the real answer is: 3

the total number of errors is: 11

the total error rate is: 0.011628

4 总结

4.1 k-近邻算法的优缺点

（1）优点：精度高，对异常值不敏感，无数据输入假定

（2）缺点：计算复杂度高，空间复杂度高

适用数据范围：数值型和标称型

4.2 k-近邻算法的一般流程

（1）收集数据：可以使用任何方法

（2）准备数据：距离计算所需的数值，最好是结构化的数据格式

（3）分析数据L：可以使用任何方法

（4）训练算法：此步骤不适合与k近邻算法

（5）测试算法：计算错误率

（6）使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

4.3 k-近邻算法使用需要注意的问题

（1）数据特征之间量纲不统一时，需要对数据进行归一化处理，否则会出现大数吃小数的问题

（2）数据之间的距离计算通常采用欧式距离

（3）kNN算法中K值的选取会对结果产生较大的影响，一般k值要小于训练样本数据的平方根

（4）通常采用交叉验证法来选择最优的K值

5 Reference

《机器学习实战》