Representative Subsets For Big Data Learning using k-NN Graphs

聚类

---

首先将大数据转换成无向加权K近邻图，每个节点表示一个数据，每个连接表示数据点之间的相似性。然后使用FURS产生子图。最后将这些选择的节点映射回原始数据。然后使用KSC进行聚类。

产生KNN图

初始设置
KNN图需要对Kernel矩阵每一列进行排序，计算整个Kernel矩阵需要非常大的RAM和存储空间。可以通过集群的方法解决。RBF kernel的带宽$\sigma\in R^{d}$通过Silverman经验法则选取：

$$\sigma=\hat{\sigma}N^{-1/(d+4)}$$

其中$\hat \sigma$是所有维度的标准差，N是数据集的总数。
Kernel矩阵估算

$$\Omega=\left(\matrix{ K(x_{1},x_{1}) & \ldots & K(x_{1},x_{N})\cr \vdots & \ddots & \vdots\cr K(x_{N},x_{1}) & \ldots & K(x_{N},x_{N})}\right)$$

其中，$K(x,y)=e^{-{\Vert x-y\Vert^{2}\over 2\sigma^{2}}}$

主要的思路就是讲矩阵划分为小矩阵，一点一点求，最后将结果融合。分为两步，首先求得$\hat \sigma$的估计值，然后根据Map-Reduce的原理计算KNN相似图。

将数据$D$划分为${\cal D}_{p}\subset {\cal D}, p\in\{1, \ldots, P\}$其对应的矩阵为$X_p, \mu_{p}\in {R}^{d},Var_{p}\in {R}^{d}$是其均值向量和方差向量。可以得到：$\mu_{X}={1\over P}{\sum}_{p=1}^{P}\mu_{p},Var_{X}={1\over P}{\sum}_{p=1}^{P}Var_{p}$，因此有
$\sigma_{X}=\sqrt{Var_{X}}\in {R}^{d}$，$\hat \sigma$是所有维度的平均，即$\hat{\sigma}={1\over d}{\sum}_{i=1}^{d}\sigma_{X}^{(i)}$
$\Omega^{(p)}$的估计可以通过$\Omega_{ij}^{(p)},j\in\{1, \ldots, N\}, p\in\{1, \ldots, P\},i\in\{m\times(p-1)+1, \ldots, m\times p\}$,然后计算每一个数据的最大个k值,保留其序号，最后将(j,k)和(k,j)聚集起来就能得到KNN图。

KNN图的稀疏性

在实验中，因为数据的稀疏性不可知是，可以生成不同的KNN图，如$\forall k\in \{10, 100, 500\}$。连接的数量为：$2k\times N$，稀疏性可以表示为：$Sparsity =1-{2k\times N\over N\times(N-1)}$
一般的，只需要先产生最大k的KNN图，然后利用它产生更小的KNN图。我们可以计算每个KNN图的度的中间值，并求出度比中间值大的节点的数量。数量越多，图的代表性越好。（这里实在很难理解，难道中间数相等的值会有很多个？或者说这里指的是非加权图？）例如：对于一个图如果原来是稀疏的，如果用较大的k产生的KNN图，将会在本来不是很相似的数据之间加上连接，因此将导致更多的节点的度比度中间值小(？？)。

复杂性分析
复杂度最高点在于产生kernel矩阵${\cal O}(N^{2})$。如果采用并行处理，那么有${\cal O}(N^{2}/p)$。第二个复杂度较高的点是排序：获得最大的K个值，其复杂度为：${\cal O}(N^2\log N)$,如果采用并行处理,复杂度为${\cal O}({N^{2}\log N\over p})$

FURS

不做详细介绍，请参考另一篇文章。

聚类实验

选择最优KNN图

FURS和其他采样算法对比

FURS优越性

总结

提出了利用分布式框架将大数据转化成KNN图，然后使用FURS采样算法，获取数据子集。