传统的非线性维数约减算法如Isomap、LLE、SIE工作在batch模式,也就是在进行嵌入时所有的采样点必须是可用的。当采样点以流的形式到达时,使用上述算法处理增量点很耗时,每到达一个点都要重复运行一次batch模式的算法。另外,当前的非线性维数约减算法需要求解大尺度的特征值问题,或需要计算全局的测地线距离。两者都是二次的复杂度,计算开销较大,在大样本集情形下应用较受限制。针对增量点的问题,本文提出AISIE算法来处理增量点。算法假设采样点和它的适应性邻域集[3]能反映它们所在位置的局域主方向。对增量点进行处理时,基于适应性邻域选择算法首先判断它是否为噪声点,然后在SIE框架下只需更新锚点到其它点的测地线距离和增量点的邻域点到其它点的测地线距离,复杂度近似线性。为了避免求解大尺度特征值问题以及避免计算全局的测地线距离,本文提出线性区域嵌入拼接算法LLI。通过求解最优化问题将两个相邻线性区域的嵌入结果拼接到一起。介绍了一种流形划分方法,对流形进行划分后确保每个子区域是近似线性的,并且区域之间存在公共点,复杂性为线性。LLI算法中最优化问题的求解依赖于相邻区域的公共点数。当时(为嵌入维)LLI解决无约束最优化问题,拼接两片的复杂性为O( );g g≥ddd 3g < d时可以添加一些伪点,或者求解二次约束最优化问题将两区域的嵌入拼接到一起,本文采用添加伪点的方法。LLI算法拼接所有分片嵌入结果的复杂性为O(k*n+m*n+m* d3),m为分片数目远小于样本点数n,k为最大分片包含的点数。结合分片算法的总复杂性为O(T*n*m*log(m)+m*n+ k*n+m*d3)为线性复杂性。