基于統(tǒng)計特征向量的時序符號化改進算法

李曉翠，張新玉，羅慶云，任長安

（湖南工學院計算機與信息科學學院，湖南 衡陽421002）

基于統(tǒng)計特征向量的時序符號化改進算法

李曉翠，張新玉，羅慶云，任長安

（湖南工學院計算機與信息科學學院，湖南 衡陽421002）

傳統(tǒng)基于統(tǒng)計特征向量的時間序列符號化算法不能較好地保留時序數(shù)據(jù)的特征信息，且不支持多維時間序列的符號化。為此，提出一種改進算法。對于單維時間序列，引入特殊點時間序列分割方法，在其基礎上實施符號化。對于多維時間序列，在利用基于加權(quán)屬性的主成分分析方法將多維時間序列轉(zhuǎn)化為單維時間序列后，再實施符號化。實驗結(jié)果表明，與傳統(tǒng)算法相比，改進算法具有較高的精確度，且能保留時序特征點，同時支持多維時間序列的符號化。

多維時間序列；特征向量；加權(quán)屬性；符號化；主成分分析

DO I：10.3969/j.issn.1000-3428.2015.10.029

1 概述

時序關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘領域中的研究熱點［1］，而時序符號化則是時序關(guān)聯(lián)規(guī)則挖掘的前提［2-3］。時序符號化一方面能夠壓縮時序，大幅減少時序關(guān)聯(lián)規(guī)則挖掘的時間，另一方面能夠使挖掘的時序關(guān)聯(lián)規(guī)則更加精確。但由于時序數(shù)據(jù)的密集性、隨機波動性及數(shù)據(jù)海量性，使得時序關(guān)聯(lián)規(guī)則挖掘還存在諸多問題和難關(guān)，尤其在多維時序的關(guān)聯(lián)規(guī)則挖掘方面更是如此。2003年，由Keogh等人提出了SAX符號化方法（Symbolic Aggregate Approximation）［4］，使得符號化方法進入了一個新的階段，然而SAX僅用平均值來表示近似表示時序，使得符號化的結(jié)果不夠精確。文獻［5］提出了基于統(tǒng)計特征的時序數(shù)據(jù)符號化算法（SFVS），該算法將時序符號看作矢量，而各時序子段的均值和方差則分別作為描述其平均值及發(fā)散的程度。然而該算法中同樣運用PAA方法（Piece-wise Aggregate Approximation）對時

序進行等寬分割，這樣也就同樣存在PAA分割方法的缺點：不能較好地保留時序的變化趨勢及形態(tài)，且不支持多維時序的符號化。

本文針對單維時序和多維時序，分別引入特殊點的時序分割方法和加權(quán)屬性的主成分方法，基于統(tǒng)計特征向量提出一種改進的時序符號化算法（ISFVS）。

2 基于統(tǒng)計特征特征向量的時序符號化算法

傳統(tǒng)基于統(tǒng)計特征特征向量的時序符號化算法具體過程如下：

（1）時序規(guī)格化。

時序規(guī)格化計算公式如下：

其中，yi為時序的原始值；χi為規(guī)則化后的新值；μ和 σ分別為原始時序的期望值和方差［6］。

（2）PAA分段線性表示，并求出個時序字段的平均值和方差。

用wi，si分別表示第i個子序列上的平均值和方差，則：

其中，ω為最大壓縮比，ω一般采用如下經(jīng)驗公式：

（3）根據(jù)符號集大小確定分裂點。

經(jīng)過規(guī)格化的時序服從標準正態(tài)分布，因此，可以查表得到各等概率劃分的分裂點，符號集與分裂點的關(guān)系如表1所示。

表1 k取不同值時所對應的劃分點

（4）時序符號化的實施。

若用Ai來表示字符集A中的第i個字符。符號化準則為：將所有小于 C1的預處理數(shù)據(jù)用符號 A1表示，將大于C1且小于C2的預處理數(shù)據(jù)用符號A2表示，而將所有大于Ck-1的預處理數(shù)據(jù)用符號Ak表示。用向量Xi表示第Cs（SX，2）個子序列的符號結(jié)果。 則：

3 單維時序符號化

統(tǒng)計特征向量符號化［5］在對時序符號化時，針對SAX方法的缺陷，引入了方差這一因素，能夠較好地描述時序特征，然而該方法中同樣運用PAA方法對時序等寬分割，這樣也就同樣繼承了PAA分割方法的缺點，不能較好地保留時序的變化趨勢及形態(tài)，進一步影響時序關(guān)聯(lián)規(guī)則挖掘的可信度?；谶@個缺陷，結(jié)合時序分割方法，ISFVS方法引入了基于分段點的時序分割方法［6-7］，先對時序進行分割，然后用基于統(tǒng)計特征向量符號化的方法對時序?qū)嵤┓柣?/p>

3.1 時序的分割

時序的分割是將時序數(shù)據(jù)表示成多段首尾相鄰的近似直線，能夠?qū)r序進行有效壓縮［8-9］，如圖 1所示。

圖1 時序分段線性化示意圖

時序分段線性表示記為：將長度為 L的時序的n段時序，分段線性模型表示為S，如式（6）所示：

其中，i=1，2，…，n；χiL表示第i段的起始點的數(shù)值；χiR表示第i段結(jié)束點的數(shù)值；ti表示第i段的結(jié)束時間；n表示整個時序劃分的直線段數(shù)目，tn=L。

3.2 符號化算法

單維時序符號化算法的具體步驟如下：

（1）時序規(guī)格化。

對時序?qū)嵤┓柣腔跇藴收龖B(tài)分布的等概率規(guī)則來劃分的。為了消除不同偏移量和振幅對符號化后相似性的影響，在對時序符號化之前必須先對其進行規(guī)則化處理，使時序滿足平均值為0，方差為1的高斯分布。這一步驟和統(tǒng)計特征向量符號化方法是一致的。

定義1 將規(guī)則化后的時序記為 X=｛χ1（ν1，t1），χ1（ν2，t2），…，χn（νn，tn）｝。

（2）時序的分段點。

將規(guī)則化后的時序 X=｛χ1（ν1，t1），χ1（ν2，t2），…χn（νn，tn）｝，用基于特殊點的線段化方法求出規(guī)則化時序的所有分段點。

定義2 如果時序X上的某點滿足如下條件之一：（1）νi＞νi-1且 νi≥νi+1，νi≥νi-1且 νi＞νi+1，其中1＜i＜n，則稱 χi（νi，ti）為 X的正極值點；（2）νi＜

νi-1且νi≤νi+1，νi≤νi-1且νi＜νi+1，其中1＜i＜n，則稱χi（νi，ti）為X的負極值點，稱 χi（νi，ti）為局部極值點，即轉(zhuǎn)折點。

定義3 定義時序X上的所有轉(zhuǎn)折點為 S=｛S1，S2，…，Sn｝。

定義4 如果保持轉(zhuǎn)折點Si的時間段與該序列的總長度的比值大于給定的閾值 C，則轉(zhuǎn)折點Si為該時序的分段點。正轉(zhuǎn)折點形成的分割點為正分割點，負轉(zhuǎn)折點處形成的分割點為負分割點［10］。

由中心極限定理，可得 Δti滿足 N［μ，σ2］的正態(tài)分布，其中n為局部極值點S集中元素的個數(shù)。

給定時序的最大壓縮率［11］為 P，則被保留的分割點的總數(shù)占時序長度總個數(shù)的比例應不大于（1-P），即分割點的存在概率應小于或等于（1-P）。因此，被保留的分割點的Δti應分布在［u-χσ，u+χσ］的范圍內(nèi)（σ代表偏離 u的程度），概率小于或等于（1-P），令Y表示該隨機事件，則有：

即2Φ（χ）-1≤1-P。

例如，要得到大于 90%的數(shù)據(jù)壓縮率，則由式（9）得：

查表得χ=0.13，即若極值點χi為分段點，則該點的應用分布在［u-0.13σ，u+0.13σ］范圍內(nèi)。

根據(jù)以上算法，從局部極值點集合中，選擇符合要求的分段點。

定義5 定義時間 D（S′1，S′2）≤D（S′1，S′3）+ D（S′3，S′2）上的所有分段點的所在位置集合為P=｛P1，P2，…，Pk｝。

（3）計算出各時序子段的均值和方差。

假設時序的起點位置為P0，終點位置為Pk+1，將其并入分段點位置集合 P，則 P=｛P0，P1，…，Pk，Pk+1｝，根據(jù)分段點集合P，可以將時序分割成k個子序列。用wi和si分別表示第i個子序列的平均值和方差，則第i個子序列的平均值為：

第i個子序列的方差為：

對時序預處理后，就可以根據(jù)字符集規(guī)模k（取3～20）和數(shù)據(jù)分布得到各個字符所代表數(shù)據(jù)區(qū)域的劃分點。因此，劃分點可以表示為：C=｛C1，C2，…，Ck-1｝。而劃分點C是通過將整個正態(tài)分布區(qū)間劃分成k個等概率區(qū)間的方式來確定，符號集規(guī)模 k和劃分點的關(guān)系如表1所示。

（4）時序符號化的實施。

根據(jù)預處理結(jié)果及劃分點集，將時序?qū)嵤┓柣Ｈ粲肁i來表示字符集A中的第i個字符。符號化準則為：將所有小于 C1的預處理數(shù)據(jù)用符號 A1表示，將大于C1且小于C2的預處理數(shù)據(jù)用符號A2表示，而將所有大于Ck-1的預處理數(shù)據(jù)用符號Ak表示。用Xi表示第 Cs（SX，2）個子序列的符號結(jié)果。 則：

其中，Ai1表示第i個子序列的平均值wi所在區(qū)間的符號；Ai2表示第 i個子序列的方差 si所在區(qū)間的符號。

4 多維時序符號化

目前，主流的時序符號化方法只能解決單維時序的符號化問題或者對多維時序的符號化效果不佳。然而多維時序卻普遍存在于各個領域，例如股票交易數(shù)據(jù)、移動通訊數(shù)據(jù)、氣象數(shù)據(jù)等，多維時序的數(shù)據(jù)挖掘及關(guān)聯(lián)規(guī)則的獲取也必須建立在多維時序的相似性度量上?；诖?，結(jié)合主成分分析法的思想，利用基于加權(quán)屬性［12］的主成分法將多維時序轉(zhuǎn)化成單維時序，然后按照單維時序的符號化方法對時序符號化。

4.1 基于加權(quán)屬性的主成分方法

定義6 定義多維時序［13］為：

其中，m為多維時序的維數(shù)。

利用主成分分析法，求出原變量協(xié)方差矩陣的特征值 λi，并將它們從大到小排列，依次為 λ1，λ2，…，λm，相應的特征化標準向量為 γ1，γ2，…，γm，將所得的m個主成分按由大到小的順序排列［14］，記為向量Y=（Y1，Y2，…，Ym），則主成分與原始變量之間存在如下關(guān)系：

通過以上方法將多維時序簡化成單維時序?；诩訖?quán)屬性的主成分方法摒棄了直接選取個別主成分進行降維而造成的信息丟失的弊端，同時也避免了不降維而帶來的算法復雜度高的缺陷。

4.2 符號化算法

多維時序符號化算法的具體步驟如下：

（1）用4.1節(jié)中基于加權(quán)屬性的主成分方法將多維時序轉(zhuǎn)化為單維時序；

（2）根據(jù)式（1）將上一步得到的單維時序規(guī)范化，使時序服從標準正態(tài)分布；

（3）用3.2節(jié)定義4中描述的方法，確定時序的分段點集合；

（4）由分段點集合，根據(jù)式（10）和式（11）計算出各時序子段的均值和方差；

（5）根據(jù)預設的符號集C，查表1確定各分裂點取值，從而實施對多維時序的符號化，將多維時序轉(zhuǎn)化為符號化序列。

步驟（2）～步驟（5）的具體方法與統(tǒng)計特征特征向量符號化方法保持一致，這里不再具體闡述。

5 實驗與結(jié)果分析

本文實驗的運行環(huán)境為Interl?Celeron?CPU E3300@2.50 GHz，2.50 GHz，2 GB內(nèi)存，500 GB硬盤，操作系統(tǒng)為32位W in 7，開發(fā)工具為Matlab 6.0及VS 2008，開發(fā)語言為C++及C#。為了驗證改進統(tǒng)計特征符號化算法的優(yōu)越性，及在多維時序中的可擴展性，采用了 2組數(shù)據(jù)進行實驗分析。第1組數(shù)據(jù)來源于Time Series Data Library，http：// www.robhyndman.info/TS-DL。第2組數(shù)據(jù)為開灤集團某礦的提升機運行數(shù)據(jù)。其中，第1組數(shù)據(jù)均為單維時序數(shù)據(jù)，第2組為多維時序數(shù)據(jù)（提升機運行曲線包括給定速度、包絡速度、實際速度、給定電壓、電流）。

實驗1 考察ISFVS算法是否能較好地保留時序特征點且具有較高的魯棒性。

圖2是原始序列圖，圖3是經(jīng)過加入噪音數(shù)據(jù)后的序列圖，圖4則是加入噪音數(shù)據(jù)前后的時序分段點圖。從圖4可以看出加噪后的時序分割點與原始時序的分割點變化不大，絕大多數(shù)的分割點為時序特征點且位置保持不變，這是因為算法預處理階段對時序進行了規(guī)范化處理，并且在選擇分段點時，根據(jù)中心極限定理很好的去除了局部波動點，即實驗中的噪聲數(shù)據(jù)，因此，本文通過實驗證明了改進ISFVS算法具有能保留時序特征信息且魯棒性強的優(yōu)點。

圖2 原始時序圖

圖3 加噪序列圖

圖4 分段結(jié)果

實驗2 考察ISFVS算法對單維時序符號化優(yōu)越性。為驗證ISFVS算法對單維時序符號化表示的優(yōu)越性，采用第1組實驗數(shù)據(jù)，并將ISFVS算法同SFVS算法進行比較。

圖5為ISFVS和SFVS符號化算法擬合誤差結(jié)果比較。從圖5可以看出，隨著符號集的增大，SFVS和ISFVS算法的擬合誤差逐漸減小，使得符號化后的序列逐漸接近于原始時序。同時，從圖5還可以看出

ISFVS算法比SFVS算法更快的接近于原始序列，這是由于SFVS算法在對時序分割時，采用等分的原則，沒有較好地保留時序形態(tài)模式，而ISFVS算法在對時序進行分割時，引入了特殊點的時序分割算法，該分割算法能夠較好地保留時序的形態(tài)，使得符號化后的時序能夠更加精確地表示原始時序。

圖5 單維時序擬合誤差比較

實驗3 考察ISFVS算法中提出的基于加權(quán)屬性主成分算法的多維時序符號化算法的優(yōu)越性。實驗數(shù)據(jù)為第2組數(shù)據(jù)。為了驗證ISFVS算法的優(yōu)越性，同基于主成分算法多維時序符號化算法進行比較（選取第一主成分將多維時序轉(zhuǎn)化為單維時序）。主成分算法的符號化算法簡記為PCAS。圖6給出了ISFVS和PCAS的執(zhí)行時間；圖7給出了ISFVS和PCAS在相同情況下的擬合誤差。

圖6 執(zhí)行時間比較

圖7 多維時序擬合誤差比較

從圖6和圖7可以看出，2種算法的執(zhí)行時間即算法的運行效率是差不多的，然而基于加權(quán)屬性的主成分的多維時序符號化算法在近似表示原始序列的能力上相對于PCAS有了較大的提升，由此可見ISFVS算法對多維時序符號化的優(yōu)越性。

6 結(jié)束語

SFVS算法在SAX算法的基礎上，增加了方差來描述時序，但沒有解決必須等分時序的問題，且不能較好地保留時序形態(tài)特征。因此，本文將基于特殊點的時序分割算法引入到時序符號化算法中，結(jié)合統(tǒng)計特征向量提出了改進的符號化算法，同時利用主成分分析算法將其擴展到多維時序，設計基于加權(quán)屬性的主成分多維時序符號化算法。實驗結(jié)果表明，該算法在解決了必須等分時序問題的同時，也能夠較好地保留時序形態(tài)特征，其在單維和多維時序符號化上均具有有效性及優(yōu)越性。下一步將研究時序符號化算法在數(shù)據(jù)挖掘中的應用。

［1］ Butzer P L，Nessel R J.Fourier Analysis and Approximation［M］.［S.l.］：Academic Press，2011.

［2］ Chaovalit P，Gangopadhyay A，Karabatis G，et al.Discrete Wavelet Transform-based Time Series Analysis and Mining［J］.ACM Computing Surveys，2011，43（2）.

［3］ Fu T.A Review on Time Series Data Mining［J］. Engineering Applications of Artificial Intelligence，2011，24（1）：164-181.

［4］ Lin J，Keogh E，Lonardi S，et al.A Symbolic Representation of Time Series，with Implications for Streaming Algorithms［C］//Proceedings of the 8 th ACM SIGMOD Workshop on Research Issues in Data Mining and Know ledge Discovery.New York，USA：ACM Press，2003：2-11.

［5］ 鐘清流，蔡自興.基于統(tǒng)計特征的時序數(shù)據(jù)符號化算法［J］.計算機學報，2008，31（10）：1857-1864.

［6］ 閆秋艷，夏士雄.一種無限長時序的分段線性擬合算法［J］.電子學報，2010，38（2）：444-448.

［7］ 周大鐲，李敏強.基于序列重要點的時間序列分割［J］.計算機工程，2008，34（23）：14-16.

［8］ 李重文，鄧騰彬，馬世龍.基于分段極值的時間序列數(shù)據(jù)查詢顯示方法［J］.計算機工程，2014，40（9）：27-30.

［9］ 李愛國，覃 征.在線分割時序數(shù)據(jù)［J］.軟件學報，2004，15（11）：1671-1678.

［10］ 肖 輝，馬海兵，龔 薇.基于時態(tài)邊緣算子的時間序列分段線性表示［J］.計算機工程與應用，2008，44（19）：156-159.

［11］ 詹艷艷，徐榮聰，陳曉云.基于斜率提取邊緣點的時間序列分段線性表示方法［J］.計算機科學，2006，33（11）：139-142.

［12］ 杜 奕，盧德唐，李道倫，等.基于層次聚類的時間序列在線劃分算法［J］.模式識別與人工智能，2007，20（3）：23-27.

［13］ Keogh E，Chakrabarti K，Pazzani M J，et al.Dimensionality Reduction for Fast Similarity Search in Large Tim e Series Databases［J］.Know ledge and Information System s，2008，3（3）：263-286.

［14］ Yi B K，F(xiàn)aloustsos C.Fast Time Sequence Indexing for Arbitrary Lp Norm s［C］//Proceedings of the 26th International Conference on Very Large Databases. Cairo，Egypt：［s.n.］，2000：385-394.

編輯 金胡考

Improved Symbolic Algorithm of Time Series Based on Statistical Feature Vector

LI Xiaocui，ZHANG Xinyu，LUO Qingyun，REN Chang’an

（School of Computer and Information Science，Hunan Institute of Technology，Hengyang 421002，China）

The traditional symbolic algorithm of time series based on statistical feature vector can not retain the timing characteristics well and support multidimensional time series symbolic.Aiming at this problem，this paper proposes an improved symbolic algorithm of time series based on statistical feature vector.The specific methods are as follow s：for single-dimensional time series，using special points’time series segmentation method to segment the time series and making it symbolic；for multi-dimensional time series，using weighted attributes’Principal Component Analysis（PCA）method to transform the multi-dimensional time series into single time series，then making it symbolic.Experimental result show s that the improved algorithm has higher accuracy than traditional algorithm.It can retain the timing characteristics and has more superiority in the aspect of multidimensional time series symbolization.

multidimensional time series；feature vector；weighted attribute；symbolic；Principal Component Analysis（PCA）

李曉翠，張新玉，羅慶云，等.基于統(tǒng)計特征向量的時序符號化改進算法［J］.計算機工程，2015，41（10）：155-159.

英文引用格式：Li Xiaocui，Zhang Xinyu，Luo Qingyun，et al.Improved Symbolic Algorithm of Time Series Based on Statistical Feature Vector［J］.Computer Engineering，2015，41（10）：155-159.

1000-3428（2015）10-0155-05

A

TP18

湖南省教育廳科學研究基金資助項目（14C0304）；國家自然科學基金資助項目（61402164）；湖南省科技計劃基金資助項目（S2013F1023）。

李曉翠（1986-），女，碩士研究生，主研方向：數(shù)據(jù)挖掘；張新玉，碩士研究生；羅慶云，教授；任長安，講師。

2014-10-10

2014-11-14E-mail：xiaocuiworld@163.com