基于自组织的鲁棒非线性维数约减算法

Self-Organizing Isometric Embedding

现有的非线性维数约减算法需要求解大尺度特征值问题 由于特征值问题至少二次的计算复杂性 ,这类算法在大样本集上的应用较受限制 此外 ,现有算法的全局优化机制对于噪声较为敏感 ,且需要考虑“病态矩阵”的计算精度问题 提出时间复杂性为O (NlogN)的自组织非线性维数约减算法SIE SIE的主要计算过程是局域的 ,可提高算法抗噪性、回避病态矩阵的计算精度问题 仿真表明 ,对于无噪数据和含噪数据 。

Most algorithms of nonlinear dimensionality reduction suffer some flaws in common. First, these algorithms need to solve large-scale eigenvalues problems or some variation of eigenvalues problems, which is usually of quadratic complexity of time. The quadratic complexity limits the applicability of algorithms in the case of large-size sampling sets, which are very prevalent in the applications of real world, e.g., texts clustering, images recognitions, biological information and so on. Second, current algorithms are global and analytic, which are often sensitive to noise and disturbed by ill-conditioned matrix. To overcome the above problems, a novel self-organizing nonlinear dimensionality reduction algorithm: SIE (self-organizing isometric embedding) is proposed. The time complexity of SIE is O(NlogN), which can bring a N/logN speedup against most current algorithms. Besides, the main computing procedure of SIE is based on locally self-organizing scheme, which improves the robustness of the algorithm remarkably and circumvents the trouble introduced by ill-conditioned matrix. The simulations demonstrate that the reconstructing quality of SIE is as optimal as the best global algorithm in the case of clean sampling sets and superior to global algorithms prominently in the case of noisy sampling sets.