基于流行学习的降维算法研究
来源:用户上传
作者:陈小军
摘要:流行学习一直是深度学习、机器学习、人工智能的研究热点,其是非性降维算法中非常重要算法思想。流行学习利用局部与欧式空间是同胚空间的概念,将高维数据空间嵌入低维流行结构,用低维局部欧氏特征表示高维数据结 构。文章介绍了流行学习的基本概念、经典算法思想,对经典算法思想进行分析比较,并提出有待进一步分析和研究的问题。
关键词:降维算法;非线性降维;流行学习;机器学习
0引言
随着 M2M(Machine to Machine,M2M)、SNS(Social Networking Services,SNS)、移动互联网的兴起,人工智 能(Artificial Intelligence,AI)、模 式 识 别(Pattern Recognition)、机器学习ML(Machine Learning,ML)、人工神经网络 ANN(Artificial Neural Network,ANN 、深度学习(Deep Learning)、数据挖掘(Data Mining)、计算机 视觉(Computer Vision)等已成为众多学者的研究热点。由于原始数据经常是Web数据、图像、视频等半结构化、非结构化的高维数据,如果直接对原始数据进行清 洗、分 析,很 容 易造成维数灾 难 问 题(Dimension Disaster)。因此需对高维的原始数据进行降维。通过降维,能有效地避免维数灾难问题,提高计算效率、节 省计算资源[1-3]。
现有的经典降维算法主要分为线性降维算法和非线性降维算法,其中线性鉴别算法LDA(Linear Discriminant Analysis,LDA)与主成分 分 析PCA (Principal Component Analysis,PCA)算法是两种经典的线性降维算法[1]。LDA算法是对原始数据的类别进 行降维,属于有监督降维算法,PCA算法是对原始数据的维度直接进行维数约简,属于无监督算法。LDA算法和PCA算法需要假设原始数据服从高斯分布,降维 时存在小样本 SSS(Small Sample Size,SSS)问题以及样 本外(Out of Sample)问题。非线性降维算法主要是流 行学习降维算法、张量降维算法。本文主要介绍基于流行学习(Manifold Learning)的经典降维算法,并进行 分析和比较。
1流行学习概念
流行学习(Manifold Learning)是借鉴了拓扑流行 概念的一种降维方法。流行是位于局部与欧氏空间同 胚的空间,高维数据样本虽然在全局空间不具有欧氏 空间的性质,但是在局部空间中仍具有欧氏空间的特点,因此可以在局部欧氏空间建立映射关系,用低维流 行嵌入到高维空间中然后再设法将此映射推广至全 局。边缘 Fisher算法(Margin Fisher Analysis,MFA)、近邻鉴别投影 NDP(Neighborhood Discriminant Projection,NDP)、NPE算法(Neighborhood Preserving Embedding,NPE)、LDE(Local Discriminant Embedding,LDE)等算法属于流行学习算法中较为经典的算法。
2流行学习的主要算法
2.1边缘 Fisher 分析算法
边缘Fisher分析MFA算法(Margin Fisher Analysis,MFA)主要是利用图嵌(Graph Embedding,GE)方法来构建本征图和惩罚图,本征图是用于描述 类内数据的紧密性,惩罚图是用于描述类间数据的分 离性。本征图是由每个样本点的最近同类 KNN(K-Nearest Neighbors,KNN)构成,在KNN图中,每个点对应于一个样本数据,如果 KNN点是该样本点的KNN近邻点,且属于同一类别,则两点之间添加一条边。以此方法,遍历所有样本点的所有KNN 同类样本点。惩罚图是由每个样本点的异类 KNN近邻点构成,惩罚图中的每个点对应一个样本数据,如果 KNN点是该样本点的所对应的KNN近邻点,并且属于异类,则在惩罚图中的两点之间添加一条边。
MFA算法是利用PCA 降维后,分别构建用于描述类内紧密性的本征图、类间分离性的惩罚图。在本征图中,如果样本点i和样本点j 互为同类的KNN近邻点,则权重 wij=1,否则权重 wij=0;同样地,在惩罚图中,如果样本点i和样本点j 互为异类的KNN近邻点,w=1,如果为同类点则 w=0。MFA 比值鉴别:
2.2NPE算法
近邻 保 持 嵌入 NPE(Neighborhood Preserving Embedding,NPE)算法属于子空间流行学习算法,通过保存数据原始流形空间的局部近邻结构来实现,即每个数据点都能用其近邻点线性表示,能较好地解决样 本外(out of sample)的问题。NPE算法的主要思想:设定原始数据空间中有m个数据,每个数据对应一个节点,第 i个节点对应原始数据空间中的第i个数据。邻接图通过KNN和ε邻域两种方法来构建,如果用KNN
方法构建邻接图,则该邻接图是有向图;如果用ε邻域方法构建邻接图,则该邻接图是无向图。
NPE算法用KNN方法构建邻接图,每个数据用其余KNN数据来表示,该算法的重点是计算KNN近临数据或节点之间的权重系数。在低维的子流形空间中,通过每个数据点的近邻及其线性相关系数重构高纬子空间的局部几何特性。数学表达式:
Wij是xi用xj近似线性表示的权重系数。为了消除在投影子空间中远距离的点,加入任意缩放因子:XMXT a=λXXT a,M矩阵是对称半正定矩阵,约束条件 yTy=1,即 aTXXT a,其中 M=(I-W)T(I-W),I是单位矩 阵 E,利用SVD 奇异值分解求得最优特征向量与特征 值,得到由最优特征向量构成的投影子空间[4]。当使用NPE算法进行降维时,KNN近邻中的K以及ε两个参数,需要根据模型多次训练的结果不断进行调整。
nlc202208292053
转载注明来源:https://www.xzbu.com/8/view-15438714.htm