实时警报通知:微信告警通知的重要性解析
978
2023-03-31
本文目录一览:
关联分析,顾名思义就是找出哪几项之间是有关联关系的,举个例子:
以上是五个购物记录,从中我们可以发现,购买了尿布的人其中有3个购买了啤酒,那么久我们可以推测,尿布和啤酒之间有较强的关联关系,尽管他们之间看起来并没有什么联系,也就是能得到规则:
因为购物分析能较好地描述关联分析,所以又被叫做 购物篮分析 。
为了较好的描述这个分析的各种名词,我们把上面的表格重新设计一下:
把每一个购物订单中,涉及到的商品都变成1,没涉及到的变成0,也就是将各个商品的购买记录 二元化 。
当然肯定也有多个分类的情况。
那么面包,牛奶这些就叫数据集的 项 ,而他们组合起来的子集就叫做 项集 。可以为空,空集是不包含任何项的项集,如果一个项集包含k个子项,就叫做k-项集。
订单12345叫做 事务 ,某个项集在所有事务中出现多少次,叫做项集的 支持度计数 。
在上面的表格中,项集{啤酒、尿布、牛奶}的支持度计数为2,因为有两个事务(3、4)包含这一项集。
用 支持度 和 置信度 来衡量,假定存在规则 ,其中X和Y是 不相交 的项集,则支持度为:
其中N是数据集中的事务个数,相当于表示该规则在数据集中出现了多少次。
置信度为:
置信度的意思就是,在出现X的情况下,有多少次同时出现了Y,代表这个关联规则的频繁程度。
注意置信度的分母是 ,因此这个评价可能会存在一定的问题。
关联分析的核心目标就是找出支持度大于等于某个阈值, 同时 置信度大于等于某个阈值的所有规则,这两个阈值记为 和 。
为了更有效率的完成这个过程,通常把关联规则算法分为两步:
可以看出来,首先要求得频繁项集,这步骤的开销很大,但是只需要考虑支持度就可以了,第二步只考虑置信度就可以了。
下面就可以分两步来解析算法:
首先我们可以把项集联想成一个树形结构,每层代表着不同的k-项集,依层递增,非叶子节点来自于他的几个父节点的并集,如图:
我们肯定不能通过传统的方式,遍历这些节点,算出支持度,然后筛选掉不满足最小支持度的那些,这样开销太大,因此我们引入先验原理,来辅助剪枝。
这个原理不难想象,假如一个项集{a,b}是非频繁项集,那么{a,b,c}肯定也是,因为ab是,在{a,b,c}中与之关联的c必须在ab出现之后才存在,因此他的支持度肯定不会大于{a,b}。
频繁的就是支持度大于等于最小支持度的项集,非频繁就是小于的。
我们可以利用这一定理,把非频繁项集的超集一并从树中减去,这样就能大大的降低计算次数,如图:
虚线圈上的,就是在{a,b}确定是非频繁项集之后,剪掉的超集,这些是不用计算的。
根据这个原理,可以说一下Apriori算法。
根据上面说的先验原理,Apriori算法先从项集宽度最低的1开始,遍历所有的项集支持度,找出频繁项集(因为第一层在找出支持度之前),之后根据先验原理,挑选任意两个频繁项集组成2-频繁项集(很简单,如果挑非频繁的,那组成的项集就不是频繁项集了),再用2-项集挑选3-项集,直到挑选不出更高层次的项集为止,把这些项集作为 候选项集 ,如图:
图中1-项集中,啤酒,面包,尿布,牛奶的支持度大于等于3(设 为3),则由他们组成2-项集,继续筛选满足支持度不小于3的项集,再由2-项集生成3-项集,这就是 Apriori 算法筛选频繁项集的基本步骤。总结如下:
上面提到了用k-1项集生成k-项集,那么如何才能最有效率的产生k-项集呢,这里用了 的方法,也就是找到一对(k-1)-项集,当他们的前(k-2)项都相同时,进行合并,合并之后的结果就是{ },因为前k-2项是相同的。
举个例子:
上面说了如何产生候选项集,接下来就是如何更有效率的确定支持度计数了,同样,如果遍历一个一个查的话效率是很低的,我们可以用枚举的方法遍历每个事务包含的项集,以查找3-项集为例,如图:
因为我们要查3-项集,因此树状结构就分到3-项集为止。
因为3-项集的开头第一个项肯定在1,2,3之间,我们就设定这三个数为三个分支,无论到哪个节点,都严格按照这个来分(1在左,2在中,3在右),在下面的层次中如何碰到比123更大的,则再向右分,就可以得到图中的关于事务t的所有3-项集。
有了所有项集的列表,我们可以用候选项集去匹配这些项集,从而看t中是否包含候选项集,如果包含,则支持度+1。
可以使用Hash树来进行匹配,从而实现支持度计数。
如下图,就是一个Hash树的例子,每个内部节点都使用Hash函数 来确定应当沿着当前节点的哪个分支向下,所以1,4,7就到了同一分支。
我们对于单个事务,可以遍历Hash树,设事务为t,则保证所有包含属于事务t的候选3-项集的叶节点至少访问一次。
由于我们之前已经通过树的方式枚举出了t中所有的3-项集,那么我们跟这个Hash一走分支,找到对应3-项集的就+1支持度,即可算出每个候选项集的支持度。
提取规则相应的比较简单,设有 频繁项集Y ,我们忽略前件为空和后件为空的规则,每个频繁项集能产生 个关联规则,提取方法就是将Y划分为两个 非空 的子集X和Y-X,使得 满足 置信度阈值 也就是最小置信度。
同样的,提取规则也有一个原理:
参考频繁项集的寻找过程,我们可以利用树形结构对规则进行剪枝。
树的每层对应规则后件中的项数,如图:
假设规则{ } { }不满足置信度阈值的要求,那么可以丢弃后件包含{a}的所有规则,如上图所示。
至此我们经历了寻找频繁项集和提取规则的过程,基本Apriori算法就算完成了,不过还有一些需要考虑的细节。
在实际应用过程中,往往频繁项集产生的数量可能很大,所以很难表示,我们需要寻找一种方法,找到一些有代表性的频繁项集,以保证其描述性。
通常有如下两种方法:
如图:
这种表示很明显降低了需要表示项集的个数,我们需要别的候选项集,直接取极大频繁项集的子集就行,任意一个肯定都是。
但是这么做,表示不出他们子集的支持度,所以就需要再遍历数据集,确定非极大频繁项集的支持度,不是很方便。
所以我们还可以用闭频繁项集来表示。
先来看闭项集的概念:
那么闭频繁项集的概念就很好理解了:
如图,我们假设 是40%。
这种做法可以保证支持度和描述性。
之前举的例子都是二元分类的,要么1要么0,下面看多分类的,我们很容易想到可以用独热编码解决这个问题,把所有分类二元化,但是这样就存在一个问题,有的属性值可能会不够频繁,没办法成为频繁项集。
所以最好是把多分类的项根据实际情况进行分类化,不要针对每个属性都设置独热编码。
或者将不太频繁的属性值合并为一个称作其他的类别。
所以面对多分类属性,我们要做的就是:
独热编码二元化-针对这些值进行一定的合并,或者分类或者并为其他 - 删除冗余的项 - 避免包含多个来自同一属性的项的候选集(例如{ },被写到了一个候选集中,但是实际上这种情况不可能发生,由于独热编码进行的二元化而产生了这种情况,需要避免。)
我们也会遇到一些连续属性,可以通过以下几种方式处理:
这种做法有一个问题就是分类的效果取决于区间的个数和跨度,如果取不好很难得到理想的结果。
如果要验证统计出的值是否具有统计意义,可以参考假设检验中针对不同比较的不同公式,这里不再举例。
把mini-Apriori算法中的支持度代入到Apriori算法的支持度中即可。
举个例子:
想要衡量模型的好与坏,肯定要有一个评估指标,我们可以根据业务实际去评价,这是主管评价,叫做 主观兴趣度度量 ,这个显然要结合业务,所以我们要看看一些客观指标。
指标的评价往往依赖于相依表,这个相依表有点类似于混淆矩阵:
其中A,B代表在事务中出现,!A,!B代表没有在事务中出现,空列空行例如 代表A的支持度计数, 表示包含B但是不包含A的事务的个数。
最基本的就是置信度和支持度了,但是这两种指标都很难做到客观评价模型,会受到多种因素的影响。
我们可以用 兴趣因子 来衡量模型:
首先我们引入 提升度 的概念,它用于计算规则置信度和 规则后件 中项集的支持度之间的比率,
对于二元变量,提升度等价于另一种称作兴趣因子的客观度量,定义为:
其中N是事务个数。
如果
但是兴趣因子有一定局限性,看上图,{p,q}和{r,s}的兴趣因子分别为1.02和4.08,虽然p和q同时出现在88%的文档中,但是他们的兴趣因子接近于1,表明他们相互独立,另一方面,{r,s}的兴趣因子闭{p,q}的高,但是r和s很少出现在一个文档中,这种情况下,置信度要比兴趣因子更可信,置信度表明p和q之间的联系94.6%远高于r和s之间。
另外还可以引入 相关系数 ,逻辑类似于向量的相关系数:
相关度的值从-1到1,如果变量相互独立,则Φ=0。
他的局限性在于在食物中把同时出现和同时不出现视为同等重要,这往往不符合实际规律,同时对于倾斜的变量很难度量。
IS度量 可以用于处理非对称二元变量,定义如下:
IS数学上等价于二元变量的余弦度量。
但是IS取决于A和B的支持度,所以存在与置信度度量类似的问题——即使是不相关或者负相关的模式,度量值也可能相当大。
支持度,全置信度,可以应用于较大的项集,兴趣因子,IS、PS、Jaccard系数等使用多维相依表中的频率,可以扩展到多个变量。
针对大多数项具有较低或中等的频率,但是少数项具有很高频率的数据集。
交叉支持模式是一个项集 ,他的支持度比率是:
小于用户指定的阈值 。
需要保证全置信度小于上面的支持度比率,而全置信度是:
其中 .
全置信度能够确保项集中的项之间是强关联的,例如,假定一个项集X的全置信度是80%,如果X中的一个项出现在某个事物中,则X中其他的项至少也有80%的几率属于同一个事务,这种强关联模式又称 超团模式 。
Apriori算法是挖掘产生布尔关联规则所需频繁项集的基本算法,也是最著名的关联规则挖掘算法之一。Apriori算法就是根据有关频繁项集特性的先验知识而命名的。它使用一种称作逐层搜索的迭代方法,k—项集用于探索(k+1)—项集。首先,找出频繁1—项集的集合.记做L1,L1用于找出频繁2—项集的集合L2,再用于找出L3,如此下去,直到不能找到频繁k—项集。找每个Lk需要扫描一次数据库。
为提高按层次搜索并产生相应频繁项集的处理效率,Apriori算法利用了一个重要性质,并应用Apriori性质来帮助有效缩小频繁项集的搜索空间。
Apriori性质:一个频繁项集的任一子集也应该是频繁项集。证明根据定义,若一个项集I不满足最小支持度阈值min_sup,则I不是频繁的,即P(I)<min_sup。若增加一个项A到项集I中,则结果新项集(I∪A)也不是频繁的,在整个事务数据库中所出现的次数也不可能多于原项集I出现的次数,因此P(I∪A)<min_sup,即(I∪A)也不是频繁的。这样就可以根据逆反公理很容易地确定Apriori性质成立。
针对Apriori算法的不足,对其进行优化:
1)基于划分的方法。该算法先把数据库从逻辑上分成几个互不相交的块,每次单独考虑一个分块并对它生成所有的频繁项集,然后把产生的频繁项集合并,用来生成所有可能的频繁项集,最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存,每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频繁项集至少在某一个分块中是频繁项集保证的。
上面所讨论的算法是可以高度并行的。可以把每一分块分别分配给某一个处理器生成频繁项集。产生频繁项集的每一个循环结束后.处理器之间进行通信来产生全局的候选是一项集。通常这里的通信过程是算法执行时间的主要瓶颈。而另一方面,每个独立的处理器生成频繁项集的时间也是一个瓶颈。其他的方法还有在多处理器之间共享一个杂凑树来产生频繁项集,更多关于生成频繁项集的并行化方法可以在其中找到。
2)基于Hash的方法。Park等人提出了一个高效地产生频繁项集的基于杂凑(Hash)的算法。通过实验可以发现,寻找频繁项集的主要计算是在生成频繁2—项集Lk上,Park等就是利用这个性质引入杂凑技术来改进产生频繁2—项集的方法。
3)基于采样的方法。基于前一遍扫描得到的信息,对它详细地做组合分析,可以得到一个改进的算法,其基本思想是:先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则,然后对数据库的剩余部分验证这个结果。这个算法相当简单并显著地减少了FO代价,但是一个很大的缺点就是产生的结果不精确,即存在所谓的数据扭曲(Dataskew)。分布在同一页面上的数据时常是高度相关的,不能表示整个数据库中模式的分布,由此而导致的是采样5%的交易数据所花费的代价同扫描一遍数据库相近。
4)减少交易个数。减少用于未来扫描事务集的大小,基本原理就是当一个事务不包含长度为志的大项集时,则必然不包含长度为走k+1的大项集。从而可以将这些事务删除,在下一遍扫描中就可以减少要进行扫描的事务集的个数。这就是AprioriTid的基本思想。 由于Apriori方法的固有缺陷.即使进行了优化,其效率也仍然不能令人满意。2000年,Han Jiawei等人提出了基于频繁模式树(Frequent Pattern Tree,简称为FP-tree)的发现频繁模式的算法FP-growth。在FP-growth算法中,通过两次扫描事务数据库,把每个事务所包含的频繁项目按其支持度降序压缩存储到FP—tree中。在以后发现频繁模式的过程中,不需要再扫描事务数据库,而仅在FP-Tree中进行查找即可,并通过递归调用FP-growth的方法来直接产生频繁模式,因此在整个发现过程中也不需产生候选模式。该算法克服了Apriori算法中存在的问颢.在执行效率上也明显好于Apriori算法。
通常智能运维中的告警收敛场景,以机器学习算法为驱动,对海量的告警事件进行降噪和关联分析,辅助根因定位并可沉淀故障处理的知识,从而提升企业的运维效率,降低运维成本。 告警产生后,AIOps系统通过算法甄别 内容相关性(重复性、相似性)、时序相关性和拓扑相关
性 事件来进行告警事件的自动化抑制。这类收敛抑制,往往能得到99%的告警压缩率,极大地提高了告警有效性。
在一个完整的智能运维告警产品里,除了告警收敛,还可以基于故障传播链及拓扑信息 ( 可选 ), 智能发现突发故障场景;基于告警“熵值”算法,实现告警的动态优先级推荐;通过时序以及拓扑关系定位故障场景根因,并进行根因标记。当这些都可以完成时,由告警事件一步步引导的根因定位和排障,才是真正智能运维发挥了作用。
关于告警关联分析算法有哪些和告警分类的介绍到此就结束了,不知道你从中找到你需要的信息了吗 ?如果你还想了解更多这方面的信息,记得收藏关注本站。 告警关联分析算法有哪些的介绍就聊到这里吧,感谢你花时间阅读本站内容,更多关于告警分类、告警关联分析算法有哪些的信息别忘了在本站进行查找喔。发表评论
暂时没有评论,来抢沙发吧~