D-Cube: Dense-Block Detection in Terabyte-Scale Tensors 阅读笔记

语言: CN / TW / HK

简介

在欺诈检测领域,Dense-Block检测被证明非常的有效。但是,至今为止,所有的Dense-Block计算方法都默认了数据集足够的小以至于可以被塞到电脑内存中。当数据量稍微大一些的话,这类算法就会产生大量的磁盘IO,以至于变得非常低效。

本文提出了D-Cube,一个基于磁盘的最密集块检测算法,该算法以最小化磁盘IO为目标进行优化,并支持Hadoop的MapReduce框架进行分布式运算。D-Cube有如下的特征——

  • 储存高效:D-Cube与传统算法相比,在相同数据集下,使用的内存减小了1600倍,而能够处理的数据规模则增大到1000倍
  • 快速:相比于State-Of-Art模型,D-Cube在真实世界的向量中有5倍加速比,在人工生成向量中有12倍加速比。
  • 准确率可靠:可证明的算法效果,和State-Of-Art算法在真实世界向量中结果相似性极高。
  • 有效性:能够高准确率检测出TCP-Dump网络攻击数据集。

问题描述

指标定义

该问题的形式定义相对比较复杂,完整的定义可以参见原文。

以下图为例,首先我们有若干关系的多元组,其中编码了N维的张量组合以及其对应的非负指标。例如在wikipedia revision history数据集中,表示了用户u修订了页面p,修改时间d,修改次数c。显然,关系可以被表示到一个维立方体中,如图b所示。我们可以进一步,在的诸多维度中,每个维度都提取出一个子集,形成一个块B。对于B和R,我们都可以定义其质量为块内所有指标的和。

上图是Dense-Block计算的例子,a)描述了一个关系R,b)描述了R的Tensor表示方法,以及其中的一个Block, B(alice,1),M(B(alice, 1)) = 9

块密度

研究者发现定义快密度对于异常检测非常有用,以下是两种快密度的表示方法

算数块密度

几何快密度

需要注意的是,这里的块密度并不是单纯的块内数值加权平均,而是一个类似于块内质量除以块平均维度大小的一个东西。

最后定义块的可疑性(Suspiciousness)

(1)  

问题定义

大规模前k密集块检测问题

给定:a)一个大规模R数组,该数组无法在内存中存下来,b)一个计算块密度的函数

计算:k个密度最大且不相交的块。

方法

首先是D-Cube的算法框架,可以看出,D-Cube的核心是一个快选择算法

算法框架,通过迭代,每次找到一个块,并从R中删除掉,直到成功选取k个块为止。

接下来是重点,如何在R中找到一个块B,使其密度尽量大。事实上也是使用迭代法,首先令B为R全集,每一轮都挑选出一个维度,计算该维度的所有标签,删掉是否能够有效增加。对于那些预估删掉可以增加密度的标签,按照预估增益效果排序依次删除,最终获得维度下,一个最优的删除子集,并进行接下来的迭代。

该函数目的在于从R中选取一个块。

最后,维度的选择也有若干方法,就不详细赘述了

效率优化

合并磁盘访问步骤:磁盘IO的总量可以通过合并多步骤的磁盘访问进行优化,这种优化的核心思路是,如果我们首先要访问一遍磁盘数据,又要写相同的数据,我们完全可以省略第二遍的磁盘IO中最为耗时的磁盘扫描。该优化能将磁盘访问数量减至原来的30%。

使用内存缓存法:对于那些最常访问的Tensor,将他们缓存到内存中,能有提速约3倍。

复杂度分析

具体分析略过,令 ,最坏复杂度,除去最坏的情况,在实际的分析中,我们发现时间复杂度和线性相关,和次线性相关。

准确率分析

令为最大化的块,为算法返回值,有 ,证明略。

MapReduce实现

分享到: