k-近邻算法（kNN）：采用测量不同特征值之间的距离方法进行分类

• 优点：

  • 简单好用，容易理解，精度高，理论成熟，既可以用来做分类也可以用来做回归；
  • 可用于数值型数据和离散型数据；
  • 训练时间复杂度为O(n)；无数据输入假定；
  • 对异常值不敏感。

• 缺点：

  • 计算复杂性高；空间复杂性高；
  • 样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；
  • 一般数值很大的时候不用这个，计算量太大。但是单个样本又不能太少，否则容易发生误分。
  • 最大的缺点是无法给出数据的内在含义。

• 使用数据范围：数值型和标称型

• 工作原理：

  • 使用无标签数据的每个特征与样本集中数据对应的特征比较，
  • 算法提取样本集中特征最相似数据（最近邻）的分类标签，
  • 只选择样本数据集中前k个最相似的数据，
  • 选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

• 一般流程

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

• 欧式距离
  
  欧式距离
  曼哈顿距离
  切比雪夫距离
  马氏距离
  巴氏距离
  汉明距离
  皮尔逊系数
  信息熵

• 手写重要代码

#导入库
import numpy as np
import operator
#创建数据集合
def createDataSet():
    group = np.array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels
#欧式距离的k-近邻算法
def classify0(inX, dataSet, labels, k):
    """
    欧式距离的k-近邻算法
    params inX：单一输入值，list or np.array
    params dataSet：样本集，np.array
    params labels：样本集标签，list or np.array
    params k：int
    returns sortedClassCount[0][0]：分类的类别
    """
    # 计算输入值与样本集的距离——基于欧式距离
    #numpy函数shape[0]返回dataSet的行数
    dataSetSize = dataSet.shape[0]
    #在列向量方向上重复inX共1次(横向)，行向量方向上重复inX共dataSetSize次(纵向)
    diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
    #二维特征相减后平方
    sqDiffMat = diffMat**2
    #sum()所有元素相加，sum(0)列相加，sum(1)行相加
    sqDistances = sqDiffMat.sum(axis=1)
    #开方，计算出距离
    distances = sqDistances**0.5

    #返回distances中元素从小到大排序后的索引值
    sortedDistIndicies = distances.argsort()
    #定一个记录类别次数的字典
    classCount = {}
    for i in range(k):
        #取出前k个元素的类别
        voteIlabel = labels[sortedDistIndicies[i]]
        #dict.get(key,default=None),字典的get()方法,返回指定键的值,如果值不在字典中返回默认值。
        #计算类别次数
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    #key=operator.itemgetter(1)根据字典的值进行排序
    #key=operator.itemgetter(0)根据字典的键进行排序
    #reverse降序排序字典
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    #返回次数最多的类别,即所要分类的类别
    return sortedClassCount[0][0]
#输入归一化
def autoNorm(dataSet):
    """
    newValue=(oldValue-min)/(max-min) 将认一取值范围的特征值转化为[0,1]
    params dataSet：归一化数集
    returns normDataSet：归一化后的特征矩阵
    returns ranges：数据范围
    returns minVals：数据最小值
    """
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = np.zeros(np.shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - np.tile(minVals, (m, 1))
    normDataSet = normDataSet/np.tile(ranges, (m, 1))   #element wise divide
    return normDataSet, ranges, minVals
#算法测试
def handwritingclasstest(data_test,data_test_label,data_train,data_train_label,k):
    """
    算法测试函数
    params data_test：测试数集
    params data_test_label：测试集的标签
    params data_train：训练数集
    params data_train_label：训练集的标签
    params k：k近邻算法的k
    """
    errorCount = 0.0
    for i in range(data_test.shape[0]):
        classifierResult = classify0(data_test[i, :], data_train, data_train_label, k)
        print(i, "the classifier came back with: %d, the real answer is: %d" % (classifierResult, data_test_label[i]))
        if (classifierResult != data_test_label[i]): errorCount += 1.0
    print("错误率:%f%%" %(errorCount/float(numTestVecs)*100))
    print(errorCount)

• sklearn实现算法
  • sklearn.neighbors模块实现kNN
    • sklearn.neighbors.KNeighborsClassifier

      class sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, weights=’uniform’, algorithm=’auto’, leaf_size=30, p=2, metric=’minkowski’, metric_params=None, n_jobs=None, **kwargs)            
      

      • 参数
        • params n_neighbors - 默认为5，就是k-NN的k的值，选取最近的k个点。
        • params weights - 默认是uniform，参数可以是uniform、distance，也可以是用户自己定义的函数。uniform是均等的权重，就说所有的邻近点的权重都是相等的。distance是不均等的权重，距离近的点比距离远的点的影响大。用户自定义的函数，接收距离的数组，返回一组维数相同的权重。
        • params algorithm - 快速k近邻搜索算法，默认参数为auto，可以理解为算法自己决定合适的搜索算法。
          • ball_tree将使用sklearn.neighbors.BallTree是为了克服kd树高纬失效而发明的，其构造过程是以质心C和半径r分割样本空间，每个节点是一个超球体;
          • kd_tree将使用sklearn.neighbors.KDTree构造kd树存储数据以便对其进行快速检索的树形数据结构，kd树也就是数据结构中的二叉树。以中值切分构造的树，每个结点是一个超矩形，在维数小于20时效率高;
          • brute将使用蛮力搜索，也就是线性扫描，当训练集很大时，计算非常耗时
        • params leaf_size - 默认是30，这个是构造的kd树和ball树的大小。这个值的设置会影响树构建的速度和搜索速度，同样也影响着存储树所需的内存大小。需要根据问题的性质选择最优的大小。
        • params metric - 用于距离度量，默认度量是minkowski，也就是p=2的欧氏距离(欧几里德度量)。
        • params p - p=1曼哈顿距离；p=2欧式距离
        • params metric_params - 距离公式的其他关键参数，这个可以不管，使用默认的None即可
        • params n_jobs - 并行处理设置。默认为1，临近点搜索并行工作数。如果为-1，那么CPU的所有cores都用于并行工作。
      • 方法
        • methods fit(X, y) - 使用X作为训练数据并将y作为目标值来拟合模型 参数
          • params X- {阵列式，稀疏矩阵，BallTree，KDTree} - 训练数据。 如果数组或矩阵，如果metric ='precomputed'，则形成[n_samples，n_features]或[n_samples，n_samples]。
          • params y - {数组式，稀疏矩阵} - shape的目标值= [n_samples]或[n_samples，n_outputs]
        • methods predict(X) - 预测提供的数据的类别标签
          • params X - 测试样本；类似数组，形状（n_query，n_features）或（n_query，n_indexed）如果metric =='precomputed'
          • ruturns y - 每个数据样本的类标签；形状数组[n_samples]或[n_samples，n_outputs]
        • methods get_params(deep=True) - 获取此估算工具的参数
          • params deep - 如果为True，将返回此估计器的参数并包含作为估算器的子对象；布尔值，可选
          • returns params - 映射到其值的参数名称。将字符串映射到任何字符串
        • methods kneighbors(X=None, n_neighbors=None, return_distance=True) - 找到一个点的K邻居。返回每个点的邻居的索引和距离。
          • params X:类似数组，形状（n_query，n_features）或（n_query，n_indexed）如果metric ='''precomputed' - 查询点或点。如果未提供，则返回每个索引点的邻居。在这种情况下，查询点不被视为自己的邻居。
          • params n_neighbors ： int - 要获取的邻居数（默认值是传递给构造函数的值）。
          • params return_distance - 布尔值，可选。默认为True。 如果为False，则不会返回距离
          • returns dist：数组 - 表示点数长度的数组，仅在return_distance = True时出现
          • returns ind：数组 - 矩阵中最近点的指数。
        • methods kneighbors_graph(X=None, n_neighbors=None, mode=’connectivity’) - 计算X中点的k-邻居的（加权）图
        • methods predict_proba(X) - 测试数据X的返回概率估计。
        • methods score(X, y, sample_weight=None) - 返回给定测试数据和标签的平均精度。
        • methods set_params(**params) - 设置此估算器的参数。

from sklearn.neighbors import KNeighborsClassifier as kNN
def kNNClassTest(data_test,data_test_label,data_train,data_train_label,k):
    """
    params data_test：测试数集
    params data_test_label：测试集的标签
    params data_train：训练数集
    params data_train_label：训练集的标签
    params k：k近邻算法的k
    """
    #构建kNN分类器
    neigh = kNN(n_neighbors = k, algorithm = 'auto')
    #拟合模型, data_train为训练数集,data_train_label为训练集的标签
    neigh.fit(data_train, data_train_label)
    #错误检测计数
    errorCount = 0.0
    #测试数据的数量
    mTest = data_test.shape[0]
    #从文件中解析出测试集的类别并进行分类测试
    #获得预测结果
    classifierResult = neigh.predict(data_test)
    for i in range(mTest):
        print("分类返回结果为%d\t真实结果为%d" % (classifierResult[i], data_test_label[i]))
        if(classifierResult[i] != data_test_label[i]):
            errorCount += 1.0
    print("总共错了%d个数据\n错误率为%f%%" % (errorCount, errorCount/mTest * 100))

• 案例实现
• 案例1：约会网站配对

# 导入数据
def file2matrix(filename):
    love_dictionary = {'largeDoses':3, 'smallDoses':2, 'didntLike':1}
    fr = open(filename)
    arrayOLines = fr.readlines()
    numberOfLines = len(arrayOLines)            #get the number of lines in the file
    returnMat = np.zeros((numberOfLines, 3))        #prepare matrix to return
    classLabelVector = []                       #prepare labels return
    index = 0
    for line in arrayOLines:
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index, :] = listFromLine[0:3]
        if(listFromLine[-1].isdigit()):
            classLabelVector.append(int(listFromLine[-1]))
        else:
            classLabelVector.append(love_dictionary.get(listFromLine[-1]))
        index += 1
    return returnMat, classLabelVector
#测试函数
def datingClassTest():
    path = r'E:\C_all\Desktop\ML仓库\机器学习实战\machinelearninginaction3x-master\Ch02\datingTestSet2.txt'
    hoRatio = 0.50      #hold out 10%
    datingDataMat, datingLabels = file2matrix(path)       #load data setfrom file
    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 classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i]))
        if (classifierResult != datingLabels[i]): errorCount += 1.0
    print("the total error rate is: %f" % (errorCount / float(numTestVecs)))
    print(errorCount)
datingClassTest()

the total error rate is: 0.068000
34.0

#应用
def classifyPerson():
    path = r'E:\C_all\Desktop\ML仓库\机器学习实战\machinelearninginaction3x-master\Ch02\datingTestSet2.txt'
    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(path)
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = np.array([
        ffMiles,
        percentTats,
        iceCream,
    ])
    classifierResult = classify0((inArr - minVals) / ranges, normMat,
                                 datingLabels, 3)
    print("You will probably like this person: %s" %
          resultList[classifierResult - 1])
classifyPerson()

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

• 案例2：手写数字分类

#数据导入
from tensorflow.examples.tutorials.mnist import input_data
# 利用tensorflow代码下载MNIST
mnist = input_data.read_data_sets("/MNIST_data/", one_hot=False)
# 代码中的one_hot=True，表示将样本标签转化为one_hot编码


#测试函数
def handwritingclasstest():
    errorCount = 0.0
    for i in range(mnist.test.images.shape[0]):
        classifierResult = classify0(mnist.test.images[i, :], mnist.train.images, mnist.train.labels, 10)
        print(i, "the classifier came back with: %d, the real answer is: %d" % (classifierResult, mnist.test.labels[i]))
        if (classifierResult != mnist.test.labels[i]): errorCount += 1.0
    print("the total error rate is: %f" % (errorCount / float(mnist.test.images.shape[0])))
    print(errorCount)
handwritingclasstest()

the total error rate is: 0.033200
332.0