在研究如何對時間序列進行線性分段的時候，瀏覽了60篇左右論文和教材的片段，對其中的6篇仔細閱讀并編寫程序和單元測試實現相應的算法。同時為了直觀的看到分段效果，還制作簡易的曲線圖呈現原始序列和分段序列。這種超負荷的工作，是在一周之內完成的，目的只有一個:選擇算法。

         作為程序員，實際上并不能算是研究人員，多數情況下，他只需要不同的蘋果中選擇一個蘋果而已，沒有必要去種蘋果樹。

      但凡需要“選擇”的時候，工作步驟如下：1、確定你想要達到的目的，這個最為重要，你的目的貫穿整個工作，千萬不要在相親的時候，突然對對方的妹妹格外關注；2、區分關注的層次比如，簡要的閱讀能夠排除很多不需深究的東西，上面說到的60篇論文中的54篇要么是作者本身顯得不妥、要么是某種方式的抄襲、要么其提供的分段圖形本身就不符合要求，簡單的五分鐘你就能夠排除，無需浪費時間。3、你感興趣的算法各有優勢和缺陷的時候，有無可能對某種主要的算法進行調整，或者組合應用其他算法的某些概念?4、實在找不到合適的算法，或者組合相應算法也無力達成的時候，能否基于你的需要而自行設計新的算法？當然，到這個層面，你也變成了那群做研究的書呆子之中的一員，不過一定要確定一點，至少你的目的明確，這和他們混稿費、混基金、呆在實驗室空想是不同的，身為程序員你其實很有優勢的。

        下面對算法的描述，并沒有采用那些很精確的命名，而只是從算法的特征來分類。事實上大約有十來種主流的算法和近百種各類擴展、調整、優化的算法，每個都號稱自己效果如何好、效率如何高、怎樣支持在線劃分等，但我們沒有必要陷入他們的戰爭。選擇到最后確定幾種分段算法，我個人用的時間是一周，過于沉湎細節的話，恐怕一個月都無法做決斷。例圖中使用深圳A股深發展在2009年和2010年的實際收盤價走勢，黑線為原始數據，紅線為擬合線段，紅點為分段點。

 

一、對時間序列分段，是什么意思？

     時間序列，在二維平面上實際上是一條曲線，所謂分段，就是用一系列首尾相接的線段，近似的表達一條曲線。

    下圖是將誤差設為5級的分段圖，這個粗略一些，用于長期趨勢的分析。實際曲線有482個點，壓縮后用22個點描繪實際曲線的趨勢變化：

 

下面是誤差設為3級的分段圖，和原有曲線走勢更加吻合一些，用于短期波動的分析：

 

二、為什么要對時間序列分段？

      第一個原因，很多時候，我們關注時間序列的主要趨勢變化，而不太關注具體的數值和少量的異常點，對序列分段，我們可以抓住重點。比如某個公司更關心其在各城市銷售數量增長沒有，今天1百萬，明天90萬，后天110萬，大后天130萬，增長了沒有？所以分段實際上是表達趨勢，你可以將時間序列用自然語言表達，即在10月1日到11月5日之間，銷售量大致保持每天增長0.5%的趨勢，11月5日到11月9日之間，銷售量以每日平均下跌0.02%的趨勢。

     第二個原因，提高時間序列的運算性能。時間序列往往很長，數據量比較大，而序列的查詢操作、聚類操作，往往涉及的計算量驚人，舉例來說，2000個接近4000條記錄的時間序列，遍歷搜索一遍，在性能不錯的筆記本上往往需要10個小時左右的時間。而縮小時間序列的長度，將大幅提高計算的效率，這個提高往往是50倍甚至100倍這樣的概念。這往往讓不可能的事情變得可能，比如你的一項分析需要運算一周才能出數據，屆時黃花菜肯定是分外的涼，估計沒有人會需要這樣的軟件系統。

     第三個原因，在不同精度層面上搜索。我們經常需要對同一時間序列，做長期趨勢、中期趨勢和短期趨勢的分析。比如我們可能需要搜索60天的數據，也可能需要搜索5天的數據。通過控制劃分時間序列的壓縮度，我們可以在不同層次上運算，一些時候考慮長遠趨勢，圖像會平滑一些。一些時候考慮短期趨勢，圖像會靈敏一些。固然，我們能夠通過使用移動平均、或者將時間周期提升一個層次，來對原始序列做預處理，但在不同的壓縮度的情況下劃分時間序列，則是比較通用的辦法。明明可以這么簡單，又何須額外考慮許多數據預處理之類的工作？    

 

三、在選擇分段算法的時候，我們的核心要求是什么？

1、可以調整搜索的精度，以獲取更精細的分段和更粗略的分段。

2、用于調整精度的閥值，要易于理解，且與不同時間序列的具體數值無關。

3、同樣的壓縮比，我們希望分段的效果和原來的曲線更加吻合。

4、次要目標:希望性能較好。這個很多時候可以放棄。

5、次要目標：希望支持在線劃分，也就是增量劃分，這樣我們可以保存分段的結果，新增數據后只要做少量的調整就行了。支持增量劃分，則性能會達到頂點，不過要注意，前提是你要支持多少個不同精度的劃分？如果算法參數過于復雜，則增量搜索要保存很多不同的分段結果，這是不合適的。所以，即使支持增量劃分的算法，也要考慮你實際應用有沒有可能使用的可能。

所以對算法優劣的評估標準，應是：在相同擬合誤差的情形下，壓縮比越高越好；算法的閥值，不應與具體序列的數值有關。

 

四、先說說我們結論：

1、分段算法，可粗略的分為全局算法和局部算法。全局算法在整個時間序列的基礎上，尋找最優的分段集合。局部算法根據局部的特征，從左到右尋找符合要求的分段。

2、如果要精確表達，同時獲得較好的壓縮比，采用BU算法，當然這種算法的計算量較大，且不支持在線劃分。如果要支持增量劃分，采用SW或者層次聚類的算法。

3、多數情況下，極值點和特征點算法，由于是局部算法，其精度和壓縮比不能很好的平衡，不予考慮。

4、分段和降噪應區分開來考慮，即先分段，然后根據需要對分段的結果降噪。這有助于簡化思維，因為在分段的時候，精度和壓縮比之間，本來存在矛盾，分段算法的關鍵在于兩者間的平衡。而降噪，則是和精度、壓縮比有關的，降噪會導致精度下降同時提高壓縮比。

5、閥值的確定，應該容易理解，同時也要容易選擇，目前尚沒有發現能夠自行根據曲線的統計特征確定閥值的算法。所以我們不妨對閥值做一定的變換，比如我們將擬合誤差變換成一個百分比，即誤差越大則分段越少，取值在0到100之間。基于距離的，我們可以將其變換為與原始點的值的比例。算法應盡可能避免和序列的實際值有關，要保證相同的閥值針對不同序列具備相同的分段效果。

6、永遠不要考慮多維時間序列的問題，因為你能處理一維，就意味著你可以處理多維，此時，你僅需要考慮不同維度的先后秩序問題和權重問題，這個并不復雜。許多從事多維數據序列分析研究的專家，其實并不適合于做研究，因為既然涉及到這個領域并投入精力，本身說明其抽象思維方面素質太差。

 

四、全局算法

1、自頂向下TD算法：

    時間序列的開始點和結束點，是首先選中的分段點。然后，遍歷兩點之間的所有點，找出和這兩點連成的直線距離最大的點，如果這個點到直線的距離“大于”預先給定的閥值，我們將其稱為R，則將它作為第三個分段點。這樣我們就有了兩個線段，做了最初步的劃分。

    之后，這個新增點到左邊相鄰點和右邊相鄰點構成的兩條線段，繼續尋找距離最大的點，然后，找到的兩個點，誰與相應的線段距離最大，且這個距離“大于”閥值R，則該點作為第四個分段點….如此循環，直到再也找不到距離大于R的點，分段完成。

    這個閥值，也就是點到線段的距離，可以使用正交距離(原始點和分段線段在該點的值的差的絕對值)、垂直距離(原始點到分段線段的直線的長度）和歐式距離，當然也可以設置其他的特性作為閥值，比如擬合誤差、又比如弧度、角度、余弦等，由此可以引申很多種不同的算法，這也是多數教授們所樂于從事的研究，簡單。我們一般選擇垂直距離就行了。

    這個閥值不太好理解，且與不同的時間序列具體取值有關，直接應用完全沒有通用性。我本人在項目中，將其做一定的變換處理的。

 

2、自底向上BU算法：

    這是TD算法的逆過程，首先將時間序列，劃分為相鄰點的短序列，當然此時的擬合誤差為0，因為第一點和第二點的連線，原始點都落在線段上。將相鄰兩個線段連接起來，此時每條線段包含三個原始點，計算中間那個點的擬合誤差。這樣，所有這些三個點的線段中的中間點的擬合誤差計算出來后，找出誤差最小且誤差小于閥值R的分段，作為第一條包含三個點的線段。

     在上面的基礎上，第一條分段同樣的和相鄰線段連接，然后計算每一條分段的擬合誤差，再找出誤差最小且小于閥值R的分段，作為第二個分段。

     依次方式循環，直到所有分段的擬合誤差都小于閥值R，分段結束。

     當然，你同樣可以使用正交距離、垂直距離等其他屬性，由此算法又演變成多種不同的算法。

 

五、局部算法

1、固定窗口PAA算法：

    這個最簡易，閥值為R，表示你要將序列分成多少段。然后使用線段的長度除以這個值，得到窗口的長度L。從序列的第一點開始，到第L-1點作為第一段，用其平均值表示。這種算法實際上類似股票日線中的5日均價、10日均量。非常粗略，擬合不夠精確。但這種算法，好象是時間序列分段研究最早的成果。

2、滑動窗口SW算法：

   給一個窗口長度的最小值N和最大值M，然后從序列第一點開始，與第N點連線，計算各點擬合誤差，如果誤差總值小于給定的閥值R，擬合成功，增加窗口的長度，連線再計算擬合誤差，如果擬合誤差小于R，繼續增加窗口長度一直到窗口長度為M。如果擬合誤差大于R，則第一段結束，該點作為新的窗口的起始點，繼續同樣的過程，直到序列劃分完畢。

      這種算法屬于局部算法，有方向性，從算法的原理來看，就容易漏報和將本應擬合的線段劃分為兩條線段。代碼實現的效果來看，劃分的不太理想。

3、極值點：

    所謂極值點，是指曲線中的轉折點，尋找極值點的算法很簡單，從序列第二點開始遍歷，沒點如果同時比前后兩點大，或者同時比前后兩點小，那么這個點就是時間序列的一個極值點。找出所有極值點的集合，就得到了所有分段點。這種算法，是基于人類視角的關注點而來，但很顯然存在兩個問題：1、是局部算法，只考慮與相鄰兩點的問題，所以劃分的時候容易過于精確而忽略趨勢。2、只考慮了趨勢反向問題，即從上升到下降和從下降到上升，沒有考慮趨勢加速問題，比如先是15%角度上升，然后是40%角度上升，之間的結合點顯然漏掉了。這也意味著此種算法從原理上就不能精確表達趨勢。優點也是有的，即計算簡單，性能很好，支持在線劃分，沒有閥值。

4、特征點：

    在極值點的基礎上，加上判斷，比如兩個極值點之間的距離必須大于某個閥值，或者該極值點除了比前后點同時大或同時小之外，還需要大于某個比例閥值R。這樣的改進意義不大，只是進一步減少極值點而已。

5、趨勢點：

    在極值點的基礎上，考慮了趨勢加速問題，即計算某點和相鄰點的角度，或者弧度、或者余弦等，大于某個特定閥值R的稱為趨勢點，按照這種算法基本上不會遺漏掉極值點，趨勢加速或減速的關鍵點也不會遺漏掉。不過這同樣是一種局部算法，極值點方法其他毛病，這種算法并沒有避免。

6、層次聚類：實際上僅僅運用了KMean算法的中心和半徑的概念，其他沒多少區別。這種算法的閥值比較多，而且看起來分類的效果不好，沒有看點。不過這種算法，其分類的效果好于SW算法，也同樣的支持在線劃分。

 

六、時間序列自身特征問題：

    一部分類型的時間序列，遵循一定的規律，價格逐日波動的過程相對平穩，另一些很可能出現前后兩天變動數倍的情形。

    這樣，首先我們面臨的問題，是能否針對不同業務含義的數據調整精度，以正常的分段；第二，是能否對數據進行預處理，以支持分段。

    這兩種方式，事實上都與業務系統相關。

    反過來說，我們需要研究，能否通過自動分析數據本身的特征，由算法來決定是否需要預處理、基于何種模式設置何種精度合適。這里涉及到的序列特征，包括序列的極值(最大與最小的差距)、序列的標準差(反映離散程度)、序列的最大取值范圍(出現最多的區域，出現百分比多少),當然，這僅僅是一些統計學方面的概念。

    事實上，對于波幅巨大的序列，如果分段，則很可能出現全部原始點都是分段點的情形，這種情形下的趨勢價值有限。使用移動平均的方式來平滑是一個辦法，但這里的相似性度量仍然會存在問題。

 

七、進一步關注的內容：

    時間序列方面的具體應用，無非落實在識別、趨勢分析和異常檢測，在趨勢分析方面，基于擬合的思路遠不如使用時間序列基于搜索、聚類和統計的思路。基于擬合的思路，做決策支持分析的時候，是無法說服客戶的。比如神經網絡之類的方式，本質上就是用公式表示現在的走勢，同時認為未來的走勢也符合這個公式的規律，這個顯然是期望使用數學來統治世界，很難令人信服。其他諸如ARMA之類的方法，大體上也是同樣的路子。 只有基于搜索、聚類和統計的方法，才能夠有一定的說服力，因為這里找出的是一些歷史上已經發現的模式，期間蘊藏著我們不容易表達的規律。

      由于時間序列，或者說有向序列，通常的需求無非在趨勢和異常兩點。而表達趨勢方面，需要一定的模糊性，那么模糊數學、機器學習方面的一些概念，能否用于這個領域，目前尚沒有特別有效的方法。

      現有的時間序列工具，當圖像被當作二維平面上的點的時候，按照先左后右獲得第一條序列，從上到下獲得所有序列這樣的順序，是能夠進行分析的，比如找出相片中有多少人、找出相片中的人是不是你本人、找出相片中出現了一輛車沒有、指紋是否符合等、雷達中獲取的反射信息構成的模糊形狀是否可能是一架飛機？當然，同樣的擴展到三維空間，則對3d圖形實際上也能夠處理，無非是確定序列數量和方向、確定各序列權重的問題。