[关闭]
@hainingwyx 2017-06-13T07:52:31.000000Z 字数 1638 阅读 1204

Representative Subsets For Big Data Learning using k-NN Graphs

聚类


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

产生KNN图

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

其中是所有维度的标准差,N是数据集的总数。
Kernel矩阵估算

其中,

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

将数据划分为其对应的矩阵为是其均值向量和方差向量。可以得到:,因此有
是所有维度的平均,即
的估计可以通过,然后计算每一个数据的最大个k值,保留其序号,最后将(j,k)和(k,j)聚集起来就能得到KNN图。

KNN图的稀疏性

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

复杂性分析
复杂度最高点在于产生kernel矩阵。如果采用并行处理,那么有。第二个复杂度较高的点是排序:获得最大的K个值,其复杂度为:,如果采用并行处理,复杂度为

FURS

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

聚类实验

选择最优KNN图
选择最优KNN图

FURS和其他采样算法对比
FURS和其他采样算法对比

FURS优越性
FURS优越性

总结

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

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