最近鄰法：保存兩個(gè)已知分類的樣本，用新樣本依次與已經(jīng)保存的兩類樣本計(jì)算歐式距離，分類
結(jié)果指向距離最小的樣本。
K-近鄰法:
在最近鄰法的基礎(chǔ)上，引進(jìn)投票機(jī)制，選擇若干個(gè)距離新樣本最近的已知樣本，用他所 得類別最大票數(shù)做為新樣本所屬類別。
注意：為保證公平，投票數(shù)量（k）為奇數(shù)
歐式距離：
||xi-xj|| xi,xj為特征向量，||。。||先取絕對(duì)值再取模
錯(cuò)誤率:
樣本趨于無(wú)窮，k值趨于無(wú)窮時(shí) k-近鄰法的錯(cuò)誤率接近貝葉斯錯(cuò)誤率
算法：
涉及的語(yǔ)言以及依賴庫(kù)：
本算法采用python3完成，事先需要安裝python3的numpy,pandas,random庫(kù)。
其中numpy庫(kù)涉及矩陣運(yùn)算，以及科學(xué)數(shù)據(jù)處理。pandas涉及excel文檔數(shù)據(jù)的導(dǎo)入。random庫(kù)涉及隨機(jī)數(shù)的產(chǎn)生，用于產(chǎn)生本程序所需要的k_折交叉驗(yàn)證用到的隨機(jī)分包索引矩陣。
程序：
# -*- coding: utf-8 -*-
"""
Created on Sun Nov 19 17:27:04 2017
@author: hasee
"""
import pandas as pd
import math
import random
import numpy as np
#讀取文件的數(shù)據(jù)集
def read_file(filename):
file_data = pd.read_excel(filename,index_col=None,header=None,sheetname=0)
example_data = np.array(file_data)
example_data = example_data.tolist()
example_data = np.mat(example_data)
return example_data
#計(jì)算矩陣中各元素平方
def numplus(plus_data):
m,n = np.shape(plus_data)
for i in list(range(0,m)):
for j in list(range(0,n)):
plus_data[i,j]=plus_data[i,j]**2
target_data = plus_data.sum(1)
m1,n1 = np.shape(target_data)
for k in list(range(0,m1)):
for v in list(range(0,n1)):
target_data[k,v]=np.sqrt(target_data[k,v])
return target_data
#尋找數(shù)量最多的元素的值
def maxnum(label_map):
label_list = label_map.tolist()
num_list=[]
m,n=np.shape(label_map)
for i in list(range(0,m)): #獲取標(biāo)簽矩陣中個(gè)數(shù)最多的元素
b=label_list[i]
d=max(b,key=b.count)
num_list.append(d)
label_mat = np.mat(num_list).T
return label_mat
#K折交叉驗(yàn)證隨機(jī)分包行標(biāo)記,row_big為樣本集最大行數(shù)
def rndom_rows(row_big,k):
rows = list(range(0,row_big))
goals = []
rows = set(rows)
for i in list(range(0,k)):
a = random.sample(rows,int(row_big/k)) #在給定的rows里面選擇row_big/k個(gè)不同的數(shù)
b = set(a)
rows = rows -b
goals.append(a)
goal = np.array(goals)
index_matrix = np.mat(goal)
return index_matrix
#用k_折交叉驗(yàn)證獲取訓(xùn)練數(shù)據(jù)以及測(cè)試數(shù)據(jù)
def k_validation(example_data,index_matrix,k1): #k1表式取索引矩陣的第k1組數(shù)據(jù)作為測(cè)試集合
exm_list=example_data.tolist() #樣本數(shù)據(jù)轉(zhuǎn)化為列表
index_list = index_matrix.tolist() #分包索引矩陣轉(zhuǎn)化問(wèn)列表
m,n = np.shape(exm_list) #獲取樣本數(shù)據(jù)大小
m1,n1 = np.shape(index_list) #獲取索引矩陣大小
test=[]
train=[]
for i in list(range(0,int(m/10))): #遍歷index_matrix中數(shù)據(jù)集測(cè)試集索引
c = index_list[k1][i]
test.append(exm_list[c]) #根據(jù)index_d=matrix的索引獲取樣本集，保存在test列表中
test_data=np.mat(test) #樣本列表轉(zhuǎn)換成矩陣
for x in test: #刪除樣本集中取出的測(cè)試集相等子集
exm_list.remove(x)
train = exm_list
train_data = np.mat(train) #訓(xùn)練樣本列表轉(zhuǎn)矩陣
return test_data,train_data #返回樣本集，測(cè)試集
#獲取測(cè)試集與訓(xùn)練集的歐式距離矩陣
def get_distance(train_data,test_data):
m,n = np.shape(train_data)
m1,n1=np.shape(test_data)
r_train = train_data[:,0:n-1] #獲取除標(biāo)簽外的test_data和train_data
r_test = test_data[:,0:n1-1]
each_row = np.mat(np.zeros((m+1,1))) #建立按列增加的矩陣
each_col = np.mat(np.zeros((1,n-1))) #建立按行增加的矩陣
for i in list(range(0,m1)):
for j in list(range(0,m)):
a=r_train[j,:]-r_test[i,:] #計(jì)算樣本和測(cè)試集坐標(biāo)差
each_col=np.vstack((each_col,a)) #按行增加保存在each_col矩陣中
target_data = numplus(each_col) #根據(jù)坐標(biāo)差調(diào)用numplus()函數(shù)，計(jì)算歐式距離
each_row = np.hstack((each_row,target_data)) #按列增加模式保存在each_row距離矩陣中
each_col = np.mat(np.zeros((1,n-1)))
distance = each_row #距離矩陣賦值給distance
m2,n2 = np.shape(distance)
distance_data = distance[1:m2,1:n2] #刪除空間分配時(shí)產(chǎn)生的零行和零列
m,n = np.shape(distance_data)
return distance_data #返回距離矩陣
#在距離矩陣中實(shí)現(xiàn)分類
def classify_data(distance,train_data,test_data,K):
m,n = np.shape(train_data)
pre_clsy = np.hstack((distance,train_data[:,n-1])) #將訓(xùn)練集的標(biāo)簽按行增加的方式，貼到距離矩陣中，距離矩陣中的每一列代表一個(gè)樣本和所有訓(xùn)練集的歐氏距離
pre_clsy = pre_clsy.T #求距離矩陣的轉(zhuǎn)置標(biāo)簽變?yōu)樽詈笠恍?br> m1,n1=np.shape(pre_clsy)
clsy_index = np.mat(np.zeros((1,n1)))
for i in list(range(0,m1-1)):
index_sort = np.argsort(pre_clsy[i,:]) #按行排序把排好序的數(shù)據(jù)在未排序之前的元素所在的位置保存在位置矩陣中
clsy_index = np.vstack((clsy_index,index_sort))
clsy_index = clsy_index[1:m1,:] #獲取除標(biāo)簽外的所有行的數(shù)據(jù)排序后的位置矩陣
target_index = clsy_index[:,0:K] #K_近鄰法要求取的前k各最小的元素，索引矩陣前k行
m2,n2 =np.shape(target_index)
for i in list(range(0,m2)):
for j in list(range(0,n2)):
a=target_index[i,j]
target_index[i,j] =train_data[a,n-1] #將索引矩陣映射到原矩陣的標(biāo)簽處
label_map = target_index
label = maxnum(label_map) #投票求出得票數(shù)最多的類型，并將其標(biāo)簽保存
target_clsy = np.hstack((test_data,label)) #得到的標(biāo)簽保存后按列擴(kuò)增后貼到測(cè)集合上
return target_clsy,label
#獲取分類的錯(cuò)誤率
def get_accuracy(target_classify_data):
m,n=np.shape(target_classify_data)
count=0
for i in list(range(0,m)):
if target_classify_data[i,n-1] !=target_classify_data[i,n-2]: #判斷分類后的標(biāo)簽與原測(cè)試數(shù)據(jù)是否相等，若不相等則count+1
count+=1
else:
true_rate=(m-count)/m #計(jì)算正確率
target_classify_data[:,n-2]=target_classify_data[:,n-1]
classify_data = target_classify_data[:,0:n-1] #刪除原標(biāo)簽，貼上分類判斷得到的結(jié)果標(biāo)簽
return classify_data,true_rate #返回分類最終結(jié)果，以及正確率
#構(gòu)建分類器
def classify_cot(filename,K):
data = read_file(filename) #獲取iris數(shù)據(jù)集
m,n = np.shape(data) #獲取原數(shù)據(jù)集行，列大小
for k0 in list(range(0,1)): #k_折交叉驗(yàn)證循環(huán)，循環(huán)次數(shù)為子集個(gè)
index_matrix = rndom_rows(m,10) #獲取樣本隨機(jī)分包索引
test_data,train_data = k_validation(data,index_matrix,1) #分包得到測(cè)試集以及數(shù)據(jù)集
distance = get_distance(train_data,test_data)
target_index,label = classify_data(distance,train_data,test_data,K)
clsy_data,true_rate = get_accuracy(target_index)
print("\n\n")
print("------------------------%s-----------------------------------------------------------"%filename)
print("分離出來(lái)的訓(xùn)練集：")
print(train_data)
print("分離出來(lái)的測(cè)試集：")
print(test_data)
print("標(biāo)簽匹配矩陣")
print(target_index)
print("分類結(jié)果矩陣")
print(clsy_data)
print("分類正確率")
print(true_rate)
print("原數(shù)據(jù)行數(shù)：")
print(m)
print("-------------------------%s-----------------------------------------------------------"%filename)
print("\n\n")
#定義最近鄰分類子函數(shù)
def B_NN():
#最近鄰法iris數(shù)據(jù)集分類
iris='iris.xlsx'
classify_cot(iris,1)
#最近鄰法sonar分類
sonar = 'sonar.xlsx'
classify_cot(sonar,1)
#定義k_近鄰子函數(shù)
def K_NN():
#最近鄰法iris數(shù)據(jù)集分類
iris='iris.xlsx'
classify_cot(iris,80)
#最近鄰法sonar分類
sonar = 'sonar.xlsx'
classify_cot(sonar,80)
B_NN()
K_NN()
最后：代碼是自己根據(jù)原理敲出來(lái)的，有什么不足之處希望大佬們斧正。
