涂 輝，劉 麗，2，張正金

TU Hui1,LIU Li1，2,ZHANG Zhengjin1

1.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫214122

2.無錫市第四人民醫(yī)院 信息科，江蘇 無錫214122

1.School of IOT Engineering,Jiangnan University,Wuxi,Jiangsu 214122,China

2.Department of Information,Wuxi Fourth People’s Hospital,Wuxi,Jiangsu 214122,China

1 引言

時(shí)間序列是一類常見且與時(shí)間相關(guān)的高維數(shù)據(jù)，也是數(shù)據(jù)挖掘領(lǐng)域中主要的研究對(duì)象，廣泛存在于金融、醫(yī)學(xué)、氣象、網(wǎng)絡(luò)安全等領(lǐng)域中[1]。時(shí)間序列相似性度量是時(shí)間序列分析中的重要任務(wù)之一，對(duì)時(shí)間序列的分類、聚類、檢索具有重要意義。

目前時(shí)間序列相似性的度量方法主要有：歐氏距離法[2]（Euclidean Distance），直接計(jì)算時(shí)間軸上對(duì)應(yīng)點(diǎn)間的距離，算法簡單、快速，但它只能應(yīng)用于等長的時(shí)間序列，且對(duì)序列在時(shí)間軸上的偏移及序列突變敏感。動(dòng)態(tài)時(shí)間規(guī)整（Dynamic Time Warping，DTW）算法根據(jù)最小代價(jià)的時(shí)間彎曲路徑進(jìn)行匹配，對(duì)時(shí)間序列發(fā)生彎曲后的相似性度量具有很好的魯棒性。算法的時(shí)間復(fù)雜度高且序列在時(shí)間軸偏上偏移較大時(shí)容易產(chǎn)生病態(tài)路徑及匹配不準(zhǔn)確的問題。如圖1 歐幾里德距離與DTW距離對(duì)比圖。

1994 年，Berndt 和Clifford 首先把動(dòng)態(tài)時(shí)間彎曲距離引入到時(shí)間序列分類的問題中[3]。針對(duì)DTW 計(jì)算量大的問題，Huang 和Kinsner 提出一種調(diào)節(jié)窗口法[4]。Thanawin 等人提出一種在大數(shù)據(jù)量下的時(shí)間序列挖掘算法[5]。這些工作的前提都是比較時(shí)間序列的相似性。

圖1 歐式距離與DTW 距離對(duì)比圖

2 相關(guān)知識(shí)

2.1 動(dòng)態(tài)時(shí)間彎曲距離

動(dòng)態(tài)時(shí)間彎曲距離的主要思想為通過調(diào)整時(shí)間點(diǎn)之間的對(duì)應(yīng)關(guān)系，找出兩個(gè)任意長時(shí)間序列中數(shù)據(jù)之間的最佳匹配路徑，從而度量時(shí)間序列的相似性[6]。時(shí)間序列X=(x1，x2，…，xm)，Y=(y1，y2，…，yn) 長度分別為m、n。距離矩陣D由xi與yj的歐式距離的平方di，j=d(xi，yj)=(xi-yj)2構(gòu)成。在D中尋找一條彎曲路徑W=(w1,w2,…，wk)使得X與Y的匹配度最大。其中max(m,n)≤k≤m+n-1，wl=(i，j) 表示xi與yj匹配。wi的約束為：

（1）邊界約束

w1=(1，1)；wk=(m，n)

（2）單調(diào)性、連續(xù)性約束

wk=(ak，bk)；wk+1=(ak+1，bk+1)

其中0 ≤ak+1-ak≤1，0 ≤bk+1-bk≤1。

DTW路徑是D中滿足以上條件的最短路徑，如圖2：

最優(yōu)路徑的查找是通過動(dòng)態(tài)規(guī)劃來實(shí)現(xiàn)的[7]。定義累積矩陣R={r(i，j)}m，n來記錄最短路徑，即

實(shí)現(xiàn)算法的時(shí)間復(fù)雜度為O(mn)。

圖2 DTW 彎曲路徑示意圖

2.2 心電信號(hào)

心電信號(hào)是心肌的電活動(dòng)在體表的表現(xiàn)，包含了許多關(guān)于心臟疾病的信息。心電圖的一個(gè)周期的波形由P-QRS-T 波構(gòu)成[8]，其中QRS 波群是單個(gè)心拍中最顯著的特征。最典型心電圖如圖3 所示。

圖3 典型心電信號(hào)

ECG 信號(hào)已被證實(shí)是一種非平穩(wěn)信號(hào)，其可視化圖形是一種非參數(shù)曲線。由于信號(hào)微弱易受噪聲影響，病變種類多，個(gè)體差異大，分布不均衡，非穩(wěn)定并且以某種不規(guī)則的復(fù)雜方式波動(dòng)[9]等原因使得心電信號(hào)的相似性度量更加困難。目前對(duì)心電信號(hào)的研究主要有3大類[10]：（1）基于機(jī)器學(xué)習(xí)的方法，如文獻(xiàn)[11]提出基于高階累計(jì)量和希爾伯特基函數(shù)獲取同一信號(hào)的兩組特征集，分別訓(xùn)練得到兩個(gè)SVM 分類器，用加權(quán)投票法對(duì)分類器結(jié)果集成。（2）數(shù)據(jù)挖掘方法，如文獻(xiàn)[12]提出一種Swift-Rule 規(guī)則挖掘方法，針對(duì)不同種類的時(shí)間序列信號(hào)挖掘，自動(dòng)得出復(fù)雜的分類規(guī)則，通過對(duì)ECG 信號(hào)的挖掘，實(shí)現(xiàn)了正異常分類。（3）基于數(shù)學(xué)模型的方法，如隱馬爾科夫模型。

形態(tài)學(xué)的方法更符合人直觀的理解，由于起步晚，準(zhǔn)確率低目前的方法不盡如人意而使用較少[13]。

3 改進(jìn)DTW 算法

本文在研究總結(jié)已有算法不足基礎(chǔ)上提出改進(jìn)型DTW 算法，該算法首先遵循最大特征點(diǎn)優(yōu)先匹配原則，然后根據(jù)信號(hào)特征自適應(yīng)確定彎曲窗口的范圍。實(shí)驗(yàn)表明，算法在提高匹配精度的同時(shí)減少了運(yùn)算時(shí)間。

3.1 最大特征點(diǎn)優(yōu)先匹配原則

傳統(tǒng)的時(shí)間序列相似性度量算法將序列看作是靜態(tài)的，嚴(yán)格按照順序進(jìn)行匹配。ECG 信號(hào)可看作是動(dòng)態(tài)的時(shí)間序列，信號(hào)中一旦出現(xiàn)病變的波形則診斷為某種疾病。大量實(shí)驗(yàn)發(fā)現(xiàn)對(duì)曲線相似性度量精度影響最大的是曲線中特異性較大的點(diǎn)。心電信號(hào)中QRS 波群幅值高，斜率大是信號(hào)中最明顯的特征。病變的心電信號(hào)如室性心律失?；颊叩腝RS 波群要比正常QRS 波群寬大，但這種病變波并不在每個(gè)周期穩(wěn)定存在[14]，如圖4 序列1 中A 波和序列2 中B 波為病變信號(hào)，也是特征最明顯的波群（本文序列橫軸使用采樣點(diǎn)個(gè)數(shù)表示，因?yàn)樵谝欢ú蓸宇l率下，采樣點(diǎn)個(gè)數(shù)與時(shí)間存在對(duì)應(yīng)關(guān)系）。如直接運(yùn)用DTW 路徑計(jì)算將出現(xiàn)誤匹配，如圖5。

圖4 兩例室性心律失常心電圖

圖5 錯(cuò)誤匹配結(jié)果

最大特征點(diǎn)優(yōu)先匹配原則是將序列1 中A點(diǎn)平移至與B點(diǎn)橫軸相當(dāng)?shù)奈恢?，再?jì)算DTW 距離。

3.2 自適應(yīng)彎曲窗口約束

臨床上廣泛使用的12 導(dǎo)聯(lián)心電圖機(jī)可記錄十幾秒的心電數(shù)據(jù)。若按2.1 小節(jié)中傳統(tǒng)算法計(jì)算，當(dāng)彎曲路徑偏離對(duì)角線較大時(shí)會(huì)產(chǎn)生病態(tài)匹配，針對(duì)該問題的改進(jìn)算法中加入彎曲窗口（Warping Window），可改善病態(tài)彎曲并輕微減少算法的運(yùn)行時(shí)間[15]，但對(duì)匹配的精度會(huì)產(chǎn)生影響，不同情況下彎曲窗口的范圍是難以確定的。最常見的彎曲窗口約束如圖6。

圖6 兩種常見的彎曲窗口約束

本文提出一種自適應(yīng)彎曲窗口約束，該方法根據(jù)不同ECG 信號(hào)QRS 波群位置可自動(dòng)調(diào)整約束窗口范圍，不僅具有普遍適應(yīng)性，還能夠降低計(jì)算時(shí)間。

研究發(fā)現(xiàn)，兩條序列的距離矩陣D中存在一些間距不等、顏色深淺不同的橫豎條帶狀平行線（三維圖中是平面），這些平行線構(gòu)成了D中大小不一的矩形，而彎曲路徑W必定經(jīng)過D的對(duì)角線上的各小矩形對(duì)角點(diǎn)，由此用這些小矩形將W分成若干段，除起止段外每段的W完全位于所在的矩形中，如圖7。

圖7 仰角為172°方位角為32°時(shí)的D 與W

這些平行線正是序列中信號(hào)特異性較大的位置也即各QRS 波群位置，W經(jīng)過對(duì)角線上矩陣的對(duì)角點(diǎn)從事實(shí)上證明了最大特征匹配的正確性。由此只需計(jì)算D中位于對(duì)角線上的矩陣內(nèi)的值，而忽略其他部分，從而減少運(yùn)算時(shí)間。對(duì)于起止段的約束如下：

W起點(diǎn)w1=(1，1)，起點(diǎn)段的右上角點(diǎn)為兩序列的第一個(gè)R波所在位置構(gòu)成的橫縱坐標(biāo)。

W終點(diǎn)wk=(m，n)，終點(diǎn)段的左下角點(diǎn)為兩序列最后一個(gè)R波所在位置構(gòu)成的橫縱坐標(biāo)。如圖8 自適應(yīng)窗口為圖中白色部分，紅色曲線為動(dòng)態(tài)彎曲路徑。匹配效果如圖9。

圖8 自適應(yīng)約束窗口

4 實(shí)驗(yàn)結(jié)果

為驗(yàn)證算法有效性，本文選取中國心血管數(shù)據(jù)庫（CCDD）中室性心律失常部分ECG 信號(hào)實(shí)驗(yàn)，從最短路徑的計(jì)算精度及算法消耗時(shí)間方面對(duì)傳統(tǒng)算法與本文提出算法進(jìn)行比較。如表1 所示。Len(t)代表t長度，Dis代表傳統(tǒng)算法的最短DTW 距離，Th_Dis代表本文算法的最短DTW 距離，T與Th_T分別代表傳統(tǒng)算法與本文算法的時(shí)間消耗。

圖9 匹配效果圖

表1 實(shí)驗(yàn)性能比較

圖10 時(shí)間消耗對(duì)比圖

圖11 DTW 距離對(duì)比圖

實(shí)驗(yàn)表明改進(jìn)算法的準(zhǔn)確度更高，隨著序列長度增加，算法的時(shí)間消耗優(yōu)勢(shì)更加明顯。

5 結(jié)束語

ECG 信號(hào)由于維數(shù)高、數(shù)據(jù)量大、變化多，直接進(jìn)行相似性度量不能滿足實(shí)際應(yīng)用需求。本文對(duì)時(shí)間序列相似性度量的傳統(tǒng)算法進(jìn)行了深入研究，在此基礎(chǔ)上提出最大特征優(yōu)先匹配原則和自適應(yīng)約束窗口法，進(jìn)一步提高了運(yùn)算精度的同時(shí)減少了算法時(shí)間復(fù)雜度，為時(shí)間序列的分類、檢索提供了新的思路。

[1] 李海林，郭崇慧.時(shí)間序列數(shù)據(jù)挖掘中特征表示與相似性度量研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2013，30（5）：1285-1291.

[2] Danielsson P.Euclidean distance mapping[J].Computer Graphics and Image Processing，1980，14：227-248.

[3] Berndt D，Clifford J.Using dynamic time warping to find patterns in time series[C]//AAAI-94 Workshop on Knowledge Discovery in Databases，Seattle，WA，USA，1994：229-248.

[4] Huang B，Kinsner W.ECG frame classification using dynamic time warping[C]//Electrical and Computer Engineering，IEEE CCECE 2002，Canadian Conference，2002，2：1105-1110.

[5] Rakthanmanon T，Campana B，Mueen A.Searching and mining trillions of time series subsequences under dynamic time warping[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York，NY，USA：ACM，2012：262-270.

[6] 李海林，郭崇慧，楊麗彬.基于分段聚合時(shí)間彎曲距離的時(shí)間序列挖掘[J].山東大學(xué)學(xué)報(bào)：工學(xué)版，2011，41（5）：57-62.

[7] Eamonn J，Michael J.Derivative dynamic time warping[C]//The First SIAM International Conference on Data Mining.Washington：IEEE，2001：1-11.

[8] Yun-Chi Yeha C，Wang Wen-June.QRS complexes detection for ECG signal：The difference operation method[J].Computer Methods and Programs in Biomedicine，2008，91：245-254.

[9] 楊小冬，寧新寶，何愛軍，等.基于多尺度的人體ECG 信號(hào)質(zhì)量指數(shù)譜分析[J].物理學(xué)報(bào)，2008，57（3）：1514-1521.

[10] 張嘉偉.心電圖形態(tài)特征的識(shí)別及其在分類中的作用研究[D].上海：華東師范大學(xué)，2012.

[11] Osowski S，Hoai L T，Markiewiez T.SVM-based expert system for reliable heartbeat recognition[J].IEEE Transactions on Biomedical Engineering，2004，51（4）：582-589.

[12] Fisch D，Gruber T，Sick B.SwiftRule：mining comprehensible classification rules for time series analysis[J].IEEE Transactions on Knowledge and Data Engineering，2011，23（5）：774-787.

[13] 董軍，徐淼，詹聰明，等.心電圖識(shí)別與分類：方法、問題和新途徑[J].生物醫(yī)學(xué)工程學(xué)雜志，2007，24（6）：1224-1229.

[14] Davis D.Quick and accurate 12-lead ECG interpretation[M].李立志，史大卓，譯.北京：科學(xué)技術(shù)文獻(xiàn)出版社，2004：421-424.

[15] 陳乾，胡谷雨.一種新的DTW 最佳彎曲窗口學(xué)習(xí)方法[J].計(jì)算機(jī)科學(xué)，2012，39（8）：191-195.