KNN

一、K-近邻算法（KNN）

  最简单最初级的分类器是将全部的训练数据所对应的类别都记录下来，当测试对象的属性和某个训练对象的属性完全匹配时，便可以对其进行分类。但是怎么可能所有测试对象都会找到与之完全匹配的训练对象呢，其次就是存在一个测试对象同时与多个训练对象匹配，导致一个训练对象被分到了多个类的问题，基于这些问题呢，就产生了KNN。

  KNN是通过测量不同特征值之间的距离进行分类。它的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别，其中K通常是不大于20的整数。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

  下面通过一个简单的例子说明一下：如下图，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。

由此也说明了KNN算法的结果很大程度取决于K的选择。

  在KNN中，通过计算对象间距离来作为各个对象之间的非相似性指标，避免了对象之间的匹配问题，在这里距离一般使用欧氏距离或曼哈顿距离：

同时，KNN通过依据k个对象中占优的类别进行决策，而不是单一的对象类别决策。这两点就是KNN算法的优势。

  接下来对KNN算法的思想总结一下：就是在训练集中数据和标签已知的情况下，输入测试数据，将测试数据的特征与训练集中对应的特征进行相互比较，找到训练集中与之最为相似的前K个数据，则该测试数据对应的类别就是K个数据中出现次数最多的那个分类，其算法的描述为：

1）计算测试数据与各个训练数据之间的距离；

2）按照距离的递增关系进行排序；

3）选取距离最小的K个点；

4）确定前K个点所在类别的出现频率；

5）返回前K个点中出现频率最高的类别作为测试数据的预测分类。

二、python实现 2.1、测试 2.1.1、创建训练集

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

2.1.2、构造分类器

1. 计算测试数据和每个训练数据的距离
2. 按照距离进行排序
3. 选择距离最小的K个点， 对各个类别进行统计
4. 按照类别的数据排序，选择数目最大的作为测试数据的分类。

def classify0(inx, data_set, labels, k):
    '''
    :param inx: 用于分类的输入向量 
    :param data_set:   训练样本
    :param labels:     标签向量
    :param k:          选择最近邻居的数目 
    :return: 
    '''

    # 计算欧式距离
    data_set_size = data_set.shape[0]
    diff_mat = np.tile(inx, (data_set_size, 1)) - data_set
    sq_diff_mat = diff_mat ** 2
    sq_distances = sq_diff_mat.sum(axis=1)
    distances = sq_distances ** 0.5

    sorted_distances = distances.argsort() # 根据元素的值从大到小进行排序， 返回下标

    class_count = {}
    for i in range(k): # 选择距离最小的k个点, 对各个类别的个数进行统计
        votei_label = labels[sorted_distances[i]]
        class_count[votei_label] = class_count.get(votei_label, 0) + 1

    # sorted_class_count = sorted(class_count.iteritems(), key=operator.itemgetter(1), reverse=True)
    # python3中已经没有iteritems这个属性，直接改为items即可
    # sorted 返回重新排序的列表。
    sorted_class_count = sorted(class_count.items(),            # 可迭代对象
                                key = operator.itemgetter(1),     # 用于进行比较的元素
                                reverse = True)                   # 排序规则，reverse = True 降序 ， reverse = False 升序（默认）。

    return sorted_class_count[0][0]

2.2、实战1： 使用knn改进约会网站的配对效果 2.2.1、加载数据

def file2matrix(filename):
    fr = open(filename)
    numberOfLines = len(fr.readlines())  # get the number of lines in the file
    returnmat = np.zeros((numberOfLines, 3))  # prepare matrix to return
    classLabelVector = []  # prepare labels return
    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

2.2.2、分析数据 2.2.2.1、绘制玩游戏与消费冰淇淋的散点图

    datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')

    import matplotlib.pyplot as plt
    plt.rcParams['font.sans-serif'] = ['SimHei']  ###显示中文
    plt.rcParams['axes.unicode_minus'] = False      ## 防止坐标轴上的"-"号变为方块
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.scatter(datingDataMat[:,1], datingDataMat[:,2],
               s = 15.0 * np.array(datingLabels),
               c = 15.0 * np.array(datingLabels)) # 通过类别标签区分样本的分类
    plt.xlabel('玩游戏时间占比')
    plt.ylabel('每周冰淇淋公升数')
    plt.show()

2.2.2.2、飞行里程与冰淇淋的散点图，该图的分类效果更好

    datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')

    import matplotlib.pyplot as plt
    plt.rcParams['font.sans-serif'] = ['SimHei']  ###显示中文
    plt.rcParams['axes.unicode_minus'] = False      ## 防止坐标轴上的"-"号变为方块
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.scatter(datingDataMat[:,0], datingDataMat[:,1],
               s = 15.0 * np.array(datingLabels),
               c = 15.0 * np.array(datingLabels)) # 通过类别标签区分样本的分类
    plt.xlabel('每年飞行里程数')
    plt.ylabel('每周冰淇淋公升数')
    plt.show()

2.2.3、准备数据： 归一化数值

在计算样本3和样本4的距离： 发现飞行里程对距离影响非常大， 远远大于其他两个属性的影响， 作为三个等权重的特征之一，飞行里程不应该如此严重的影响到计算结果。

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

# 归一化
# newValue = (oldValue - min) / (max - min)
def autoNorm(data_set):
    # 参数0 使得函数可以从列中获取最小值， 而不是当前行的最小值
    minVals = data_set.min(0)
    maxVals = data_set.max(0)
    ranges = maxVals - minVals  # (oldValue - min)
    normdataset = np.zeros(np.shape(data_set))
    m = data_set.shape[0]
    # 使用numpy.tile 将minVals复制成输入矩阵同样大小的矩阵
    normdataset = data_set - np.tile(minVals, (m, 1))    # (oldValue - min)
    # 注意这是具体特征值相除， 而对于某些数值处理软件包， / 可能意味矩阵相除， 但在numpy中， 矩阵除法需要使用linalg.solve(matA, matB)
    normdataset = normdataset / np.tile(ranges, (m, 1))  # newValue = (oldValue - min) / (max - min)
    return normdataset, ranges, minVals

2.2.3、分类器对约会网站的测试

def datingclassTest():
    hoRatio = 0.50  # hold out 10%

    datingdatamat, datingLabels = file2matrix('datingTestset2.txt')  # 加载数据
    normmat, ranges, minVals = autoNorm(datingdatamat)               # 归一化

    m = normmat.shape[0]
    numTestVecs = int(m * hoRatio)     # 测试的数量

    errorcount = 0.0
    # 0 ~ numTestVecs -1 为测试数据
    # numTestVecs ~ m-1  为训练数据
    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)

2.3、实战2： 手写识别系统