降维算法

绪论、研究内容及方法、研究结果以及讨论、结论

以下全部认定数据集为而一张二维表格，每一行代表一个样本，每一列表示一个维度（属性）

高维数据并非所有维度都具有很高的价值，可能存在“无用的维度”，因为数据的获取是任意的。比如我们在研究运动员的各项生理指标以期按人种进行分类时，若样本数据集中将手的只数作为一个维度记录了下来，那么基本上所有样本在这一维度取值都相同，这体现了数据的冗余性，就可以认为该维度为一个无效的维度。但实际上不会有这种可以直接剔除的无用维度。
如何从众多维度中提取有信息价值的维度保留下来呢？PCA算法的回答是，最先被选取的维度是在其上的投影具有最大方差的维度，而之后在保证正交性之后，选取方差第二大、第三大...的维度。将高维数据集投影到这些维度，投影的值（多个维度时为投影所得的向量）就是主成分。我们将主成分与代表各维度的投影基底相乘，便得到了降维后的数据集。

简单来说：PCA的原理就是找到投影矩阵W的原理，为了使得Y=WX具有最大的方差，我们则需要W满足它是X的协方差矩阵的本征向量

PCA算法的另一种理解为SVD分解，AV = UΣ，A=UΣVT。
由极分解定理保证任何一个方阵都可以SVD分解：因为A方阵对应的算子一定可以写成一个等距同构复合一个正算子，进一步可以推广到非方阵。
从奇异值分解来理解，A可以写成r个秩一的矩阵的和，其中r为A的秩，V的每一个列向量（即A的右奇异向量）都是一个主成分，U的每一个列向量都是是主成分的对应维度的方向向量（后称为主方向）。奇异值的大小表示这个秩一矩阵的重要性。所以我们只要由大到小选取目标维数个的奇异值，以及对应的左奇异向量，就可以获得降维的数据了——即将原数据集A的转置乘以由主方向矩阵，即U（左奇异向量集），获得的就是降维后的数据的转置。

如果我们降维之后进一步的动作是进行分类任务，则在将高维数据点向低维空间投影时应该持有这样一个原则：同一类别的投影点尽可能靠近，不同类别的投影点尽可能原理。该算法对应监督学习，需要事先给出数据集标签。与PCA算法相似，该算法最终的目标是学习得到一个投影矩阵，通过该矩阵将原数据集投影至投影空间后获得降维后的数据集

通过构造优化函数瑞利商将目标实质化为求优化函数的最值。瑞利商的统计意义为，其值越大，协方差的投影越小，而均值之间的区别越大。换言之，类内差别小，类间差别大。进而转化为求投影空间

在很多情况下，数据点/样本点之间的某种度量（如欧式距离）表征了它们之间的不相似度，当我们更多地考虑数据之间不相似度时，比如在进行聚类时，我们可以尝试着在保证数据点之间的度量尽可能不发生改变的前提下，将数据集的维数降低。

设原数据集为X，其距离矩阵为D，设降维后的数据集为Z，定义内积矩阵B=ZTZ。
若要保证降维后的数据集Z的距离矩阵尽可能与X的距离矩阵相近，通过数学推导，则应当如此构成内积矩阵B：B_ij=-1/2 (D_ij^2-D_(i·)^2-D_(·j)^2+D_(··)^2 ) ，之后对矩阵B进行本征值分解B=VΛV^T，取最大的目标维数个本征值与对应的本征向量相乘即可。。（这里在文章中可以将证明写上去，有很多字的）之后对Z取一个转置就得到了降维后的数据集。

当高维数据点处于某个低维流形上时，欧式距离不再能反映全局的数据点之间的相似关系，如三维空间中的S型曲面，此时流形上的测地线距离才能客观地反应数据点之间的关系，那么我们进行数据降维应当尽可能保证任意两点之间的测地线距离不变。

一般情况下我们无法获知数据所处的流形的准确信息，并且假使知道了，测地线距离的严格计算也相当复杂，故我们采用局部欧氏距离近似的方法来获得测地线距离，这个近似不但绕开了流形获取的困难，还避开了复杂的计算。具体来说根据数据点的稠密程度选定一个最近邻个数k，并认定每个点与自己最近邻的k个点之间的测地线距离近似等于欧氏距离；而对于最近的k个点之外的其他数据点，则应全程依每个历经点的最近邻测地线距离取最短路径相连接。如此可得到一个测地线距离矩阵，接下来可以按照CMDS的方法对测地线距离矩阵进行处理，获得降维后的数据集。

其中最关键的算法流程为连接任意两点间的测地线路径，我们采用floyd算法实现。（其中很重要的一点是k近邻/kNN学习），得到的floyd矩阵的元素是对应两点通过最近邻连接得到的距离之和，是测地线距离的近似。之后将floyd矩阵当做距离矩阵代入CMDS方法，得到降维的保测地线距离的向量集。

高维数据点之间的线性表出关系体现了它们之间的结构关系，我们若重视这种关系，则应在降维后尽可能保留高维流形的几何结构。
将每一个数据点用k个近邻点线性表出，这种表出 体现的是一种几何结构，也是原本流形的局部性质。故该降维算法的目标为保持原来的流形的局部特征，也即保留每个数据点与最近邻的k个点之间的线性表出关系，使得降维后每个数据点仍然能按原来的系数通过k个近邻点表出。
我们将表出的系数称为重构系数（也称为权重因子），降维的标准是降维前后表出的重构系数尽可能相同。

该方法的原理须通过较复杂的数学推导，核心步骤是在保持k邻接局部线性嵌入（即用k近邻点线性表出）的原则上，在约束条件下（W矩阵的每一列是规范化的）通过优化权重系数矩阵W使得衡量线性表出是否准确的综量Φ取极值（，也即约束条件下的最优化问题），来获得最佳重构系数矩阵W；之后再一次利用约束条件下的优化来求降维后的数据集Z。推导过程中会用到拉格朗日乘子法，会对向量乃至矩阵求导；实现的过程中依旧需要k近邻学习。