時間序列分類算法研究.pdf

1、時間序列數(shù)據(jù)廣泛存在于日常生活中的幾乎每一個應(yīng)用領(lǐng)域。它們是實值型的序列數(shù)據(jù)，具有數(shù)據(jù)量大，數(shù)據(jù)維度高，以及數(shù)據(jù)不斷更新等特點。時間序列分類問題與傳統(tǒng)分類問題之間的主要區(qū)別在于，時間序列數(shù)據(jù)的各個變量之間具有次序關(guān)系，而傳統(tǒng)分類問題認(rèn)為屬性次序是不重要的，并且變量之間的相互關(guān)系獨立于它們的相對位置。因此，時間序列分類問題已成為數(shù)據(jù)挖掘領(lǐng)域的特殊挑戰(zhàn)之一。
　　時間序列分類問題主要面臨著三個方面的挑戰(zhàn)。首先，對于傳統(tǒng)分類器而言，輸入

2、數(shù)據(jù)為特征向量，然而時間序列數(shù)據(jù)并沒有明確的特征;其次，盡管可以在時間序列數(shù)據(jù)上進(jìn)行特征選擇，但由于其特征空間維度非常大，特征選擇的過程會花費很大的計算量;最后，在某些應(yīng)用中，除了精確的分類結(jié)果之外，我們還希望得到具有可解釋性的分類器。但由于其沒有明確的特征，建立一個可解釋性的分類器是非常困難的。本文圍繞以上三個問題深入研究如何建立具有可解釋性的時間序列分類器，主要貢獻(xiàn)如下:
　　(1)研究得出一種基于邏輯shapelets轉(zhuǎn)換的

3、時間序列分類算法。時間序列shapelets是時間序列中最具有辨別性的子序列。首先，針對時間序列規(guī)范化過程緩慢的問題，通過應(yīng)用一種基于智能存儲和計算重用的技術(shù)，將發(fā)現(xiàn)shapelets的時間復(fù)雜度降低一個數(shù)量級;其次，為提升shapelet的辨別性，提出一種基于合取或析取的邏輯shapelets的轉(zhuǎn)換方法。通過邏輯shapelets轉(zhuǎn)換，將初始時間序列轉(zhuǎn)換成新的非序列數(shù)據(jù)，同時也把時間序列的分類問題轉(zhuǎn)化成了經(jīng)典的分類問題。此方法在保持s

4、hapelets辨別性的同時提升了分類的準(zhǔn)確性。
　　(2)研究得出一種簡單有效的shapelet剪枝和覆蓋方法。首先，針對shapelets轉(zhuǎn)換時相似shapelets過多的問題，提出一種基于shapelet分裂閾值的剪枝方法，用于過濾掉相似的shapelets，并大幅度減少候選shapelets樣本的數(shù)量;其次，提出一種基于shapelets覆蓋的方法來確定數(shù)據(jù)轉(zhuǎn)換時shapelets的數(shù)量，并保證shapelets對實例的覆

5、蓋;最后，闡述如何將所提出算法擴展到邏輯shapelets轉(zhuǎn)換中，并將所提出的算法和其他基于shapelets的時間序列分類算法，以及基于不同距離度量的1-NN基準(zhǔn)分類器作對比，闡明所提出算法的分類準(zhǔn)確性和可解釋性。
　　(3)首次將關(guān)聯(lián)式分類器應(yīng)用于普遍的時間序列分類問題中，闡述了基于SAX(Symbolic Aggregate approXimation)表示的關(guān)聯(lián)式分類器在時間序列數(shù)據(jù)上的可解釋性。首先，針對傳統(tǒng)關(guān)聯(lián)規(guī)則主要

6、應(yīng)用于符號型事務(wù)數(shù)據(jù)而無法應(yīng)用于數(shù)值型時間序列的問題，采用SAX表示方法離散化并符號化時間序列;其次提出一種改進(jìn)的CBA(Classification Based on Associations)算法，用于發(fā)現(xiàn)類序列規(guī)則并分類預(yù)測。在此基礎(chǔ)上，提出一種懶惰式的關(guān)聯(lián)式分類算法，避免產(chǎn)生過量規(guī)則，并保證規(guī)則對測試實例的覆蓋。另外也評估了四種不同的類序列規(guī)則評價方式。
　　(4)研究得出一種具有可解釋性的基于動態(tài)時間彎曲(Dynamic

7、 Time Warping，DTW)的k近鄰（k nearest neighbours，k-NN）分類器。k-NN分類器被認(rèn)為是當(dāng)前解決時間序列分類問題的基準(zhǔn)分類器。針對其可解釋性的不足，首先，提出了一種新的有效的時間序列加權(quán)模型，為每一條時間序列的每一個特征提供權(quán)值;其次，提出了兩種不同的DTW加權(quán)方式來發(fā)現(xiàn)辨別性子序列，通過和其他基于非相似性度量的k-NN分類器相比較，展示了其可解釋性;最后，將所提出模型擴展至多變量時間序列分類問題