对一个关联规则序贯抽样算法的改进与效率分析，本文主要内容关键词为：算法论文,效率论文,规则论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
中图分类号：TP301.6;O212 文献标识码：A
引言
关联规则是数据挖掘模式发现中一种重要的探索性数据分析方法。从应用来看，关联规则发现是从交易数据库中找出统计关联较大的商品，从而发现有价值的购买行为模式，这些模式的提取可为商品货架布局、存货控制、多目标客户营销和交叉配售等业务管理提供决策支持[1]。然而，关联规则引起研究的兴趣不仅限于是因为规则本身可以作为知识产生商业价值，对关联规则计算算法的探索在机器学习计算复杂性问题中具有普遍意义。关联规则算法效率的评价分析，也是目前数据挖掘中亟待突破的难点问题之一。
最初的关联规则发现算法多为静态一次性抽样算法，其中较有权威性的算法是Agrawal、Imielinski和Swami[2]于1993年提出的算法Apriori。H.Toivonont[3]提出将一次性抽样算法BSAI与Apriori算法结合训练关联规则，并根据PAC学习理论计算训练样本的最小样本量为
，其中│H│表示待挖掘规则的条数，ε表示错误率，而δ表示置信度。传统的一次性抽样算法至少存在两方面的问题：①一次性抽样算法虽然在理论上保证了结果的高精度，然而当用于商品种类过多，交易量非常大的关联发现，则计算时间是相当可观的，甚至是不可在有限年内解决；②一次性抽样算法很难应用于联机分析，这些问题将限制Apriori算法的使用。Carlos Domingo[4]提出了基于序贯抽样理论设计的可升级性算法ASAR，证明了ASAR算法可以有效地产生频繁集，并且比一次性抽样算法需要更少的样本。序贯抽样算法事先不固定样本容量，通过序列抽取样本的方式，不断缩小备选规则集的选择范围，逐步淘汰候选规则集，从而降低算法对样本量的实际的运行时间，提高算法的执行效率。该算法的提出为用更少的样本得到在重要的规则提出了新的思路。这种算法与最初的Apriori算法没有本质性的结合，这使得ASAR并没有充分利用事务型数据库的特点进行设计，因而仍然会出现理论样本量过高的表现。
本文由两部分构成，第一部分提出Apriori和ASAR相结合的算法ApASAR，给出该算法的理论停止时间的结果和证明，第二部分给出部分通过模拟实验比较APASAR,ASAR和BSAR三种不同算法的运行效果。
一、ApASAR算法的基本设计原理
关联规则发现的效率主要由频集计算效率体现。提高频集计算效率的最主要的方法是将候选集组织成树状结构，树的根节点表示成一个候选规则，它的子树则是该候选规则的从属规则。Apriori算法是其中的典型，它利用了频繁集组合的向下封闭性，将所有可能的规则组合按照
项集依次排列，构成搜索空间，这样当项集中的某个项规则组合成为大项集中的一员，则它的
项规则组合(i=1,…,k-1)都会成为大项集中的一员，如果有很多规则组合不会出现在候选集中，那么就可以在设计的时候，将候选规则集的规模不固定，候选规则集里的规则组合随着抽样的进行，不断更新，更新的可能结果有三种：①在候选规则集中加入新的规则组合。②将候选集中表现突出的规则组合晋升至大项集中。③将候选规则集表现太差的规则组合淘汰。如上一节所示，结合Apriori和规则更新而设计的算法，我们称为ApASAR。
表1 模拟规则集的分布
最小值
1/4分位数 中位数 平均数 3/4分位数 最大值 偏度
Min Q1 Median
Mean
Q3 Max
Skew
0.003162
0.01249
0.04188 0.08842 0.1153
0.3044 3.2
由这些规则集产生随机样本共设σ为0.1，δ取值为0.05。所有可能的规则集个数为
，分别实施三种算法，观察候选规则集中待检验规则的数量随样本量增加的递减情况，如表2所示。
表2 三种算法模拟停止时的样本量
一次性抽样Apriori
ASAR
APASAR
算法模拟停止时的样本量 6万 2万
1.5万
候选规则集中最多的规则数
-
8万
4万
实际上，一次性抽样的样本量为6万。在序贯抽样算法中，随着样本量的增加，ASAR算法仅用了2万左右的样本就可能使得剩余备选规则数达到稳定状态，而APASAR则平均只需1.5万样本量，就能使得剩余备选规则数达到稳定状态。从候选规则集的规则数看出，APASAR候选集中最多的规则数是4万，比ASAR最多的规则数8万占有更少的空间，这是因为在设计算法的时候，利用了规则搜索空间的分布特点，增加了每个频集系列效应的循环。
表3 理论停止时间和实际停止时间比较
停止时间 BSAR
ASAR
ApASAR
理论停止时间
0.03
15008
7393
7967
实际停止时间
0.03
- 5383
3875
理论停止时间和实际停止时间，如表3所示。表3中还显示了算法的效率，笔者选择了候选规则中最后淘汰的规则个数和没有进入计算的规则个数，用于刻画算法的效率。
由表2和表3以及前面的分析中，可以得到序贯抽样算法与一次性抽样相比较所具有的几个特点：
1.一次性抽样算法的理论样本量比ASAR和ApASAR都大，这是因为一次性抽样样本量的计算采用的是一致的估计精度，而序贯抽样算法采用的是不断变小的精度，从而导致样本量的需要是逐渐增加的，而增加到可以允许的精度范围内，可以提前停止算法，从而节省了总的样本量。而在理论停止时间上，ASAR算法对样本量的要求稍低于ApASAR。
2.从实际的停止时间来看，ApASAR比ASAR的停止时间要短的多，但是ApASAR的停止时间大约占理论停止时间的一半左右，而ASAR的实际停止时间占理论时间的比例大约2/3左右，这说明对ApASAR的算法的执行效率应该进行更深层次的挖掘。
3.最小支持度和最小支持度上界之差对算法的理论停止时间和实际停止时间的影响是明显的。选择较大的可以比较明显地降低所需要的样本容量。
4.在算法的执行效率上，ApASAR最终淘汰的规则集是很少的，r=0.1的时候，最后淘汰的规则占所有规则的比例只有389/1024=38%，而在ASAR算法中，最后淘汰的规则集个数占所有规则的比例为60%。没有被抽样的数据所支持的规则集的比例大约占85%，从平均的意义上来看，正是由于这些规则没有进入，使得内存空间节省了一半。
通过以上实验，我们可以得到如下结论，ApASAR无论在实际停止时间上，还是在算法的规则空间占有上，都显示出ASAR和ApASAR比BSAR算法具有较强的优势，而ApASAR则在内存空间的节省方面又迈出了重要的一步。