1-概率与学习-KNN

1. 回顾

1.1. 特征和属性

统计学角度看机器学习：得到映射函数

将原始数据通过特征工程（手工/自动）得到特征向量x,再求映射函数，得到标签y
属性：特征向量的每个维度

1.2. 分类问题和回归问题

分类：输出离散值，找到一个决策边界
回归：输出连续值

1.3. 距离度量/相似性度量

[[0-introduction#3.2. 距离度量函数]]

机器学习中大多是向量运算。

2. k-近邻分类器

2.1. 算法流程👍

1. 计算测试样本和中的训练样本之间的距离
2. 对所有距离值（相似度）进行升序（降序）排序
3. 选择k个最邻近（距离最小，相似度最高）的训练样本
4. 采取投票法，将近邻中样本数最多的标签分配给

2.2. k的影响

• k一般是奇数，避免平局
• k不同取值，结果不同
• k太小，对噪声敏感，模型整体变得复杂，容易过拟合
• k太大，对噪声不敏感，模型整体变得简单，容易欠拟合

3. 最近邻分类器

3.1. 算法流程

k近邻的简化，选取最近的一个

1. 计算测试样本和中的训练样本之间的距离
2. 对所有距离值（相似度）进行升序（降序）排序
3. 选择最近的那个训练样本
4. 标签分配给

3.2. 泛化错误率

虽然简单，但错误率不超过贝叶斯分类器的两倍

4. k-近邻回归

4.1. 算法流程👍

1. 计算测试样本和中的训练样本之间的距离
2. 对所有距离值（相似度）进行升序（降序）排序
3. 选择k个最邻近（距离最小，相似度最高）的训练样本
4. 将距离值倒数作为权重，然后求k个最近邻的标签加权平均，作为的预测值

和分类器主要区别在于回归输出是连续值。

4.2. 近邻平滑

加权平均plus，得到很好的回归模型。

• 核平滑法
  • 二次核
  • 次方核
  • 高斯核

4.3. 讨论

• k-NN是典型的“懒惰学习”(lazy)
  • 训练阶段仅仅把数据收集起来，训练开销时间为零，带收集到测试样本后再开始处理
• KVM、CNN是典型的“急切学习”(eager learning)
  • 训练开销很大，但是测试时可以直接运行。尝试在训练阶段构造一个通用的、与输入无关的目标函数。

4.3.1. 优缺点

• 优点：
  • 精度高
  • 对异常值不敏感（k取值不一样，设置更大的k可以减少异常值的影响）
  • 无数据输入假定（无训练阶段）
• 缺点
  • 计算复杂度高
  • 空间复杂度高

4.3.2. 时间复杂度

假设是欧氏距离，时间复杂度
训练阶段：
测试阶段：

Top k问题时间复杂度：

algorithm - Find the top K elements in O(N log K) time using heaps - Stack Overflow

What would be the time complexity to find top K elements in an unsorted array of size N using MaxHeap (of size N) and MinHeap (of size K) and which one would be more efficient? - Quora

5. 降低近邻计算

• 维度2-5：维诺图
• 维度6-30：KD-Tree
• 高维特征：
  • 降维算法：如PCA
  • 近似最邻近（ANN）
  • 哈希

5.1. 维诺图

根据一组给定的目标，将一个平面分成靠近每一个目标的多个区块。

维诺单元定义
假设X是一个点集

5.1.1. 查询测试

5.2. KD-Tree

对K维空间中的实例点进行存储一便对其快速检索的树状数据结构

KD树是二叉树，表示对k维空间的一个划分。

Introduction to K-D Trees | Baeldung on Computer Science

5.2.1. 构造

5.3. 降维

5.4. 近似最近邻ANN

flann

5.5. 哈希

• 把任意长度的输入映射成固定长度的输入

概率化的k-NN