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

涂 輝，劉 麗，2，張正金

TU Hui1,LIU Li1，2,ZHANG Zhengjin1

1.江南大學 物聯網工程學院，江蘇 無錫214122

2.無錫市第四人民醫院 信息科，江蘇 無錫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 引言

時間序列是一類常見且與時間相關的高維數據，也是數據挖掘領域中主要的研究對象，廣泛存在于金融、醫學、氣象、網絡安全等領域中[1]。時間序列相似性度量是時間序列分析中的重要任務之一，對時間序列的分類、聚類、檢索具有重要意義。

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

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

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

2 相關知識

2.1 動態時間彎曲距離

動態時間彎曲距離的主要思想為通過調整時間點之間的對應關系，找出兩個任意長時間序列中數據之間的最佳匹配路徑，從而度量時間序列的相似性[6]。時間序列X=(x1，x2，…，xm)，Y=(y1，y2，…，yn) 長度分別為m、n。距離矩陣D由xi與yj的歐式距離的平方di，j=d(xi，yj)=(xi-yj)2構成。在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）單調性、連續性約束

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

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

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

最優路徑的查找是通過動態規劃來實現的[7]。定義累積矩陣R={r(i，j)}m，n來記錄最短路徑，即

實現算法的時間復雜度為O(mn)。

圖2 DTW 彎曲路徑示意圖

2.2 心電信號

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

圖3 典型心電信號

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

形態學的方法更符合人直觀的理解，由于起步晚，準確率低目前的方法不盡如人意而使用較少[13]。

3 改進DTW 算法

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

3.1 最大特征點優先匹配原則

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

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

圖5 錯誤匹配結果

最大特征點優先匹配原則是將序列1 中A點平移至與B點橫軸相當的位置，再計算DTW 距離。

3.2 自適應彎曲窗口約束

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

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

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

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

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

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

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

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

圖8 自適應約束窗口

4 實驗結果

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

圖9 匹配效果圖

表1 實驗性能比較

圖10 時間消耗對比圖

圖11 DTW 距離對比圖

實驗表明改進算法的準確度更高，隨著序列長度增加，算法的時間消耗優勢更加明顯。

5 結束語

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

[1] 李海林，郭崇慧.時間序列數據挖掘中特征表示與相似性度量研究綜述[J].計算機應用研究，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].山東大學學報：工學版，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 信號質量指數譜分析[J].物理學報，2008，57（3）：1514-1521.

[10] 張嘉偉.心電圖形態特征的識別及其在分類中的作用研究[D].上海：華東師范大學，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].生物醫學工程學雜志，2007，24（6）：1224-1229.

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

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