展开查看详情
3 .大纲 k 近邻学习 多维缩放 主成分 分析 流形学习 度量学习
4 .k 近邻学习 k 近邻学习的工作机制 k 近邻 (k-Nearest N eighbor, kNN ) 学习是一种常用的监督学习方法 : 确定训练样本，以及某种距离度量。 对于某个给定的测试样本，找到训练集中距离最近的 k 个样本，对于分类问题使用“投票法”获得预测结果，对于回归问题使用“平均法”获得预测结果。还可基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。 投票法：选择这 k 个样本中出现最多的类别标记作为预测结果。 平均法：将这 k 个样本的实值输出标记的平均值作为预测结果。
5 .“懒惰学习”与“急切学习” “懒惰学习” (lazy learning): 此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理。 “急切学习 ” (eager learning): 在训练阶段就对样本进行学习处理的方法。 K 近邻学习没有显式的训练过程，属于“懒惰学习”
6 .k 近邻分类示意图 k 近邻分类器中的 k 是一个重要参数，当 k 取不同值时，分类结果会有显著不同。另一方面，若采用不同的距离计算方式，则找出的“近邻”可能有显著差别，从而也会导致分类结果有显著不同。
7 .k 近邻学习 分析 1NN 二分类错误率 暂且假设距离计算是“恰当”的，即能够恰当地找出 k 个近邻，我们来对“最近邻分类器”（ 1NN ，即 k=1 ）在二分类问题上的性能做一个简单的讨论。给定测试样本 ，若其最近邻样本为 ，则最近邻出错的概率就是 与 类别标记不同的概率，即
8 .k 近邻学习 分析 1NN 二分类错误率 假设样本独立同分布，且对任意 和任意小正整数 ，在 附近 距离范围内总能找到一个训练样本；换言之，对任意测试样本，总能在任意近的范围内找到 中的训练样本 z 。 令 表示贝叶斯最优分类器的结果，有 最近邻分类虽简单，但它的泛化错误率不超过贝叶斯最优分类器错误率的两倍！
9 .低维嵌入 维数灾难 (curse of dimensionality) 上述讨论基于一个重要的假设：任意测试样本 附近的任意小的 距离范围内总能找到一个训练样本，即训练样本的采样密度足够大，或称为“密采样”。然而，这个假设在现实任务中通常很难满足： 若属性维数为 1 ，当 =0.001 ，仅考虑单个属性，则仅需 1000 个样本点平均分布在归一化后的属性取值范围内，即可使得任意测试样本在其附近 0.001 距离范围内总能找到一个训练样本，此时最近邻分类器的错误率不超过贝叶斯最优分类器的错误率的两倍。若属性维数为 20 ，若样本满足密采样条件，则至少需要 个样本。 现实应用中属性维数经常成千上万，要满足密采样条件所需的样本数目是无法达到的天文数字。许多学习方法都涉及距离计算，而高维空间会给距离计算带来很大的麻烦，例如当维数很高时甚至连计算内积都不再容易。 在高维情形下出现的数据样本稀疏、距离计算困难等问题，是所有机器学习方法共同面临的严重障碍，被称为“维数灾难”。
10 .低维嵌入 缓解维数灾难的一个重要途径是降维 (dimension reduction ) 即通过某种数学变换，将原始高维属性空间转变为一个低维“子空间” (subspace) ，在这个子空间中样本密度大幅度提高，距离计算也变得更为容易。 为什么能进行降维 ？ 数据样本虽然是高维的，但与学习任务 密切相关的也许仅是某个低维分布， 即高维空间中的一个 低维 “ 嵌入 ” ( embedding ) ，因而可以对数据 进行有效的降维。
11 .多维缩放 若要求原始空间中样本之间的距离在低维空间中得以保持，即得到“多维缩放” (Multiple Dimensional Scaling, MDS) ： 假定有 m 个样本，在原始空间中的距离矩阵为 ，其第 i 行 j 列的元素 为样本 到 的距离。 目标是获得样本在 维空间中的欧氏距离等于原始空间中的距离，即 令 ，其中 为降维后的内积矩阵， ，有
12 .多维缩放 为便于讨论，令降维后的样本 被中心化，即 。显然，矩阵 的行与列之和均为零，即 易知 其中 表示矩阵的迹 (trace) ， 。令 由此即可通过降维前后保持不变的距离矩阵 求取内积矩阵 :
13 .多维缩放 对矩阵 做特征值分解 (eigenvalue decomposition) ，其中 为特征值构成的对角矩阵， 在现实应用中为了有效降维，往往仅需降维后的距离与原始空间中的距离尽可能接近，而不必严格相等。此时可取 个最大特征值构成对角矩阵 ，令 表示相应的特征向量矩阵，则 可表达为 为特征向量矩阵，假定其中有 个非零特征值， 它们构成对角矩阵 ， 为特征向量矩阵。 令 表示相应的特征矩阵，则 可表达为 。
14 .设 A 是 n 阶方阵，如果数 λ 和 n 维非零列向量 x 使 关系式： A x= λx 成立 ， 则 数 λ 称为矩阵 A 特征值，非零向量 x 称为 A 的对应于特征值 λ 的特征向量 。 式 A x=λx 也可写成 ( A-λE)X=0 。这是 n 个未知数 n 个方程的齐次线性方程组，它有非零解的充分必要条件是系数 行列式 |A- λE |= 0 与
18 .线性降维方法 一般来说，欲获得低维子空间，最简单的是对原始高维空间进行线性变换。给定 维空间中的样本 ，变换之后得到 维空间中的样本 变换矩阵 可视为 个 维属性向量。换言之， 是原属性向量 在新坐标系 中的坐标向量。若 与 正交，则新坐标系是一个正交坐标系，此时 为正交变换。显然，新空间中的属性是原空间中的属性的线性组合。 基于线性变换来进行降维的方法称为线性降维方法，对低维子空间性质的不同要求可通过对 施加不同的约束来实现。 其中 是变换矩阵， 是样本在新空间中的表达。
19 .主成分分析 主成分分析 (Principal Component Analysis, 简称 PCA ) 对于 正交属性空间中的样本点，如何用一个超平面对所有样本进行恰当的表达 ？ 容易想到，若存在这样的超平面，那么它大概应具有这样的性质： 最近重构性：样本点到这个超平面的距离都足够近； 最大可分性：样本点在这个超平面上的投影能尽可能分开。 基于最近重构性和最大可分性，能分别得到主成分分析的两种等价推导。
20 .主成分的几何意义 设有 n 个样品，每个样品有两个观测变量 二维平面的散点图。 n 个样本点，无论沿着 轴方向还是 轴方向，都有较大的离散性，其离散程度可以用 或 的方差表示。 当只考虑一个时，原始数据中的信息将会有较大的损失。若将坐标轴旋转一下： 主元分析示意图
21 .主成分的几何意义 设有 n 个样品，每个样品有两个观测变量 二维平面的散点图。 n 个样本点，无论沿着 轴方向还是 轴方向，都有较大的离散性，其离散程度可以用 或 的方差表示。 当只考虑一个时，原始数据中的信息将会有较大的损失。若将坐标轴旋转一下： 主元分析示意图
22 .主成分分析 最近重构性 对样本进行中心化， ，再假定投影变换后得到的新坐标系为 ， 其中 是标准正交基向量， 若丢弃新坐标系中的部分坐标，即将维度降低到 ，则样本点在低维坐标系中的投影是 ， 是 在低维坐标下第 维的坐标，若基于 来重构 ，则会得到
23 .主成分分析 最近重构性 考虑整个训练集，原样本点 与基于投影重构的样本点 之间的距离 为 根据最近重构性应最小化上式。考虑到 是标准正交基， 是协方差矩阵，有 这就是主成分 分析的优化目标。
24 .主成分分析 最大可分性 样本点 在新空间中超平面上的投影是 ，若所有样本点的投影能尽可能分开，则应该使得投影后样本点的方差最大化。若投影后样本点的方差是 ，于是优化目标可写为 显然与 等价。
25 .主成分分析 PCA 的求解 对优化式使用拉格朗日乘子法可得 只需对协方差矩阵 进行特征值分解，并将求得的特征值排序： ，再取前 个特征值对应的特征向量构成 ，这就是主成分分析的解。
28 .主成分分析 降维后低维空间的维数 通常是由用户事先指定，或通过在 值不同的低维空间中对 k 近邻分类器（或其它开销较小的学习器）进行交叉验证来选取较好的 值。对 PCA ，还可从重构的角度设置一个重构阈值，例如 ，然后选取使下式成立的最小 值： PCA 仅需保留 与样本的均值向量即可通过简单的向量减法和矩阵 - 向量乘法将新样本投影至低维空间中。 降维虽然会导致信息的损失，但一方面舍弃这些信息后能使得样本的采样密度增大，另一方面，当数据受到噪声影响时，最小的特征值所对应的特征向量往往与噪声有关，舍弃可以起到去噪效果。
29 .核化线性降维 线性降维方法假设从高维空间到低维空间的函数映射是线性的，然而，在不少现实任务中，可能需要非线性映射才能找到恰当的低维嵌入：
热门城市
