流形学习算法（共7篇）
流形学习算法 篇1
0 引言
近年来, 数据分类问题是数据挖掘领域较为热点的问题。一些特定算法可以直接完成数据分类, 如支持向量机 (SVM) [1]、随机森林[2]、Adaboost[3]等。这些代表算法对维数不高的数据有着良好的效果, 当输入高维数据时, 适用能力明显减弱。
针对高维数据需进行特征提取, 以更准确地完成数据分类, 其代表算法有:尺度不变特征变换 (SIFT) [4]、梯度方向直方图 (HOG) [5]等, 其本质是对数据进行特征提取后, 再利用训练完成的分类器完成数据分类。特征提取只能提取数据的特征, 有一定的降维作用, 但降维的幅度不能具体指定, 这就造成了提取的特征向量维数依然较高, 仍不能很好地适用于分类器。
为了更好地解决数据分类问题, Rencher等[6]提出主成分分析 (PCA) 算法, 用于解决线性数据降维问题;Wang等[7]使用核方法改进了PCA, 提出核主成分分析 (KPCA) , 与SVM算法结合解决非线性数据分类问题;Zafeiriou等[8]提出核线性判别分析 (KLDA) 算法, 利用核方法对LDA算法进行改进, 从而使其适应非线性数据的特征提取;Roweis等[9]提出局部线性嵌入LLE (Locally Linear Embedding) 算法, 利用流形局部特征, 进行数据降维。
Damianou等[10]对数据分类问题进行研究, 提出一种新型隐变量模型解决数据分类问题。王秀美等[11]提出基于有监督学习的SGP-LVM算法, 利用改进型GP-LVM回避传统谱算法, 且不需构建分类器, 完成数据分类;Luo等[12]提出自适应高斯过程分类算法 (AGP-LVM) , 提高高斯过程分类算法的分类准确率。
针对流形学习 (LLE算法) 的邻近点选取影响降维结果, 笔者提出一种基于最优邻近点的改进型LLE算法, 利用降维后数据集内部离差最小, 数据集间离差最大的原则, 选取最优邻近点个数, 结合SVM算法, 完成数据分类。选取Iris flower数据集, Yale数据集, UCI数据集分别验证算法在各类数据集下的可行性和优越性。
1 算法描述
1.1 LLE算法
LLE算法[13,14,15,16,17]是针对非线性数据的一种新的降维方法, 处理后的低维数据均能保持原有的拓扑关系, 且算法操作简单, 属于局部优化算法。LLE降维过程如图1所示, 通过LLE将数据映射到二维空间中, 可以看出, 降维后的数据能很好地保持原有数据的邻域特性。
假定N个输人向量X, 通过LLE算法, 得到输出向量Y。LLE算法可以归结为三个方面。LLE计算过程如图2所示。
具体计算步骤如下:
Step1计算出每个样本点的k个邻近点。把相对于所求样本点距离最近的k个样本点作为样本点的k个邻近点。
Step2计算出样本点的局部重建权值矩阵。这里定义一个代价误差函数:
其中xij (j=1, 2, …, k) 为xi的k个邻近点, wji是xi与xij之间的权值, 且要满足条件为求取W矩阵, 需要构造一个局部协方差矩阵:
将式 (2) 与相结合, 并采用拉格朗日乘法, 即可
求出局部最优化重建权值矩阵。
在实际运用中, Qi可能是一个奇异矩阵, 此时必须正则化Qi, 即:
其中r是正则化参数, I是一个k×k的单位矩阵。
Step3将所有的样本点映射到低维空间中, 必须满足以下条件:
其中, ε (Y) 为损失函数值, yi是xi的输出向量, yij (j=1, 2, …, k) 是yi的k个邻近点, 且满足以下条件:
其中I是m×m的单位矩阵。这里wji (i=1, 2, …, N) 可以存储在N×N的稀疏矩阵W中, 当xj是xi的邻近点时, Wij=wji, 否则Wij=0, 则损失函数可重写为:
其中M是一个N×N的对称矩阵, 表示为:
要使损失函数值达到最小, 需取Y为M的最小m个非零特征值所对应的特征向量。在处理过程中, 将M的特征值从小到大排列, 第一个特征值几乎接近于零, 那么舍去第一个特征值。通常取第2~m+1间的特征值所对应的特征向量作为输出结果。
1.2 邻近点选取的改进
传统LLE算法的邻近点选取没有统一的标准, 一般根据样本数量的不同而改变, 而邻近点的个数k直接决定数据降维的结果。设 (a1, a2, …, an) 表示n类数据集, 每类数据为n维, 为了保证降维后的数据更具代表性, 则必须保证类内离差最小, 类间离差最大。
设ai, aj为任意两类数据集, 降维后可表示为则类内离差Tl可表示为:
计算类间离差时, 需要知道同类数据分布的大致区域, 选择区域中的某个数据点作为代表其余数据的代表点, 当降维后的数据超过3维时, 已经无法将其在坐标平面进行展现, 以2维坐标平面为例, 代表点选取如图3所示。
图3中, C1, C2是X轴上投影差最大的2个点, C3, C4是Y轴上投影差最大的2个点, 设C1= (w11, w21) , C2= (w12, w22) , C3= (w13, w23) , C4= (w14, w24) , 则D点可表示为:
根据式 (9) 进行推演, n维空间下的代表点表示为:
类间离差可表示为:
其中, Di表示任意一类数据的代表点, 根据式 (8) 、式 (11) , 离差比ω可表示为:
由式 (12) 可以看出, 类内离差Tl越小, 类间离差Tc越大, 则离差比ω越大, 表示降维后的数据越具代表性, 越理想。
当数据不变时, 离差比ω由邻近点个数k所决定, 则最优化邻近点个数可表示为:
1.3 算法的实现
根据本文所提出的改进LLE算法中邻近点个数的选取标准, 设同类样本数为n, 则k
Step1设定初始邻近点个数k=1, 根据1.2节所述, 计算离差比ω1。
Step2 k=k+1, 计算此时的离差比ω, 重复Step2, 直到k=n-1, 则离差比向量可表示为ω= (ω1, ω2, …, ωn) 。
Step3判断离差比向量中最大的元素, 可得:
根据式 (14) , 可得最优的邻近点个数k。
Step4设定式 (14) 计算得到的k作为LLE算法的输入邻近点个数, 进行数据降维。
Step5利用SVM算法对降维后的数据进行分类。
2 实验分析
本文在Inter (R) Core (TM) Duo-E7500的CPU, 内存6GB的Linux操作系统下进行实验。采用Iris flower数据集、Yale数据集和UCI数据集对本文所提方法进行可行性的验证。
2.1 Iris flower数据集实验
Iris flower数据集是由鸢尾属植物的三种单独的花的测量结果所组成, 模式类别数为3, 特征维数是4, 每类各有50个模式样本, 总共有150个样本。
实验中, 利用改进的LLE算法将数据集进行降维, 且m=2, 则将数据集从原来的4维降成2维。随机抽取降维后的每类样本中50%的样本作为SVM的训练集, 其余作为测试集, 从而保证训练集和测试集无交叉。
在测试阶段, 标记测试集中样本的模式类别, 设测试集个数为nc, 算法准确分类的个数为nt, 则分类准确率pt可表示为:
将本文算法所得结果与PCA算法、KPCA算法、LLE算法所得结果进行比较, 实验结果如图4所示。
由图4可得, 针对Iris flower数据集, 本文算法可以对其进行有效的分类, 平均分类准确率保持在96.7%, 而PCA算法、KPCA算法、LLE算法分别保持在82.1%、86.6%、91.5%, 较分类效果最好的LLE算法提高5%左右, 体现出本文算法具有一定优越性。
2.2 Yale数据集实验
Yale数据集是由耶鲁大学推行的包含不同光照、表情的人脸数据库, 模式类别数为15, 每类各有11个模式样本, 图像大小为100×100, 灰度级256, 总共有165个样本, 部分数据如图5所示。
按照2.1节中对数据集的分配比例构建对应的训练集和测试集, 按照其实验方法对其进行人脸数据分类实验, 将本文算法再次与PCA算法、KPCA算法、LLE算法比较, 所得结果如图6所示。
由图6可得, 在Yale数据集的实验中, 本文算法的分类准确率较Iris flower数据集有所下降, 其原因为图像属于高维数据, 其维数为10 000维, 针对高维数据, 各类算法的适用性明显削弱, PCA算法、KPCA算法、LLE算法的平均准确率保持在70.2%、78.4%、81.6%, 而本文算法保持在86.8%, 体现出算法对高维数据的适用能力明显强于传统算法。
2.3 UCI数据集实验
UCI数据库是加州大学欧文分校提出的用于机器学习的数据库, 该数据库目前共有187个数据集, 其数目还在不断增加, UCI数据库是一个常用的标准测试数据集。实验选取UCI数据库中的Wine, Pittsburgh Bridges, Balance Scale, Libras Movement, Arrhythmia, Low Resolution Spectrometer (Spectrometer) 总共6类数据集作为实验数据, Wine数据集由178个样本组成, 样本维数为13, Pittsburgh Bridges数据集由108个样本组成, 样本维数为13;Balance Scale数据集由625个样本组成, 特征维数为4;Libras Movement数据集由360个样本组成, 特征维数为91;Arrhythmia数据集由452个样本组成, 特征维数279;Spectrometer数据集由531个样本组成, 特征维数为102。
在UCI数据集下的分类实验, 采用十次十折交叉验证法。将本文所得结果与KPCA算法、KLDA算法、AGP-LVM算法、SGP-LVM算法进行比较, 结果如表1所示。
表1列出结果均是利用交叉验证法所得结果, 每个数据集上最优结果以黑体表示。由表1可得, 在不同维数和不同样本数量的数据下, 本文算法所得分类结果均为最优, 这是由于本文算法在LLE邻近点选取时进行有监督的最优邻近点选取, 从而将传统LLE算法进行改进, 得到更为准确的特征信息, 提高了分类效果。
3 结语
本文对流形学习 (LLE算法) 进行深入研究, 结合SVM算法, 提出一种改进型LLE的数据分类算法。该算法首先利用降维后数据集离差比最大化, 选取LLE算法中最优的邻近点个数, 进行数据的最优化降维, 得到最优的降维结果, 再通过SVM算法对数据进行分类。
实验结果表明:本文算法有较强的适用能力, 针对多个数据库具有较好的分类准确率。Iris flower数据集实验中所得结果较现有算法更为准确, 平均准确率高达96.7%;Yale数据集实验表明:算法在高维数据中准确率依旧优于现有算法, 体现算法在不同维数的数据集中均有较好的适用性;UCI数据集实验表明:针对各类数据下, 算法均有较强的适用能力, 与传统算法比较结果显示本文算法的优越性。今后的任务是进一步研究高维数据分类问题, 提高算法在高维数据中的分类准确率。
摘要：针对高维数据分类问题的特点, 提出一种基于改进型局部线性嵌入LLE (Locally Linear Embedding) 算法的数据降维算法, 结合支持向量机SVM (Support Vector Machine) 算法实现数据分类。首先, 通过LLE算法降维后的数据集, 按照数据集内的离差最小化, 数据集间的离差最大化的原则, 计算得到最优化邻近点个数;其次, 将最优邻近点个数所得的降维数据作为最优结果, 按一定比例选取训练集, 输入SVM算法建立数据分类器;最后, 将测试集输入训练完成的分类器中, 实现最优化数据分类。选取Iris flower, Yale等多类数据集与传统算法进行对比实验, 验证算法的可行性。实验结果表明:所提出的算法可以有效地完成数据分类, 针对低维数据和高维数据分类问题具有较好的适用性和优越性, 在人脸检测中也取得较好的结果。
关键词：数据分类,局部线性嵌入,最优邻近点个数,降维,最大化
流形学习算法介绍与相关问题综述 篇2
2000年, Seung等人在SCIENCE上发表文章称, 现实世界中的高维数据集都可以看成是近似分布在一个低维非线性流形上的, 而通过对这个低维流形进行分析就能够获得它所对应的高维数据集的各种性质。至此, 一种全新的处理高维非线性数据集降维问题的方法——流形学习就第一次被正式提了出来。
流形学习可以被描述为一种从高维数据集中恢复其低维流形结构的数据降维方法。也即, 从高维数据集的分布中挖掘出其符合的低维流形结构, 并将此低维流形结构在低维欧氏空间中表示出来, 获得对应的低维坐标, 从而实现数据降维的目的。流形学习算法突破了线性方法的诸多先天不足, 能够从本质上发掘出数据集的内在规律, 得出与高维数据集最为相近的低维嵌入坐标, 因此, 该类算法一经提出, 就获得了广泛的关注和讨论, 并很快成为了处理高维非线性数据集降维问题的标志性算法。在流形学习算法被提出后的数十年间, 它的有效性和算法效率也被无数的实验和实际应用所证实, 时至今日依然展现出了强大的生命力。流形学习的代表性算法包括局部线性嵌入 (LLE) [3]、等距特征映射 (ISOMAP) [4]、拉普拉斯特征映射 (LEM) [5]以及局部切空间排列 (LTSA) [6]、最大方差展开 (MVU) [7]和扩散映射 (DFM) [8]等算法。这些算法在遵循了流形学习的一般框架之外, 都具有各自非常鲜明的特点, 都取得了良好的算法效果。
1 流形学习算法概览
下面先结合三个典型的流形学习算法, 详细介绍它们的算法思想, 算法步骤以及算法特点, 并为后文探索该类算法的共性做好铺垫。
1.1 局部线性嵌入 (LLE)
首先介绍LLE算法。它是一种非监督的学习算法, 能够计算高维数据的的低维嵌入, 这种嵌入保留了数据的邻域性质。假设数据是分布在一个非线性流形上, 它最终是被映射到一个独立的低维全局坐标系上去的。这种映射是通过局部线性重构的的对称性而获得的, 而且嵌入结果的计算最终是归结于一个稀疏矩阵特征值问题的。
LLE算法在计算低维嵌入的过程中遵循的一个最重要的原则:高维空间中相邻的点在低维空间中仍然保持相邻, 并且整体上来说, 数据点的分布也与高维空间中的分布相似。在适当的条件下, 仅仅从高维空间的邻域中的几何性质也能够获得这种低维嵌入。
首先, 假设数据由N个实值向量Xi构成, 每一个向量的维数都为D, 从一个光滑的潜在流形上采样而来。当数据点的个数很充足 (也就是此流形是良好采样) 的时候, 就可以认为每一个数据点和它的邻域都是分布或者近似分布在一个流形的一个局部线性的小块上的。对于每一个数据点, 总存在一些邻近的点, 它和这些邻近的点就可以定义一个流形上的近似的线性平面。在这种情况下, 每个数据点就能够用它的邻域来进行重构, 得到的线性系数就用来刻画每个数据点邻域内的局部几何特性。最后就是运用这个权重矩阵来恢复低维空间中的嵌入数据。LLE算法的详细过程可叙述如下:
1) 邻域搜索。LLE方法中的第一步就是确定每个数据点的邻域。确定邻域的方法主要有两种, 一种是K邻域法, 也就是对每个数据点取它的K个最邻近的点作为邻域, 这是用欧氏距离来度量的。另一种方法就是对每个数据点定义一个半径固定的球域, 所有在此球域范围内的点都被当成是它的邻域。但是在实际应用中也可以根据一定的先验知识灵活决定邻域搜索的办法。
2) 约束最小二乘优化。LLE算法的第二步是将每一个数据点由它的邻域重构出来。这是通过解决一个约束最小二乘优化的问题来实现的。最小代价函数为:
其中。然后求解以下线性方程组:∑kGjkwk=1, 再调整w的权值使其和为1。则得到的结果向量wk就是每个点的重构系数, 将所有wk写成矩阵形式得到的矩阵W即为权重矩阵。
3) 特征值问题。LLE算法的最后一步就是基于第二步中建立的权重矩阵W来计算高维输入的低维嵌入。低维输出是在W固定的情况下, 通过最小化如下代价函数所获得的:
为了对上述代价函数进行优化, 可以把它重写成如下形式:
其中, 矩阵M定义如下:
为了使问题表达的更清楚, 即去掉低维输出结果Y中的平移、旋转及缩放的自由度, Y还需要满足以下两项约束条件:
在满足上述两个限制条件的同时, 再对代价函数公式 (2) 进行优化, 就得到了最优化的嵌入。这是通过求解矩阵M的第2到第d+1小的特征值所对应的特征向量来实现的。
1.2 等距特征映射 (ISOMAP)
下面再接着介绍ISOMA算法。ISOMAP算法是另一种非常经典的流形学习算法, 它建立在古典MDS方法的基础上, 通过获取所有点对之间的测地距离, 力求能够保留数据的内在几何特征。此方法的难点在于如何在仅仅知道输入空间中点的距离的情况下, 对离的很远的点估计它们的测地距离。对近邻点, 输入空间中的距离很大程度上能够看成是测地距离的近似。而对于离的较远的点, 测地距离则通过将邻近点间的距离逐一相加来近似得到。
ISOMAP算法同样可以分为三个步骤:
1) 确定数据点间的邻域关系。这是通过输入空间X中任意两点i和j之间的距离dX (i, j) 来决定的。具体来说, 这又有两种简单的方法。第一种是规定一个固定的半径ε, 以一个点为中心, 所有在此半径范围内的点都称作这个点的近邻点;另一种方法是选择一个点的K个最邻近的点作为它的近邻点。这些近邻关系是通过定义在数点上的赋权图G来表示的, 相邻的点之间存在一条边, 边的权重就赋予它们的距离dX (i, j) 。
2) Isomap通过计算图G中的最短路径距离dG (i, j) 来估计流形M上所有点间的测地距离dM (i, j) 。一个用来寻找最短路径的简单算法如下:首先初始化dG (i, j) , 令当i, j之间有边连接时, dG (i, j) =dX (i, j) ;否则dG (i, j) =∞。然后依次为每一个k=1, 2, …, N, 用min{dG (i, j) , dG (i, k) +dG (k, j) }来代替dG (i, j) 。得到的最终结果DG={dG (i, j) }就包含了图G中所有点之间的最短路径距离。
3) 将古典MDS方法运用到图G的距离矩阵DG上, 构建出d维欧氏空间Y上的嵌入数据, 构建出的嵌入数据能够最好的保留流形的预计内在几何特征。而低维空间Y中点的坐标向量yi的选取必须使得如下的代价函数取得最小值。
其中τ (DG) =-HSH/2, S是将DG中各元素平方后得到的矩阵, 。将矩阵τ (DG) 的特征值记为s1, s2, … (按降序排列) , v1, v2, …为与之相对应的特征向量 (v1、v2为列向量) 。那么矩阵中的行向量就是最合适的d维嵌入坐标, 也是整个算法的最终输出。
1.3 拉普拉斯特征映射 (LEM)
将要介绍的第三个流形学习算法是LEM算法。它运用图的Laplacian概念, 可以计算出数据集的低维表示, 能够在某种意义下最好地保持局部邻近信息。算法所产生的映射可以看作是对流形几何的连续映射的一种离散逼近。LEM算法的核心是使用Laplace Beltrami算子在流形上达到最优化的嵌入。此算法用数据点的邻域图来近似流形, 用邻域图的含权Laplace矩阵来近似Laplace Beltrami算子。由于Laplace Beltrami算子在热传导方程中的关键作用, 这就为选择热核作为权的衰退方程提供了理论支持。另外, Laplace特征映射保持局部特征的性质使得它对噪声不敏感, 即使只使用局部距离, 也不易引起短路。
LEM算法的具体过程可表述如下:
1) 建立邻接图。如果xi和xj“邻近”, 就在节点i和j之间置一条边, 这一步骤与上述的两种算法相同, 都有两种做法:ε-邻域法或者K-最近邻域法。
2) 选择权值。同样的, 也有两种为边确定权值的方法。
(a) 热核 (Heat Kernel) 法[参数t∈R]:
若i和j之间有边连接, 定义边的权值为, 否则Wij=0。
(b) 简单法[无参数, 即上面的t=∞]:
若i和j之间有边连接, 定义边的权值为Wij=1, 否则Wij=0。这种方法较简单, 避免了选择参数t。
(3) 特征映射。假设前面建立的图是连通的, 否则用第3步对每个连通分支进行操作。
计算下面广义特征向量问题的特征值和特征向量:
其中D是对角权矩阵, 其对角元是W矩阵的列和 (或行和, W是对称的) :
Dii=∑jWji (9
L=D-W称为Laplace矩阵, 它是对称的, 半正定的矩阵, 可以看作是定义在图G上的算子函数。则经过特征分解后得到的第2到第d+1小的特征值对应的特征向量即是算法的d维输出坐标。
2 从图嵌入的视角看流形学习算法
上面介绍了三种很有代表性的流形学习算法, 可以看出, 虽然它们的算法目标不同, 各自保持的数据集性质不同, 计算过程也是各有偏重, 但是, 它们同作为流形学习算法的代表, 还是有很多能体现这一类算法共性的相似之处的。
其中, 比较明显的就是, 这三种算法的步骤都大致相同。比如, 算法的第一步都是确立数据点的邻域关系, 第二步都是根据邻域关系对数据集进行某一方面的刻画, 比如LLE刻画邻域点间的重构线性系数;ISOMAP刻画邻域点间的相互距离, 从而得到全局各点间的最短路径距离;LEM刻画邻域点间的相互远近关系。算法的第三步就是将第二步中得到的关于数据集某一方面信息的刻画保持到低维输出结果中去, 从而使得低维输出结果在我们想要保持的那种性质方面尽可能的逼近高维原始数据。这样一来, 各算法间的区别就可以看成是它们想要在低维嵌入结果中保持的原始数据集的哪种性质了, 而这些算法从整体上看, 可以说是共同遵循了某种特定的框架。
而在文献[9]中, 作者就提出, 目前所有这些流形学习算法, 都可以统一在图嵌入的框架下, 都可以从谱图理论的角度作统一的解读。下面就将作者文中的一些观点做一个综述。
对于流形学习算法, 算法的输入为:X=[x1, x2, ..., xN], 其中xi∈Rm, N是输入点的个数, D是输入数据的维数;算法的输出则是Y=[y1, y2, ..., yN], 其中yi∈Rm', m'<
其中d是常数, B是为了避免代价函数出现平凡解而定义的约束矩阵, 通常是一个用于控制解的规模的对角矩阵。由这样的图保持标准所带来的相似性保持性质就有两方面的解释, 如果样本点xi和xj有较大的相似性, 那么它们对应的嵌入点yi和yj就应该距离相近;反之, 如果xi和xj相似性较小, 则yi和yj也应相互远离。
上述分析就给出了图嵌入的一般框架, 可以看出, 图嵌入的核心思想就是在低维输出结果中保持相似性图上各点间的相似性。这显然与各种流形学习算法的目标是一致的。而这也是流形学习算法能够统一在图嵌入框架下的根本原因。下面就将具体描述前一节中介绍的三种流形学习算法是如何描述成图嵌入的方法的。
首先看LLE方法。LLE方法在将输入数据映射到低维空间中去的时候注重保持的是邻域点间的相互关系。首先要计算的是局部重构系数矩阵M, 满足∑j∈Nk (i) Mij=1, 其中Nk (i) 是样本点xi的k个最近邻的索引集, 然后低维表示y就是通过最小化代价函数来实现的。如果令图嵌入中的相似矩阵W=M+MT+MTM, B=I, 那么LLE的代价函数公式 (2) 就可以和图嵌入的代价函数公式 (10) 完全的等同起来。所以, LLE和图嵌入的等价关系由此可以直接建立起来。
再看ISOMAP方法。ISOMAP在寻求数据集低维表示的过程中所注重的是对数据点间测地距离的保持。令最短路径矩阵DG为获得的近似测地距离矩阵, 函数τ (DG) =-HSH/2就将距离矩阵转换为了相应的内积矩阵 (其中, Sij=DG2 (i, j) 。如果令W=τ (DG) , B=I, 那么ISOMAP中求解τ (DG) 的最大特征值对应特征向量的问题就可以和求图嵌入的代价函数公式 (10) 的最优解等价起来。所以ISOMAP方法也可以看成是图嵌入的另一个例子。
最后再来看LEM方法。它保持的是邻域点间的相似性。LEM方法和图嵌入的联系算是所有流形学习算法中最紧密最直观的了, 因为它的代价函数和图嵌入的代价函数具有完全相同的形式。只是在具体的选择相似矩阵W时有两种不同的方法, 一种是选择高斯函数;另一种是当j∈Nk (i) 或i∈Nk (j) 时让Wij=1, 否则Wij=0。所以最后LEM方法也可以很好的与图嵌入统一起来。
所以, 如果我们从图嵌入的角度来看这些流形学习算法, 可以发现它们都可以很好的统一在图嵌入的框架下, 算法最终都归结为将定义在图上的相似矩阵保持到低维空间中去。而各算法间的区别就体现为所定义的相似矩阵的区别, 比如有的算法以两个样本点的全局距离作为它们相似性的度量, 有的算法则以样本点在局部邻域中的相互位置关系作为相似性的度量。而各算法相似矩阵上的区别也正体现了不同算法所追求保持的数据集性质的不同, 这也是各个算法最终的学习效果各有优势却也截然不同的关键所在。所以说, 从图嵌入的角度来看这些流形学习算法, 我们可以很清晰的看出这些算法都是紧密联系同时又是各有所长的。
3 流形学习算法成功的条件
前面两节中详细介绍了几种代表性的流形学习算法, 可以说, 经过人们不断的研究和扩展, 流形学习算法作为一种能够处理非线性数据降维问题的一类算法已经得到了很广泛的应用, 并在很多数据集上都取得了成功。但是, 流形学习算法也并不是对任何数据集都能取得很好效果的, 甚至对一些很简单的数据集, 算法却有可能会输出一些很离奇的结果。这种情况就是流形学习算法的一些固有缺陷的反映, 比如, 流形学习算法的低维输出结果只考虑使代价函数取得最小值而完全不考虑所选择的特征向量是否有意义。对于这种固有的缺陷, 下面将要介绍的这篇文章[10]就作出了详细的分析, 并列出了想要算法取得成功就必须满足的一些条件。
在本文中, 作者首先对何为算法的“失败”给出了一个明确的定义:令X=XN×d为原始样本。输入是由ψ (X) ⊂RD给出的, 其中ψ:Rd→RD是光滑映射, D≥d是输入数据的维数。令Y=YN×d是原始样本X的一个仿射变换, 这样就能满足上述正则化约束。当算法成功的时候, 就意味着输出应该与Y很相似。令Z=ZN×d为任何满足正则约束的矩阵, 如果存在这样的Z使得Φ (Y) >Φ (Z) , 就认为算法失败了。其中Z是和Y显著不同的, 因而也是和X显著不同的。或者说, 如果存在一个显著不同的Z, 它的代价比最适当的嵌入Y要小, 那么算法就失败了。这篇文章中并没有明确的给出“显著不同”的定义, 通常来看, 当Z的维数比Y小时就认为Z与Y是显著不同的。这里的矩阵Z并不一定要与算法的输出相似, 它仅仅是一个数学的构造, 来显示流形学习算法的输出结果并不一定总能恢复流形的真实结构。
其中 (2i) 就保证了Z’1=0, 而σ和ρ的选择使得Z (1) 和Z (2) 的方差都等于1。Z (1) 关于原点的对称性就暗含了Cov (Z (1) , Z (2) ) =0, 因此正则约束Cov (Z) =I就能成立。对此, 作者给出了如下定理:
定理1:令yij为内点, 并设置比率大于2, 那么有φ (Yij) >φ (Zij) 成立。
此定理就说明了, 对于长宽比大于2的格子数据集, 一维嵌入Z比对原始数据进行线性变换而得到的Y的代价更小, 而显然一维嵌入Z并不是原来数据真实结构的反应。
由此可以得出, 当存在Z使得Φ (Y) >Φ (Z) 时, 算法就失败了。可以看出, 流形学习算法想要取得成功还必须对所处理的输入数据集进行一定的限定, 并不是对任意的数据集都能产生很好的结果的。甚至是对一些看上去十分简单的数据集, 算法仍然可能产生错误的结果, 这不得不说对流形学习算法的应用前景产生很大影响的因素, 也是在未来的研究工作中值得去进一步改进和完善的。
4 流形学习中的一些问题
流形学习算法自2000年首次被提出以来, 经过人们不断的研究与完善, 如今已相对比较成熟, 而且已经在很多其他领域中得到了广泛的应用。但是, 关于流形学习算法仍然有一些公开的问题并没有能够得到很好的解决, 这些问题已经成为制约着流形学习取得进一步发展的重要因素。
比如说, 在算法的邻域搜索步骤中, 邻域选择的参数K或者ε往往是人们凭经验或者某种对数据集的先验的了解给出的, 而并不是通过某种规则推导得出的。这就使得这两个参数的选择有很大的随意性, 可能会影响算法的效果。更关键的是, 流形学习算法都是建立在一个根本的假设之上的:流形上足够小的一个局部邻域可以被看成是一个线性空间。流形学习算法一个最普遍的做法就是, 使用线性的方法对每个局部邻域进行分析, 然后将每个局部邻域的信息汇集起来得到对整个流形的刻画。所以, 流形学习算法取得成功的基础就在于, 每个局部邻域真的能近似的看成一个线性的子空间。而控制局部邻域是否构成一个线性子空间的, 正是算法的邻域参数K或者ε。如果对邻域参数的确定没有明确的选择方法, 那就意味着算法对所选取的每个局部邻域是否能真实的逼近一个线性子空间没有一个理论上的保证。这才是确定邻域参数中真正的问题所在。比如一个弯曲程度较大的二维流形, 为了算法的成功, 所选取的邻域应该能够近似的逼近一个二维平面, 而对于某个给定的邻域参数K, 在流形上比较平坦的区域, K个点所构成的邻域能很好的逼近二维平面, 而在流形上弯曲程度较大的区域, K个最近邻点就有可能无法构成一个二维平面而只能看作是一个曲面。在这个曲面上运用线性的方法, 比如计算相互间的欧氏距离, 来获得关于此邻域的刻画显然是不真实的。再比如在一些密度分布不均匀的数据集上, 取多少个邻域点才能构成一个近似的线性空间, 同样是一个现有算法无法解决的问题。目前针对这一问题还没有一个十分完美的解决方案。有一些方法试图对此作出优化, 比如可以根据数据集局部的密度或者曲率的不同灵活的调整邻域个数的选择, 但是对于邻域参数的选择与邻域能否构成一个线性子空间之间理论上的联系仍然没有一个很完善的结论。这算是流形学习算法中留待解决的一个疑问。
流形学习算法中另一个公开的问题是流形本质维度确定的问题。流形学习算法的目标是将寻求分布在流形上的高维数据集的低维表示, 而这里低维的维数就应该是流形的本质维度, 在一般算法中, 流形的本质维度是作为算法的参数先验的给出的。在为了验证流形学习算法的有效性而经常用到的几个人造数据集中, 它们所在流形的本质维度是很容易看出的, 因而算法作为参数的低维维度很容易确定。而在绝大多数的实际数据集中, 数据集所在流形的维度是无法直接看出的, 需要通过计算才能给出。目前比较普遍的确定流形本质维度的方法主要是计算残差法, 即作出算法输出结果的残差随输出维度的变化而变化的曲线, 将曲线的拐点处对应的维度作为流形的本质维度。这样做一个主要的问题就是, 拐点只是一个相对的概念, 有的时候不同的维度所对应的曲线斜率变化相差并不大, 难以确定真实的拐点。而且, 单凭所谓拐点来确定流形本质维度同样没有理论上的证明, 目前的方法只能被证明是选出了“最适合”的嵌入维度。能否更有效率且更准确的获得数据集所在流形的本质维度, 这也将是决定着流形学习算法能否扩展其应用领域的重要因素。
除此之外, 流形学习算法中还有一些其他的问题也是值得深入探究的。比如多流形上的数据集的降维问题, 即如何将分布在多个流形相互交叉和重叠的“多流形”上的数据集统一的在一个低维坐标系中表示出来, 就是一个很有意义却还没能得到很好解决的问题;而如何发掘出数据集中隐藏的其他有意义的信息, 并将其作为对高维数据性质的新的刻画, 从而丰富和发展流形学习算法的方法和种类 (就像当初扩散距离被引入到流形学习中而形成的扩散映照算法) , 也同样是一个很有挑战性的问题。
5 总结
本文对当前的流形学习作了一个较为全面的综述。包括介绍了几种最具代表性的流形学习算法, 并介绍了如何从图嵌入的角度将这些算法统一起来, 探讨了算法能否取得成功的一些判定条件。本文的主要工作在于对流形学习领域的主要工作及相关成果作了一个总体的介绍, 对涉及到的相关问题作了一个简单的梳理。当然, 本文主要选取了各个方面的一些代表性文章作了介绍, 对流形学习领域的所有成果显然无法全部涉及。相信随着对流形学习研究的不断深入, 流形学习目前所遇到的一些难题一定会得到解决, 流形学习作为一种很有潜力的学习算法, 一定能够得到更广泛的应用。
摘要：流形学习是近年来新发展成熟的一种学习的模式, 是机器学习中的一个重要组成部分。流形学习假设待学习的高维数据集分布于一个光滑的非线性流形上, 通过对此流形上各点间的邻域关系或者全局测地距离等性质进行刻画和保持, 再借助于谱分解的方法和理论, 就能获得能够保持分布在流形上的高维数据集某方面特性的低维表示。该文就将结合目前流形学习领域已有的研究成果, 对流形学习的各个相关方面做一个较为全面的综述。
关键词：流形学习,数据降维,图嵌入
参考文献
[1]Jolliffe I T.Principal Component Analysis[M].Springer-Verlag, New York, 1986.
[2]Cox T F, Cox M A A.Multidimensional Scaling[M].London:Chapman and Hall, 1994.
[3]Roweis S T, Saul L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science, 290 (5500) :2323-2326, 2000.
[4]Tenenbaum J B, De Silva V, Langford J C.A global geometric framework for nonlinear dimensionality reduction.[J]Science, 290 (5500) :2319-2323, 2000.
[5]Belkin M, Niyogi P.Laplacian Eigenmaps for Dimensionality Reduction and Data Representation[J].Neural Computation, 2003, 15 (6) :1373-1396.
[6]Zhang Z, Zha H.Principal Manifolds and Nonlinear Dimension Reduction via Local Tangent Space Alignment.Scientific Computing, 2005, 26 (1) :313-338.
[7]Weinberger K Q, Saul L K.An introduction to nonlinear dimensionality reduction by maximum variance unfolding.In AAAI, 2006.
[8]Coifman R R, Lafon S.Diffusion Maps.Computational and Harmonic Analysis, 2004.
[9]Yan S, Xu D, Zhang B, et al.Graph-embedding:A general framework for dimensionality reduction.In Proc.IEEE Int.Conf.Comput.Vis.Pattern Recog., 2005:830-837.
流形学习算法 篇3
流形学习算法是近年来发展起来的一类机器学习算法,文献[1]提出的等度规特征映射(Isomap)算法以及文献[2,3]提出的局部线性嵌入(LLE)算法引领了该领域快速地发展。流形的定义是:设M是一个Hausdorff 拓扑空间,若对每一点都有p∈M,都有p的一个开邻域U和Rn的一个开子集同胚,则称M为n维拓扑流形,简称为n维流形。通俗地讲可以把流形理解为包括各种维数的曲线、曲面等。流形学习问题可以表述为[4]:设Y⊂Rd是一个低维流形,f:Y→RD 是一个光滑嵌入,其中D>d。数据集{yi}是随机生成的,且经过f映射为观测空间的数据{xi=f(yi)}。流形学习就是在给定观测样本集{xi}的条件下重构f和{yi}。流形学习把一组在高维空间中的数据在低维中重新表示,与PCA和MDS不同,在流形学习算法中假设所处理的数据观测值是采样于一个潜在的流形上,或者说对于这组数据存在一个潜在的流形。由于流形学习能从复杂的自然数据观测值中找出内在的非线性自由度,因而越来越受到研究者重视[5],并已经在人脸识别[6]等领域得到了成功的应用。
1 Isomap与LLE
1.1 Isomap算法
Isomap是建立在经典的MDS基础之上的一种算法[1],它力求保持数据内在几何特性,对于流形上所有的点,Isomap用它们之间的测地线距离代替欧式距离。这是因为对于含有高度非线性信息的数据点集,数据点之间的欧式距离有时并不能反映出对应流形的内在结构。如图1A所示,图中的数据点集位于一个潜在的二维流形上,图中两个画圈的点之间的欧式距离(虚线表示)并不能反映它们在流形上的相对位置信息,Isomap算法就用这两点在流形表面的测地线距离来表示这种位置信息,如图1B所示。测地线距离的计算分两种情况:对于相邻的两点,Isomap用欧式距离来近似地表示测地线距离;对于不相邻的两点(距离较远的两点),测地线距离可以在两点间所有经过一系列相邻点连接起来的欧式距离的叠加中取最小值来近似地估计,如图1C所示。一般可以通过Dijkstra算法得到测地线距离的估计值。
Isomap算法共分为三步,第1步:计算每个点的相邻点,也就是构造邻接图(一般采用K近邻法);第2步:计算任意两点间的测地线距离(最短距离);第3步:用MDS求低维嵌入流形。
1.2 LLE算法
与Isomap算法要计算流形上所有数据点集之间的测地线距离不同,LLE算法从流形的局部入手,它假设一个流形在一个局部邻域上可以近似看成是具有线性特征的,那么在这个小的局部邻域上的一个点就可以用它的相邻点在最小二乘意义下最优地线性表示。通过连接的邻域我们可以从局部逐步扩展到整体。
假定
这里Wij表示第j个数据点对第i个数据点重建的贡献。式(1)有两个条件约束:第一,对于每一个数据点
LLE算法的计算分为三步(如图2所示):第1步,计算
式(2)与式(1)在形式上相同,但这里我们保持Wij不变。
2 实验结果
本实验的目的是测试Isomap与LLE两种学习算法在参数变化时的性能变化、对高维数据点集的要求以及执行效率,它在一定程度上反映了全局方法与局部方法的特点,从而为不同应用提供参考。算法的实现步骤参见第1节。实验平台为Intel Pentium(M)1.6GHz处理器,1GB DDR400内存,Microsoft Windows XP SP2操作系统,实验环境为Matlab7 (R14),采用Swiss roll三维数据点集。
2.1 参数K的选择
Isomap和LLE算法的第一步都要先构造一个邻接图,邻接图的选取对于算法的成功至关重要。对每一个数据点都要按一定的规则选择它的相邻点,事实上相邻点的选择可以是相当复杂的[3]。在实践中一般采用K近邻法,即对每一个数据点都选择与它距离最近的K个点作为它的相邻点。图3A为包含1000个采样点(N=1000)的Swiss roll三维数据集,该数据集采样于一个二维流形上,一个好的降维算法应能将数据点展开成如图3B所示。图4和图5分别是Isomap和LLE算法对不同K值的结果。
由图中可以看出若仔细选择K值,Isomap(K=8)与LLE(K=8)都能很好地将Swiss roll数据集展开,但是相对于LLE,Isomap对不同的参数K有更好的稳定性,直观上理解为由于LLE只考虑保持局部特征,而不计算任两点的测地线距离,因此反映局部特征的K值对LLE影响更为显著。
2.2 采样点数N的影响
LLE算法的前提条件是数据点集应是充分采样的[3],即N值足够大,所谓充分采样就是流形上的几何特征在采样中应能被保留下来,而Isomap算法对采样没有作出明确要求。本文实验中固定K值为8,对于N分别为250、500、800、1000和2000的Swiss roll分别作Isomap和LLE,结果如图6所示。实验结果表明,尽管相对LLE 来讲Isomap对N的容忍度要大一些,但它对点数N还是有一定要求的。当N为1000和2000时,Isomap和LLE都工作得很好;当N为800点时,Isomap仍能比较正常地将Swiss roll展开,而LLE开始出现畸变;当N为500点时,两种算法都发生畸变。
2.3 算法效率
本文不对两种算法效率作理论分析,理论分析请参考相关文献[3,4]。表1给出了完成2.2节实验两种算法分别耗费的时间。必须指出算法最终执行时间受多种因素影响,本文的结果只能对两种算法的执行效率作出粗略的直观反映。实验结果表明:在计算效率上,由于Isomap需要计算所有数据点之间的测地线,因此对计算强度要求相对较高,LLE算法则把计算量限制在局部范围,不需要迭代,因此计算复杂度相对较小。
3 结 论
Isomap通过流形上所有采样点的测地线(或其他方法)的近似逼近来对流形几何结构进行重建,因此该类算法能较好地反映流形的整体拓扑结构;而LLE采用的是另一种思路,它从流形的局部结构入手,通过合理地假设流形局部具有线性结构,通过局部线性重建和相邻点之间的嵌套的办法来最终重建流形的整体结构,因此LLE可以学习具有局部线性的任意维数的低维流形。两个算法在参数的选择上还需要进行进一步的研究,特别是最近邻点数K的取值还没有理论上最优的解决办法。最后两个算法都要求较好的采样,他们对输入噪声十分敏感,这也是目前所有流形学习算法普遍存在的缺点。
以Isomap算法和LLE算法为代表的流形学习非线性降维机器学习算法可以从大量的高维数数据观测值中发现潜在的结构性信息,因此可以用来对原始数据进行特征选择和特征提取。
摘要：流形学习(Manifold Learning)算法是近年来发展起来的非线性降维机器学习算法。等度规特征映射Isomap(Isometric feature mapping)和局部线性嵌入LLE(Locally Linear Embedding)是两种典型的流形学习算法。通过实验比较和分析两种算法中邻接参数K和采样点数N的选取对降维结果以及执行时间的影响,实验结果表明Isomap对邻接参数K和采样点数N具有较高的容忍度,而LLE算法在计算速度上优势明显。
关键词：等度规特征映射,局部线性嵌入,流形学习,非线性降维
参考文献
[1]Tenenbaum J B,Silva V,Langford J C.A global geometric frameworkfor nonlinear dimensionality reduction[J].Science,2000,290:2319-2323.
[2]Roweis S T,Saul L K.Nonlinear dimensionality reduction by locallylinear embedding[J].Science,2000,290:2323-2326.
[3]Saul L K,Roweis S T.Think globally,fit locally:unsupervised learningof low dimensional manifolds[J].Journal of Machine Learning Re-search,2003,4:119-155.
[4]Silva V,Tenenbaum J B.Global versus local methods in nonlinear di-mensionality reduction[C]//Advances in Neural Information Process-ing Systems 15.Cambridge:MITPress,2003,705-712.
[5]尹峻松,肖健,周宗潭,等.非线性流形学习方法的分析与应用[J].自然科学进展,2007,17(8):1015-1025.
流形学习算法 篇4
对数据进行降维,按照所处理的数据类型,可以分为两类:线性降维方法和非线性降维方法。传统的线性降维方法,假设高维数据集存在全局的线性结构,构成数据集的各个变量之间是独立无关的,其代表算法有:主分量分析法(Principal Component Analysis,简称PCA)[1],线性判别分析法(Linear Discriminant Analysis,简称LDA)[2],非负矩阵分解法(Non-negative Matrix Factorization,简称NMF)[3]等。当数据存在全局线性关系时,这些方法可有效地学习出线性结构,找出数据之间的线性关系。但是,对于非线性数据,这些方法则无法挖掘出本质信息。因此,对于非线性数据降维的研究,得到了广泛重视。
由于现实生活中,大量的数据都是分布或者近似分布于非线性的流形上,因此非线性降维方法也称为流形学习方法。流形学习的经典算法主要有:等距离映射算法(Isometric Mapping,简称Isomap)[4],局部线性嵌入算法(Local Linear Embedding,简称LLE)[5],拉普拉斯特征映射算法(Laplacian Eigenmap,简称LE)[6],局部切空间排列算法(Local Tangent Space Alignment,简称LTSA)[7]等。这些流形学习算法之所以能够挖掘出数据间的非线性关系,就在于其与传统线性降维方法的主要区别,即通过构造出高维数据点的局部邻域结构,再利用这些局部邻域结构全局映射到低维空间,得到数据间的本质低维信息。由于这些流形学习算法具有参数少、计算快、易求全局最优解等优点,近几年来在许多领域都得到了广泛关注[8,9]。本文主要研究流形学习算法在文本分类中的应用,针对文本数据的特点,对流形学习算法做出相应的改进,使其能够更好地处理文本数据的分类。
文本分类,顾名思义,就是将大量文本文档划分成为一个或者一组类别,使得各个类别代表不同的概念主体[10]。在计算机中,可以利用文本集的词库来代替文本,再利用词库构造的向量来表示文本信息。因此,文本数据可以用高维的向量进行表示。直接对高维的文本数据进行分类,现有的分类算法不仅计算代价大,而且无法得到满意的分类效果。因此,一种改进的方案就是先对高维的文本数据进行有效地降维,再用分类器对低维数据进行相应地分类识别,以提高分类器的识别效果。
但是,传统的流形学习算法,只是用欧式距离作为构造样本邻域集的标准。这种简单的构造邻域方案,对于稀疏庞大的文本数据,往往无法找到样本准确的邻域集。因此,本文主要利用文本分类中的类别信息,对流形学习算法的度量距离做出相应的改进,“拉近”类别相同的数据,“疏远”类别不同的数据,构造出样本中类别相同的邻域集,使其更好地挖掘出数据间的本质信息,再用现有的分类器对其进行分类识别。与此同时,本文还利用现有的半监督流形学习算法,构造相应的分类器,对高维数据直接进行降维分类,为半监督流形学习算法在文本数据的分类中提供一种思路。在算法的选择上,本文主要针对局部线性嵌入算法(LLE)和半监督局部线性嵌入算法(Semi-Supervised Local Linear Embedding,简称SSLLE)[11]进行设计改进,提出一种基于邻域选取进行修正的局部线性嵌入算法(Based On Neighbors Selecting Modified Local Linear Embedding,简称M-LLE),其他的流形学习算法可以据此进行相应的改进。
1 LLE算法简介
LLE算法是由Roweis和Saul提出的,作为一种经典的流形学习算法,LLE算法利用重构权在高维空间和嵌入空间保持不变的特点,在高维空间构造样本间的重构权,并且在嵌入空间中恢复出样本间的重构关系。因此,LLE算法可以归纳如下:
输入:高维数据集X,邻域参数k,嵌入维数d
输出:低维嵌入坐标Y
Step1.选取邻域 计算样本点xi与其他样本点间的欧式距离,选取距离xi的最近k个样本点,构造xi的邻域集Ni={xij|j=1,2,…k},其中i1,i2,…ik为xi局部邻域点的下标集;
Step2.计算重构权 记Gi=[xi-xij,…,xi-xik],通过求解线性方程
undefined得到xi对应的重构权向量,相应地嵌入到权值矩阵W中;
Step3.计算低维嵌入 计算矩阵M=(I-W)T(I-W)最小的(d+1)个特征值对应的特征向量[u1,u2,...,ud+1],所求的低维嵌入坐标为Y=[u2,u3,...,ud+1]。
2 基于文本分类的改进局部线性嵌入算法
2.1基于邻域选取进行修正的局部线性嵌入算法
假设文本数据中词库的单词数量为D,文本数据u和v可以用向量形式表示为u=[u1,u2,…,uD]和v=[v1,v2,…,vD],D为高维向量的维数。传统的LLE算法仅仅采用欧式距离作为度量距离来构造样本点的局部邻域,即undefined。这种度量方式尽管简单方便,计算量小,但由于文本数据本身庞大稀疏的特点,简单地利用这种度量方式来构造样本点的局部邻域,往往会造成邻域选取的不准确。
在文本分类问题中,有些单词在每类文本中都可能会出现,这些单词可以称之为常用单词;有些单词,只有在专门的文本分类中才会出现,则相应地称之为属性单词。对于流形学习算法,在进行邻域选取时,为了使类别相同的数据能够成为邻域点,可以对不同的单词赋予不同的权值,通过这种差异性来计算文本数据间的距离,从而真正反映数据间的相似程度,即undefined,其中wi为第i个单词的重要性权值。显然,对于常用单词,wi的值应该更小些;而对于属性单词,wi的值应该更大些。
对于权值wi的构造,本文采用的方法如下:由于在文本分类问题中,部分样本数据间的类别信息已经可以提前获得。针对这种半监督问题,可以根据已有的分类文本,统计每个单词在各类文本中出现的次数,如果单词ui在所有类别的文本中出现的次数均较高,则ui就可能是一个常用单词;如果ui仅在一类文本中出现的次数较高,则ui更可能是一个属性单词。因此,对于C类的文本数据,假设单词ui在第Ci类出现的次数为ai,则单词ui的权值wi可以表示为undefined。
因此,本文提出的基于邻域选取进行修正的LLE算法(Based On Neighbors Selecting Modified Local Linear Embedding,简称M-LLE),可以归纳如下:
输入:高维文本数据集X,邻域参数k,嵌入维数d,文本词库集U,类别信息C
输出:低维嵌入坐标Y
Step1.计算权值 由样本的类别信息Ci,计算每个单词ui在每类文本中出现的次数ai,再通过undefined计算每个单词ui对应的权值wi;
Step2.选取邻域 通过dist(xi,xj)=∑rwr(uir-ujr)2,计算距离样本点xi的最近k个样本点,构造xi的邻域集undefined,其中i1,i2,…,ik为xi局部邻域点的下标集;
Step3.计算重构权 记Gi=[xi-xi1,…,xi-xik],通过求解线性方程undefined得到xi对应的重构权向量,相应地嵌入到权值矩阵W中;
Step4.计算低维嵌入 计算矩阵(I-W)T(I-W)最小的(d+1)个特征值对应的特征向量[u1,u2,…,ud+1],所求的低维嵌入坐标为Y=[u2,u3,…,ud+1]。
本文采用带权值的欧式距离作为度量距离来构造文本数据的局部邻域,这种方法可以看做是传统LLE算法的一种推广。这种基于邻域选取进行修正的LLE算法,能够较好地体现出高维空间中文本数据的距离关系,从而更好地对文本数据的邻域进行选择,进而得到准确的低维嵌入坐标;再用现有的分类器对低维坐标进行相应的分类识别,就能够得到较好的文本分类效果。
2.2半监督局部线性嵌入算法
作为流形学习算法与半监督机器学习相结合的产物,SSLLE算法提供了另外一种进行文本分类的思路。
SSLLE算法则是建立在LLE算法的基础上,利用部分已知低维信息的样本点作为监督点,挖掘测试数据低维信息的半监督流形学习算法。SSLLE算法的主要思想是:假设样本数据集X中一些数据点集X1={x1,x2,...,xm}已提前获取其低维坐标Y1=[y1,y2,...,ym](m
在样本点的邻域选取和重构权构造上,SSLLE算法与LLE算法相同。与LLE算法的不同之处在于:在计算低维嵌入坐标时,由于引入了监督点集X1的低维信息Y1,需要对矩阵M进行相应的分块,即
,M11大小为m×m,通过极小化价值函数:
转化为带有约束条件Y1的极小化问题。求解该问题,等价于求解关于Y2的偏导数,并令其为0。因此,可以利用公式M22Yundefined=-MundefinedYundefined计算测试点集X2对应的低维坐标Y2。
这种半监督的流形学习算法,充分利用了样本点已知的低维信息作为监督信息,在计算样本低维嵌入时,通过引入监督点的监督信息来改善最终映射效果,提高分类识别的准确率。因此,在文本分类的实验中,可以利用已知的类别信息,采用SSLLE算法对文本数据进行降维,根据低维嵌入结果yi,i=1,...,N,判断数据点xi对应的类别为undefined,其中C为文本的类别。
3 数值试验
本实验采用的文本数据取自20group_news数据集[12],该文本数据用100个单词组成的逻辑型向量表示,共有16242个文本。整个数据集分为4类,每类的数量各不相同。考虑到内存的容量,本实验对每类数据均随机选取1000个文本,构造一个100*4000的文本分类数据集。
3.1用M-LLE算法对文本数据进行分类
本实验将不同的流形学习算法,如M-LLE、LLE等,分别对高维的文本数据进行降维,再用现有的分类器,如1_NN、NFL,对低维数据进行分类识别。通过识别率的比较,来检验不同算法的降维效果。
3.1.1 不同邻域参数的识别率比较
本组实验,从每类数据中随机选取200个文本样本,构造成1_NN、NFL分类器中的监督点。再用M-LLE、LLE算法对该文本数据集进行降维,实验中,嵌入维数d=30。如表1所示,为邻域参数K取值不同时,1_NN、NFL分类器的识别率比较。
如表1所示,在不同的邻域参数K下,经过改进的M-LLE算法对高维文本数据降维后,在不同的分类器下,其对应的识别率都要高于LLE算法相应的嵌入结果。这表明,M-LLE算法确实能够提供对文本数据的分类能力。
3.1.2 不同嵌入维数的识别率比较
为了更好地说明M-LLE算法能很好地应用于文本分类问题,本组实验对比在不同嵌入维数d下,1_NN、NFL分类器对相应的低维嵌入结果的识别率比较。实验中,随机选取每类数据的200样本作为分类器的监督点。M-LLE、LLE算法的邻域参数K=4。实验结果如图1所示。
从图1可以看出,在不同的嵌入维数下,用不同的分类器对嵌入结果进行识别率的比较,M-LLE算法嵌入结果的识别率都要高于LLE算法的嵌入结果。因此,这也验证了M-LLE算法能够很好地改进LLE算法对于文本数据的分类效果。
3.2用SSLLE算法对文本数据进行分类
本实验中,用SSLLE算法构造的分类器,对高维文本数据进行分类。实验中,随机选取每类数据中的一定数量的样本作为监督点。监督点的类别信息用一个4维的单位向量来表示,即第1类数据的类别信息表示为[1],第2类数据的类别信息表示为[0,1,0,0],第3类数据的类别信息为[0,0,1,0],第4类数据的类别信息为[0,0,0,1]。然后,用SSLLE算法对高维文本数据进行降维,嵌入维数d=4。对于低维嵌入结果,数值最大的分量所对应的标号为相应的类别号。
在本组实验中,从每类数据中随机选取200个文本作为监督点。然后用SSLLE算法构造的分类器进行实验,再利用1_NN、NFL分类器对LLE算法的降维结果进行识别,对比三种分类器的识别效果。实验中,LLE算法的嵌入维数为d=30。如表2所示,为不同邻域参数K下,三种分类器的识别率比较。
4 结束语
本文基于文本数据分类的特点,对流形学习算法做出适当的改进。首先,从文本数据邻域构造的角度出发,提出一种带权值的欧式距离度量方式,能够改善文本数据的邻域构造;第二,引入半监督的流形学习算法,制作成相应的分类器,利用半监督流形学习算法的优势,提高文本分类的效果。
参考文献
[1]T.Jolliffe.Principal component anlysy[M].New York.Springer-Verlag.1986.305-320
[2]边肇祺,张学工.模式识别[M].第二版.北京:清华大学出版社.1999.87-90
[3]D.Lee,S.Seung.Learning the parts of objects by non-negative matrix factorization[J].Nature 1999(401):788-791
[4]J.Tenenbaum,D.Siivad,A.Angford.Global geometric framework for nonlinear dimensionality reduction[J].Science.2000,(290):2319-2323
[5]S.Roweis,L.Saul.Nonlinear dimensionality reduction by locally linear embedding[J].Science.2000,(290):2323-2326
[6]M Beikin,I Niyogi.Laplacian eigcnmaps for dimensionality reduction and data representation[J].Neural Computation.2003.15(6):1373-1396
[7]Z.Zhang,H.Zha.Principal manifolds and nonlinear dimensionality reduction via tangent space alignment[J].SIAM J ScientificComputing.2005.6(1):313-338
[8]A Hadid,M Pietikainen.Manifold learning for gender classification from face sequences[J].In:Proc.3rd IAPR/IEEE InternationalConference on Biometrics.2009,9(16):790-801
[9]A Hadid,M Pietikainen.Manifold Learning for Video-to-Video Face Recognition[J].Biome-tric ID Management and Multimo-dal Communication.2009,7(16):709-716
[10]王靖.流形学习的理论与算法研究[D].浙江:浙江大学大学博士学位论文.2006.
[11]X Yang,H Fu,H Zha.Semi-supervised nonlinear dimensionality reduction[C].Proceedings of the 23th International Conferenceon Machine Learning.2006:1065-1072
流形学习算法 篇5
短期负荷预测是电力系统调度、运行、控制必须面对的重要课题,受到了广泛重视[1,2],已有诸多预测方法[1,2,3,4,5,6,7,8,9,10]。但由于负荷的多样性、复杂性和随时空变化性,现有方法仍然难以满足要求,其中一个重要原因在于研究方法和角度存在一定的局限性。
现有负荷预测研究方法主要分为两类:一类是以时间序列法和回归分析法为代表的传统方法[2,3],另一类是以人工神经网络、最小二乘支持向量机、遗传算法为代表的人工智能方法[4,5,6,7,8,9]。传统方法原理简单,速度较快,但基于一维空间思维,模型过于简单,难以准确刻画负荷变化的复杂规律。人工智能方法通过模拟人类思维能在一定程度上反映负荷的非线性变化规律,预测精度较高,但仍从一维角度对负荷系统进行考虑,丢失了样本数据中可能包含的其他有效信息。实际上,一天中各时刻点负荷值之间本身存在着很强的相关性[10],气温、湿度、日类型等因素也是以天为单位对负荷进行影响,因此可从多维角度出发,对日负荷24维数据进行整体分析与建模,克服现有一维处理方法的不足,从而更好地刻画日负荷变化规律,提高预测结果的准确性和预测方法的适应性。
本文从系统论角度出发,把日24小时负荷看成一个系统,提出一种从整体上刻画和预测短期负荷的新方法,建立高维预测模型。利用流形学习[11,12,13,14,15]方法对建立的高维空间模型进行有效降维,在降维空间内对短期负荷进行预测。通过局部线性嵌入法(Locally Linear Embedding,LLE)[13,14,15]对24维空间模型进行非线性降维,进而有效提取高维空间数据的固有属性和整体规律,采用最小二乘支持向量机[5,6,7,8](Least Square Support Vector Machines,LS-SVM)模型在低维空间进行负荷预测后,用LLE重构得24个时刻的预测值。将本文方法用于国内某地区电网进行建模预测,并将预测结果与一维预测结果进行比较,证明本文方可行性和正确性。
1 负荷系统高维预测模型及其特点
电力负荷系统是一个多维非线性系统[10],短期负荷预测,如日负荷预测,需根据现有历史数据资料,预测出未来一天或数天多个时刻点(如24、48、96、288)的负荷值。设已有N天24点负荷数据X'(n)=[X1'(n),X2'(n),,X24'(n)]T(n=1,2,,N),共24*N个点,由于多维时间序列预测的有关理论尚不成熟且计算量一般较大,现有方法大多从一维角度进行分析,即把X'(n)按小时类型看作24个X'(n),形成24类训练、预测样本,分别进行24次建模预测。文献[10]对河北电网和京津唐网某年日24小时负荷值序列进行了相关性计算,发现相邻点时间序列之间的相关系数最小为0.875 8,最大为0.9954,非相邻点相关系数最小为0.665 2,由此可见,一天中各时刻负荷值之间存在着很强的相关性,将其分为24个一维序列分别建模,忽略了各时刻负荷值之间的整体性和相关性,损失了许多有价值的信息。可对该24维数据集进行整体分析,从多维角度挖掘历史数据中所蕴含的有效信息,从而更准确地刻画日负荷变化的规律。
将N天24小时历史负荷记作X=[X1,X2,…,XN],其中每个Xi为一个24维数据,即Xi=[Xi1,Xi2,,Xi24]T,由于电力负荷系统本身是一个复杂非线性系统,影响因素多,波动规律复杂,由N天24小时负荷值组成的24维数据集,其蕴含的有效信息和内在规律难以直接感知和认识,需要借助相应的数据分析和约简方法来实现该高维空间数据的挖掘。解决这种高维空间数据挖掘问题的重要手段之一便是对高维数据进行降维[16],通过降维剔除原始数据中的噪声和冗余信息,在尽可能少损失信息的条件下将其转换为低维数据,进而在低维空间中提取高维数据的固有属性和整体几何规律,揭示其蕴含的有效信息。本文基于流形学习理论[11,12,13,14,15]对24维负荷数据进行分析,采用局部线性嵌入法[13,14,15]对其进行非线性降维,得到N个d(d<24)维数据Y=[Y1,Y2,…,YN](各Yi维数为d),降维空间内的d维序列互不相关,可对该d维序列分别进行预测,再对d维预测值进行LLE重构得到24点负荷预测值。
2 基于流形学习的模型降维与重构
2.1 流形学习原理
随着信息技术的不断发展,人们获取数据与存储数据的能力大大增强,且所获取的数据大多为高维度数据。对于高维数据集,利用现有方法很难直接感知其内在规律,必须借助于各种数据分析和约简方法来理解数据并揭示其中蕴涵的有效信息,这一过程可称作数据的信息刻画。从数据到信息是一次从量变到质变的飞跃,需要有效的学习方法,其中,流形学习是一种用于对高维数据进行降维的非参数方法。
2000年,《科学》杂志(Sicence)上发表了3篇论文[11,12,13],从认知上讨论了流形学习,并首次使用了manifold learning术语,标志着以非线性为主要特征的流形学习方法诞生。流形学习的定义如下:设Y⊂Rd是一个低维流形,f:Y→RD是一个光滑嵌入,其中D>d,数据集{Yi}是随机生成的,且经过f映射为观察空间的数据{Xi=f(Yi)},流形学习就是在给定观察样本集{Xi}的条件下重构f和{Yi}。流形学习方法的基本思想是每个高维空间内的流形都有一个低维空间内的流形与之对应,并试图找出一个光滑映射,把高维源数据映射成其低维目标空间内的对应,其主要目的,是在没有任何先验假设的情况下,揭示所研究数据蕴含的整体几何规律,即从观测的现象中去寻找事物本质,找到产生数据的内在规律。现有流形学习方法主要包括:局部线性嵌入法[13,14,15]、等距映射算法[12]、多维尺度法[12]、拉普拉斯特征映射算法[14]等,研究发现,局部线性嵌入法(LLE)在电价、电力负荷数据的分析建模上应用性能较好[15]。
2.2 局部线性嵌入法
LLE是一种通过局部线性关系的联合来揭示全局非线性结构的非线性降维方法,它在保持数据的邻域关系下,计算高维输入数据在低维空间中的嵌入流形[14]。与其他降维方法相比,LLE降维法有很多优势:(1)它对非线性流形结构数据具有自适应性;(2)它只涉及到较少的参数选择问题;(3)由于它保持了数据在高维空间的内在拓扑结构,其信息损失很小。
设高维欧氏空间RD中有数据集X={X1,X2,…,XN},数据集位于本征维数为d(d<
第一步,邻域选择。计算每个样本点Xi(i=1,2,…,N)的邻域点(取距离最近的K个邻域点或固定半径的球状邻域)。
第二步,计算重构权Wij。在Xi的邻域中,计算能最好地重构每个Xi的权值矩阵Wij,使下列目标函数E(W)最小。
式中:N为样本点的个数;K为邻域点的个数;Xj(j=1,2,…,K)为Xi对应的K个邻近点;Wij是Xi由Xj(j=1,2,…,K)线性重构的一组加权值,Wij满足下面两个约束条件,如式(2)～式(3)。
Wij=0 Xj不是Xi的邻近点时(2)
式中:Xi表示第i个样本点;Xj表示第i个样本点的第j个邻近点。
第三步,计算d维嵌入值Yi。使下列重构误差φ(Y)最小。
式中:Yi为各样本点Xi的低维嵌入向量,Yj为对应Yi的K个邻近点。
为了保证公式(2)能得到唯一解,低维嵌入Yi需满足下面两个约束条件,如式(5)～式(6)。
式中,I为单位矩阵。求解式(2)等价于求一个稀疏、对称、半正定矩阵M的特征向量,即。
式中,W为重构权矩阵。取M最小的d+1个特征值对应的特征向量按升序排列,丢掉第一个特征值对应的特征向量,剩下的d个特征向量组成的矩阵就是所求的低维嵌入向量Y。
2.3 LLE重构
给定一组嵌入式低维空间的特征向量,LLE重构则是基于这组标准数据找出高维空间中与其对应的数据集。假设我们已经通过LLE得到了低维空间的特征向量Y={Y1,Y2,…,YN},把新的低维向量记作Y0。LLE重构法则可用来基于X={X1,X2,…,XN}和Y={Y1,Y2,…,YN},找到高维空间原始数据点X0近似值X0。具体步骤[15]为
第一步,在Y={Y1,Y2,…,YN}找出离新的特征向量Y0最近的K个邻近向量。
第二步,计算权重系数Wj,使得下列目标函数E(W)最小。
式中:Y0为需重构的低维向量;Yj(j=1,2,…,K)为Y0的K个邻近点。
约束条件为
第三步,高维空间中的数据X0可由式(10)重构得到。
假设X0(j)是向量X0的第j个组成元素,X0的重构误差(RE)定义为
式中,1≤j≤D,D为高维空间维数。
整个数据集X的重构误差(TRE)定义为
3 基于流形学习的LLE短期负荷预测模型与方法
3.1 数据预处理
(1)异常数据处理。电力系统负荷建模需要大量的历史数据,而历史数据大多通过电量采集器或远动系统采集得来,除了受测量设备本身或数据传输中造成的不准确数据及缺失数据外,还有由于各种随机因素影响造成的非正常负荷值。因此历史负荷数据中往往包含非真实数据,即“异常数据”,需要剔除这些非真实数据,保证资料的完整与准确[7]。本文采取的方法是取该点值前后两点正常负荷值的平均值来替代该异常点。
(2)对数转换。一天中各时刻的负荷值波动范围较大,对其进行对数转换后可使流形学习在低维空间的分布更加均匀,从而提高流形学习的有效性并减少数据集的重构误差[15]。
3.2 最小二乘支持向量机(LS-SVM)预测
支持向量机(SVM)是由Vapnik等在20世纪90年代中期根据统计学理论提出的一种新的机器学习方法。该方法建立在统计学习理论的VC维及结构风险最小化原则的基础上,通过求解一个二次规划问题较好地解决了小样本、非线性、高维数和局部最小点等实际应用问题,与传统基于经验风险最小化的神经网络方法相比,该方法具有学习速度快、全局最优和泛化能力强的优点,被认为是神经网络的替代方法[5,6]。最小二乘支持向量机(LS-SVM)是标准SVM的一种扩展,其优化指标采用平方项,并采用等式约束代替标准SVM的不等式约束,将二次规划问题转化为线性方程组的求解,降低了计算复杂性,加快了求解速度,在电力系统短期负荷预测领域得到了广泛的应用[7,8]。
3.3 基于流形学习的LLE短期负荷预测模型
对预处理后的数据进行整体分析,将每天24小时负荷值看作一个观察值。研究发现,本征维数d取3最适合用于描述跨时负荷之间关系的描述[17]。表1给出了对国内某地区电网日负荷数据降维后,低维空间3个维度序列与原始高维日负荷数据统计值(包括平均值、标准差、变异系数、极差)关联性较大的维坐标,及其对应的相关系数值。
由表1可以看出,对高维负荷数据进行降维后的低维空间特征向量序列能够反映原始高维数据相应的动态变化规律,对其进行分析建模可进行方便、准确的负荷预测。考虑相关影响因素,对低维空间各特征向量序列分别采用LS-SVM分析建模,再对低维空间各序列预测值进行LLE重构,得到预测日的24点负荷预测值。具体流程图如图1所示。
4 算例分析
4.1 数据样本和来源
为了验证本文方法的可行性和正确性,以国内某地区电网2009年2月13日～5月9日93天的日24小时负荷数据作为基础数据,分别采用本文所提出预测方法和一维分量预测法对该地区5月10日～5月16日一周的24个整点时刻负荷值进行仿真预测,预测模型采用LS-SVM算法,核函数为高斯径向基函数。
4.2 参数分析
最小二乘向量机算法中,参数C和б对预测精度有直接影响[6,7],C值过小易造成对训练数据造成欠学习现象,过大易对训练数据造成过学习现象而导致泛化能力下降,宜设置为1～100;б过小易对训练数据造成过学习现象,过大则造成欠学习现象,宜设置为0.1～10。此外,不敏感损失函数中的参数ε值越大,支持向量数目越少,预测精度也越低,本文取ε=0.001。
LLE算法的本征维数d和邻域点个数K对预测精度也有较大影响。本征维数d可采用文献[17]中的邻近算法进行评估,本文d=3;邻域点个数K可根据其与该数据集重构误差TRE影响关系进行确定[15],开始的时候TRE随着K值的增大急剧减小,达到一定值后趋于稳定,本文取K=38。
4.3 误差测量与结果分析
用相对误差e作为判断各方法预测结果的依据,即
式中:xi为i时刻的预测负荷值;yi为i时刻的实际负荷值。本文以3%作为最大允许误差(Maximum Permit Error,MPE),若某点的e>3%,则判定该点预测结果为不合格。定义某预测日负荷预测结果的合格率为预测误差小于3%的点与总预测点的比值。
将预测所得结果与预测日实际负荷值做比较,采用式(13)进行误差计算。表2列出了采用本文方法和一维分量预测法对国内某地区电网一周预测结果的对比。表3给出了该电网5月14日的日24小时预测值结果。
从表2和表3数据可以看出,采用本文所提出方法进行日24小时负荷预测,预测的精度得到了有效提高。根据表3所列出对国内某地区电网2009年5月14日的24小时预测结果,采用一维分量预测,平均预测误差为1.95%,日最大误差为5.15%;而采用本文方法预测,平均预测误差为1.41%,日最大误差为3.50%。图2给出了两种方法在2009年5月14日24小时负荷预测误差(绝对值)对比曲线。
以2009年5月14日本文方法预测平均误差1.41%为例,误差控制在该精度范围内的预测点数,一维分量预测方法为41.67%,本文方法为62.5%。采用一维分量预测合格率为79.17%,采用本文方法预测合格率为95.83%。同时,进行日24小时负荷预测,采用一维分量预测所需平均时间为3.74 s,而采用本文方法平均时间仅为1.23 s。由此可见,本文所提出方法预测精度高、速度快。
5 结论
(1)考虑到日24小时负荷之间的整体性与相关性,从多维角度对其进行整体分析与建模,更能准确地刻画日负荷复杂的波动规律。
(2)流形学习是一种对高维数据进行有效降维的非参数方法,通过LLE对高维负荷数据进行非线性降维,剔除其中的噪声和冗余信息,挖掘原始高维数据的内在规律,揭示其中蕴含的有效信息。
(3)采用LS-SVM方法在降维空间进行负荷预测,再通过LLE重构得到日24点负荷预测值。该方法充分考虑了日24小时负荷之间的相关性,仅需对低维空间少数几个不相关的序列进行LS-SVM建模,降低了建模复杂度。算例分析表明,本文方法相比于传统一维分量预测法,有效地提高了速度和精度。
流形学习算法 篇6
关键词：流形学习,拉普拉斯特征映射,局部线性嵌入,头部姿态估计
人脸识别一直以来都是计算机视觉和模式识别研究中的热点问题, 作为生物特征识别的关键技术之一, 其特定条件下的人脸识别取得了很大的进展, 但头部姿态变化是其中的瓶颈。为了实现对不同头部转动姿态的人脸识别, 估计人脸头部姿态因而具有重要的研究意义和实用价值。流形学习自从2000被提出以来, 到现在已经有众多的方法用来解决人脸识别, 姿态估计还有维数约简等方面的实际问题。流形学习理论假设数据是采样于一个高维欧氏空间中的低维流形上, 并从高维观测数据中发现并找到潜在的低维流形结构, 并构造高维空间到低维空间嵌入的非线性映射或者线性映射, 以实现维数约简或数据可视化。目前提出的流行学习方法中比较有影响力的, 包括等距特征映射算法 (ISOMAP) 、局部线性嵌入算法 (LLE) 、拉普拉斯特征映射算法 (LE) 等。而具有头部转动姿态的人脸图像很自然地看成一个具有特定低维流形结构的高维空间, 因此采用流形学习进行人脸头像的头部姿态估计获得了比较大的关注, 比如Balasubramanian等人将流形嵌入扩展到监督学习领域并进行头部姿态估计;BenAbdelkader等人提出了监督流形学习框架用于头部姿态估计的方法。
本论文融合LE和LLE算法, 提出监督Laplacian LLE流形学习算法, 针对传统流形学习算法无法获得直接的显式映射的问题, 提出用正则化最小二乘来学习直接的显式映射。而且实验验证了我们算法比对比的算法能更加有效地的提高头部姿态估计的准确率。
一、基于监督的Laplacian LLE流形学习算法
如果存在一组具有嵌入头部姿态流形的数据集, 观测空间中的每个样本点被假定是其邻域内的近邻数据点的加权组合, 同时针对数据集的局部近邻关系, 数据集的头部姿态样本近邻需要得到保持, 因此融合LLE和LE的算法思想, 提出Laplacian LLE算法, 如下:
Step 1:给定数据集其中为样本总数, 是的类别标记, 搜索数据集中每个的个最近邻;
Step 2:定义, 考虑约束, 按照最小方差准则求解用于LLE项的权矩阵。
Step 3:定义局部近邻的高斯核权值用于LE项:- (47) xi-xj (47) 2
Step 4:定义Laplacian LLE的目标函数:
其中Ù*=a r g mÙi nφ () 。考虑约束。式 (2) 可重写为求解Y (M+λL) YT, 的最小化问题。Y*的最优解是求矩阵 (M+λL) 的一组最小本征向量。由约束可知, 本征值为零时, 需要去除, 此时数据集会坍缩至一个点。因此获得的低维方法是计算矩阵 (M+λL) 的最小 (l+1) 个本征向量, 并舍弃 (l+1) 中的最小本征值对应的本征向量。
上述提出的Laplacian LLE算法能够探索和保持数据集本身具有的特定的局部几何结构, 对于监督学习来说, 要加入监督的类别标签信息来进一步提高头部姿态估计准确率。根据SML框架的原理, 加入, 用于监督学习问题中, 其中，
因此监督Laplacian LLE算法描述如下:
上式可推导为:YT MY+λYT LY+αYT LΛY, 其中, 。此外, 针对欧式空间的距离度量仅仅定义为样本之间的欧式距离, 由于噪声和冗余信息等因素会造成欧式距离近邻的点并非真正的同类别近邻, 我们加入一个偏差系数来引导欧式距离近邻项同类别近邻靠近, 根据BME[5]的思想, 我们对确定局部K近邻的欧式距离加入一个系数, , 其中, 表示样本之间的类别标记距离, β都为控制参数。这样局部K近邻Nk的距离定义为, 其中D (i, j) 为欧式空间度量。
监督Laplacian LLE嵌入能生成一个仅仅定义在训练数据样本上的低维嵌入, 但是监督分类来说则需要个一个显式的映射f能很好的处理样本外扩展 (outof-sample extension) 。考虑一个线性映射, 我们通过线性变换y=aT x来获得映射f, 这是线性流形学习采用的方法, 如LPP等。实际上, 这个线性映射可能并不存在。因此我们把我们的算法分为两步, 第一步使用监督Laplacian LLE求得低维嵌入, 第二步则可以采用Tikhonov正则化来拟合从高维输入数据到低维嵌入数据:
特别注i意此处的是样本的低维嵌入而不是样本类别标记。 (5) 式可以推导为一个闭式解=, a (XXT+γI) -1Xy, 那么线性映射矩阵A则由d个解向量1a, a2, ..., ad构成。很自然地, 通过 (5) 式获得的直接的显式线性映射f能够充分处理样本外扩展, 同时考虑到训练数据的映射到的低维子空间和测试数据的低维映射子空间的一致性, 我们把训练数据和测试数据使用线性映射都投影至同一低维子空间, 然后再低维子空间的K近邻分类算法则能充分有效的进行头部姿态估计。
二、实验
实验部分主要采用FacePix数据集, 示例如Fig.1。FacePix数据集包含30个主题, 每个主题包含181幅图像, 姿态转动角度为[-90, +90]。我们实验使用15个主题, 并且使用留一法 (leave-out-one) 进行验证, 即最后一个主题作为测试其余作为训练。
Table 1显示了我们的算法与LE+RLS、LLE+RLS的在不同的头部姿态采样率下的头部姿态估计MAE比较, 显示我们的算法更稳定并且其MAE (Mean Absolute Error用来评价估计的头部姿态与真实姿态的绝对偏差) 值更低更加有效。Fig.2显示了我们的算法与LE+RLS和LLE+RLS算法在不同的嵌入维数下的MAE的比较, 结果同样显示在不同的嵌入维数下我们的算法更加鲁棒有效。因此我们提出的S-Laplacian LLE算法有效的提高了头部姿态估计的准确率。
三、结论
我们提出了一种两步 (two-step) 的监督Laplacian LLE流形学习方法, 用于头部姿态估计问题, 采用监督Laplacian LLE流形嵌入和正则化最小二乘方法结合来有效的处理地维嵌入和样本外扩展问题, 实验结果显示我们的算法有效地提高的头部姿态的准确率。
参考文献
[1]M.E and Trivedi, M.M, Head pose estimation in computer vision:A survey, in:PAMI, 31, 2009, pp.607-626.
[2]J.Tenenbaum, V.Silva, and J.Langford, A global geometric framework for nonlinear dimensionality reduction, in:Science, 290, 2000, pp.2319-2323.
[3]K.S.Lawrence and T.R.Sam, Think globally, fit locally:unsupervised learning of low dimensional manifolds, in:Journal of Machine Learning Research, 4, 2003, pp.119-155.
[4]M.Belkin and P.Niyogi, Laplacian eigenmaps for dimensionality reduction and data representation, in:Journal of Neural Computation, 15, 2003, 1373-1396.
[5]V.N.Balasubramanian, J.Ye, and S.Panchanathan, Biased manifold embedding:a framework for person-independent head pose estimation, in:CVPR, 2007.
[6]C.BenAbdelkader, Robust Head Pose Estimation Using Supervised Manifold Learning, in:ECCV, 2010, Part VI, LNCS6316, 518-531.
流形学习算法 篇7
船舶柴油机作为船舶动力的重要装置, 其能否正常运行对整个船舶有直接影响, 船舶柴油机一旦发生故障, 如果得不到及时处理, 将会给整个营运过程带来重大损失, 甚至还会危及人们生命财产安全。对船舶柴油机进行故障诊断和状态监测, 能及时发现船舶潜在的隐患, 并采取有效措施避免隐患发生, 极大地降低了柴油机的故障发生率, 从而有效保证柴油机正常运转, 同时, 对节省维修费用和避免重大事故等也具有深远意义。
1 流形学习的基本概念
流形学习主要是以微分流形、拓扑学和变分学等为理论基础, 用来描述所有事物的空间存在形式。流形学习的实质是从豪斯多夫空间到欧氏空间的一系列映射过程。假设在豪斯多夫空间M中存在任意样本a, 均存在于邻域U与n维欧氏空间中的某一特定子集中, 那么就可以认为M属于一种d维流形。流形学习的主要目的是:保证在拓扑空间中具有相近或相同属性的高纬流形数据, 降维到低维空间后, 这些高维数据仍可保留相同或相近的属性特征。目前, 流形学习法虽然在一些图像识别等基础领域已得到广泛应用, 但在机械故障诊断方面还处在发展阶段。现阶段, 机械领域对流形学习的研究工作也主要集中在弱冲击的信号提取、噪声的去除及状态的识别和趋势分析等层面。
1.1 弱冲击信号的提取和噪声的去除
柴油机系统, 其结构特征之一就是复杂性程度较高, 在加上测试环境的不稳定性, 在柴油机振动故障的诊断过程中, 或多或少地会受到机械运行噪声的影响, 消除噪声干扰能有效保证柴油机故障诊断的精度, 且还能及时发现早期故障特征, 杜绝柴油机振动故障的发生。流形学习作为机械学习和模式识别的热点之一, 在弱冲击信号的提取和噪声的去除等方面发挥着重要作用。
1.2 状态的识别
在柴油机的运行状态中, 多个指标参数之间都存在重叠, 传统方法不能完整地对复杂设备的运行状态进行描述, 因此, 通过流形学习的优势, 有效地将多维的特征指标进行融合, 同时, 有效去除存在于指标间的冗余成分, 保证准确提取设备运行状态的有效特征, 这已成为当前研究的热点之一。
1.3 状态趋势分析
通过流形学习的方法, 建立机械状态预测模型, 并和其他一些机械运行指标结合, 有效完成了对设备状态变化趋势的描述, 从而能更好诊断出柴油机振动故障的发生时间, 同时还能更好地把握机械设备的剩余使用寿命。
虽然经过不断的研究和实践, 流形学习法在柴油机等机械设备的振动故障诊断方面已经取得了突破性的进展, 但还存在着某些不足, 如流形学习法和柴油机振动故障信号间的匹配问题还有待改善, 尤其是如何降低柴油机振动噪音以避免影响流形学习诊断的精确度, 如何改进、完善流形学习算法, 从而保证保留有效信息, 等等, 这些都需要后期持续完善。
2 基于流形学习的船舶柴油机振动故障诊断分析
2.1 概述
流形学习法属于一种无监督降维的方法, 具备良好的维数精简功能, 近年来, 受到各方学者的高度关注。流形学习认为, 存在于高纬空间的数据都具有一定的低维流形结构, 通过流形算法对相应低维嵌入的求解, 进而实现高维空间数据的低维转化, 并实现数据的可视化。简单来讲, 流形学习就是透过现象来研究数据本质, 挖掘数据的内在规律, 进而实现数据维数的约简。
2.2 船舶柴油机振动信号的指标特征分析
2.2.1 时域性特征
时域性特征指的是通过对柴油机振动信号的直接利用, 来计算相关的结果, 属于一种最直接而又简便的数据处理方法。对时域性特征指标的提取又分为无量纲型和有量纲型两大类。在利用有量纲型的指标参数进行柴油机的状态分析比较过程中, 要严格保证柴油机运行参数和测点位置的高度一致性, 否则分析的结果就不能准确说明问题。在利用无量纲型进行振动振幅分析时, 其计算结果只和柴油机的运行状态有关, 而与其他运行参数无关, 所以, 一般情况下, 对柴油机振动故障的诊断, 都应用无量纲型的指标来进行分析对比。
2.2.2 频域特征
对柴油机这一类别的旋转型机械, 具有十分复杂的振动信号, 这也是由于柴油机振动故障的加深而引发其他部位共振导致的;此外, 不同故障类型的冲击规律也不尽相同。因此, 利用时域指标, 很难对其进行特性分析。而频域性指标能更好地描述机械不同类型的故障冲击规律, 为现阶段的柴油机故障类型和故障原因分析提供了一套行之有效的方法。
2.2.3 时频域特征
傅里叶变化通常针对的是振动信号的全局变换, 而无法对平稳信号的局部统计进行描述, 而对故障诊断过程中的非平稳信号, 随着时间的变化, 其统计特征也发生相应改变;此时, 就需要同时考虑时域性和频域性, 也就是所谓的时频域性分析。通常用到的时频域分析方法有小波分解、短时傅里叶变换、希尔伯特变换等。
2.3 基于流形学习法的船舶柴油机故障诊断分析
船舶柴油机复杂的结构特性, 也使其故障诊断工作呈现出复杂化的特点。一般情况下, 船舶柴油的故障原因与故障预兆间呈现出的往往是一种毫无规律的非线性关系, 这也直接加大了对船舶柴油故障诊断工作的难度。流形学习法属于一种基于统计学理论的故障处理方法, 能有效处理传统方法不能处理的非线性关系。该方法在处理非线性关系过程中的基本思路是将处在高维特征空间的数据关系, 通过一定的函数关系, 成功将其映射到低维空间中, 然后再描述其非线性的数据关系。流形学习法经过近几年的发展和应用, 在取得显著成果的同时, 也逐渐成为一大热点研究内容。流形学习法凭借自身特有的优势, 在解决小样本、高维模式识别和非线性等多项常规方法不能解决的问题中发挥出了重要作用, 因此, 流形学习法在船舶柴油机的振动故障诊断过程中较为适用。虽然基于流形学习法的船舶柴油机故障诊断技术现在还只是处在起步阶段, 但根据其应用成果来看, 该技术具有较强的实用性和可行性。相信随着技术的不断进步, 基于流形学习法的故障诊断技术在船舶柴油机故障诊断工作中将会取得更为广泛的应用, 将发挥出更大的实际效果。
3 结语
本文介绍了流形学习方法的基本原理, 并在此基础上提出基于不同维数的流形学习算法。对柴油机振动故障诊断过程中的参数指标的时域性特征和频域性特征及时频域性特征进行分析。经研究发现, 流形学习方法在船舶柴油机故障诊断过程中具有重要作用。但同时, 当前的船舶柴油机故障诊断中的流形学习法还处在起步阶段, 在某些方面还存在一定的缺陷和不足, 还需要后期不断地进行研究改进。
摘要：船舶柴油机是一个复杂程度较高的系统, 其复杂性的构造和工作原理增加了其产生故障症状的复杂性和故障诊断工作的困难性。一般情况下, 船舶柴油机故障原因和故障预兆间呈现出一种错综复杂的非线性关系, 且在各个参数间也存在较强的非线性和耦合性, 所以, 诊断船舶柴油机故障, 往往是顺应船舶柴油的这一复杂性结构要求而采用非线性手段对其进行相应的故障诊断和状态监测。流形学习法就是这样一种方法。随着流形学习算法被广泛应用于机械故障诊断领域, 其已成为我国模式识别研究领域中的一个热点问题。但目前, 流形学习在柴油机故障诊断过程中的应用还存在一定缺陷。本文基于流形学习的基本理论原理进行探讨, 并着重对流形学习法在船舶柴油机振动故障诊断方面的应用进行归纳和总结。
关键词：船舶柴油机,流形学习,振动故障,诊断
参考文献
[1]苏祖强, 汤宝平, 姚金宝.基于敏感特征选择与流形学习维数约简的故障诊断[J].振动与冲击, 2014, (3) :70-75.
[2]王冠伟, 张春霞, 庄健, 等.流形学习在机械故障诊断中的应用研究[J].工程数学学报, 2012, (4) :593-599.
[3]郭江华, 侯馨光, 陈国钧, 等.船舶柴油机故障诊断技术研究[J].中国航海, 2005, (4) :75-78.
【流形学习算法】推荐阅读：
滑模学习算法06-29
迭代学习算法08-26
RLS学习算法05-31
深度学习算法存在问题06-06
学习感想-学习感想 个人学习心得体会08-28
学习演讲稿2018：向雷锋学习与学习演讲稿：努力学习09-16
勤学习≠会学习09-18
合作学习学习心得06-15
学习通知学习要求08-20
勤奋学习善于学习09-12