网站开发业务需求分析,硅云wordpress多站点,南昌市房产网,做网站菏泽K 最近邻算法 简单 KNN海伦约会手写数字识别KNN 算法的优缺点 K 最近邻#xff08;K-NearestNeighbor#xff0c;KNN#xff09;算法#xff0c;是 1967 年由 Cover T 和 Hart P 提出的一种用于分类与回归的方法。 基本原理#xff1a;存在一个带标签的数据集#xff08;… K 最近邻算法 简单 KNN海伦约会手写数字识别KNN 算法的优缺点 K 最近邻K-NearestNeighborKNN算法是 1967 年由 Cover T 和 Hart P 提出的一种用于分类与回归的方法。 基本原理存在一个带标签的数据集也称为训练集数据集中的每一个样本与所属标签一一对应。当输入新的不带标签的样本数据预测数据时新的样本数据的每个特征会与训练集中每个样本的对应特征进行相似度计算最后提取与预测样本最相似的训练样本的标签。一般而言我们会选择训练集中前 K 个最相似的样本数据这就是 K 最近邻算法。
简单 KNN
假设有一个带标签的数据集包含“打斗镜头”和“接吻镜头”两个特征标签为“电影类型”数据集如下表所示
电影名称打斗镜头接吻镜头电影类型电影11101爱情片电影2589爱情片电影31085动作片电影41158动作片
现在有一个新的样本数据101 个打斗镜头20 个接吻镜头该如何预测它的所属类型呢
我们可以把打斗镜头作为 x 维度把接吻镜头作为 y 维度以此建立坐标系它们的坐标关系如下图所示 那我们又该如何比较新样本数据与训练集中样本数据的相似性呢
我们可以利用它们之间的距离来表示相似度具体可以根据以下公式 ∣ A B ∣ ( x 1 − x 2 ) 2 ( y 1 − y 2 ) 2 |AB| \sqrt{{(x_1 - x_2)}^{2} {(y_1 - y_2)}^{2}} ∣AB∣(x1−x2)2(y1−y2)2 通过计算我们可以得到以下结果
(101, 20) - 动作片 (108, 5) 的距离约为 16.55(101, 20) - 动作片 (115, 8) 的距离约为 18.44(101, 20) - 爱情片 (5, 89) 的距离约为 118.22(101, 20) - 爱情片 (1, 101) 的距离约为 128.69
通过计算可知新样本数据 (101, 20) 与训练集中的样本 (108, 5) 距离最近也就是最相似因此我们提取样本 (108, 5) 的标签“动作片”并将其赋给新样本数据 (101, 20)从而预测出新样本数据的电影类型为“动作片”这就是 KNN 模型完整的预测过程。
如果模型根据最相似的一个结果对新样本数据进行预测这只能说是最近邻算法而非 K 最近邻算法。K 最近邻算法需要返回最相似的前 K 个结果并对这 K 个结果进行概率统计最终选取概率最高的作为最后的预测结果。
K 最近邻算法步骤如下
计算新样本数据与训练集中每个样本数据之间的距离按照距离递增次序对样本数据进行排列选取前 K 个最相似的样本数据并获取它们的标签计算这 K 个标签的出现频率将出现频率最高的标签作为预测结果
比如在上述例子中选取 K3按照距离递增次序排列的前三个样本分别为动作片 (108, 5)、动作片 (115, 8)、爱情片 (5, 89)其中动作片出现的频率为 2/3因此我们可以预测新样本数据 (101, 20) 的电影类型为“动作片”。
上述案例的代码实现
import numpy as np
import pandas as pd# 读取数据集并划分特征数据和标签数据
def read_dataset():df pd.read_csv(rD:\MachineLearning\movie_type.csv) # 读取数据集data df.iloc[:, 1:] # 获取数据集的第 2、3、4 列数据data data.to_numpy() # 将 pandas.core.frame.DataFrame 转为 numpy.ndarraytrain_data data[:, :2] # data 的第 1、2 列为特征数据labels data[:, -1] # data 的第 3 列为标签数据return train_data, labels# 计算距离
def calculate_distance(predict_data, train_data):dist np.sqrt(np.sum((predict_data - train_data) ** 2, axis1)) # 计算新样本数据与训练集中每一个样本数据间的距离return dist# 预测结果
def select_best_result(dist, labels, k):labels_lst [labels[index] for index in dist.argsort()[:k]] # 获取前 k 个最相似数据对应的标签# 选取前 k 个标签中出现频率最高的作为最终结果num_labels {}num labels_lst.count(labels_lst[0])num_labels[labels_lst[0]] numif len(labels_lst) 1:for i in range(1, len(labels_lst)):for j in range(i):if labels_lst[i] labels_lst[j]:breakelse: # 第二个循环没有执行 break 时会执行 elsenum labels_lst.count(labels_lst[i])num_labels[labels_lst[i]] numresult max(num_labels, keynum_labels.get) # 获取字典中每个键对应的值并将最大值对应的键返回return resultif __name__ __main__:predict_data np.array([101, 20]) # 预测数据train_data, labels read_dataset() # 获取特征数据和标签数据train_data train_data.astype(float) # 将整数数组转换为浮点数组方便后续计算predict_data np.full((4, 2), predict_data) # 将预测数据填充为跟 train_data 有相同的维度predict_data predict_data.astype(float) # 将整数数组转换为浮点数组方便后续计算dist calculate_distance(predict_data, train_data) # 计算距离result select_best_result(dist, labels, k1) # 选取最好的结果print(result)
---------
action海伦约会
海伦女士一直使用在线约会网站寻找适合自己的约会对象她会将接触过的人按以下方式进行分类
没有魅力的人魅力一般的人魅力十足的人
海伦已经收集了一段时间的约会数据她把这些数据存放在一个文本文件中一共有 1000 个样本数据每个样本数据包含以下三种特征
每年获得的飞行常客里程数玩视频游戏所消耗的时间百分比每周消费的冰淇淋公升数
数据集中存放的数据格式如下图所示 我们将使用 KNN 模型对其进行分析并预测完整代码如下所示
import numpy as np
import pandas as pd# 读取数据集将数据集划分成训练集和测试集并划分特征数据和标签数据同时将标签进行相应转换以方便后续处理
def read_dataset():df pd.read_table(rD:\MachineLearning\dating_set.txt, headerNone) # 读取数据集共 1000 个样本data df.iloc[:, :] # 获取数据集的第 1、2、3、4 列数据train_for_data data.sample(frac0.9) # 从原始数据 data 中随机选择 90% 的数据作为训练集test_for_data data.drop(train_for_data.index) # 从原始数据 data 中提取剩下的 10% 数据作为测试集train_for_data train_for_data.to_numpy() # 将 pandas.core.frame.DataFrame 转为 numpy.ndarraytest_for_data test_for_data.to_numpy() # 将 pandas.core.frame.DataFrame 转为 numpy.ndarraytrain_data train_for_data[:, :3] # train_for_data 的第 1、2、3 列为训练集的特征数据train_labels train_for_data[:, -1] # train_for_data 的第 4 列为训练集的标签数据test_data test_for_data[:, :3] # test_for_data 的第 1、2、3 列为训练集的特征数据test_labels test_for_data[:, -1] # test_for_data 的第 4 列为训练集的标签数据label_mapping {didntLike: 1, smallDoses: 2, largeDoses: 3} # 建立能将字符串标签映射成数字标签的字典train_labels np.array([label_mapping[label] for label in train_labels]) # 将字符串标签转换成数字标签test_labels np.array([label_mapping[label] for label in test_labels]) # 将字符串标签转换成数字标签return train_data, test_data, train_labels, test_labels# 归一化
def normalize(train_data, test_data):for i in range(train_data.shape[1]):arr train_data[:, i] # 一列特征数据max_value arr.max() # 最大值min_value arr.min() # 最小值arr (arr - min_value) / (max_value - min_value) # 归一化计算train_data[:, i] arrfor i in range(test_data.shape[1]):arr test_data[:, i] # 一列特征数据max_value arr.max() # 最大值min_value arr.min() # 最小值arr (arr - min_value) / (max_value - min_value) # 归一化计算test_data[:, i] arrreturn train_data, test_data# 计算距离
def calculate_distance(predict_data, train_data):dist np.sqrt(np.sum((predict_data - train_data) ** 2, axis1)) # 计算新样本数据与训练集中每一个样本数据间的距离return dist# 预测结果
def select_best_result(dist, labels, k):labels_lst [labels[index] for index in dist.argsort()[:k]] # 获取前 k 个最相似数据对应的标签# 选取前 k 个标签中出现频率最高的作为最终结果num_labels {}num labels_lst.count(labels_lst[0])num_labels[labels_lst[0]] numif len(labels_lst) 1:for i in range(1, len(labels_lst)):for j in range(i):if labels_lst[i] labels_lst[j]:breakelse: # 第二个循环没有执行 break 时会执行 elsenum labels_lst.count(labels_lst[i])num_labels[labels_lst[i]] numresult max(num_labels, keynum_labels.get) # 获取字典中每个键对应的值并将最大值对应的键返回return result# 计算错误率
def calculate_error_rate(test_result, test_labels):num_error 0for i in range(len(test_result)):if test_result[i] ! test_labels[i]:num_error 1error_rate num_error / len(test_result) * 100print(f错误率为{error_rate}%)if __name__ __main__:train_data, test_data, train_labels, test_labels read_dataset() # 获取用于训练与测试的特征数据和标签数据train_data, test_data normalize(train_data, test_data) # 将用于训练与测试的特征数据归一化train_data train_data.astype(float)test_data test_data.astype(float)num_samples train_data.shape[0] # 训练集中的样本个数行数num_features train_data.shape[1] # 训练集中的特征个数列数test_result []for i in range(len(test_data)):predict_data np.full((num_samples, num_features), test_data[i]) # 将测试数据集中的一个样本填充为跟 train_data 有相同的维度predict_data predict_data.astype(float)dist calculate_distance(predict_data, train_data) # 计算距离result select_best_result(dist, train_labels, k1) # 选取最好的结果test_result.append(result)test_result np.array(test_result)calculate_error_rate(test_result, test_labels) # 计算测试集的错误率
---------
错误率为6.0%手写数字识别
scikit learn 简称 sklearn是 Python 的一个第三方库里面包含了很多机器学习的方法借助 sklearn我们可以很快地实现一个机器学习算法。
sklearn.neighbors 模块实现了 KNN 算法其函数实现如下所示
sklearn.neighbors.KNeighborsClassifier(n_neighbors5, weightsuniform, algorithmauto, leaf_size30, p2, metricminkowski, metric_paramsNone, n_jobsNone)- n_neighbors参数 k 的值默认为 5- weights参数值可以是 uniform、distance 或用户自定义的函数默认为 uniformuniform 表示均等的权重即所有邻近点的权重都是相等的distance 表示不均等的权重距离近的点要比距离远的点的影响大用户自定义的函数接收距离数组并返回维数相同的权重- algorithm用于计算最近邻的算法默认使用 auto 方式即根据传递给拟合方法的值决定最合适的算法除此外还可以指定 ball_tree、kd_tree、brute 等方式进行最近邻的计算brute 是暴力搜索当训练集很大时计算非常耗时kd_tree 是数据结构中的二叉树构造的 kd 树可以方便地对存储数据进行快速检索在数据维度小于 20 时效率高ball_tree 是为了克服 kd 树高维失效而构建的其以质心和半径分割样本空间每个节点都是一个超球体- leaf_size传递给 ball_tree 或 kd_tree 的大小默认为 30该参数的设置会影响树的构建速度、查询速度以及存储树所需的内存最佳取值取决于问题的性质- p闵可夫斯基距离度量的幂参数当 p1 时相当于使用曼哈顿距离 l1当 p2 时相当于使用欧几里得距离 l2对于任意 p 值则使用闵可夫斯基距离minkowski distance- metric距离度量默认为 minkowski闵可夫斯基距离也被称为闵式距离它将多个距离公式曼哈顿距离、欧式距离、切比雪夫距离总结成了一个公式- metric_params距离公式的其他关键参数这个可以不管使用默认的 None 即可- n_jobs搜索邻近点时的并行工作数默认为 1如果为 -1则表示 CPU 的所有 Cores 都用于并行工作由 KNeighborsClassifier 创建的实例对象 neigh 具有以下方法
fit(X, y) # 根据训练集拟合 k 近邻分类器- X训练数据形状为 (n_samples, n_features)- y目标值训练样本对应的标签形状为 (n_samples,)返回拟合的 k 近邻分类器get_params(deepTrue) # 以字典形式返回 KNeighborsClassifier 类的参数- deep布尔值默认为 True返回 {algorithm: auto, leaf_size: 30, metric: minkowski, metric_params: None, n_jobs: None, n_neighbors: 3, p: 2, weights: uniform}kneighbors(XNone, n_neighborsNone, return_distanceTrue) # 给定一个样本和一个查询集查找该样本在查询集中的 k 个近邻- X训练数据或者说是查询数据形状为 (n_samples, n_features)- n_neighbors查找的近邻数量 k默认值为传给构造函数的值- return_distance布尔值表示是否返回距离默认为 True返回形状为 (n_samples, n_features) 的距离当 return_distanceTrue 时才会返回以及对应的形状为 (n_samples, n_features) 的索引predict(X) # 预测所提供数据的类别标签- X预测数据形状为 (n_samples, n_features)以 np.ndarray 形式返回形状为 (n_samples,) 的每个数据样本的类别标签predict_proba(X) # 返回预测数据 X 在各类别标签中所占的概率- X预测数据形状为 (n_samples, n_features)返回该样本在各类别标签中的预测概率类别标签按词典顺序排列比如对于 [1. 0. 0. 0. 0. 0. 0. 0. 0. 0.] 这个结果样本识别为数字 0 的概率为 1类别标签从 0 到 9 依次排列score(X, y, sample_weightNone) # 返回预测结果和标签之间的平均准确率- X预测数据形状为 (n_samples, n_features)- y预测数据的目标值真实标签- sample_weight默认为 None返回预测数据的平均准确率相当于先执行了 self.predict(X)而后再计算预测值和真实值之间的平均准确率我们知道手写数字图像是大小为 32×32 的二进制图像为了方便计算我们可以将其转换为 1×1024 的向量。在 KNeighborsClassifier 函数中输入可以是矩阵不过为了跟自己写的 KNN 算法对应上这里也做了向量化处理。完整的手写数字识别 KNN 模型代码实现如下
import os
import numpy as np
import pandas as pd
from sklearn.neighbors import KNeighborsClassifier# 将 (32, 32) 的矩阵转换成 (1, 1024) 的向量
def mat_to_vector(file: str) - np.ndarray:df pd.read_table(file, headerNone)df df.to_numpy()vec np.zeros((1, df.shape[0] * df.shape[0])) # (1, 1024)with open(file, r) as f:rows f.readlines() # 读取文件中的所有行并以列表形式返回for i in range(len(rows)):row rows[i].strip() # 读取列表中的一个字符串元素columns [int(row[i:i1]) for i in range(len(row))] # 将字符串分割成单个数字并以列表形式返回for j in range(len(columns)):vec[0, 32 * i j] int(columns[j]) # 将每一个数字赋值给向量 vec 对应的位置return vec# 读取训练集
def read_train_dataset(path: str) - (np.ndarray, np.ndarray):train_labels [] # 用于存储手写数字图像对应的数字标签train_files os.listdir(path) # 读取所有二进制图像文件并以列表形式返回df pd.read_table(os.path.join(path, train_files[0]), headerNone)df df.to_numpy()m len(train_files) # 1934train_mat np.zeros((m, df.shape[0] * df.shape[0])) # (1934, 1024)for i in range(m):train_file_name train_files[i]digit int(train_file_name.split(_)[0])train_labels.append(digit) # 将每一个图像文件对应的数字标签存储到列表train_mat[i, :] mat_to_vector(os.path.join(path, train_files[i])) # 将每一个 (1, 1024) 的二进制图像数据赋值到矩阵train_labels np.array(train_labels)return train_mat, train_labels# 读取测试集
def read_test_dataset(path: str) - (np.ndarray, np.ndarray):test_labels [] # 用于存储手写数字图像对应的数字标签test_files os.listdir(path) # 读取所有二进制图像文件并以列表形式返回df pd.read_table(os.path.join(path, test_files[0]), headerNone)df df.to_numpy()m len(test_files) # 946test_mat np.zeros((m, df.shape[0] * df.shape[0])) # (946, 1024)for i in range(m):test_file_name test_files[i]digit int(test_file_name.split(_)[0])test_labels.append(digit) # 将每一个图像文件对应的数字标签存储到列表test_mat[i, :] mat_to_vector(os.path.join(path, test_files[i])) # 将每一个 (1, 1024) 的二进制图像数据赋值到矩阵test_labels np.array(test_labels)return test_mat, test_labels# 构建 KNN 模型
def knn_model(train_data: np.ndarray, train_labels: list) - object:neigh KNeighborsClassifier(n_neighbors3)neigh.fit(train_data, train_labels)return neighif __name__ __main__:train_path rD:\MachineLearning\trainingDigitstest_path rD:\MachineLearning\testDigitstrain_data, train_labels read_train_dataset(train_path) # 读取训练数据并返回训练集和对应标签neigh knn_model(train_data, train_labels) # 构建 KNN 模型并返回 KNN 对象test_data, test_labels read_test_dataset(test_path) # 读取测试数据并返回测试集和对应标签result neigh.predict(test_data) # 预测结果并以 np.ndarray 形式返回result_lst (result - test_labels).tolist() # 将数组转成列表error_rate (len(result_lst) - result_lst.count(0)) / len(result_lst) * 100 # 计算错误率print(f错误率为{error_rate}%)训练集和测试集的文件格式如下图所示第一个数字为该二进制图像文件对应的数字标签 文件中存储的数据格式如下图所示 KNN 算法的优缺点
优点
简单直观KNN 是一种非参数化算法不需要假设数据的分布情况。它通过比较实例之间的距离来进行分类或回归易于理解和实现。适用于多类别问题KNN 可以处理多类别问题不受类别数量的限制。对异常值不敏感由于 KNN 根据最近的邻居进行分类或回归异常值对结果的影响较小。模型可以随时更新当新的训练样本加入时可以很容易地对模型进行更新而无需重新进行训练。
缺点
高计算复杂度在预测时需要计算测试样本与所有训练样本之间的距离因此随着训练集规模的增大计算复杂度也会增加。这可能导致 KNN 在大型数据集上的效率低下。对特征尺度敏感如果特征之间的尺度差异很大那么在计算距离时尺度较大的特征会主导结果从而忽略了其他特征的影响。因此在使用 KNN 之前需要对数据进行特征缩放。需要确定 K 值KNN 算法中的 K 值表示选择多少个最近邻居来进行决策。选择不同的 K 值可能会对结果产生不同的影响而且没有明确的准则可以确定最佳的 K 值需要通过交叉验证或其他方法进行调优。类别不平衡问题当训练集中某个类别的样本数远远多于其他类别时KNN 可能会偏向于占主导地位的类别。
综上所述KNN 算法简单直观对异常值不敏感适用于多类别问题并且可以随时更新模型。然而它的计算复杂度高对特征尺度敏感需要确定 K 值并且对类别不平衡问题比较敏感。在实际应用中需要权衡这些因素并根据具体问题的特点选择合适的机器学习算法。
