#?encoding:utf-8
import?numpy?as?np
import?os
import?operator

#?訓練數據集文件路徑
Dir?=?‘C:\Users\zqwke\Desktop\dataset\digits\\trainingDigits\\‘
#?測試數據集文件路徑
Dir_test?=?‘C:\Users\zqwke\Desktop\dataset\digits\\testDigits\\‘

‘‘‘
算法思路：
1、首先將（32x32）的數據矩陣轉化為（1x1024）的格式。
然后把訓練數據集最后轉化為（Mx1024）的一個矩陣形式，記為A，每一行是一個手寫數字
2、同樣把要測試的單個手寫數字轉化為（1x1024）格式，然后重復訓練樣本個數的次數，得到（Mx1024）的格式，記為B，每一行都一樣，M為訓練樣本總數
3、計算A與B之間的距離，得到單個手寫數字與所有訓練集的距離
4、對距離數組排序，得到距離最近的K個點
5、在K個點中出現頻率最高的數字記為最后分類結果

‘‘‘

#?原數據矩陣轉化方法，由?[32?32]?→?[1?1024]
def?ImageVector（Dir?filename）:
????#?創建一個1x1024的零矩陣
????ImageVec?=?np.zeros（1024）
????fr?=?open（Dir?+?filename）
????#?將原數據儲存進零矩陣
????for?i?in?range（32）:
????????line?=?fr.readline（）
????????for?j?in?range（32）:
????????????ImageVec[32*i+j]?=?int（line[j]）
????return?ImageVec

#?數據載入
def?LoadData（Dir）:
????List?=?os.listdir（Dir）??#?得到Dir路徑下的所有文件目錄
????NumTraining?=?len（List）??#?計算共用多少個文件
????TrainingSet?=?np.zeros（（NumTraining?1024））??#?構建一個Mx1024的矩陣?，?M即為文件個數
????Labels?=?np.zeros（NumTraining）??#?標簽矩陣
????#?將訓練集儲存到一個訓練矩陣
????for?i?in?range（NumTraining）:
????????FileName?=?List[i]
????????int_x?=?ImageVector（Dir?FileName）
????????for?j?in?range（1024）:
????????????TrainingSet[i][j]?=?int_x[j]
????????Labels[i]?=?List[i][0]??#?得到每個手寫數據的對應標簽數組
????return?TrainingSet?Labels

#?計算距離，此處省略對差作平方，這一步放在Classify中，距離公式等于distance?=?（∑（trainingSet?-?輸入）**2）**0.5
def?DisCompute（Array）:
????Distance?=?0
????for?i?in?range（len（Array））:
????????Distance?+=?Array[i]
????return?Distance**0.5

#??KNN分類
def?Classify（input?DataSet?Label?k）:
????DataSize?=?DataSet.shape[0]
????diffMat?=?np.tile（input?（DataSize?1））?-?DataSet
????sqDiffMat?=?diffMat?**?2
????Distance_squence?=?np.zeros（len（sqDiffMat））??#?距離序列
????for?i?in?range（len（sqDiffMat））:
????????distances?=?DisCompute（sqDiffMat[i]）
????????Distance_squence[i]?=?distances
????sortedDistance?=?Distance_squence.argsort（）??#?將距離按升序排列，argsort得到的是升序排序的索引值，而不是距離
????classcount?=?{}??#?K近鄰字典
????#??把距離最近的前K個點的標簽存進字典，Key為標簽。value為出現頻數
????for?i?in?range（k）:
????????voteLabel?=?Label[sortedDistance[i]]
????????classcount[voteLabel]?=?classcount.get（voteLabel?0）?+?1
????#??得到排序后的字典，按value值排序，最終返回出現次數最高的類標簽，即為分類結果
????sortedClassCount?=?sorted（classcount.iteritems（）?key=operator.itemgetter（1）?reverse=True）
????return?sortedClassCount[0][0]


def?handWritingTest（）:
????print?‘......Loading?Training?Date......‘
????trainingset?Label_x?=?LoadData（Dir）
????print?‘......Loading?Testing?Date.......‘
????testingset?Label_y?=?LoadData（Dir_test）
????testing_num?=?len（testingset）
????count?=?0
????print?‘......Testing......‘
????#??開始測試，識別正確輸出Right和對應序號，識別錯誤輸出False和對應序號
????for?i?in?range（testing_num）:
????????output?=?Classify（testingset[i]?trainingset?Label_x?5）
????????if?output?==?Label_y[i]:
????????????print?‘Right?%d‘?%?i
????????????count?+=?1
????????else:
????????????print?‘False?%d‘?%?i
????TheRightRate?=?float（count）/testing_num
??

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_0.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_1.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_10.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_11.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_12.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_13.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_14.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_15.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_16.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_17.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_18.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_19.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_2.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_20.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_21.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_22.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_23.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_24.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_25.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_26.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_27.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_28.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_29.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_3.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_30.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_31.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_32.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_33.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_34.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_35.txt
?????文件????????1088??2010-10-07?21:35??digits\testDigits\0_36.txt
............此處省略2850個文件信息