KNN分类算法及应用

1、KNN分类算法原理

1.1 概述

K最近邻（k-Nearest Neighbor，KNN）分类算法是最简单的机器学习算法。

KNN算法的指导思想是“近朱者赤，近墨者黑”，由你的邻居来推断出你的类别。

本质上，KNN算法就是用距离来衡量样本之间的相似度

1.2 算法图示

从训练集中找到和新数据最接近的k条记录，然后根据多数类来决定新数据类别。

算法涉及3个主要因素：

1. 训练数据集

2. 距离或相似度的计算衡量

3. k的大小

算法描述

1. 已知两类“先验”数据，分别是蓝方块和红三角，他们分布在一个二维空间中

2. 有一个未知类别的数据（绿点），需要判断它是属于“蓝方块”还是“红三角”类

3. 考察离绿点最近的3个（或k个）数据点的类别，占多数的类别即为绿点判定类别

1.3 算法要点

1.3.1、计算步骤

计算步骤如下：

1）算距离：给定测试对象，计算它与训练集中的每个对象的距离

2）找邻居：圈定距离最近的k个训练对象，作为测试对象的近邻

3）做分类：根据这k个近邻归属的主要类别，来对测试对象分类

1.3.2、相似度的衡量

距离越近应该意味着这两个点属于一个分类的可能性越大。但距离不能代表一切，有些数据的相似度衡量并不适合用距离。

相似度衡量方法：包括欧式距离、夹角余弦等。

1.3.3、类别的判定

简单投票法：少数服从多数，近邻中哪个类别的点最多就分为该类。

加权投票法：根据距离的远近，对近邻的投票进行加权，距离越近则权重越大（权重为距离平方的倒数）

1.4 算法不足之处

1.4.1 样本不平衡容易导致结果错误

如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。

改善方法：对此可以采用权值的方法（和该样本距离小的邻居权值大）来改进。

1.4.2 计算量较大

因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。

改善方法：事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。

该方法比较适用于样本容量比较大的类域的分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

2、KNN分类算法Python实战

2.1 kNN简单数据分类实践

2.1.1 需求

有以下先验数据，使用knn算法对未知类别数据分类

属性1	属性2	类别
1.0	0.9	A
1.0	1.0	A
0.1	0.2	B
0.0	0.1	B

未知类别数据

属性1	属性2	类别
1.2	1.0	?
0.1	0.3	?

2.1.2 Python实现

首先，我们新建一个kNN.py脚本文件，文件里面包含两个函数，一个用来生成小数据集，一个实现kNN分类算法。代码如下：

from numpy import *
import os
def createDataSet():
    dataSet = array([[1.0,0.9],[1.0, 1.0],[0.1, 0.2],[0.0,0.1]])
    label = array(['A','A','B','B'])
    return dataSet,label
def KNN(newInput,dataSet,label,k):
    # ##1. 计算输入的节点和所有节点的距离
    distinct = ((dataSet - newInput) ** 2).sum(1) ** 0.5
    # ##2. 排序
    # ##对应的最小值的下标 （按照大小对下标进行排序）
    sortArg = argsort(distinct)
    # ##3. 选取k个值来计算邻近的点
    res = {}
    for i in range(k):
        value = label[sortArg[i]]
        res[value] = res.get(value,0)+1
    for k,v in res.items():
        if(v == max(res.values())):
            return k

train_x,train_y,test_x,test_y = loadDataSet()
print(KNN(test_x[86],train_x,train_y,10))

2.2 kNN实现手写数字识别

2.2.1 需求

利用一个手写数字“先验数据”集，使用knn算法来实现对手写数字的自动识别；

先验数据（训练数据）集：

数据维度比较大，样本数比较多。

数据集包括数字0-9的手写体。

每个数字大约有200个样本。

每个样本保持在一个txt文件中。

手写体图像本身的大小是32x32的二值图，转换到txt文件保存后，内容也是32x32个数字，0或者1，如下：

数据集压缩包解压后有两个目录：

目录trainingDigits存放的是大约2000个训练数据

目录testDigits存放大约900个测试数据。

2.2.2 python实现

四个函数：

1. 一个用来生成将每个样本的txt文件转换为对应的一个向量，

2. 一个用来加载整个数据集，

3. 一个实现kNN分类算法。

4. 最后就是实现加载、测试的函数.

from numpy import *
import os
def loadDataSet():
    filesList = os.listdir("trainingDigits")
    length = len(filesList)
    train_x = zeros((length,1024))
    train_y = []
    for i in range(length):
        filename = filesList[i]
        train_x[i,:] = img2arr("trainingDigits/%s"%filename)
        label = int(filename.split("_")[0])
        train_y.append(label)
    testFilesList = os.listdir("testDigits")
    length = len(testFilesList)
    test_x = zeros((length,1024))
    test_y = []
    for i in range(length):
        filename = testFilesList[i]
        test_x[i,:] = img2arr("testDigits/%s"%filename)
        label = filename.split("_")[0]
        test_y.append(label)
    return train_x,train_y,test_x,test_y

def img2arr(filename):
    read = open(filename)
    rows = 32
    cols = 32
    lineArr = zeros((1,rows*cols))
    for row in range(rows):
        line = read.readline()
        for col in range(cols):
            lineArr[0,32*row+col] = line[col]
    return lineArr

def KNN(newInput,dataSet,label,k):
    # ##1. 计算输入的节点和所有节点的距离
    distinct = ((dataSet - newInput) ** 2).sum(1) ** 0.5
    # ##2. 排序
    # ##对应的最小值的下标 （按照大小对下标进行排序）
    sortArg = argsort(distinct)
    # ##3. 选取k个值来计算邻近的点
    res = {}
    for i in range(k):
        value = label[sortArg[i]]
        res[value] = res.get(value,0)+1
    for k,v in res.items():
        if(v == max(res.values())):
            return k
        
train_x,train_y,test_x,test_y = loadDataSet()
print(KNN(test_x[86],train_x,train_y,10))

3、KNN算法补充

3.1、k值设定为多大？

k太小，分类结果易受噪声点影响；k太大，近邻中又可能包含太多的其它类别的点。

（对距离加权，可以降低k值设定的影响）

k值通常是采用交叉检验来确定（以k=1为基准）

经验规则：k一般低于训练样本数的平方根

3.2、类别如何判定最合适？

投票法没有考虑近邻的距离的远近，距离更近的近邻也许更应该决定最终的分类，所以加权投票法更恰当一些。而具体如何加权，需要根据具体的业务和数据特性来探索

3.3、如何选择合适的距离衡量？

高维度对距离衡量的影响：众所周知当变量数越多，欧式距离的区分能力就越差。

变量值域对距离的影响：值域越大的变量常常会在距离计算中占据主导作用，因此应先对变量进行标准化。

3.4、训练样本是否要一视同仁？

在训练集中，有些样本可能是更值得依赖的。

也可以说是样本数据质量的问题

可以给不同的样本施加不同的权重，加强依赖样本的权重，降低不可信赖样本的影响。

3.5、性能问题？

kNN是一种懒惰算法，平时不好好学习，考试（对测试样本分类）时才临阵磨枪（临时去找k个近邻）。

懒惰的后果：构造模型很简单，但在对测试样本分类地的系统开销大，因为要扫描全部训练样本并计算距离。

已经有一些方法提高计算的效率，例如压缩训练样本量等。

还有诸如：

浓缩技术(condensing)

编辑技术(editing)