不完整张量上基于流形学习和张量分解的特征提取_潘恪谨.pdf

小 型 微 型 计 算 机 系 统 ：年 月 第 期 收稿日期：收修改稿日期：基金项目：国家自然科学基金项目（）资助 作者简介：潘恪谨，男，年生，硕士研究生，研究方向为数据挖掘；胡建华（通讯作者），女，年生，博士，讲师，研究方向为李代数、大数据分析；宋 燕，女，年生，博士，教授，会员，研究方向为大数据分析、图像处理、预测控制；沈春根，男，年生，博士，副教授，研究方向为非线性规划、矩阵优化、金融优化不完整张量上基于流形学习和张量分解的特征提取潘恪谨，胡建华，宋 燕，沈春根（上海理工大学 理学院，上海）（上海理工大学 光电信息与计算机工程学院，上海）：摘 要：针对不完整张量数据的特征提取问题，传统的“两步走”方法，即先张量补全再特征提取，难以避免无关特征增大填补误差，进而影响特征提取的效果；而近年提出的 方法尽管可以同时进行张量补全和特征提取，但由于没有考虑数据的局部结构特点，特征提取效果仍不理想 因此，本文提出一个基于流形学习和张量分解的不完整张量特征提取方法：首先，利用“部分距离法”和非负对称矩阵分解得到完整的样本相似矩阵，进而得到样本近邻图；然后，根据近邻图建立基于流形学习和张量分解的特征提取模型，主要思想是将方差最大化和局部保持投影策略融入张量分解中 该方法可以直接从不完整张量中提取有效特征，同时保留数据的局部结构特点 本文在 个图像数据集上与 种较新的方法进行对比 实验结果表明，新提出的方法在张量补全和利用所提取的特征进行分类时性能上都有显著的优越性关 键 词：特征提取；张量分解；流形学习；非负对称矩阵分解中图分类号：文献标识码：文 章 编 号：（），（，）（，）：，：，；，：；引 言近年来，大量的数据呈现为高阶张量的形式，例如彩色图片，监控录像等 这些高阶张量数据往往具有较高的维度，并且通常包含许多无用的和冗余的信息，在很大程度上降低了机器学习的能力和效率 特征提取是解决这一问题的有效方法之一，它将高维特征变换到一组新的低维特征，从而提高机器学习的计算效率和识别能力 特征提取可以显著地提高模型泛化能力、降低存储空间以及减少计算消耗，因此在文本处理、图像识别等众多领域都有广泛的应用为了对高阶张量数据进行特征提取，一些基于判别分析和流形学习的张量特征提取方法被相继提出 例如，张量线性判别分析（，）利用标签信息最大化类间距离并最小化类内距离，得到最优投影矩阵，从而对高阶张量进行降维 多线性主成分分析（，）将 应用到张量的每一个模态上，进而从高阶张量数据中提取特征 张量局 部 保 持 投 影（，）考虑了数据的拓扑结构，利用近邻图实现张量的特征提取，同时保留了数据的局部特性虽然这些特征提取方法都已经成功地应用到人脸识别、图像去噪等领域，但它们都基于数据完备性假设 事实上，高阶张量数据常常是不完整的，例如在工业应用中，因为设备的分辨率不足或部分功能的损坏，部分图像可能会出现不规则的模糊或缺失 因此，如何从不完整张量数据中提取有效信息是一个有意义且具有挑战性的问题为了从不完整张量中提取特征，一种简单的方法是采取“两步走”策略，先将不完整张量补全，再对完整的张量进行特征提取，即“张量补全 特征提取”例如，先通过低秩张量补全模型 估计缺失值，再利用 进行特征提取 然而，这种“分离式”方法有明显的不足：高维数据中大量的无关特征可能会放大张量补全的估计误差，进而影响后续的特征提取；又由于需要分别进行张量补全和特征提取，其计算效率也较低另一种方法是对不完整张量建立特征提取模型，通过求解模型直接得到低维的特征 等人将低秩张量分解与特征方差最大化相结合，提出了一个张量特征选择框架 该方法的优点是将张量补全与特征提取同时进行，减弱了无关特征对张量补全的影响，进而提高了特征提取的有效性 但是，方法并没有考虑到张量数据的局部分布结构特点，这可能导致提取出的特征会破坏原始数据的分布结构 此外，并没有对张量重构损失和方差损失进行权衡，在一定程度上降低了特征提取的效果针对上述方法的不足，本文提出了一种基于流形学习和张量分解的不完整张量特征提取模型 该模型在 分解的基础上，最大化特征方差并最小化近邻样本特征的距离，从而提取出与原始样本具有相似分布结构的特征具体地，本文对每个张量样本建立 分解模型，最大化模型中核心张量的方差，同时利用样本近邻图最小化近邻样本的核心张量的距离，最后优化得到的核心张量即为提取的特征 此外，由于数据的不完备性，样本相似矩阵难以准确计算 为此，本文先利用“部分距离法”得到部分相似矩阵，再通过建立非负对称矩阵分解模型估计矩阵中的缺失值本文的主要贡献如下：）针对不完整张量数据的特征提取问题，提出了一种基于流形学习和张量分解的特征提取方法：此方法能够直接从不完整张量中提取有效特征，且同时保留数据的局部结构特点）考虑到近邻图的对称性和非负性，通过非负对称矩阵分解模型重构出完整的相似矩阵，同时用“部分距离法”采集更多的样本信息）在多个数据集上验证了所提方法在张量补全和特征提取上的有效性 方法的相关工作及原理 符号定义与张量运算用 表示标量，、和 分别表示维度为 的向量、维度为 的矩阵和维度为 的 阶张量、，、，分别表示、中的第、（，）、（，）个元素 张量 的 模展开记为（）；表示哈达玛积（），表示克罗内克积（），表示矩阵对应元素相除；为 范 数，其 计 算 方 式 为，；表示矩阵的核范数，是矩阵所有奇异值之和；为元素全为 的矩阵或张量；张量 为张量 的指示张量，其对应元素为：，如果，否则（）定义（张量 模积）张量 与矩阵 的 模积定义为 ，其中，并且（）（）非负对称矩阵分解非负对称矩阵分解是非负矩阵分解的一个拓展，它继承了非负矩阵分解计算简单、存储空间小等优点，其分解结构为：（）其中 为 阶非负对称矩阵，该模型的损失函数为：（，），（，()（，），）（）在文献的研究中，模型的训练采用单元素更新，其优点是占用更少的存储空间和更快的模型收敛速度，但由于单元素更新难以并行计算，因此每次迭代耗时较长 张量补全 分解是张量分解中最常用的分解形式，可用于张量补全问题，其思想是将一个高阶张量分解为一个核心张图 三阶张量的 分解 量和多个因子矩阵，图 展示了一个三阶张量的 分解 分解可以描述为：，（）（）（）（）（）是一个基于低秩张量分解的张量补全方法，它通过最小化张量在各阶展开后的核范数来估计张量中的缺失值，其优化问题描述为：（），（）是一个基于 分解和核范数正则化的张量补全模型，它在最小化 分解的重构误差的同时，最小化因子矩阵的核范数，其优化模型表示为：，（）（）（）（）（）小 型 微 型 计 算 机 系 统 年其中（）（）（）（），（）为（）的第 列，为外积，为（）、（）的列数 张量的特征提取是主成分分析（）的高阶泛化，它首先将一个高阶张量矩阵展开并中心化，再通过奇异值分解得到对应模态的投影矩阵，进而对高维的张量数据进行降维是局部保持投影（），在张量空间的推广，其核心思想是在高维张量空间中相邻的点，经过降维后，在低维空间中仍然应该相邻 因此其优化问题可以表示为：（），（）（）（）其中 （）（），表示 与 的相似度，和 利用张量运算直接对高阶张量进行降维，相比于向量化的方法降低了计算量，并且保留了张量的空间结构，但不能对不完整张量进行特征提取利用主成分分析特征提取的思想，将特征方差最大化与 分解模型相结合，从而在张量补全的同时提取出低维张量特征，其优化模型为：，（）（）（）?），（）（），（）其中 为核心张量 直接从不完整张量中提取特征，从而降低了“两步走”策略中张量补全带来的近似误差 然而，并没有对张量重构损失和方差损失进行权衡，导致难以找到更优的低维特征 方法的实现为了从高维不完整的张量数据中提取有效的特征，本文提出了一种基于流形学习和张量分解的特征提取方法 首先，利用“部分距离”策略计算出部分缺失的相似矩阵，通过非负对称矩阵分解估计矩阵中的缺失值，进而得到完整的相似矩阵，相应的给出样本近邻图 其次，基于近邻图建立不完整张图 不完整张量的特征提取 量的特征提取模型，利用梯度下降法和交替更新规则优化模型 最后，模型学习到的核心张量即为提取的低维特征 不完整张量特征提取的过程如图 所示 近邻图流形学习是指从高维空间中的样本学习出数据的低维流形结构和对应的嵌入映射，从而实现维数消减，近邻图可以用来描述样本之间的一种非线性关系，因此能够很好地近似原始数据的流形结构近邻图的构造依赖于样本相似矩阵，但部分样本信息不完整导致相似矩阵难以准确计算 一种方法是保留完整样本之间的相似度，再填充矩阵中的缺失值，例如用 替代，或者利用矩阵分解进行填补 然而，这种方法显然会丢失那些不完整样本中的有效信息 另一种方法则通过“部分距离法”计算出两个不完整样本之间的相似度，进而直接得到完整的相似矩阵 然而，如果两个不完整样本的交叉信息较少，那么该方法计算的相似度并不准确 因此，本文将“部分距离法”与非负对称矩阵分解相结合，对于交叉信息较多的两个样本，利用“部分距离法”计算其相似度，对于交叉信息较少的则通过非负对称矩阵分解进行估计）对于任意两个张量样本、，将 和 分别压缩成向量 和 （），如果 和 的交叉信息较多，则根据“部分距离法”和热核函数计算它们之间的相似度，否则保留为缺失值 相似矩阵的具体计算见式（）：，（），否则|（）其中 为给定的常数，表示向量 和 的维数，表示交叉信息的阈值；表示交叉信息的指示向量，其对应元素为：，且，否则（）于是可以得到不完整的对称相似矩阵 （，）和相应的指示矩阵）建立非负对称矩阵分解模型，填补不完整相似矩阵，其优化损失函数（矩阵形式）为：（，）（）（）其中 ，、为正则化项系数根据梯度下降法，可以得到参数、的更新公式：（）（）（）其中 、为学习率矩阵 为了保证、的非负性，令：（）（）（）于是得到、的非负更新公式：（）（）（）（）（）（）这里，本文通过交替地更新、得到最优的模型参数显然，只要初始化矩阵 非负、非负且对称，则可以保证优化后的目标矩阵是非负且对称的 于是，根据公式（）可以得到完整的非负对称相似矩阵 期 潘恪谨 等：不完整张量上基于流形学习和张量分解的特征提取 （）（）（）根据相似矩阵 将互为 近邻的样本相连，得到样本近邻图和权重矩阵，其对应元素为：，与 相连，否则（）近邻图的详细计算过程在算法 中给出算法 近邻图的计算输入：不完整张量样本集合 ，正则化系数、，潜在空间维数，阈值 初始化：参数 ，近邻样本数 ，最大迭代次数 ，非负矩阵 ，非负对称矩阵 将 中的每一个样本压缩成向量，利用式（）和式（）得到不完整的样本相似矩阵 及其对应的指示矩阵 ：利用（）式更新 利用（）式更新 （）（）由 得到近邻图，并利用式（）计算权重矩阵 输出：近邻图与权重矩阵 这里计算近邻图的方法有两个优点：）“部分距离法”可以充分地利用部分缺失样本中的有效信息，进而得到更加充分的样本相似关系；）充分考虑了相似矩阵的对称性和非负性，采用了更加合理的非负对称矩阵分解模型，从而可以恢复更加准确的样本相似关系；模型的训练过程中摒弃原有的单元素更新形式，采用矩阵形式并行计算，提高了计算效率 不完整张量的特征提取模型设 ，为给定的不完整张量样本的集合 为了从 中提取出有效特征，本文基于流形学习和张量分解，提出以下优化模型，简记为，（）（）（），（），（）其中 为样本 的核心张量，即为待学习的低维特征；特征维数，为待优化的参数；，为权重矩阵 的元素，、和 均为大于 的常数模型中第 项最小化重构误差，第 项最大化特征方差，第 项为特征局部保持投影，最后一项为投影矩阵的稀疏正则化 在 的基础上增加了流形学习，从而使提取的特征保留了原始数据的局部结构特点 同时，为了权衡重构误差项和正则项，该模型为方差项和局部保持投影项分别分配了权重 和，使模型能够更好地拟合张量数据此外，相比于 方法，将投影矩阵的正交约束替换为稀疏约束，这是因为尽管正交约束可以保证解的唯一性，但得到的解却是较为保守的，而不是最优的解由于模型中没有正交约束条件，无法求出参数的显式解，因此本文通过梯度下降法和交替