K-近邻算法

作者:管理员 发布时间:2021-02-07 16:33

k-邻近算法的原理:

存在一个样本数据集合,也称作训练样本集,并且样本集中每个数据都存在标签,即我们知道样本集中每一条数据与所属分类的对应关系。输入没有标签的新数据后,将新数据的每个特征与样本集每个样本数据对应的特征进行比较,然后提取样本集中特征最相似数据(k个最邻近数据)的分类标签。k一般不超过20,最后选择k个最相似数据中出现次数最多的分类,作为新数据的分类。

k-邻近算法 的优缺点:

    优点:精准度高、对异常值不敏感、无数据输入假定。

    缺点:计算复杂度高、空间复杂度高。

   适用范围:数值型和标称型。


实例:手写数字识别系统
样例数据如下:许许多多这样的文本,我们需要先读出每个文件到数据集中,然后在后续分类(提供有格外的测试文件夹)  

  

import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split
import os
 
#Tanimoto距离 计算数据集间的距离
def tanimoto(data,person1,person2):
	n = len(person2)
	combine = [person2[item] for item in range(n) if data.iloc[person1][item] == person2[item]]
	return float(len(combine)) / (2*n - len(combine))
 
#kNN核心预测函数 predict(数据集,目标变量,测试数据行,kNN数,计算距离函数)
def predict(data,target,test_data,cnt=3,calculate=tanimoto):
	k = []
	n = len(data)
	for i in range(n):
		score = calculate(data,i,test_data)
		k.append((score,target.iloc[i]))
	k.sort(reverse=True)			#k 获得所有距离元组列表
	rank = k[:cnt]					#rank 获得排序后的前cnt个列表
	only_labels = set(target)		#only_labels 获得唯一标签集合
	dic_labels = {}					#dic_labels 获得标签出现次数
	for i in only_labels:			#初始化字典
		dic_labels[i] = 0
	for i in rank:					#计算出现次数
		dic_labels[i[1]] +=1
	result = [(j,i) for i,j in dic_labels.items()]	#i:类 j:次数		需要交换位置以便排序
	result.sort(reverse=True)
	return result[0][1]
 
#测试错误率函数 errop_test(数据集DataFrame,目标变量Series)
def error_test(df_data,df_target):
	train_X,test_X,train_y,test_y = train_test_split(df_data,df_target,test_size=0.1,random_state=10)
	error = 0
	n = len(test_X)
	for i in range(n):
		print("{} 条数据运行中...".format(i))
		value = predict(train_X,train_y,test_X.iloc[i],5)
		if(value != test_y.iloc[i]):
			error +=1
			print("预测值:{0},真实值:{1}".format(value,test_y.iloc[i]))
	error_rate = error / float(n)
	print("测试结果所得错误率为:{}".format(error_rate))
 
#读取文件内容
def img2vector(filename):
	returnVect = np.zeros((1,1024))
	fr = open(filename)
	for i in range(32):
		lineStr = fr.readline()
		for j in range(32):
			returnVect[0,32*i+j] = int(lineStr[j])
	return returnVect
 
#处理数据格式,然后测试错误率
def handwriting():
	train_hwtarget = []
	train_hwdata = []
	train_filelists = os.listdir(r"./digits/trainingDigits")	#获取数据集
	n = len(train_filelists)
	for i in range(n):
		train_hwdata.append(img2vector(r'./digits/trainingDigits/{0}'.format(train_filelists[i]))[0])
		train_hwtarget.append(int(train_filelists[i].split('_')[0]))
	train_data = pd.DataFrame(train_hwdata)
	train_target = pd.Series(train_hwtarget)
	test_hwtarget = []
	test_hwdata = []
	test_filelists = os.listdir(r"./digits/testDigits")		#根据文件名获取目标变量
	m = len(test_filelists)
	for i in range(m):
		test_hwdata.append(img2vector(r'./digits/testDigits/{0}'.format(test_filelists[i]))[0])
		test_hwtarget.append(int(test_filelists[i].split('_')[0]))
	test_data = pd.DataFrame(test_hwdata)
	test_target = pd.Series(test_hwtarget)
	print("下面开始进行测试:")
 
	# error_test(train_data,train_target)		#方法一:直接利用训练数据集 进行划分后求错误率
 
	error = 0
	for i in range(m):						#方法二:训练数据集只训练,利用已知答案测试数据集来求错误率
		value = predict(train_data,train_target,test_data.iloc[i,:],5,tanimoto)
		print("{} 条数据运行中...".format(i))
		if(value != test_target.iloc[i]):
			error +=1
			print("预测错误:预测值:{0},真实值:{1}".format(value, test_target.iloc[i]))
	error_rate = error / float(m)
	print("测试结果所得错误率为:{}".format(error_rate))
 
if __name__=="__main__":
	#手写数字
	handwriting()

由于计算量太大,每个测试向量2000次距离计算,每个距离1024个维度运算,总共执行900次。所以我提前结束了,我用较少的测试集试过代码正确的。

这里也是我需要说明的一点,前面在缺点说明时提过,KNN的时间、空间复杂度很高,所以应该合理的使用该算法。


标签:
Copyright © 2020 万物律动 旗下 AI算法狮 京ICP备20010037号-1
本站内容来源于网络开放内容的收集整理,并且仅供学习交流使用;
如有侵权,请联系删除相关内容;