時(shí)間序列分類(lèi)算法研究.pdf

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

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

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

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

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

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

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