K-近邻算法（k-Nearest Neighbor）

简单的说，K-近邻算法采用测量不同特征值之间的距离方法进行分类。｛使用欧几里得度量（euclidean metric）｝
优点：精度高、对异常值不敏感、无数据输入假定。
缺点：计算复杂度高、空间复杂度高。
适用数据范围：数值型和标程称型。
 
K-近邻算法的一般流程
（1）收集数据：可以使用任何方法。
（2）准备数据：距离计算所需要的数值，最好是结构化的数据格式。
（3）分析数据：可以使用任何方法。
（4）训练算法：此步骤不适用于K-近邻算法。
（5）测试算法：计算错误率。
（6）使用算法：首先需要输入样本数据和结构化的输出结果，然后运行K-近邻算法判断输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。
 
K-近邻算法是分类数据最简单最有效的算法。K-近邻算法是基于实例的学习，使用算法时我们必须有接近实际数据的训练样本数据。K-近邻算法必须保存全部数据集，如果训练数据集的很大，必须使用大量的存储空间。此外，由于必须对数据集中的没个数据计算距离值。实际使用时可能非常耗时。
K-近邻算法的另一个缺陷是无法给出任何数据的基础结构信息，因此我们也无法知晓平均实例样本和典型实例样本具有什么特征。
 
官方给的是python 2的代码，很多东西在python 3中已经无法使用，并且python 2 也快停止维护了。
增加了很多注释，能够更方便的理解 。
 

# -*- coding: utf-8 -*-
# K阶邻算法
from numpy import *
import operator
import matplotlib
import matplotlib.pyplot as plt
from os import listdir
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
# 用kNN计算电影级别
def classify0(inX, dataSet, labels, k):  # 测试  训练  结果  k阶
    # shape 的功能是查看矩阵或者数组的维数。
    # shape()或者a.shape返回的是矩阵的行列数（[a,b]，其中a是行数，b是列数）
    # shape[0] 只返回行数  shape[1] 只返回列数
    dataSetSize = dataSet.shape[0]
    # tile 重复A的各个维度
    # tile（A,B） 在行方向上重复A次，在列方向上重复B次
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet
    # diffMat的二次方  （a**b == a的b次方）
    sqDiffMat = diffMat ** 2
    # sum  numpy 下的方法 默认axis为None，表示将所有元素的值相加 axis=1表示按行相加 , axis=0表示按列相加
    sqDistances = sqDiffMat.sum(axis=1)
    # 开根号
    distances = sqDistances ** 0.5
    # argsort返回数值从小到大的索引（值数组索引0,1,2,3）
    sortedDistIndecies = distances.argsort()
    # 新建字典
    classCount = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndecies[i]]
        # 在字典中查找voteIlabel，如果找不到返回0，默认为 None
        # 不断累加计数的过程
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    # python3中：classCount.iteritems()修改为classCount.items()
    # sorted(iterable, cmp=None, key=None, reverse=False) --> new sorted list。
    # reverse默认升序
    # key关键字排序itemgetter（1）按照第1位元素的大小（字典序）排序
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    # 返回的sortedClassCount 是对出现次数的排序 返回排序的第一个元素的第一个子元素
    # eg:[('A', 2), ('B', 1)]   返回  ('A', 2)  中的  第0个  'A'
    return sortedClassCount[0][0]
# 从文件里读取数据
def file2Matrix(filename):
    fr = open(filename)
    # readlines() 方法用于读取所有行(直到结束符 EOF)并返回列表
    arrryOlines = fr.readlines()
    # 获取数据行数
    numberOfLines = len(arrryOlines)
    # zeros 创建0矩阵
    returnMat = zeros((numberOfLines, 3))
    classLabelVector = []
    index = 0
    for line in arrryOlines:
        line = line.strip()
        listFromLine = line.split('\t')
        # t[index, :]   ==   t[index: , index: ]  对于二维数组的遍历
        # t[: ,index]   ==   t[: index, : index]  对于二维数组的遍历
        returnMat[index, :] = listFromLine[0:3]
        # -1索引表示最后一列元素,位label信息存储在classLabelVector
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat, classLabelVector
# 画特征图
def paintFigure(datingDataMat, datingLabels):
    fig = plt.figure()
    ax = fig.add_subplot(111)
    # 没样本分类的特征图
    # ax.scatter(datingDataMat[:, 1], datingDataMat[:, 2])
    # 有样本分类的特征图
    ax.scatter(datingDataMat[:, 1], datingDataMat[:, 2], 15.0 * array(datingLabels), 15.0 * array(datingLabels))
    plt.show()
# 归一化数值方法
def autoNorm(dataSet):
    # min(0)中的参数0 使得函数可以从从列中选取最小值，而不是选取当前行的最小值
    minVals = dataSet.min(0)
    # max(0)中的参数0 使得函数可以从从列中选取最大值，而不是选取当前行的最大值
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    # 创建数据长度大小的数组（shape 返回维数[a,b]）
    normDataSet = zeros(shape(dataSet))
    # shape[0] 只返回行数  shape[1] 只返回列数
    m = dataSet.shape[0]
    # 这里是对矩阵进行计算，而不是对单一数据进行计算，用tile()对minVals展开到m，（m,1） 沿着各个维度延伸的次数
    normDataSet = dataSet - tile(minVals, (m, 1))
    normDataSet = normDataSet / tile(ranges, (m, 1))
    return normDataSet, ranges, minVals
# 对文件数据进行k阶邻算法
def datingClassTest():
    # 测试数据百分比
    hoRatio = 0.10
    datingDataMat, datingLabels = file2Matrix(
        'G:\MLiA_SourceCode\machinelearninginaction\Ch02\datingTestSet2.txt')
    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 classifer came back with:%d，the real answer is:%d" % (classifierResult, datingLabels[i]))
        if (classifierResult != datingLabels[i]):
            errorcount += 1
    print("the total errror rate is:%f" % (errorcount / float(numTestVecs)))
def classifyPerson():
    resultList = ['not at all', 'in small doses', 'in large doses']
    percentTats = float(input("percentage of time spent playing miles earned per year?"))
    ffMiles = float(input("frequent flier miles earned per year?"))
    iceCream = float(input("liters of ice cream consumed per year?"))
    datingDataMat, datingLabels = file2Matrix(
        "G:\MLiA_SourceCode\machinelearninginaction\Ch02\datingTestSet2.txt")
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = array([ffMiles, percentTats, iceCream])
    classifierResult = classify0((inArr - minVals) / ranges, normMat, datingLabels, 3)
    print("You will probably like this person:", resultList[classifierResult - 1])
# 将二进制图片存到数组中
def img2vector(filename):
    returnVect = 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
# 手写数字系统的测试代码
def handwritingClassTest():
    hwLabels = []
    #
    trainingFileList = listdir('G:/MLiA_SourceCode/machinelearninginaction/Ch02/digits/trainingDigits')
    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(
            'G:/MLiA_SourceCode/machinelearninginaction/Ch02/digits/trainingDigits/%s' % fileNameStr)
    testFileList = listdir('G:/MLiA_SourceCode/machinelearninginaction/Ch02/digits/testDigits')
    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(
            'G:/MLiA_SourceCode/machinelearninginaction/Ch02/digits/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)))
if __name__ == '__main__':
    # 测试电影分级方法
    # groups, labels = createDataSet()
    # print(classify0([0.5, 1.5], groups, labels, 3))
    # 测试画特征图方法
    # datingDataMat, datingLabels = file2Matrix(
    #     'G:\MLiA_SourceCode\machinelearninginaction\Ch02\datingTestSet2.txt')
    # paintFigure(datingDataMat, datingLabels)
    # 测试autoNorm 归一化数值方法
    # print(datingDataMat[0:5])
    # print("\n\n")
    # datingDataMat, ranges, minVals = autoNorm(datingDataMat)
    # print(ranges)
    # print("\n\n")
    # print(minVals)
    # print("\n\n")
    # print(datingDataMat[0:5])
    # 测试约会网站评级
    # datingClassTest()
    # 输入数据测试约会网站
    # classifyPerson()
    # 测试手写系统
    handwritingClassTest()
    # 矩阵输出测试
    # a = arange(9)
    # b = a.reshape(3, 3)
    # print(b)
    # print("\n\n")
    # print(b[0:1, 0:2])