序列分析綜述

張傳斌，陳水標，吳偉堅

(肇慶學院,計算機科學與軟件學院，肇慶 526061)

0 引言

序列分析的應用范圍非常廣泛，如基因和蛋白質(zhì)的序列分析、信息檢索、健康分析、金融數(shù)據(jù)分析、交通流預測、天氣預報和網(wǎng)絡安全檢測等。這些都是多學科交叉的領域，具有良好的社會和經(jīng)濟研究價值，因此序列分析也一直是研究熱點。

我們可以把序列劃分為以下三個類別：

(1)符號序列

符號序列可以是由單個符號組成的簡單有序列表，如DNA序列；也可以是由符號向量組成的有序列表，如用戶每次使用軟件查看新聞的類別序列〈(軍事，新聞，歷史)，(軍事，新聞，新聞)，…，(歷史，新聞，歷史)〉。

(2)時間序列

時間序列是指按一定時間間隔順序排列的符號或數(shù)值列表，列表中的值通常是實數(shù)或?qū)崝?shù)向量，如交通流數(shù)據(jù)、水文和氣溫數(shù)據(jù)等。在時間序列中，當前元素與之前的元素具有關(guān)聯(lián)性，蘊含著研究對象的發(fā)展趨勢或周期性。

(3)復雜結(jié)構(gòu)序列

復雜結(jié)構(gòu)序列是指序列中的每個元素具有較復雜的結(jié)構(gòu)，如患者的醫(yī)療記錄，每個記錄都可能包括姓名、性別、年齡、心電圖、體溫、醫(yī)囑和用藥明細等數(shù)據(jù)。

中國管理科學研究院研究員吳興杰從中美貿(mào)易戰(zhàn)的背景切入，以《基于中美貿(mào)易戰(zhàn)的鄉(xiāng)村振興戰(zhàn)略的思想創(chuàng)新》為題，重點對鄉(xiāng)村振興戰(zhàn)略的思想創(chuàng)新進行了研究，提出：鄉(xiāng)村振興戰(zhàn)略的重點和難點在中西部落后鄉(xiāng)村，東部特別是沿海鄉(xiāng)村要實現(xiàn)從富起來到強起來再到美起來。鄉(xiāng)村振興戰(zhàn)略要從政治訴求轉(zhuǎn)化為發(fā)展的內(nèi)在邏輯進而落地的關(guān)鍵是思想的創(chuàng)新，即哲學創(chuàng)新。規(guī)避鄉(xiāng)村振興“上熱下冷→外熱內(nèi)冷→表熱實冷”的關(guān)鍵，是解決誰來干和怎么干這兩大核心問題，防止樣板化、錯位化與非農(nóng)化而偏離其正軌。

1 序列分析任務類型

序列分析的任務主要有分類和預測。符號序列主要以分類操作為主，如對新蛋白質(zhì)進行歸類，對新聞軟件的用戶進行分類等。預測任務常用于時間序列的分析，如預測交通流的趨勢、股票走勢預測，天氣預報等，時間序列也可通過分類進行分析，如對長期的全球氣溫數(shù)據(jù)進行分析，判斷那段時間是否屬于厄爾尼諾現(xiàn)象頻發(fā)的異常氣候時期。

分類任務主要有三大技術(shù)難點：①較難從序列中提取出合適的特征值，而對于絕大部分分類算法來說，特征值的好壞直接影響分類器的性能；②即使能從序列中提取出特征，其特征空間也是高維空間，計算難度很大；③某些序列甚至無法提取明確的特征值。

對時間序列的預測任務中，同樣也面臨著特征提取困難的挑戰(zhàn)，而且序列的前后元素存在耦合現(xiàn)象，特征的次序也會對預測效果產(chǎn)生較大影響。

2 序列分類方法

2.1 基于特征的分類

這種方法將序列轉(zhuǎn)換成特征向量，再使用各種分類算法進行分類。K元語義模型(K-Gram)是其中一種提取序列特征的方法。一般是指定一個K元短序列的集合，將源序列表示為短序列出現(xiàn)和缺失情況的向量，或者短序列出現(xiàn)頻率的向量，然后再使用傳統(tǒng)的分類方法進行處理[1-3]。此外還有基于模式的特征選擇方法，通過這種方法獲取滿足以下三個條件的特征：①在某個類中常見；②與該類別高度相關(guān)；③僅出現(xiàn)在該類別中。通過上述方式提取特征后，就可以進行分類，如使用樸素貝葉斯算法進行處理[4-5]。以上的方法通常是針對序列的局部進行特征提取，Aggarwal等人[6]通過小波分析，將序列分解為不同頻率的子波，從近似和細節(jié)兩個方面提取特征值，再通過K近鄰算法進行分類。

2.2 基于距離的分類

這種方法通過計算序列間的距離來進行分類，序列間的相似程度可以通過一系列距離函數(shù)來衡量，然后使用K近鄰算法、支持向量機等算法，根據(jù)序列間的距離進行分類操作[7-10]。

歐幾里德距離是最為常用的距離計算方法。假設有兩個長度為L的序列S和S′，則兩者間的距離可通過以下公式進行計算：

在蛋白質(zhì)和基因測序等應用中，不同序列的長度可能不同，動態(tài)時間規(guī)整(Dynamic Time Warping，DTW)距離[11]可用于衡量長度不同的序列的相似程度。

其主要思想是盡可能按順序?qū)π蛄兄休^相似的片段進行比較，但序列中的點不需要進行一一對應，片段間可存在一些間隔點，如圖1所示。此外，還有類似的改進算法[12-14]，通過局部對齊的方式計算兩個序列間的距離。

核函數(shù)可將序列映射到超平面，在超平面中使用支持向量機進行切分，能有效地提升長序列的分類性能。其中K-譜核(K-spectrum kernel)是應用最為廣泛的核函數(shù)[15]。Lodhi等人[16]提出一種字符串核(string kernel)方法處理文本分類，給定一個長度均為K的子序列的集合，將源序列轉(zhuǎn)換成子序列權(quán)重值的特征向量。K-譜核有許多改進算法，提升了K-譜核函數(shù)的計算效率，并對不匹配的權(quán)值也進行了適當處理[10，17]。此外還有其他類型的核函數(shù)[18-19]，并在各種符號序列分類應用中取得了不錯的效果。

圖1 動態(tài)時間規(guī)整距離的計算方式

2.3 基于模型的分類

樸素貝葉斯模型[20]原理簡單、適用性強，被廣泛應用于文本分類[21]及其他符號序列的分類任務，如基因和蛋白質(zhì)測序[22]。根據(jù)應用場景的特點，許多改良的樸素貝葉斯模型也取得了不錯的效果，文獻[25]在訓練樸素貝葉斯模型時，使用期望最大化過程去優(yōu)化參數(shù)。樸素貝葉斯模型通常要求每條序列是相互獨立的，而馬爾可夫鏈模型或隱馬爾可夫鏈模型可用于處理存在相互依賴關(guān)系的序列。Yakhnenko等人[23]使用K階馬爾科夫鏈模型處理蛋白質(zhì)分類和文本序列。Srivastava等人[24]使用隱馬爾可夫鏈模型處理生物序列，此文章的模型通過嵌入、匹配和刪除三個狀態(tài)進行學習，并會為每個訓練集中的各個類分別進行學習，在對新序列進行分類時，會使用所有訓練得到模型進行測試，將新序列歸類為可能性最高的一類。Kalpakis等人[26]使用求和自回歸平均模型(Autoregressive Integrated Moving Average Model，ARIMA)來描述時間序列，并通過計算兩個序列的線性預測編碼倒譜(Linear Predictive Coding Cepstrum)之間的歐幾里德距離來量化相似程度。

3 序列預測方法

時間序列一般具有趨勢性和周期性，如某條河流的水文數(shù)據(jù)、道路的交通流數(shù)據(jù)、某地的氣溫數(shù)據(jù)。從宏觀角度看，我們可以觀測到這些數(shù)據(jù)的趨勢或者周期波動。此外，序列也可能是服從某種概率分布隨機產(chǎn)生的，如拋擲硬幣的正反面結(jié)果的序列、粒子進行布朗運動的位置序列，我們也可以通過統(tǒng)計方法分析序列蘊含的規(guī)律。另外，由于現(xiàn)實世界存在許多偶然因素，數(shù)據(jù)測量也會引入誤差，時間序列也包含不確定性和噪聲。

3.1 傳統(tǒng)的時間序列模型

傳統(tǒng)的時間序列模型將序列分為平穩(wěn)時間序列和非平穩(wěn)時間序列兩類。平穩(wěn)時間序列是指序列通過隨機過程生成，而且其統(tǒng)計規(guī)律保持不變，即滿足均值和方差不變，任意兩個時間間隔的協(xié)方差與當前時間無關(guān)。針對這類時間序列的模型有自回歸模型(Auto Regressive，AR)、移動平均模型(Moving Average，MA)、自回歸移動平均模型(Auto Regressive Moving Average，ARMA)[27-28]。

非平穩(wěn)時間序列是指序列具有時變均值，現(xiàn)實場景中的時間序列大多是非平穩(wěn)的，如股價變化、移動軌跡等[27]。然而序列元素之間的差值可能具備平穩(wěn)性，如果一個時間序列{Xt}經(jīng)過d次差分得到的序列是一個平穩(wěn)的ARMA過程，則{Xt可通過自回歸積分滑動平均模型(Autoregressive Integrated Moving Average Model，ARIMA)進行描述。一個具體的應用例子是Kumar等人使用ARIMA預測交通噪聲的變化情況[30]。

“Box-Jenkins”方法[31]是一種求解上述四個模型參數(shù)的通用方法，其步驟如下：

(1)根據(jù)序列的圖形大致判斷序列的平穩(wěn)性，也可以通過分段計算序列的均值和方差進行判斷，更為嚴謹?shù)呐袛喾椒樵鰪V迪基-福勒檢驗(Augmented Dickey-Fuller test)[32]。如果序列為非平穩(wěn)的，則先對序列進行d次差分運算，轉(zhuǎn)化為平穩(wěn)時間序列。

(2)求第(1)步獲得的平穩(wěn)序列的偏自相關(guān)函數(shù)(Partial Auto-Correlation Function，PACF)和自相關(guān)函數(shù)(Auto-Correlation Function，ACF)，根據(jù)所求圖形確定p或q的值。

(3)根據(jù)前兩步的計算結(jié)果選取合適的模型，利用序列數(shù)據(jù)對模型進行擬合，計算出剩余的參數(shù)φ，θ，c。此步驟可通過最大似然估計[27]和EM算法(Expectation Maximization Algorithm)求解[33]。

3.2 支持向量機

支持向量機(Support Vector Machine，SVM)是一種基于統(tǒng)計學習理論的算法，在處理高維度和非線性問題時具有強大能力。支持向量機被廣泛運用于經(jīng)濟數(shù)據(jù)的預測[34-37]，這些文章的主要思想時將時間序列被映射到超平面，然后在超平面中使用最小二乘支持向量機，建立回歸方程，實現(xiàn)預測。Ip等人[38]將最小二乘支持向量機用于空氣污染狀況的預測，用于測試的時間序列中的元素是由污染水平、風向、溫度、濕度等因素組成的向量，取得了良好的預測效果。Mellit等人[39]使用最小二乘支持向量機預測氣候狀況，文章中的時間序列包含光照、氣溫、相對濕度、風速、風向和氣壓等因素，支持向量機在測試集中的效果最優(yōu)。

3.3 神經(jīng)網(wǎng)絡與深度學習

神經(jīng)網(wǎng)絡(Neural Network，NN)也稱人工神經(jīng)網(wǎng)絡，是參考生物的神經(jīng)結(jié)構(gòu)設計的一種網(wǎng)絡模型[40]。利用大量數(shù)據(jù)對有足夠數(shù)量神經(jīng)元的神經(jīng)網(wǎng)絡進行訓練，能讓神經(jīng)網(wǎng)絡學習到數(shù)據(jù)中隱含的統(tǒng)計規(guī)律，相當于建立了一個非常復雜的函數(shù)，從而實現(xiàn)對新事件的預測。Abhishek等人[41]使用反向傳播神經(jīng)網(wǎng)絡(Back-Propagation Neural Network)實現(xiàn)降水值的預測。Mellit等人[42]利用神經(jīng)網(wǎng)絡提前一天預測日照情況，幫助光伏發(fā)電廠進行能源調(diào)度。Yang等人[43]和Thomas等人[44]在病毒研究時，通過神經(jīng)網(wǎng)絡預測蛋白酶的切割位置，為藥物研制提供精準靶點，提高疾病的治療效果。

深度學習(Deep Learning)脫胎于神經(jīng)網(wǎng)絡，通過增加大量隱層，并逐層進行特征變換的方式獲取數(shù)據(jù)更深層的特征，而且克服了神經(jīng)網(wǎng)絡容易過擬合、調(diào)參困難和訓練速度較慢等問題[45]。

深度學習是當前非常熱門的人工智能研究領域之一，在圖像處理、模式識別等領域取得了豐碩成果。AlphaGo利用大量的人類對弈數(shù)據(jù)和自我對弈數(shù)據(jù)進行深度學習訓練，在與人類對弈時同時使用四個策略網(wǎng)絡進行評估和預測，擊敗了人類最頂級的棋手[46]。Hinton等人[47]總結(jié)了深度學習在語音識別方面的成果，目前已經(jīng)有大量用于商用的語音識別系統(tǒng)。Yu等人[48]提出了一個時序正則化矩陣分解(Temporal Regularized Matrix Factorization，TRMF)框架處理高維時間序列問題。Lai等人[49]提出了利用深度學習對長短時間模式進行建模，為處理各類多元時間序列數(shù)據(jù)提供了一個通用框架。

4 結(jié)語

本文介紹了序列分析任務類型和序列的分類預測方法，并闡述了分類和預測方法中所常用的各種技術(shù)如小波分析、支持向量機、人工神經(jīng)網(wǎng)絡等。這些技術(shù)方法解決了實際工作中的一些相關(guān)問題，并具有一定的實際意義和應用價值。