·504· 智能系统学报 第16卷 升、平稳和下降3种，用q1.92、9表示，q表示时 X表示叶子节点所在的列表，x为树的叶子节 间序列名。例如：TA=(a2,a,a1,a3,a1,a3,a1,a1)是一条 点，也是列表的部分项，即X中的项需要满足某 符号化后的时间序列数据，将其用趋势项一位置 些条件后才能成为树的叶子节点。，表示列表 表示为list_A=[{a1(2,4,6,7)},{a2:(0,1)},{as(3,5)], Y的项。loc list表示叶子节点信息表与列表项位 其中，{a2:(0,1)}表示趋势项a2在第0和第1个时 置表的信息交集，其信息量用loc count表示， 区内出现。 data表示仅包含频繁项的数据集，min_supc表示 1.2性能比较与分析 最小支持度计数。 显然事务集表示法并没有减少原数据量，而 算法SFT算法 趋势项-位置表示法只保留每个趋势项，相同趋 输入data,min supc; 势项则用位置索引代替。由于特征表示数据是各 输出频繁K项集。 类算法挖掘工作的基础，其对算法运行效率具有 1)以Root为根，首条时间序列的所有项为 很大影响，因此有必要从转换时效和转换后数据 x,构建一棵基础树； 的内存占用情况对上述2种表示法的性能进行比 2)让所有叶子结点x,与时间序列X后的所有 较和分析。实验采用python程序将后文使用的 Y序列进行匹配计算； 3条股票时间序列数据分别进行事务集表示和趋 3)对x,与y,求loc_Iist,并判断loc_count 势项-位置表示，每条数据量为5343，共16029个 是否不小于min supc: 数据。实验结果如表1所示。 ①是，将loclist作为的节点信息表，y,作 表12种表示法的性能比较 为叶子节点，即x,。x所在的树枝节点构成频繁 Table 1 Performance comparison of two representations 项集，频繁项数即为x所在的树层，项集个数即 性能 事务集表示法 趋势项-位置表示法 为loc count。判断Y是否为最后一条时间序列： 转换时效/s 0.038 0.039 是，输出频繁K项集； 否，输出频繁K项集，重复2)、3)： 内存占用B 16560 96 ②否，不是叶子节点，舍弃。 从转换时效方面，2种表示法处理的数据量 相同，因而差异性不大：从内存占用方面，由趋势 3实例分析 项-位置表示的数据要远低于事务集表示的数 设最小支持度计数min supc为2，用趋势项- 据，因为趋势项-位置表示法以数值型(int)数据 位置表示的时间序列数据集data=[{a:(0,2,3,5, 记录趋势项的变化趋势，而事务集表示法则以字 7,9),a2:(4,6,8),a3:(1)}1,{b1:(2,3),b2:(04,5,6,8 符型(str)数据记录，由于int占用的内存要低于 9),b3:(1,7)}][{c:(3,4,6),c2:(2,7),c3:(0,1,5,8,9) sr占用的内存，因此用前者表示的数据，内存占 }]l,data可视化结果如图1所示，{b:(2,3)}表示 用情况要优于后者。 趋势项b,在第2和第3个时区内出现过。在构建 2同步频繁树 同步频繁树前，需要先去除data中的非频繁项。 鉴于经典算法Apriori和FP-growth不能直接 2 对时间序列数据进行关联规则挖掘，提出了一种 V* 可以解决上述问题的新算法，即SFT算法。新算 :b1 法通过求叶子节点与列表项间的信息交集，便可 a2:a1 判断该项是否与该树枝中的所有节点构成频繁项 集。算法总体思路：先将时间序列用趋势项-位 置表示，并去除非频繁项，再用首条时间序列构 建一棵基础树，通过求叶子节点与列表项间的信 息交集，便可以在树的生长过程中不断挖掘出频 图1实例数据可视化 繁K项集。通过给出频繁K项集所有前缀项的 Fig.1 Visualization of an instance data 信息量，便可以计算出频繁K项集的支持度与置 在data中，由于a的数量仅为l,小于2，因 信度。新方法除了适用于多条数时间序列数据外， 此去掉此非频繁项。根据SFT算法的挖掘步骤， 在小数据和大数据中，其都能取得较优的时间效 利用首条时间序列[{a:(0,2,3,5,7,9),:(4,6,8)] 率，此外还能给出频繁项集的支持度和置信度。 中的a,和a2项构建一棵基础树，如图2所示。升、平稳和下降 3 种，用 q1、q2 、q3 表示，q 表示时 间序列名。例如：TA=(a2 ,a2 ,a1 ,a3 ,a1 ,a3 ,a1 ,a1 ) 是一条 符号化后的时间序列数据，将其用趋势项−位置 表示为 list_A=[{a1 :(2,4,6,7)},{a2 :(0,1)},{a3 :(3,5)}]， 其中，{a2 :(0,1)}表示趋势项 a2 在第 0 和第 1 个时 区内出现。 1.2 性能比较与分析 显然事务集表示法并没有减少原数据量，而 趋势项−位置表示法只保留每个趋势项，相同趋 势项则用位置索引代替。由于特征表示数据是各 类算法挖掘工作的基础，其对算法运行效率具有 很大影响，因此有必要从转换时效和转换后数据 的内存占用情况对上述 2 种表示法的性能进行比 较和分析。实验采用 python 程序将后文使用的 3 条股票时间序列数据分别进行事务集表示和趋 势项−位置表示，每条数据量为 5 343，共 16 029 个 数据。实验结果如表 1 所示。 表 1 2 种表示法的性能比较 Table 1 Performance comparison of two representations 性能 事务集表示法 趋势项−位置表示法 转换时效/s 0.038 0.039 内存占用/B 16 560 96 从转换时效方面，2 种表示法处理的数据量 相同，因而差异性不大；从内存占用方面，由趋势 项−位置表示的数据要远低于事务集表示的数 据，因为趋势项−位置表示法以数值型 (int) 数据 记录趋势项的变化趋势，而事务集表示法则以字 符型 (str) 数据记录，由于 int 占用的内存要低于 str 占用的内存，因此用前者表示的数据，内存占 用情况要优于后者。 2 同步频繁树 鉴于经典算法 Apriori 和 FP-growth 不能直接 对时间序列数据进行关联规则挖掘，提出了一种 可以解决上述问题的新算法，即 SFT 算法。新算 法通过求叶子节点与列表项间的信息交集，便可 判断该项是否与该树枝中的所有节点构成频繁项 集。算法总体思路：先将时间序列用趋势项−位 置表示，并去除非频繁项，再用首条时间序列构 建一棵基础树，通过求叶子节点与列表项间的信 息交集，便可以在树的生长过程中不断挖掘出频 繁 K 项集。通过给出频繁 K 项集所有前缀项的 信息量，便可以计算出频繁 K 项集的支持度与置 信度。新方法除了适用于多条数时间序列数据外， 在小数据和大数据中，其都能取得较优的时间效 率，此外还能给出频繁项集的支持度和置信度。 X 表示叶子节点所在的列表，x 为树的叶子节 点，也是列表的部分项，即 X 中的项需要满足某 些条件后才能成为树的叶子节点。yi 表示列表 Y 的项。loc_list 表示叶子节点信息表与列表项位 置表的信息交集，其信息量用 loc_count 表示， data 表示仅包含频繁项的数据集，min_supc 表示 最小支持度计数。 算法 SFT 算法 输入 data，min_supc； 输出 频繁 K 项集。 1) 以 Root 为根，首条时间序列的所有项为 xt，构建一棵基础树； 2) 让所有叶子结点 xt 与时间序列 X 后的所有 Y 序列进行匹配计算； 3) 对 xt 与 yi 求 loc_list，并判断 loc_count 是否不小于 min_supc： ①是，将 loc_list 作为 yi 的节点信息表，yi 作 为叶子节点，即 xi 。xi 所在的树枝节点构成频繁 项集，频繁项数即为 xi 所在的树层，项集个数即 为 loc_count。判断 Y 是否为最后一条时间序列： 是，输出频繁 K 项集； 否，输出频繁 K 项集，重复 2)、3)； ② 否，yi 不是叶子节点，舍弃。 3 实例分析 设最小支持度计数 min_supc 为 2，用趋势项− 位置表示的时间序列数据集 data=[[{a1 : (0, 2, 3, 5, 7, 9), a2 : (4, 6, 8), a3 : (1)}],[{b1 : (2, 3), b2 : (0, 4, 5, 6, 8, 9), b3 : (1,7)}],[{ c1 : (3, 4, 6), c2 : (2, 7), c3 : (0, 1, 5, 8, 9) }]], data 可视化结果如图 1 所示，{b1 : (2, 3)}表示 趋势项 b1 在第 2 和第 3 个时区内出现过。在构建 同步频繁树前，需要先去除 data 中的非频繁项。 t 0 1 a1 a1 a1 a1 a1 a1 a3 a2 a2 a2 b2 b2 b2 b2 b2 b2 b3 b1 b1 b1 c3 c3 c3 c3 c3 c1 c c1 2 c2 c2 t2 t3 t5 t4 t6 C B 数值 A t/s y4 y3 y2 y1 图 1 实例数据可视化 Fig. 1 Visualization of an instance data 在 data 中，由于 a3 的数量仅为 1，小于 2，因 此去掉此非频繁项。根据 SFT 算法的挖掘步骤， 利用首条时间序列 [{a1 : (0, 2, 3, 5, 7, 9), a2 : (4, 6, 8) }] 中的 a1 和 a2 项构建一棵基础树，如图 2 所示。 ·504· 智 能 系 统 学 报 第 16 卷