特征抽取 多维尺度分析MDStype
status
date
slug
summary
tags
category
icon
password
Property
原理
MDS基本原理
给定个维的样本数据：
这个样本之间的欧式距离可以表示成如下的矩阵：
是样本和样本之间的欧式距离，有：
MDS的基本原理是在一个低维的空间中，将个物体嵌入到该空间中，使得彼此间的相似度尽可能地保留。如果这个低维的空间是2维或者3维，则可以画出该个物体的可视化结果。
假设将这个样本映射到新的维空间中，映射成的矩阵形式如下：
其中，一般取2或3。通常，计量多元尺度法（Metric MDS）是最小化如下的目标函数：
欧式距离，可以被任意旋转和变换，因为这些变换不会改变样本间的距离。所以对于，解不唯一。
基本的最优化理论
假设待优化的函数有最优的最小解，但是直接求解的解析解是非常困难的。因此可以找一个简单的，更容易求解最优值的函数 来代替求解，满足如下条件：
对于任意的有：
其中是一个固定点，并且必须“着陆”于，即必须满足如下条件：
假设是最小值，则，又因为是最小值，则有，所以可以得到如下的一个不等式链：
经过函数， 朝着下降的”方向”走去( )。
若反复迭代，则会找到函数的一个局部最小值，若是凸函数，则会找到的最小值。
该优化方法的迭代流程如下：
- 选择一个初始值，找到一个函数使得满足： 和
- 第步，求解函数，得到最小值
- 如果，则结束， 的最优值是；否则，令，转到步骤(2)
柯西-施瓦茨不等式
在寻找函数的时候，会用柯西-施瓦茨不等式：
不等式成立的条件是：
其中，柯西-施瓦茨不等式可以化成如下的形式：
证明：
考虑一个一元二次方程：
转化形式如下
很显然，该方程要不没有实数解，要不就是有重根，所以其判别式，有：
所以 成立。
当该方程是重根时，，即
有公式成立。
Basic SMACOF methodology
将公式 展开，拆成3部分：
观察公式有：
是一个常数项，对目标函数优化没有影响。
是一个凸的二次函数，有最小值。
第三项，根据柯西-施瓦茨不等式，可以得知其有界：
其中是常数。当时，上述不等式变成等式，符合优化理论，可得到：
则根据优化理论，迭代可求解得到的最优解。
为了便于优化，可以将公式转化成矩阵的形式，设：
对于公式中的，有：
其中， ， ， 则其他地方等于0。则
其中，tr是矩阵的迹。矩阵是函数的海森矩阵，其形式如下：
对于，有：
其中
则
综上，
根据前面公式得：
至此，可以优化来迭代求解
求解得：
其中， 是的广义逆
代码
