4.4 风险情报关联规则算法

Apriori算法是经典的挖掘频繁项集和关联规则的数据挖掘算法，最早在1944年由R.Agrawal和R.Srikant提出。Apriori算法使用一种称为逐层搜索的迭代方法，其中k项集用于探索（k+1）项集。实现的顺序是：第一，通过对数据库进行扫描，累计数据库中每个项目的计数，并收集满足最小支持度的项目，找出一组频繁1项集的集合，记为L1；第二，使用L1找出频繁2项集的集合L2，使用L2找出L3，依此类推地进行下去，直到不能再找到频繁k项集。每个1层都需要一个数据库扫描。为提高频繁项集逐层产生的效率，Apriori算法使用频繁项集的先验性质来压缩搜索空间，这也是Apriori算法最具价值的特性。

传统的Apriori算法对新项目的敏感性问题。各类风险信息不断更新，以往原有的一些风险行为特征会逐渐消失，取而代之的是一些新的风险线索的不断出现。针对这种情况，风险信息数据库所涵盖的项目也在不断更新，减少或增加的项目之间发生的关联也在不断地变化，生成了新的关联规则。然而，传统的Apriori算法却基本没有考虑到这个问题，换言之，即便是增加了新的项目，在计算每个项目集的支持度时，算法都是根据整个数据库的风险信息记录总数进行计算，此情况不符合关联规则挖掘的目的。这种问题所产生的最大不足就是无法发现最新出现的频繁项目集，也就不能产生最新的关联规则。

传统的Apriori算法最大的缺陷就是不能有效地解决新项目的敏感性问题，这使得传统的Apriori算法无法在新汇集的数据库中及时发现新的风险威胁，更做不到对风险的提前预警。因此，对传统Apriori算法进行优化的目的，主要是加强对新出现的风险情报的敏感性。面对风险的不断出现，为使风险情报分析工作更加高效，将新出现风险的敏感性运用到对Apriori算法的优化过程中，将对风险情报发现工作起到巨大的推动作用。

目前，虽然Apriori算法本身已经得到了许多优化，但在实际应用中还仍然存在一些缺陷。比如，当数据库数量较大时，发现规则长度增加，运行时间就会大幅度增长，导致效率极度低下。因此，一些研究者相继提出了对于这一问题的优化方法。

最主要的改进方法如下：

（1）基于散列的优化方法。基于散列（Hash-Based）的优化方法可以用于压缩候选k项集的集合Ck（k>1）。在数据库中扫描每个事务时，由C1中的候选1项集产生频繁1项集L1时，我们可以对每个事务产生所有的2项集，并把其散列分布到散列表的不同容器中，增加容器的计数，在散列表中对应的容器计数低于支持度阈值的2项集不可能是频繁的，那么就由候选集中对其删除。这种技术当k=2时特别有效，其关键是构造一个有效的散列函数。

（2）减少交易次数的方法。通过减少不必要的事务的数量来减少所扫描的事务数据库的大小，以提高挖掘的效率。其基本原理是，当事务不包括任意k项集，它也必须不包括任何（k+1）项集，就可以将此类别的事务删除。

（3）基于划分的优化方法。基于划分的优化方法采用了对原始事务数据库D进行两次扫描的技术。在第一遍扫描时，首先将事务数据库D从逻辑上分成几个互不相交的块，每个部分的最小支持度计数等于D的最小支持度与该部分的事务数之积。对于每个部分来讲，查找这一部分的频繁项集，就可以称为局部频繁项集。局部频繁项集可能不是整个事务数据库的频繁项集，整个事务数据库的任何频繁项集必须以本地频繁项集的形式出现在至少一个部分中。只有如此，把所有局部频繁项集的集合作为D的候选项集，称作全局候选项集。再次扫描D，根据全局候选项集和实际最小支持度确定全局频繁项集。每个部分的大小和分区的数量取决于该部分是否可以放入内存。

（4）基于采样的优化方法。基于采样的优化方法是在一个特定的数据库A中对随机样本B进行挖掘，这种方法的不足之处就是精确度不高，但其优点也显而易见，它的有效性得到提升。样本B中的频繁项集不一定是数据库A中的频繁项集，而且数据库A中的频繁项集不一定出现在样本B的频繁项集中，因此，应该使用比最小支持度低的支持度值来搜索样本B中的频繁项集，之后通过数据库的其余部分再来计算每个项集的实际频繁度。

（5）基于动态项集计数的优化方法。基于动态项集计数的优化方法主要是将数据库进行划分，分割为标记起点的块，该算法可以在任意起点添加新的候选集。这一技术动态地评估已计数的所有项集的支持度，若某个项集的所有子集都被识别为具有频繁属性，那么就将其添加为一组新的候选项集。这种算法在数据库中执行的扫描次数比Apriori算法要少很多。