根因分析之iDice 文章复现
1 Abstract
原文给的场景是对于大规模集群的运维，当一条issue被上报的时候，通常会带上一些attribute，比如时间，软件版本，所处的国家，城市，具体在哪个机房，浏览器，操作系统等等。在平时的时候，每天的上报的issue数量应该是差不多的，但有些时候，报错数量会突然上升，对于运维人员定位到问题所在往往很花时间。背后的问题可能是某个attribute或者某几个attributes的组合，文章称为effective combination。
这里通过三个步骤来从所有的attribute combination中找到最后可能引发报错激增的effective combination。
2 Challenge
想要找到所有effective combination的最暴力的做法就是，枚举所有attribute combination，然后以某种方式来衡量它对于总体issue激增的关系。这里主要的问题在于搜索空间过大，本文最大的创新在于对搜索空间的剪枝。如果一共有m个attribute，那一共的组合方式就是(2^m - 1)种
3 Approach
文章把整个流程主要分成三个步骤（用做剪枝）和一个结果排序- Impact based Pruning: 基于影响的用户量做剪枝（不含时间信息）
- Change Detection based Pruning: 基于时间线上的突变来剪枝（时间序列处理）
- Isolation Power based Pruning: 计算一个类似信息熵增益的值来判断这个attribute combination的区分度
- Result Ranking: 计算这个attribute combination对于全局的显著性
3.1 Impact based Pruning
对于一个effective combination而言，它必须影响足够多的用户。所以这里定一个threshold来过滤掉一些不可能的参数组合。（排除时间这个维度）这里的目的是 寻找closed frequent itemsets，文章里的没有对算法进行详细描述，就说用BFS-based closed itemset mining algorithm。
在复现的时候，我先用了现成的找frequent itemset的算法（Apriori/FPMax/FPGrowth），然后在这个结果集上找closed frequent itemset。
名词解释：
frequent itemset: 简单来说就是满足出现频次大于threshold的attribute combination，对应出现的频次称之为它的support，下图里面设定threshold=2，灰底色的itemset就是frequent itemsetclosed frequent itemset：对于下面右边图中的CE而言，他的所有children={ACE, BCE, CDE}的support都小于CE的support，这这种情况，CE被称作closed frequent itemset
复现中数据的frequent itemset 和 对应的support → 进一步筛选得到closed frequent itemset :
在我的数据集上从175条降到28条
这一步的问题转化成了 时间序列的CDE（change point detection） 问题。这里介绍几个名词，下图标的转折点叫Change point，之后的一段激增的区域叫做change region，change point 左边记为前面
文章里用的算法是GLR (generalized likelihood ratio) Test，检验change point前后是否是同分布。
作者并没有给出更详细的信息，对changepoint前后属于什么分布做进一步的说明，这导致了如果用GLR来做，我只能假定前后属于某一个分布（比如正态分布 ），然后对前后两段做最大似然估计，再计算两者比值，对这个比值是否小于某个阈值进行判断在给定日期点是否前后分布不一致，从而判断是否存在突变点。
这里的详细做法可以参考 数理统计讲义-第3章
复现时候考虑到实现的方便，我先把原数据做了一下smooth 然后用Piecewise-LR(linear regression)来做change point detection。
这里的做法是分段linear regression，这里设定用两条线（1个changepoint）来做linear regression。然后根据算法得到的转折点是否在全局chagnepoint（周围）来作为剪枝条件。
下图描述的是X={'os_android', 'media_src_organic'} 在2020-03-01 ～ 2020-04-01 的banrole情况。
其中蓝点表示的是当天封号的人数；黄点是对它进行了smooth以后对应的点；红线是piecewise-LR所判断出的chagnepoint，用于检验是否符合全局的changepoint。
比如，下图是一个positive case， 红线所在的日期就是2020-03-26，就对应全局的changepoint，所以这个attribute combination被保留。
piecewise linear regression可以参考[1] ，[2]
在经过了这步的筛选以后，候选集合变成了14个
直观理解：这里每一个X都把原所有数据分成两部分，满足X的数据 和 不满足X的数据。IP(X)衡量了以X作为划分依据所能得到的信息熵。
3.2 Change Detection Based Pruning
这一步是从时间序列的角度来剪枝掉一些attribute combinations。这一步的问题转化成了 时间序列的CDE（change point detection） 问题。这里介绍几个名词，下图标的转折点叫Change point，之后的一段激增的区域叫做change region，change point 左边记为前面
文章里用的算法是GLR (generalized likelihood ratio) Test，检验change point前后是否是同分布。
作者并没有给出更详细的信息，对changepoint前后属于什么分布做进一步的说明，这导致了如果用GLR来做，我只能假定前后属于某一个分布（比如正态分布 ），然后对前后两段做最大似然估计，再计算两者比值，对这个比值是否小于某个阈值进行判断在给定日期点是否前后分布不一致，从而判断是否存在突变点。
这里的详细做法可以参考 数理统计讲义-第3章
复现时候考虑到实现的方便，我先把原数据做了一下smooth 然后用Piecewise-LR(linear regression)来做change point detection。
这里的做法是分段linear regression，这里设定用两条线（1个changepoint）来做linear regression。然后根据算法得到的转折点是否在全局chagnepoint（周围）来作为剪枝条件。
下图描述的是X={'os_android', 'media_src_organic'} 在2020-03-01 ～ 2020-04-01 的banrole情况。
其中蓝点表示的是当天封号的人数；黄点是对它进行了smooth以后对应的点；红线是piecewise-LR所判断出的chagnepoint，用于检验是否符合全局的changepoint。
比如，下图是一个positive case， 红线所在的日期就是2020-03-26，就对应全局的changepoint，所以这个attribute combination被保留。
piecewise linear regression可以参考[1] ，[2]
在经过了这步的筛选以后，候选集合变成了14个
3.3 Isolation Power Based Pruning
在这一步，作者用了一个参数叫IP(Isolation Power)，来对上一步筛选下来的attribute combination进行进一步评估。直观理解：这里每一个X都把原所有数据分成两部分，满足X的数据 和 不满足X的数据。IP(X)衡量了以X作为划分依据所能得到的信息熵。
这里衡量了，用ground truth时间突变点，分别把X和全局各分成了两部分，观察前半部分两者差异大不大，后半部分两者差异大不大。
IP(X) 表示的对于attribute combination X，所对应的IP值:
\begin{align*}
IP(x) &= -\frac{1}{\bar \Omega_a+\bar \Omega_b}(\bar X_a\ln \frac{1}{P(a|X)} + \bar X_b \ln \frac{1}{P(b|X)}+(\bar \Omega_a-\bar X_a)\ln\frac{1}{P(a|\bar X)}+(\bar \Omega_b-\bar X_b)\ln\frac{1}{P(b|\bar X)})
\end{align*}
P(b|X) &=\frac{\bar X_b}{\bar X_a+\bar X_b}\\
P(a|\bar X) &=\frac{\bar \Omega_a-\bar X_a}{\bar \Omega_a-\bar X_a+ \bar \Omega_b - \bar X_b}\\
P(b|\bar X) &=\frac{\bar \Omega_b-\bar X_b}{\bar \Omega_a-\bar X_a+ \bar \Omega_b - \bar X_b}
\end{align*}
上面公式中的a，指代的是change region这部分时间段；b，指代的是在change point 之前的那段时间段的数据；X表示一种attribute combination，比如 {'language_zh', 'country_CN', 'media_src_organic'}
\begin{align*}
\bar X_a &: X在chage region 中平均每天的聚合数 (复现用的例子就是banrole数量) \\
\bar \Omega_a &: 全局在change region 中每天的聚合数 \\
\bar X_b &: X在chage point之前平均每天的聚合数 \\
\bar \Omega_b &: 全局在changepoint之前每天的聚合数 \\
P(a|X) &: 在X的条件筛选下，changeregion中的均值 与 整个时段均值的比值\\
P(b|X) &: 在X的条件筛选下，change point之前的均值 与 整个时段均值的比值\\
P(a|\bar X) &: 在非X的条件筛选下（X的补集），changeregion中的均值 与 整个时段均值的比值\\
P(b|\bar X) &: 在非X的条件筛选下，change point之前的均值 与 整个时段均值的比值
\end{align*}
IP(X) = & \frac{\bar X_a + \bar X_b}{\bar \Omega_a + \bar \Omega_b}[P(a|X)ln(P(a|X)) + P(b|X)ln(P(b|X))] \\& + (1-\frac{\bar X_a + \bar X_b}{\bar \Omega_a + \bar \Omega_b})[P(a|\bar X)ln(P(a|\bar X)) + P(b|\bar X)ln(P(b|\bar X))]
\end{align*}
IP(X) 表示的对于attribute combination X，所对应的IP值:
IP(x) &= -\frac{1}{\bar \Omega_a+\bar \Omega_b}(\bar X_a\ln \frac{1}{P(a|X)} + \bar X_b \ln \frac{1}{P(b|X)}+(\bar \Omega_a-\bar X_a)\ln\frac{1}{P(a|\bar X)}+(\bar \Omega_b-\bar X_b)\ln\frac{1}{P(b|\bar X)})
\end{align*}
其中：
\begin{align*} P(a|X) &=\frac{\bar X_a}{\bar X_a+\bar X_b}\\P(b|X) &=\frac{\bar X_b}{\bar X_a+\bar X_b}\\
P(a|\bar X) &=\frac{\bar \Omega_a-\bar X_a}{\bar \Omega_a-\bar X_a+ \bar \Omega_b - \bar X_b}\\
P(b|\bar X) &=\frac{\bar \Omega_b-\bar X_b}{\bar \Omega_a-\bar X_a+ \bar \Omega_b - \bar X_b}
\end{align*}
\begin{align*}
\bar X_a &: X在chage region 中平均每天的聚合数 (复现用的例子就是banrole数量) \\
\bar \Omega_a &: 全局在change region 中每天的聚合数 \\
\bar X_b &: X在chage point之前平均每天的聚合数 \\
\bar \Omega_b &: 全局在changepoint之前每天的聚合数 \\
P(a|X) &: 在X的条件筛选下，changeregion中的均值 与 整个时段均值的比值\\
P(b|X) &: 在X的条件筛选下，change point之前的均值 与 整个时段均值的比值\\
P(a|\bar X) &: 在非X的条件筛选下（X的补集），changeregion中的均值 与 整个时段均值的比值\\
P(b|\bar X) &: 在非X的条件筛选下，change point之前的均值 与 整个时段均值的比值
\end{align*}
这里作者类比了信息熵的计算方式来定义得出Isolation Power
这里对于IP(X)的定义如下：(相当于对信息熵取负号）所以IP(X) 越大，意味着X把所有数据分的越纯。
\begin{align*}IP(X) = & \frac{\bar X_a + \bar X_b}{\bar \Omega_a + \bar \Omega_b}[P(a|X)ln(P(a|X)) + P(b|X)ln(P(b|X))] \\& + (1-\frac{\bar X_a + \bar X_b}{\bar \Omega_a + \bar \Omega_b})[P(a|\bar X)ln(P(a|\bar X)) + P(b|\bar X)ln(P(b|\bar X))]
\end{align*}
把上式整理化简以后可以得到和原文中相同的IP(X)定义。
在复现例子中，设-0.1为threshold，保留IP(X) > -0.1 的attribute combination，于是得到了3个候选
在复现例子中，设-0.1为threshold，保留IP(X) > -0.1 的attribute combination，于是得到了3个候选
3.4 Result Ranking
在经过了三层剪枝之后，剩下的combination已经不多，这里作者用一个ranking来给剩下的内容进行显著性排序。$ R = p_a * ln\frac{p_a}{p_b} $
其中：
\begin{align*}& p=\frac{V_{Xt}}{V_t} \\ & V_{Xt}: 对于X在时间t上所对应的聚合数（复现例子中的banrole数量）\\ & V_t: 指全局在时间t上对应的聚合数 \end{align*}
直觉上可以理解为：这个R衡量了当前的attribute combination对于整体的显著性。
对于这剩下的三个candidate，分别计算他们的result ranking
R值最大的attribute combination为：{'os_android', 'android.cn', 'region_android_cn'}
下图红线为全局的banrole情况，蓝点为对应的这个attribute combination的banrole情况，可以看到在2020-03-26的激增是符合全局激增的。
4. 个人感想
- 这篇paper的思路非常清晰，定位问题是搜索问题，然后逐步减少搜索空间，并且每个步骤都是目的明确，具体选用的算法可以根据实际情况更换。
- 实际情况中也不一定要把所有步骤走完，感觉当剩下的candidate小到可以人工遍历得到真相的时候就可以停止了。
- 在实际复现前，可以对attribute进行一些预处理，减少彼此间的相关性。比如language = zh 和 region = cn 和 pkg = com.android.cn 之间相关性很高。
- 当然这种操作只会在数据量太大导致这些维度叠加增加额外计算量的情况下考虑预处理，复现时候用的下面这个数据集1500+行，10+列的情况下保留也无所谓。
- 对于数据量大的情况下，上面三个步骤其实每个步骤内部都可以分布式进行。
- 寻找frequent itemsets本身就有分布式实现；后面两个步骤其实都只和当前attribute combination以及总体的聚合值有关。
复现代码，链接
复现代码打开显示无权限，可以再分享下吗？谢谢了。
ReplyDelete复现代码能在共享下么？
ReplyDelete