在变化特征的数据流中进行实时异常检测(xStream,KDD'18)

xStream 优势与贡献

xStream: Outlier Dete‘x’ion in Feature-Evolving Data Streams

  • 首次对特征不断变换的数据流进行异常检测。
    • 数据流不仅随着时间出现的新的数据点,已有数据点的特征可能也会变化,出现新的特征,也就是说数据矩阵的行列规模都是不确定的。
  • 算法xStream的特性
    • 算法运行的内存空间固定,对于每个流数据的处理时间固定;
    • 使用子空间投影,可以处理高维数据;
    • 多种尺度来衡量异常点,区分离散的异常点和聚集的异常群;
    • 基于窗口的方法来处理非平稳数据;

问题定义

数据流\(D=\{e_t\}_{t=1,2,...}\),每一个元素\(e_t\)都是一个三元组的形式\((id,f,\delta)_t\)。这里的\(id\)对于每一个数据点来说是唯一的,\(f\)是特征名,由一个字符串代替,\(\delta\)是一个连续或者离散的标量。每一个三元组都是对一个不可见特征空间里点的更新。

问题: 给定一个数据流\(D=\{e_t\}_{t=1,2,...}\)以及对应数据三元组\((id,f,\delta)_t\)计算并持续对每个点打分,要求所有的异常点分数都高于非异常点。


xStream算法描述

在不提前知道潜在特征空间的条件下,通过整合Half-Space Chains来有效估计密度。每个链通过不同尺度地计算近邻点来实现密度估计。算法主要组成部分如下:

  1. StreamHash:通过稀疏随机投影来选择子空间,从而实现降维。
  2. Half-Space Chains:多尺度的密度估计方法。
  3. 对非静态、非平稳流式数据的扩展处理。

StreamHash

随机投影的主要目的是在保证数据点距离的前提下,实现数据的降维。传统的随机投影方法是通过抽取一组高斯随机向量\(\{r_1,...,r_K\}\subset \mathbb{R}^d\),并把每一个点\(x\in \mathbb{R}^d\)投影到一个低维嵌入空间(embedding)\(y\in \mathbb{R}^K\),\(y = (x^Tr_1,...,x^Tr_K)\),其中K是随机投影的个数。这种低维嵌入(embedding)方式可以高精度保留原空间点对的距离关系。

对于高维数据,异常点经常是存在于低维的子空间中(个人理解是说可能只有在一部分维度异常,而非全维度的异常),由于不相干特征的存在导致很难检测出异常。这样的话我们在低维空间找异常就会简单很多。作者采用数据友好型(database-friendly)的随机投影,这个变种方法可以将原先离散的随机向量用高斯随机向量进行替换,使得只有\(1/3\)的向量是非零向量,这样的话我们在保留原来点对距离的前提下,缩减了\(2/3\)的特征空间。具体的投影遵循以下分布: \[ r_i[j] = \sqrt{\frac{3}{K}}\left\{\begin{matrix} -1 & prob = \frac{1}{6}\\ 0 & prob = \frac{2}{3}\\ +1 & prob = \frac{1}{6} \end{matrix}\right. \]

然而,本文中的问题设置中强调了特征也有可能随着流数据不断变化,也就是说真正的维度d是不确定的,因此不可能确定地抽取一组随机向量\(r_1,...,r_K\)作为先验维度。作者使用StreamHash解决这个问题,这是一个在不断变化的(不确定的)特征空间基于哈希的稀疏随机投影。它由K个哈希函数\(h_1(\cdot),...h_K(\cdot)\)实例化,每个哈希函数都能将一个特征名称(通常由字符串表示)\(f\)映射成一个哈希值\(h_i:f\rightarrow \mathbb{R}\),给定一个固定特征空间\(\mathcal{F}\)的点\(x\),StreamHash随机投影结果如下: \[ y[i]=\sum_{f_j\in\mathcal{F}}h_i(f_j)x[j], i=1,...,K \tag{1} \] 上式是对已知所有特征空间的处理方式,对于不断变化(不确定)特征空间,在数据流\(\mathcal{D}\)中新到达数据\((id,f,\delta)\)时,增量式更新方法如下(类似于+=操作): \[ y_{id}[i] = y_{id}[i]+h_i(f)\delta, i=1,...,K \]

如果更新项\(y_{id}\)不存在,那么他就将使用第一次的更新值作为初始值,在这个投影规则下,尽管数据是在不断接受的,我们仍可以计算并保持低维的投影。

对于哈希函数的选择,要求哈希结果要与原数据的分布相同,我们使用哈希族\(g_1(\cdot),...,g_K(\cdot)\)将特征(字符串)哈希成32bit整数(具体可以根据机器字节数调整)。令\(a_i(f)=g_i(f)/(2^{32}-1)\)是0~1任意一的数字,\(h_i(f)\)被定义为\(K\)随机投影(这一部分其实就是用哈希的方式随机抽取一定的数据进行分布),遵循公式(1)的分布,利用哈希族选择的特征如下:

\[ h_i[f]=\sqrt{\frac{3}{K}} \left\{\begin{matrix} -1 & if\ a_i(f)\in[0,1/6)\\ 0 & if\ a_i(f)\in[1/6,5/6)\\ +1 & if\ a_i(f)\in[5/6,1] \end{matrix}\right. \]


Half-Space Chains

通常基于密度的异常点估计,都是通过半径作为参数来调整(缩放)。但是直接通过与临近点计算密度会由两个问题不容忽视的问题(1)参数敏感,也就是半径的选择是很困难的(尤其在没有先验知识的情况下)(2)高维问题,随着维度增加,样本在特征空间过于稀疏导致找不到邻居点。为了同时解决这两个问题,作者在StreamHash基础上还结合Half-Space Chains 技术共同处理这个问题。

作者在StreamHash中选择的\(K\)维空间\(\mathcal{P}=\{1,...,K\}\)上进行密度估计。一种非常基础的密度估计方法就是用等宽组距(bin)构造出一个基于计数(bin-counts)的直方图,但是随着维度增加,划分出的组(bin)数量会指数增长,过于稀疏的组(bin)肯定是不利于密度估计的,因为这可能会导致维度灾难。所以作者提出了深度为\(D\)的Half-space chains技术。核心思想是将每个chain在不同的层级\(l=1,...D\) 都从降维后的空间\(\mathcal{P}\)中随机选择一个维度\(p\in\mathcal{P}\)进行划分,然后沿着这个维度递归地将特征空间划分为离散的组(bin)。因为\(p\)是随机采样的,如果在chain的后续重复采样到该特征,那么就用较小的组距(bin width)来实现多尺度的密度估计(也就是更细粒度)。

形式化地定义这个问题:

\(p[l]\in\mathcal{P}\)代表不同层级(level)的划分特征,\(\Delta[p]\)代表初始化的组距宽度(注意如果某个特征在不同层级被重复采样,会将组距宽度减半)。主要目标是通过组内计数(bin-counts)的方式来估计某一个投影点\(\textbf{y}\)在层级\(l\)的密度。令组向量(bin-vector)\(\bar{z}\in\mathbb{Z}^K\)初始化为\(\textbf{0}\)\(p=p[1]\in\mathcal{P}\)是在层级\(l=1\)时采样的特征,那么组向量在层级\(l=1\)时可以用初始组距进行计算:\(\bar{z}[p]=\left \lfloor y[p]/\Delta[p] \right \rfloor\),(可以看出这是一个累加和和宽度的比值,等于密度估计)。每次在chain中对特征\(p\)进行采样更新时,都会将组距宽度减半,然后进行更新。

对于基于组划分的密度估计(binning-based),划分位置(bin的边界位置)非常重要,主要会对接近边界的点产生影响。作者对于每个维度都设置了一个随机偏移量\(s[p],s[p]\in Uniform(0,\Delta[p])\),这个偏移量可以通过将数据划分到一组来减少因为组边界设置导致的密度错误估计。令\(o(p,l)\)表示特征\(p\)在自顶向下到层级\(l\)(包含层级\(l\))时被选择的次数,例如\(o(p,l)=1\)表示在特征\(p\)在层级\(l\)被首次选中。这样,投影点\(\textbf{y}\)在层级\(l\)的组向量(bin-vector)可以计算为: \[ \tag{2} z[p] = \frac{y[p]+s[p]/2^{o(p,l)-1}}{\Delta[p]/2^{o(p,l)-1}},\forall p \in \mathcal{P} \] \[ \bar{z} = \left \lfloor z \right \rfloor \]

其中\(z[p]\)是非离散化表示,\(\bar{z}\)是离散化的结果。论文中举例如下

example
example

这是一个在二维特征空间迭代划分的例子,但是没有考虑随机偏移\(s[p]\),该值在两个维度均为0:

  1. 在层级\(l=1\)时,纵向特征第一次被选中划分,根据公式(2),\(z[0] = \frac{2.2 + 0/2^{1-1}}{2/2^{1-1}} = 1.1\)
  2. 在层级\(l=2\)时,横向特征第一次被选中划分,根据公式(2),\(z[1] = \frac{3 + 0/2^{1-1}}{2/2^{1-1}} = 1.5\)
  3. 在层级\(l=3\)时,纵向特征第二次被选中划分,根据公式(2),\(z[0] = \frac{2.2 + 0/2^{1-1}}{2/2^{2-1}} = 2.2\),相较于第一次,这此划分粒度更细。

通过上述例子可以看出,给定任意层级下的\(\bar{z}\),我们都可以索引到该点在该层级下的组计数(bin-count),然而在粗粒度、高层级下,组向量可能会比较大(这里应该指长度),在流式数据中可能时无界的。因此作者在每个层级使用了count-min sketch(这是一个统计流式数据频率的算法,类似于bloom过滤器的变型)\(H_l \in \mathcal{H}\) 来估计次数统计(好处是算法空间一定)。总体来说,每个链(chain)都定义成\(C=\{\mathbf{p,\Delta,s,\mathcal{H}}\}\)\(M\)个上述链\(\mathcal{C} = \{C_1,...,C_M\}\)组成了xStream的Half-Space Chains。

对于组向量,适用于流数据的增量构造方法如下,分别表示特征被首次选取后初始化,和重复选取的增量计算方式: \[ z[p] = (y[p]+s[p])/\Delta[p]\ \ \ \ if\ o(p,l)=1\\ z[p] = 2z[p]-s[p]/\Delta[p]\ \ \ \ if\ o(p,l)>1 \]

多尺度的异常点评分。在高层级由于数据稀疏很明显每个组的密度较低,组计数(bin-counts)也较少。为了能够在不同层级比较异常点的分值,作者用\(2^lH_l\lfloor \bar{z}\rfloor\)来定义不同层级的异常值。对于某一个点\(\mathbf{y}\)的异常得分是其在所有链\(\mathcal{C}\)上得分的均值: \[ S(y)=\frac{1}{M}\sum_{C\in \mathcal{C}}S_{C}(y)=\frac{1}{M}\sum_{C\in \mathcal{C}}min_l 2^lH_l[\bar{z}] \]


处理非平稳数据和特征不断变化的点

由于流式数据可能会改变数据的分布,也可能会对历史点进行更新,所以针对这方面的改进就很必要了。

非平稳数据,处理方法是设置(1)当前窗口(2)参考窗口,这两个窗口都包含相同数量的点。这样对于两个窗口要分别维护 count-min-sketch算法中的两个计数器\(H_{l.c},H_{l.r}\)(current and reference)。当数据向下一层级传播时,\(H_{l.c}\)层级加1,\(H_{l.r}\)计算异常分值,对于新数据来的时候,\(H_{l.r}\) 赋值 \(H_{l.c}\)的结果,\(H_{l.c}\)初始化为0,并开始计算下一个窗口。通过这种交替迭代的方式来进行迭代更新。窗口大小取决于数据分布变化的快慢,显然如果数据分布变化快则需要小窗口。

特征不断变化的点 由于流式数据的增量特征,有限内存需要采用最近最少使用算法(LRU)来进行数据更新:新的数据点进入缓存后,最近最少使用的点则被遗忘。这一优化是针对随着时间改变有相应更新操作的点(id相同)。

算法如下: algo

4-10行是窗口更新相关操作,11-15是LRU的缓存机制,16-17行是对每条链(chain)的更新及评分操作。


参考资料

xStream 主页

xStream 代码