# -*- coding: utf-8 -*-
#pip install numpy
import os
import os.path
from numpy import *
import operator
import time
from os import listdir
 
"""
描述：
  KNN算法實(shí)現(xiàn)分類器
參數(shù)：
  inputPoint：測試集
  dataSet：訓(xùn)練集
  labels：類別標(biāo)簽
  k:K個(gè)鄰居
返回值：
  該測試數(shù)據(jù)的類別
"""
def classify(inputPoint,dataSet,labels,k):
  dataSetSize = dataSet.shape[0] #已知分類的數(shù)據(jù)集（訓(xùn)練集）的行數(shù)
  #先tile函數(shù)將輸入點(diǎn)拓展成與訓(xùn)練集相同維數(shù)的矩陣，再計(jì)算歐氏距離
  diffMat = tile(inputPoint,(dataSetSize,1))-dataSet #樣本與訓(xùn)練集的差值矩陣
 
  # print(inputPoint);
  sqDiffMat = diffMat ** 2 #sqDiffMat 的數(shù)據(jù)類型是nump提供的ndarray,這不是矩陣的平方，而是每個(gè)元素變成原來的平方。
  sqDistances = sqDiffMat.sum(axis=1)  #計(jì)算每一行上元素的和
  # print(sqDistances);
  distances = sqDistances ** 0.5   #開方得到歐拉距離矩陣
  # print(distances);
  sortedDistIndicies = distances.argsort() #按distances中元素進(jìn)行升序排序后得到的對應(yīng)下標(biāo)的列表,argsort函數(shù)返回的是數(shù)組值從小到大的索引值
  # print(sortedDistIndicies);
 
  # classCount數(shù)據(jù)類型是這樣的{0: 2, 1: 2}，字典key：value
  classCount = {}
  # 選擇距離最小的k個(gè)點(diǎn)
  for i in range(k):
    voteIlabel = labels[ sortedDistIndicies[i] ]
    # print(voteIlabel)
    # 類別數(shù)加1
    classCount[voteIlabel] = classCount.get(voteIlabel,0)+1
  print(classCount)# {1: 1, 7: 2}
  #按classCount字典的第2個(gè)元素（即類別出現(xiàn)的次數(shù)）從大到小排序
  sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True)
  print(sortedClassCount)# [(7, 2), (1, 1)]
  return sortedClassCount[0][0]
 
"""
描述：
  讀取指定文件名的文本數(shù)據(jù)，構(gòu)建一個(gè)矩陣
參數(shù)：
  文本文件名稱
返回值：
  一個(gè)單行矩陣
"""
def img2vector(filename):
 returnVect = []
 fr = open(filename)
 for i in range(32):
  lineStr = fr.readline()
  for j in range(32):
   returnVect.append(int(lineStr[j]))
 return returnVect
 
"""
描述：
  從文件名中解析分類數(shù)字，比如由0_0.txt得知這個(gè)文本代表的數(shù)字分類是0
參數(shù)：
  文本文件名稱
返回值：
  一個(gè)代表分類的數(shù)字
"""
def classnumCut(fileName):
  fileStr = fileName.split('.')[0]
  classNumStr = int(fileStr.split('_')[0])
  return classNumStr
 
"""
描述：
  構(gòu)建訓(xùn)練集數(shù)據(jù)向量，及對應(yīng)分類標(biāo)簽向量
參數(shù)：
  無
返回值：
  hwLabels：分類標(biāo)簽矩陣
  trainingMat：訓(xùn)練數(shù)據(jù)集矩陣
"""
def trainingDataSet():
  hwLabels = []
  trainingFileList = listdir('trainingDigits')   #獲取目錄內(nèi)容
  m = len(trainingFileList)
  # zeros返回全部是0的矩陣，參數(shù)是行和列
  trainingMat = zeros((m,1024))    #m維向量的訓(xùn)練集
  for i in range(m):
    # print (i);
    fileNameStr = trainingFileList[i]
    hwLabels.append(classnumCut(fileNameStr))
    trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)
  return hwLabels,trainingMat
 
"""
描述：
  主函數(shù)，最終打印識別了多少個(gè)數(shù)字以及識別的錯(cuò)誤率
參數(shù)：
  無
返回值：
  無
"""
def handwritingTest():
  """
  hwLabels,trainingMat 是標(biāo)簽和訓(xùn)練數(shù)據(jù)，
  hwLabels 是一個(gè)一維矩陣，代表每個(gè)文本對應(yīng)的標(biāo)簽（即文本所代表的數(shù)字類型）
  trainingMat是一個(gè)多維矩陣，每一行都代表一個(gè)文本的數(shù)據(jù)，每行有1024個(gè)數(shù)字（0或1）
  """
  hwLabels,trainingMat = trainingDataSet() #構(gòu)建訓(xùn)練集
  testFileList = listdir('testDigits') #獲取測試集
  errorCount = 0.0    #錯(cuò)誤數(shù)
  mTest = len(testFileList)    #測試集總樣本數(shù)
  t1 = time.time()
  for i in range(mTest):
    fileNameStr = testFileList[i]
    classNumStr = classnumCut(fileNameStr)
    # img2vector返回一個(gè)文本對應(yīng)的一維矩陣，1024個(gè)0或者1
    vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
    #調(diào)用knn算法進(jìn)行測試
    classifierResult = classify(vectorUnderTest, trainingMat, hwLabels, 3)
    # 打印測試出來的結(jié)果和真正的結(jié)果，看看是否匹配
    print ("the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr))
    # 如果測試出來的值和原值不相等，errorCount+1
    if (classifierResult != classNumStr):
      errorCount += 1.0
  print("\nthe total number of tests is: %d" % mTest)   #輸出測試總樣本數(shù)
  print ("the total number of errors is: %d" % errorCount )  #輸出測試錯(cuò)誤樣本數(shù)
  print ("the total error rate is: %f" % (errorCount/float(mTest))) #輸出錯(cuò)誤率
  t2 = time.time()
  print ("Cost time: %.2fmin, %.4fs."%((t2-t1)//60,(t2-t1)%60) ) #測試耗時(shí)
 
"""
描述：
  指定handwritingTest（）為主函數(shù)
"""
if __name__ == "__main__":
 handwritingTest()