異常點檢測算法分析與選擇

1、異常點檢測算法分析與選擇分類：數(shù)據(jù)倉庫及數(shù)據(jù)挖掘20090911 17:27 3026人閱讀評論(0)收藏舉報算法數(shù)據(jù)挖掘產(chǎn)品數(shù)據(jù)庫工作數(shù)據(jù)分析目錄+11.1常見異常點檢測算法在數(shù)據(jù)庫中包含著少數(shù)的數(shù)據(jù)對象，它們與數(shù)據(jù)的-一般行為或特征不一致， 這些數(shù)據(jù)對象叫做異常點(outlier)，也叫做孤立點。異常點的檢測和分析是-種 十分重要的數(shù)據(jù)挖掘類型，被稱之為異常點挖掘。對于異常數(shù)據(jù)的挖掘主要是使用偏差檢測，在數(shù)學(xué)意義上，偏差是指分類中 的反常實例、不滿足規(guī)則的特例，或者觀測結(jié)果與模型預(yù)測值不-致并隨口寸間的 變化的值等等。偏差檢測的基本目標(biāo)是尋找觀測結(jié)果與參照值之間有意義的差別, 主要的偏差技

2、術(shù)有聚類、序列異常、最近鄰居法、多維數(shù)據(jù)分析等。除了識別異 常數(shù)據(jù)外，異常數(shù)據(jù)挖掘還致力于尋找異常數(shù)據(jù)間隱含模型，用于猶能化的分析 預(yù)測。對于異常數(shù)據(jù)分析方法的研究是論文的垂要內(nèi)容之一，通過研究異常數(shù)據(jù)， 找到適合岀口企業(yè)產(chǎn)品質(zhì)量深入分析和有效監(jiān)管的方法和策略。1.1.1基于統(tǒng)計的異常點檢測算法從20世紀(jì)80年代起，界常檢測問題就在統(tǒng)計學(xué)領(lǐng)域里得到廣泛研究，通 常用戶用某個統(tǒng)計分布對數(shù)據(jù)點進行建模，再以假定的模型，根據(jù)點的分布來確 定是否界常。許許多多針對不同分布的界常測試(discordancy test)方法發(fā)展起來, 它們分別適用于不同的情形：數(shù)據(jù)分布狀況；數(shù)據(jù)分布參數(shù)是否己知；界 常數(shù)

3、據(jù)數(shù)量；界常數(shù)據(jù)類型(高于或低于一般抽樣值)。這方面比較有代表性 的有1967年mikey , dunn & clark提出的基于“均數(shù)漂移”模型的單點診斷 量，1970 年 gentleman &wilk 提岀的群組診斷量，1972 年 tietjen &moore 提 出的單樣本k個離群點的統(tǒng)計量ek，1985年marasinghe提岀的改進的e k統(tǒng) 計量f k,1989年rosner提岀的單樣本多個離群檢測算法esd(generalizedextreme studentized deviate)方法，1991 年 paul & fung 改進了 esd

4、方法參 數(shù)k選擇的主觀性，提出了回歸分析的gesr (generalized extreme studentized deviateresi2dual)方法。近年來，多樣本的離群檢測方法也得到了一定的發(fā)展， 總的思路是先盡量得到一個不含離群點的“干凈集”，然后在此基礎(chǔ)上對剩余的 其他數(shù)據(jù)點進行逐步離群檢測29】。目前利用統(tǒng)計學(xué)研究異常點數(shù)據(jù)有了一些新的方法，如通過分析統(tǒng)計數(shù)據(jù)的 散度情況，即數(shù)據(jù)變異指標(biāo)，來對數(shù)據(jù)的總體特征有更進一步的了解，對數(shù)據(jù)的 分布情況有所了解，進而通過數(shù)據(jù)變異指標(biāo)來發(fā)現(xiàn)數(shù)據(jù)中的異常點數(shù)據(jù)。常用的 數(shù)據(jù)變異指標(biāo)有極差、四分位數(shù)間距、均差、標(biāo)準(zhǔn)差、變異系數(shù)等等，變異指標(biāo) 的

5、值大表示變異大、散布廣；值小表示離差小，較密集?；诮y(tǒng)計的方法檢測出來的離群點很可能被不同的分布模型檢測出來，可以 說產(chǎn)生這些離群點的機制可能不唯一，解釋離群點的意義時經(jīng)常發(fā)生多義性，這 是基于統(tǒng)計方法的一個缺陷。其次，基于統(tǒng)計的方法在很大程度上依賴于待挖掘 的數(shù)據(jù)集是否滿足某種概率分布模型，模型的參數(shù)、離群點的數(shù)冃等對基于統(tǒng)計 的方法都有非常重要的意義，而確定這些參數(shù)通常都比較困難。為克服這一問題, 一些人提出對數(shù)據(jù)集進行分布擬合，但分布擬合存在兩個問題：給出的分布可 能不適合任一標(biāo)準(zhǔn)分布。即使存在一個標(biāo)準(zhǔn)分布，分布擬合的過程耗時太長。 此外，基于統(tǒng)計的離群檢測算法大多只適合于挖掘單變量的數(shù)

6、值型數(shù)據(jù)，冃前幾 乎沒有多元的不一致檢驗，對于大多數(shù)的應(yīng)用來說，例如圖像和地理數(shù)據(jù)，數(shù)據(jù) 集的維數(shù)卻可能是高維的。實際生活中，以上缺陷都大大限制了基于統(tǒng)計的方法 的應(yīng)用，使得它主要局限于科研計算，算法的可移植性較差。1.1.2基于距離的異常點檢測算法用什么標(biāo)準(zhǔn)判定一個數(shù)據(jù)對象是孤立點呢？即便是對給定的距離量度函數(shù), 對孤立點也有不同的定義，以下是使用較多的兒個：基于距離的離群點最早是由knorr和ng提出的，他們把記錄看作高維 空間中的點，離群點被定義為數(shù)據(jù)集中與大多數(shù)點之間的距離都大于某 個閾值的點，通常被描述為db (pct, d min),數(shù)據(jù)集t中一個記錄0稱 為離群點，當(dāng)且僅當(dāng)數(shù)據(jù)集

7、t中至少有pct部分的數(shù)據(jù)與0的距離大 于dmin o換一種角度考慮,記m=n x(l-pct),離群檢測即判斷與 點0距離小于泅的點是否多于m。若是，則0不是離群點，否則 0是離群點141,361 o孤立點是數(shù)據(jù)集中到第k個最近鄰居的距離最大的個對象37'。孤立點是數(shù)據(jù)集中與其k個最近鄰居的平均距離最大的n個對象381o 基于距離的離群點定義包含并拓展了基于統(tǒng)計的思想，即使數(shù)據(jù)集不滿足任 何特定分布模型，它仍能有效地發(fā)現(xiàn)離群點，特別是當(dāng)空間維數(shù)比較高時，算法 的效率比基于密度的方法要高得多】。算法具體實現(xiàn)時，首先給出記錄間距離 的度量，常用的是絕對距離(曼哈頓距離)、歐氏距離和馬氏距

8、離盹。在給出 了距離的度量并對數(shù)據(jù)進行一定的預(yù)處理以后，任意給定參數(shù)“c/和就可以 根據(jù)離群的定義來檢測離群。rastogi和ramaswamy在上面基于距離的離群點 定義的基礎(chǔ)上，提出改進的基于距離的k最近鄰伙nn)離群檢測算 法37 4142。基于距離的離群檢測方法中，算法需要事先確定參數(shù)/x7和心,對于不同 的數(shù)據(jù)集這往往是一件比較困難的事情，特別是泅，不同聚類密度的數(shù)據(jù) 集血加會有很大的差異，而這一般沒有規(guī)律可循，因此，對于給定的不同幾血， 異常檢測結(jié)果通常具有很大的不穩(wěn)定性。另一方而，基于距離的方法理論上 能處理任意維任意類型的數(shù)據(jù)，當(dāng)屬性數(shù)據(jù)為區(qū)間標(biāo)度等非數(shù)值屈性時，記錄之 間的距

9、離不能直接確定，通常需要把屈性轉(zhuǎn)換為數(shù)值型37k441,再按定義計算記 錄之間的距離。當(dāng)空間的維數(shù)大于三維時，由于空間的稀疏性，距離不再具有常 規(guī)意義，因此很難為異常給出合理的解釋。針對這個問題，一些人通過將高維空 間映射轉(zhuǎn)換到子空間的辦法來解決數(shù)據(jù)稀疏的問題，此方法在聚類算法中用得比 較多45146, agarwal r.45 等人曾試著用這種投影變換的方法來挖掘離群?？?的來說，基于距離的離群檢測方法具有比較直觀的意義，算法比較容易理解，因 此在實際中應(yīng)用得比較多。目前比較成熟的基于距離的異常點檢測的算法有：1 .基于索引的算法(index-based):給定一個數(shù)據(jù)集合，基于索引的算法采

10、 用多維索引結(jié)構(gòu)r樹，匕d樹等，來查找每個對彖在半徑d范圍內(nèi)的鄰居。假 設(shè)m為異常點數(shù)據(jù)的d領(lǐng)域內(nèi)的最大對象數(shù)目o如果對彖0的m+1個鄰居被發(fā) 現(xiàn)，則對象0就不是異常點。這個算法在最壞情況下的復(fù)雜度為0(陽),r為 維數(shù)，為數(shù)據(jù)集合中對象的數(shù)目。當(dāng)r增加時，基于索引的算法具有良好的擴 展性。2.嵌套循環(huán)算法(nested-loop):嵌套一循環(huán)算法和基于索引的算法有相同 的計算復(fù)雜度，但是它避免了索引結(jié)構(gòu)的構(gòu)建，試圖最小化i/o的次數(shù)。它把內(nèi) 存的緩沖空間分為兩半，把數(shù)據(jù)集合分為若干個邏輯塊。通過精心選擇邏輯塊裝 入每個緩沖區(qū)域的順序，i/o效率能夠改善屮】。3基于單元的算法(cell-bas

11、ed)471 :在該方法中，數(shù)據(jù)空間被劃為邊長等 于/(2恢血)的單元。每個單元有兩個層圍繞著它。第一層的厚度是一個單元, 而第二層的厚度是2 1/2-lo該算法逐個單元地對異常點計數(shù)，而不是逐個對 象地進行計數(shù)。對于一個給定的單元，它累計三個計數(shù)：單元中對象的數(shù) 目(cell_count)、單元和第一層中對彖的數(shù)目(cell_+_ 1 _layer_count)單元和兩個 層次中的對象的數(shù)目(cell_+_2_layers_count)。該算法將對數(shù)據(jù)集的每一個元素 進行異常點數(shù)據(jù)的檢測改為對每一個單元進行異常點數(shù)據(jù)的檢測，它提高了算法 的效率。它的算法復(fù)雜度是0（ck+n）,這里的c是依賴

12、于單元數(shù)目的常數(shù)，k是 維數(shù)。它是這樣進行異常檢測的：若cell_+_l_layer_count>m ,單元中的所有對 象都不是異常；若cell_+_2_layers_count<=m ,單元中的所有對彖都是異常；否 則，單元中的某一些數(shù)據(jù)可能是異常。為了檢測這些異常點，需要逐個對彖加入 處理?；诰嚯x的異常點檢測方法要求用戶設(shè)置參數(shù)p和d,而尋找這些參數(shù) 的合適設(shè)置可能涉及多次試探和錯誤?；诰嚯x的方法與基于統(tǒng)計的方法相比，不需要用戶擁有任何領(lǐng)域知識，與 序列異常相比，在概念上更加直觀。更重要的是，距離異常接近hawkins的異 常本質(zhì)定義。然而，三種類型的基于距離的離群檢測算法

13、中，基于索引的算法和 循環(huán)一一嵌套算法需要0伙切右的時間開銷，因此在大數(shù)據(jù)集中還有待于改進; 而基于單元的算法，雖然與具有線性的時間關(guān)系，但是它與£成指數(shù)關(guān)系，這 限制了它在高維空間中的應(yīng)用，此外，基于單元的算法還需要事先確定參 數(shù)pct, 泅以及單元的大小，這使得算法的可行性比較差；高維空間中，基于 索引的方法由于需要事先建立數(shù)據(jù)集的索引，建立與維護索引也要花大量的時間。 因此三種方法對于高維空間中的大數(shù)據(jù)集，算法的效率都不高44 o1.1.3基于密度的異常點檢測算法基于密度的離群檢測算法一般都建立在距離的基礎(chǔ)上，某種意義上可以說基 于密度的方法是基于距離的方法中的一種，但基于密度

14、的異常觀點比基于距離的 異常觀點更貼近hawkins的異常定義，因此能夠檢測出基于距離的異常算法所 不能識別的一類異常數(shù)據(jù)一一局部異常?；诿芏鹊姆椒ㄖ饕枷胧菍⒂涗浿g 的距離和某一給定范圍內(nèi)記錄數(shù)這兩個參數(shù)結(jié)合起來,從而得到“密度”的概念， 然后根據(jù)密度判定記錄是否為離群點。breunig等人提出的基于局部離群因子的異常檢測算法lof是基于密度方 法的一個典型例子。它首先產(chǎn)生所有點的minpts鄰域及minpts距離，并計算到 其中每個點的距離；對低維數(shù)據(jù)，利用網(wǎng)格進行k - nn查詢，計算時間為0）； 對中維或中高維數(shù)據(jù)，采用如x2樹等索引結(jié)構(gòu)，使得進行k2nn查詢的時間 為0（如）,整

15、個計算時間為o （nlogn）；對特高維數(shù)據(jù),索引結(jié)構(gòu)不再有效, 時間復(fù)雜度提高到0（，嚴(yán)）。然后計算每個點的局部異常因子，最后根據(jù)局部異 常因子來挖掘離群。lof算法中，離群點被定義為和對于全局的局部離群點， 這與傳統(tǒng)離群的定義不同，離群不再是一個二值屬性（要么是離群點，要么是正 常點），它按棄了以前所有的異常定義中非此即彼的絕對異常觀念，更加符合現(xiàn) 實生活中的應(yīng)用。lof算法中充分體現(xiàn)了 “局部”的概念，每個點都給出了一個離群程度， 離群程度最強的那幾個點被標(biāo)記為離群點。此外，aggarwal也提出了一個結(jié)合 子空間投影變換的基于密度的高維離群檢測算法。1.1.4基于深度的異常點檢測算法基

16、于深度的離群點檢測算法的主要思想是先把每個記錄標(biāo)記為k維空間里 的一個點，然后根據(jù)深度的定義(常用peeling depth contours定義)給每個點賦 予一個深度值；再根據(jù)深度值按層組織數(shù)據(jù)集，深度值較小的記錄是離群點的可 能性比深度值較大的記錄大得多，因此算法只需要在深度值較小的層上進行離群 檢測，不需要在深度值大的記錄層進行離群檢測?；谏疃鹊姆椒ū容^有代表性 的有struyf和rousseeuw提岀的deeploc算法。雖然，理論上基于深度的識 別算法可以處理高維數(shù)據(jù)，然而實際計算時，k維數(shù)據(jù)的多層操作中，若數(shù)據(jù)集 記錄數(shù)為n,則操作的時間復(fù)雜度為q (nw 因此 當(dāng)維數(shù)kw3時

17、處理大 數(shù)據(jù)集時還有可能是高效的，而當(dāng)k4時，算法的效率就非常低。也就是說, 已有的基于深度的離群點檢測算法無法挖掘高維數(shù)據(jù)，只有當(dāng)k w 3時計算效率 才是可接受的。1.1.5基于偏移的異常點檢測算法基于偏移的離群檢測算法(deviation-based outlier detection)通過對測試數(shù) 據(jù)集主要特征的檢驗來發(fā)現(xiàn)離群點。目前，基于偏移的檢測算法大多都停留在理 論研究上，實際應(yīng)用比較少。以下三種是比較有代表性的：arning采用了系列 化技術(shù)的方法來挖掘離群，由于算法對異常存在的假設(shè)太過理想化，因此并沒有 得到普遍的認(rèn)同，對于現(xiàn)實復(fù)雜數(shù)據(jù)，其效果不太好，經(jīng)常遺漏了不少的異常數(shù)

18、據(jù)；sarawagi應(yīng)用olap數(shù)據(jù)立方體引進了發(fā)現(xiàn)驅(qū)動的基于偏移的異常檢測 算法；jagadish給出了一個高效的挖掘時間序列中異常的基于偏移的檢測算 法。雖然，基于偏移的離群檢測算法理論上可以挖掘各種類型的數(shù)據(jù)，但是由于 要事先知道數(shù)據(jù)的主要特征，而現(xiàn)實世界中的數(shù)據(jù)集一方面由于數(shù)據(jù)量比較大, 另一方面由于屬性比較多，因此這方面的特征往往不容易發(fā)現(xiàn)，當(dāng)確定記錄z間 的相異度函數(shù)時，如果選擇不合適，則得到的離群挖掘結(jié)果很可能不盡人意，所 以本方法在實際問題屮應(yīng)用得比較少。基于偏移的異常點檢測不采用統(tǒng)計檢驗或者基于距離的度量值來確定異常 對象，它是模仿人類的思維方式，通過觀察一個連續(xù)序列后，迅速

19、地發(fā)現(xiàn)其屮某 些數(shù)據(jù)與其它數(shù)據(jù)明顯的不同來確定異常點對象，即使不清楚數(shù)據(jù)的規(guī)則?；?偏移的界常點檢測常用兩種技術(shù)：序列界常技術(shù)和olap數(shù)據(jù)立方體技術(shù)。我 們簡單介紹序列界常的界常點檢測技術(shù)。序列界常技術(shù)模仿了人類從一系列推測 類似的對象中識別界常對象的方式。它利用隱含的數(shù)據(jù)冗余。給定n個對象的集 合s,它建立一個子集合的序列，s 1 , s2，sm,這里2<= m <=n , 由此，求出子集間的偏離程度，即“相異度”。該算法從集合中選擇一個子集合 的序列來分析。對于每個子集合,它確定其與序列中前一個子集合的相異度差異。 光滑因子最大的子集就是異常數(shù)據(jù)集。這里對幾個相關(guān)概念進行解

20、釋：1 .異常集：它是偏離或異常點的集合，被定義為某類對彖的最小子集，這 些對彖的去除會產(chǎn)生剩余集合的相異度的最大減少。2 相異度函數(shù)：已知一個數(shù)據(jù)集，如果兩個對象相似，相異函數(shù)返回值較 小，反之，相異函數(shù)返回值較大；一個數(shù)據(jù)子集的計算依賴于前個子集的計算。3基數(shù)函數(shù)：數(shù)據(jù)集、數(shù)據(jù)子集中數(shù)據(jù)對彖的個數(shù)。4 光滑因子：從原始數(shù)據(jù)集中去除子集，相異度減小的兩度，光滑因子最 大的子集就是異常點數(shù)據(jù)集。基于偏差的異常點數(shù)據(jù)的檢測方法的時間復(fù)雜度通常為0()，n為對彖個 數(shù)?；谄畹漠惓｜c檢測方法計算性能優(yōu)異,但由于事先并不知道數(shù)據(jù)的特性, 異常存在的假設(shè)太過理想化，因而相異函數(shù)的定義較為復(fù)雜，對現(xiàn)實

21、復(fù)雜數(shù)據(jù)的 效果不太理想。1.1.6高維數(shù)據(jù)的異常點檢測算法以上兒種異常檢測算法一般都是在低維數(shù)據(jù)上進行的，對于高維數(shù)據(jù)的效果 并不是很好。與低維空間不同，高維空間中的數(shù)據(jù)分布得比較稀疏，這使得高維 空間中數(shù)據(jù)之間的距離尺度及區(qū)域密度不再具有直觀的意義1481 o基于這個原 因，aggarwal和yu提出一個高維數(shù)據(jù)異常檢測的方法。它把高維數(shù)據(jù)集映射 到低維子空間，根據(jù)子空間映射數(shù)據(jù)的稀疏程度來確定異常數(shù)據(jù)是否存在。(4-1)高維數(shù)據(jù)的異常點檢測的主要思想是：首先它將數(shù)據(jù)空間的每一維分成小個等 深度區(qū)間。所謂等深度區(qū)間是指將數(shù)據(jù)映射到此一維空間上后，每一區(qū)間包含相 等的f=i/的數(shù)據(jù)點。然后在

22、數(shù)據(jù)集的k維子空間中的每一維上各取一個等深 度區(qū)間，組成一個£維立方體，則立方體中的數(shù)據(jù)映射點數(shù)為一個隨機數(shù)毛。設(shè)n(d)為e維立方體d所包含點數(shù)，n為總的點數(shù)。定義稀疏系數(shù)s(d)如(41所示：嚴(yán)）一2嚴(yán) z嚴(yán)）s（d）為負(fù)數(shù)時，說明立方體d中數(shù)據(jù)點低于期望值，s（d）越小，說明該立方 體中數(shù)據(jù)越稀疏。數(shù)據(jù)空間的任一模式可以用ml m2 . mi表示。mi指此數(shù)據(jù)在第i維子 空間映射區(qū)間，可以取值1到，或者*（牢表示可以為任意映射值）。異常檢測 問題可以轉(zhuǎn)化成為尋找映射在k（k作為參數(shù)輸入）維子空間上的異常模式以及 符合這些異常模式的數(shù)據(jù)。如4維空間中一個映射在2維子空間上的模 式

23、（=10 ） *3*90高維數(shù)據(jù)中尋找異常模式是非常困難的。一個簡單辦法是對所 有數(shù)據(jù)維進行組合，來搜索可能異常模式，但是效率極其低下。1.2岀口產(chǎn)品質(zhì)量異常檢測的思路和算法分析檢疫檢疫局監(jiān)管出口企業(yè)牛產(chǎn)批質(zhì)量數(shù)據(jù)的過程是：首先檢驗檢疫局下發(fā)給 企業(yè)產(chǎn)品出口標(biāo)準(zhǔn)和參數(shù)，企業(yè)的質(zhì)量控制人員可以參考此標(biāo)準(zhǔn)和參數(shù)組織生產(chǎn) 活動，同時將出口產(chǎn)品的某一批次定位牛產(chǎn)批，在產(chǎn)品的生產(chǎn)過程，將牛產(chǎn)批的 質(zhì)量監(jiān)控數(shù)據(jù)上報到檢疫檢疫局。此牛產(chǎn)批將與后期在檢驗檢驗局擊口報檢產(chǎn)品 建立對應(yīng)關(guān)系，這樣如果出口產(chǎn)品出現(xiàn)問題，檢疫檢疫丸法機構(gòu)可以通過此種模 式的回溯機制定位到此產(chǎn)品牛產(chǎn)過程的質(zhì)量參數(shù)。目前企業(yè)上報的牛產(chǎn)批數(shù)

24、據(jù)主 要是企業(yè)自身的質(zhì)量控制人員手工錄入的，數(shù)據(jù)錄入過程中人為因素很大。出口 電子監(jiān)管系統(tǒng)中建立了一套復(fù)雜的基于規(guī)則標(biāo)準(zhǔn)的監(jiān)管體系，檢疫檢疫局認(rèn)可通 過出口電子監(jiān)管系統(tǒng)綜合評定的企業(yè)上報的牛產(chǎn)批數(shù)據(jù)，但是對于一些有意鉆漏 洞的企業(yè)，如果其一旦掌握了電子監(jiān)管系統(tǒng)的評定規(guī)則，將對出口產(chǎn)品的質(zhì)量安 全帶來新的危險。出口產(chǎn)品質(zhì)量的異常檢測就是在此問題的背景下，借助文中闡 述的olam模型，通過時間序列的相似度查詢，找到異常序列。企業(yè)在牛產(chǎn)過程中是存在某些時間序列的，其時間序列可能存在一些規(guī)律性 的變換，例如季節(jié)變化產(chǎn)牛的植物類食品的周期性變換，企業(yè)的牛產(chǎn)工藝加工方 法造成的周期性變化等等。有些異常點檢

25、測的研究主要集中于數(shù)據(jù)集內(nèi)單數(shù)據(jù)點, 這一方法在進行欺詐檢測、金融監(jiān)管、可疑交易監(jiān)控等實際應(yīng)用過程中出現(xiàn)了誤 報率高、真正的異常行為模式被掩蓋的問題，產(chǎn)牛問題的原因是現(xiàn)實?；钪懈鞣N 波動周期的存在印。例如，一個賬戶連續(xù)11個月每月存入5千元，到第12月 突然存入5萬元，基于單數(shù)據(jù)點比較的離群判別模式將認(rèn)為該月數(shù)據(jù)顯著異常而 報告為離群點，而這5萬元實際可能是一筆正常的年終獎金?；跁r間序列相似 度分析的方法則將多個數(shù)據(jù)點通過時間軸連接成曲線，由點擴展到線，對線與線 之間的相似度或差異度進行分析，由此可將孤立事件宙聯(lián)而成有規(guī)律的行為模式 理解，更能夠反映岀人們在現(xiàn)實生活中的活動規(guī)律。由此可見，電

26、子監(jiān)管中的出 口企業(yè)也同樣存在這個規(guī)律，尤其食品的出口跟時間有著密切的聯(lián)系。論文中的 通過研究不同的異常點檢測算法，找到了一種基于時間序列相似度的離群點檢測 模式。1.2.1時間序列相關(guān)背景時間序列由兩個基本因素構(gòu)成：一個是被研究現(xiàn)象所屬時間，另一個是反映 該現(xiàn)象一定時間條件下數(shù)量特征的指標(biāo)值。從統(tǒng)計意義上來講，所謂時間序列就是將某一指標(biāo)在不同時間上的不同數(shù)值, 按照時間的先后順序排序而成的數(shù)列。這種數(shù)列由于受到各種偶然因素的影響， 往往表現(xiàn)岀某種隨機性，彼此之間存在這統(tǒng)計上的依賴關(guān)系。雖然每一個時刻上 的取之或數(shù)據(jù)點的位置具有一定的隨機性，不可能完全準(zhǔn)確地用歷史值來預(yù)測將 來，但是前后時刻的

27、數(shù)值或數(shù)據(jù)點的相關(guān)性往往呈現(xiàn)某種趨勢性或周期性變化， 這是時間序列挖掘的可行性之所在。時間序列挖掘通過對過去歷史行為的客觀記 錄分析，揭示其內(nèi)在的規(guī)律（如波動的周期、振幅、趨勢的種類等），進而完成 預(yù)測未來行為等決策性工作30,o在統(tǒng)計分析中，對時間序列還采取一種簡化、直接的分析方法，它沒有具體 描述被研究現(xiàn)象與其影響因素之間的關(guān)系，而是把各影響因素分別看作一種作用 力，被研究對象的時間序列則看成合力；然后按作用特點和影響效果將影響因素 規(guī)為4類，即趨勢變動（t ）、季節(jié)變動（s ）、循環(huán)變動（c ）和隨機變動 （i）o這四種類項的變動疊加在一起，形成了實際觀測到的時間序列，因而可 以通過對這

28、四種變動形式的考察來研究時間系列的變動31在時間序列序列挖掘的研究中，目前比較集中的問題之一是時間序列的快速 查詢以及相應(yīng)的存取結(jié)構(gòu)設(shè)計。早期的工作著重與精確查找。但是，大多數(shù)新型 的數(shù)據(jù)庫應(yīng)用，特別是數(shù)據(jù)挖掘應(yīng)用需要數(shù)據(jù)庫具備相似（similarity）查找能 力。對于在兒兆，甚至兒十兆的時間序列數(shù)據(jù)庫中發(fā)現(xiàn)兩個模式相似的序列，手 工處理很難勝任這樣的工作，傳統(tǒng)的數(shù)據(jù)庫查找方法也難以完成此類任務(wù)，因此 時間序列相似性查找成為目前數(shù)據(jù)挖掘領(lǐng)域的一個新的研究課題。目前國際和國 內(nèi)對時間序列相似度的研究提岀了許多種解決方法，這些方法主要包括基于直接 距離、傅立葉變換、arma模型參數(shù)法、規(guī)范變換、

29、時間彎曲模型、界標(biāo)模型、 神經(jīng)網(wǎng)絡(luò)、小波變換、規(guī)則推導(dǎo)等。從理論上來看，基于統(tǒng)計特性描述(如一階統(tǒng)計量和高階統(tǒng)計量)或參數(shù)建 模(如ar建模和arma建模)的傳統(tǒng)時間序列分析方法有可能用來解決相似 性問題，但實際上并不能得到很好的結(jié)果，其主要困難在于相似性度量的定義和 算法的時間復(fù)雜度，而這兩者都依賴于時間序列的近似表示方法。因此，尋求某 種魯棒性強且計算復(fù)雜度低的時間序列近似表示方法，一直是解決相似性搜索問 題的關(guān)鍵。迄今為止，時間序列相似性搜索問題已經(jīng)提出了 10年左右的時間， 在這段時間內(nèi)，先后出現(xiàn)了許多而向相似性搜索的時間序列近似表示方法， 如 agrawal 采用的離散傅立葉變換(d

30、ft , discrete fourier transform) chan 等 人采用的haai小波變換方法、last等人提出的關(guān)鍵特征(如斜率和信噪比) 法、guralnik等人提岀的字符表方法、korn等人提出的奇異值分解(svd , singular value decomposition )法、keogh 等人先后提岀的分段累積 近似法(paa , piecewise aggregate approximation )、分段線性表示(plr , piecewise linear representation )和適應(yīng)性分段常數(shù)近似法(apca , adaptive piecewise

31、constant )等分段方法，以及 pcrng 等人提出的 界標(biāo)模型(landnk model )等。這些表示方法各有所長，為時間序列相似性 研究提供了諸多可以借鑒與參考的方向卩卩。本論文通過olam模型，實現(xiàn)了 在weka中基于離散傅里葉變換的時間序列相似性查找方法，通過此異常檢查策 略的實際應(yīng)用來展示olam模型的實用性。1.2.2基于離散傅立葉變換的時間序列相似性查找傅立葉變換是一種重要的積分變換，早已被廣泛應(yīng)用。在時間序列分析方面, 離散傅立葉變換具有獨特的優(yōu)點。例如，給定一個時間序列，可以用離散傅立葉 變換把其從時域空間變換到頻域空間。根據(jù)parseval的理論，時域能量函數(shù)與頻

32、域能量譜函數(shù)是等價的。這樣就可以把比較時域空間的序列和似性問題轉(zhuǎn)化為比 較頻域空間的頻譜相似性問題。另外，因為頻域空間的大部分能量集中前兒個系 數(shù)上，因此可以不考慮離散傅立葉變換得到的其他系數(shù)。把這些被保留系數(shù)看作 從時間序列上提取的特征，這樣就可以從每個序列中獲得若干(記為k)特征, 進而可以進一步把它們映射到k維空間上。這樣就可以用一些目前被廣泛采用多 維索引方法(如r*數(shù)、kd-樹、線性四叉樹(linear quad tree )、網(wǎng)格文件(grid - file ),來存儲和檢索這些多維空間的點】®。下面描述一下如何進行基于離散傅立葉變換的完全匹配。所謂完全匹配必須 保證被查找的序列與給岀的序列有相同的長度。因此，與子序列匹配相比，工作 就相對簡單一些。1.1.1完全匹配查找算法給定一個時間序列x=xt|t = o, 1 ,，ml,對x進行離散傅立葉變 換，得到（4-2）這里，x與xt代表時域信息，而與xf代表頻域信息，=xf| f=0, 1 , , n - 1 , xf為傅立葉系數(shù)。n-1了= 1/亦工“exp（-ft'f =ojv.j/-l（"2八根據(jù)parserval的理論，時域能