全套清华大学数据分析 统计学 系列课程 03 第三章 k 近邻法 （共20页）.pptx

【清华大学大数据 数据分析 统计学 系列课程】 全套清华大学数据分析 统计学 系列课程 01 第一章 统计学习方法概论 （共32页）.pptx 全套清华大学数据分析 统计学 系列课程 02 第二章 感知机 （共28页）.pptx 全套清华大学数据分析 统计学 系列课程 03 第三章 k 近邻法 （共20页）.pptx 全套清华大学数据分析 统计学 系列课程 04 第四章 朴素贝叶斯法 （共17页）.pptx 全套清华大学数据分析 统计学 系列课程 05 第五章 决策树-2016-ID3CART （共85页）.pptx 全套清华大学数据分析 统计学 系列课程 06 第六章 Logistic回归 逻辑斯的回归与最大熵模型（共54页）.pptx 全套清华大学数据分析 统计学 系列课程 07 第七章 支持向量机 （共95页）.pptx 全套清华大学数据分析 统计学 系列课程 08 第八章 提升方法 （共58页）.pptx 全套清华大学数据分析 统计学 系列课程 09 第九章 EM算法及其推广 （共46页）.pptx 全套清华大学数据分析 统计学 系列课程 10 第十章 隐马尔科夫模型 （共50页）.pptx 全套清华大学数据分析 统计学 系列课程 11 第十一章 条件随机场 （共60页）.pptx 全套清华大学数据分析 统计学 系列课程 12 第十二章 统计学习方法总结.pptx k近邻法（K-Nearest Neighbors，简称kNN）是统计学和数据分析领域中一种基础而重要的无监督学习算法。它主要用于分类和回归任务，尤其在处理小规模或中等规模数据集时表现出色。kNN算法的核心思想是通过寻找与待分类样本最接近的k个邻居来确定样本的类别。 ### k近邻算法 1. **算法原理**： kNN算法假设数据点被分配到与之最近的k个邻居中最常见的类别。对于新的数据点，计算它与训练集中所有数据点的距离，选取距离最近的k个点，然后根据这些点的类别进行投票，选择出现频率最高的类别作为预测结果。 2. **特点**： - **优点**：kNN精度较高，对异常值不敏感，无需对数据做出任何先验假设（无数据输入假定），适合处理数值型和标称型数据。 - **缺点**：计算复杂度高，因为需要计算每个新样本与所有训练样本的距离；空间复杂度高，需要存储所有训练样本；在大规模数据集上可能不适用，尤其是在高维空间。 3. **一般流程**： - **收集数据**：可以采用各种方法获取数据。 - **准备数据**：将数据转化为适合距离计算的格式。 - **分析数据**：可以使用任何分析方法。 - **训练算法**：kNN算法不需要训练阶段。 - **测试算法**：计算错误率以评估算法性能。 - **使用算法**：输入新数据，计算其与训练数据的相似性，根据kNN规则进行分类。 ### k近邻模型 - **模型**：kNN模型依赖于距离度量来确定邻居。 - **距离度量**：常用的距离度量包括欧氏距离、曼哈顿距离、L∞距离等。欧氏距离是最直观的距离，适用于各维度同等重要的情况；曼哈顿距离考虑了各维度的绝对差异；L∞距离则关注最大维度差异。 - **k值的选择**：k值的选择直接影响模型的复杂性和泛化能力。较小的k值可能导致过拟合，对噪声敏感；较大的k值能降低估计误差，但可能导致模型过于简单，可能欠拟合。通常，k取值在1到20之间。 - **分类决策规则**：多数表决规则是最常见的决策规则，即选择k个邻居中出现最多的类别作为新样本的分类。 ### k近邻法的实现：kd树 - **kd树**：是一种针对K维数据的空间分割数据结构，用于高效地存储和检索K维空间中的对象。kd树是一种二叉树，每个节点代表一个k维超矩形区域。 - **构造kd树**：通过不断沿着坐标轴进行切分，将K维空间划分为一系列超矩形区域。这样可以在O(log k)的时间复杂度内完成最近邻搜索。 - **搜索kd树**：通过递归遍历kd树，每次沿着当前轴方向找到最近的边界，直到达到叶子节点。然后回溯并检查其他可能的近邻。 在实际应用中，kNN算法与kd树结合可以显著提高高维数据的检索效率，但同时也需要权衡计算复杂性和存储需求。在处理大数据集时，还可以考虑使用其他数据结构或算法优化，如球树（ball tree）或基于质心的方法来提高效率。此外，k值的选择、距离度量方式以及异常值处理策略也是kNN算法性能的关键因素。