論文閱讀：Streaming pattern discovery in multiple time-series

VLDB 發(fā)表時間：2005 作者：Spiros Papadimitriou
在2005年提出的該方法具有很強(qiáng)的先進(jìn)性奠衔，可以利用該思想對模型進(jìn)行改進(jìn)和驗證。是一篇非常值得學(xué)習(xí)的文章

abstract

In this paper, we introduce SPIRIT (Streaming Pattern discovery in multIple Time-series). Given n numerical data streams, all of whose values we observe at each time tick t, SPIRIT can incrementally find correlations and hidden variables, which summarise the key trends in the entire stream collection. It can do this quickly, with no buffering of stream values and without comparing pairs of streams. Moreover, it is anytime, single pass, and it dynamically detects changes. The discovered trends can also be used to immediately spot potential anomalies, to do efficient forecasting and, more generally, to dramatically simplify further data processing. Our experimental evaluation and case studies show that SPIRIT can incrementally capture correlations and discover trends, efficiently and effectively.

1.這篇文章提出了SPIRIT多時間序列中流模式的發(fā)現(xiàn)导狡，從時間間隔為t的n個數(shù)據(jù)流，找到相關(guān)性和隱藏變量（提取流數(shù)據(jù)中的關(guān)鍵信息）偎痛。
2.該方法具有快速旱捧、不需要緩存、不需要對照流的優(yōu)點(diǎn)看彼，同時可以在任何時候廊佩、動態(tài)的檢測變化囚聚。
3.該方法可以立刻檢測異常點(diǎn)，進(jìn)行高效的預(yù)測标锄，簡化下一步的數(shù)據(jù)處理顽铸。
4.并通過實驗驗證了該方法捕獲相關(guān)性和發(fā)現(xiàn)趨勢越來越有效。

背景：

流數(shù)據(jù)是非常常見的數(shù)據(jù)形式料皇，他們都有兩個共同點(diǎn)谓松，1）數(shù)據(jù)量大刷新頻率高，實時處理緩慢2）用戶或者應(yīng)用不能得到及時的數(shù)據(jù)反饋践剂。流數(shù)據(jù)的處理已經(jīng)有一些基礎(chǔ)模型鬼譬，并在實際中應(yīng)用。流數(shù)據(jù)管理系統(tǒng)對預(yù)測模型和行慣性分析是十分重要的逊脯，流數(shù)據(jù)中很多變量是相關(guān)的优质，用很少的隱藏變量處理表示流數(shù)據(jù)的是十分重要的，該文章提出用少數(shù)變量表示整個流數(shù)據(jù)特征的方法军洼。

該方法主要有兩個作用：

1.發(fā)現(xiàn)流數(shù)據(jù)的模式巩螃，用隱藏變量表示流數(shù)據(jù)的變化規(guī)律。
2.自動確定隱藏變量個數(shù)匕争。

該方法對數(shù)據(jù)的要求：

1.流數(shù)據(jù)
2.數(shù)據(jù)根據(jù)流數(shù)的多少進(jìn)行線性變化（不能是平方或者非線性）
3.It is adaptive, and fully automatic.（個人理解應(yīng)該是動態(tài)變化的）

解決問題：

對多個流數(shù)據(jù)進(jìn)行自動特征提取避乏，用k個變量表征多個流數(shù)據(jù)的規(guī)律「噬＃可以用作異常檢測和預(yù)測拍皮。

實現(xiàn)該方法的主要步驟：

1.計算隱藏變量
1）主成分分析獲得 $w_t$
2）根據(jù) $w_t$ 計算隱藏變量 $y_i$
3）根據(jù)隱藏變量計算重構(gòu)誤差 $e$
4）根據(jù)誤差 $e$ 更新 $w_t$ 和 $y_i$
2.計算隱藏變量的個數(shù) $k$
1）根據(jù)輸入 $x_t$ 的平方和計算 $E_{t+1}$
2）計算 $k$ 個隱藏變量下的 $E_{(k)}$
3）根據(jù) $E_{t+1}$ 、 $E_{k}$ 和兩個閾值調(diào)整 $k$ 的大小
其中 $w_t$ 跑杭、 $y_i$ 铆帽、 $e$ 、 $E_{t+1}$ 艘蹋、 $E_{k}$ 給出了詳細(xì)的計算步驟锄贼。

實驗結(jié)果：

論文用了三種數(shù)據(jù)集驗證該方法的有效性票灰，并對精度進(jìn)行分析女阀。

結(jié)論：

該方法有效地實現(xiàn)了在流數(shù)據(jù)中尋找模式、相關(guān)性和隱藏變量屑迂，并具有以下特性：

發(fā)現(xiàn)多個流之間的潛在相關(guān)性浸策，獲得隱藏變量，并通過一些隱藏變量提供流集合的非常緊湊的表示惹盼。
自動估計要隱藏變量的數(shù)量k庸汗。
無論是在數(shù)據(jù)庫大小（即時間刻度t的數(shù)量）還是在流的數(shù)量n上手报，它的擴(kuò)展都非常好蚯舱。因此改化，它適用于大量的傳感器/數(shù)據(jù)源。
計算要求低：只需O(nk)浮點(diǎn)運(yùn)算枉昏，無矩陣變換和奇異值分解（SVD）
它可以很自然地與任何預(yù)測方法相結(jié)合陈肛，因此很容易進(jìn)行預(yù)測，并處理缺失值兄裂。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者