#!/usr/bin/python 
#coding:utf-8 
 
import numpy as np 
import operator 
import matplotlib 
import matplotlib.pyplot as plt 
import os 
 
''''' 
KNN算法 
1. 計算已知類別數(shù)據(jù)集中的每個點依次執(zhí)行與當(dāng)前點的距離。 
2. 按照距離遞增排序。 
3. 選取與當(dāng)前點距離最小的k個點 
4. 確定前k個點所在類別的出現(xiàn)頻率 
5. 返回前k個點出現(xiàn)頻率最高的類別作為當(dāng)前點的預(yù)測分類 
''' 
 
''''' 
inX為要分類的向量 
dataSet為訓(xùn)練樣本 
labels為標簽向量 
k為最近鄰的個數(shù) 
''' 
def classify0(inX , dataSet , labels , k): 
 dataSetSize = dataSet.shape[0]#dataSetSize為訓(xùn)練樣本的個數(shù) 
 diffMat = np.tile(inX , (dataSetSize , 1)) - dataSet#將inX擴展為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#如果之前這個voteIlabel是有的，那么就返回字典里這個voteIlabel里的值，如果沒有就返回0 
 sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)#key=operator.itemgetter(1)的意思是按照字典里的第一個排序，{A:1,B:2},要按照第1個（AB是第0個），即‘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()