knn算法识补，即k-NearestNeighbor排截，后面的nn意思是最近鄰的意思章鲤，前面的k是前k個的意思税产，就是找到前k個離得最近的元素
離得最近這個詞具體實現(xiàn)有很多種抖仅，我使用的是歐式幾何中的距離公式
二維中兩點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算法是要計算距離的，也就是數(shù)字之間的運算砖第，而圖像是png撤卢，jpg這種格式，并不是數(shù)字也不能直接參與運算梧兼，所以我們需要進(jìn)行一下轉(zhuǎn)換
如圖所示一個數(shù)字8放吩，首先要確定的是這一步我做的是一個最簡單的轉(zhuǎn)換，因為我假定背景和圖之間是沒有雜物的羽杰，而且整個圖只有一個數(shù)字（0-9）如果遇到其他情況渡紫，比如背景色不純或者有其他干擾圖像需要重新設(shè)計轉(zhuǎn)換函數(shù)
接下來就是最簡單的轉(zhuǎn)換到推，將圖片白色部分（背景）變0，有圖像的部分變1惕澎。轉(zhuǎn)換后的大小要合適莉测，太小會影響識別準(zhǔn)確度，太大會增加計算量唧喉。所以我用的是書上的32*32捣卤，轉(zhuǎn)換后結(jié)果如圖所示
這樣一來，圖片就變成了能進(jìn)行計算的數(shù)字了八孝。
接下來我們需要創(chuàng)建一個庫董朝，這個庫里面存著0-9這些數(shù)字的各種類似上圖的實例。因為我們待識別的圖像要進(jìn)行對比干跛，選出前k個最近的子姜，比較的對象就是我們的庫。假定庫中有0-9十個數(shù)字楼入，每個數(shù)字各有100個這種由0和1表示的實例哥捕，那么我們就有了一共1000個實例。
最后一步就是進(jìn)行對比嘉熊，利用開頭說的歐式幾何距離計算公式遥赚，首先這個32*32的方陣要轉(zhuǎn)換成一個1*1024的1024維坐標(biāo)表示，然后拿這個待識別的圖像和庫中的1000個實例進(jìn)行距離計算记舆，選出前k個距離最近的。比如50個呼巴，這50個里面出現(xiàn)次數(shù)最多的數(shù)字除以50就是結(jié)果數(shù)字的概率泽腮。比如50個里面數(shù)字8出現(xiàn)40次，那么待識別數(shù)字是8的可能性就是40/50 = 80%
個人理解：
只能識別單個數(shù)字衣赶，背景不能有干擾诊赊。如果想多數(shù)字識別或者背景有干擾需要針對具體情況考慮具體的圖像轉(zhuǎn)01的方法。
數(shù)字識別非常依賴庫中的圖像府瞄，庫中的圖像的樣子嚴(yán)重影響圖像的識別（因為我們是和庫中的一一對比找出距離最近的前k個）碧磅，所以數(shù)字的粗細(xì)，高低遵馆，胖瘦等待都是決定性因素鲸郊，建庫時一定全面考慮數(shù)字的可能樣子
計算量比較大，待識別圖像要和庫中所有實例一一計算货邓，如果使用32*32秆撮，就已經(jīng)是1024維了。如果庫中有1000個换况，那就是1024維向量之間的1000次計算职辨，圖像更清晰盗蟆，庫更豐富只會使計算量更大
對于其他可以直接計算距離的數(shù)值型問題，可以用歐式距離舒裤，也可以用其他能代表距離的計算公式喳资，對于非數(shù)值型的問題需要進(jìn)行合適的轉(zhuǎn)換，轉(zhuǎn)換方式很重要腾供，我覺得首先信息不能丟失仆邓，其次要精確不能模糊，要實現(xiàn)圖片轉(zhuǎn)換前后是一對一的關(guān)系
參考資料：機器學(xué)習(xí)實戰(zhàn) [美] 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 待識別圖像轉(zhuǎn)換為01txt文件輸出宏赘，size圖像大小，默認(rèn)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文件轉(zhuǎn)換為向量
? ? 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('此數(shù)字是',number[0][0],'的可能性是','%.2f%%' % ((number[0][1]/len(result))*100))
def distinguish(filename1,filename2,filename3,size=(32,32)):
? ? # filename1 png，jpg等格式原始圖像路徑峻汉，filename2 原始圖像轉(zhuǎn)換成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)
