24.1 k近邻学习 - 维数危机k近邻学习 (k-Nearest Neighbor简称kNN) 是一种常用的监督学习方法其工作机制非常简单给定测试样本基于某种距离度量找出训练集中与其距离最近的k个训练样本然后基于这k个近邻的信息来进行预测。通常在分类任务中可使用投票法在回归任务中可使用平均法​还可基于距离远近进行加权投票或加权平均距离越近的样本权重越大。k近邻学习有一个明显的不同之处它似乎没有训练过程k是一个重要参数当k取不同值时分类结果会有显著不同。另一方面若采用不同的距离计算方式找出的近邻可能有显著差别也会导致分类结果有显著不同。k近邻学习基于一个重要假设任意测试样本x在其附近任意小的δ距离范围内总能找到一个训练样本 (例如若δ0.001仅考虑单个属性则需1000个样本点平均分布在归一化后的属性取值范围内可使任意测试样本在其附近0.001距离范围内总能找到一个训练样本)即训练样本的采样密度足够大或称为密采样(dense sample) -- 此时近邻分类器的错误率不超过贝叶斯最优分类器的错误率的两倍。然而这仅是属性维数为1的情形若有更多的属性例如属性维数为20若要求样本达到密采样(及错误率)的条件至少需1000^2010^60个样本这个条件在现实应用中通常很难满足且现实任务中属性维数如果成千上万则满足密采样条件所需的样本数目更是无法达到的天文数字 -- 高维空间出现的数据样本稀疏、距离计算困难等问题维数危机。24.2 降维缓解维数危机的一个重要途径是降维(dimension reduction)即通过某种数学变换将原始高维属性空间转变为一个低维子空间(subspace)在这个子空间中样本密度大幅提高距离计算也变得更为容易。为什么能进行降维这是因为在很多时候人们观测或收集到的数据样本虽是高维属性的但与学习任务密切相关的数据内在规律很可能仅是一个低维分布。如下图所示给出了一个直观的例子原始高维空间中的样本点在这个低维子空间中更容易进行学习。24.3 MDS降维方法若要求原始高维空间中样本之间的距离 (代表数据分布的内部规律) 在低维空间中得以保持即得到多维缩放 (Multiple Dimensional Scaling简称MDS)算法 ​[Cox and Cox,2001]这是一种经典的降维方法。MDS算法如下24.3.1 算法解读MDS算法解读如下假定m个样本在原始d维空间的距离矩阵为 D∈Rm×m其第i行j列的元素distij为样本xi到xj的距离。目标是获得样本在d低维空间的表示Z∈Rd′×m且任意两个样本在d′低维空间中的欧氏距离等于原始空间中的距离即‖zi-zj‖ distij。令BZᵀZ(Rd′×m)ᵀ(Rd′×m)∈Rm×m其中B为降维后样本的内积矩阵bijziᵀzj则有distij^2 ‖zi-zj‖^2 ‖zi‖^2 ‖zj‖^2 - 2ziᵀzj biibjj-2bij令降维后的样本Z被中心化即Σ(i1,m)zi0则矩阵B的行之和、列之和均为零即Σ(i1,m)bij Σ(j1,m)bij 0。Σ(i1,m)distij^2 Σ(i1,m)bii mbjj tr(B) mbjjΣ(j1,m)distij^2 Σ(j1,m)bjj mbii tr(B) mbiiΣ(i1,m)Σ(j1,m)distij^2 Σ(i1,m)tr(B) Σ(i1,m)mbii 2mtr(B)其中tr(B) Σ(i1,m)bii 表示矩阵的迹(trace)。即disti·^2 (1/m)tr(B)biidist·j^2 (1/m)tr(B)bjjdist··^2 (2/m)tr(B)则有 :bij -(1/2)(distij^2-bii-bjj) -(1/2)(distij^2 -disti·^2 -dist·j^2 dist··^2)得出降维后样本的内积矩阵B内元素 bij 与样本之间的距离 distij 的对应关系由此即可通过降维前后样本之间距离保持不变的距离矩阵D求取内积矩阵B。对内积矩阵B做特征值分解(eigenvalue decomposition)BVΛVᵀ其中Λdiag(λ1, λ2, ..., λd)为特征值构成的对角矩阵 (λ1≥λ2≥...≥λd)V为相应的特征向量矩阵。假定其中有d*个非零特征值构成对角矩阵 Λ* diag(λ1, λ2, ..., λd*)令V*表示相应的特征向量矩阵则Z可表达为在现实应用中为了有效降维往往仅需降维之后的样本距离与原始空间中的样本距离尽可能接近而不必严格相等。此时可取d≪d个最大特征值构成对角矩阵 Λdiag(λ1, λ2, ..., λd)令V表示相应的特征向量矩阵则Z可表达为24.4 引子 : 线性降维方法一般来说欲获得低维子空间最简单的方法是对原始高维空间进行线性变换。给定原始d维空间中的样本 X(x1,x2,...,xm) ∈ Rd×m变换之后得到 d≤d 维空间中的样本ZWᵀX其中 W ∈ Rd×d′是变换矩阵Z ∈ Rd′×m是样本在新空间中的表达。变换矩阵W可视为d个d维基向量ziWᵀxi 是d维向量xi与这d个d维基向量分别做内积而得到的d维向量。也就是说zi是原d维向量xi通过新坐标系{w1, w2, ..., wd′} (wi是d维向量) 转换得到的d维向量。若新坐标系是一个正交坐标系此时W为正交变换则新空间中的属性是原空间中属性的线性组合。基于线性变换进行降维的方法称为线性降维方法都符合 ZWᵀX 的基本形式不同之处是对低维子空间的性质有不同的要求相当于对W施加了不同的约束。在下一篇我们将会看到要求低维子空间对样本具有最大可分性的一种极为常用的线性降维方法。Enjoy!