肥城市网站建设,创意咨询策划公司,水处理网站源码,网页制作工具有哪些局部保持投影#xff08;Locality preserving projections#xff0c;LPP#xff09;
方法概述
核心思想 有映射 Y m ∗ n f ( X d ∗ n ) \underset{m*n}{Y}f(\underset {d*n}X) m∗nYf(d∗nX)#xff0c;能够实现将d维的样本变换到m维空间之中 假设#xff1a;对…局部保持投影Locality preserving projectionsLPP
方法概述
核心思想 有映射 Y m ∗ n f ( X d ∗ n ) \underset{m*n}{Y}f(\underset {d*n}X) m∗nYf(d∗nX)能够实现将d维的样本变换到m维空间之中 假设对于一个好的降维方法在高维空间下距离近相似度高的两个点在低维空间下依旧保持相近的关系。高维空间相似度高的两个点在低维空间相似度依旧很高 考虑映射 Y W T X YW^TX YWTX即原样本空间中有 x i x_i xi与 x j x_j xj距离近 y i y_i yi 与 y j y_j yj( y i W T x i y_iW^T x_i yiWTxi)仍保持相近关系
优化目标
定义优化目标 m i n ∑ i ∑ j ∣ ∣ y i − y j ∣ ∣ 2 s i j min\sum_i \sum_j ||y_i - y_j||^2s_{ij} mini∑j∑∣∣yi−yj∣∣2sij 即在原始空间中近的点 s i j s_{ij} sij大其在降维后应该尽可能接近 y i 与 y j 距离更小 y_i与y_j 距离更小 yi与yj距离更小
方法推导
对于LPP方法有目标 a r g m i n W ∑ i ∑ j ∣ ∣ y i − y j ∣ ∣ 2 s i j \underset{W}{arg\ min} \sum_i \sum_j ||y_i- y_j||^2s_{ij} Warg mini∑j∑∣∣yi−yj∣∣2sij
对于目标 ∑ i 1 n ∑ j 1 n ∣ ∣ y i − y j ∣ ∣ 2 s i j ∑ i 1 n ∑ j 1 n ( y i T y i − y i T y j − y j T y i y j T y j ) s i j ∑ i 1 n ( ∑ j 1 n s i j ) 2 y i T y i − ∑ i 1 n ∑ j 1 n y i T y j s i j 2 ∑ i n y i T y i d i i − 2 ∑ i n ∑ j n y i T y j s i j 2 t r ( Y D Y T ) − 2 t r ( Y S Y T ) 2 t r ( Y L Y T ) \sum_{i1}^n \sum_{j1}^n ||y_i- y_j||^2s_{ij}\\ \sum_{i1}^n \sum_{j1}^n (y_i^Ty_i-y_i^Ty_j-y_j^Ty_iy_j^Ty_j)s_{ij}\\ \sum_{i1}^n (\sum_{j1}^ns_{ij})2y_i^Ty_i-\sum_{i1}^n \sum_{j1}^ny_i^Ty_js_{ij}\\ 2\sum_i^ny_i^Ty_id_{ii}-2\sum_i^n\sum_j^ny_i^Ty_js_{ij}\\ 2tr(YDY^T)-2tr(YSY^T)\\ 2tr(YLY^T)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i1∑nj1∑n∣∣yi−yj∣∣2siji1∑nj1∑n(yiTyi−yiTyj−yjTyiyjTyj)siji1∑n(j1∑nsij)2yiTyi−i1∑nj1∑nyiTyjsij2i∑nyiTyidii−2i∑nj∑nyiTyjsij2tr(YDYT)−2tr(YSYT)2tr(YLYT)
去除乘数最终优化目标为 t r ( Y L Y T ) tr(YLY^T) tr(YLYT) 带入 Y W T X Y W^TX YWTX得到最小化目标 t r ( W T X L X T W ) tr(W^TXLX^TW) tr(WTXLXTW) 该目标存在平凡零解 W O m ∗ d WO_{m*d} WOm∗d 此时L取最小值0出现维度坍缩所有样本映射到同一个点上此解无意义 当W不取零矩阵时由于没有添加尺度约束在降维子空间一定组成基向量方向一致情况下当尺度不断变小时目标L会同时变小无限趋于0不存在最小值 因此考虑对最小化目标变形为 t r ( Y L Y T ) t r ( Y D Y T ) t r ( W T X L X T W ) W T X D X T W \frac{tr(YLY^T)}{tr(YDY^T)} \frac{tr(W^TXLX^TW)}{W^TXDX^TW} tr(YDYT)tr(YLYT)WTXDXTWtr(WTXLXTW) 考虑到尺度因素加以约束 Y D Y T I YDY^TI YDYTI也即 W T X D X T W I W^TXDX^TWI WTXDXTWI, 原始优化问题有多个解。由于是线性映射若同比例缩小低维样本 y i y_i yi得到的数据集Y都可作为最优的低维数据集。故加入约束 t r ( Y D Y ⊤ ) ∑ i 1 n d i i y i T y i 1 tr(YDY^\top)\sum_{i1}^nd_{ii}y_i^Ty_i1 tr(YDY⊤)∑i1ndiiyiTyi1通过限制 y i y_i yi的模长使问题有唯一解。 参考LDA中提到的广义瑞利商可知 λ m i n ( ( X D X T ) − 1 ( X L X T ) ) ≤ t r ( W T X L X T W ) t r ( W T X D X T W ) ≤ λ m a x ( ( X D X T ) − 1 ( X L X T ) ) λ_{min}((XDX^T)^{-1}(XLX^T))≤\frac{tr(W^TXLX^TW)}{tr(W^TXDX^TW)}≤λ_{max}((XDX^T)^{-1}(XLX^T)) λmin((XDXT)−1(XLXT))≤tr(WTXDXTW)tr(WTXLXTW)≤λmax((XDXT)−1(XLXT)) 变换矩阵 W [ w 1 , w 2 , . . . , w m ] W[w_1,w_2,...,w_m] W[w1,w2,...,wm]由 ( X D X T ) − 1 ( X L X T ) (XDX^T)^{-1}(XLX^T) (XDXT)−1(XLXT)最小m个特征向量构成 矩阵形式推导
由拉格朗日乘子法构建L L t r ( W T X L X T W ) − t r ( Λ ( W T X D X T W − I ) ) L tr(W^TXLX^TW)-tr(\Lambda(W^TXDX^TW-I)) Ltr(WTXLXTW)−tr(Λ(WTXDXTW−I))
对W求偏导并令为0 2 X L X T W − 2 X D X T W Λ 0 X L X T W X D X T W Λ 有 ( X D X T ) − 1 X L X T W W Λ 2XLX^TW-2XDX^TW\Lambda0\\ XLX^TW XDX^TW \Lambda\\ 有(XDX^T)^{-1}XLX^TWW\Lambda 2XLXTW−2XDXTWΛ0XLXTWXDXTWΛ有(XDXT)−1XLXTWWΛ
W由 ( X D X T ) − 1 X L X T (XDX^T)^{-1}XLX^T (XDXT)−1XLXT的特征向量作为列向量构成且为了最小化目标函数选取的特征向量应该是最小m个特征值对应的特征向量
相关定义 权重矩阵S 定义样本 x i x_i xi和 x j x_j xj之间的权重 w i j w_{ij} wij, 原则是样本点之间距离越小权重越大 权重矩阵S常用定义方式 S i j { s i j e x p ( − ∣ ∣ x i − x j ∣ ∣ 2 t ) x i ∈ N k ( x j ) 即 x i 是 x j 的 k 近邻 s i j 0 e l s e S_{ij} \left\{ \begin{matrix} s_{ij} exp(-\frac{||x_i - x_j||^2}{t})\ \ \ \ \ x_i∈N_k(x_j) 即x_i是x_j的k近邻\\ s_{ij}0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ else \end{matrix} \right. Sij{sijexp(−t∣∣xi−xj∣∣2) xi∈Nk(xj)即xi是xj的k近邻sij0 else 度矩阵D 度矩阵D是一个对角阵其对角元素 D i i ∑ j 1 n s i j D_{ii} \sum_{j1}^{n} s_{ij} Dii∑j1nsij D { ∑ j 1 n s 1 j 0 . . . 0 0 ∑ j 1 n s 2 j . . . 0 . . . . . . . . . . . . 0 0 . . . ∑ j 1 n s n j } D \left. \left \{ \begin{matrix} \sum_{j1}^ns_{1j}\ \ \ \ 0\ \ \ \ ...\ \ \ \ 0 \\ 0\ \ \ \ \sum_{j1}^ns_{2j}\ \ \ \ ...\ \ \ \ 0 \\ ...\ \ \ \ ...\ \ \ \ ...\ \ \ \ ... \\ 0\ \ \ \ 0\ \ \ \ ...\ \ \ \ \sum_{j1}^ns_{nj} \end{matrix} \right. \right\} D⎩ ⎨ ⎧∑j1ns1j 0 ... 00 ∑j1ns2j ... 0... ... ... ...0 0 ... ∑j1nsnj⎭ ⎬ ⎫ 拉普拉斯矩阵LLD-S
有运算 Y D Y T [ y 1 , y 2 , . . . , y n ] [ d 11 0 . . . 0 0 d 22 . . . 0 . . . . . . . . . . . . 0 0 . . . d n n ] [ y 1 T y 2 T . . . y n T ] [ d 11 y 1 , d 22 y 2 , . . . , d n n y n ] [ y 1 T y 2 T . . . y n T ] d 11 y 1 y 1 T d 22 y 2 y 2 T . . . d n n y n y n T ∑ i 1 n y i d i i y i T ∑ i 1 n d i i y i y i T YDY^T [y_1,y_2,...,y_n] \left. \left [ \begin{matrix} d_{11}\ \ \ \ 0\ \ \ \ ...\ \ \ \ 0 \\ 0\ \ \ \ d_{22}\ \ \ \ ...\ \ \ \ 0 \\ ...\ \ \ \ ...\ \ \ \ ...\ \ \ \ ... \\ 0\ \ \ \ 0\ \ \ \ ...\ \ \ \ d_{nn} \end{matrix} \right. \right] \left. \left [ \begin{matrix} y_1^T \\ y_2^T \\ ... \\ y_n^T \end{matrix} \right. \right] \\ [d_{11}y_1,d_{22}y_2,...,d_{nn}y_n] \left. \left [ \begin{matrix} y_1^T \\ y_2^T \\ ... \\ y_n^T \end{matrix} \right. \right] \\ d_{11}y_1y_1^T d_{22}y_2y_2^T ... d_{nn}y_ny_n^T\sum_{i1}^ny_id_{ii}y_i^T\sum_{i1}^nd_{ii}y_iy_i^T\\ YDYT[y1,y2,...,yn] d11 0 ... 00 d22 ... 0... ... ... ...0 0 ... dnn y1Ty2T...ynT [d11y1,d22y2,...,dnnyn] y1Ty2T...ynT d11y1y1Td22y2y2T...dnnynynTi1∑nyidiiyiTi1∑ndiiyiyiT 因此有 t r ( Y D Y T ) ∑ i 1 n d i i y i T y i tr(YDY^T) \sum_{i1}^nd_{ii}y_i^Ty_i tr(YDYT)i1∑ndiiyiTyi 类似可得 t r ( Y S Y T ) ∑ i 1 n ∑ j 1 n s i j y i T y j tr(YSY^T) \sum_{i1}^n\sum_{j1}^ns_{ij}y_i^Ty_j tr(YSYT)i1∑nj1∑nsijyiTyj
方法流程 1由样本矩阵X构建权重矩阵S度矩阵D拉普拉斯矩阵L
2求 ( X D X T ) − 1 X L X T (XDX^T)^{-1}XLX^T (XDXT)−1XLXT的特征向量取最小m个作列向量构成变换矩阵W
3由 Y W T X YW^TX YWTX完成降维
