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實現

略