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小于平均值，那么这些标签一定拖了总体密度的后腿，可尝试删去（实现细节有所不同）
遍历直到每一个维度都被压缩成一系列高密度的标签为止。

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

效率优化

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

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

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

合并磁盘访问步骤：磁盘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).