郭爱心

（山西师范大学物理与信息工程学院，山西 太原 030006）

1 引言

随着信息技术的发展和海量数据的积累，数据处理与挖掘日益重要。而现实中的数据往往具有很高的维度，如手写数据、人脸数据和监控视频等，难以用现有的数据分析方法去处理，故需要对高维数据进行降维处理，分析其内在结构和特征。手写数据的非线性结构分析在手写数据识别[1]和手写签名认证[3]中扮演了重要角色。鉴于手写数据的高维非线性特征，应使用非线性降维算法进行降维分析。常用的非线性降维算法有等距特征映射算法[4]（Isometric Feature Mapping,ISOMAP）、局部线性嵌入算法[5]（Locally Linear Embedding,LLE）、拉普拉斯映射算法[6]（Laplacian Eigenmaps,LE）和局部切空间排列算法[7]（Local Tangent Space Alignment,LTSA）等。其中ISOMAP算法可以保留全局特征，广泛应用于图像处理、数据可视化和信号处理。然而，由于要计算最短距离和特征值分解，当数据量过大的时，ISOMAP算法的效率会降低。为了提高ISOMAP的可扩展性，Silva等提出了随机选择地标点的ISOMAP算法，即Landmark-ISOMAP(L-ISOMAP)算法[8]，但随机选择地标点会导致算法性能不稳定。在此基础上，文献[9]基于最小子集覆盖进行地标点的选择，提出了Fast-ISOMAP算法，但地标点仍存在冗余。本文从地标点的选择出发，提出了改进ISOMAP算法（Improved ISOMAPBased on Landmark,IL-ISOMAP），并将其应用于手写数据的非线性结构分析。

2 ISOMAP算法

ISOMAP算法降维的实质是通过保持高维空间和低维空间的距离相似来保持数据的内在特征。设流形数据X={x1,x2,…,xn}⊂M⊂Rd,其中M为D维流形。设Y={y1,y2,…,yn}⊂Rd为d维欧几里得空间的嵌入结果，其中d<

（1）通过k近邻或固定阈值的方法构建数据点的邻域图G，邻域图中的每条边的权重为d(xi,xj)。……