背景
密集块
本文直接略过了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网络攻击数据集。
问题描述
指标定义
该问题的形式定义相对比较复杂,完整的定义可以参见原文。

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

块密度
研究者发现定义快密度对于异常检测非常有用,以下是两种快密度的表示方法
算数块密度
几何快密度
需要注意的是,这里的块密度并不是单纯的块内数值加权平均,而是一个类似于块内总质量除以块各维度平均大小的一个东西。
最后定义块的可疑性(Suspiciousness)
(1)
问题定义
大规模前k密集块检测问题
给定:a)一个大规模R数组,该数组无法在内存中存下来,b)一个计算块密度的函数
计算:k个密度最大且不相交的块。
方法
首先是D-Cube的算法框架,该框架使用迭代的方式,每一轮都调用算法获得一个密集块,然后将密集块中出现过的标签都从数据集中删掉——
- 计算R的质量M_R作为后续find_single_block调用的参数
- 调用find_single_block 得到一个密集块B
- 令R←R – B
- 进入下一个迭代
可以看出,D-Cube作为大的框架,多次调用快选择算法。

接下来是重点,如何在R中找到一个块B,使其密度尽量大。事实上也是使用迭代法,首先令B为R全集,每一轮都挑选出一个维度
,计算该维度的所有标签对应的
值,删掉那些不能够有效增加
的项。在所有维度都被遍历之后返回一个极度压缩的块。大体思路如下——
- 选择一个维度i(如标签数量最大的维度)
- 遍历维度i的所有标签,计算每个标签对应的质量Mass
- 一定会有一部分标签的Mass小于平均值,那么这些标签一定拖了总体密度的后腿,可尝试删去(实现细节有所不同)
- 遍历直到每一个维度都被压缩成一系列高密度的标签为止。

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

效率优化
注意到所有数据都是以文件的形式储存的,这意味着
- 每次访问数据,都需要从文件中把数据给读出来。
- 每次修改数据,都需要先从文件中读取数据,将修改后的数据写入临时文件,最后将临时文件移动覆盖原文件。
文章提到了两种效率优化的方式——
合并磁盘访问步骤:磁盘IO的总量可以通过合并多步骤的磁盘访问进行优化,这种优化的核心思路是,如果我们首先要访问一遍磁盘数据,又要写相同的数据,我们完全可以省略第二遍的磁盘IO中最为耗时的磁盘扫描。该优化能将磁盘访问数量减至原来的30%。
使用内存缓存法:对于那些最常访问的Tensor,将他们缓存到内存中,能有提速约3倍。
以D-Cube函数的line5和line8为例

- 在执行line8的时候
- 从磁盘文件[disk_value_current]中读入权值数据
- 依照Block的指示,将那些存在于Block的权重置0
- 置0的同时,将权重写入文件[disk_value_temp]
- 顺便执行下一轮迭代的line5
- 写回数据过程中,顺便对新的权重求和
- 使用[disk_value_temp]覆盖[disk_value_current]完成数据更新
- 额外的,对于数据前面
条数据,直接缓存到内存中。
复杂度分析
具体分析略过,可以证明最坏复杂度
表示要寻找k个密集块
表示数据维度
表示数据集大小
除去最坏的情况,在实际的分析中,我们发现时间复杂度和线性相关,和
次线性相关。
准确率分析
可证明模型返回的块密度上界为最优解块密度的N倍,即——
令为最大化
的块,
为算法返回值,有
,证明略。
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).
小朋友很棒哦