Page 248 - 《软件学报》2020年第10期

3224 Journal of Software 软件学报 Vol.31, No.10, October 2020

算法 1 给出了本文从指定区间为每个窗口长度寻找最优傅里叶值个数(即,最优单词长度)的过程.首先,我
们使用监督 SFA 对训练集 D 进行转换得到数组 AF(第 2 行),其中,AF 第 1 维对应不同长度滑动窗口的序号,维
度为 max−min+1;第 2 维对应训练实例的序号,维度为 N;第 3 维为转换后的实例,维度为对应滑动窗口从该实例
上获得的子序列的个数,且实例中的每个单词长度为 maxF(若滑动窗口长度小于 maxF,则单词长度为窗口长
度).由文献[22]可知,使用单一滑动窗口对 N 个实例进行监督傅里叶符号化转换的时间复杂度为 O(|W i |×
w i logw i ),其中,w i 为第 i 个滑动窗口长度,W i 为该滑动窗口在数据集 D 上生成的子序列集合,|W i |表示集合 W i 中元
3
素个数.由于|W i |包含 O(N×n)个子序列,w i ≤n,因此,算法 1 第 2 步的算法复杂度为 O(N×n logn).然后,我们在转换
后的数据 AF 的基础上从区间[minF,maxF]中学习各滑动窗口对应的性能最优的单词长度(第 3 行~第 12 行).
在学习各窗口最优单词长度的过程中,我们依次只使用单一滑动窗口长度对训练实例进行转换(第 6 行),
这一转换过程只需要截取每个单词序列(AF[i][x][y])的前 j个字母即生成指定长度的单词,这一过程的时间复杂
度可忽略.然后在转换得到的数据集上利用交叉验证进行预测(第 7 行),并将正确预测实例数最大值对应的傅里
叶值的个数作为该窗口长度对应的最优单词长度(第 8 行~第 11 行).整个单词长度的学习过程需执行 max×
maxF×k 次模型训练和预测过程.本文我们使用的预测算法是一种适用于处理大规模稀疏表示数据的运行较快
的逻辑回归算法 [29] ,其算法复杂度取决于使用的梯度下降算法的收敛速度,这不在本文讨论范围之内.我们假定
3
使用的分类模型的时间复杂度为 T(n),则算法 1 的时间复杂度为 O(maximum(N×n logn,max×maxF×k×T(n))).实
验过程中,我们将交叉验证重数统一设为 10.
2.2 鉴别性特征生成
本节我们介绍如何对训练集和测试集中的实例进行符号化转换,这一过程是算法 1 中数据符号化转换的
主要内容.转换过程主要分为两步.
(1) 利用监督 SFA 技术将时间序列或子序列转换为一组傅里叶值序列;
(2) 利用离散化技术将傅里叶值转换为字母表中的字母.
傅里叶值的选择关系到时间序列及其子序列转换得来的特征的鉴别性强弱.不同位置的傅里叶值的鉴别
性强弱不同.我们利用 F 统计量度量每个位置的傅里叶值的鉴别性,然后选择整体分类性能最优时对应的傅里
叶值个数作为该长度窗口生成单词的长度,最后利用装箱技术将时间序列子序列对应的各最优傅里叶值转换
为字母表中的字母,这些字母共同组成一个单词,即,特征.下面介绍本文使用的傅里叶值的挑选算法.
算法 2. SelectFourierCoefficient(w i ,W,bestF).
输入:滑动窗口长度 w i ,长为 w i 的子序列集合:W,最优傅里叶值个数:bestF;
输出:最优傅里叶值序号集合:indexBestF.
1: indexBestF←∅
2: double[][] A←supervisedSFA(W)
3: double s←0
4: for int i←0 to w i −1
5: s←calculateStatistic(A[i])
6: tuple←buildTuple(i,s)
7: indexBestF.add(tuple)
8: sorted(indexBestF) according to the statistic in descending order
9: indexBestF←selectTopK(indexBestF,bestF)
10: return indexBestF
算法 2 基于指定长度的子序列集合计算各个位置傅里叶值的鉴别性强弱.首先,对原始子序列进行离散傅
里叶变换.由于单个长度为 n 的时间序列进行离散傅里叶变换的时间复杂度为 O(nlogn),因此这一过程的时间
2
复杂度为 O(N×n logn)(第 2 行).矩阵 A 中每行对应一个子序列转换得到的傅里叶值数组,A[i]表示所有子序列的
第 i 个位置的傅里叶值组成的数组(即,矩阵 A 的第 i 列).算法 2 中依次计算第 i 个位置傅里叶值的鉴别性强弱