降维——多维缩放MDS
转载自 http://blog.****.net/victoriaw/article/details/78500894
多维缩放（Multidimensional Scaling, MDS）是一组对象之间的距离的可视化表示，也可以当做一种无监督降维算法使用。
为了直观了解MDS，给一个简单例子。假设现在给定一组城市之间的距离信息如下：
现在要求绘制一幅地图，在地图中标出所有城市，并且城市之间的距离等于上表中给出的距离。显然，这种图不是唯一的，因为平移、旋转操作并不改变距离。其中一种绘制方法如下图：
MDS应用在数据降维时，基本思想和上面的例子相同：保证所有数据点对在低维空间中的距离等于在高维空间中的距离。
假设给定N个实例，可以计算出原始空间中的距离矩阵，其中第行第列的元素表示第个实例和第个实例之间的距离。现在希望把数据降维到维空间中去，得到所有样本点在中的表示，其中表示第个实例，并且任意两个实例在维空间中的距离等于原始空间中的距离。事实上，可以推导出满足此条件的解析解。
由保持距离原则可知
不失一般性，我们假设低维空间中的实例点是中心化的，即
由(2)(3)(4)可知：
定义内积矩阵，即。则
对矩阵做特征分解，得到
其中，是由B的特征值生成的对角矩阵，是特征向量作为列的矩阵。
我们希望降到维空间中，那么选择前个最大特征值及对应的特征向量，得到和，则降维后的特征表示为