KNN算法

一、KNN算法介绍

KNN 算法，也称 k邻近算法，是 有监督学习 中的 分类算法 。它可以用于分类或回归问题，但它通常用作分类算法。

二、KNN算法流程

1.计算已知类别数据集中的点与当前点的距离

2.按照距离增次序排序

3.选取与当前点距离最小的k个点

4.确定前k个点所在类别的出现频率

5.返回前k个点出现频率最高的类别作为当前点的预测分类

三、K的取值

K取太小分类结果易被噪声影响，预测结果破碎

四、过拟合和欠拟合

过拟合：模型训练太好，将早点也归为一般性质，泛化性下降，不会举一反三

欠拟合：样本的一般性尚未完好

五、归一化

计算两个样本之间的距离时，数字查值最大的属性对计算结果的影响最大，为了处理不同取值范围的特征值，使各个属性的权重相等，我们将数值归一化，下列公式可以将数值归一化到0-1之间：

$newValue = (oldValue - min)/min-max$

六、基于K近邻算法的分类器的实现

1.问题引入

海伦一直使用在线约会网站寻找适合自己的约会对象。她曾交往过三种类型的人：

不喜欢的人
一般喜欢的人
非常喜欢的人

这些人包含以下三种特征

每年获得的飞行常客里程数
玩视频游戏所耗时间百分比
每周消费的冰淇淋公升数

该网站现在需要尽可能向海伦推荐她喜欢的人，需要我们设计一个分类器，根据用户的以上三种特征，识别出是否该向海伦推荐。

2.需求概要分析

根据问题，我们可知，样本特征个数为3，样本标签为三类。现需要实现将一个待分类样本的三个特征值输入程序后，能够识别该样本的类别，并且将该类别输出。

3.程序结构设计说明

根据问题，可以知道程序大致流程如下。

其中输入数据应包含三个值，输出应为喜欢，一般，不喜欢，三个中的一个。

4、K近邻算法的一般流程

数据准备：这包括收集、清洗和预处理数据。预处理可能包括归一化或标准化特征，以确保所有特征在计算距离时具有相等的权重。

玩视频游戏所耗时间百分比每年获得的飞行常客里程数每周消费的冰淇淋的公升数样本分类

我们很容易发现，当计算样本之间的距离时数字差值最大的属性对计算结果的影响最大，也就是说，每年获取的飞行常客里程数对于计算结果的影响将远远大于上表中其他两个特征-玩视频游戏所耗时间占比和每周消费冰淇淋公斤数的影响。而产生这种现象的唯一原因，仅仅是因为飞行常客里程数远大于其他特征值。但海伦认为这三种特征是同等重要的，因此作为三个等权重的特征之一，飞行常客里程数并不应该如此严重地影响到计算结果。

在处理这种不同取值范围的特征值时，我们通常采用的方法是将数值归一化，如将取值范围处理为０到１或者-１到１之间。下面的公式可以将任意取值范围的特征值转化为０到１区间内的值：

选择距离度量方法：确定用于比较样本之间相似性的度量方法，常见的如欧几里得距离、曼哈顿距离等。

确定K值：选择一个K值，即在分类或回归时应考虑的邻居数量。这是一个超参数，可以通过交叉验证等方法来选择最优的K值。

找到K个最近邻居：对于每一个需要预测的未标记的样本：

计算该样本与训练集中所有样本的距离。

根据距离对它们进行排序。

选择距离最近的K个样本

预测：

对于分类任务：查看K个最近邻居中最常见的类别，作为预测结果。例如，如果K=3，并且三个最近邻居的类别是[1, 2, 1]，那么预测结果就是类别1。

对于回归任务：预测结果可以是K个最近邻居的平均值或加权平均值。

评估：使用适当的评价指标（如准确率、均方误差等）评估模型的性能。

优化：基于性能评估结果，可能需要返回并调整某些参数，如K值、距离度量方法等，以获得更好的性能。

5.算法实现

data_loader.py：加载数据，归一化处理

首先，从指定文件中读取数据，将前三列（特征）转换为浮点数并存储为 NumPy 数组，最后一列（标签）存储为字符串数组。

normalize_data 函数对特征数据进行归一化处理，将每列的值缩放到 [0, 1] 区间，以便后续计算。最终，代码返回归一化后的特征数据、每列的范围和最小值。

import numpy as np
import osdef load_data(filename):if not os.path.exists(filename):raise FileNotFoundError(f"文件 {filename} 不存在！")# 读取文件内容with open(filename, 'r') as file:lines = file.readlines()# 初始化特征和标签列表features = []labels = []# 解析每一行for line in lines:parts = line.strip().split('\t')# 前三列是特征，转换为浮点数features.append([float(parts[0]), float(parts[1]), float(parts[2])])# 最后一列是标签，保留为字符串labels.append(parts[3])# 转换为 NumPy 数组features = np.array(features)labels = np.array(labels)return features, labelsdef normalize_data(features):min_vals = features.min(axis=0)max_vals = features.max(axis=0)ranges = max_vals - min_valsnorm_features = (features - min_vals) / rangesreturn norm_features, ranges, min_vals

`knn_algorithm.py`实现 KNN 算法

euclidean_distance 函数计算两个样本之间的欧几里得距离。

knn_classify 函数对测试样本进行分类：它计算测试样本与每个训练样本的距离，按距离排序后选择距离最近的 k 个邻居，统计这些邻居的标签，并返回出现次数最多的标签作为预测结果。

import numpy as np
from collections import Counter
import mathdef euclidean_distance(x1, x2):return math.sqrt(np.sum((x1 - x2) ** 2))def knn_classify(test_data, train_data, train_labels, k):distances = []for i in range(len(train_data)):distance = euclidean_distance(test_data, train_data[i])distances.append((distance, train_labels[i]))# 按距离排序distances.sort(key=lambda x: x[0])# 选择前k个最近邻居k_nearest_neighbors = distances[:k]# 统计k个邻居的类别k_nearest_labels = [neighbor[1] for neighbor in k_nearest_neighbors]most_common = Counter(k_nearest_labels).most_common(1)return most_common[0][0]

`tester.py`负责测试模型的性能

根据 test_ratio 划分测试集和训练集，然后对每个测试样本调用 knn_classify 函数进行分类，并比较预测结果与实际标签。如果预测错误，则增加错误计数。最后，计算并返回测试集的错误率，同时打印每个测试样本的预测结果和实际结果。

from knn_algorithm import knn_classifydef test_knn(norm_features, labels, k, test_ratio=0.1):num_test_samples = int(len(norm_features) * test_ratio)error_count = 0.0for i in range(num_test_samples):# 使用KNN进行分类predicted_label = knn_classify(norm_features[i], norm_features[num_test_samples:], labels[num_test_samples:], k)# 打印预测结果和实际结果print(f"测试样本 {i + 1}: 预测结果: {predicted_label}, 实际结果: {labels[i]}")if predicted_label != labels[i]:error_count += 1.0# 计算错误率error_rate = error_count / num_test_samplesprint(f"测试集错误率: {error_rate}")return error_rate

`main.py`主程序，负责调用其他模块的功能

首先加载数据并进行归一化处理，然后测试 KNN 模型的性能，计算测试集的错误率。接着，程序提示用户输入新样本的特征值，将其归一化后使用 KNN 算法进行分类，并输出预测结果。如果数据文件不存在，程序会捕获并提示文件未找到的错误。

import numpy as np  # 添加 numpy 导入
from data_loader import load_data, normalize_data
from knn_algorithm import knn_classify
from tester import test_knndef classify_new_sample(norm_features, labels, ranges, min_vals, k):# 输入新样本的特征值print("请输入待分类样本的三个特征值：")flight_miles = float(input("每年获得的飞行常客里程数："))game_time = float(input("玩视频游戏所耗时间百分比："))ice_cream = float(input("每周消费的冰淇淋公升数："))# 将输入的特征值归一化new_sample = np.array([flight_miles, game_time, ice_cream])  # 使用 np.arraynew_sample_norm = (new_sample - min_vals) / ranges# 使用KNN进行分类predicted_label = knn_classify(new_sample_norm, norm_features, labels, k)# 输出分类结果print(f"新样本的分类结果: {predicted_label}")if __name__ == "__main__":# 文件路径filename = r'E:\University\2xia\MachineLearning\pythonProject1\datingTestSet.txt'try:# 加载数据features, labels = load_data(filename)# 归一化处理norm_features, ranges, min_vals = normalize_data(features)# 设置K值k = 3# 测试KNN模型print("开始测试KNN模型...")test_knn(norm_features, labels, k)# 分类新样本print("\n开始分类新样本...")classify_new_sample(norm_features, labels, ranges, min_vals, k)except FileNotFoundError as e:print(e)