数据挖掘中的剔除非频繁项超集法

2022-09-11

在关联规则数据挖掘中, 经典的Apriori算法需要对数据库作多次遍历, 假设一个数据库在用户指定的最小支持度的限定下, 存在的频繁项集最大长度为k, Apriori算法则需要扫描数据库k次。这严重影响算法的执行效率。这里提出采用剔除非频繁项超集法, 以布尔矩阵为基础, 只需扫描数据库三次, 克服了Apriori算法需要对数据库作多次遍历的缺点, 具有较好的时间和空间复杂度。

1 剔除非频繁项超集法原理

剔除非频繁项超集法的原理是:非频繁项的超集仍是非频繁项。Apriori算法或其它的关联挖掘算法通常是直接求频繁项, 本算法思路是求2-项非频繁项, 再求2-项非频繁项的所有超集, 从候选项集中剔除非频繁项的所有超集, 剩下的就是频繁项。

例如:项集I={A, B, C, D, E}, {AE, BE}是非频繁项集, 则有{A B E, A C E, B D E, ABCE, ABDE}ACDE, BCDE, ABCDE}为非频繁模式, 只要找出频繁2-项集中的非频繁项集, 然后去掉这些项集及它们的超集, 就能得到包含最大频繁项集的超集。下面叙述一下算法的思路。

1.1 初使化事务数据库

下面用一个实例来说明剔除非频繁项超集法, 已知minsup≥2 (minsup为最小支持度) 。

项集I={A, B, C, D, E}, 事物数据库由下列事务组成:T1={A, B, E}, T2={B, D}, T3={B, C}, T4={A, B, D}, T5={A, C}, T6={B, C}, T7={A, C}, T8={A, B, C, E}, T9={A, B, C}。将事务数据库排序后再转化为布尔矩阵存储形式, T 1={1 1 0 0 1}, T 2={01010}, T3={01100}, T4={11010}, T5={10100}, T6={01100}, T7={10100}, T8={11101}, T9={11100}。

1.2 第1次遍历数据库

求频繁1-项集和非频繁1-项集。扫描的数据库不再是原始数据库, 而是布尔数据库, 统计支持度≥minsup的所有项, 即在布尔矩阵数据库中, 在某项的垂直方向出现“1”的个数。统计结果如下:候选1-项集{A}、{B}、{C}、{D}、{E}的支持度分别为6、7、6、2、2。频繁1-项集{A}、{B}、{C}、{D}、{E}的支持度分别为6、7、6、2、2。这里求得了候选1-项集和频繁1-项集, 没有非频繁1-项集。

1.3 第2次遍历数据库

候选2-项集{A, B}{A, C}{A, D}{A, E}{B, C}{B, D}{B, E}{C, D}{C, E}{D, E}的支持度分别为4, 4, 1, 2, 4, 2, 2, 0, 1, 0。频繁2-项集{A, B}{A, C}{A, E}{B, C}{B, D}{B, E}的支持分别为4, 4, 2, 4, 2, 2。非频繁2-项集{A, D}{C, D}{C, E}{D, E}的支持度1, 0, 1, 0。

求频繁2-项集和非频繁2-项集。求候选2-项集方法是在布尔矩阵数据库中, 将两个项对应的布尔值相“与”, 再统计相与结果为1的个数。支持度≥minsup的为频繁2项集, 反之为非频繁2-项集。

1.4 第3次遍历数据库

求长度≥3候选项和非频繁2-项集的超集。项集I={A, B, C, D, E}, 项集I所有的长度大于等于3的子集为:

G={A B C, A B D, A B E, A C D, A C E, ADE, BCD, BCE, BDE, CDE, ABCD, ABCE, ABDE, ACDE, BCDE, ABCDE}。再在集合G中剔除非频繁2-项集{AD, CD, CE, DE}的超集, 最后可得出频繁项集为{ABC, ABE}。

2 剔除非频繁项超集法与Apriori算法的比较

剔除非频繁项超集法的效率高于Apriori算法。下面从扫描数据库的次数、时间复杂度和空间复杂度三方面进行比较。对于一个事务数据库D, 设它的频繁项集的最大长度是k, 比较结果为:

(1) 从扫描数据库D的次数来看, 当k=1, 2, 3时, 两种算法须扫描D的次数相同;当k>3时, 剔除非频繁项超集法扫描D三次, 而Apriori算法须扫描数据库k次。

(2) 从算法的时间复杂度来看, 当求频繁1-项集时, 二者的时间复杂度均为n;当求频繁2-项集时, 二者的时间复杂度均为n2;当求长度≥3的频繁项集时, 剔除非频繁项超集法时间复杂度为nk;而对于Apriori算法来说, 在产生任一长度为k1 (3≤k1≤k) 的频繁模式的过程中, 要对频繁 (k1-1) -项集的频繁模式的每一项进行比较, 以产生长度为k的频繁模式集的候选集, k1的最大值是k, 所以, 这一过程的时间复杂度是nk-1, 又因为须对每一长度为k1 (3≤k1≤k) 的模式均作同样的工作, 因此总次数为:T (n) =n1+n2+…+nk-1= (nk-n) / (n-1) =O (nk) , 其时间复杂度也是O (nk) 。

(3) 从空间复杂度来看, 二者所需的内存空间是存储强关联规则、频繁模式集的候选集和频繁模式集的空间。二者产生的频繁模式集及强关联规则是相同的, 因而只需看产生的候选集的规模的大小。Apriori算法在求长度为k1的候选集时, 可以覆盖长度为k1-1的候选集, 只需存储每一长度k1 (3≤k1≤k) 的候选集;剔除非频繁项超集法须将长度大于等于3的所有候选模式集中存储。所以, 剔除非频繁项超集法存储候选集所须的内存空间, 将大于Apriori算法存储候选集的内存空间, 但小于 (k-2) 倍Apriori算法存储候选集的内存空间。