An Embedding Dimension Reduction Algorithm Based on Sparse Analysis
-
摘要: 近几年局部流形学习算法研究得到了广泛的关注, 如局部线性嵌入以及局部切空间排列算法等.这些算法都是基于局部可线性化的假设而提出的, 但局部是否可线性化的问题没有得到很好有效的解决, 使得目前的降维算法对自然数据效果不佳. 自然数据中有很多是稀疏的,对稀疏数据的降维是局部线性嵌入算法所面临的一个问题. 基于对数据自然属性的考虑,利用数据的统计信息动态确定局部线性化范围, 依据数据的分布提出一种排列的稀疏局部线性嵌入算法(Sparse local linear embedding algorithm, SLLEA). 在数据集稀疏的情况下,该算法能够很好地把握数据的局部和整体信息. 将该算法应用于手工流形及图像检索等试验中,验证了该算法的有效性.Abstract: In recent years, local manifold learning algorithms have been widely concerned, such as local linear embedding and local tangent space alignment algorithm. These algorithms are mostly based on the hypothesis of local linearization. However, the problem of whether local linearization can be realized has not been effectively solved, which makes the dimensionality reduction algorithms have poor results on natural data. In natural data, many of them are sparse, so it is important to deal with the dimension reduction for sparse data. Under the consideration of natural attributes with statistical information, an alignment of sparse local linear embedding algorithm (SLLEA) is proposed in this paper. In the algorithm, local linear range is determined dynamically according to the probability distribution of the data. For sparse data sets, the algorithm can effectively obtain local and global information. Experiments on handwork manifold and image retrieval test verify the effectiveness of the algorithm.
-
Key words:
- Linearization /
- locally linear embedding (LLE) /
- sparse /
- dimensionality reduction
-
[1] Roweis S T, Saul L K. Nonlinear dimensionality reduction by locally linear embedding. Science, 2000, 290(5500): 2323-2326[2] Zhang Z, Zha H. Principal manifolds and nonlinear dimensionality reduction via tangent space alignment. SIAM Journal of Scientific Computing, 2004, 26(1): 313-338[3] Jolliffe I T. Principal Component Analysis. New York: Springer-Verlag, 1986[4] Wang J, Zhang Z Y, Zha H Y. Adaptive manifold learning. In: Proceedings of the Neural Information Processing Systems. Vancouver, Canada: The MIT Press, 2004. 1473-1480[5] Teh Y W, Roweis S. Automatic alignment of local representations. In: Proceedings of the Neural Information Processing Systems. Vancouver, Canada: The MIT Press, 2002. 841-848[6] Yang L. Alignment of overlapping locally scaled patches for multidimensional scaling and dimensionality reduction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(3): 438-450[7] Belkin M, Niyogi P. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 2003, 15(6): 1373-1397[8] Donoho D L, Grimes C. Hessian eigenmaps: locally linear embedding, techniques for high-dimensional data. Proceedings of the National Academy of Sciences of the United States of America, 2003, 100(10): 5591-5596[9] He X F, Niyogi P. Locality preserving projections. In: Proceedings of the Neural Information Processing Systems. Vancouver, Canada: The MIT Press, 2003. 153-160[10] He X F, Cai Deng, Yan S C, Zhang H J. Neighborhood preserving embedding. In: Proceedings of the 10th IEEE International Conference on Computer Vision. Beijing, China: IEEE, 2005. 1208-1213[11] Kokiopoulou E, Saad Y. Orthogonal neighborhood preserving projections: a projection-based dimensionality reduction technique. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(12): 2143-2156[12] Li Le, Zhang Yu-Jin. Linear projection-based non-negative matrix factorization. Acta Automatica Sinica, 2010, 36(1): 23-39(李乐, 章毓晋. 基于线性投影结构的非负矩阵分解. 自动化学报, 2010, 36(1): 23-39)[13] Wen Ying, Shi Peng-Fei. An approach to face recognition based on common vector and 2DPCA. Acta Automatica Sinica, 2009, 35(2): 202-205(文颖, 施鹏飞. 一种基于共同向量结合2DPCA的人脸识别方法. 自动化学报, 2009, 35(2): 202-205)[14] Lin T, Zha H. Riemannian manifold learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(5): 796-809[15] Balasubramanian M, Schwartz E L. The isomap algorithm and topological stability. Science, 2002, 295(5552): 7[16] Silva J G, Marques J S, Lemos J. Selecting landmarks points for sparse manifold learning. In: Proceedings of the Neural Information Processing Systems. Vancouver, Canada: The MIT Press, 2006. 1241-1248[17] Zhang Run-Chu. Multivariate Statistical Analysis. Beijing: Science Press, 2006. 36-44(张润楚. 多元统计分析. 北京: 科学出版社, 2006. 36-44)[18] Cheng Yun-Peng, Zhang Kai-Yuan, Xu Zhong. Matrix Theory. Xi'an: Northwestern Polytechnical University Press, 2006. 124-129(程云鹏, 张凯院, 徐仲. 矩阵论. 西安: 西北工业大学出版社, 2006. 124-129)[19] Golub G H, Luk F, Overton M. A block Lanzcos method for computing the singular values and corresponding singular vectors of a matrix. ACM Transactions on Mathematical Software, 1981, 7(2): 149-169[20] Zhang Xian-Da. Matrix Analysis and Applications. Beijing: Tsinghua University Press, 2004(张贤达. 矩阵分析与应用. 北京: 清华大学出版社, 2004)
点击查看大图
计量
- 文章访问数: 1424
- HTML全文浏览量: 61
- PDF下载量: 1286
- 被引次数: 0