内容：

• K-近邻算法基本理论
• 如何使用距离测量的方法分类物品
• 使用Python从文本文件中导入并解析数据
• 避免计算距离时可能碰到的常见错误
• 如何使用K-近邻算法改进约会网站和手写数字识别系统

0.1 KNN概述

K-近邻算法采用不同特征值之间的距离方法进行分类。
优点：精度高、对异常值不敏感、无数据输入假定
缺点：计算复杂度高、空间复杂度高
适用数据范围：数值型和标称型

Q：什么是数值型数据？什么是标称型数据？
答：①数值型：数值型目标变量可以从无限的数值中取值，如0.100，42.001等 (数值型目标变量主要用于回归分析)
②标称型：标称型目标变量的结果只在有限目标集中取值，如真与假(标称型目标变量主要用于分类)

KNN工作原理：存在一个训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前K个最相似的数据中出现次数最多的分类，作为新数据的分类。

K-近邻算法的一般流程

1. 收集数据：可以使用任何方法。
2. 准备数据：距离计算所需要的数值，最好是结构化的数据格式。
3. 分析数据：可以使用任何方法。
4. 训练算法：此步骤不适用于k-近邻算法。
5. 测试算法：计算错误率。
6. 使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

0.1.1使用Python导入数据

导入两个模块：科学计算包Numpy和运算符模块operator
K-近邻算法执行排序操作时将使用这个模块提供的函数。
使用createDataSet()函数，创建数据集和标签。代码如下：

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

group里面有4组数据，每个数据有两个我们已知的属性或者特征值。上面的group矩阵每行包含一个不同的数据，而lables包含了每个数据点的标签信息，lables包含的元素个数等于group矩阵行数。这里我们将数据点(1, 1.1)定义为类A，数据点(0, 0.1)定义为类B。

k-近邻算法：带有4个数据点的简单例子

0.1.2 实施kNN算法

这里的目的是：使用k-近邻算法将每组数据划分到某个类中。对未知类别属性的数据集中的每个点依次执行以下步骤：

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

def classify0(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):
        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]

• 关于numpy中shape的用法：https://www.cnblogs.com/bnuvincent/p/7754932.html
  shape函数的功能是查看矩阵或者数组的维数。

e = eye(3) #建立一个单位矩阵
e.shape  #查看矩阵维数：(3,3)

c = array([[1,1],[1,2],[1,3],[1,4]])
c.shape  #查看矩阵c的维数：(4,2)
c.shape[0]  #查看矩阵行数：4
c.shape[1]  #查看矩阵列数：2

• 关于numpy中tile的用法：https://www.cnblogs.com/chulin/p/9261752.html
  tile的功能是重复某个数组，比如tile(A,n)，功能是将数组A重复n次，构成一个新的数组。

0.1.3 如何测试分类器

分类器给出的答案是否符合我们的预期，我们可以使用多种方法检测分类器的正确率，例如：我们使用已知答案的数据，看看分类器给出的结果是否符合预期结果。通过大量的测试数据，我们可以得到分类器的错误率——分类器给出的错误结果次数除以测试执行的总数。
错误率是常用的评估方法：完美分类器的错误率为0，最差分类器错误为1，也即是根本无法找到哪怕一个正确答案！

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

海伦使用约会网站，曾交往过3类人：

1. 不喜欢的人
2. 魅力一般的人
3. 极具魅力的人
   她希望周一~周五约会那些魅力一般的人，而周末更喜欢与那些极具魅力的人为伴。海伦收集了一些数据，有助于约会网站匹配对象的归类。
   在约会网站使用k-近邻算法的步骤

• 收集数据：提供文本文件
• 准备数据：python解析文本
• 分析数据：使用Matplotlib画二维扩散图
• 训练算法：不需要
• 测试算法：使用海伦提供的部分数据作为测试样本
  测试样本与非测试样本的区别在于：测试样本是已经完成分类的数据，如果预测分类与实际分类不同，则标记为一个错误。
• 使用算法：产生简单的命令行程序，然后海伦可以输入一些特征数据以判断对方是否是自己喜欢的类型

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

海伦的数据有1000行，样本包含3个特征：

• 每年获得的飞行常客里程数
• 玩视频游戏所耗时间百分比
• 每周消费的冰淇淋公升数
  将上述特征数据输入到分类器之前，必须先将数据的格式改为分类器可以接受的格式。为此，创建file2matrix函数，以此来处理输入格式问题。该函数的输入为文件名字符串，输出为训练样本矩阵和类标签向量。

#将文本记录转换为Numpy的解析程序
def file2matrix(filename):
    fr = open(filename)
    numberOfLines = len(fr.readlines())         #得到文件行数
    returnMat = zeros((numberOfLines,3))        #创建返回的numpy矩阵
    classLabelVector = []                       
    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

numpy数组和Python数组：
使用numpy数组可以通过from numpy import array将其导入，也可以通过直接导入所有的numpy库将其导入。由于numpy库提供的数组操作并不支持python自带的数据类型，因此在编写代码时注意不要使用错误的数组类型。

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

if __name__ == "__main__":
    datingDataMat,datingLables = file2matrix("datingTestSet2.txt")
    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函数支持个性化标记散点图上的点。如下：

if __name__ == "__main__":
    #注意datingTestSet2.txt和datingTestSet.txt的区别，将lable转换为数字标签
    datingDataMat,datingLables = file2matrix("datingTestSet2.txt")
    #print(datingDataMat)
    datingLables = [int(i) for i in datingLables]  #将字符串列表转换为整型列表
    #print(datingLables[0:20])
    import matplotlib
    import matplotlib.pyplot as plt #将函数重命名为简单形式
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLables),15.0*array(datingLables))
    plt.show()

带有样本分类标签的约会数据散点图。虽然能够比较容易地区分数据点从属类别，但依然很难根据这张图得出结论性信息

每年赢得的飞行常客里程数与玩视频游戏所占百分比的约会数据散点图。约会数据有三个特征，通过图中展示的两个特征更容易区分数据点从属的类别

0.2.3 准备数据：归一化数值

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))   #element wise divide
    return normDataSet, ranges, minVals