劉 利 何先平 袁文亮

（1.池州學(xué)院 數(shù)學(xué)計(jì)算機(jī)系，安徽 池州 247000；2.長(zhǎng)江大學(xué) 信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023）

檢測(cè)非平穩(wěn)時(shí)間序列中離群點(diǎn)和變化點(diǎn)的統(tǒng)一框架

劉 利1何先平2袁文亮1

（1.池州學(xué)院 數(shù)學(xué)計(jì)算機(jī)系，安徽 池州 247000；2.長(zhǎng)江大學(xué) 信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023）

文章為在非平穩(wěn)時(shí)間序列的在線學(xué)習(xí)理論的基礎(chǔ)上檢測(cè)離群點(diǎn)和變化點(diǎn)提出了一個(gè)統(tǒng)一框架.在這個(gè)框架中數(shù)據(jù)源的一個(gè)概率模型用一種在線折扣學(xué)習(xí)算法被逐步學(xué)習(xí)，該算法能通過(guò)逐漸忘記過(guò)去數(shù)據(jù)的效果自適應(yīng)地跟蹤變化的數(shù)據(jù)源.然后任一給定數(shù)據(jù)的分?jǐn)?shù)被計(jì)算出來(lái)測(cè)量它與學(xué)習(xí)模型的偏差，高分表明更有可能是離群點(diǎn).進(jìn)一步地?cái)?shù)據(jù)流中的變化點(diǎn)通過(guò)用這一學(xué)習(xí)模型應(yīng)用這種得分方法到一個(gè)移動(dòng)平均損失預(yù)測(cè)時(shí)間序列中來(lái)檢測(cè).特別地我們?yōu)閬?lái)自時(shí)間序列數(shù)據(jù)的自回歸模型的在線折扣學(xué)習(xí)發(fā)明了一種有效算法，并通過(guò)仿真和在股票市場(chǎng)數(shù)據(jù)分析的實(shí)際應(yīng)用驗(yàn)證框架的有效性.

離群點(diǎn)；變化點(diǎn)；非平穩(wěn)時(shí)間序列；在線學(xué)習(xí)

0 引言

現(xiàn)有非平穩(wěn)數(shù)據(jù)源的離群點(diǎn)檢測(cè)算法中，適應(yīng)性離群點(diǎn)檢測(cè)算法已經(jīng)被提出了.可是，沒(méi)有得出任何明確的統(tǒng)計(jì)模型以便于時(shí)間序列能被處理.

為檢測(cè)離群點(diǎn)和變化點(diǎn)我們用AR模型來(lái)代表時(shí)間序列數(shù)據(jù)的統(tǒng)計(jì)行為.AR模型是一種最典型的時(shí)間序列統(tǒng)計(jì)模型，該模型在統(tǒng)計(jì)中已經(jīng)被廣泛采用.大多數(shù)現(xiàn)有的估計(jì)AR模型的參數(shù)的算法都是在數(shù)據(jù)源是平穩(wěn)的假定下設(shè)計(jì)的，一種處理非平穩(wěn)數(shù)據(jù)的方法是介紹一種系數(shù)是隨時(shí)間變化的AR模型.相反地，我們通過(guò)模型化AR模型評(píng)估算法來(lái)處理非平穩(wěn)數(shù)據(jù)，逐步更新它的參數(shù)估計(jì)值以便過(guò)去例子的效果逐漸被打折.然后我們給每個(gè)數(shù)據(jù)／時(shí)間點(diǎn)一個(gè)分?jǐn)?shù)，高分表明更有可能是離群點(diǎn).這使得程序更有效率，并可適用于不能用簡(jiǎn)單的分段模型表示的數(shù)據(jù)源.

在文［1］中解決變化點(diǎn)檢測(cè)問(wèn)題時(shí)沒(méi)有假設(shè)數(shù)據(jù)是局部平穩(wěn)的.反而，在文［1］中用分段函數(shù)來(lái)擬合依賴于時(shí)間的數(shù)據(jù)，變化點(diǎn)被定義為連續(xù)函數(shù)的分界點(diǎn).在該方法中，可通過(guò)找模型擬合誤差最小的點(diǎn)作為變化點(diǎn).可是，找到這樣的點(diǎn)計(jì)算復(fù)雜度太大，因?yàn)閿?shù)據(jù)每輸入一次，有多少分界點(diǎn)，就得擬合多少次局部模型.進(jìn)一步當(dāng)數(shù)據(jù)源不能很好地用一個(gè)簡(jiǎn)單的分段函數(shù)表示時(shí)它不能保證有效.

盡管在大多數(shù)先前的工作中離群點(diǎn)檢測(cè)和變化點(diǎn)檢測(cè)沒(méi)有明確地相關(guān)，本文給出了它們間一個(gè)清楚的聯(lián)系，并提出了從非平穩(wěn)時(shí)間序列在線打折學(xué)習(xí)的角度同時(shí)處理他們的一個(gè)統(tǒng)一框架.在我們的框架中，我們能在同一個(gè)學(xué)習(xí)算法的基礎(chǔ)上同時(shí)檢測(cè)離群點(diǎn)和變化點(diǎn).本文提出的變化點(diǎn)探測(cè)算法計(jì)算效率高，達(dá)到了很高的探測(cè)準(zhǔn)確性.

1 數(shù)據(jù)模型和在線學(xué)習(xí)算法

我們記一個(gè)數(shù)據(jù)序列為｛x t：t＝1，2，…｝，這里t是時(shí)間變量.設(shè)該序列的概率密度函數(shù)為｛p t：t＝1，2，…｝，它描述了底層機(jī)制的生成數(shù)據(jù).這一序列應(yīng)該從｛x t｝中被逐步學(xué)習(xí)，一旦一個(gè)數(shù)據(jù)x t被輸入進(jìn)來(lái)，我們也建造一個(gè)預(yù)測(cè)值｛＾x t：t＝1，2，…｝，這里＾x t應(yīng)該在｛p t｝和｛x t｝的基礎(chǔ)上計(jì)算.下面我們描述構(gòu)造｛p t｝和｛x t｝的模型和學(xué)習(xí)算法.

1.1 獨(dú)立模型

我們首先考慮數(shù)據(jù)每次是獨(dú)立抽取的情況.假定多維域X?Rn是連續(xù)的，我們用x代表X上的一個(gè)隨機(jī)變量，用下面形式的Gaussian混合模型代表非平穩(wěn)獨(dú)立數(shù)據(jù)生成的一個(gè)概率密度函數(shù)：

SDEM算法由推廣的Neal和Hinton的逐步EM算法［2］介紹，以便過(guò)去例子的效果能隨著時(shí)間流逝逐漸打折.SDEM算法用依賴于折扣參數(shù)r的帶權(quán)的平均值更新參數(shù)估計(jì)值，這里r值越小表明SDEM算法對(duì)過(guò)去例子的影響越大.

在SDEM算法中，參數(shù)α為了提高c i估計(jì)值的穩(wěn)定性被提出來(lái)，ci被設(shè)定在1.0～2.0.

1.2 時(shí)間序列模型

注意：上述學(xué)習(xí)AR模型的算法中假定數(shù)據(jù)源是平穩(wěn)的，一旦我們看到完整的數(shù)據(jù)就要估計(jì)參數(shù).

我們介紹SDAR算法在以下兩方面來(lái)修改文［2］中的算法：

1）在線評(píng)估.即：一旦觀測(cè)到數(shù)據(jù)就要更新參數(shù).

2）折扣屬性.介紹一種折扣參數(shù)r使統(tǒng)計(jì)指數(shù)隨時(shí)間帶有乘法因子（1－r）衰變.這使我們能夠處理非平穩(wěn)數(shù)據(jù).

SDAR算法描述如下：

SDAR算法（0＜r＜1）

Step1 初始化

對(duì)每一時(shí)間t，SDAR算法更新依賴于折扣參數(shù)r（＞0）的帶權(quán)平均值的參數(shù)估計(jì)值，r值越小表明SDEM算法對(duì)過(guò)去例子的影響越大.

我們記p t為SDAR算法在時(shí)間t更新的參數(shù)指定的方程（1）的概率密度函數(shù).然后可得到一個(gè)概率密度序列：｛p t：t＝1，2，…｝.

2 得分

2.1 離群點(diǎn)檢測(cè)

對(duì)x t的每一個(gè)輸入值，我們由下面的公式計(jì)算得分：

方程（3）左邊表示與概率密度函數(shù)p t－1相關(guān)的x t的預(yù)測(cè)［3］損失，我們稱作對(duì)數(shù)損失.從信息理論的角度，對(duì)數(shù)損失可以被看作代碼長(zhǎng)度在數(shù)據(jù)是根據(jù)概率密度p t－1生成的假定下把x t編碼成二進(jìn)制序列的代碼長(zhǎng)度.

我們也可以定義分?jǐn)?shù)為x t前后間的統(tǒng)計(jì)偏離.

這里p（＊），q（＊）是概率密度函數(shù).

直覺(jué)地，分?jǐn)?shù)測(cè)量了概率密度函數(shù)在從x t中學(xué)習(xí)后從p t－1移動(dòng)了多少.

注意：x t分?jǐn)?shù)越高表明x t更有可能是離群點(diǎn).

2.2 變化點(diǎn)檢測(cè)

設(shè)T是一個(gè)正的常量，｛x t｝是一數(shù)據(jù)序列，我們就像T－平均分?jǐn)?shù)｛Score（x i）：i＝t－T＋1，…，t｝定義y t為：

這里Score（x i）根據(jù)（3）或（4）計(jì)算，然后我們獲得一個(gè)時(shí)間序列｛y t：t＝1，2，…｝.

為了表示時(shí)間序列｛y t｝我們用AR模型，再用SDAR算法來(lái)構(gòu)建由AR模型決定的概率密度函數(shù)的一個(gè)序列，記為｛qt：t＝1，2，…｝.然后給出T′，如方程（3）（對(duì)數(shù)損失）定義t時(shí)刻的T′平均分如下：

或者我們可以就像方程（8）那樣用下面的分?jǐn)?shù)：

這里d是測(cè)量前面部分兩個(gè)概率密度函數(shù)間區(qū)別的函數(shù).

因此我們能夠在同樣范例中同一學(xué)習(xí)算法的基礎(chǔ)上處理離群點(diǎn)檢測(cè)和變化點(diǎn)檢測(cè).這給出了這兩個(gè)問(wèn)題間很強(qiáng)的聯(lián)系.

注意：Score（t）越高表明時(shí)間點(diǎn)t更有可能是變化點(diǎn).

在方程（9）中，在T是小的情況下，離群點(diǎn)和變化點(diǎn)能在它們一出現(xiàn)就立即被檢測(cè)，可是它們很難相互區(qū)分.在T是大的情況下，導(dǎo)致了探測(cè)變化點(diǎn)的時(shí)間耽擱，可是，離群點(diǎn)被過(guò)濾，只有變化點(diǎn)被準(zhǔn)確檢測(cè).

3 實(shí)驗(yàn)結(jié)果

3.1 仿真

我們用兩種數(shù)據(jù)集由數(shù)字模擬評(píng)估我們的方法.第一類數(shù)據(jù)集是一個(gè)數(shù)據(jù)序列使得變化點(diǎn)間每一個(gè)數(shù)據(jù)都根據(jù)下面的AR模型抽取：

這里εt是具有均值0和方差1的高斯隨機(jī)變量.該數(shù)據(jù)集由10 000個(gè)記錄組成.變化點(diǎn)在時(shí)間x×10 000（x＝1，2，…，9）.記x－th和（x－1）－th變化點(diǎn)的變化量為Δ（x），稱為x處變化大小.在這種情況下設(shè)Δ（x）＝x.檢測(cè)大些的x的變化點(diǎn)要容易些.

我們測(cè)試了數(shù)據(jù)建模和得分的兩種組合.在第一種組合（稱為SDEM1）中，我們?yōu)閿?shù)據(jù)建模用獨(dú)立模型（具有兩個(gè)組成的有限混合），為得分用k＝2的AR模型.在第二種組合（稱為SDAR1）中，我們?yōu)閿?shù)據(jù)建模用k＝2的AR模型，為得分用k＝2的AR模型.這里我們用對(duì)數(shù)損失作為分?jǐn)?shù)，SDAR和SDEM算法中的參數(shù)是r＝0.005.就像在方程（5）和（6）中一樣我們?yōu)橛?jì)算得分令T＝5，T′＝5.我們可以看到SDAR1檢測(cè)變化點(diǎn)與SDEM1一樣好，但SDAR1給出的分?jǐn)?shù)比SDEM1更準(zhǔn)確地反映了變化程度.

第二類數(shù)據(jù)集是一數(shù)據(jù)序列使得變化點(diǎn)間的每一個(gè)數(shù)據(jù)都是根據(jù)AR模型抽取.方差和均值都隨著時(shí)間改變.變化點(diǎn)在時(shí)刻x×10 000（x＝1，2，…，9），標(biāo)準(zhǔn)偏差定義為0.1／（0.01＋time／10 000）我們記xth.

變化點(diǎn)的變化大小與標(biāo)準(zhǔn)偏差的比為R（x），稱為改變信噪比.在這個(gè)數(shù)據(jù)集中，我們?cè)O(shè)R（x）≈x（x＝1，2，…，9）我們觀察到SDAR1能夠準(zhǔn)確地探測(cè)變化點(diǎn)盡管方差隨時(shí)間改變.

接下來(lái)，我們檢查了錯(cuò)誤警率和SDAR1的查全率，錯(cuò)誤警率定義為非變化點(diǎn)被定義為變化點(diǎn)的百分比，查全率定義為準(zhǔn)確檢測(cè)到的變化點(diǎn)與應(yīng)該被檢測(cè)到的變化點(diǎn)的總數(shù)比.我們準(zhǔn)備了具有變化的信噪比的三個(gè)數(shù)據(jù)集.每個(gè)數(shù)據(jù)集由AR模型（8）產(chǎn)生100 000個(gè)記錄.對(duì)每個(gè)數(shù)據(jù)集，變化點(diǎn)在時(shí)刻x×1 000（x＝1，2，…，9）發(fā)生.三個(gè)數(shù)據(jù)集對(duì)每個(gè)變化點(diǎn)x的信噪比分別為R（x）＝20，10，5.如果一個(gè)檢測(cè)到的變化點(diǎn)位于正確的變化點(diǎn)后50個(gè)記錄內(nèi)就認(rèn)為檢測(cè)是正確的.

3.2 真實(shí)數(shù)據(jù)實(shí)驗(yàn)

我們用TOPIX（股票價(jià)格指數(shù)）數(shù)據(jù)來(lái)看我們的變化點(diǎn)探測(cè)方法對(duì)實(shí)際問(wèn)題效果如何.

我們用k＝4的AR模型來(lái)建模，k＝4的AR模型來(lái)計(jì)算得分.設(shè)x t是最原始的時(shí)間序列數(shù)據(jù)，y t＝x t－x t－1，我們處理二維數(shù)據(jù)（x t，y t）.我們標(biāo)示這種策略為SDAR2.這里我們用對(duì)數(shù)損失作為分?jǐn)?shù)，SDAR算法中用的打折參數(shù)為r＝0.005，如（5）和（6）中那樣計(jì)算得分令T＝5，T′＝5.高分的時(shí)間點(diǎn)表示指數(shù)發(fā)生了重要變化的點(diǎn).我們觀察到SDAR能夠探測(cè)指數(shù)的真正的重要變化.所有重要點(diǎn)都被準(zhǔn)確探測(cè)到.這表明我們的方法能夠發(fā)現(xiàn)指數(shù)中有意義的變化點(diǎn).

4 結(jié)束語(yǔ)

本文提出了檢測(cè)來(lái)自非平穩(wěn)時(shí)間序列的離群點(diǎn)和變化點(diǎn)的一個(gè)框架.該框架由兩部分組成：數(shù)據(jù)建模和計(jì)算得分.在數(shù)據(jù)建模部分，我們逐步獲得一個(gè)數(shù)據(jù)序列的概率密度函數(shù).具體來(lái)說(shuō)，在文中我們采用了AR模型，并為AR模型的在線折扣學(xué)習(xí)引入了SDAR算法.SDAR算法的特點(diǎn)在于它的打折屬性：過(guò)去數(shù)據(jù)的效果逐漸被打折.這使得我們能夠處理非平穩(wěn)數(shù)據(jù).在計(jì)算得分部分我們?cè)趯W(xué)習(xí)模型的基礎(chǔ)上給每個(gè)數(shù)據(jù)或每個(gè)時(shí)間點(diǎn)一個(gè)分?jǐn)?shù).具體來(lái)說(shuō)減少了變化點(diǎn)檢測(cè)到來(lái)自移動(dòng)平均分?jǐn)?shù)的離群點(diǎn)檢測(cè)的問(wèn)題.因此我們能夠用在同一個(gè)范式的同一個(gè)學(xué)習(xí)算法來(lái)處理這兩個(gè)問(wèn)題.這給出了離群點(diǎn)檢測(cè)和變化點(diǎn)檢測(cè)的一個(gè)統(tǒng)一觀點(diǎn).

［1］Hamiltion J D.Time senes analysis［M］.New Jersey：Princeton University Press，2000：26-42

［2］Hawkins D.Identification of outliers［M］.London：Chapman and Hall，1980

［3］Trevor Hastie，Robert Tibshirani，Jerome Friedman.統(tǒng)計(jì)學(xué)習(xí)基礎(chǔ)——數(shù)據(jù)挖掘、推理與預(yù)測(cè)［M］.范 明，譯.北京：電子工業(yè)出版社，2004

［4］黃 超.基于特征分析的金融時(shí)間序列挖掘若干關(guān)鍵問(wèn)題研究［D］.上海：復(fù)旦大學(xué)，2005

［5］Enke D，Thawornwong S.The use of data mining and neural networks for forecasting stock market returns［J］.Expert systems with applications，2005，18（29）：201-205

［6］David West.Neural network credit scoring models［J］.Computers Operation Research，2000，27（11-12）：1 131-1 152

A Unifying Framework for Detecting Outliers and Change Points from Non-Stationary Time Series Data

Liu li1He Xianping2Yuan Wenliang1
（1.Department of Mathematics and Computer，Chizhou College，Chizhou 247000；2.Information and Mathematical college of Yangtze University，Jingzhou 434023，China）

We present a unifying framework for dealing with outlier and change point on the basis of the theory of on-line learning of non-stationary time series.In this framework a probabilistic model of the data source is incrementally learned using an on-line discounting learning algorithm，which can track the changing data source adaptively by forgetting the effect of past data gradually.Then the score for any given data is calculated to measure its deviation from the learned model，with a higher score indicating a high possibility of being an outlier.Further change points in a data stream are detected by applying this scoring method into a time series of moving averaged losses for prediction using the learned model.Specifically we develop an efficient algorithms for on-line discounting learning of auto-regression models from time series data，and demonstrate the validity of our framework through simulation and experimental applications to stock market data analysis.

outlier；change point；non-stationary time series；on-line learning

王映苗】

1672-2027（2011）03-0005-04

O212.1

A

2011-03-15

國(guó)家自然科學(xué)基金項(xiàng)目（60873021／F0201）.

劉 利（1981-），女，湖北天門人，碩士，池州學(xué)院數(shù)學(xué)計(jì)算機(jī)系講師，主要從事概率與數(shù)理統(tǒng)計(jì)的研究.