D-Cube: Dense-Block Detection in Terabyte-Scale Tensors 阅读笔记
简介
在欺诈检测领域，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的算法框架，可以看出，D-Cube的核心是一个快选择算法
接下来是重点，如何在R中找到一个块B，使其密度尽量大。事实上也是使用迭代法，首先令B为R全集，每一轮都挑选出一个维度，计算该维度的所有标签，删掉是否能够有效增加。对于那些预估删掉可以增加密度的标签，按照预估增益效果排序依次删除，最终获得维度下，一个最优的删除子集，并进行接下来的迭代。
最后，维度的选择也有若干方法，就不详细赘述了
效率优化
合并磁盘访问步骤：磁盘IO的总量可以通过合并多步骤的磁盘访问进行优化，这种优化的核心思路是，如果我们首先要访问一遍磁盘数据，又要写相同的数据，我们完全可以省略第二遍的磁盘IO中最为耗时的磁盘扫描。该优化能将磁盘访问数量减至原来的30%。
使用内存缓存法：对于那些最常访问的Tensor，将他们缓存到内存中，能有提速约3倍。
复杂度分析
具体分析略过，令 
，最坏复杂度，除去最坏的情况，在实际的分析中，我们发现时间复杂度和线性相关，和次线性相关。
准确率分析
令为最大化的块，为算法返回值，有 
，证明略。
MapReduce实现
略