多维缩放(MDS)
多维缩放(multidimensional scaling ,MDS)，是另外一种线性降维方式，与主成分分析法不同的是，多维缩放的目标不是保留数据的最大可分性，而是更加关注高维数据内部的特征。多维缩放算法集中于保留高维空间中的“相似度”信息，而在一般的问题解决的过程中，这个“相似度”通常用欧式距离来定义
- 多维缩放方法要求原始空间的样本之间的相似度在低维空间中得以保持，即原始空间的样本之间的距离与在低维空间中的距离相同
给定一个的样本集合
设样本之间的距离矩阵为
，其第
行第
列元素
表示样本
与
之间的距离。假设降维到低维空间后对应为低维空间中的为
令
，即
是
的内积矩阵，
，多维缩放的目的是保证降维前后样本间距相等即
，则有
不妨设降维后样本已被中心化，即
，矩阵第列的和为
%5C%5C%0A%26%3D0%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0A%5Csum%7Bi%3D1%7D%5ENb%7Bij%7D%26%3D%5Csum%7Bi%3D1%7D%5ENZ_i%5ETZ_j%5C%5C%0A%26%3D%5Csum%7Bi%3D1%7D%5EN%5Csum%7Bk%3D1%7D%5Eqz%7Bik%7Dz%7Bjk%7D%5C%5C%0A%26%3D%5Csum%7Bk%3D1%7D%5Eqz%7Bjk%7D%5Cleft%28%5Csum%7Bi%3D1%7D%5ENz_%7Bik%7D%5Cright%29%5C%5C%0A%26%3D0%0A%5Cend%7Baligned%7D%0A&height=185&width=197)
同理矩阵第行的和
。即矩阵每行或每列的和均为零，于是距离矩阵第列的和为
%2BNb%7Bjj%7D%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0A%5Csum%7Bi%3D1%7D%5ENd%7Bij%7D%5E2%26%3D%5Csum%7Bi%3D1%7D%5ENb%7Bii%7D%2B%5Csum%7Bi%3D1%7D%5ENb%7Bjj%7D-2%5Csum%7Bi%3D1%7D%5ENb%7Bij%7D%5C%5C%0A%26%3D%5Csum%7Bi%3D1%7D%5ENb%7Bii%7D%2BNb%7Bjj%7D%5C%5C%0A%26%3Dtr%28B%29%2BNb_%7Bjj%7D%0A%5Cend%7Baligned%7D%0A&height=131&width=261)
同理距离矩阵第行的和为
%2BNb%7Bii%7D%0A#card=math&code=%5Csum%7Bj%3D1%7D%5ENd%7Bij%7D%5E2%3Dtr%28B%29%2BNb%7Bii%7D%0A&height=55&width=160)
距离矩阵所有元素的和为
%2BNb%7Bii%7D)%5C%5C%0A%26%3D%5Csum%7Bi%3D1%7D%5ENtr(B)%2BN%5Csum%7Bi%3D1%7D%5ENb%7Bii%7D%5C%5C%0A%26%3D2Ntr(B)%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0A%5Csum%7Bi%3D1%7D%5EN%5Csum%7Bj%3D1%7D%5ENd%7Bij%7D%5E2%26%3D%5Csum%7Bi%3D1%7D%5EN%28tr%28B%29%2BNb%7Bii%7D%29%5C%5C%0A%26%3D%5Csum%7Bi%3D1%7D%5ENtr%28B%29%2BN%5Csum%7Bi%3D1%7D%5ENb%7Bii%7D%5C%5C%0A%26%3D2Ntr%28B%29%0A%5Cend%7Baligned%7D%0A&height=131&width=251)
又因为
%3D%5Csum%7Bi%3D1%7D%5ENb%7Bii%7D%3D%5Csum%7Bi%3D1%7D%5ENZ_i%5ETZ_i%3D%5Csum%7Bi%3D1%7D%5EN%7C%7CZi%7C%7C%5E2%0A#card=math&code=tr%28B%29%3D%5Csum%7Bi%3D1%7D%5ENb%7Bii%7D%3D%5Csum%7Bi%3D1%7D%5ENZi%5ETZ_i%3D%5Csum%7Bi%3D1%7D%5EN%7C%7CZ_i%7C%7C%5E2%0A&height=53&width=288)
令距离矩阵第行的平方和的均值为
令距离矩阵第列的平方和的均值为
令距离矩阵所有元素平方和的均值为
综上可得
%0A#card=math&code=b%7Bij%7D%3D%7B1%5Cover2%7D%28d%7Bi%5Ccdot%7D%5E2%2Bd%7B%5Ccdot%20j%7D%5E2-d%7B%5Ccdot%5Ccdot%7D%5E2-d_%7Bij%7D%5E2%29%0A&height=37&width=202)
于是我们用样本的距离矩阵求出了样本降维后对应的内积矩阵，换句话说就是如果想要让降维前后距离矩阵不变等价于降维前后的内积矩阵不变
如果对做特征值分解有
diag(%5Clambda_1%2C%5Clambda_2%2C%5Ccdots%2C%5Clambda_N)(u_1%2Cu_2%2C%5Ccdots%2Cu_N)%5ET%0A#card=math&code=B%3DU%5CLambda%20U%5ET%3D%28u_1%2Cu_2%2C%5Ccdots%2Cu_N%29diag%28%5Clambda_1%2C%5Clambda_2%2C%5Ccdots%2C%5Clambda_N%29%28u_1%2Cu_2%2C%5Ccdots%2Cu_N%29%5ET%0A&height=23&width=491)
设矩阵有
个不为零的特征值即
中有个不为零的值，那么不妨设
不为零，设
是
对应的特征向量，做如下分块可得
于是令
即满足，至此我们计算出了降维后的样本
- 但是上述推导中有存在问题，矩阵的非零特征值个数不一定比原始空间维度
小。事实上我们在使用时并不一定要求降维前后样本间距离一定相同，而是要求降维前后距离矩阵尽可能相同，根据之前推导这等价于让降维前后内积矩阵尽可能相同，那么我们可以舍弃内积矩阵较小的特征值，保证保留大部分的信息，因此实际可以选取
个大特征值，其对应的特征向量组成的矩阵和对角阵相乘即为维空间的样本
