2.1 k-邻近算法概述

2.1.1 原理

k-邻近算法（k-Nearest Neighbor，KNN），存在一个样本数据集合，称作训练样本集，并且样本集中每个数据都存在标签。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，只选择样本数据集中前k个最相似的数据，通常k是不大于20的整数。最后选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

2.1.2 特点

优点：精度高、对异常值不敏感、无数据输入假定
缺点：计算复杂度高、空间复杂度高
适用数据范围：数值型和标称型

2.1.3 准备：使用Python导入数据

创建kNN.py文件，输入

from numpy import *
import operator

def createDataSet():
    group = array([[1.0, 1.1], [1.0, 1.0], [0, 0],[0, 0.1]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels

在CMD中打开kNN.py所在目录，进入Python交互式开发环境
python
import kNN
group, labels = kNN.createDataSet()

2.1.4 实施kNN分类算法

算法：
对未知类别属性的数据集中的每个点依次执行以下操作：

1. 计算已知类别数据集中的点与当前点之间的距离；
2. 按照距离递增次序排序；
3. 选取与当前点距离最小的k个点；
4. 确定前k个点所在类别的出现频率；
5. 返回前k个点出现频率最高的类别作为当前点的预测分类

代码：

from numpy import *
import operator

def createDataSet():
    # 数据集
    group = array([[1.0, 1.1], [1.0, 1.0], [0, 0],[0, 0.1]])
    # 标签
    labels = ['A', 'A', 'B', 'B']
    return group, labels

def classify(inX, dataSet, labels, k):
    # 获取长度
    dataSetSize = dataSet.shape[0]
    # 作差
    diffMat = 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):
        voteIlable = labels[sortedDistIndicies[i]]
        # 查找voteIlable
        classCount[voteIlable] = classCount.get(voteIlable, 0) + 1
    # 对结果进行排序
    sortedClassCount = sorted(classCount. iteritems(), key = operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]  

输出：

Notes：
.shape[0] 获取矩阵第一维度的长度

tile(inX, (m, n)) 将inX复制n次的结果作为行，再将该行复制m次

diffMat = tile(inX, (dataSetSize, 1)) - dataSet矩阵作差，对应位相减

.sum(axis=1) 求和，axis=1表示按行相加 , axis=0表示按列相加
x.argsort() 将x中的元素从小到大排列，提取其对应的index(索引)，然后输出
.get(key, default=None) key是字典中要查找的键,default为默认值，如果指定键的值不存在时，返回该默认值

sorted(iterable, cmp=None, key=None, reverse=False) 参数iterable，可迭代类型；cmp用于比较的函数；key为用列表元素的某个属性或函数进行作为关键字，有默认值；reverse为排序规则，reverse = True 降序， reverse = False 升序，有默认值；返回值是一个经过排序的可迭代类型，与iterable一样.

operator.itemgetter 定义了一个函数，通过该函数作用到对象上获取值

2.2 示例：使用k-邻近算法改进约会网站的配对效果

2.2.1 准备数据：从文本文件中解析数据

在kNN.py中创建名为file2matrix的函数，处理输入格式问题，该函数的输入为文件名字符串，输出为训练样本矩阵和类标签向量
代码：

def file2matrix(filename):
    # 打开文件
    fr = open(filename)
    arrayOLines = fr.readlines()
    numberOfLines = len(arrayOLines)
    
    # 创建矩阵
    returnMat = zeros((numberOfLines, 3))
    
    classLabelVector = []
    index = 0

    for line in arrayOLines:
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1

    return returnMat, classLabelVector

输出：

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

在Python命令行环境中，输入
import matplotlib
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:,1], datingDataMat[:,2])
plt.show()
输出：

横轴：玩视频游戏所耗时间百分比 纵轴：每周消费的冰淇淋公升数
没有类别标签的散点图难以辨识样本分类，Matplotlib库提供的scatter函数支持个性化标记散点图上的点，重新输入以上代码，调用scatter函数时使用下列参数：
ax.scatter(datingDataMat[:,1], datingDataMat[:,2], 15.0*array(datingLabels), 15.0*array(datingLabels))
输出：

2.2.3 准备数据：归一化数值

在处理不同取值范围的特征值时，通常采用的方法是数值归一化，如将取值范围处理为0到1或者-1到1之间，下面的公式可以将任意取值范围的特征值转化为0到1区间内的值：
newValue = (oldValue - min) / (max - min)
代码：

def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)

    ranges = maxVals - minVals

    normDataSet = zeros(shape(dataset))

    m = dataSet.shape[0]
    normDataSet = dataSet - tile(minVals, (m, 1))
    normDataSet = normDataSet / tile(ranges, (m, 1))

    return normDataSet, ranges, minVals

输出：

Notes：
dataSet.min(0) 参数0使得函数可以从列中选取最小值，而不是选取当前行的最小值

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

代码：

def datingClassTest():
    hoRatio = 0.04
    datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]
    numTestVecs = int(m*hoRatio)
    errorCount = 0
    for i in range(numTestVecs):
        classifierResult = classify(normMat[i,:], normMat[numTestVecs:m,:], datingLabels[numTestVecs:m], 3)
        print("The classifier came back with: %s\t, the real answer is: %s" % (classifierResult, datingLabels[i]))
        if (classifierResult != datingLabels[i]):
            errorCount += 1.0
    print("The total error rate is: %f" % (errorCount/float(numTestVecs)))

输出：

Ratio=0.04

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

代码：

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("Frequent flier miles earned per year?"))
    iceCream = float(input("Liters of ice cream consumed per year?"))

    datingDataMat, datingLabels = file2matrix("datingTestSet2.txt")
    normMat, ranges, minVals = autoNorm(datingDataMat)

    inArr = array([ffMiles, percentTats, iceCream])

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

输出：