Knn算法原理

如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 看下面这幅图：

创新互联服务项目包括荣县网站建设、荣县网站制作、荣县网页制作以及荣县网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，荣县网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到荣县省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！

KNN的算法过程是是这样的： 从上图中我们可以看到，图中的数据集是良好的数据，即都打好了label，一类是蓝色的正方形，一类是红色的三角形，那个绿色的圆形是我们待分类的数据。 如果K=3，那么离绿色点最近的有2个红色三角形和1个蓝色的正方形，这3个点投票，于是绿色的这个待分类点属于红色的三角形 如果K=5，那么离绿色点最近的有2个红色三角形和3个蓝色的正方形，这5个点投票，于是绿色的这个待分类点属于蓝色的正方形 我们可以看到，KNN本质是基于一种数据统计的方法！其实很多机器学习算法也是基于数据统计的。 KNN是一种memory-based learning，也叫instance-based learning，属于lazy learning。即它没有明显的前期训练过程，而是程序开始运行时，把数据集加载到内存后，不需要进行训练，就可以开始分类了。 具体是每次来一个未知的样本点，就在附近找K个最近的点进行投票。

KNN算法的实现就是取决于，未知样本和训练样本的“距离”。我们计算“距离”可以利用欧式距离算法：

求出K个最相近的元组后，用这些元组对应的数值的平均值作为最终结果。

可以从K=1开始，逐步增加，用检验数据来分析正确率，从而选择最优K。这个结果要均衡考虑正确率与计算量，比如K=3时，正确率为90%，而K=10时，正确率为91%，则需要考虑计算量换来的1%提升是否合算了。

（1）如果可能的话先对样本数据进行排序，从而知道只需要与哪些数据进行比较。但对于高维数据，这几乎是不可行的。

（2）将样本数据划分为多个子集合，待分类数据只需要与其中的一个或者多个子集合进行比较。比如属性是经纬度，距离是2个经纬度点之间的距离，则可以将样本根据经纬度的整数部分将各个样本分到不同的子集合去，待分类元组只需要跟与自己整数部分相同的子集合进行比较即可，当子集合内的样本数据不足K时，再和邻近的集合进行比较。

（1）理论成熟，思想简单，既可以用来做分类又可以做回归

（2）可以用于非线性分类

（3）训练时间复杂度比支持向量机之类的算法低

（4）和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感

（5）由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属的类别，因此对于类域的交叉或重叠较多的待分类样本集来说，KNN方法较其他方法更为适合

（6）该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量比较小的类域采用这种算法比较容易产生误分类情况

（1）计算量大，尤其是特征数非常多的时候

（2）样本不平衡的时候，对稀有类别的预测准确率低

（3）KD树，球树之类的模型建立需要大量的内存

（4）是慵懒散学习方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢

（5）相比决策树模型，KNN模型的可解释性不强

注：图片来源于：

怎样在spark里跑java版的knn算法

将KNN算法调用Spark的api进行重写。然后就可以在sparkshell里运行了

简单数字识别(knn算法)

knn算法，即k-NearestNeighbor，后面的nn意思是最近邻的意思，前面的k是前k个的意思，就是找到前k个离得最近的元素

离得最近这个词具体实现有很多种，我使用的是欧式几何中的距离公式

二维中两点x(x1,y1),y(x2,y2)间距离公式为sqrt( (x1-x2)^2+(y1-y2)^2 )

推广到n维就是

x(x1,x2, … ,xn),y(y1,y2, … ,yn)

sqrt [ ∑( x[i] - y[i] )^2 ] (i=1,2, … ,n)

knn算法是要计算距离的，也就是数字之间的运算，而图像是png，jpg这种格式，并不是数字也不能直接参与运算，所以我们需要进行一下转换

如图所示一个数字8，首先要确定的是这一步我做的是一个最简单的转换，因为我假定背景和图之间是没有杂物的，而且整个图只有一个数字（0-9）如果遇到其他情况，比如背景色不纯或者有其他干扰图像需要重新设计转换函数

接下来就是最简单的转换，将图片白色部分（背景）变0，有图像的部分变1。转换后的大小要合适，太小会影响识别准确度，太大会增加计算量。所以我用的是书上的32*32，转换后结果如图所示

这样一来，图片就变成了能进行计算的数字了。

接下来我们需要创建一个库，这个库里面存着0-9这些数字的各种类似上图的实例。因为我们待识别的图像要进行对比，选出前k个最近的，比较的对象就是我们的库。假定库中有0-9十个数字，每个数字各有100个这种由0和1表示的实例，那么我们就有了一共1000个实例。

最后一步就是进行对比，利用开头说的欧式几何距离计算公式，首先这个32*32的方阵要转换成一个1*1024的1024维坐标表示，然后拿这个待识别的图像和库中的1000个实例进行距离计算，选出前k个距离最近的。比如50个，这50个里面出现次数最多的数字除以50就是结果数字的概率。比如50个里面数字8出现40次，那么待识别数字是8的可能性就是40/50 = 80%

个人理解：

只能识别单个数字，背景不能有干扰。如果想多数字识别或者背景有干扰需要针对具体情况考虑具体的图像转01的方法。

数字识别非常依赖库中的图像，库中的图像的样子严重影响图像的识别（因为我们是和库中的一一对比找出距离最近的前k个），所以数字的粗细，高低，胖瘦等待都是决定性因素，建库时一定全面考虑数字的可能样子

计算量比较大，待识别图像要和库中所有实例一一计算，如果使用32*32，就已经是1024维了。如果库中有1000个，那就是1024维向量之间的1000次计算，图像更清晰，库更丰富只会使计算量更大

对于其他可以直接计算距离的数值型问题，可以用欧式距离，也可以用其他能代表距离的计算公式，对于非数值型的问题需要进行合适的转换，转换方式很重要，我觉得首先信息不能丢失，其次要精确不能模糊，要实现图片转换前后是一对一的关系

参考资料：机器学习实战 [美] Peter Harrington 人民邮电出版社

python源码

import numpy

import os

from PIL import Image

import heapq

from collections import Counter

def pictureconvert(filename1,filename2,size=(32,32)):

#filename1待识别图像，filename2 待识别图像转换为01txt文件输出，size图像大小，默认32*32

image_file = Image.open(filename1)

image_file = image_file.resize(size)

width,height = image_file.size

f1 = open(filename1,'r')

f2 = open(filename2,'w')

for i in range(height):

    for j in range(width):

        pixel = image_file.getpixel((j,i))

        pixel = pixel[0] + pixel[1] + pixel[2]

        if(pixel == 0):

            pixel = 0

        elif(pixel != 765 and pixel != 0):

            pixel = 1

        # 0代表黑色（无图像），255代表白色（有图像）

        # 0/255 = 0,255/255 = 1

        f2.write(str(pixel))

        if(j == width-1):

            f2.write('\n')

f1.close()

f2.close()

def imgvector(filename):

#filename将待识别图像的01txt文件转换为向量

vector = numpy.zeros((1,1024),numpy.int)

with open(filename) as f:

    for i in range(0,32):

        linestr = f.readline()

        for j in range(0,32):

            vector[0,32*i+j] = int(linestr[j])

return  vector

def compare(filename1,filename2):

#compare直接读取资源库识别

#filename1资源库目录，filename2 待识别图像01txt文档路径

trainingfilelist = os.listdir(filename1)

m = len(trainingfilelist)

labelvector = []

trainingmatrix = numpy.zeros((m, 1024), numpy.int8)

for i in range(0,m):

    filenamestr = trainingfilelist[i]

    filestr = filenamestr.split('.')[0]

    classnumber = int(filestr.split('_')[0])

    labelvector.append(classnumber)

    trainingmatrix[i,:] = imgvector(filename1 + '/' + filenamestr)

textvector = imgvector(filename2)

resultdistance = numpy.zeros((1,m))

result = []

for i in range(0,m):

    resultdistance[0,i] = numpy.vdot(textvector[0],trainingmatrix[i])

resultindices = heapq.nlargest(50,range(0,len(resultdistance[0])),resultdistance[0].take)

for i in resultindices:

    result.append(labelvector[i])

number = Counter(result).most_common(1)

print('此数字是',number[0][0],'的可能性是','%.2f%%' % ((number[0][1]/len(result))*100))

def distinguish(filename1,filename2,filename3,size=(32,32)):

# filename1 png，jpg等格式原始图像路径，filename2 原始图像转换成01txt文件路径，filename3 资源库路径

pictureconvert(filename1,filename2,size)

compare(filename3,filename2)

url1 = "/Users/wang/Desktop/number.png"

url2 = "/Users/wang/Desktop/number.txt"

traininglibrary = "/Users/wang/Documents/trainingDigits"

distinguish(url1,url2,traininglibrary)

分享文章：knn算法java源代码 knn算法c++实现
链接URL：http://azwzsj.com/article/ddocspo.html