[关闭]
@hainingwyx 2017-05-28T14:20:52.000000Z 字数 3027 阅读 1259

Spectral Grouping Using Nystrom Method

聚类


Nystrom extension

Nystrom 方法是用于寻找具有以下格式的特征函数的近似解

在积分区间均匀离散化,得到

,可以转变为矩阵的特征值问题:

其中, , 是矩阵A对应特征值的特征向量。

综上,可以得到的 Nystrom 扩展表示,

表明可以利用采样点的特征向量表示任意点的特征向量。

矩阵实现

如何利用上面的结论实现利用采样点之间的亲密度矩阵A和采样点与测试点之间的亲密度矩阵B,来表示测试点之间的亲密度矩阵?

假设的矩阵,B则是的矩阵。利用上面得到的结论,可以得到测试点特征向量的Nystrom扩展矩阵表示:

将亲密度矩阵表示为:

其特征向量

可利用特征向量表示W的近似

可看出C的近似为.

此时还不是正交的,需要根据A是否是正定的,进行相应正交化处理。

正交化方法

A正定的情况
定义矩阵,其对角化为
则有可对角化为,其中为:

给出MATLAB代码
找出前nvec个特征向量
E保存了最后的结果。

A非正定的情况

Ncut的应用

计算每个节点的度:

其中分别表示矩阵A,B行的和;表示矩阵B的列的和

对于拉普拉斯矩阵可以从上面的结果中得到:

性能

利用Fisher criterion来判断二分图的情况下的分割质量:

其中分别表示第i类的均值和方差。

实验

efg中的虚线表示dense problem的解的分类效果。可以看出,样本越多,效果越好;距离R越大,效果越好。

时间

从图中可以看出,稀疏方法(前两个)对问题本身可分性非常敏感。Nystrom速度较快,几乎不受影响。虚线是dense solver的时间,仅作为参考。

采样

通过选择两个不同的随机采样集,通过比较两个特征向量的结果来确定到底需要多少样本才能得到一个稳定的结果。

对于不同的特征向量计算F范数内积来衡量重复性。

由上面公式,特征向量的旋转不影响,主要是构成的特征向量空间。

样本稳定性

对于图片的结果,结果1表明完全相同,那么从上图来看,400个样本点几乎足够了,所需要的样本数几乎在1%左右!

颜色和纹理图片划分

检验是比较两个直方图的简单而有效的方法,对于颜色和纹理的划分有非常鲁棒的效果。对于归一化直方图

为了防止的情况出现,每一个空的bin都会加上一个小数

从而定义亲密度矩阵,可以证明这个核是正定的。

图片划分

纹理划分

参考文献

[1].Fowlkes C, Belongie S, Chung F, et al. Spectral grouping using the Nystrom method[J]. IEEE transactions on pattern analysis and machine intelligence, 2004, 26(2): 214-225.

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注