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：
- 不能直接学习到聚类结果，需要对数据相似图进行后处理以完成聚类任务；
- 相似图的质量很大程度上决定了聚类结果的好坏，现有的构图方法无法保证对于不同规模数据集的构图质量。
- Solution：
- 直接学习有k个连通分量的数据相似图；
- 对数据相似图施加拉普拉斯秩约束，保证k个连通分量的存在；
- 针对1范数和2范数，提出两种聚类目标函数并给出优化算法。
New Clustering Formulations
- 重述了introduction中的问题与解决思路。
- 引入拉普拉斯矩阵，给出定理：拉普拉斯矩阵Ls的特征值中0出现的次数就是相似度矩阵连通区域的个数。根据定理，对数据相似图施加拉普拉斯秩约束
，保证了k个连通分量的存在，进而可以直接将数据点划分为k簇。
- 避免出现全0行，将S的每一行和约束为1。
-
针对两种距离，分别给出目标函数。其中的约束是非线性的，文章在下文中提出了解决的算法。
Optimization Algorithms
L2-norm:
- 令
表示第
小的特征值，
是半正定的，因此
。
-
一步步将原来的目标函数(1)转化成了(5)式，相比之前更容易优化求解。
5.png
- 接下来交替更新S和F：
- Fix S and update F:
F的最优解由对应于k个最小特征值的Ls的k个特征向量组成。(可以参考对谱聚类的介绍，如：https://www.cnblogs.com/pinard/p/6221564.html) - Fix F and update S:
应用拉普拉斯矩阵的性质：对于任意一个实向量，都有以下公式成立：
(证明见：https://blog.csdn.net/yujianmin1990/article/details/48420483)
结合范数的定义，则(5)式转化成了(7)式。每一行独立，所以按行展开，整理后得到(9)式，利用拉格朗日乘子法可以解决，如(30)式或论文：A New Simplex Sparse Learning Model to Measure Data Similarity for Clustering。
-
算法如下：
L1-norm:
-
同理可得：
-
参考Efficient and Robust Feature Selection via Joint ℓ2,1-Norms Minimization这篇论文，有：
-
化简整理得：
上式利用拉格朗日乘子法可以迭代求解。
-
算法如下：
Learning an Initial Graph
- 这一部分是介绍学习合适的初始相似度矩阵的过程，出发点在于：
- 与两点之间距离成反比；
- 保持稀疏，刚好保证每一个点的相似度向量有m个非零值。
-
于是有：
-
经过一步步推导求解得到：
- 这样设置初始相似度矩阵有以下优点：
- 只涉及加减乘除基本运算，效率高；
- 学习得到的A是稀疏的；
- A中的相似度是与距离保持一致的，距离大则相似度随之大，反之亦然；
- A中的相似度具有缩放不变性，被任意标量缩放，保持不变；
- 只涉及一个参数，且这个参数是整数，易于调整：在大多数情况下，m<10即可。
Connection to Normalized Cut
-
这一部分证明了上文提出的基于L2-norm的目标函数与NCut的关系：
Experiments
- 这一部分是实验，包括了toy数据集和几个常用的数据集。M被设置为5，同时为了加速，采用了一种启发式的算法：先设置较小的λ，然后在每一次迭代的时候，计算Ls的特征值0的个数，超过k则λ减半，反之增倍，直到等于k，结束迭代。
