Apriori算法的复杂度是多少？

Apriori算法的计算复杂度受以下因素影响：

支持度阈值 -降低支持度阈值会导致更多项集被认为是频繁的。这会对算法的计算复杂度产生不利影响，因为需要生成和计算更多候选项集。

频繁项集的最大大小也会随着支持度阈值的降低而增加。随着频繁项集最大大小的增加，算法需要对数据集进行更多次扫描。

项数（维数） -随着项数的增加，需要更多空间来存储项的支持度计数。如果频繁项的数量也随着数据的维数增加而增加，则由于算法生成的候选项集数量增加，计算和I/O开销也会增加。

事务数 -由于Apriori算法需要对数据集进行多次扫描，因此其运行时间会随着事务数的增加而增加。

平均事务宽度 -对于稠密数据集，平均事务宽度可能很高。这会通过两种方式影响Apriori算法的复杂度：随着平均事务宽度的增加，频繁项集的最大大小也会增加。事务宽度增加，事务中包含的项集更多。这将增加支持度计数期间执行的多次哈希树遍历。

频繁l-项集的生成 -对于每个事务，需要更新事务中每个项的支持度计数。假设w是平均事务宽度，此操作需要O(Nw)时间，其中N是事务总数。

候选集生成 -它可以生成候选k-项集，通过组合频繁(k - 1)-项集的每一对来确定它们是否至少有k - 2个共同项。每个组合操作最多需要k - 2次相等性比较。在最佳情况下，每个组合步骤都会生成一个有效的候选k-项集。

在最坏情况下，算法需要组合先前迭代中找到的每对频繁(k - 1)-项集。因此，合并频繁项集的总成本为

$$\mathrm{\displaystyle\sum\limits_{k=2}^w\:(k-2)|C_{k}|<\:合并成本\:<\displaystyle\sum\limits_{k=2}^w\:(k-2)|F_{k}-1|^2}$$

在候选集生成过程中还会生成哈希树来存储候选项集。由于树的最大深度为k，因此使用候选项集填充哈希树的成本为O($\mathrm{\displaystyle\sum\limits_{k=2}^w\:k|C_{k}|}$) 。

在候选集剪枝过程中，需要检查每个候选k-项集的k - 2个子集是否频繁。由于在哈希树中查找候选的成本为O(k)，因此候选集剪枝步骤需要O($\mathrm{\displaystyle\sum\limits_{k=2}^w\:k|C_{k}|}$)时间。

Ginni

更新于：2022年2月11日

浏览量：1K+

开启你的职业生涯

通过完成课程获得认证

开始学习