KNN分类算法笔记

### KNN分类算法知识点 #### 一、KNN算法概述 **1.1 主要思想** KNN（K-Nearest Neighbors）分类算法是一种基于实例的学习方法，其核心思想是利用距离度量来判断未知样本与已知样本之间的相似度，从而实现分类。具体而言，假设有一个带有标签的训练数据集，对于一个新的未标记样本，KNN算法会根据该样本与训练集中各个样本之间的距离，找出最接近的K个训练样本（即K个最近邻），然后根据这K个样本的标签来预测新样本的类别。通常情况下，K是一个较小的正整数，通常不超过20。 **1.2 优缺点与适用范围** - **优点**： - **精度高**：KNN算法可以根据训练集中的大量数据来确定新样本的类别，理论上能够达到较高的分类准确率。 - **对异常值不敏感**：由于KNN算法考虑的是最近邻样本的整体特性，因此即使训练集中存在一些异常值，也不会对分类结果造成显著影响。 - **无数据输入假定**：KNN算法不需要对数据分布做出任何假设，适用于各种类型的数据。 - **缺点**： - **计算复杂度高**：对于大规模数据集，计算每个样本之间的距离是非常耗时的。 - **空间复杂度高**：需要存储整个训练数据集，在内存中占用较大空间。 - **适用数据范围**： - **数值型和标称型**：KNN算法适用于处理数值型数据（如连续值）以及标称型数据（如分类标签）。 #### 二、算法流程 **2.1 归一化** 在计算距离之前，通常需要对数据进行归一化处理，以消除不同特征之间数值差异对结果的影响。常见的归一化方法包括： - **简单缩放**（Min-max normalization）：将每个特征的值缩放到[0,1]区间内。 - **逐样本均值消减**（Mean subtraction）：从每个特征中减去该特征的平均值。 - **特征标准化**（Standardization）：使每个特征具有零均值和单位方差。 **2.2 计算距离** 计算待分类样本与训练集中每个样本之间的距离，常用的距离度量包括欧氏距离、曼哈顿距离等。 **2.3 找邻居** 找出距离最近的K个训练样本作为待分类样本的最近邻。 **2.4 做分类** 根据这K个最近邻样本的标签，采用多数表决的方式确定待分类样本的类别。 #### 三、数据归一化 **3.1 概要** 数据归一化是机器学习预处理的重要步骤之一，有助于提高算法性能并加快收敛速度。常见的归一化方法包括简单缩放、标准差标准化等。 **3.2 方法** - **简单缩放**（Min-max normalization）：将每个特征的值缩放到[0,1]区间内。计算公式为 \(x' = \frac{x - min}{max - min}\)，其中 \(x\) 是原始值，\(min\) 和 \(max\) 分别是该特征的最大值和最小值。 - **标准差标准化**（Z-score standardization）：使每个特征具有零均值和单位方差。计算公式为 \(x' = \frac{x - \mu}{\sigma}\)，其中 \(\mu\) 是样本的均值，\(\sigma\) 是样本的标准差。 **3.2.1 简单缩放** 简单缩放方法适用于特征值相对集中的情况，但若最大值和最小值不稳定，则归一化结果可能会随之波动。 **3.2.2 标准差标准化** 标准差标准化更适合需要度量距离的场景，例如在进行聚类或分类时，可以更好地反映数据间的相对距离。 #### 四、数据的距离度量和相似度度量 在数据分析和数据挖掘中，衡量个体间的差异通常涉及到距离度量和相似度度量。常用的度量方式包括： - **欧氏距离**：适用于多维空间中两个点之间的距离计算。 - **曼哈顿距离**：适用于多维空间中两点沿坐标轴方向的距离之和。 - **余弦相似度**：适用于计算两个非零向量之间的角度余弦值，用于衡量它们之间的相似度。 这些度量方法在不同的应用场景中有着各自的优势和局限性，选择合适的方法对于确保模型的有效性和准确性至关重要。