#!/usr/bin/python 
#coding:utf-8 
 
import numpy as np 
import operator 
import matplotlib 
import matplotlib.pyplot as plt 
import os 
 
''''' 
KNN算法 
1. 計(jì)算已知類別數(shù)據(jù)集中的每個(gè)點(diǎn)依次執(zhí)行與當(dāng)前點(diǎn)的距離。 
2. 按照距離遞增排序。 
3. 選取與當(dāng)前點(diǎn)距離最小的k個(gè)點(diǎn) 
4. 確定前k個(gè)點(diǎn)所在類別的出現(xiàn)頻率 
5. 返回前k個(gè)點(diǎn)出現(xiàn)頻率最高的類別作為當(dāng)前點(diǎn)的預(yù)測分類 
''' 
 
''''' 
inX為要分類的向量 
dataSet為訓(xùn)練樣本 
labels為標(biāo)簽向量 
k為最近鄰的個(gè)數(shù) 
''' 
def classify0(inX , dataSet , labels , k): 
 dataSetSize = dataSet.shape[0]#dataSetSize為訓(xùn)練樣本的個(gè)數(shù) 
 diffMat = np.tile(inX , (dataSetSize , 1)) - dataSet#將inX擴(kuò)展為dataSetSize行，1列 
 sqDiffMat = diffMat**2 
 sqDistances = sqDiffMat.sum(axis=1) 
 distances = sqDistances**0.5 
 sortedDistIndicies = distances.argsort()#返回的是元素從小到大排序后，該元素原來的索引值的序列 
 classCount = {} 
 for i in range(k): 
  voteIlabel = labels[sortedDistIndicies[i]]#voteIlabel為類別 
  classCount[voteIlabel] = classCount.get(voteIlabel,0)+1#如果之前這個(gè)voteIlabel是有的，那么就返回字典里這個(gè)voteIlabel里的值，如果沒有就返回0 
 sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)#key=operator.itemgetter(1)的意思是按照字典里的第一個(gè)排序，{A:1,B:2},要按照第1個(gè)（AB是第0個(gè)），即‘1'‘2'排序。reverse=True是降序排序 
 print sortedClassCount 
 return sortedClassCount[0][0] 
 
 
''''' 
將圖像轉(zhuǎn)換為1*1024的向量 
''' 
def img2vector(filename): 
 returnVect = np.zeros((1,1024)) 
 fr = open(filename) 
 for i in range(32): 
  line = fr.readline() 
  for j in range(32): 
   returnVect[0,i*32+j] = int(line[j] ) 
 return returnVect 
 
''''' 
手寫體識別系統(tǒng)測試 
''' 
def handwritingClassTest(trainFilePath,testFilePath): 
 hwLabels = [] 
 trainingFileList = os.listdir(trainFilePath) 
 m=len(trainingFileList) 
 trainSet = np.zeros((m,1024)) 
 for i in range(m): 
  filename = trainingFileList[i] 
  classNum = filename.split('.')[0] 
  classNum = int(classNum.split('_')[0]) 
  hwLabels.append(classNum) 
  trainSet[i] = img2vector( os.path.join(trainFilePath,filename) ) 
 testFileList = os.listdir(testFilePath) 
 errorCount = 0 
 mTest = len(testFileList) 
 for i in range(mTest): 
  filename = trainingFileList[i] 
  classNum = filename.split('.')[0] 
  classNum = int(classNum.split('_')[0]) 
  vectorUnderTest = img2vector(os.path.join(trainFilePath, filename)) 
  classifyNum = classify0(vectorUnderTest,trainSet,hwLabels,10) 
  print "the classifier came back with : %d , the real answer is : %d"% (classifyNum , classNum) 
  if(classifyNum != classNum) : errorCount+=1 
 print ("\nthe total number of error is : %d"%errorCount) 
 print ("\nthe error rate is : %f"%(float(errorCount)/mTest)) 
handwritingClassTest()