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ù)字也不能直接參與運算，所以我們需要進行一下轉換
如圖所示一個數(shù)字8，首先要確定的是這一步我做的是一個最簡單的轉換，因為我假定背景和圖之間是沒有雜物的，而且整個圖只有一個數(shù)字（0-9）如果遇到其他情況，比如背景色不純或者有其他干擾圖像需要重新設計轉換函數(shù)
接下來就是最簡單的轉換，將圖片白色部分（背景）變0，有圖像的部分變1。轉換后的大小要合適，太小會影響識別準確度，太大會增加計算量。所以我用的是書上的32*32，轉換后結果如圖所示
這樣一來，圖片就變成了能進行計算的數(shù)字了。
接下來我們需要創(chuàng)建一個庫，這個庫里面存著0-9這些數(shù)字的各種類似上圖的實例。因為我們待識別的圖像要進行對比，選出前k個最近的，比較的對象就是我們的庫。假定庫中有0-9十個數(shù)字，每個數(shù)字各有100個這種由0和1表示的實例，那么我們就有了一共1000個實例。
最后一步就是進行對比，利用開頭說的歐式幾何距離計算公式，首先這個32*32的方陣要轉換成一個1*1024的1024維坐標表示，然后拿這個待識別的圖像和庫中的1000個實例進行距離計算，選出前k個距離最近的。比如50個，這50個里面出現(xiàn)次數(shù)最多的數(shù)字除以50就是結果數(shù)字的概率。比如50個里面數(shù)字8出現(xiàn)40次，那么待識別數(shù)字是8的可能性就是40/50 = 80%
個人理解：
只能識別單個數(shù)字，背景不能有干擾。如果想多數(shù)字識別或者背景有干擾需要針對具體情況考慮具體的圖像轉01的方法。
數(shù)字識別非常依賴庫中的圖像，庫中的圖像的樣子嚴重影響圖像的識別（因為我們是和庫中的一一對比找出距離最近的前k個），所以數(shù)字的粗細，高低，胖瘦等待都是決定性因素，建庫時一定全面考慮數(shù)字的可能樣子
計算量比較大，待識別圖像要和庫中所有實例一一計算，如果使用32*32，就已經(jīng)是1024維了。如果庫中有1000個，那就是1024維向量之間的1000次計算，圖像更清晰，庫更豐富只會使計算量更大
對于其他可以直接計算距離的數(shù)值型問題，可以用歐式距離，也可以用其他能代表距離的計算公式，對于非數(shù)值型的問題需要進行合適的轉換，轉換方式很重要，我覺得首先信息不能丟失，其次要精確不能模糊，要實現(xiàn)圖片轉換前后是一對一的關系
參考資料：機器學習實戰(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 待識別圖像轉換為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('此數(shù)字是',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)
