ch6 基于实例的学习

1. 基本概念

参数化：

• 假设一个函数表达式
• 简单，很容易估计和预测
• 可能存在较高的偏差，因为真实数据可能与假设的函数表达式不匹配

非参数化：

• 基于数据得出密度分布和趋势
• 相对来说，假设比较少

基于实例的学习：

• 不构建模型，只是把训练数据存起来
• 当发现新实例时，将新实例分配给最接近的类别

2. 最邻近算法

将实例之间的相似性描述为距离，当拿到一个新实例时，计算它与每个类的距离，然后分入距离最近的类别。

错误率不小于贝叶斯学习，不大于两倍贝叶斯学习的错误率。

如果最近邻样例是噪声：

• 使用多个近邻进行投票（K 近邻算法）

3. K 近邻算法

如何计算距离：

• 闵可夫斯基距离：

  \[d(i,j) = \bigg(\sum_{k=1}^{p} |x_k(i) - x_k(j)|^{\lambda} \bigg)^{\frac{1}{\lambda}} \]

• 欧几里得距离：\(\lambda = 2\)

• 曼哈顿距离：\(\lambda = 1\)

如何描述属性：

• 需要对属性进行必要的放缩（归一化）
• 对属性进行加权

连续的输出怎么办：

• 取 \(K\) 近邻的均值

\(K\) 怎么选：

• 多数时候 \(K = 3\)，并不是 \(K\) 越大越好
• 交叉验证：将一个数据拿出来做验证，于是每个数据都可以拿出来做一次验证

一般来说，\(KNN\) 算法是比较稳定的，但是可能会出现死锁。

如何解除死锁：

• 对 \(K\) 近邻进行加权，近的邻居权重可以大一些

如何提升效率：

• 构建 \(KD\) 树，是一种空间换时间的做法。

4. KD 树

构建 \(KD\) 树：

• 选择哪一个维度进行分割：最宽的

• 选择哪一个值进行分割：选定分割维度的中位数

• 什么时候停止：设置一个点数阈值，或者设定维度的最小宽度

\(KNN\) 算法的特征：

• 概念简单，但是可以解决复杂问题
• 对噪声非常鲁棒，尤其是 \(K>1\) 时
• 容易理解
• 在训练阶段是没有信息损失的，因为所有数据都被存储起来了
• 实现简单，稳定，无参，容易做交叉验证
• 有较大的内存消耗，因为要存储所有数据
• 有较大的 CPU 消耗，对样例分类比较耗时
• 恰当的距离函数不好选择
• 无关特征可能会影响距离函数的计算

5. 距离加权的 K 近邻算法

权值函数：\(w_i = K(d(x_i, x_j))\)

加权均值：\(\sum w_i y_i / \sum s_i\)

核函数 \(K\)：\(1/d^2\)、\(e^{-d}\)、\(1/(1+d)\)...

影响因素：

• 距离函数
• 邻居数量
• 加权函数
• 拟合局部点