小白学习机器学习===谱聚类之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的指示，具体为：

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

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

进一步，计算小白学习机器学习===谱聚类之NCut切图，可以得到：

小白学习机器学习===谱聚类之NCut切图 , 推导过程与ratioCut几乎完全相同

此外，相比与Ratiocut，Ncut特有的一点性质是：小白学习机器学习===谱聚类之NCut切图，具体如下：

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

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

同样，可以得到：

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

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

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

下面进一步说明，令

， D -1/2 意为对D对角线上元素开方再求逆。将小白学习机器学习===谱聚类之NCut切图

代入

可以得到：

以及：

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

至此，目标操作小白学习机器学习===谱聚类之NCut切图可以修改为：

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

其中，

这一步操作，就是对L矩阵进行normalize，而normalize可以理解为标准化，具体为: 小白学习机器学习===谱聚类之NCut切图

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

的前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^’等)的降维。

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

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

Ncut

相关推荐