【机器学习】降维

我们日常观测或者收集到的数据来看，很多数据特征都是用不到的，而学习任务可能仅仅局限于某个低维分布（某些低维特征），这就是高维空间中的一个低维“嵌入”。数据降维，是解决数据“维数灾难”的有效手段，即通过某种数学变换将原始高维属性空间转变为一个低维的“子空间”。MDS算法（Multiple Dimensional Scaling,简称MDS）是一种行之有效的低维嵌入算法，即在保障原始空间与低维空间样本之间距离一致的前提下，将高维数据进行降维。

假设有mmm个样本，其样本空间如下： T={x1,x2,⋯,xm}xi∈RdT=\{x_1,x_2,\cdots,x_m\} \qquad x_i \in R^dT={x1​,x2​,⋯,xm​}xi​∈Rd 令DDD表示样本间的距离，其中D∈Rm×mD\in R^{m \times m}D∈Rm×m,其中第iii行jjj列的元素distijdist_{ij}distij​为样本xix_ixi​到样本xjx_jxj​之间的距离。很显然，矩阵DDD是一个对称矩阵。MDS算法的目的是在不改变样本间距离的前提下，实现数据降维，故我们最终要得到样本在d′d'd′（新样本空间）中的表示Z∈Rd′×m,d′≤dZ \in R^{d' \times m},d'\leq dZ∈Rd′×m,d′≤d,且任意两个样本在d′d'd′维空间中的欧氏距离等于原始空间中的距离，即∣∣zi−zj∣∣=distij||z_i-z_j||=dist_{ij}∣∣zi​−zj​∣∣=distij​ 令B=ZTZ∈Rm×mB=Z^TZ \in R^{m \times m}B=ZTZ∈Rm×m，其中BBB为降维后样本的内积矩阵，其中bij=ziTzjb_{ij}=z_i^Tz_jbij​=ziT​zj​，则有 distij2=∣∣zi∣∣2+∣∣zj∣∣2−2ziTzj=bii+bjj−2bij…(1)\begin{aligned} dist_{ij}^2 &=||z_i||^2+||z_j||^2-2z_i^Tz_j \\&=b_{ii}+b{jj}-2b_{ij} \qquad \qquad \dots(1)\end{aligned}distij2​​=∣∣zi​∣∣2+∣∣zj​∣∣2−2ziT​zj​=bii​+bjj−2bij​…(1)​ 为了便于讨论，令降维后的样本ZZZ被中心化，即∑i=1mzi=0\sum_{i=1}^mz_i=0∑i=1m​zi​=0,显然，矩阵BBB的行与列之和均为0，即∑i=1mbij=∑j=1mbij=0\sum_{i=1}^mb_{ij}=\sum_{j=1}^mb_{ij}=0∑i=1m​bij​=∑j=1m​bij​=0，可得如下一些变换： ∑i=1mdistij2=tr(B)+mbjj…(2)\sum_{i=1}^m dist_{ij}^2=tr(\textbf{B})+mb_{jj} \qquad \qquad \dots(2)i=1∑m​distij2​=tr(B)+mbjj​…(2) ∑j=1mdistij2=tr(B)+mbii…(3)\sum_{j=1}^m dist_{ij}^2=tr(\textbf{B})+mb_{ii} \qquad \qquad \dots(3)j=1∑m​distij2​=tr(B)+mbii​…(3) ∑i=1m∑j=1mdistij2=2m tr(B)…(4)\sum_{i=1}^m \sum_{j=1}^m dist_{ij}^2=2m \ tr(\textbf{B}) \qquad \qquad \dots(4)i=1∑m​j=1∑m​distij2​=2m tr(B)…(4) 其中tr(⋅)tr(\cdot)tr(⋅)表示矩阵的迹（trace）,tr(B)=∑i=1m∣∣zi∣∣2tr(\textbf{B})=\sum_{i=1}^m||z_i||^2tr(B)=∑i=1m​∣∣zi​∣∣2。令 disti⋅2=1m∑j=1mdistij2…(5)dist_{i\cdot}^2=\frac{1}{m}\sum_{j=1}^m dist_{ij}^2 \qquad \qquad \dots(5)disti⋅2​=m1​j=1∑m​distij2​…(5) dist⋅j2=1m∑i=1mdistij2…(6)dist_{\cdot j}^2=\frac{1}{m}\sum_{i=1}^m dist_{ij}^2 \qquad \qquad \dots(6)dist⋅j2​=m1​i=1∑m​distij2​…(6) dist⋅⋅2=1m2∑i=1m∑j=1mdistij2…(7)dist_{\cdot \cdot}^2=\frac{1}{m^2}\sum_{i=1}^m \sum_{j=1}^mdist_{ij}^2 \qquad \qquad \dots(7)dist⋅⋅2​=m21​i=1∑m​j=1∑m​distij2​…(7) 结合以上（1）~（7）可得： bij=−12(distij2−disti⋅2−dist⋅j2+dist⋅⋅2)…(8)b_{ij}=-\frac{1}{2}(dist_{ij}^2-dist_{i \cdot}^2-dist_{\cdot j}^2+dist_{\cdot \cdot}^2) \qquad \qquad \dots(8)bij​=−21​(distij2​−disti⋅2​−dist⋅j2​+dist⋅⋅2​)…(8) 由此即可通过降维前后保持不变的距离矩阵DDD求取内积矩阵BBB,又由于矩阵BBB是对阵矩阵，对其进行特征分解，即 B=VΛVTB=V\Lambda V^TB=VΛVT 其中，Λ=diag(λ1,λ2,⋯,λd)\Lambda=diag(\lambda_1,\lambda_2,\cdots,\lambda_d)Λ=diag(λ1​,λ2​,⋯,λd​)为特征值构成的对角矩阵，λ1≥λ2≥⋯≥λd\lambda_1\geq \lambda_2 \geq \cdots \geq \lambda_dλ1​≥λ2​≥⋯≥λd​,VVV为对应的特征向量矩阵。假定其中有d∗d^*d∗个非零特征值，它们构成对角矩阵Lambda∗=diag(λ1,λ2,⋯,λd∗)Lambda_*=diag(\lambda_1,\lambda_2,\cdots,\lambda_{d^*})Lambda∗​=diag(λ1​,λ2​,⋯,λd∗​),令V∗V_*V∗​表示相应的特征向量矩阵，则ZZZ可表达为： Z=Λ∗12V∗T∈Rd∗×mZ=\Lambda_*^{\frac{1}{2}}V_*^T \in R^{d^* \times m}Z=Λ∗21​​V∗T​∈Rd∗×m 在现实应用中为了有效降维，往往仅需降维后的距离与原始空间中的距离尽可能接近，而不必言格相等。此时可取d′