改進DTW 算法的心電信號相似性度量

涂 輝，劉 麗，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 引言

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

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

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

圖1 歐式距離與DTW 距離對比圖

2 相關(guān)知識

2.1 動態(tài)時間彎曲距離

動態(tài)時間彎曲距離的主要思想為通過調(diào)整時間點之間的對應(yīng)關(guān)系，找出兩個任意長時間序列中數(shù)據(jù)之間的最佳匹配路徑，從而度量時間序列的相似性[6]。時間序列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)路徑的查找是通過動態(tài)規(guī)劃來實現(xiàn)的[7]。定義累積矩陣R={r(i，j)}m，n來記錄最短路徑，即

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

圖2 DTW 彎曲路徑示意圖

2.2 心電信號

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

圖3 典型心電信號

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

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

3 改進DTW 算法

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

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

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

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

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

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

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

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

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

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

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

圖7 仰角為172°方位角為32°時的D 與W

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

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

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

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

4 實驗結(jié)果

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

圖9 匹配效果圖

表1 實驗性能比較

圖10 時間消耗對比圖

圖11 DTW 距離對比圖

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

5 結(jié)束語

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

[1] 李海林，郭崇慧.時間序列數(shù)據(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] 李海林，郭崇慧，楊麗彬.基于分段聚合時間彎曲距離的時間序列挖掘[J].山東大學(xué)學(xué)報：工學(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 信號質(zhì)量指數(shù)譜分析[J].物理學(xué)報，2008，57（3）：1514-1521.

[10] 張嘉偉.心電圖形態(tài)特征的識別及其在分類中的作用研究[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] 董軍，徐淼，詹聰明，等.心電圖識別與分類：方法、問題和新途徑[J].生物醫(yī)學(xué)工程學(xué)雜志，2007，24（6）：1224-1229.

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

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