关联规则的渐进采样算法SEE：高效与准确的平衡之道

### 关联规则的渐进采样算法SEE：高效与准确的平衡之道 在数据挖掘领域，关联规则挖掘是一项重要的任务，它能够从大量数据中发现有趣的关联关系。然而，处理大规模数据库时，直接挖掘整个数据库可能会耗费大量的时间和资源。因此，如何选择合适的样本大小进行采样，以在保证挖掘准确性的同时提高效率，成为了一个关键问题。本文将介绍一种渐进采样算法SEE，它能够有效地解决这一问题。 #### 样本大小与采样误差的关系 在实际应用中，对于一个指定的项目，获取错误项目类型的概率取决于样本大小。具体来说，样本中项目支持度的方差与样本大小的平方根成反比。这意味着，随着样本大小的增加，采样误差的影响会减小。例如，项目{面包}在3000条记录的样本中的支持度方差会比在1000条记录的样本中的方差小。这表明，3000条记录的样本将具有更小的将{面包}识别为非频繁项目的错误概率。因此，对于每个项目，随着样本大小的增加，识别其项目类型的错误概率会降低。 挖掘关联规则会生成大量的项目集。随着样本大小的减小，所有项目集错误识别其项目类型的概率会增加，因为采样误差也会随着样本大小的减小而增加。因此，如果当样本大小大于某个样本大小sn时，采样误差不能显著减小，那么sn可以被建议作为关联规则的合适样本大小。 #### 采样误差的测量 采样误差源于样本中每个项目的比例与其总体比例之间的差异。项目in在样本S中的采样误差可以定义为： - **定义1**：（样本S中项目in的采样误差） - $SE(in, S) = |Sup(in, S) - Sup(in, D)|$ - 其中，$Sup(in, S)$和$Sup(in, D)$分别表示项目in在样本S和整个数据库D中的支持度。 为了评估关联规则的准确性，需要计算所有项目集的采样误差，因为所有项目集的采样误差都会影响关联规则的结果。因此，样本S的采样误差可以定义为整个数据库中每个出现的项目集的采样误差的均方根和。 然而，使用这种测量方法来评估关联规则的模型准确性会遇到两个问题： 1. **效率问题**：检查所有项目集的采样误差效率低下，因为项目集的数量巨大。 2. **不必要的计算**：计算某些项目集的采样误差实际上是不必要的。例如，如果最小支持度指定为20%，项目{面包}的项目类型识别错误概率将接近零。因此，该项目的采样误差不会影响关联规则的准确性。 为了解决第一个问题，我们只计算1 - 项目集的采样误差。虽然计算1 - 项目集的采样误差不能完全反映关联规则的模型准确性，但通常是足够的。因为关联规则的向下闭合属性表明，1 - 项目集的采样误差会影响2 - 项目集、3 - 项目集等的准确性。因此，计算1 - 项目集的采样误差是确定样本大小是否足以挖掘关联规则的一个很好的先导。 为了解决第二个问题，我们考虑采样误差与最小支持度之间的关系。假设p表示样本比例，即$|S|/|D|$，其中$|S|$和$|D|$分别是S和D的大小。由于采样可能会导致项目支持度的变化，当项目支持度的范围(0 - 1)被划分为3个区间时，将考虑支持度变化的三种不同情况： - **区间A**：$[0, p · Min Sup]$ - **区间B**：$[p · Min Sup, Min Sup]$ - **区间C**：$[Min Sup, 1]$ 具体情况如下： |情况|描述| |----|----| |情况(1)|项目的支持度在采样后从区间C变为区间B。这些项目在D中被识别为频繁项目，但在S中被识别为非频繁项目。| |情况(2)|项目的支持度在采样后从区间B变为区间C。这些项目在D中被识别为非频繁项目，但在S中被识别为频繁项目。| |情况(3)|项目在D和S中都被识别为频繁项目。| 模型准确性通常通过召回率和精确率的组合来计算。F - 分数是一种广泛使用的测量方法，它结合了召回率和精确率。在样本S上挖掘得到的结果的F - 分数定义为： - $F - score = \frac{(\beta^2 + 1) · P · R}{\beta^2 · P + R}$ - 其中，P和R分别是精确率和召回率，β是加权值，通常设置为1以公平考虑精确率和召回率。 频繁项目集在样本S中的精确率$P(S)$和召回率$R(S)$定义为： - $P(S) = \frac{|F Ia(S)|}{|F Ia(S)| + |F Ib(S)|}$ - $R(S) = \frac{|F Ia(S)|}{|F Ia(S)| + |F Ic(S)|}$ - 其中，$FIa(S)$由属于情况(3)的项目集组成，$FIb(S)$由属于情况(2)的项目集组成，$FIc(S)$由属于情况(1)的项目集组成。$|FIa(S)|$、$|FIb(S)|$和$|FIc(S)|$是它们相应的大小。 因此，在样本S上挖掘得到的频繁项目集的准确性可以表示为： - $F(S) = \frac{2 · P(S) · R(S)}{P(S) + R(S)}$ 实际上，只有属于$