1、k-近邻算法介绍

k近邻法(k-nearest neighbor, k-NN)的工作原理是：存在一个样本数据集合，也称作为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似数据(最近邻)的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

1. K-近邻算法.png

举个例子，使用k-近邻算法分类一个电影是爱情片还是动作片。

每部电影的打斗镜头数、接吻镜头数以及电影类型

首先使用欧氏距离计算未知电影与样本集中其他电影的距离。

已知电影与未知电影的距离

将距离列表排序，选出前k个最相似的样本。此处我们假设k=3，将上表中的距离进行排序后前3分别是：He’s Not Really into Dudes，Beautiful Woman，California Man。统计最相似样本的分类，此处很容易知道这3个样本均为爱情片。将分类最多的类别作为未知电影的分类。那么我们就得出结论，未知电影属于爱情片。

欧氏距离公式

2、Python3.6 代码实现

算法一般流程

(1)准备数据集

# -*- coding: UTF-8 -*-
from numpy import *
from numpy import array
# 操作符包
import operator

def creatDataSet():
    """
    Function:
        创建训练数据集
    Parameters:
        无
    Returns:
        group  - 数据集
        labels - 分类标签
    Modify:
        2018-07-23
    """
    group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    lables = ['A','A','B','B']
    return group, lables

运行结果

(2)k-近邻算法

def classify0(inX,dataSet,labels,k):
    """
    Function:
        kNN算法
    Parameters:
        inX - 测试集
        dataSet - 训练集
        labes - 分类标签
        k - 选择距离最小k个点
    Returns:
        sortedClassCount[0][0] - 分类结果
    Modify:
         2018-07-23
    """
    dataSetSize = dataSet.shape[0]
    # tile（A, reps）返回一个shape=reps的矩阵，矩阵的每个元素是A
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistance = sqDiffMat.sum(axis=1)
    distance = sqrt(sqDistance)
    # argsort()返回数组值从小到大的索引值
    sortedDistIndicies = distance.argsort()
    classCount = {}
    for i in range(k):
        voteIlable = labels[sortedDistIndicies[i]]
        # dict.get(key,default=None),返回指定键的值,如果值不在字典中返回默认值。
        classCount[voteIlable] = classCount.get(voteIlable, 0) + 1
    # dict.items()以列表返回可遍历的(键, 值)元组数组
    # 使用字典的第二个元素进行降序排序
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    # 返回次数最多的类别
    return sortedClassCount[0][0]

kNN算法运行结果

3、示例：k-近邻算法实战之约会网站配对效果

海伦收集约会数据存放在文本文件datingTestSet.txt中，有1000行的约会数据，样本主要包括以下3种特征：

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

她约会过的对象可以进行如下分类：

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

算法一般流程

实现代码

def file2Matrix(filename):
    """
    Function:
        打开并解析文件
    Parameters:
        filename - 文件名
    Returns:
        returnMat - 特征矩阵
        classLabelVector - 分类Label向量
    Modify:
        2018-07-23
    """
    f = open(filename, 'r')
    # 读取文件所有内容
    arrayOlines = f.readlines()
    numberOlines = len(arrayOlines)
    returntMat = zeros((numberOlines, 3))
    classLabelVector = []
    index = 0
    for line in arrayOlines:
        # strip(rm)删除所有rm字符。当rm空时默认删除空白符(包括'\n', '\r', '\t', ' ')
        # split(str)将字符串根据str分隔符进行切片，返回列表。
        listFromLine = line.strip().split('\t')
        returntMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return  returntMat, classLabelVector

def autoNorm(dataSet):
    """
    Function:
        归一化数据
    Parameters:
        dataSet - 特征矩阵
    Returns:
        normDataSet - 归一化后的特征矩阵
        ranges - 数据范围
        minVals - 数据集每列最小值
    Modify:
        2018-07-23
    """
    # 获取数据集中每一列的最小数值
    minVals = dataSet.min(0)
    # 获取数据集中每一列的最大数值
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    m = shape(dataSet)[0]
    normDataSet = dataSet - tile(minVals, (m, 1))
    normDataSet = normDataSet / tile(ranges, (m, 1))
    return normDataSet, ranges, minVals

def datingClassTest():
    """
    Function:
        分类器测试函数
    Parameters:
        无
    Returns:
        normDataSet - 归一化后的特征矩阵
        ranges - 数据范围
        minVals - 数据集每列最小值
    Modify:
        2018-07-23
    """
    # 设定测试样本占比
    hoRatio = 0.1
    datingDataMat, datingLabels = file2Matrix( 'D:/PyCharm WorkPlace/machinelearninginaction/Ch02/datingTestSet2.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]
    # 测试样本数量
    numTestVecs = int(m * hoRatio)
    errorCount = 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, result is :%s" % (
         classifierResult, datingLabels[i], classifierResult == datingLabels[i]))
        if (classifierResult != datingLabels[i]):
            errorCount += 1.0
    print("the total error rate is: %f" % (errorCount / float(numTestVecs)))

def classifyPerson():
    """
    函数说明:
        构建可手动输入系统，通过输入一个人的三维特征进行分类输出
    Parameters:
        无
    Returns:
        无
    Modify:
        2018-07-23
    """
    # 定义预测结果
    resultList = ['didntLike', 'smallDoses', 'largeDoses']
    # input()接收任意任性输入，将所有输入默认为字符串处理，并返回字符串类型。
    percentTats = float(input( "percentage of time spent playing video games?"))
    ffMiles = float(input("frequent filer miles earned per year?"))
    iceCream = float(input("liters of ice cream consumed per year?"))
    # 将输入的数值放在数组中
    inArr = array([ffMiles, percentTats, iceCream])
    datingDataMat, datingLabels = file2Matrix('D:/PyCharm WorkPlace/machinelearninginaction/Ch02/datingTestSet2.txt')
    normMat, ranges, minValues = autoNorm(datingDataMat)
    classifierResult = classify0((inArr - minValues) / ranges, normMat, datingLabels, 3)
    print("you will probably like this person:", resultList[classifierResult - 1])

数据可视化结果

分类器测试函数运行结果

手动输入三维特征运行结果

4、示例：手写识别数字

def img2Vector(filename):
    """
    Function:
        将32x32的二进制图像转换为1x1024向量。
    Parameters:
        filename - 文件名
    Returns:
        returnVect - 返回的二进制图像的1x1024向量
    Modify:
        2018-07-23
    """
    returnVect = zeros((1, 1024))
    f = open(filename, 'r')
    for i in range(32):
        lineStr = f.readline()
        for j in range(32):
            returnVect[0,32 * i + j] = int(lineStr[j])
    return returnVect

def handwritingClassTest():
    """
    Function:
        手写识别数字分类测试
    Parameters:
        无
    Returns:
        无
    Modify:
        2018-07-23
    """
    hwLabels = []
    trainingFileDir = 'D:/PyCharm WorkPlace/machinelearninginaction/Ch02/digits/trainingDigits'
    testFileDir = 'D:/PyCharm WorkPlace/machinelearninginaction/Ch02/digits/testDigits'
    trainingFileList = listdir(trainingFileDir)
    m = len(trainingFileList)
    trainingMat = zeros((m,1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        trainingMat[i,:] = img2Vector(trainingFileDir + '/' + fileNameStr)

    testFileList = listdir(testFileDir)
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2Vector(testFileDir + '/' + fileNameStr)
        classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        print("the classifierResult came back with: %d,the real answer is: %d" % (classifierResult, classNumStr))
        if (classifierResult != classNumStr ): errorCount += 1.0
    print("the total number of errors is: %d" % errorCount)
    print("the total error rate is: %f" % (errorCount / float(mTest)))

手写识别数字分类测试运行结果

5、应用scikit-learn库实现手写识别数字

代码与之前类似

def img2Vector(filename):
    """
    Function:
        将32x32的二进制图像转换为1x1024向量。
    Parameters:
        filename - 文件名
    Returns:
        returnVect - 返回的二进制图像的1x1024向量
    Modify:
        2018-07-23
    """
    returnVect = zeros((1, 1024))
    f = open(filename, 'r')
    for i in range(32):
        lineStr = f.readline()
        for j in range(32):
            returnVect[0,32 * i + j] = int(lineStr[j])
    return returnVect

def SklearnHandwritingClassTestS():
    """
    Function:
        手写识别数字分类测试
    Parameters:
        无
    Returns:
        无
    Modify:
        2018-07-23
    """
    hwLabels = []
    trainingFileDir = 'D:/PyCharm WorkPlace/machinelearninginaction/Ch02/digits/trainingDigits'
    testFileDir = 'D:/PyCharm WorkPlace/machinelearninginaction/Ch02/digits/testDigits'
    trainingFileList = listdir(trainingFileDir)
    m = len(trainingFileList)
    trainingMat = zeros((m,1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        trainingMat[i,:] = img2Vector(trainingFileDir + '/' + fileNameStr)

    neigh = kNN(n_neighbors=3, algorithm='auto')
    neigh.fit(trainingMat, hwLabels)
    testFileList = listdir(testFileDir)
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2Vector(testFileDir + '/' + fileNameStr)
        # classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        classifierResult = neigh.predict(vectorUnderTest)
        print("the classifierResult came back with: %d,the real answer is: %d" % (classifierResult, classNumStr))
        if (classifierResult != classNumStr ): errorCount += 1.0
    print("the total number of errors is: %d" % errorCount)
    print("the total error rate is: %f" % (errorCount / float(mTest)))

sklearn运行结果

6、小结

k近邻算法是分类数据最简单最有效的算法。k紧邻算法必须保存全部数据集，如果训练数据集很大，必须使用大量的存储空间。此外，由于必须对数据集中的每个数据计算距离值，实际使用时可能非常耗时。k近邻算法的另外一个缺陷是它无法给出任何数据的基础结构信息，因此我们也无法知晓平均实例样本和典型实例样本具有什么特征。