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

张伟 等:一种时间序列鉴别性特征字典构建算法 3225

统计量 F 值,然后将对应的傅里叶值序号和 F 值组成一对元组添加到集合 indexBestF 中(第 5 行~第 7 行).最后,
根据 F 值对集合 indexBestF 中的元素进行降序排列(第 8 行),并返回其中前 bestF 个元组组成的集合(第 9 行~
2
第 10 行).算法 2 的时间复杂度为 O(N×n logn).
获得子序列集合对应的最优傅里叶值序号数组后,我们对子序列进行符号化转换,傅里叶值符号化的过程
是将 real i 或 imag j 映射到符号空间的过程.下面给出将时间序列子序列转换成特征的算法.
算法 3(VLWEA). createFeature(indexBestF,S,alphabet).
输入:指定长度鉴别性最强的傅里叶值序号数组:indexBestF,子序列转换得到的傅里叶值数组:S,字母
表:alphabet;
输出:特征:word.
1: word←S.length
2: for int i=0 to |indexBestF|−1
3: letter←f(SF[indexBestF[i]],alphabet)
4: word.combined(letter)
5: return word
算法 3 给出了将时间序列子序列转换成单词的算法过程,首先,根据最优傅里叶值序号数组将转换得到的
子序列傅里叶值数组 S 中对应位置的傅里叶值依次利用装箱技术映射为字母表中的字母(第 3 行),并将获得的
字母依次组合起来构成一个单词(第 4 行),最后得到的单词序列即为一个特征.这一符号化转换过程需要在离散
化区间中执行 O(|S|×log|alphabet|)次运算 [22] .
2.3 特征选择和鉴别性特征字典构建

本节我们给出基于变长单词生成算法建立特征字典的过程,以及基于 tf-idf 的特征选择算法.首先,给出利
用可变长度的单词建立特征字典的算法过程.
算法 4. createFeatureDictionary(min,max,windowBestF[],D,alphabet).
输入:滑动窗口最小长度:min,滑动窗口最大长度:max,各滑动窗口对应的最优傅里叶值个数:windowBestF
[],时间训练数据集:D,字母表:alphabet;
输出:特征字典:dict.
1: dict←null
2: for each instance T in D
3: for int l=min to minimum(|T|,max)
4: subSequenceSet←generatingSubSequenceSet(T,l)
5: for each subsequence S in subSequenceSet
6: word←createFeature(windowBestF[l−min],S,alphabet)
7: dict.add(word,T.classValue)
8: return dict
算法 4 给出了基于训练集建立特征字典的算法过程.首先,遍历训练集中的每个实例(第 2 行);然后,利用长
度从 min 到 max 的滑动窗口在时间序列上进行滑动获得一系列子序列,并将这些子序列逐个转换为单词(第 3
行~第 6 行);最后,将不重复的单词作为特征加入到特征字典中(第 7 行).算法 4 中特征构建过程的主要部分为训
3
练集实例的 SFA 转换过程,因此,特征库构建过程的时间复杂度也为 O(N×n logn).
基于特征包的方法转换过程中会生成规模巨大的特征字典.为提高分类模型的效率,通常需要对输入模型
的特征进行选择.本文提出了一种根据不同窗口生成特征的整体分类性能来动态设定特征选择阈值的特征选
算法.下面介绍本文提出的鉴别性特征字典构建算法.
算法 5(TfIDfDynamicVLWEA). createTfIdfFeatureDict(dict,corrects[],θ).
输入:特征字典:dict,各滑动窗口对应的交叉验证分类精度:corrects[],阈值加权因子:θ;