基于图正则化的非负模糊联合编码数据聚类

埃及信息学杂志22（2021）91全文基于图正则化的非负模糊联合编码数据聚类算法彭勇a，b，张义凯a，秦飞伟a，孔万增a，ca杭州电子科技大学计算机科学与技术学院，浙江杭州310018b苏州大学计算机信息处理技术省级重点实验室，苏州215123c脑机协同智能浙江省重点实验室，杭州310018阿提奇莱因福奥文章历史记录：收到2020年2020年5月4日修订2020年5月10日接受可于2020年保留字：非负矩阵分解模糊编码局部坐标编码图正则聚类A B S T R A C T非负矩阵分解（NMF）是一种将数据转化为非负系数表示的有效模型，其区分能力通常被增强以用于各种模式识别任务。在基于NMF的聚类中，我们经常需要对学习的系数执行K-均值作为后处理步骤，以获得最终的聚类分配。这打破了特征学习和识别阶段之间的联系。在本文中，我们建议学习的非负系数矩阵的基础上，我们共同执行模糊聚类，通过查看字典矩阵的每一列因此，我们制定了一个新的模糊聚类模型，称为联合非负和模糊编码与图正则化（G-JNFC），并设计了一个有效的优化方法来解决它的交替方向优化框架下。除了G-JNFC的收敛性和计算复杂性分析，我们进行了广泛的实验合成和代表性的基准数据集。实验结果表明，G-JNFC模型在数据聚类中是有效的©2020 THE COUNTORS.由Elsevier BV代表计算机和人工智能学院发布开罗大学法律系这是一篇CC BY-NC-ND许可证下的开放获取文章（http：//creative-commons.org/licenses/by-nc-nd/4.0/）上提供。1. 介绍在机器学习社区中，基本的管道首先将数据转换为特征表示，我们可以基于此执行模式识别任务。作为一种有效的学习模型，NMF[1，2]可以将原始数据转换为相应的系数表示，而系数表示可以看作是数据的特征表示，通常具有增强的鉴别能力。然后可以在学习的系数矩阵上进行各种模式识别任务，如聚类[3，4]，半监督学习[5，6]，分类[7，8]和一些特定的应用[9，10]。一般来说，大多数改进的NMF变体在不同的应用中获得了可接受的性能。在数据聚类领域中，在得到NMF中的系数表示矩阵后，往往需要进行K-均值运算来得到每个样本的最终聚类分配。这表明系数表示矩阵本身不能充当聚类*通讯作者：杭州市江干区下沙高教园区二大道1158号邮编：310018电子邮件地址：yongpeng@hdu.edu.cn（Y. Peng）。开罗大学计算机和信息系负责同行审查。指标矩阵，直接为我们提供聚类结果。因此，这种两阶段范例，然而，这种范式至少存在两个局限性。一个是它不可避免地打破了这两个步骤之间的联系，并在后处理步骤中造成额外的计算负担。另一个是一个有前途的聚类方法不仅要确定每个数据点对一个特定聚类的归属，而且要为我们提供关于不同聚类边界区域样本的更详细的信息。因此，模糊聚类[17，18]可以描述每个数据点对不同聚类的置信度，与硬聚类相比，有时更符合我们对数据知识的直观理解。针对传统的基于矩阵分解的聚类算法存在的上述两个局限性，本文提出了一种改进的聚类算法，使学习的系数矩阵同时达到最终的聚类结果，并提供每个数据点对不同聚类的隶属度.新制定的模型被称为联合非负和模糊编码与图正则化（G-JNFC）。在G-JNFC中，除了https://doi.org/10.1016/j.eij.2020.05.0011110-8665/©2020 THE COURORS.由Elsevier BV代表开罗大学计算机和人工智能学院出版。这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表埃及信息学杂志杂志主页：www.sciencedirect.com92Y. Peng et al./ Egyptian Informatics Journal 22（2021）91XXykx-lk;222TU;V2U;V2U;V2ik我K2U;V22U;V2图正则化和局部坐标编码[19]，我们另外将系数表示矩阵中行元素的总和约束为1。这使得所提出的G-JNFC模型可以从两个不同的角度来说明，改进的局部坐标编码和联合表示学习和模糊聚类。我们提出了一个有效的算法来优化G-JNFC的目标函数。一旦解决了G-JNFC，我们就可以通过检查系数表示矩阵每行的最大值来将每个数据点分类到指定的聚类中。此外，如果每行中存在多个非零值，则这意味着对应的数据点对不同的聚类具有模糊隶属关系。给出了优化方法的计算复杂度和收敛性。在合成数据集和基准数据集上的大量实验表明了G-JNFC的有效性本文的其余部分组织如下。第二节简要介绍了非负矩阵分解和局部坐标编码的相关工作。建议的G-JNFC模型包括显然，我们可以发现JNFC目标额外地强制系数矩阵的每一行的总和为1。虽然这是一个小的修改，我们宣布，1）JNFC可以直接实现聚类结果，通过检查每一行的系数矩阵的最大值，而不进行后处理;2）JNFC可以为我们提供每个数据点的隶属度不同的集群，导致一个模糊聚类模型。有两个不同的角度来描述（3）中第二项的动机，下面分别解释。改进的局部坐标编码[21]。在数学上，我们可以将NMF视为通过字典矩阵的列线性表示每个数据点。由此看来，相应的表示系数Vik应该是如果数据点xi更接近特定列uk，则该值更大。如果我们使用平方欧几里德距离来衡量接近程度，达到这一事实的一个合理目标是模型公式化、优化、收敛和复杂性C分析见第3节。在第4节中，我们进行了广泛的实验以评估G-JNFC的有效性第5minXXv ikkxi-ukk2：44分i<$1k<$1包括整个文件。2. 相关作品联合表示学习和模糊聚类。为了将数据分组到具有一定隶属度的每个聚类中，模糊K均值聚类的目标可以定义为：nCNMF是通过用两个非线性函数对数据矩阵进行数学近似来学习基于零件的表示的。minY1¼1;YP0;lj2J2联系我们负因子矩阵minkX-UVTk2;s：t：UP0;VP0;≤1 μm其中c是聚类数，Y2Rn×c是模糊聚类数.此外，lj是第j个聚类的质心，并且聚类中心的质心为C，1/2l1;l2;· · ·;lc] 2Rd×c。Each其中XRd×n是数据矩阵，URd×c是中的基矩阵其中每一列都期望捕捉一个聚类中数据点的本质，V2Rn×c是系数矩阵。在这里，d;n;c分别是维度、数据点的数量和类（聚类）的数量。可以通过交替地更新两个变量来优化（1）中的该目标。在模式识别任务中，V通常被用作特征。如果我们将基矩阵U视为一组锚点，并强制每个数据点仅由几个附近锚点的线性组合表示，则通过将以下约束[19]作为正则化项并入NMF目标来制定非负局部坐标因子分解（NLCF）[20矩阵Y的元素yij表示属于第j个聚类的第i个样本的隶属度[22]。通过遵循将基矩阵的列的数目设置为聚类的数目的惯例，基矩阵的每一列可以被称为“概念”以表征聚类的本质属性。换句话说，基矩阵的每一列应该近似等于某个簇的质心。基于这种分析，我们可以将（3）中的第二项视为修改的模糊K均值目标。然后，提出的JNFC模型可以看作是NMF和模糊K均值的结合此外，我们还考虑了学习的表示系数矩阵的局部一致性，nc图正则化器[23]到JNFC模型中 ，然后公式化minXXvikkxi-ukk2：n2--具有图正则性的联合非负i<$1k<$1（G-JNFC）模型，具体来说，如果x离u更近，我们会有一个更大的v。nC伊克伊克minkX-UVTk2kXXvkx-uki<$1k<$1在学习的V上获得最终结果。3. 该模型在本节中，我们对现有的矩阵分解模型进行了改进，使其能够学习直接和可解释的聚类结果。3.1. 模型配方我们将联合非负和模糊编码（JNFC）模型的目标函数公式化为s：t：UP0;VP0;V1¼1：显然，当第二正则化参数c趋于零时，G-JNFC将退化为JNFC。总的来说，我们提出的G-JNFC具有以下三个主要优点。首先，G-JNFC是联合数据表示学习和聚类的统一模型。在大多数现有的研究中，学习的系数矩阵被视为数据表示，K-均值是额外执行，以获得最终的聚类分配。在G-JNFC中，一旦获得系数矩阵，我们可以通过检查系数矩阵每行的最大值来nc●其次，G-JNFC考虑了数据流形minkX-UVTk2kXXvikkxi-ukk2;i<$1k<$1所学习的系数被约束为沿着该路径变化顺利这种局部不变性的思想在s：t：UP0;VP0;V1¼1：提高学习模型的性能。●●●否则，当xi和uk不相似时，我们将有一个更小的v ik。在聚类任务中，NMF和NLCF都依赖于执行K-ð6Þð3ÞY. Peng等人/Egyptian Informatics Journal 22（2021）91931/1P， P.C.2R;¼ð—k Þþcv2Riiijji1n@U2L2nnn2我vi我我我我我JKP0;vT12-krubberx 1TKu¼0P0;vT121/1我我JKJK子问题（18）是单形上的欧几里得投影[24- 261/1JK不1n我第三，G-JNFC考虑了基矩阵和系数矩阵之间的联系。即G-JNFC作为dii¼Pnsij。因此，我们建议按行优化V，v是使用与模型中的两个变量相关的二元约束这可以看作是二阶约束。最小值vTAv-vTb;s：t：vP0;vT1 ¼1; ±13 ℃3.2. 优化方法下面，我们给出了一个优雅的优化方法的目标函数的G-JNFC（6）。一般来说，它是在交替方向优化框架下，我们把重点放在其中A UT Ud Ic×c b UT X ET2nsc×1j¼并且是矩阵UTX-kET的第i列。为了求解（13），我们引入一个辅助变量z（同时删除下标以简化表达式），将其重写为关于V的更新规则的推导■ 更新U，修复V我们可以重写目标函数minvP0;vT1¼1;zzT Av- zT b：140（6）作为n基于增广拉格朗日乘子（ALM）方法，问题（14）可以重写为minkX-UVTk2kXkxi1T-UK1=2k2;7UP02i21/1minT Tlb2z Av-zbv -z;15其中K¼diagvT2Rc×c是对角矩阵，vT 是第i个vP0;vT1¼1;z2磅代表系数列矩阵V相应的拉格朗日函数是LUkX-UVTk2kXkxi1T-UK1=2k2TrUT：因此，应用替代的优化方法以解决问题（15）。1) 修正v更新z 通过对问题（15）求导，关于z，并将其设为零，我们有2i21/1b-平均数取L对U的导数，我们有n●（6），与之相关的目标函数我我94Y. Peng et al./ Egyptian Informatics Journal 22（2021）91z1/z2/z3/z4/z5/z4/@L1/2UVTV-2XVkX-2xi1TKi2UKiU：2) 修正z更新v 当z固定时，问题（15）变为Y. Peng等人/Egyptian Informatics Journal 22（2021）9195jkTð Þ2P0;V1¼我不 2不不不不不1/196Y. Peng et al./ Egyptian Informatics Journal 22（2021）91TlübY. Peng等人/Egyptian Informatics Journal 22（2021）9197L我使用KKT条件/ujk<$$>0（j<$1;···;d;k< $1;··· ;c），我们得到98Y. Peng et al./ Egyptian Informatics Journal 22（2021）91v 最小值1/2/17/2Y. Peng等人/Egyptian Informatics Journal 22（2021）9199以下等式UVTV-X VujkkXUKiujk100Y. Peng et al./ Egyptian Informatics Journal 22（2021）91¼200万美元2G P0;不可通过填写v的平方形式Y. Peng等人/Egyptian Informatics Journal 22（2021）91101jkjki¼1jkð8 Þ¨¨Xvmin¼12？v-zlbAz？：18102Y. Peng et al./ Egyptian Informatics Journal 22（2021）91这导致U的更新规则为XTY. Peng等人/Egyptian Informatics Journal 22（2021）9110326]。在这里，我们提出了一个有效的算法来解决（18）。104Y. Peng et al./ Egyptian Informatics Journal 22（2021）91记为m<$ z-1<$b <$ AT z<$，则（18）等于第十五届会议Y. Peng等人/Egyptian Informatics Journal 22（2021）91105ujk←u jki¼1jkUVTV;209min106Y. Peng et al./ Egyptian Informatics Journal 22（2021）91（19）的拉格朗日函数是vP0;vT1¼12kv-mk2：119Y. Peng等人/Egyptian Informatics Journal 22（2021）91107其可以用紧凑矩阵形式重写为Lviv;d;g1v-mk2-dmvT1-1mv-gTv;20mvujk←uððkþ1ÞXVÞjk:10UHUHUH UH其中d;g是待确定的拉格朗日乘子。如果vω是最优解，dω;gω是相应的乘数，基于108Y. Peng et al./ Egyptian Informatics Journal 22（2021）91这里HRc×c是一个对角矩阵，其元素是列v的总和■ 更新V，修复U。将eik1/kxi-ukk2表示为ki;kki-1。Y. Peng等人/Egyptian Informatics Journal 22（2021）91109在KKT条件下，我们有以下方程，t2½1;c]8>v ωt-mt-dω-gωt0;110Y. Peng et al./ Egyptian Informatics Journal 22（2021）91矩阵E2Rn×c的第n个元素，我们有

下载后可阅读完整内容，剩余1页未读，立即下载