基于k近邻的快速和参数自适应训练的稀疏子空间聚类.pdf

第 卷 第 期 年 月南昌工程学院学报 收稿日期：基金项目：国家自然科学基金资助项目（）作者简介：朱恪蠧（），女，硕士生，通信作者：黎敏（），男，博士，教授，文章编号：（）基于 近邻的快速和参数自适应训练的稀疏子空间聚类朱恪蠧，黎敏（南昌工程学院 信息工程学院，江西 南昌 ）摘要：稀疏子空间聚类算法具有较强的子空间识别能力和灵活的建模特性，但该算法存在复杂度高、参数敏感及聚类结果不稳定等问题。对此，本文提出了一种将高效率近邻过滤和参数自适应训练相结合，并应用于稀疏子空间聚类模型的算法。该算法通过 近邻算法筛选重构样本的候选点，并利用数据全局关系自适应地拟合正则参数，改变了原始稀疏子空间聚类自表示数据点和正则参数的选取方式。通过仿真实验验证了提出的算法不仅降低了运算成本，而且能够自适应选择参数，提高了聚类精度。关键词：近邻算法；稀疏子空间聚类；自适应参数训练中图分类号：文献标志码：，（，）：，：；网络传输技术、社交媒体及计算机性能的协同发展使得人类社会产生的数据呈指数级别增长，海量数据以文本、视频、音频以及图像等多样化形式不断产生 。人们生活的方方面面依赖于对数据的分析和挖掘。目前，针对低维数据集聚类的问题已获得广泛研究，衍生的算法包含多个类别，例如基于划分的聚类 ，基于网格的聚类 ，基于层次的聚类 等等。但传统的聚类算法面临高维数据聚类任务时就不再具备优越性。子空间聚类算法的提出解决了高维数据集聚类困难的问题。子空间聚类通过将高维数据投影到底层子空间的方式，使高维数据聚类任务变得简单。为了进一步提高子空间聚类的优越性，等将稀疏理论引入到子空间聚类中，提出了稀疏子空间聚类算法（，），并将该算法推广到图像识别和计算机视觉领域等高维数据聚类任务中。稀疏子空间聚类在计算机视觉领域中有着广泛的应用，其中包括人脸识别、运动分割以及图像分割等方面。人脸识别是计算机视觉领域的重要研究内容，目的是对人的面部特征进行学习并识别 。运动分割问题是将同一场景下多个刚体运动的特征点进行聚类，从而得到物体的运动轨迹 。图像分割是图像处理的初始步骤，目的是将图像分割成为具有相似性质的不同区域 。多领域多层面的复杂数据聚类需求，促进了稀疏子空间聚类算法的优化。尽管关于 的改进算法层出不穷，但这些算法大多数在小型高维数据集上表现出较好的性能，在大规模高维数据集上仍然存在着如下问题：原始 算法 （）的内存需求和 （）的浮点运算要求，导致了 及其改进算法面对大型高维数据集聚类任务时，会出现计算成本急剧增大的问题 ；相关算法忽视正则参数的有效设置，大多数改进方法依靠数据先验知识设置参数，或者重复训练的方式调整正则参数，但这些做法会导致聚类精度降低。鉴于这些问题，本文在综合分析目前稀疏子空间聚类最新进展的基础上，提出了降低 算法复杂度与科学训练 正则参数相结合的改进方案。相关技术研究进展针对稀疏子空间聚类算法复杂度高的问题，目前研究中的主要改进思路是以牺牲最小的聚类精度为代价达到降低复杂度的目的。以最小精度损失为代价近似的相关改进方法具体可分为归纳法和启发式方法两大类。面对大规模的复杂数据集的聚类任务时，许多研究通常采用归纳法 。归纳法又可分为横向归纳和纵向归纳。横向归纳首先在（，），（数据子集上学习相似矩阵，再归纳扩展到整个数据集。换言之，这些研究大多从数据中随机选择一些候选样本进行稀疏子空间聚类。然后按照剩余样本与训练数据所形成簇的匹配度，将剩余样本分配给各个簇。基于横向归纳的相关算法成功的关键在于两方面，其一是均匀随机抽样的样本点能够有效代表所有簇的空间分布。其二是候选样本必须足够多。要同时满足这两方面的需求，对于多样且复杂的聚类任务来说是一个棘手的问题。纵向归纳首先在数据的部分子空间（，）进行聚类，然后通过子集的归纳转移获得整个数据集的相似矩阵。基于启发式方法的正交匹配追踪（，），也被称为贪心的稀疏近似方法 。是一种新颖的贪心稀疏近似算法。该算法首先计算每个数据点 与剩余向量（）的残差值，并且设置残差项最小的 作为 的近邻，然后通过将数据点投影到当前近邻的距离来更新残差，直到相邻边界数量足够小时停止循环。虽然计算残差更新近邻的贪心近似方法是有效的稀疏近似方法，但是该方法仍然存在着许多问题。以复杂度为例，该算法进行近邻搜索时，计算成本往往会由于数据集维数的增加而急剧增加。为了解决该问题，和 等对 进行了优化并且降低了 的运算成本 。贪心近似方法为研究人员开辟了思路，如后来的贪婪子空间聚类（，）和基于 的可伸缩弹性网子空间聚类的活动集算法（）等都将贪心近似方法作为改进子空间聚类的核心思路。而 等人则基于 近邻搜索的思想，提出了基于最近邻过滤的稀疏子空间聚类算法（），该算法依靠 筛选数据点近邻构成系数矩阵的方法，大幅降低了 的复杂度 。近年来的相关研究中，面向大型高维数据集的聚类精度依然有局限。以提升聚类精度为目的的相关研究以优化目标函数为主要思路。基于这种思路的改进方法中，其中一种是改变目标函数的约束条件。如 和 等通过增加目标函数正则项，在确保表示矩阵不同子空间稀疏的同时，保留表示矩阵相同聚类簇的数据全局信息，使获得的表示矩阵具有更好的聚类簇的可识别性能 。另一种则不改变目标函数的约束，通过引入辅助参量减小系数矩阵所包含的全局信息，从而提高子空间划分性能。如迭代重加权稀疏子空间聚类（，），对 算法中添加相应权重系数来使最小化 范数的值更接近 范数，进而得到更加稀疏的系数矩阵 。但针对原始算法目标函数的改进优化中，正则参数的设置对于稀疏子空间聚类精度的作用却被忽略。等人在 年介绍稀疏子空间聚类算法理论支撑和辅助证明一文中表明，当数据集先验知识已知时，设 槡，其中 为底层子空间维数。当数据集先验知识未知时，采用两步定参法 。如在无先验知识的数据集上，等采用重复训练调试最优参数 。等人使用默认参数 进行实验 ，当已知数据先验知识时，等采用 槡 的方式确定正则参数。等于 年在基于自适应参数训练的稀疏子空间聚类（，）不在依靠数据先验知识，而是扩展两步定参法拟合底层子空间维数 并自适应求得正则参数第 期朱恪蠧，等：基于 近邻的快速和参数自适应训练的稀疏子空间聚类，聚类精度有了明显增益 ，证明了参数训练对于稀疏子空间聚类精度提高的可行性。综上所述，目前的稀疏子空间聚类算法面对超高维复杂数据时仍然存在计算量大，聚类精度不理想以及参数设置敏感等问题。对此，提出了一种新颖的基于近邻过滤和参数自适应训练的高效稀疏子空间聚类算法。算法 算法思想将 个数据点（，）列优先排列于数据矩阵 中，解决的是一个数据之间自表示的问题：，（）是用于重构 的系数列。对整个数据集进行式（）自表示之后，优化目标函数为 ，（），（）式（）中第一项约束重构误差最小，第二项约束系数矩阵 稀疏，并且 （），避免出现数据自表示的情况。公式中的正则参数 用于约束系数矩阵两方面的性质，一方面约束系数矩阵的稀疏，另一方面确保矩阵能有很好的表示能力 。由于系数矩阵的 范数围绕底层子空间维数槡 波动，并且正则参数 的选择同样依靠底层维数 的先验知识 。因此 扩展两步定参法，首先利用初始参数训练系数矩阵。然后通过拟合系数矩阵的 范数近似代替底层子空间维数 ，最后为系数矩阵每列训练不同的参数（），具体为式（）：，（），（），（）改进了数据自表示的过程。该算法不再对整个数据集进行自表示，而是利用 算法为 筛选近邻后，利用近邻点集重构。数学表达式如式（）所示：（）式中 表示用于重构数据点 的候选点集，即 的近邻。筛选近邻的目的是避免选择与 不同子空间中的数据点进行自表示，从而降低算法复杂度，提高算法的效率。综合 和 两者的优势，将 近邻过滤的思想与参数自适应训练的稀疏子空间聚类算法相结合，定义式（）所示的目标函数：，（），（），（）由于重复训练会导致系数矩阵的表示能力变差，使得聚类精度降低。所以在 筛选近邻后首先利用参数自适应训练的思想为数据 自适应的训练参数，然后利用 重新训练系数矩阵。通过重新训练系数矩阵的方式避免多次训练系数矩阵 而导致其表示性能减小。具体优化模型如下：，（），（），（）最后，将重新训练的系数矩阵 按照 的流程构造相似矩阵，并且利用谱聚类得到聚类结果。综上所述，基于 近邻的快速和参数自适应训练的稀疏子空间聚类（）算法如表 所示：表 算法 ：，：（）：（），：（）：在原始 的基础上增加了参数训练的过程，并且首先利用 的快速近似方法筛选近邻训练参数，然后利用训练所得的正则参数重新训练系数矩阵。相较于 算法，计算复杂度理论上提升了一倍。由于 的复杂度与 在 两 方 面 有 所 不 同，所 以 对 于 而 言，的复杂度仍然是减小了。其中第一个方面是 计算时间复杂度为 （）和 （）分别用于预处理和近邻搜索 ，并且有关于 的快速算法也大大减小了用于近邻搜索的时间成南昌工程学院学报 年本，而 需要对整个数据集进行 （）的数据搜索。另一个方面是在实验过程中 每次迭代只更新 中每列的 项，而 则需要更新 中的 项。因此复杂度大大减小。同样，更新 所需的内存量也大大减少。因此 的复杂度可记为式（）：（）（）（）（）（）（）（）由于 （）（），因此 理论上要比 复杂度更优。该假设分析将在实验部分进行验证。实验结果在本节采用两种策略检验 的性能。首先利用合成数据集评估 的复杂度表现，并与 、以及 进行比较。然后采用真实数据集扩展 以及运动分割数据集 评估 的聚类性能以及复杂度表现，并分别与贪婪子空间聚类算法（）、稀疏子空间聚类算法（）、可伸缩稀疏子空间聚类算法（）、基 于 阈 值 的 鲁 棒 子 空 间 聚 类 算 法（）、基于最近邻过滤的高效稀疏子空间聚类算法（）和基于参数自适应训练的稀疏子空间聚类算法（）进行对比。参数设置方面，所有对比算法的参数均采用对应参考文献中设置的参数值。为保证自适应得到的参数不会由于数值过大从而影响系数矩阵的稀疏生成，与 采用 （），方式训练参数 。另外 与 中的参数 按照 （，）选取 。在本节使用聚类错误率评估算法性能，具体定义为误分点的数量与数据总量的比值。聚类错误越小，则聚类性能越好。反之则越差，此外，增加常见的聚类评价指标 评价聚类性能，定义为 （，）（，）（）（），（）式中 （，）是 和 的互信息，（）为 的信息熵，（）为 的信息熵。另外设 为原始数据，在运动分割实验过程中为数据增加噪声干扰 ，并定义峰值噪声率（）为 （），（）式中 为数据集 中元素的最大值。基于合成数据集的测试本节利用合成数据集评估算法复杂度表现。通过改变数据集的大小，评估本方法与 ，以及 的复杂度差异。同时设置底层子空间维数为 ，与 中正则参数设置为 槡，与 中的参数按照自适应方法求得。实验结果如图 所示，继承了 算法高效的性能。而 由于数据间重复的自表示和巨大的内存需求增加了复杂度。由于 在 的基础上进行二次计算，很显然复杂度明显高于 。图 合成数据集上算法运行时间对比 基于扩展 数据集的测试扩展 数据集的聚类任务是将数据集中的人脸数据识别为多个类别。本节实验用到的数据包含 张照片涉及 个类别的人脸。由于该数据的维数巨大，为了方便实验和节省时间成本，本节实验随机选取了三个类别的照片进行性能测试。实验重复迭代 次，各算法任意 次聚类错误率如图 所示，聚类结果明显更优。另外，类别数 时，各算法的 性能表现如表 所示，同样具备优越性。人脸数据集具有环境维数大的特点，采用传统算法计算复杂度大。但结合图 可以证明面对高维数据集聚类任务时，复杂度优于 与 。这表明改进后的算法在吸收了 高效率的同时，保持了 较好的聚类精度。由于 采用随机选择候选样本进行部分稀疏子空间聚类，然后按照适应度分配剩余样本到各个聚类，迫使 聚类精度较低，而复杂度最优。第 期朱恪蠧，等：基于 近邻的快速和参数自适应训练的稀疏子空间聚类图 扩展 数据集上算法聚类错误率对比图 扩展 数据集上算法运行时间对比 基于 数据集的测试运动分割是计算机视觉领域的一个重要范畴。由于稀疏子空间聚类对于运动分割问题具有良好的鲁棒性 ，因此稀疏子空间聚类被广泛应用于运动分割问题中。实验中的数据来自 数据集的刚性运动序列 。数据集中大约有 个特征轨迹以及 个帧数。本节实验以从视频中提取相应的运动或对象的特征点并进行分配为目标。各算法的聚类性能表现如图 所示。此外，两个运动序列的各算法聚类 如表 所示。依然保有较优的性能表现。时，各算法的运行时间如图 所示。由于 需要对数据二次表示，所以难以避免地在复杂度方面表现不佳。但相对于 和 来说，改进后的算法在复杂度方面有了一定程度上的优化。而对于 来说，以损失精度获得较优复杂度的代价无疑是巨大的，在聚类精度方面表现最差。表 各算法在两数据集上 比较算法 （）（）图 数据集上算法聚类结果对比图 数据集上算法运行时间对比 结束语针对稀疏子空间聚类算法存在的复杂度高、参数敏感及聚类结果不稳定等问题，本文提出了一种基于 近邻的快速和参数自适应训练的稀疏子空间聚类算法（），并利用合成数据集和真实数据集分别验证了 算法的复杂度和聚类性能。结果表明，算法具有高效率、参数自适应训练且聚类性能较优等特点。南昌工程学院学报 年参考文献：于茜茜 稀疏低秩子空间聚类算法研究 大连：大连海事大学，：陶涛，毛伊敏 基于 和改进人工蜂群算法的并行划分聚类算法 科学技术与工程，（）：，（）：，：，（）：，：，：，（）：武继刚，陈招红，孟敏，等 基于低秩稀疏表示的子空间学习研究综述 华中科技大学学报（自然科学版），（）：王越，严亮，张强 混合最小二乘回归的稀疏子空间聚类算法 计算机应用与软件，（）：姜枫，顾庆，郝慧珍，等 基于内容的图像分割方法综述 软件学报，（）：，：张琦，郑伯川，张征，等 基于随机分块的稀疏子空间聚类方法 计算机应用，（）：荆雪纯，赵鹏，崔志华 一种基于信息传递的稀疏子空间聚类算法框架 小型微型计算机系统，（）：，：，：，：，（）：，（），：，：，（）：，：，：，：，：，：，：，：，：，（）：，：，：，：，：，（）：郭江桥 基于子空间聚类的运动分割方法研究 郑州：郑州大学，：，：，：第 期朱恪蠧，等：基于 近邻的快速和参数自适应训练的稀疏子空间聚类