小白学习机器学习===谱聚类之NCut切图

Ncut

       Ncut切法实际上与Ratiocut相似，但Ncut把Ratiocut的分母|Ai|换成vol(Ai)(Vol(Ai)表示子集A中所有边的权重之和)，这种改变与之而来的，是L的normalized，这种特殊称谓会在下文说明，而且这种normalized，使得Ncut对于spectral clustering来说，其实更好，下文会说明。 

       同样，Ncut的目标，也是极小化各子图连边的和，如下： 

                         min Ncut(A1,A2,A3,...,Ak)

 同样，引入{A1,A2,⋯,Ak}的指示向量hj={hj1,hj2,...,hjn},j=1,2...,k.其中i表示样本下标，j表示子集下标， 表示样本i对子集j的指示，具体为：

                          

       如果在原始数据中第i个样本被分割到子集Aj里，则hj的第i个元素为1/根号(vol(Aj))，否则为0。 

       进一步，计算，可以得到： 

, 推导过程与ratioCut几乎完全相同

      

       此外，相比与Ratiocut，Ncut特有的一点性质是：，具体如下： 

                           

       进一步，令H={h1,h2,h3,...,hk}，构成一个n*k矩阵，则HTDH=I,其中I为单位对角矩阵。 

       同样，可以得到：

                       　　

       如此，便将极小化问题：minNcut(A1,A2,...,Ak)，转化为： 

                    

       除了H的限制条件，Ncut的极小化与Ratiocut的极小化基本无差异，但是就是这微小的条件，使得Ncut实质上是对L做了normalize（不得不叹数学真是十分奇妙）。 

       下面进一步说明，令， D -1/2 意为对D对角线上元素开方再求逆。将 代入

可以得到： 

　

        以及： 

         

        至此，目标操作可以修改为： 

        其中，这一步操作，就是对L矩阵进行normalize，而normalize可以理解为标准化，具体为: ，这么做的一个好处就是对L中的元素进行标准化处理使得不同元素的量纲得到归一，具体理解就是，同个子集里，不同样本点之间的连边可能大小比较相似，这点没问题，但是对于不同子集，如果两个子集中的weight差异过大，会使得结果偏向于量纲大的一方(就好像KNN之前要对特征进行归一化处理)。做 这一步normalize操作，可以将L中的元素归一化在[-1,1]之间，这样量纲一致，对算法迭代速度，结果的精度都是有很大提升。 
       最后，F矩阵的求解可通过求的前k个特征向量组成。
       之后再对F的行进行kmeans或GMM聚类即可。 
       以上是Ncut的内容。 

 谱聚类中的矩阵：

    可见不管是L、L^’都与E联系特别大。如果将E看成一个高维向量空间，也能在一定程度上反映item之间的关系。将E直接kmeans聚类，得到的结果也能反映V的聚类特性，而谱聚类的引入L和L^’是使得G的分割具有物理意义。

    而且，如果E的item(即n)足够大，将难计算出它的kmeans，我们完全可以用PCA降维(仍为top的特征值与向量)。

    上述对将E当成向量空间矩阵，直观地看符合我们的认知，但缺乏理论基础；而L(L^’等)的引入，如第2节所述，使得计算具有理论基础，其前k个特征向量，也等价于对L(L^’等)的降维。

    因而聚类就是为图的划分找了理论基础，能达到降维的目的。