SLS机器学习介绍（04）：规则模式挖掘-阿里云开发者社区

文章系列链接

SLS机器学习最佳实战：时序异常检测和报警

摘要

模式挖掘中设计的几个研究较多的点，构建结构如下图所示：
模式挖掘研究路线图.png

模式挖掘的基本原理

机器学习中的规则（rule）通常是指语义明确、能描述数据分布所隐含的客观规律或领域概念、可写成若(…)则(…)形式的逻辑规则。规则学习（Rule Learning）是从训练数据中学习出一组能用于对未见示例进行判别的规则。

显然，规则集合中的每条规则都可看作一个子模型，规则集合是这些子模型的一个集成。当同一个示例被判别结果不同的多条规则覆盖时，称发生了冲突（conflict），解决冲突的办法称为冲突消解（conflict resolution）。常用的冲突消解策略有投票法、排序法、元规则法等。投票法是将判别相同的规则数最多的结果作为最终结果。排序法是在规则结合上定义一个顺序，在发生冲突时使用排序最前的规则；相应的规则学习过程称为带序规则（ordered rule）学习或优先级规则（priority rule）学习。元规则法是根据领域知识事先设定一些元规则（meta-rule），即关于规则的规则，例如发生冲突时使用长度最小的规则，然后根据元规则的指导来使用规则集。

从语言形式来讲，规则可以分成如下形式：

命题规则（Propositional Rule）
- 由原子命题和逻辑连接词（与、或、非、包含）构成简单的陈述句
一阶规则（First-Order Rule）
- 基本成分是能描述事物的属性或关系的原子公式，如表达父子关系的谓词
- 一阶规则能表达复杂的关系，因此也被称为关系型规则（Relational Rule）

序列覆盖法

规则学习的目标是产生一个能覆盖尽可能多的样例的规则集。最直接的做法是序贯覆盖（sequential covering），即逐条归纳：在训练集上每学到一条规则，就将该规则覆盖的训练样例去除，然后以剩下的训练样例组成训练集重复上述过程。由于每次只处理一部分数据，因此也称为分治（separate-and-conquer）策略。

基本算法流程：

从空规则开始，将正例类别作为规则头，然后逐个遍历训练集合中的每个属性以及取值，尝试将其作为逻辑文字增加到规则体中，再取出剩余样本尝试生成下一条规则
在属性和候选值较多时会存在组合爆炸的问题

两种序列覆盖法策略

自顶向下
- 从比较一般的规则开始，逐条添加新文本描述，以缩小规则覆盖范围，直到满足预定条件为止
- 逐条规则特殊化的过程，从一般到特殊的生成逻辑
- 该方法更容易产生泛化性能较好的规则
- 对噪声的鲁棒性较好
自低向上
- 从某一条较为特殊的规则开始，逐渐删除属性，以扩大覆盖范围，直到满足预定条件为止
- 逐条规则泛化的过程，从特殊到一般的生成逻辑
- 适合于训练样本较少的情况

集束搜索（Beam Search）

在规则学习的过程中，需要设定一个评估规则优劣的标准，例如：先考虑规则的准确率，再考虑覆盖样例数，最后考虑属性的次序。但在规程生成过程中，每次只考虑单条样本的命中情况，过于贪心，容易陷入局部最优问题。
考虑每轮保留最优的N个逻辑属性，在下一轮均用于构建候选集，再把候选集中最优的N个保留到下一轮使用。

剪枝优化方法

似然率统计量LRS(Likelihood ratio statistics)
- 其中，$m_{+}, m_{-}$分别表示训练样本集合中，正、负样本的数目
- 其中，$\hat{m}_{+},\hat{m}_{-}$分别表示规则集覆盖的正、负样本的数目

$$ LRS = 2 * ( \hat{m}_{+} * log_{2}( \frac{\frac{\hat{m}_{+}}{\hat{m}_{+} + \hat{m}_{-}}}{\frac{m_{+}}{m_{+} + m_{-}}} ) + \hat{m}_{-} * log_{2}(\frac{\frac{\hat{m}_{-}}{\hat{m}_{+} + \hat{m}_{-}}}{\frac{m_{-}}{m_{+} + m_{-}}})) $$

衡量了规则覆盖样本比例的分布与训练样本集中经验分布的差异：
- LRS越大，采用规则集进行预测与直接使用训练集正、负比例进行猜测的差别越大
- LRS越小，说明规则集的效果可能是偶然现象
- 在数据量较大的学习任务中，通常设置LRS很大（0.99）时算法停止学习

后剪枝策略REP（Reduced Error Pruning）
- 基本流程：将数据集划分为训练集和验证集，从训练集中学习到规则R后进行多轮剪枝，在每一轮穷举所有可能的剪枝操作（删除某个属性，删除某些属性），然后用验证集对该规则集进行评估，保留最好的一组规则，提高验证集上的性能
- 算法复杂度过高，在实际使用中，需要使用改进的剪枝策略：IREP
- IREP：在生成每条规则前，先将当前样例集划分为训练集和验证集，在训练集中产生一条规则$r$，立即在验证集中进行REP剪枝操作，得到新的规则$r^{*}$，将$r^{*}$覆盖的样例去除，在更新后的样例集上重复该过程。该方法可以将复杂度降低到$O(m * log^{2}(m))$

一阶规则学习

命题逻辑表达，很难处理对象之间的关系，而关系信息在很多任务中有很重要的位置，因此有比较介绍用一阶规则进行关系学习。

一阶规则学习能容易的引入领域知识，这是它相对于命题规则学习的另一大优势。在命题规则学习乃至一般的统计学习中，想要引入领域知识，通常需要两种做法：
- 在现有属性的基础上基于领域知识构造出新属性
- 基于领域知识设计某种函数机制（如正则化）来对假设空间进行约束
FOIL（First-Order Inductive Learner）是著名的一阶规则学习算法，它采用自顶向下的规则归纳策略。由于逻辑变量的存在，FOIL在规则生成时要考虑不同变量组合。FOIL使用FOIL增益来选择属性

$$ F_{Gain} = \hat{m}_{+} * ( log_{2}\frac{\hat{m}_{+}}{\hat{m}_{+} + \hat{m}_{-}} - log_{2}\frac{m_{-}}{ m_{+} + m_{-}}) $$

$\hat{m}_{+}$和$\hat{m}_{-}$分别表示增加候选文字后新规则所覆盖的正负样本数量
$m_{+}$和$m_{-}$分别表示原规则所覆盖的正负样本数量
FOIL增益与决策时增益不同，它考虑正例的信息量，并且用新规则的正例数量作为权重。

频繁模式挖掘

在关联分析中，频繁项集的挖掘最常用的方法是Apriori算法，该算法是一种先产生候选项集，之后在数据集中检验是否存在是频繁的模式，当数据集很大时，需要不断扫描数据集造成运行效率过低。而FP-Growth算法较好的解决了这个问题。它的思路是把数据集中的事物映射到一棵FP-Tree上，这过程中，只需要扫描两次数据集。

具体的算法原理和构建流程，已经有经典文章，在此引用先大佬的文章

频繁项挖掘和关联规则

模式差异化提取算法设计

问题描述
- 服务器端的所有请求日志，数据量庞大（每分钟40w条请求日志），现准备分析在10分钟之内，请求延迟大于10ms的问题的大致和那些因素相关？
解决方法
- 通过指定的筛选条件，可以得到样本数据
  - 正样本数据：Latency > 10ms
  - 负样本数据：Latency <= 10ms
- 分别挖掘正、负样本集合中频繁规则，正样本规则集合$Rule_{pos}$，负样本规则集合$Rule_{neg}$
- 将挖掘出来的规则按照一定的规则排序后，对负样本规则创建字典树，命名为$TrieTree_{neg}$
- 采用序列覆盖法，使用$Rule_{pos}$去覆盖$TrieTree_{neg}$，寻找出满足一定约束的规则$Rule_{diff}$
- 最后，将$Rule_{diff}$按照一定的规则进行合并，去掉冗余的规则
问题解决
- 正负样本采样问题
  - 若用户指定采样数量的上限，可以使用蓄水池采样算法对流式数据进行采样
  - 若仅仅给定采样比例，后台利用随机数生成规则利用均匀分布进行采样
- 连续型数值变量离散化
  - 对于待分析的数据列，其中字符型变量使用枚举方法进行离散编码
  - 对于待分析的数据列，其中数值型连续变量，需要使用一定的方法进行离散化编码
连续型变量离散化编码
- 由于离散化的方法很多，且各有千秋，若再次详述则脱离了本文主题，以后会有机会进行详细阐述，这里仅介绍实际使用的离散化方法，基于熵的离散化方法
- 熵的定义：假设数据中共有K个不同的标签（即共有K个类别），其中$m_{i}$是划分的第i个区间中样本的个数，而$m_{ij}$是第i个区间上类别为j的样本的个数，第i个区间的熵$e_{i}$如下式，其中$p_{ij}$表示$\frac{m_{ij}}{m_{i}}$，第i个区间内类别为j的样本出现的概率。

$$ e_{i} = - \sum_{j=1}^{K} p_{ij} log_{2}(p_{ij}) $$

而划分的总熵e是每个区间熵的加权平均如下表达式，其中$w_{i}$是第i个区间样本占据总体的比例，n是划分区间的总个数。

$$ e = \sum_{i=1}^{n}w_{i} e_{i} $$

平台实验结果

对数据进行摸底

针对operation_log，先观察一下请求的延迟情况

# time range: 2018-09-29 11:40:00~2018-09-29 11:55:00
* | select __time__, avg(Latency) as avgLatency from log GROUP BY __time__ order by __time__ limit 1000

15分钟内平均每秒钟的请求延迟.png

设计针对延迟指标的分割阈值，分析Latency > 10ms的关键因素
- 统计下正负样本的数量
```
* and Latency > 10000 | select COUNT(*)
```
- 统计下负样本的数量
```
* and not Latency > 10000 | select COUNT(*) as "Latency<=10ms"
```

差异化模式挖掘

针对上述结果编写SQL Query语句进行分析

参数的简单估计

1. 实际样本集合中的正负比例
posSample / negSample: 6891 / 4927624 = 0.001398442738
2. 设定的目标采样比例
posSample : negSample = 1: 10
3. 设置正样本全部采样
posSampleRate = 1.0
4. 估算负样本的采样率
negSampleRate = 0.001398442738 * 10 = 0.01398442738 ~ 0.014

SQL分析语句编写

* | select pattern_diff(array[ Category, ClientIP, ProjectName, LogStore, Method, Source, UserAgent ], array[ 'Category', 'ClientIP', 'ProjectName', 'LogStore', 'Method', 'Source', 'UserAgent' ], array[ InFlow, OutFlow ], array[ 'InFlow', 'OutFlow' ], Latency > 10000, 0.1, 1.0, 0.014) limit 1000

分析结果部分如下
- 各字段说明
  - possupport：查找出来的部分规则在正样本中的支持度（覆盖率）
  - posconfidence：查找出来的部分规则在正样本中的置信度
  - negsupport：查找出来的部分规则在负样本中的支持度（覆盖率）
  - diffpattern：挖掘出来的差异化模式（可以直接作为条件进行筛选）