kNN(k近邻)方法在《机器学习实战》这本书里是最先介绍的算法，估计也是最简单的了。。。k-近邻算法(kNN)工作原理：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的数据之后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中最相似数据（最近邻）的分类标签。一般来说，我们只选取样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常来说k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

举个栗子，如果没有告诉坐标平面内一二三四象限的定义（其实我已经忘了咋定义的了），已知(1, 1)，(-1, 1)，(-1, -1)，(1, -1)分别在第一二三四象限，现在再给一个点(x, y)，你猜这个点最可能是在第几象限。。。我猜离已知那四个点哪个最近，就是他对应的第几象限。为什么？我猜的，只可意会不可言传。。。俗话说近朱者赤近墨者黑，也就是跟啥走得近就是啥一个道理。。。

根据上面所说的，推广到多维，也是可以的，先来一小段代码实现kNN分类(需要先安装python和pip然后在pip install numpy)，过程的解释都在注释中，创建kNN.py：

# -*- coding: utf8 -*-

from numpy import *
import operator

def createDataSet():
    group = array([[1.0, 1.0], [-1.0, 1.0], [-1.0, -1.0], [1.0, -1.0]])
    labels = ['第一象限', '第二象限', '第三象限', '第四象限']

    return group, labels


def classify0(inX, dataSet, labels, k):
    '''
    funtion: 使用kNN的方法计算标签为lables的dataSet中的数据为样本，inX的前k个近邻的计算结果
    args:
        inX: 待分类的向量
        dataSet: 已有标签的向量集合
        labels: 与dataSet对应的标签
        k： kNN中的前k个
    return:
        kNN的计算结果,lables中的一个
    '''
    # 获取dataSet中向量数量，shape返回numpy.array的维度，返回值为tuple类型
    dataSetSize = dataSet.shape[0]
    # 把inX重复至与dataSet数量相同并与其做差，其中tile把inX重复(dataSetSize, 1)次构造成一个numpy.array，第二个参数指定维度
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet
    # 将diffMat中的每个元素都乘方
    sqDiffMat = diffMat ** 2
    # 将sqDiffMat中的向量在第二维度上累加，axis的值就是维度，从0开始，与shape返回的纬度顺序对应
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5
    # numpy.array.argsort() 返回array的排序后的键值数字顺序，而非是array中的数据
    sortedDistIndicies = distances.argsort()
    classCount = {}
    for i in range(k):
        # 每个label出现一次就在classCount里计数一次
        voteLabel = labels[sortedDistIndicies[i]]
        classCount[voteLabel] = classCount.get(voteLabel, 0) + 1
    # 因为classCount是个字典，则key=operator.itemgetter(1)就是按照字典里的值排序
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)

    return sortedClassCount[0][0]


def file2matrix(filename):
    file = open(filename)
    arrayOfLines = file.readlines()
    # 看看有几行数据，就是多少样本
    numberOfLines = len(arrayOfLines)
    # 数据里面前3列是特征值
    returnMat = zeros((numberOfLines, 3))
    # 数据里面最后一列是标签
    classLabelVector = []
    index = 0
    for line in arrayOfLines:
        # 删除一行中的首尾的空白字符(如结束换行的\r\n等)
        line = line.strip()
        # 每行用 \t 分割放进list
        listFromLine = line.split('\t')
        # list的前3项就是特征值
        returnMat[index, :] = listFromLine[0:3]
        # list的最后一项是标签
        classLabelVector.append(listFromLine[-1])
        index += 1

    return returnMat, classLabelVector


if __name__ == '__main__':
    group, labels = createDataSet()
    print classify0([0.01, -0.3], group, labels, 1)

运行上述程序执行结果是’第四象限’，哎呦不错还说明。。。因为已知标签中每类都只有一个，所以k就只能是1了。当然实际情况不会是这样的这都木有啥意义了。

这本书告诉我，k近邻算法流程有：收集数据、准备数据、分析数据、测试算法、使用算法（kNN就木有训练算法了，把N个已知的标签以摆只管算就好了。。。）。书中的例子是给海伦找对象，海伦是一个很屌的人，自己收集的约会数据就有1000条，样本主要包含3种特征：每年获得的飞行常客里程数、玩视频游戏所消耗时间百分比、每周消费的冰淇淋公升数，并且为每条都标注有”didntLike”、”smallDoses”或”largeDoses”。

首先就是收集数据，海伦已经收集好了。。。不用咱们自己去约1000个了。。。拿去下载：datingTestSet（这个页面里有下载链接，不跳转别的网站不要积分。。。无毒无公害的文本文件。。。）

然后是准备数据，新建一个文件夹，就叫kNN吧，然后把datingTestSet.txt放进去。。。好的准备好了。。。还得把文件里面的数据能够格式化的读出来。打开文件看看发现第一列应该是”每年获得的飞行常客里程数”，第二列应该是”玩视频游戏所消耗时间百分比”，第三列应该是”每周消费的冰淇淋公升数”，第四列就是标签了，每列数据之间tab分割。我们把数据用程序读出来，还是在kNN.py中加入下面的函数：

def file2matrix(filename):
    file = open(filename)
    arrayOfLines = file.readlines()
    # 看看有几行数据，就是多少样本
    numberOfLines = len(arrayOfLines)
    # 数据里面前3列是特征值
    returnMat = zeros((numberOfLines, 3))
    # 数据里面最后一列是标签
    classLabelVector = []
    index = 0
    for line in arrayOfLines:
        # 删除一行中的首尾的空白字符(如结束换行的\r\n等)
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index, :] = listFromLine[0:3]
        classLabelVector.append(listFromLine[-1])
        index += 1

    return returnMat, classLabelVector

然后在if name == ‘main’:下面修改一下就可以测试file2matrix()函数好不好使了。

if __name__ == '__main__':
    #group, labels = createDataSet()
    #print classify0([0.01, -0.3], group, labels, 1)
    # 此处文件位置改成刚才datingTestSet.txt保存的目录即可
    group, labels = file2matrix('C:\Users\CPY\Desktop\MLiA_SourceCode\Ch02\datingTestSet.txt')
    print group[0:10]
    print labels[0:10]

运行一下观察输出，就是文件的前10行内容，说明数据解析的还可以。

然后是分析数据，通过画图的方式最直观明了，接下来用matplotlib画图。新建show.py与kNN.py同目录，要是引入时报错”ImportError: cannot import name unpack_labeled_data“就pip install matplotlib –upgrade更新一下就好了，代码里顺路解决了一个matplotlib显示中文是框框或者直接报错的问题：

# -*- coding: utf8 -*-

import kNN
import matplotlib
import matplotlib.pyplot as plt
from ImageEnhance import Color

# 借助上一步所写的函数读取文件分别获得特征和标签
# group 三列分别是：每年获得的飞行常客里程数、玩视频游戏所消耗时间百分比、每周消费的冰淇淋公升数
group, labels = kNN.file2matrix('C:\Users\CPY\Desktop\MLiA_SourceCode\Ch02\datingTestSet.txt')
# 选一个系统里面有的字体文件，要不中文显示很坑
myfont = matplotlib.font_manager.FontProperties(fname='C:/Windows/Fonts/msyh.ttc') 
# 创建一个figure，参数为窗口的显示名字
fig = plt.figure(u'海伦的口味')
# 创建一个subplot，等同于ax = fig.add_subplot(1, 2, 1)
ax = fig.add_subplot(121)
ax1 = fig.add_subplot(122)
# 颜色越深越喜欢
colors = []
for label in labels:
    if label == 'didntLike':
        colors.append("#AAAAAA")
    elif label == 'smallDoses':
        colors.append("#666666")
    else:
        colors.append("#000000")
# 将玩视频游戏所消耗时间百分比和每周消费的冰淇淋公升数分别作为y轴和x轴描点
ax.scatter(group[:, 1], group[:, 2], c=colors)
# 设置fontproperties为选的myfont，要不中文显示就哭了，还有字符串前必须有u
ax.set_title(u'视频游戏 - 冰淇淋', fontproperties=myfont)
ax.set_xlabel(u'玩视频游戏所消耗时间百分比', fontproperties=myfont)
ax.set_ylabel(u'每周消费的冰淇淋公升数', fontproperties=myfont)

ax1.scatter(group[:, 0], group[:, 1], c=colors)
ax1.set_title(u'飞行常客里程 - 视频游戏', fontproperties=myfont)
ax1.set_xlabel(u'每年获得的飞行常客里程数', fontproperties=myfont)
ax1.set_ylabel(u'玩视频游戏所消耗时间百分比', fontproperties=myfont)

plt.show()

观察如下一部分数据发现，三个数据大小很不一样，这时候在计算样本之间距离的时候大的数很明显会影响很大，小的都没啥感觉了。。。所以得对数据进行归一化处理。就是把这些数据都转换成0-1之间的数。方法就是newValue = (oldValue – minValue) / (maxValue – minValue)

40920   8.326976    0.953952    largeDoses
14488   7.153469    1.673904    smallDoses
26052   1.441871    0.805124    didntLike
75136   13.147394   0.428964    didntLike
38344   1.669788    0.134296    didntLike

再接着在kNN.py中再加入一个归一化函数，并适当修改测试：

def autoNormal(dataSet):
    # 计算每一列的最大值和最小值
    minValue = dataSet.min(0)
    maxValue = dataSet.max(0)
    ranges = maxValue - minValue
    # 创建归一化后的值
    normalDataSet = zeros(shape(dataSet))
    # 对于每一个样本都与各个特征的最小值相减再除以范围，得到归一化的值
    m = dataSet.shape[0]
    normalDataSet = dataSet - tile(minValue, (m, 1))
    normalDataSet = normalDataSet / tile(ranges, (m, 1))
    
    return normalDataSet, ranges, minValue


if __name__ == '__main__':
    # 此处文件位置改成刚才datingTestSet.txt保存的目录即可
    group, labels = file2matrix('C:\Users\CPY\Desktop\MLiA_SourceCode\Ch02\datingTestSet.txt')
    print autoNormal(group)

然后就来到了测试算法的步骤：把数据集中的前一部分数据作为待分类样本，其余的作为训练样本，同样在kNN.py中加入新的测试函数。

def datingClassTest():
    # 测试数据所占的比例
    hoRatio = 0.1
    datingDataMat, datingLables = file2matrix('C:\Users\CPY\Desktop\MLiA_SourceCode\Ch02\datingTestSet.txt')
    normalMat, ranges, minValues = autoNormal(datingDataMat)
    m = normalMat.shape[0]
    numTestVectors = int(m * hoRatio)
    # 浮点方便除法
    errorCounter = 0.0
    for i in range(numTestVectors):
        classifierResult = classify0(normalMat[i, :], normalMat[numTestVectors:m, :], datingLables[numTestVectors:m], 3)
        print "the classifier came back with: %s, and the real label is: %s" % (classifierResult, datingLables[i])
        if classifierResult != datingLables[i]:
            errorCounter += 1.0
    print "the total error rate is: %f" % (errorCounter / float(numTestVectors)) 

if __name__ == '__main__':
    datingClassTest()

结果错误率是5%，应该还可以的，所以可以进一步使用算法，给海伦一个方便用的程序，省得他再约会发愁，，，

# -*- coding: utf8 -*-
import kNN
import numpy

def classifyPerson():
    # 海伦的输入，获取待分类人的各项特征值
    percentTats = float(raw_input("percentage of time spent in playing video games?"))
    ffMiles = float(raw_input("frequent flier miles earned per year?"))
    iceCream = float(raw_input("liters of ice cream consumed per week?"))
    
    # 获取海伦已标注过的约会对象的数据
    datingDataMat, datingLabels = kNN.file2matrix('C:\Users\CPY\Desktop\MLiA_SourceCode\Ch02\datingTestSet.txt')
    # 进行归一化处理
    normalMat, ranges, minValues = kNN.autoNormal(datingDataMat)
    inArr = numpy.array([ffMiles, percentTats, iceCream])
    # 将输入的数据进行kNN算法计算
    classifierResult = kNN.classify0(inArr, datingDataMat, datingLabels, 3)
    # 为海伦输出结果
    print "you will probably like this person: ", classifierResult
    

if __name__ == '__main__':
    classifyPerson()

运行程序，玩玩试试，还可以，海伦可以放心大胆的约会去了。。。

percentage of time spent in playing video games?10
frequent flier miles earned per year?10000
liters of ice cream consumed per week?0.5
you will probably like this person:  smallDoses