KNN（K近邻算法）
程序员文章站
2022-07-13 11:27:25
...
一、基本知识
KNN算法
===================================
KNN的三要素：
K值的影响：
1. K值过小，可能会导致过拟合
2. K值过大，可能会导致欠拟合
KNN伪代码：(将执行过程转换为代码的执行方式<代码+注释的形式>)
-1. 简单来写
def fit(self, X, Y, k=3):
self.X_train = X
self.Y_train = Y
self.k = k
def predict(self, X):
result = []
# 遍历所有的待预测样本，产生预测值，并将预测值保持到result临时集合中
for x in X:
# a. 计算当前样本x到训练数据集中的所有样本的距离
# 并返回样本的下标和距离组成的集合,eg,[(距离1，样本1下标), (距离2, 样本2下标).....]
all_distinces = self.calc_distinces(x)
# b. 按照距离的远近对样本做一个排序的操作(升序)
sort(all_distinces, key=lambda t: t[0])
# c. 获取距离最近的K个样本对应的距离和下标组成的集合
top_k_distinces = all_distinces[:self.k]
# d. 从最近的样本距离、下标集合中获取样本下标
top_k_indexs = list(map(lambda t:t[1], top_k_distinces))
# e. 获取K个邻居样本对应的目标属性Y
tmp_y = self.Y[top_k_indexs]
# f. 统计一下临时集合tmp_y中各个类别取值出现的数量
label_2_count_dict = self.calc_label_2_count(tmp_y)
# g. 将字典转换为数组
label_2_count_list = list(label_2_count_dict.items())
# h. 对数据按照出现次数做一个排序（升序）
sort(label_2_count_list, lambda t:t[1])
# i. 获取出现次数最多的那个类别作为预测值
tmp_label = label_2_count_list[-1][0]
# j. 将预测值添加到集合中
result.append(tmp_label)
return result
简化:
def fit(self, X, Y, k=3):
self.X_train = X
self.Y_train = Y
self.k = k
def predict(self, X):
result = []
# 遍历所有的待预测样本，产生预测值，并将预测值保持到result临时集合中
for x in X:
# a. 获取和当前样本最相似的K个邻近样本的下标值
top_k_indexs = self.fetch_nearst_neighbors(x)
# b. 获取K个邻居样本对应的目标属性Y
tmp_y = self.Y[top_k_indexs]
# c. 计算K个样本中各个类别出现的概率，并获取概率最大的类别作为预测值
tmp_label = self.fetch_max_proba_label(tmp_y)
# d. 将预测值添加到集合中
result.append(tmp_label)
return result
============================================================
以KNN算法为例：
-1. KNN算法是什么？KNN算法的基本原理是什么？
-2. KNN伪代码怎么写的？
-3. 你觉得有哪些因素可能影响KNN算法模型效果呢？你觉得KNN算法有什么缺点？
-4. 你觉得KNN算法的这个缺点可以怎么来解决？
以线性回归算法为例：
-1. 线性回归算法是什么？线性回归基本原理是什么？构建原理是什么？
-2. 损失函数是什么？
-3. 什么是梯度下降？BGD、SGD、MBGD这三种有什么区别？
-4. 建议：基于最大似然估计到处最小二乘的损失函数的那个过程理解一下。
-5. 你觉得线性回归算法有什么局限性吗？那你觉得这个局限性怎么解决？
-6. 过拟合和欠拟合的解决方案
-7. L1正则和L2正则
========================================================================
-1. 基于BGD、SGD的线性回归代码的实现
-2. 基于Python实现KNN分类算法(多数投票的分类算法)2、基于python的伪代码
数据：
======================= 基于python的KNN算法的伪代码 =====================================
#_*_coding:utf-8_*_
# 刘康
import warnings,os,re
import numpy as np
import pandas as pd
import matplotlib as mpl
import matplotlib.pyplot as plt
class Knn_code():
def __init__(self):
pass
def fit(self,X,Y,k):
'''
初始化样本
:param X: 已知特征属性矩阵 X
:param Y: 已知目标矩阵 Y
:param k: KNN算法k值
:return:
'''
self.X=X
self.Y=Y
self.k =k
def calc_distance(self,once):
'''
计算每一个待测样本与一直样本的距离的字典（key是已知样本的下标，value是与该样本的距离）
'''
distance_dict = {}
for index in range(X.shape[0]):
once_distance = np.sqrt(sum((X[index] - once)**2))
distance_dict[index] = once_distance
# print(distance_dict)
return distance_dict
def calc_label_counts_dict(self,label):
'''
计算每个标签类型的数量，返回一个字典（key是每一个标签类型，value是该类型的数目）
'''
counts_dict = dict(pd.Series(label).value_counts())
# print(counts,type(counts)) # Series 可以直接转化为字典
return counts_dict
def predict(self,X_predict):
'''
对给定数据进行数据类型预测
:param X_predict: 待预测 的样本的特征属性 矩阵X
:return:
'''
result = []
# 遍历所有的待预测样本，预测所有样本的类型，并保存带result列表中
for once in X_predict:
#计算被遍历单个样本与已知样本之间的距离字典（key是每个样本的索引，values与每个样本的距离）
distance_dict = self.calc_distance(once)
#将上述距离字典根据值进行升序排序，得到元组格式，即前k个是距离待测样本距离最近的k个样本
distance_list = list(sorted(distance_dict.items(),key=lambda x:x[1]))
# print(distance_list)
#利用上诉元组键值对获取k个最近样本的索引列表
index_list = list(map(lambda t:t[0],distance_list))[:self.k]
# 根据上述索引取出对应样本的目标属性
label_Y = self.Y[index_list]
# print(label_Y)
# 统计k个最近样本目标属性出现类别次数的字典
Y_count_dict = self.calc_label_counts_dict(label_Y)
# 将字典根据值的大小排序，返回列表
Y_count_list = list(sorted(Y_count_dict.items(),key = lambda t:t[1]))
# 获取上述列表最后一个元素中的类型
Y_type = Y_count_list[-1][0]
# print(Y_type)
# 将改样本的类型预测保存
result.append(Y_type)
return np.array(result)
if __name__ == '__main__':
df_data = pd.read_csv('./iris.data',sep=',',header=None)
print(df_data.info(),df_data.head())
# 清洗数据
df_data_label = df_data.iloc[:,-1]
df_data_label_list = np.unique(df_data_label)
# print(df_data_label_list)
label_transform_dict = dict(zip(df_data_label_list,range(len(df_data_label_list))))
# print(label_transform_dict)
label_list = [label_transform_dict[i] for i in df_data_label]
# print(label_list)
# 提取特征属性X 目标属性Y
X = np.array(df_data.iloc[:,:-1]) # 二维
Y = np.array(label_list) # 一维
knn = Knn_code()
knn.fit(X,Y,10)
# print(X)
# print('='*100)
# print(knn.Y)
# 带预测样本
X_test = np.array(df_data.iloc[:,:-1])
# print(X_test)
result_list = knn.predict(X_predict=X_test)
print('样本真实值结果是：{}'.format(Y))
print('样本预测的结果是：{}'.format(result_list))
三、基于sklearn库的KNN代码
=============================== ROC曲线 与 AUC值 ======================================
import matplotlib.pyplot as plt
from sklearn import metrics
if __name__ == '__main__':
------------------ 实际的类别y
y_true = [0, 0, 1, 1, 0, 1, 0]
------------------ 决策函数值，或者是样本属于y=1的概率值
y_scoreProd = [0.2, 0.45, 0.55, 0.68, 0.51, 0.9, 0.1]
------------------ 计算fpr， tpr以及阈值
fpr, tpr, thresholds = metrics.roc_curve(y_true, y_scoreProd)
print("FPR的值:{}".format(fpr))
print("TPR的值:{}".format(tpr))
print("阈值:{}".format(thresholds))
auc = metrics.auc(x=fpr, y=tpr)
print("面积：{}".format(auc))
plt.plot([0, 0, 0, 1], [0, 1.0 / 3, 1.0, 1.0], 'r-o') ----------- 'r-o' 画出红线带点的图
plt.show()
========================== 基于sklearn 库的 KNN算法模型 ===========================
#_*_coding:utf-8_*_
# 刘康
import os,re,warnings
import numpy as np
import pandas as pd
import matplotlib as mpl
import matplotlib.pyplot as plt
import sklearn
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import LabelEncoder
from sklearn.metrics import f1_score,accuracy_score,precision_score,recall_score,confusion_matrix,classification_report
# 1、加载数据
df_data = pd.read_csv('./iris.data',sep=',',header=None)
# print(df_data.info(),df_data.head())
# 2、清洗数据
df_label_Y = df_data.iloc[:,-1]
le = LabelEncoder()
le.fit(df_label_Y)
df_Y_trans = le.transform(df_label_Y) # 自动根据分类将标签进行编码 0,1,2,3 ......
# print(df_Y_trans)
# 3、提取特征属性X 目标属性Y
X = df_data.iloc[:,:-1]
Y = df_Y_trans
# print(X,Y)
# 4、分割训练集与测试集
# 5、特征工程
# 6、构建KNN模型
'''
class sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, weights='uniform',
algorithm='auto', leaf_size=30, p=2, metric='minkowski', metric_params=None, n_jobs=1, **kwargs)
'''
KNN_model = KNeighborsClassifier(n_neighbors=10,weights='distance',algorithm='kd_tree')
# 7、训练模型
KNN_model.fit(X,Y)
# 8、模型评估、参数查看、可视化
Y_predict = KNN_model.predict(X)
print('KNN模型的正确率：{}'.format(KNN_model.score(X,Y)))
# print('KNN模型的召回率：{}'.format(recall_score(Y,Y_predict))) # 注意默认的 二分类不能计算多分类的召回率
print('KNN模型测试集的概率：{}'.format(KNN_model.predict_proba(X))) #返回的是一个 N * 类型数量列 的矩阵
'''
# kneighbors：从训练数据中获取样本X的邻近样本，获取n_neighbors参数多个样本，并且根据参数return_distance决定是否返回距离值
# 当前参数的情况下，返回的是一个二元组，二元组的第一个元素是一个集合，集合中存储的是邻近样本的距离；第二个元素还是一个集合，存储的是邻近样本的下标
kneighbors = algo.kneighbors(X=x_test, n_neighbors=9, return_distance=True)
'''
X_test = X.iloc[:3,:]
print(X_test.shape)
kneighbors = KNN_model.kneighbors(X=X_test,n_neighbors=3,return_distance=True)
print('KNN模型测试集的最近的k个样本的距离、下标：{}'.format(kneighbors)) #
print(kneighbors) # 返回的是一个索引值
'''
# kneighbors_graph, 对于X而言，从训练数据中获取距离最近的n_neighbors多个样本，将X和这些样本之间认为是可以连通的，
故将其值设置为1
# mode给定值的设置方式，connectivity表示设置为1，distance表示设置为距离值
# 返回对象表示的是X和训练数据中哪些样本是可以连通的
# 列的数目是训练数据特征向量的数目，行的数目是x_test的样本数目
kneighbors_graph(X=None, n_neighbors=None, mode='connectivity')
'''
kneighbors_graph = KNN_model.kneighbors_graph(X=X_test,n_neighbors=2,mode='distance')
print('连接矩阵为：{}'.format(kneighbors_graph))
'''
连接矩阵为： (0, 0) 0.0
(0, 17) 0.09999999999999998
(1, 1) 0.0 ----------------- 前三行是第一个样本的三个最近样本的链接情况，最前面是下标，后面是距离
(1, 45) 0.14142135623730986
(2, 2) 0.0
(2, 47) 0.14142135623730978
'''
# 混淆矩阵
print('KNN模型的混淆矩阵为：{}'.format(confusion_matrix(Y,Y_predict)))
# 9、模型部署持久化
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.preprocessing import LabelEncoder
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import classification_report, confusion_matrix
from sklearn import metrics
if __name__ == '__main__':
# 1. 加载数据
df = pd.read_csv('../datas/iris.data', header=None, names=['A', 'B', 'C', 'D', 'E'])
# 删除一个类别的数据
df = df[df.E != 'Iris-setosa']
df.info()
"""
最终目的，是将X和Y转换为numpy数组的形式，并且值全部转换为数值型
-1. 因为需要获取X和Y，所以这里第一步从df中提取对应的X、Y， 并将X和Y转换为numpy数组
-2. 需要将Y中的字符串使用数字进行替换，eg:"Iris-setosa": 0, "Iris-versicolor": 1, "Iris-virginica": 2
"""
# 获取X和Y
columns = df.columns
X = np.array(df[columns[:-1]])
Y = np.array(df[columns[-1]])
# 使用LabelEncoder对Y进行编码
le = LabelEncoder()
le.fit(Y)
Y = le.transform(Y)
print("Y中的类别:{}".format(le.classes_))
# print("反转恢复:{}".format(le.inverse_transform([0, 1])))
# 2. 获取X的最后两列数据作为原始的特征属性X
# 按照索引获取所有行的最后两列的数据
X = X[:, -2:]
# print(X)
# 3. 构建模型
algo = KNeighborsClassifier(n_neighbors=9)
# 4. 模型训练
algo.fit(X, Y)
# 5. 看模型效果
Y_predict = algo.predict(X)
print("准确率:{}".format(algo.score(X, Y)))
print("训练数据上的分类报告:\n{}".format(classification_report(Y, Y_predict)))
# 更改阈值(我希望将所有有病的数据全部预测正确)
threshold = 0.77777778
# 获取所有的预测概率
test_predict_prob = algo.predict_proba(X)
# 获取下标为1的那一列概率
test_predict_prob = test_predict_prob[:, 1]
# 做一个布尔索引，将所有值大于等于阈值的区域设置为4.0，小于阈值的区域设置为2.0
test_predict_prob[test_predict_prob >= threshold] = 1
test_predict_prob[test_predict_prob < threshold] = 0
print("测试数据上的混淆矩阵:\n{}".format(confusion_matrix(Y, Y_predict)))
print("更改阈值后测试数据上的混淆矩阵:\n{}".format(confusion_matrix(Y, test_predict_prob)))
-------------------------- 多分类的情况不适合以下方法更改阈值、计算roc曲线，这里只谈论二分类更改阈值 ---------
# 需要计算一下AUC和ROC的值
# fpr、tpr和阈值 --> 需要实际值y和决策函数或者预测概率
test_predict_prob = algo.predict_proba(X)
print(test_predict_prob)
# 将类别y=1当做正例则获取预测为类别y=1的概率作为auc计算过程中的阈值列表对象
test_predict_prob = test_predict_prob[:, 1]
# 计算fpr、tpr和阈值
fpr, tpr, thresholds = metrics.roc_curve(Y, test_predict_prob)
# 计算AUC面积
auc = metrics.auc(x=fpr, y=tpr)
print("AUC面积：{}".format(auc))
print(thresholds)
plt.plot(fpr, tpr, 'r-o')
plt.show()============================ KNN多分类 ROC曲线与AUC值 ==================================
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.preprocessing import LabelEncoder
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import classification_report, confusion_matrix
from sklearn import metrics
if __name__ == '__main__':
# 1. 加载数据
df = pd.read_csv('../datas/iris.data', header=None, names=['A', 'B', 'C', 'D', 'E'])
df.info()
"""
最终目的，是将X和Y转换为numpy数组的形式，并且值全部转换为数值型
-1. 因为需要获取X和Y，所以这里第一步从df中提取对应的X、Y， 并将X和Y转换为numpy数组
-2. 需要将Y中的字符串使用数字进行替换，eg:"Iris-setosa": 0, "Iris-versicolor": 1, "Iris-virginica": 2
"""
# 获取X和Y
columns = df.columns
X = np.array(df[columns[:-1]])
Y = np.array(df[columns[-1]])
# 使用LabelEncoder对Y进行编码
le = LabelEncoder()
le.fit(Y)
Y = le.transform(Y)
print("Y中的类别:{}".format(le.classes_))
# print("反转恢复:{}".format(le.inverse_transform([0, 1])))
# 2. 获取X的最后两列数据作为原始的特征属性X
# 按照索引获取所有行的最后两列的数据
X = X[:, -2:]
# print(X)
# 3. 构建模型
algo = KNeighborsClassifier(n_neighbors=9)
# 4. 模型训练
algo.fit(X, Y)
# 5. 看模型效果
Y_predict = algo.predict(X)
print("准确率:{}".format(algo.score(X, Y)))
print("训练数据上的分类报告:\n{}".format(classification_report(Y, Y_predict)))
# 更改阈值(我希望将所有有病的数据全部预测正确)
threshold = 0.77777778
# 获取所有的预测概率
test_predict_prob = algo.predict_proba(X)
# 获取下标为1的那一列概率
test_predict_prob = test_predict_prob[:, 1]
# 做一个布尔索引，将所有值大于等于阈值的区域设置为4.0，小于阈值的区域设置为2.0
test_predict_prob[test_predict_prob >= threshold] = 1
test_predict_prob[test_predict_prob < threshold] = 0
print("测试数据上的混淆矩阵:\n{}".format(confusion_matrix(Y, Y_predict)))
print("更改阈值后测试数据上的混淆矩阵:\n{}".format(confusion_matrix(Y, test_predict_prob)))
# 需要计算一下AUC和ROC的值
# 分别计算AUC的值
test_predict_prob = algo.predict_proba(X)
print(test_predict_prob)
print(Y)
# TODO: 三段代码合并，也就是说要求不允许直接出现0 1 2这三个数字
# 对于第一个类别的AUC值的计算（y=0）
# 构建计算fpr和tpr的时候的实际值，将原始数据中所有类别为0的设置为1，其他类别设置为0
y1_true = (Y == 0).astype(np.int)
y1_score = test_predict_prob[:, 0]
fpr1, tpr1, _ = metrics.roc_curve(y1_true, y1_score)
auc1 = metrics.auc(fpr1, tpr1)
print("类别1的AUC值:{}".format(auc1))
# 对于第二个类别的AUC值的计算（y=1）
# 构建计算fpr和tpr的时候的实际值，将原始数据中所有类别为1的设置为1，其他类别设置为0
y2_true = (Y == 1).astype(np.int)
y2_score = test_predict_prob[:, 1]
fpr2, tpr2, _ = metrics.roc_curve(y2_true, y2_score)
auc2 = metrics.auc(fpr2, tpr2)
print("类别2的AUC值:{}".format(auc2))
# 对于第三个类别的AUC值的计算（y=2）
# 构建计算fpr和tpr的时候的实际值，将原始数据中所有类别为2的设置为1，其他类别设置为0
y3_true = (Y == 2).astype(np.int)
y3_score = test_predict_prob[:, 2]
fpr3, tpr3, _ = metrics.roc_curve(y3_true, y3_score)
auc3 = metrics.auc(fpr3, tpr3)
plt.plot(fpr1, tpr1, 'r-o')
plt.plot(fpr2, tpr2, 'g-o')
plt.plot(fpr3, tpr3, 'b-o')
plt.show()
================================= 一起计算 ROC与AUC值 ===================================
knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(X_train, Y_train)
# b. 模型效果输出
## 将正确的数据转换为矩阵形式
y_test_hot = label_binarize(Y_test,classes=(1,2,3)) ---------- 该方法的重点
## 得到预测属于某个类别的概率值
knn_y_score = knn.predict_proba(X_test)
## 计算roc的值
knn_fpr, knn_tpr, knn_threasholds = metrics.roc_curve(y_test_hot.ravel(),knn_y_score.ravel())
## 计算auc的值
knn_auc = metrics.auc(knn_fpr, knn_tpr)
print ("KNN算法准确率：", knn.score(X_train, Y_train))
print ("KNN算法AUC值：", knn_auc)
# c. 模型预测
knn_y_predict = knn.predict(X_test)
上一篇： TF2.0学习NOTE5: 探索解析 过拟合/欠拟合
下一篇： dropout学习笔记