SLS机器学习介绍(04):规则模式挖掘-阿里云开发者社区

开发者社区> 阿里云存储服务> 正文

SLS机器学习介绍(04):规则模式挖掘

简介: 利用模式挖掘中的算法(Apriori Tree、FP-Growth Tree)进行相关的模式挖掘。针对文本中的各个字段信息的统计模式,得到数据中的关联关系,将海量日志中有频繁的模式进行分析。同时可以针对不同的条件进行差异的模式分析,可以快速的辅助分析日志中的有价值信息。

文章系列链接



摘要

模式挖掘中设计的几个研究较多的点,构建结构如下图所示:
模式挖掘研究路线图.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(*)

    Latency>10ms.png

    • 统计下负样本的数量
    * and not Latency > 10000 | select COUNT(*) as "Latency<=10ms"

    Latency<=10ms.png

差异化模式挖掘

  • 针对上述结果编写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:挖掘出来的差异化模式(可以直接作为条件进行筛选)

image.png
image.png


硬广时间

日志进阶

阿里云日志服务针对日志提供了完整的解决方案,以下相关功能是日志进阶的必备良药:

  1. 机器学习语法与函数: https://help.aliyun.com/document_detail/93024.html
  2. 日志上下文查询:https://help.aliyun.com/document_detail/48148.html
  3. 快速查询:https://help.aliyun.com/document_detail/88985.html
  4. 实时分析:https://help.aliyun.com/document_detail/53608.html
  5. 快速分析:https://help.aliyun.com/document_detail/66275.html
  6. 基于日志设置告警:https://help.aliyun.com/document_detail/48162.html
  7. 配置大盘:https://help.aliyun.com/document_detail/69313.html

更多日志进阶内容可以参考:日志服务学习路径


联系我们

纠错或者帮助文档以及最佳实践贡献,请联系:悟冥
问题咨询请加钉钉群:

f5d48178a8f00ad1b8e3fffc73fb9158b3f8fe10_jpeg


参考文献

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:

阿里云存储基于飞天盘古2.0分布式存储系统,产品多种多样,充分满足用户数据存储和迁移上云需求。

官方博客
链接