谱聚类方法推导和对拉普拉斯矩阵的理解

    谱聚类可以看作是基于图的一种聚类方法，在各大论坛有许多介绍谱聚类算法的博客，但是在看的过程中，总是会存在各种各样的困惑，尤其是拉普拉斯矩阵的引入等一些列问题上介绍的不是很清楚。这里基于 Ncut 文章中的推导，给出谱聚类算法的一个整体的推导过程和一些重要细节。

    首先有必要简单介绍一些图的基本知识，为了尽可能的简单，我们仅仅介绍必要的概念：

无向图定义：

定义图无向图  ，其中，  为图中的顶点，  为图中的边，  为边上权值构成的矩阵。举个栗子： 

对这样的一幅图，如果我们认为连接的节点的权值是  ，没有连接的节点的权值为  ，则此时我们可以得到一个权值矩阵：  

其中红色数字表示节点的标号，图中的每一行和每一列是对称的，他们都反映了该节点与其他节点的连接情况。

度：

定义顶点的度为该顶点与其他顶点连接权值之和：

度矩阵  为对角矩阵，上面图对对应的度矩阵为：  

子图和子图的连接权

我们可以将上面的图划分成两个子图，如下图所示：  

定义  和   是图   中两个不相交的子图，则定义子图的连接权值:

对于上面的图，我们希望通过一种最优的划分将其分为两个部分，实际上  和  两个子图的划分就是一种最优的划分：  

    我们定义这样的划分满足  最小。当图中有  个节点，有   个类别的情况，我们希望：

    这样的一个图划分问题称为最小割问题。然而在实际中，基于最割理论并不能很好的实现划分，这是因为，当仅仅依赖最小割的划分方法的话，在对图进行划分时倾向于将图中的孤立的节点划分成一类。其实这也非常容易理解，因为最小割的定义 实际上是与两个子图之间的连接边的数量是正相关的，也就是说连接边的数量越多，该值越大。在对图划分的时候，任何一个对孤立节点的划分都会小于对该节点所在类的一个更大的子图的划分的  值，所以在在该目标函数下容易产生孤立点的划分结果。

聚类的定义： 聚类就是对大量未知标注的数据集，按数据的内在相似性将数据划分成多个类别，使得类别内数据相似度较大而类别间的数据相似度较小。

Normalized cut

    针对这个问题， Normalized Cuts and Image Segmentation 中提出了 Normalized Cut，定义如下： 

其中  。也就是说，在计算每一类的割的时候，Normalized Cut 考虑的是每类割占该类所有节点到图中所有节点连接之和的比例。此时我们分析两类的情况，考虑边上权值为简单的  ，上式子可以写为：

 
这时我们可以假设  类为一个孤立节点，此时   为除了与  中节点有连接的所有边和，而  ，当图的规模比较大时，此时  。不再是该目标函数所能取得的最小值（可以观察发现最小值时小于  的）

    给定图  的顶点  一个划分  ，  ，令  为  维的指示向量。  时  ，  时  。令  表示节点  与其他所有节点间的连接之和。此时我们有： 

令   ，  ， 

 为  的全  向量。令  和   分别为  和  的指示向量。以  为例，  所得向量中每个元素表示的是图中节点  与所有子图  中节点的连接权值之和。  则能够得到子图  中与子图  中节点权值之和。而且根据  的定义我们有： 

则上式可化为：

令: 

 
则： 

在最小化的过程中可以将常数项去掉，也就是  ，同时  也可以去掉，此时： 

令  ，且  ，则

此时令  ，则有 

则最终，我们有： 

且满足  ，  我们发现这个形式刚好是广义瑞利熵的形式，对于上述形式的问题的最小化，可以利用拉格朗日乘子法进行求解： 

其中  为拉格朗日乘子。

注意： 这里实际上已经有了一个近似，在我们通过函数来求解最小值的时候已经不在原始的离散空间中，而是在实数空间中。

则对上式求导，令导  ，有： 

这时我们可以发现这个式子实际上就是对  进行特征值特征向量分解。但是我们要注意，上述的最终目标函数是由两个条件的。不过这些条件在广义的特征值特征向量分解下得到满足，即：

其中  ，这时我们很容易计算得到特征值  所对应的特征向量  。考虑  为半正定矩阵，变换到原始的表示形式中可以得到， 

(1) 最小特征值  对应的特征向量为 

(2) 根据正交性有  
根据瑞利熵的一个性质：

对于实对称矩阵   ，则   的最小值在其最小的非   特征值对应的特征向量上取得。 

根据以上叙述，我们知道  与第一小的特征向量  正交，则在   时，目标函数就可以取得最小值有： 

则： 

    此时第二小的特征向量便是我们所求目标函数在实数域上的解。如果是  类的划分，相当于我们每次从整体的图中割出最优的一部分，第一次的最优割就是第二小的特征值对应的特征向量。而下一次的割则是与上一次割不重叠的最优的割，也就是与上一次割正交的次优的割，实际上就是第三小的特征值对应的特征向量，以此类推，我们可以得到   类所对应的   个割，这些割是互相正交的。但是，我们所定义的   并不是在实数域，而是可以取   两个值，所以我们在得到每个划分时都是一种近似，如果对其继续划分时，会产生误差的累积，所以类别过多时，结果会变得不那么精确。

    另一个问题，虽然我们已经得到了实数域上目标函数的最优解，但是我们如何能够确定图的划分呢？以两类为例，我们得到的特征向量中的每个值在离散域上实际上只能够取  两个结果，则每个结果对应着该类的节点。而此时  是连续的，则我们可以通过阈值的方式来对其进行划分。如果是多类的情况，我们不能再通过只是向量将其分开，则我们可以把所得特征值向量对每个样本的表示看作是一种类别编码，我们通过聚类的方法能够得到最终结果。

谱

    在上面整个方法的介绍中我们发现在并没有介绍谱的概念，我们依旧可以推导出谱聚类算法。但是我们实际上已经用到了谱的形式，实际上矩阵  称为拉普拉斯矩阵，对它的特征值特征向量的分解就涉及到了谱分析，所以也就称为谱聚类了。现在我们引入谱一些知识，和一些思考。

    当我们提到 “谱” 这个概念的时候，都会感觉十分难以理解。而实际上我们可以简单的认为 谱 实际上就是对一个信号（视频，音频，图像，图）分解为一些简单元素的线性组合（小波基，图基）。而为了使得这种分解更加有意义，我们可以使得这些分解的元素之间是线性无关的的（正交的）。也就是说这些分解的简单元素可以看作是信号的基。

    在信号处理中我们最容易想到的谱就是傅里叶变换，它提供了不同频率下的正弦和余弦波作为基，从而我们可以将信号在这些基进行分解。但是当我们讨论图的时候，我们所称的 “谱”指的是对拉普拉斯矩阵  的特征值分解。我们可以把拉普拉斯矩阵看作是图上邻接矩阵的一种特殊的正则化形式，而它的特征值分解过程就是我们寻找构造图所需的正交基的过程。

    谱的定义：将方阵（矩阵）作为线性算子，它的所有的特征值的全体统称为方阵的谱。定义谱半径为该方阵最大的特征值。栗子：如果我们有一般矩阵   则该矩阵的谱半径为   的最大特征值。

图拉普拉斯矩阵和一些它的物理意义：

    图拉普拉斯矩阵，如果把它看作线性变换的话，它起的作用与分析中的拉普拉斯算子是一样的。，我们将在下面详细讨论，这里需要一些基本的知识：

梯度（矢量） ：梯度 “   ” 的本意是一个向量（矢量），表示某一函数在该点处的方向导数沿着该方向取得最大值，即函数在该方向处沿着该方向（此梯度方向）变化最快，变化率最大（为该梯度的模）。 

假设一个三元函数  在空间区域  内具有一阶连续偏导数，点  ， 称向量 

为函数  

在点  处的梯度，记为  或  其中：

称为（三维）向量的微分算子或 Nabla 算子。

散度（标量） 散度 "   " （divergence）可用于表针空间中各点矢量场发散的强弱程度，物理上，散度的意义是长的有源性。当   ，表示该点有散发通量的正源（发散源）；当   表示该点有吸收能量的负源（洞或汇）；当    ，表示该点无源。

散度是作用在向量场上的一个算子。用三维空间举例，向量场就是在空间中每一点处都对应一个三维向量的向量函数： 

它是一个标量函数（场），也就是说，在定义空间中每一点的散度是一个值。矢量 $V$ 的散度在笛卡尔坐标（直角坐标系）下的表达式：

拉普拉斯算子： 拉普拉斯算子（Laplace Operator）是   维欧几里得空间中的一个二阶微分算子，定义为梯度（   ）的散度（   ）。 

 

笛卡尔坐标系下的表示法： 

 维形式 

离散函数的导数： 

则我们可以将拉普拉斯算子也转化为离散形式（以二维为例） 

其矩阵表示形式为：  
 
实际上，拉普拉斯算子计算得到的是对矩阵中某一点进行微小扰动后获得的总增益

我们现在将这个结论推广到图：

    假设具有  个节点的图  ，此时图中每个节点的自由度至多为  ，此时该图为完全图，即任意两个节点之间都有一条边连接，则对其中一个节点进行微扰，它可能变为图中任意一个节点。

    此时以上定义的函数  不再是二维，而是  维向量：  ，其中  为函数 在图中节点  处的函数值。类比于  在节点  处的值。
    对  节点进行扰动，它可能变为任意一个与它相邻的节点  ,  表示节点  的一阶邻域节点。

    我们上面已经知道拉普拉斯算子可以计算一个点到它所有自由度上微小扰动的增益，则通过图来表示就是任意一个节点  变化到节点  所带来的增益，考虑图中边的权值相等（简单说就是1）则有： 

而如果边  具有权重  时，则有： 

由于当   时表示节点  不相邻，所以上式可以简化为： 

继续推导有：

对于所有的   个节点有： 

这里的 实际上就是的拉普拉斯矩阵 
    根据前面所述，拉普拉斯矩阵中的第   行实际上反应了第  个节点在对其他所有节点产生扰动时所产生的增益累积。直观上来讲，图拉普拉斯反映了当我们在节点   上施加一个势，这个势以哪个方向能够多 顺畅的流向其他节点。谱聚类中的拉普拉斯矩阵可以理解为是对图的一种矩阵表示形式。

拉普拉斯矩阵的性质

推导： 

 是对称半正定矩阵   的最小特征值是  ，相应的特征向量是  ，  的  个非负实特征值 

正则拉普拉斯矩阵的定义及性质：

1）symmetric: 

2) Random walk: 

有如下性质：

1）如果  是  的特征值和特征向量，当且仅当  是  的特征值特征向量。 

2）  是  的特征值和特征向量，  是   的特征值和特征向量；3） 和   是半正定的，由   个非负实特征值