论文笔记:The Constrained Laplacian Rank algorithm for graph-based clustering

时间:2024-03-23 15:50:03

The Constrained Laplacian Rank algorithm for graph-based clustering ——论文笔记

主要介绍了CLR方法,是聂飞平老师16年的论文,文章和代码见聂老师主页:http://www.escience.cn/people/fpnie/index.html

Abstract

  • 现有的基于图的聚类方法都是在固定输入的数据图上进行聚类,如果输入的图质量较差,则聚类结果也会较差;
  • 这些方法往往需要进行后处理才能完成聚类;
  • 针对这两个缺点,提出Constrained Laplacian Rank (CLR)方法,将数据图本身作为聚类过程的一部分进行调整;
  • 该方法可以学得刚好有k个连通分量的图;
  • 基于L2范数和L1范数,产生了两种聚类目标,分别推导了优化算法进行求解。

Introduction

  • 现有的基于图的聚类方法都是先由数据构建数据图,然后在固定的数据图上完成优化。
  • Problem:
    1. 不能直接学习到聚类结果,需要对数据相似图进行后处理以完成聚类任务;
    2. 相似图的质量很大程度上决定了聚类结果的好坏,现有的构图方法无法保证对于不同规模数据集的构图质量。
  • Solution:
    1. 直接学习有k个连通分量的数据相似图;
    2. 对数据相似图施加拉普拉斯秩约束,保证k个连通分量的存在;
    3. 针对1范数和2范数,提出两种聚类目标函数并给出优化算法。

New Clustering Formulations

  • 重述了introduction中的问题与解决思路。
  • 引入拉普拉斯矩阵,给出定理:拉普拉斯矩阵Ls的特征值中0出现的次数就是相似度矩阵连通区域的个数。根据定理,对数据相似图施加拉普拉斯秩约束(rank(LA)=nk),保证了k个连通分量的存在,进而可以直接将数据点划分为k簇。

    论文笔记:The Constrained Laplacian Rank algorithm for graph-based clustering

  • 避免出现全0行,将S的每一行和约束为1。

  • 针对两种距离,分别给出目标函数。其中的约束是非线性的,文章在下文中提出了解决的算法。
    论文笔记:The Constrained Laplacian Rank algorithm for graph-based clustering

Optimization Algorithms

L2-norm:

  • σi(LS)表示第i小的特征值,LS是半正定的,因此σi(LS)非负。当λ足够大时,原来的目标函数(1)等同于上式,同时保证了rank(LA)=nk

    论文笔记:The Constrained Laplacian Rank algorithm for graph-based clustering

  • 一步步将原来的目标函数(1)转化成了(5)式,相比之前更容易优化求解。

    论文笔记:The Constrained Laplacian Rank algorithm for graph-based clustering

  • 接下来交替更新S和F:

    1. Fix S and update F:
      F的最优解由对应于k个最小特征值的Ls的k个特征向量组成。(可以参考对谱聚类的介绍,如:https://www.cnblogs.com/pinard/p/6221564.html)
    2. Fix F and update S:
      应用拉普拉斯矩阵的性质:对于任意一个实向量fRm,都有以下公式成立:
      fTLf=12Σi,j=1mwij(fifj)2

      (证明见:https://blog.csdn.net/yujianmin1990/article/details/48420483)
      结合范数的定义,则(5)式转化成了(7)式。每一行独立,所以按行展开,整理后得到(9)式,利用拉格朗日乘子法可以解决,如(30)式或论文:A New Simplex Sparse Learning Model to Measure Data Similarity for Clustering。
      论文笔记:The Constrained Laplacian Rank algorithm for graph-based clustering
  • 算法如下:
    论文笔记:The Constrained Laplacian Rank algorithm for graph-based clustering

L1-norm:

  • 同理可得:
    论文笔记:The Constrained Laplacian Rank algorithm for graph-based clustering
  • 参考Efficient and Robust Feature Selection via Joint ℓ2,1-Norms Minimization这篇论文,有:

    论文笔记:The Constrained Laplacian Rank algorithm for graph-based clustering

  • 化简整理得:

    论文笔记:The Constrained Laplacian Rank algorithm for graph-based clustering

上式利用拉格朗日乘子法可以迭代求解。
- 算法如下:

论文笔记:The Constrained Laplacian Rank algorithm for graph-based clustering

Learning an Initial Graph

  • 这一部分是介绍学习合适的初始相似度矩阵的过程,出发点在于:
    1. 与两点之间距离成反比;
    2. 保持稀疏,刚好保证每一个点的相似度向量有m个非零值。
  • 于是有:

    论文笔记:The Constrained Laplacian Rank algorithm for graph-based clustering

  • 经过一步步推导求解得到:

    论文笔记:The Constrained Laplacian Rank algorithm for graph-based clustering

  • 这样设置初始相似度矩阵有以下优点:

    1. 只涉及加减乘除基本运算,效率高;
    2. 学习得到的A是稀疏的;
    3. A中的相似度是与距离保持一致的,距离大则相似度随之大,反之亦然;
    4. A中的相似度具有缩放不变性,被任意标量缩放,保持不变;
    5. 只涉及一个参数,且这个参数是整数,易于调整:在大多数情况下,m<10即可。

Connection to Normalized Cut

  • 这一部分证明了上文提出的基于L2-norm的目标函数与NCut的关系:
    论文笔记:The Constrained Laplacian Rank algorithm for graph-based clustering

Experiments

  • 这一部分是实验,包括了toy数据集和几个常用的数据集。M被设置为5,同时为了加速,采用了一种启发式的算法:先设置较小的λ,然后在每一次迭代的时候,计算Ls的特征值0的个数,超过k则λ减半,反之增倍,直到等于k,结束迭代。