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

背景

密集块

本文直接略过了Dense-Block的含义,这里稍微提一提[1]——

假设你拥有一个点评网站的评分数据集,里面记录了“某个时刻,某个用户,对某个页面,进行了点评”。怎么找到数据集里面的虚假点评呢?

研究发现,“点评者相同、点评时间相同、点评页面相同”,意味着这些点评可能是一个群聚虚假点评!

如果把所有的数据,放到一个K维的立方体中,上述虚假点评会组成一个“块”,块内的权值比其他位置更为“密集”。这就是密集块(Dense-Block)的含义。

计算机储存的层次结构

计算机内存访问速度快、容量较小;与之相反计算机磁盘访问速度慢、容量较大。这意味着,对于小数据,我们的程序都会将他放在内存中以获得较快的访问速度。但是倘若数据量增大,那么数据就不得不被放在更低层级的储存结构上(如硬盘),而访问速度会变慢约1000倍之多。

简介

在欺诈检测领域,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网络攻击数据集。

问题描述

指标定义

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

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

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

块密度

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

算数块密度

\rho_{ari}(B,R) = \rho_{ari}(M_B, \{|B_n|\}_{n=1}^{N},M_R, \{|M_n|\}_{n=1}^{N}) = \frac{M_B}{\frac{1}{N}\sum_{n=1}^{N}|B_n|}

几何快密度

\rho_{geo}(B,R) = \rho_{geo}(M_B, \{|B_n|\}_{n=1}^{N},M_R, \{|M_n|\}_{n=1}^{N}) = \frac{M_B}{(\prod_{n=1}^{N}|B_n|)^{\frac{1}{N}}}

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

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

(1)   \begin{align*}\rho_{susp}(B,R) =& \rho_{susp}(M_B, \{|B_n|\}_{n=1}^{N},M_R, \{|M_n|\}_{n=1}^{N}) \\=& M_B \left(log\left(\frac{M_B}{M_R}\right)-1\right) + M_R \prod_{n=1}^{N} \frac{|B_N|}{|R_N|}  \\& -M_B log\left(\prod_{n=1}^{N}\frac{|B_N|}{|R_N|}\right)\end{align*}

问题定义

大规模前k密集块检测问题
给定:a)一个大规模R数组,该数组无法在内存中存下来,b)一个计算块密度的函数\rho
计算:k个密度最大且不相交的块。

方法

首先是D-Cube的算法框架,该框架使用迭代的方式,每一轮都调用find\_single\_block算法获得一个密集块,然后将密集块中出现过的标签都从数据集中删掉——

  • 计算R的质量M_R作为后续find_single_block调用的参数
  • 调用find_single_block 得到一个密集块B
  • 令R←R – B
  • 进入下一个迭代

可以看出,D-Cube作为大的框架,多次调用快选择算法find\_single\_block

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

接下来是重点,如何在R中找到一个块B,使其密度\rho尽量大。事实上也是使用迭代法,首先令B为R全集,每一轮都挑选出一个维度i,计算该维度的所有标签对应的M值,删掉那些不能够有效增加M_B的项。在所有维度都被遍历之后返回一个极度压缩的块。大体思路如下——

  • 选择一个维度i(如标签数量最大的维度)
  • 遍历维度i的所有标签,计算每个标签对应的质量Mass
  • 一定会有一部分标签的Mass小于平均值,那么这些标签一定拖了总体密度的后腿,可尝试删去(实现细节有所不同)
  • 遍历直到每一个维度都被压缩成一系列高密度的标签为止。
find_single_block,该函数目的在于从R中选取一个尽量密集的块。

最后,维度的选择也有若干方法,但他们本质上只决定了贪心的顺序,对于模型本身没有太大的结构性贡献。

效率优化

注意到所有数据都是以文件的形式储存的,这意味着

  • 每次访问数据,都需要从文件中把数据给读出来。
  • 每次修改数据,都需要先从文件中读取数据,将修改后的数据写入临时文件,最后将临时文件移动覆盖原文件。

文章提到了两种效率优化的方式——

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

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

以D-Cube函数的line5和line8为例

此图像的alt属性为空;文件名为image-3.png
line5:计算R中所有权值的和;Line8:依据计算出来的R中的块B,将B的所有标签从R中删除
  • 在执行line8的时候
    • 从磁盘文件[disk_value_current]中读入权值数据
    • 依照Block的指示,将那些存在于Block的权重置0
    • 置0的同时,将权重写入文件[disk_value_temp]
  • 顺便执行下一轮迭代的line5
    • 写回数据过程中,顺便对新的权重求和
  • 使用[disk_value_temp]覆盖[disk_value_current]完成数据更新
  • 额外的,对于数据前面num_of_buffer条数据,直接缓存到内存中。

复杂度分析

具体分析略过,可以证明最坏复杂度O(kN^2|R|L)

  • k表示要寻找k个密集块
  • N表示数据维度
  • R表示数据集大小
  • L = max_{n \in \{1\dots n\}}|R_n|

除去最坏的情况,在实际的分析中,我们发现时间复杂度和k,N,R线性相关,和L次线性相关。

准确率分析

可证明模型返回的块密度上界为最优解块密度的N倍,即——

B*为最大化\rho_{ari}(B,R)的块,\tilde{B}为算法返回值,有\rho_{ari}(\tilde{B},R) \geq \frac{1}{N} \rho_{ari}(B*,R),证明略。

MapReduce实现

Map-Reduce框架适用于数据被储存在分布式文件系统的情况。 实际上本文基本上算是将最经典的Map-Reduce模型套进来了,创新点是“用了”而非“如何用”。

例如要计算R每一个标签对应的质量——

  • [MAP]将所有需要计算的标签分发到所有分布式Client节点
  • [PROCESS]分布式节点计算每一个标签的质量
  • [REDUCE]将计算的结果汇总到Master节点

参考文献

[1]M-zoom: Fast dense-block detection in tensors with quality guarantees.
[原文] Shin, K., Hooi, B., Kim, J., & Faloutsos, C. (2017, February). D-cube: Dense-block detection in terabyte-scale tensors. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining (pp. 681-689).

《D-Cube: Dense-Block Detection in Terabyte-Scale Tensors 阅读笔记》有一个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据