錢(qián)國(guó)軍

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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