最近邻法：保存两个已知分类的样本，用新样本依次与已经保存的两类样本计算欧式距离，分类
结果指向距离最小的样本。
K-近邻法:
在最近邻法的基础上，引进投票机制，选择若干个距离新样本最近的已知样本，用他所 得类别最大票数做为新样本所属类别。
注意：为保证公平，投票数量（k）为奇数
欧式距离：
||xi-xj|| xi,xj为特征向量，||。。||先取绝对值再取模
错误率:
样本趋于无穷，k值趋于无穷时 k-近邻法的错误率接近贝叶斯错误率
算法：
涉及的语言以及依赖库：
本算法采用python3完成，事先需要安装python3的numpy,pandas,random库。
其中numpy库涉及矩阵运算，以及科学数据处理。pandas涉及excel文档数据的导入。random库涉及随机数的产生，用于产生本程序所需要的k_折交叉验证用到的随机分包索引矩阵。
程序：
# -*- 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
#读取文件的数据集
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
#计算矩阵中各元素平方
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
#寻找数量最多的元素的值
def maxnum(label_map):
label_list = label_map.tolist()
num_list=[]
m,n=np.shape(label_map)
for i in list(range(0,m)): #获取标签矩阵中个数最多的元素
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折交叉验证随机分包行标记,row_big为样本集最大行数
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个不同的数
b = set(a)
rows = rows -b
goals.append(a)
goal = np.array(goals)
index_matrix = np.mat(goal)
return index_matrix
#用k_折交叉验证获取训练数据以及测试数据
def k_validation(example_data,index_matrix,k1): #k1表式取索引矩阵的第k1组数据作为测试集合
exm_list=example_data.tolist() #样本数据转化为列表
index_list = index_matrix.tolist() #分包索引矩阵转化问列表
m,n = np.shape(exm_list) #获取样本数据大小
m1,n1 = np.shape(index_list) #获取索引矩阵大小
test=[]
train=[]
for i in list(range(0,int(m/10))): #遍历index_matrix中数据集测试集索引
c = index_list[k1][i]
test.append(exm_list[c]) #根据index_d=matrix的索引获取样本集，保存在test列表中
test_data=np.mat(test) #样本列表转换成矩阵
for x in test: #删除样本集中取出的测试集相等子集
exm_list.remove(x)
train = exm_list
train_data = np.mat(train) #训练样本列表转矩阵
return test_data,train_data #返回样本集，测试集
#获取测试集与训练集的欧式距离矩阵
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] #获取除标签外的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,:] #计算样本和测试集坐标差
each_col=np.vstack((each_col,a)) #按行增加保存在each_col矩阵中
target_data = numplus(each_col) #根据坐标差调用numplus()函数，计算欧式距离
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] #删除空间分配时产生的零行和零列
m,n = np.shape(distance_data)
return distance_data #返回距离矩阵
#在距离矩阵中实现分类
def classify_data(distance,train_data,test_data,K):
m,n = np.shape(train_data)
pre_clsy = np.hstack((distance,train_data[:,n-1])) #将训练集的标签按行增加的方式，贴到距离矩阵中，距离矩阵中的每一列代表一个样本和所有训练集的欧氏距离
pre_clsy = pre_clsy.T #求距离矩阵的转置标签变为最后一行
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,:]) #按行排序把排好序的数据在未排序之前的元素所在的位置保存在位置矩阵中
clsy_index = np.vstack((clsy_index,index_sort))
clsy_index = clsy_index[1:m1,:] #获取除标签外的所有行的数据排序后的位置矩阵
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] #将索引矩阵映射到原矩阵的标签处
label_map = target_index
label = maxnum(label_map) #投票求出得票数最多的类型，并将其标签保存
target_clsy = np.hstack((test_data,label)) #得到的标签保存后按列扩增后贴到测集合上
return target_clsy,label
#获取分类的错误率
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]: #判断分类后的标签与原测试数据是否相等，若不相等则count+1
count+=1
else:
true_rate=(m-count)/m #计算正确率
target_classify_data[:,n-2]=target_classify_data[:,n-1]
classify_data = target_classify_data[:,0:n-1] #删除原标签，贴上分类判断得到的结果标签
return classify_data,true_rate #返回分类最终结果，以及正确率
#构建分类器
def classify_cot(filename,K):
data = read_file(filename) #获取iris数据集
m,n = np.shape(data) #获取原数据集行，列大小
for k0 in list(range(0,1)): #k_折交叉验证循环，循环次数为子集个
index_matrix = rndom_rows(m,10) #获取样本随机分包索引
test_data,train_data = k_validation(data,index_matrix,1) #分包得到测试集以及数据集
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("分离出来的训练集：")
print(train_data)
print("分离出来的测试集：")
print(test_data)
print("标签匹配矩阵")
print(target_index)
print("分类结果矩阵")
print(clsy_data)
print("分类正确率")
print(true_rate)
print("原数据行数：")
print(m)
print("-------------------------%s-----------------------------------------------------------"%filename)
print("\n\n")
#定义最近邻分类子函数
def B_NN():
#最近邻法iris数据集分类
iris='iris.xlsx'
classify_cot(iris,1)
#最近邻法sonar分类
sonar = 'sonar.xlsx'
classify_cot(sonar,1)
#定义k_近邻子函数
def K_NN():
#最近邻法iris数据集分类
iris='iris.xlsx'
classify_cot(iris,80)
#最近邻法sonar分类
sonar = 'sonar.xlsx'
classify_cot(sonar,80)
B_NN()
K_NN()
最后：代码是自己根据原理敲出来的，有什么不足之处希望大佬们斧正。
