[科普中国]-关联规则模板

关联规则模板，是形如X→Y的蕴含式，其中X和Y分别称为关联规则的先导和后继。其中，关联规则XY，存在支持度和信任度的固定格式。

效益度的高效关联规则挖掘算法关联规则挖掘算法中常用的支持度和可信度是对关联规则在统计意义上的有效性度量，在挖掘结果的有用度上缺乏指导作用，它们不能作为有用性的指标。从数据挖掘的最终目的出发定义了基于最终用户实际目标 的效益度指标，并对最小效益度筛选性质进行了论证，提出了一种快速有效的关联规则挖掘算法。讨论了从关联规则的兴趣模板和限制模板转换到效益度的方法。实验结果表明，效益度指标具有支持度与可信度不可替代的作用；该算法的最小效益度剪切技术是有效的，不仅可以较大幅度地提高算法速度，而且可以作为规则模板的统一实现算法以及提供更精确的控制。1

存在的问题及已有的相关问题已有的研究大多数是基于支持度和可信度框架的完善和改进。在实际应用中，人们发现依靠支持度和可信度框架选出的规则不理想，发现的某条关联规则即使可信度和支持度都很高，仍没有实际意义甚至是误导性的，满足最小支持度和最小可信度条件的规则并不都是人们感兴趣的。注意到这2个统计指标的缺陷后，不断有研究人员从不同的角度提出选择感兴趣的或剪除不感兴趣的规则的办法。兴趣度的概念和规则模板的概念是其中最有代表性的2类改进。思路是定义称为兴趣度的度量值，把一条规则的兴趣度定义为基于统计独立性假设的真正的强度与期望的强度之比。Sri-kant等人给出了感兴趣规则的定义。Klemettin-en等人提出了关联规则的模板概念，用户可用包含模板来确定哪些规则是令人感兴趣的，而用限制模板来定义哪些规则不感兴趣。对大多数的数据挖掘模型或算法的使用者来说，提高企业的盈利或效益才是真正的有用标准，投入产出比是企业决策者最终关心的。因此，应该从数据挖掘用户的最终目标的角度，考虑解决可信度和支持度在有用度上的不足。1

效益度与规则模板的关系及其转换关联规则模板的概念与人们通常的认知方法相近并且直观，是一种可以让用户较清楚地表达自己感兴趣和不感兴趣的关联规则的一种好方法；而直接表达效益度中涉及的概念相对复杂。定性的方法从规则的外形来选择有用的规则，通过定量的手段从用户的使用目标来衡量规则的有用度。虽然有些差异，但从作用和目标来看两者是相同的。

实际上，从关联规则模板转换到效益度的方法相当简单。可以把结果中感兴趣的属性项的Pik设为1，不感兴趣的设为0；把条件中感兴趣的属性项的Cik设为1，不感兴趣的设为某一大数，而完全不感兴趣的设为∞(实际中可取一个比较大的正数)。另外，可以把感兴趣的程度分为不同的级别，从而可以区分感兴趣的不同程度，实现对兴趣模板的改进。1

大规模网络安全态势分析中的报警关联挖掘在对传统的关联规则和序列规则相关概念和算法的讨论基础之上，过渡到报警日志挖掘的具体问题上来。在挖掘报警关联规则过程中，由于报警日志数目庞大，当最小置信度设置较小时，传统的关联规则挖掘算法效率低下，而且不可避免的生成大量无用的关联规则。鉴于问题，引出了几种筛选报警关联规则结果的几种方法，详细讨论了通过制定报警关联规则模板的方法来减少无用规则的生成；通过引入兴趣度评价标准改进支持度——置信度框架，重新评价关联规则的价值；并结合报警关联规则模板和兴趣度，提出了MFP-template算法。实验证明，MFP-template算法不仅可以缩短挖掘时间，降低耗费的系统资源，而且能减少大量无用的关联规则，生成用户更感兴趣的知识。2

报警关联规则结果筛选在完成频繁项集的挖掘后，根据频繁项集的每一个非空子集生成相应的关联规则，其中无疑参杂了大量用户不感兴趣的规则，如果频繁项集数目庞大，产生的无用的关联规则数目将更为巨大。因此需要对挖掘结果进行筛选。在关联规则中挑选出用户感兴趣的规则并不是一件容易的事情，删除无用规则的同时很有可能删掉很有价值的规则。删减无用、冗余的关联规则，可以从以下几个方面入手：

(1)用主属性参照剪枝。将主属性作为剪枝的条件。在报警记录中的各种属性存在权重关系，主属性在描述报警数据方面起到决定性的作用，将此种属性看作一个记录的本质属性，其它属性作为非本质属性用来描述辅助信息。报警记录通常由时间、源主机地址、目的主机地址、源端口、目的端口、报警名称等属性字段组成，这些都描述了报警的基本属性即主属性，一个项集必须包含主属性的值。通过剪枝操作，可以除掉不包含主属性的频繁项集，从而删除了有这种频繁项集生成的关联规则。

(2)使用用户定制的规则模版。用户感兴趣的关联规则只限于有限的几种类型，若能够由用户定制相应的规则模板，将其运用到频繁项集的挖掘过程中，不仅能够删除大量不符合规则模板的规则，还能提高频繁项集的挖掘效率。

(3)改进关联规则的评价体系。在挖掘时，仅满足最小支持度和最小置信度的阈值产生的规则不一定都是有用的，最小支持度和最小置信度的评价体系并不能完全揭示关联规则的价值，所以需要引入其它评价关联规则的方法，比如兴趣度等。

(4)规则合并。关联分析提取的关联规则很多，其中有些规则只有一些细小的差别，但其反映的本质入侵行为是一致的，这就需要将类似的模式合并，合并的原则是：多条规则的左右两边有部分相同，或者他们的左边和右边都能分别被合并。2

MFP-template算法在报警日志的关联规则挖掘过程中，最突出的问题就是算法的效率问题和最小支持度的选择。如果选择效率低下的MApriori算法，最小支持度不能设置过小，而且能够支持的报警日志的规模极其有限。当最小支持度设置过高时，挖掘出来的是显而易见的规则，而报警日志库中新颖的，有价值的规则都是隐含在出现频度有限的报警中，设置过高的最小支持度很容易漏掉这些规则。所以关联规则挖掘过程中，要求最小支持度设置尽量低一些，这就对挖掘算法的性能提出了更高的要求，而且当最小支持度设置较低时，大量无用规则的泛滥严重影响了关联规则挖掘的可用性；关联规则模板可以限制关联规则的生成类型，只生成用户感兴趣的规则，减少了无用规则的生成；在此基础上，用兴趣度来评价规则价值的高低，进一步指导用户发现报警日志中有用的知识。MFP-template算法就是在上述情况下提出的。MFP-template算法利用了MFP-growth算法中FP树这种压缩的数据存储结构，采用以下分治策略：

(1)将提供频繁项集的报警日志库压缩到一棵频繁模式树FP-tree，保留项集的频度计数和维度属性；

(2)然后将这种压缩后的数据库分成一组条件数据库，根据已找到的频繁模式将原始大数据库分割成若干数据子集，由局部频繁模式组合得到更长的频繁模式；在频繁模式增长的过程中，利用关联规则模板约束模式的增长，只生成模板需要的模式，并计算其支持度，这样不仅删去了大量无用的频繁项集，而且加快了算法的收敛速度，实现了更高的性能。

安全事件报警日志是一个多属性的记录集，至少包括以下几个字段：时间、报警名称、目的 IP、目的端口、源 IP、源端口等。例如：

03/07-23:50:02·146207 ， RSERVICES rsh root ， 202·77·162·213 ， 514 ，172·16·115·20，1023，TCP。

报警关联规则就是在这样的报警日志库中进行。同基本的关联规则挖掘一样，报警日志的关联规则挖掘也由两个步骤组成：

(1)通过用户给定的最小支持度(min_supp)，寻找所有的频繁项目集。

(2)在每个频繁项目集中，寻找相应的关联规则。第一步，采用MFP-template算法完成频繁项集的挖掘，第二步，在每个频繁项集中，按照关联规则模板，寻找兴趣度大于1的关联规则，支持度和置信度作为评价关联规则的辅助指标。2

实验结果与分析实验由以下几个部分组成：

(1)首先实现MFP-template算法，设置最小支持度和最小兴趣度，对实际环境中的IDS报警日志按关联规则模板约束完成频繁项集挖掘，生成关联规则，并对结果进行分析。

(2)设置一定的最小支持度，对不同规模的报警日志库，分别运用MApriori算法、MFP-growth算法和MFP-template算法进行频繁项集的挖掘，比较它们的运行时间。

(3)设置一定的最小支持度，对报警日志库，运用MFP-growth算法和MFP-template算法进行频繁项集的挖掘，比较它们的运行时间，占用内存峰值的大小和频繁项集的数量。

(4)MFP-template算法在最小支持度最低的情况下对报警日志规模的可扩展性实验。2

本词条内容贡献者为:

何星 - 副教授 - 上海交通大学