引用本文

陈晓云, 廖梦真. 基于稀疏和近邻保持的极限学习机降维. 自动化学报, 2019, 45(2): 325-333. doi: 10.16383/j.aas.2018.c170216

CHEN Xiao-Yun, LIAO Meng-Zhen. Dimensionality Reduction With Extreme Learning Machine Based on Sparsity and Neighborhood Preserving. ACTA AUTOMATICA SINICA, 2019, 45(2): 325-333. doi: 10.16383/j.aas.2018.c170216

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2018.c170216

关键词

极限学习机，近邻表示，稀疏表示，降维 

摘要

近邻与稀疏保持投影已被广泛应用于降维方法，通过优化得到满足近邻结构或稀疏结构的降维投影矩阵，然而这类方法多数只考虑单一结构特征.此外，多数非线性降维方法无法求出显式的映射函数，极大地限制了降维方法的应用.为克服这些问题，本文借鉴极限学习机的思想，提出面向聚类的基于稀疏和近邻保持的极限学习机降维算法（SNP-ELM）.SNP-ELM算法是一种非线性无监督降维方法，在降维过程中同时考虑数据的稀疏结构与近邻结构.在人造数据、Wine数据和6个基因表达数据上进行实验，实验结果表明该算法优于其他降维方法.

文章导读

随着大数据时代的到来, 人们对数据的处理正面临巨大挑战.在大数据应用研究中, 高维数据分析与研究是其主要内容之一.在现代机器学习与统计学的研究背景下, 高维数据所引发的维数灾难主要表现为:众多低维空间中表现良好的算法在面对高维数据时性能急剧下降.其主要原因有: 1)维数增加导致数据空间体积急剧膨胀、同等数量样本分布非常稀疏, 难以形成有效的簇; 2)高维空间中存在测度``集中现象", 使样本点间距离度量的类区分性随着维数增加而减弱; 3)样本数据包含大量冗余信息对聚类或分类无用, 甚至会降低算法的性能.基于上述原因, 对降维方法进行研究是十分有必要的.

总体上说, 面向聚类的降维方法均为无监督降维方法, 可分为线性降维和非线性降维.当前, 多数无监督线性降维方法假设观测数据落在一个低维流形子空间中, 通过寻找高维空间到低维子空间的线性投影实降维, 如主成分分析(Principal component analysis, PCA)[1]、局部保持投影(Locality preserving projections, LPP)[2]、近邻保持嵌入(Neighborhood preserving embedding, NPE)[3]和稀疏保持投影(Sparsity preserving projections, SPP)[4]. PCA是最经典的线性降维方法, 以最大化投影散度为目标, 但未考虑样本间的近邻结构关系, 不适合分布于流形上的非线性数据; LPP和NPE则考虑了样本间的近邻结构, LPP以保持降维前后样本间的近邻关系不变为目标, 而NPE旨在保持降维前后样本间的局部近邻结构; SPP的优化目标是使降维前后样本间的稀疏表示结构得以保持.但当数据非线性分布时, 上述线性降维算法就会失效.为弥补线性降维算法的不足, 各种非线性扩展方法被提出, 如核主成分分析(Kernel component analysis, KPCA)[5]和局部线性嵌入(Locally linear embedding, LLE)[6]. KPCA是PCA基于核技巧的非线性推广, 用于对非线性分布数据降维; LLE以保持投影前后局部线性关系不变为目的构造目标函数.然而这些非线性降维方法无法求出显式的映射函数, 当有新样本加入时, 需要重新学习优化模型.

极限学习机(Extreme learning machine, ELM)[7-8]最早被用于训练单隐层前馈神经网络, 具有学习速度快、泛化能力强等特点, 为有监督学习如分类和回归提供了简单有效的方法[9-10]. 2014年, Huang等基于流形正则的思想将ELM推广到无监督学习任务, 提出了一种新的非线性降维方法无监督极限学习机(Unsupervised extreme learning machine, US-ELM)[11].该方法很好地利用了ELM的逼近能力, 通过非线性映射将原数据投影到低维空间中, 并能够得到显式的非线性映射函数.但该方法利用高斯函数描述近邻样本间的相似度, 由于高斯函数用到距离测度, 难以避免地也存在高维空间中测度``集中现象", 即样本点间高斯相似性度量的类区分性随着维数增加而减弱, 进而影响降维算法性能.此外, US-ELM直接利用给定高斯函数计算样本近邻表示系数, 不具有数据自适应性.

针对上述问题, 本文对US-ELM进行改进, 同时考虑非线性数据的局部线性表示和全局稀疏表示.其中, 局部线性表示用于解决非线性流形数据的刻画问题, 以获取数据的局部结构[12];全局稀疏表示用于描述数据的全局结构[13];并通过加权参数融合近邻线性表示信息和稀疏表示信息.由此, 我们提出基于稀疏和近邻保持的极限学习机降维方法(SNP-ELM), 使得降维前后样本间的局部近邻表示关系和全局稀疏性保持不变. SNP-ELM通过学习得到近邻表示系数, 较之US-ELM具有更好的数据自适应性.

图 1  ELM网络结构示意图

图 2  人造数据集

图 3  人造数据一维可视化结果

目前, ELM模型主要用于有监督分类或回归问题, 本文则对ELM模型推广到无监督降维问题进行了进一步研究, 提出基于稀疏和近邻结构保持的极限学习机降维算法SNP-ELM. SNP-ELM通过模型优化求解计算近邻表示系数, 具有一定的数据自适应性, 实验结果表明SNP-ELM算法在Wine数据和基因表达数据集上性能优于其他对比方法.从研究中我们可以得到以下2个结论: 1)对Wine数据、高维基因表示数据降维时, 同时考虑稀疏结构和近邻结构比只考虑单一结构更有效; 2)基于ELM的非线性降维方法在Wine数据和基因表达数据上优于线性降维方法.

作者简介

廖梦真

福州大学数学与计算机科学学院硕士研究生.主要研究方向为数据挖掘, 模式识别.E-mail:liao_mengzhen@163.com

陈晓云   

福州大学数学与计算机科学学院教授.主要研究方向为数据挖掘, 模式识别.本文通信作者.E-mail:c_xiaoyun@fzu.edu.cn