序列分析综述

张传斌，陈水标，吴伟坚

(肇庆学院,计算机科学与软件学院，肇庆 526061)

0 引言

序列分析的应用范围非常广泛，如基因和蛋白质的序列分析、信息检索、健康分析、金融数据分析、交通流预测、天气预报和网络安全检测等。这些都是多学科交叉的领域，具有良好的社会和经济研究价值，因此序列分析也一直是研究热点。

我们可以把序列划分为以下三个类别：

(1)符号序列

符号序列可以是由单个符号组成的简单有序列表，如DNA序列；也可以是由符号向量组成的有序列表，如用户每次使用软件查看新闻的类别序列〈(军事，新闻，历史)，(军事，新闻，新闻)，…，(历史，新闻，历史)〉。

(2)时间序列

时间序列是指按一定时间间隔顺序排列的符号或数值列表，列表中的值通常是实数或实数向量，如交通流数据、水文和气温数据等。在时间序列中，当前元素与之前的元素具有关联性，蕴含着研究对象的发展趋势或周期性。

(3)复杂结构序列

复杂结构序列是指序列中的每个元素具有较复杂的结构，如患者的医疗记录，每个记录都可能包括姓名、性别、年龄、心电图、体温、医嘱和用药明细等数据。

中国管理科学研究院研究员吴兴杰从中美贸易战的背景切入，以《基于中美贸易战的乡村振兴战略的思想创新》为题，重点对乡村振兴战略的思想创新进行了研究，提出：乡村振兴战略的重点和难点在中西部落后乡村，东部特别是沿海乡村要实现从富起来到强起来再到美起来。乡村振兴战略要从政治诉求转化为发展的内在逻辑进而落地的关键是思想的创新，即哲学创新。规避乡村振兴“上热下冷→外热内冷→表热实冷”的关键，是解决谁来干和怎么干这两大核心问题，防止样板化、错位化与非农化而偏离其正轨。

1 序列分析任务类型

序列分析的任务主要有分类和预测。符号序列主要以分类操作为主，如对新蛋白质进行归类，对新闻软件的用户进行分类等。预测任务常用于时间序列的分析，如预测交通流的趋势、股票走势预测，天气预报等，时间序列也可通过分类进行分析，如对长期的全球气温数据进行分析，判断那段时间是否属于厄尔尼诺现象频发的异常气候时期。

分类任务主要有三大技术难点：①较难从序列中提取出合适的特征值，而对于绝大部分分类算法来说，特征值的好坏直接影响分类器的性能；②即使能从序列中提取出特征，其特征空间也是高维空间，计算难度很大；③某些序列甚至无法提取明确的特征值。

对时间序列的预测任务中，同样也面临着特征提取困难的挑战，而且序列的前后元素存在耦合现象，特征的次序也会对预测效果产生较大影响。

2 序列分类方法

2.1 基于特征的分类

这种方法将序列转换成特征向量，再使用各种分类算法进行分类。K元语义模型(K-Gram)是其中一种提取序列特征的方法。一般是指定一个K元短序列的集合，将源序列表示为短序列出现和缺失情况的向量，或者短序列出现频率的向量，然后再使用传统的分类方法进行处理[1-3]。此外还有基于模式的特征选择方法，通过这种方法获取满足以下三个条件的特征：①在某个类中常见；②与该类别高度相关；③仅出现在该类别中。通过上述方式提取特征后，就可以进行分类，如使用朴素贝叶斯算法进行处理[4-5]。以上的方法通常是针对序列的局部进行特征提取，Aggarwal等人[6]通过小波分析，将序列分解为不同频率的子波，从近似和细节两个方面提取特征值，再通过K近邻算法进行分类。

2.2 基于距离的分类

这种方法通过计算序列间的距离来进行分类，序列间的相似程度可以通过一系列距离函数来衡量，然后使用K近邻算法、支持向量机等算法，根据序列间的距离进行分类操作[7-10]。

欧几里德距离是最为常用的距离计算方法。假设有两个长度为L的序列S和S′，则两者间的距离可通过以下公式进行计算：

在蛋白质和基因测序等应用中，不同序列的长度可能不同，动态时间规整(Dynamic Time Warping，DTW)距离[11]可用于衡量长度不同的序列的相似程度。

其主要思想是尽可能按顺序对序列中较相似的片段进行比较，但序列中的点不需要进行一一对应，片段间可存在一些间隔点，如图1所示。此外，还有类似的改进算法[12-14]，通过局部对齐的方式计算两个序列间的距离。

核函数可将序列映射到超平面，在超平面中使用支持向量机进行切分，能有效地提升长序列的分类性能。其中K-谱核(K-spectrum kernel)是应用最为广泛的核函数[15]。Lodhi等人[16]提出一种字符串核(string kernel)方法处理文本分类，给定一个长度均为K的子序列的集合，将源序列转换成子序列权重值的特征向量。K-谱核有许多改进算法，提升了K-谱核函数的计算效率，并对不匹配的权值也进行了适当处理[10，17]。此外还有其他类型的核函数[18-19]，并在各种符号序列分类应用中取得了不错的效果。

图1 动态时间规整距离的计算方式

2.3 基于模型的分类

朴素贝叶斯模型[20]原理简单、适用性强，被广泛应用于文本分类[21]及其他符号序列的分类任务，如基因和蛋白质测序[22]。根据应用场景的特点，许多改良的朴素贝叶斯模型也取得了不错的效果，文献[25]在训练朴素贝叶斯模型时，使用期望最大化过程去优化参数。朴素贝叶斯模型通常要求每条序列是相互独立的，而马尔可夫链模型或隐马尔可夫链模型可用于处理存在相互依赖关系的序列。Yakhnenko等人[23]使用K阶马尔科夫链模型处理蛋白质分类和文本序列。Srivastava等人[24]使用隐马尔可夫链模型处理生物序列，此文章的模型通过嵌入、匹配和删除三个状态进行学习，并会为每个训练集中的各个类分别进行学习，在对新序列进行分类时，会使用所有训练得到模型进行测试，将新序列归类为可能性最高的一类。Kalpakis等人[26]使用求和自回归平均模型(Autoregressive Integrated Moving Average Model，ARIMA)来描述时间序列，并通过计算两个序列的线性预测编码倒谱(Linear Predictive Coding Cepstrum)之间的欧几里德距离来量化相似程度。

3 序列预测方法

时间序列一般具有趋势性和周期性，如某条河流的水文数据、道路的交通流数据、某地的气温数据。从宏观角度看，我们可以观测到这些数据的趋势或者周期波动。此外，序列也可能是服从某种概率分布随机产生的，如抛掷硬币的正反面结果的序列、粒子进行布朗运动的位置序列，我们也可以通过统计方法分析序列蕴含的规律。另外，由于现实世界存在许多偶然因素，数据测量也会引入误差，时间序列也包含不确定性和噪声。

3.1 传统的时间序列模型

传统的时间序列模型将序列分为平稳时间序列和非平稳时间序列两类。平稳时间序列是指序列通过随机过程生成，而且其统计规律保持不变，即满足均值和方差不变，任意两个时间间隔的协方差与当前时间无关。针对这类时间序列的模型有自回归模型(Auto Regressive，AR)、移动平均模型(Moving Average，MA)、自回归移动平均模型(Auto Regressive Moving Average，ARMA)[27-28]。

非平稳时间序列是指序列具有时变均值，现实场景中的时间序列大多是非平稳的，如股价变化、移动轨迹等[27]。然而序列元素之间的差值可能具备平稳性，如果一个时间序列{Xt}经过d次差分得到的序列是一个平稳的ARMA过程，则{Xt可通过自回归积分滑动平均模型(Autoregressive Integrated Moving Average Model，ARIMA)进行描述。一个具体的应用例子是Kumar等人使用ARIMA预测交通噪声的变化情况[30]。

“Box-Jenkins”方法[31]是一种求解上述四个模型参数的通用方法，其步骤如下：

(1)根据序列的图形大致判断序列的平稳性，也可以通过分段计算序列的均值和方差进行判断，更为严谨的判断方法为增广迪基-福勒检验(Augmented Dickey-Fuller test)[32]。如果序列为非平稳的，则先对序列进行d次差分运算，转化为平稳时间序列。

(2)求第(1)步获得的平稳序列的偏自相关函数(Partial Auto-Correlation Function，PACF)和自相关函数(Auto-Correlation Function，ACF)，根据所求图形确定p或q的值。

(3)根据前两步的计算结果选取合适的模型，利用序列数据对模型进行拟合，计算出剩余的参数φ，θ，c。此步骤可通过最大似然估计[27]和EM算法(Expectation Maximization Algorithm)求解[33]。

3.2 支持向量机

支持向量机(Support Vector Machine，SVM)是一种基于统计学习理论的算法，在处理高维度和非线性问题时具有强大能力。支持向量机被广泛运用于经济数据的预测[34-37]，这些文章的主要思想时将时间序列被映射到超平面，然后在超平面中使用最小二乘支持向量机，建立回归方程，实现预测。Ip等人[38]将最小二乘支持向量机用于空气污染状况的预测，用于测试的时间序列中的元素是由污染水平、风向、温度、湿度等因素组成的向量，取得了良好的预测效果。Mellit等人[39]使用最小二乘支持向量机预测气候状况，文章中的时间序列包含光照、气温、相对湿度、风速、风向和气压等因素，支持向量机在测试集中的效果最优。

3.3 神经网络与深度学习

神经网络(Neural Network，NN)也称人工神经网络，是参考生物的神经结构设计的一种网络模型[40]。利用大量数据对有足够数量神经元的神经网络进行训练，能让神经网络学习到数据中隐含的统计规律，相当于建立了一个非常复杂的函数，从而实现对新事件的预测。Abhishek等人[41]使用反向传播神经网络(Back-Propagation Neural Network)实现降水值的预测。Mellit等人[42]利用神经网络提前一天预测日照情况，帮助光伏发电厂进行能源调度。Yang等人[43]和Thomas等人[44]在病毒研究时，通过神经网络预测蛋白酶的切割位置，为药物研制提供精准靶点，提高疾病的治疗效果。

深度学习(Deep Learning)脱胎于神经网络，通过增加大量隐层，并逐层进行特征变换的方式获取数据更深层的特征，而且克服了神经网络容易过拟合、调参困难和训练速度较慢等问题[45]。

深度学习是当前非常热门的人工智能研究领域之一，在图像处理、模式识别等领域取得了丰硕成果。AlphaGo利用大量的人类对弈数据和自我对弈数据进行深度学习训练，在与人类对弈时同时使用四个策略网络进行评估和预测，击败了人类最顶级的棋手[46]。Hinton等人[47]总结了深度学习在语音识别方面的成果，目前已经有大量用于商用的语音识别系统。Yu等人[48]提出了一个时序正则化矩阵分解(Temporal Regularized Matrix Factorization，TRMF)框架处理高维时间序列问题。Lai等人[49]提出了利用深度学习对长短时间模式进行建模，为处理各类多元时间序列数据提供了一个通用框架。

4 结语

本文介绍了序列分析任务类型和序列的分类预测方法，并阐述了分类和预测方法中所常用的各种技术如小波分析、支持向量机、人工神经网络等。这些技术方法解决了实际工作中的一些相关问题，并具有一定的实际意义和应用价值。