·508· 智能系统学报 第16卷 K项集的过程中，SFT算法不会产生候选频繁项 法，然而在数据量较大的股票数据中，该算法会 集；2)SFT算法只需要对叶子节点和列表趋势项 产生候选频繁K项集，因而其时间效率略低于 求一次信息交集，即可快速判断出频繁K项集； FP-growth算法。3)MapReduce算法通过合并具 3)由1.2节分析得出，由趋势项-位置表示的数 有相同键的频繁K-1项集，即可快速产生候选频 据，其所占内存要远低于事务集表示的数据，因 繁K项集，因而其挖掘速率要快于Apriori算法， 而导致在程序运行过程中，SFT算法的处理速度 但是正因它还会产生较多的候选项集，因此导致 要快于其他算法。 其运行效率不及余下的其他算法。4)FP- 限于篇幅有限并且考虑到各类因素对不同算 growth算法只需要扫描2次数据库，并通过头指 法的影响程度不同，因而对于每个对比算法，仅 针可以快速找到其他树枝上的相同项，因而在数 给出必要的分析和解释：1)WV Apriori算法在数 据量较大的股票数据中，其挖掘速率要优于除了 据量较少的商品数据中，具有较好的时间效率， SFT以外的其他算法，但是由于其挖掘的基础数 而在数据量较大的股票数据中，其时间效率明显 据用事务集表示，此外，在重新对事务集进行排 降低，表现出很差的稳健性。导致这种结果的原 序、构建FP-tree、提取条件模式基以及构建条件 因：①在创建0-1矩阵的过程中，每项表示一列， FP-tree过程中，消耗了较多时间，因此导致其运 每个事务表示一行，当数据量越来越大时，其创 行速率不及SFT算法。5)当最大频繁项集是 建的矩阵会越来越大，因而将会消耗更多的时 K时，Apriori算法需要扫描K次数据库，并从大 间；②由于频繁项集的挖掘是基于0-1矩阵，当矩 量候选频繁项集中挖掘出频繁K项集，因而导致 阵很大时，除了遍历矩阵需要较多的时间外，矩 其具有较低的挖掘速率。 阵占用较多内存也会影响程序的运行速率；③由 表5分别从6个层面，概括总结6种算法的 于WV Apriori算法只需要遍历一次数据库，并且 区别与联系：除了SFT算法外，其他算法都是基 在挖掘更高的频繁项集时，不断缩小矩阵，因此 于用事务集表示的数据；SFT和BM Apriori算法 当数据量较小时，其效率要高于Apriori、FP- 分别用项的位置和事务的序号代替原数据，而其 growth和MapReduce算法，正因为该算法需要遍 他算法仅仅是通过不同的方法表示保留原数据： 历完整个矩阵后才能判断项间是否构成频繁项 SFT算法与FP-growth和WV Apriori算法一样不 集，因此其运行速率不及BM_Apriori和SFT算 会产生候选频繁项集；仅有SFT算法和BM_Apri- 法。2)由于BM_Apriori算法直接求2个频繁 o算法可以直接判断频繁K项集，而其他算法则 K-1项之间的序号列表交集，即可快速找出它们 需要遍历完整个数据库才能判断；SFT和Apri 之间的所有项集个数，但是该算法的基础数据用 oi算法能给出频繁项集的支持度与置信度，而其 事务集表示，因而在数据量较少的商品数据中， 他算法不能；SFT算法与FP-growth、Mapre 其时间效率要优于除了SFT算法以外的其他算 duce和BM Apriori算法都能应用于大数据中。 表56种算法对比 Table 5 Comparison of six algorithms 对比项 Apriori FP-growth Mapreduce BM Apriori WV_Apriori SFT 基础数据表示 事务集 事务集 事务集 事务集 事务集 趋势项-位置 挖掘基础 Cu-1) 条件模式基 Co-1) 事务的序号 布尔矩阵 项的位置 候选频繁项集 有 无 有 有 无 无 直接判断频繁K项 否 否 否 是 否 是 有无sup,conf 有 无 无 无 无 有 适用大数据 否 是 是 是 否 是 显然，无论在定量分析还是定性分析中， 联规则的新方法，即SFT算法，并给出了近些年 SFT算法都要优于其他算法。 来提出的，且具有较好性能的MapReduce、 5结束语 BM_Apriori和WV_Apriori算法挖掘结果作对 比。SFT算法的总体思路是先将时间序列数据用 针对经典算法Apriori和FP-growth不适用于 趋势项-位置表示，再通过求叶子节点与列表项间 时间序列数据，提出了一种挖掘时间序列数据关 的信息交集，进而可以快速挖掘出频繁K项集。K 项集的过程中，SFT 算法不会产生候选频繁项 集；2) SFT 算法只需要对叶子节点和列表趋势项 求一次信息交集，即可快速判断出频繁 K 项集； 3) 由 1.2 节分析得出，由趋势项−位置表示的数 据，其所占内存要远低于事务集表示的数据，因 而导致在程序运行过程中，SFT 算法的处理速度 要快于其他算法。 限于篇幅有限并且考虑到各类因素对不同算 法的影响程度不同，因而对于每个对比算法，仅 给出必要的分析和解释：1) WV_Apriori 算法在数 据量较少的商品数据中，具有较好的时间效率， 而在数据量较大的股票数据中，其时间效率明显 降低，表现出很差的稳健性。导致这种结果的原 因：①在创建 0-1 矩阵的过程中，每项表示一列， 每个事务表示一行，当数据量越来越大时，其创 建的矩阵会越来越大，因而将会消耗更多的时 间；②由于频繁项集的挖掘是基于 0-1 矩阵，当矩 阵很大时，除了遍历矩阵需要较多的时间外，矩 阵占用较多内存也会影响程序的运行速率；③ 由 于 WV_Apriori 算法只需要遍历一次数据库，并且 在挖掘更高的频繁项集时，不断缩小矩阵，因此 当数据量较小时，其效率要高于 Apriori、FP￾growth 和 MapReduce 算法，正因为该算法需要遍 历完整个矩阵后才能判断项间是否构成频繁项 集，因此其运行速率不及 BM_Apriori 和 SFT 算 法。2) 由于 BM_Apriori 算法直接求 2 个频繁 K−1 项之间的序号列表交集，即可快速找出它们 之间的所有项集个数，但是该算法的基础数据用 事务集表示，因而在数据量较少的商品数据中， 其时间效率要优于除了 SFT 算法以外的其他算 法，然而在数据量较大的股票数据中，该算法会 产生候选频繁 K 项集，因而其时间效率略低于 FP-growth 算法。3) MapReduce 算法通过合并具 有相同键的频繁 K−1 项集，即可快速产生候选频 繁 K 项集，因而其挖掘速率要快于 Apriori 算法， 但是正因它还会产生较多的候选项集，因此导致 其运行效率不及余下的其他算法。 4) FP￾growth 算法只需要扫描 2 次数据库，并通过头指 针可以快速找到其他树枝上的相同项，因而在数 据量较大的股票数据中，其挖掘速率要优于除了 SFT 以外的其他算法，但是由于其挖掘的基础数 据用事务集表示，此外，在重新对事务集进行排 序、构建 FP-tree、提取条件模式基以及构建条件 FP-tree 过程中，消耗了较多时间，因此导致其运 行速率不及 SFT 算法。5) 当最大频繁项集是 K 时，Apriori 算法需要扫描 K 次数据库，并从大 量候选频繁项集中挖掘出频繁 K 项集，因而导致 其具有较低的挖掘速率。 表 5 分别从 6 个层面，概括总结 6 种算法的 区别与联系：除了 SFT 算法外，其他算法都是基 于用事务集表示的数据；SFT 和 BM_Apriori 算法 分别用项的位置和事务的序号代替原数据，而其 他算法仅仅是通过不同的方法表示保留原数据； SFT 算法与 FP-growth 和 WV_Apriori 算法一样不 会产生候选频繁项集；仅有 SFT 算法和 BM_Apri￾ori 算法可以直接判断频繁 K 项集，而其他算法则 需要遍历完整个数据库才能判断；SFT 和 Apri￾ori 算法能给出频繁项集的支持度与置信度，而其 他算法不能； SFT 算法与 FP-growth、 Mapre￾duce 和 BM_Apriori 算法都能应用于大数据中。 表 5 6 种算法对比 Table 5 Comparison of six algorithms 对比项 Apriori FP-growth Mapreduce BM_Apriori WV_Apriori SFT 基础数据表示 事务集 事务集 事务集 事务集 事务集 趋势项-位置 挖掘基础 C(k-1) 条件模式基 C(k-1) 事务的序号 布尔矩阵 项的位置 候选频繁项集 有 无 有 有 无 无 直接判断频繁K项 否 否 否 是 否 是 有无sup,conf 有 无 无 无 无 有 适用大数据 否 是 是 是 否 是 显然，无论在定量分析还是定性分析中， SFT 算法都要优于其他算法。 5 结束语 针对经典算法 Apriori 和 FP-growth 不适用于 时间序列数据，提出了一种挖掘时间序列数据关 联规则的新方法，即 SFT 算法，并给出了近些年 来提出的，且具有较好性能 的 MapReduce、 BM_Apriori 和 WV_Apriori 算法挖掘结果作对 比。SFT 算法的总体思路是先将时间序列数据用 趋势项−位置表示，再通过求叶子节点与列表项间 的信息交集，进而可以快速挖掘出频繁 K 项集。 ·508· 智 能 系 统 学 报 第 16 卷