#!/usr/bin/python 
#coding:utf-8 
 
import numpy as np 
import operator 
import matplotlib 
import matplotlib.pyplot as plt 
import os 
 
''''' 
KNN算法 
1. 計算已知類別數據集中的每個點依次執行與當前點的距離。 
2. 按照距離遞增排序。 
3. 選取與當前點距離最小的k個點 
4. 確定前k個點所在類別的出現頻率 
5. 返回前k個點出現頻率最高的類別作為當前點的預測分類 
''' 
 
''''' 
inX為要分類的向量 
dataSet為訓練樣本 
labels為標簽向量 
k為最近鄰的個數 
''' 
def classify0(inX , dataSet , labels , k): 
 dataSetSize = dataSet.shape[0]#dataSetSize為訓練樣本的個數 
 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] 
 
 
''''' 
將圖像轉換為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 
 
''''' 
手寫體識別系統測試 
''' 
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()