[發(fā)明專(zhuān)利]一種時(shí)間序列相似性計(jì)算裝置和方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201910080442.4
• 申請(qǐng)日: 2019-01-28
• 公開(kāi)（公告）號(hào): CN109783051B
• 公開(kāi)（公告）日: 2020-05-29
• 發(fā)明（設(shè)計(jì)）人: 鄢貴海;盧文巖;朱凱
• 申請(qǐng)（專(zhuān)利權(quán)）人: 中科馭數(shù)（北京）科技有限公司
• 主分類(lèi)號(hào): G06F7/02
• 分類(lèi)號(hào): G06F7/02
• 代理公司: 北京金咨知識(shí)產(chǎn)權(quán)代理有限公司 11612
• 代理人: 宋教花

本申請(qǐng)?zhí)峁┝艘环N時(shí)間序列相似性計(jì)算裝置和方法，該裝置包括：序列緩沖器，用于緩存第一時(shí)間序列和作為模板序列的第二時(shí)間序列；距離運(yùn)算單元，用于計(jì)算第一時(shí)間序列的元素值和第二時(shí)間序列的元素值之間的距離，得到距離矩陣；存儲(chǔ)單元，用于存儲(chǔ)第一時(shí)間序列的多個(gè)滑動(dòng)窗口對(duì)應(yīng)的距離矩陣；多個(gè)累加距離運(yùn)算單元，用于根據(jù)滑動(dòng)窗口長(zhǎng)度和模板序列的長(zhǎng)度，在多個(gè)滑動(dòng)窗口內(nèi)復(fù)用所述距離矩陣的元素并基于動(dòng)態(tài)時(shí)間規(guī)整算法并行計(jì)算第一時(shí)間序列在各個(gè)滑動(dòng)窗口內(nèi)的子序列與第二時(shí)間序列的規(guī)整路徑距離；以及控制邏輯，用于對(duì)所述序列緩沖器、距離運(yùn)算單元和多個(gè)累加距離運(yùn)算單元進(jìn)行邏輯控制。

技術(shù)領(lǐng)域

本申請(qǐng)涉及數(shù)據(jù)處理技術(shù)領(lǐng)域，尤其涉及一種時(shí)間序列相似性計(jì)算裝置和方法。

背景技術(shù)

時(shí)間序列是金融計(jì)算中常見(jiàn)的數(shù)據(jù)形式。對(duì)于時(shí)間序列處理來(lái)說(shuō)，一個(gè)普遍的任務(wù)就是比較兩個(gè)時(shí)間序列的相似性。在實(shí)際應(yīng)用中，時(shí)間序列的長(zhǎng)度往往并不相等，傳統(tǒng)的歐式距離無(wú)法有效衡量不等長(zhǎng)時(shí)間序列之間的相似性，由此引入了動(dòng)態(tài)時(shí)間規(guī)整算法(Dynamic Time Warping,DTW)。DTW是一種基于動(dòng)態(tài)規(guī)劃(Dynamic Programming,DP)的序列匹配算法，它通過(guò)時(shí)間序列補(bǔ)齊和距離累積的方式來(lái)計(jì)算兩個(gè)不等長(zhǎng)時(shí)間序列的相似性，廣泛應(yīng)用于模式識(shí)別，數(shù)據(jù)挖掘和信息檢索中。具體算法如下所述：

若時(shí)間序列X和時(shí)間序列Y的長(zhǎng)度分別為n和m，即

X(X(1),X(2),X(3),...,X(i),...,X(n))；

Y(Y(1),Y(2),Y(3),...,Y(j),...,Y(m))；

根據(jù)時(shí)間序列X和Y可構(gòu)建m*n階矩陣：

矩陣元素d(i,j)表示時(shí)間序列X的元素值x_i和時(shí)間序列Y的元素值y_j之間的距離。動(dòng)態(tài)時(shí)間規(guī)整算法的核心思想在于尋找一條通過(guò)矩陣元素的路徑，使得路徑上矩陣元素d(i,j)的累加和最小，路徑通過(guò)的元素即為計(jì)算兩個(gè)時(shí)間序列相似性的點(diǎn)，路徑的累積距離就是兩個(gè)時(shí)間序列的相似性。

定義規(guī)整路徑W(Warping Path)：

W＝w₁,w₂,…,w_i,…，w_kmax(m，n)≤k≤m+n-1

規(guī)整路徑W將時(shí)間序列X的時(shí)間軸n非線(xiàn)性地映射到時(shí)間序列Y的時(shí)間軸m上，并且滿(mǎn)足式中D(n，m)為規(guī)整路徑的累積距離，或稱(chēng)規(guī)整路徑距離。規(guī)整路徑需要滿(mǎn)足以下約束條件：

(1)邊界條件：w₁＝(1,1),w_k＝(m,n)

(2)單調(diào)連續(xù)條件：若w_i-1＝(a，b),w_i＝(a′，b′)，則a′-a＝0，1，且b′-b＝0,1。

目前，基于動(dòng)態(tài)時(shí)間規(guī)整算法的大規(guī)模時(shí)間序列處理往往采用通用處理器來(lái)實(shí)現(xiàn)，而摩爾定律的放緩使得通用處理器的性能提升有限，數(shù)據(jù)規(guī)模的與日俱增更加凸顯了通用處理器計(jì)算能力的不足。因此，目前基于動(dòng)態(tài)時(shí)間規(guī)整算法的大規(guī)模時(shí)間序列處理受限于硬件的運(yùn)算速度，無(wú)法滿(mǎn)足大數(shù)據(jù)實(shí)時(shí)處理的需求，同時(shí)系統(tǒng)的能耗也相對(duì)較高。

發(fā)明內(nèi)容

有鑒于此，本發(fā)明提出了一種基于滑動(dòng)時(shí)間窗口的時(shí)間序列相似性計(jì)算裝置和方法，以專(zhuān)用的數(shù)據(jù)架構(gòu)實(shí)現(xiàn)對(duì)時(shí)間序列的高效處理，來(lái)快速計(jì)算時(shí)間序列間的相似性。

本發(fā)明的一個(gè)方面提供一種時(shí)間序列相似性計(jì)算裝置，該裝置包括：

序列緩沖器，用于緩存第一時(shí)間序列和作為模板序列的第二時(shí)間序列；