時間序列數(shù)據(jù)預(yù)處理的維度簡約文獻(xiàn)研究

錢國軍

【摘 要】時間序列數(shù)據(jù)是現(xiàn)實數(shù)據(jù)庫中最重要的數(shù)據(jù)類型之一，由于其具有數(shù)據(jù)量大、維度高和連續(xù)更新的特點，直接對時間序列數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘非常困難，必須在數(shù)據(jù)預(yù)處理階段對原時間序列進(jìn)行維度簡約，提高數(shù)據(jù)挖掘可操作性。文章對現(xiàn)有時間序列維度簡約技術(shù)進(jìn)行了匯總比較，為研究者進(jìn)一步探索和挖掘時間序列數(shù)據(jù)提供參考。

【關(guān)鍵詞】時間序列 數(shù)據(jù)挖掘 維度簡約

【中圖分類號】TP311.13【文獻(xiàn)標(biāo)識碼】A【文章編號】1672-5158（2013）02-0067-01

現(xiàn)實中大量數(shù)據(jù)都是按時間順序保存在數(shù)據(jù)庫中，如金融市場的股票數(shù)據(jù)，數(shù)據(jù)量之大致使傳統(tǒng)的時間序列分析效果甚微，大量包含有用信息的歷史數(shù)據(jù)只能束之高閣。近幾十年來，數(shù)據(jù)挖掘技術(shù)迅速發(fā)展，數(shù)據(jù)分析逐漸從單純的統(tǒng)計分析向和計算機技術(shù)緊密聯(lián)系的數(shù)據(jù)挖掘方向發(fā)展。數(shù)據(jù)挖掘通過各種算法讓計算機在人的控制下探索海量數(shù)據(jù)，發(fā)現(xiàn)其中人所感興趣的信息。時間序列數(shù)據(jù)是數(shù)據(jù)挖掘的重要方面，直接對原始進(jìn)行數(shù)據(jù)處理是無法發(fā)現(xiàn)有用信息，一種可行的辦法就是對原始數(shù)據(jù)進(jìn)行特征提取，這一方面降低了數(shù)據(jù)維度，另一方面也消除了噪音。本文將著重介紹各種時間序列數(shù)據(jù)挖掘特征提取技術(shù)。

時間序列維度簡約中最簡單的方法可能是采樣。然而，如果采樣率很低，采樣方法的缺點是扭曲了被采樣時間序列的形狀。一個提高的方法是使用每個分割的平均值帶便相應(yīng)的數(shù)據(jù)點集合。這種方法也稱為分段聚集近似。Keogh提出一個擴展版本自適應(yīng)分段常數(shù)近似，每個分割的長度不是固定的，而是是適用于序列的現(xiàn)狀。Lee提出使用分割的總變異（SSV）表示時間序列的每個分割。

使用直線近似時間序列是一種重要方法，主要分為兩類：線性插值和線性回歸。第一類是線性插值。一個普遍的方法是使用分段線性表示PLR。PLR是一種自底向上的算法，此方法往往連接連續(xù)分割的末端，用銜接的直線來分段近似。反復(fù)合并代價最低的分割對，直到達(dá)到需要的分割數(shù)量。Ge把PLR擴展到分層結(jié)構(gòu)。Keogh和Pazzani通過考慮分割的權(quán)重和來自使用者的信息反饋完善了PLR。第二種方法是線性回歸，使用最優(yōu)擬合直線代表子序列。

此外，保留顯著點降低維度一種有效的方法。這些點稱為感知重要點PIP。Chung首先引入了PIP識別過程，并適用于金融應(yīng)用的技術(shù)模式的模式匹配。時間序列P有n個數(shù)據(jù)點， P中所有數(shù)據(jù)點在整個PIP識別過程中按其重要性排序，再按順序識別，這種PIP定位過程直到達(dá)到要求的PIP數(shù)量。

這一思想和30年前Douglas and Peucker減少要求的數(shù)據(jù)點來代表直線的技術(shù)相似，他使用了路標(biāo)模型識別時間序列中的重要點。Man和Wang提出晶格結(jié)構(gòu)來表示時間序列中的識別的頂點和谷點。Pratt、Fink和Finketal定義了時間序列中如極大極小的極值，通過選擇僅僅每個重要的極值點丟棄其他點壓縮時間序列。這一算法也能處理新來的數(shù)據(jù)點，他根據(jù)時間序列分割的局部信息識別重要點，不需要儲存原先的序列。目前，金融數(shù)據(jù)分析提出了關(guān)鍵點模型和基于關(guān)鍵點序列的高度表示方法。關(guān)鍵點表示時間序列適用于于奇異值識別。

另一類普遍的時間序列表示方法是把數(shù)值時間序列轉(zhuǎn)化為符號形式。首先把時間序列離散化為分割片段，然后把每個分割轉(zhuǎn)換為一個符號。Lin提出一種稱為符號聚集近似的方法SAX，把PAA的結(jié)果轉(zhuǎn)換為符號串。Jonsson 和Badal使用“形狀描述字符SDA”。Qu采用梯度字母如向上、平坦和向下作為符號。Huang 和yu提出使用相鄰數(shù)據(jù)點的變化量來把時間序列轉(zhuǎn)換為符號串。

Megalooikonomou提出使用來自關(guān)鍵序列的碼本的碼字來表示每個劃分。Megalooikononou考慮多路解決擴展了這一方法。Morchen和Ultsch提出了基于質(zhì)量得分和持續(xù)狀態(tài)的無監(jiān)督離散處理。這一算法不是像很多其他方法忽略數(shù)據(jù)的時態(tài)順序，而是包括了時態(tài)信息。

此外，子序列聚類是一種產(chǎn)生符號的普遍方法。Li提出是基于時間序列的符號形式多抽象層挖掘方法MALM。

目前為止介紹的大部分方法是在時間域內(nèi)直接表示時間序列。在另一個域內(nèi)表示時間序列是另一大類方法。一個流行的時間序列轉(zhuǎn)換技術(shù)是傅里葉轉(zhuǎn)換DFT，它首先由Agrawal在這一領(lǐng)域使用。Rafiei 和Mendelzon使用DFT開發(fā)了基于相似性查詢。Janacek提出使用似然比統(tǒng)計量檢驗序列間不同的假設(shè)，而不是使用轉(zhuǎn)換域的歐幾里得距離。目前研究使用小波轉(zhuǎn)換來表示時間序列。離散的小波轉(zhuǎn)換DWT已認(rèn)為是替代DFT的有效方法，哈爾變換最為流行。哈爾變換是一系列對時間序列的平均和差分操作。Shahabi提出多層次小波轉(zhuǎn)換表示。Popivanov 和Miller表明大部分小波轉(zhuǎn)換的可用于時間序列表示。Dasha比較了不同小波特征向量。Wu和Morchen對DFT和DWT之間優(yōu)缺點的進(jìn)行了比較。Kawagoe和Ueda提出了傅里葉和小波轉(zhuǎn)換的聯(lián)合使用。Keogh 和Vlachos提出的整合了兩種和兩種以上的表示方法整體索引。

主成分分析PCA是一種用于多元統(tǒng)計處理監(jiān)督方法的流行多元技術(shù)，并應(yīng)用于金融時間序列。在大部分相關(guān)研究中，PCA用于消除不顯著的成分或傳感器，減少數(shù)據(jù)表示只表示最為顯著的數(shù)據(jù)點，把數(shù)據(jù)點畫在兩維空間。PCA定義了線性超平面，可以認(rèn)為是PLR的多元擴展。PCA把多元數(shù)據(jù)映射到地位空間，在相關(guān)高位數(shù)據(jù)的分析和可視化中很有用。奇異值分解SVD是另一種基于轉(zhuǎn)換的方法。

其他時間序列表示方法包括使用隱藏的馬克魯夫模型模擬時間序列. Deligiannakis提出了多元數(shù)據(jù)流的壓縮技術(shù)，他是基于信號的，這信號給相關(guān)數(shù)據(jù)值的分段線性相關(guān)性編碼。

以上介紹的許多表示方法和不同的索引方法想結(jié)合的。對于現(xiàn)存的多維索引結(jié)構(gòu)的表示適用于普遍的表示方法方法。Agrawal提出了F-索引，他采用R*樹索引第一少數(shù)DFT系數(shù)。Faloutsos進(jìn)一步提出了ST-索引，這擴張了先前子序列處理的研究。Agrawal采用了R*和R+樹作為索引結(jié)構(gòu)。Vlachos提出多矩陣樹，這是對歐幾里得和間歇空間的混合索引結(jié)構(gòu)。最小邊界矩形MBR也是一種普遍的時間序列索引技術(shù)。Rafiei采用了MBR，發(fā)展了基于傅里葉轉(zhuǎn)黃的MT-索引，Kahveci 和Singh 提出了基于小波轉(zhuǎn)換的多路解決索引。Chen提出對PLR表示的索引機制。另一方面，Kim提出針對控制時間序列模式數(shù)據(jù)庫的TIP-索引。EMDF Kim通過改善擴展的多維動態(tài)索引發(fā)展TIP-索引。iSAX是基于SAX的大量時間序列索引。Li提出多分辨率索引結(jié)構(gòu)，適用于不同的表示。

總之，對于給定的索引結(jié)構(gòu)，索引的有效性僅取決于維度簡約空間的近似準(zhǔn)確性。然而在選擇維度簡約技術(shù)時，我們不能簡單選擇任意一種壓縮算法。需要能產(chǎn)生能索引的表示的技術(shù)。例如，很多時間序列可以通過delta編碼有效的壓縮，但之中表示不能使他自己能索引。相反，SVD、DFT、DWT和PAA傅里葉系數(shù)、小波系數(shù)或者聚集劃分映射到索引樹的一維中，能是容易得到索引。