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

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

Abstract

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

重述了introduction中的问题与解决思路。
引入拉普拉斯矩阵，给出定理：拉普拉斯矩阵Ls的特征值中0出现的次数就是相似度矩阵连通区域的个数。根据定理，对数据相似图施加拉普拉斯秩约束 $(r a n k (L_{A}) = n - k)$ ，保证了k个连通分量的存在，进而可以直接将数据点划分为k簇。
避免出现全0行，将S的每一行和约束为1。
针对两种距离，分别给出目标函数。其中的约束是非线性的，文章在下文中提出了解决的算法。

令 $σ_{i} (L_{S})$ 表示第 $i$ 小的特征值， $L_{S}$ 是半正定的，因此 $σ_{i} (L_{S})$ 非负。当λ足够大时，原来的目标函数(1)等同于上式，同时保证了 $r a n k (L_{A}) = n - k$ 。
一步步将原来的目标函数(1)转化成了(5)式，相比之前更容易优化求解。
接下来交替更新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:
  应用拉普拉斯矩阵的性质：对于任意一个实向量 $f \in R^{m}$ ，都有以下公式成立：
  $f^{T} L f = \frac{1}{2} Σ_{i, j = 1}^{m} w_{i j} {(f_{i} - f_{j})}^{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。
算法如下：

同理可得：
参考Efficient and Robust Feature Selection via Joint ℓ2,1-Norms Minimization这篇论文，有：
化简整理得：

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

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