# A Fast Method for Abrupt Change Detection from Large-Scale Electrocardiogram (ECG) Time Series

Jin-Peng Qi, Qing Zhang, Jie Qi, Ying Zhu

► To cite this version:

Jin-Peng Qi, Qing Zhang, Jie Qi, Ying Zhu. A Fast Method for Abrupt Change Detection from Large-Scale Electrocardiogram (ECG) Time Series. 15th International Conference on Informatics and Semiotics in Organisations (ICISO), May 2014, Shanghai, China. pp.420-429, 10.1007/978-3-642-55355-4_44. hal-01350952

HAL Id: hal-01350952

https://inria.hal.science/hal-01350952

Submitted on 2 Aug 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Fast Method for Abrupt Change Detection from Large-Scale Electrocardiogram (ECG) Time Series

Jin-Peng Qi¹, Qing Zhang², Jie Qi³, and Ying Zhu⁴

¹College of Information Science & Technology, Donghua University, Shanghai 201620, P.R.
China

¹qipengkai@dhu.edu.cn, ³jieqi@dhu.edu.cn

²Hunter New England Health, Royal North Shore Hospital, NEW South Wales, Australia

⁴ying.zhu@hnehealth.nsw.gov.au

³E-Health Research, ICT Center, Csiro, PO Box 350, Brisbane, QLD4060, Australia

²qing.zhang@csiro.au

**Abstract.** In previous work, we proposed a promising method, named HWBST, for Change-Point (CP) detection from time series. However, the performance of HWBST is affected partly by the search criteria in terms of Binary Search Tree (BST). In this paper, we propose an improved method for fast CP detection from large-scale ECG time series, based on multi-level Haar Wavelet and Ternary Search Tree (HWTST, for short). In this method, we construct a ternary search tree termed TSTcD from a diagnosed time series by using multi-level HW. Then, we implement fast detection abrupt change from root to leaf nodes in TSTcD, by introducing two search criteria in terms of the data fluctuation in the left, right, and virtual middle branches of TSTcD. Based on the assembled and abnormal ECG samples, we evaluate the proposed HWTST by comparing with HWBST, KS, and T methods. The results show that the proposed HWTST is a faster and more efficient than HWBST, KS and T in terms of the computation time, error, accuracy, and distance of e.c.d.f.

**Keywords:** CP detection, ECG Time series, Large-Scale, Haar Wavelet (HW), Ternary Search Tree (TST).

## 1 Introduction

Currently, Change-Point (CP) detection has attracted considerable attention in the fields of data mining and statistics. CP detection has been widely studied in many real-world problems, such as atmospheric and financial analysis [1], intrusion detection in computer network [2], signal segmentation in data stream [3], as well as fault detection in engineering system [2, 4]. In the past decade, Wavelet Transform (WT), and its revised approaches have emerged as an important mathematical tool for analyzing time series [5-10]. WT is a promising approach for CP detection. It has found applications in anomaly detection, time series prediction, image processing, and noise reduction [6, 10-12]. WT can represent general functions at different scales and posi-
tions in a versatile and sophisticated manner, so the data distribution features can be
easily extracted from different time or space scales [12, 13]. As a simple WT, Haar
Wavelet (HW), owns some attracting features including fast for implementation and
able to analyze the local feature. HW is very useful to find discontinuity and high
frequency change in time series, so it is a potential candidate in modern electrical and
computer engineering applications, such as signal and image compression, as well as
abnormality detection from time series [14, 15].

Previously, we proposed a HWBST method for fast CP detection [16]. HWBST is a promising method for detecting abrupt change from large-scale time series. However, the performance of HWBST is affected partly by binary search criteria, especially when abrupt change occurs near the middle boundary of BST. To resolve this problem, in this paper, we propose an improved method for fast CP detection from large-scale time series, named HWTST, based on multi-level HW and ternary search tree. In the proposed method, a ternary search tree (TST), named TSTcD is built based on a binary search tree, TcD derived from a diagnosed time series, by adding a virtual middle sub-tree; and then abrupt change is detected from TSTcD in terms of two search criteria. To evaluate the proposed method, we apply the HWTST, HWBST, KS, and T to detect abrupt change from both the assembled and the abnormal ECG samples. The detailed HWTST method is implemented as follows.

2 Method

2.1 Definition and assumption [16]

Suppose $Z = \{z_1, \dots, z_N\}$ is a diagnosed time series, we observe

$$
Z = f(i/n) + X, i = 1, \dots, N, \tag{1}
$$

where $X = \{x_i\}_{i=1,...,N}$ are discrete and centred i.i.d. random variables, and $f$ is a noisy mean signal with unknown distribution.

**Definition 1:** We define the data fluctuation between two adjacent segments in Z as,

$$
D_{mn}(c) = \sup_{1 \le L, R \le N} \left| \frac{1}{m} \sum_{L=a}^{c} z_L - \frac{1}{n} \sum_{R=c+1}^{b} z_R \right|, \quad (2)
$$

where $Z = \{Z_L, Z_R\}$, $Z_L = \{z_a, \dots, z_c\}$, $Z_R = \{z_{c+1}, \dots, z_b\}$, and $m=c-a$, $n=b-c-1$, and $m+n \le N$. If a change point $c$ occurs in $Z$, there exists a value $c$ satisfies $D_{mn}(c) > \delta$, $z_c \in [z_1, z_N]$, and $\delta \in R$.

Hypotheses:

(1) $H_0$: if $D_{mn}(c) \le \delta$, no abrupt change occurs in $Z$.

(2) $H_1$: if $D_{mn}(c) > \delta$, abrupt change occurs in $Z$.

where $\delta \in R$ is a threshold of data fluctuation in a time series Z within an identical distribution. We wish to test $H_0$ against $H_1$ from observations. Thereafter, we as-
assume that the number, the location, and the size of the function f are unknown. However, the upper bound of data fluctuation δ is supposed to be known.

## 2.2 Multi-level HW

Generally, as shown in Fig.1, by using multi-level HW, a discrete time-series signal $Z=\{z_1, z_2, ..., z_N\}$, can be decomposed into the $k^{th}$-level trend $cA^k$, and $k$ level fluctuations, i.e., $cD^1, cD^2, ..., cD^k, k=1, 2, ..., \log_2 N$. The $k$-level HW is the mapping $H_k$ defined by [8],

$$Z \xrightarrow{H_k} (cA^k | cD^1 | cD^{k-1} | ... | cD^2 | cD^1), \quad (3)$$

<figure><img src="image_2.png" /><figcaption>Fig. 1. The diagram of multi-level HW for a time-series signal Z, it is composed of k-level cA and cD vectors, i.e., the average and difference coefficients vectors.</figcaption></figure>

Suppose a diagnosed sample $Z=\{z_1, z_2, ..., z_N\}$ is decomposed by means of multi-level HW, we can represent the approximation and detail coefficient vectors by the following matrices, namely McA and McD:

$$McA = \begin{bmatrix} cA^0 \\ cA^1 \\ \vdots \\ cA^k \\ \vdots \\ cA^M \end{bmatrix} = \begin{bmatrix} cA_{0,1} & \cdots & \cdots & \cdots & cA_{0,N} \\ cA_{1,1} & \cdots & \cdots & \cdots & cA_{1,N/2} \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ cA_{k,1} & \cdots & cA_{k,j} & & \cdots \\ \vdots & & \vdots & & \vdots \\ cA_{M,1} & & & & & \cdots \\ \vdots & & & & & \vdots \\ cA_{M,N} & & & & & \cdots \end{bmatrix} \quad McD = \begin{bmatrix} cD^0 \\ cD^1 \\ \vdots \\ cD^k \\ \vdots \\ cD^M \end{bmatrix} = \begin{bmatrix} cD_{0,1} & \cdots & \cdots & \cdots & cD_{0,N} \\ cD_{1,1} & \cdots & \cdots & \cdots & cD_{1,N/2} \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ cD_{k,1} & \cdots & cD_{k,j} & & \cdots \\ \vdots & & \vdots & & \vdots \\ cD_{M,1} & & & & & \cdots \end{bmatrix}, \quad (4)$$

where $cA^0 = cD^0 = Z = \{z_1, z_2, ..., z_N\}$, $0 \le k \le M = \log_2 N$, and $1 \le j \le N/2^k$.

## 2.3 Overview of HWTST method

The scheme of integrated HWTST method (Fig.2) is composed of three parts. First, a ternary search tree, TSTcD, is constructed from a diagnosed time-series Z by multi-level HW method. Second, abrupt CP is detected from root to leaf nodes in TSTcD, in
terms of two search criteria. Last, the proposed method is evaluated by comparing with HWBST, KS, and T methods.

<figure><img src="image_3.png" /><figcaption>Fig. 2. The scheme of the integrated HWTST framework, it includes three parts: TSTcD construction, CP detection from TSTcD in terms of two ternary search criteria, and evaluation for HWTST method.</figcaption></figure>

## 2.4 Construction of TSTcD

First, we build a binary tree TcD, in terms of McD. As shown in Fig.3, we deal the element cD$_{k,j}$ in McD as the root, the other elements as non-leaf left and right child nodes, and the original Z= {z₁, z₂, ..., zN} as N leaf nodes, respectively. Then, a virtual middle-child node termed cD$_{k,j;M}$ is added into non-leaf parent node cD$_{k,j}$ in TSTcA.

## 2.5 CP Detection from TSTcD

**Definition 2:** Suppose the current non-leaf node cD$_{k,j}$ is selected in TSTcD, with its left, virtual middle, and right child non-leaf node, namely cD$_{k,jL}$, cD$_{k,jM}$, and cD$_{k,jR}$, respectively. To measure the data fluctuation in different segments of Z, three statistic variables, D$_{k,jL}$, D$_{k,jM}$, and D$_{k,jR}$ are defined as:

$$D_{k,j,L} = |cD_{k,j,L}| = \left| \frac{1}{(\sqrt{2})^{k-1}} \left( \sum_{L=a}^{uM-1} z_L - \sum_{R=aM}^{c} z_R \right) \right|, \quad (16)$$
<figure><img src="image_4.png" /><figcaption>Fig. 3. The scheme of TSTcD construction, the virtual non-leaf middle-child node is added.</figcaption></figure>

$$D_{k,j;R} = |cD_{k,j;R}| = \left| \frac{1}{(\sqrt{2})^{k}(k-1)} \left( \sum_{L=c+1}^{bM} z_L - \sum_{R=bM+1}^{b} z_R \right) \right|, \quad (17)$$

$$D_{k,j;M} = |cD_{k,j;M}| = \left| \frac{1}{(\sqrt{2})^{k}(k-1)} \left( \sum_{L=aM}^{c} z_L - \sum_{R=c+1}^{bM} z_R \right) \right|, \quad (18)$$

where $a = 2^k(j-1)+1$, $b = 2^k * j$, and $c = 2^k(j-1)+2^{k-1}$; $aM = 2^{k-1}(2j-2)+2^{k-2}+1$, and $bM = 2^{k-1}(2j-1)+2^{k-2}$; $1 \le j \le N/2^k$, and $2 \le k \le \log_2 N$. Thereafter, we can introduce the first search criterion in terms of the data fluctuation defined above.

**Criterion 1:** Suppose the current non-leaf node $cD_{k,j}$ is selected in TSTcD, $2 \le k \le \log_2 N$,

(a) If $(\max(D_{k,j,L}, D_{k,j,R}, D_{k,j,M}) = D_{k,j,L})$ holds true, then the left-child node $cD_{k,j,L}$ in TSTcD, is selected to be involved into the current search path;

(b) If $(\max(D_{k,j,L}, D_{k,j,R}, D_{k,j,M}) = D_{k,j,R})$ holds true, then the right-child node $cD_{k,j,R}$ in TSTcD, is selected to be involved into the current search path;

(c) If $(\max(D_{k,j,L}, D_{k,j,R}, D_{k,j,M}) = D_{k,j,M})$ holds true, then the virtual middle-child node $cD_{k,j,M}$ in TSTcD, is selected to be involved into the current search path.

In addition, we introduce another criterion to deal with the last leaf node in TSTcD, and then decide whether the selected leaf node is the potential CP or not. We define the second search criterion in terms of the data fluctuation in the last leaf node level as follows.

**Criterion 2:** Suppose the current selected non-leaf node is $cD_{k,j}$, $k=1$, with left, and right-child leaf node, $cD_{0,2j}$, and $cD_{0,2j}$, namely, $z_{2j}$, and $z_{2j}$,

(a) If $(|cD_{k,j}| > \sqrt{2}\alpha)$ is satisfied, then the right-child leaf node $cD_{0,2j}$, i.e., $z_{2j}$ is selected, and dealt as the estimated CP in $Z$;

(b) If $(|cD_{k,j}| > \sqrt{2}\alpha)$ is satisfied, then there is no abrupt change detected from $Z$.
Based on two search criteria above, a fast CP detection is implemented, and then an
estimated CP can be detected from root to leaf-nodes in TSTcD.

3 Results

To verify the performance of the proposed method further, we apply HWKS, and KS, HW, and T methods, to detect abrupt change from ECG time series provided by PhysioBank. In ECG experiments, we design the diagnosed ECG samples from different ECG datasets, including the MIT-BIH Normal Sinus Rhythm Database (NSRDB) [17], MIT-BIH Noise Stress Test Database (NSTDB) [18], and MIT-BIH Malignant Ventricular Arrhythmia Database (MVADB) [19].

**3.1 CP detection from assembled ECG samples**

First, we select a normal ECG dataset, 16265m from NSRDB, and an abnormal ECG dataset, 118e00m from NSTDB. Specifically, we take the normal ECG segment of size *m* as X<sub>m</sub>, and the abnormal segment of size *n* as Y<sub>n</sub>, respectively, and then assemble the diagnosed ECG sample Z={X<sub>1</sub>,..., X<sub>m</sub>, Y<sub>1</sub>,..., Y<sub>n</sub>}. Then, a single CP test position is arranged at the middle part in each diagnosed ECG sample. The selected results are shown in Fig 2, and the results of the computation time, error and accuracy for all ECG samples of size from 2<sup>7</sup> to 2<sup>14</sup> are summarized in Table 1.

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>
<caption>**Fig. 1.** The results of CP detection from the assembled ECG time series Z1-Z4. (A1)-(A4) the assembled Z1-Z4; (B1)-(B4),(C1)-(C4) , (D1)-(D4), and (E1)-(E4) the e-CP detected from Z1-Z4, by HWTST, HWBST, KS, and T, respectively; (F1)-(F4) the diagram analysis for the computation time, (G1)-(G4) the error of e-CP, and (H1)-(H4) the accuracy for HWTST, HWBST, KS, and T, respectively. In histograms (F)-(H), '1', '2', '3', and '4' stands for HWTST, HWBST, KS, and T, respectively.</caption>

<table><caption>Table 1. The results of CP detection from the assembled ECG samples.</caption><thead><tr><th rowspan="2">M</th><th rowspan="2">Z</th><th rowspan="2">Size, N</th><th>2^7</th><th>2^8</th><th>2^9</th><th>2^10</th><th>2^11</th><th>2^12</th><th>2^13</th><th>2^14</th><th rowspan="2">Mean</th></tr><tr><th>2^6</th><th>2^7</th><th>2^8</th><th>2^9</th><th>2^10</th><th>2^11</th><th>2^12</th><th>2^13</th></tr></thead><tbody><tr><td rowspan="4">Time</td><td>HWTST</td><td>.0050</td><td>.0060</td><td>.0060</td><td>.0060</td><td>.0060</td><td>.0060</td><td>.0070</td><td>.0090</td><td>.0063</td><td></td></tr><tr><td>HWBST</td><td>.0060</td><td>.0060</td><td>.0070</td><td>.0080</td><td>.0080</td><td>.0100</td><td>.0140</td><td>.0240</td><td>.0103</td><td></td></tr><tr><td>KS</td><td>.0100</td><td>.0130</td><td>.0200</td><td>.0440</td><td>.0119</td><td>.3910</td><td>1.420</td><td>5.431</td><td>.9176</td><td></td></tr><tr><td>T</td><td>.0300</td><td>.0450</td><td>.0740</td><td>.1390</td><td>.2870</td><td>.6750</td><td>1.653</td><td>4.461</td><td>.9205</td><td></td></tr><tr><td rowspan="4">Error</td><td>HWTST</td><td>9</td><td>8</td><td>8</td><td>8</td><td>31</td><td>8</td><td>8</td><td>8</td><td>11</td><td></td></tr><tr><td>T</td><td>63</td><td>63</td><td>15</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>18</td><td></td></tr><tr><td>KS</td><td>15</td><td>15</td><td>15</td><td>15</td><td>15</td><td>90</td><td>52</td><td>70</td><td>36</td><td></td></tr><tr><td>HWBST</td><td>62</td><td>4</td><td>70</td><td>198</td><td>988</td><td>1194</td><td>388</td><td>8074</td><td>1372</td><td></td></tr><tr><td rowspan="4">Accuracy</td><td>HWTST</td><td>.9297</td><td>.9688</td><td>.9844</td><td>.9922</td><td>.9849</td><td>.9980</td><td>.9990</td><td>.9995</td><td>.9821</td><td></td></tr><tr><td>KS</td><td>.8828</td><td>.9414</td><td>.9707</td><td>.9854</td><td>.9927</td><td>.9780</td><td>.9937</td><td>.9957</td><td>.9675</td><td></td></tr><tr><td>T</td><td>.5078</td><td>.7539</td><td>.9707</td><td>.9990</td><td>.9995</td><td>.9998</td><td>.9999</td><td>.9999</td><td>.9038</td><td></td></tr><tr><td>HWBST</td><td>.5156</td><td>.9844</td><td>.8633</td><td>.8066</td><td>.5176</td><td>.7085</td><td>.9526</td><td>.5072</td><td>.7320</td><td></td></tr></tbody></table>

In this assembled ECG experiments, the results of CP detection illustrated in Fig.2, and Table 1 show that, the proposed HWTST can estimate CP position efficiently, and then distinguish the normal and abnormal segments from the assembled ECG samples with faster, smaller error and higher accuracy than HWBST, KS, and T. For HWBST, although faster than KS, and T, it has the biggest error and the lowest accuracy in all four methods. For KS, although slightly bigger error than T, it is faster than T, and has smaller error and higher accuracy than HWBST. For T, it has smaller error and higher accuracy than HWBST, whereas, it needs the longest computation time in all methods. These results indicate the proposed HWTST is more sensitive and efficient than HWBST, for CP detection at the middle boundary. Especially, it has the shortest computation time, the smallest error, and the highest accuracy in all four methods.

## 3.2 CP Detection from abnormal ECG time series

To verify the performance of the proposed method further, we apply HWTST, HWBST, KS, and T to analyze the abnormal ECG time series directly. In this part, we select the abnormal ECG segment from 615m in the MVADB, i.e., $Z=\{Y_n\}=(y_1, ..., y_n)$, as a diagnosed ECG sample. To some extent, the distance of e.c.d.f can partly reflect the statistic fluctuation. Therefore, we take this variable as an indicator of the data fluctuation between two adjacent ECG segments divided by the estimated CP (e-CP) position. The selected results of CP detection are plotted in Fig.2, and the results for all abnormal ECG samples, including the e-CP position, computation time, and the variance of e.c.d.f are summarized in Table 2.

For abnormal ECG samples Z1-Z6 of size N from $2^{10}$ to $2^{15}$, the results show that the proposed HWTST can detect the abrupt change position, and then divide the original ECG sample into two adjacent parts, with the shortest computation time in four methods; and it has bigger distance of e.c.d.f than HWBST, and T methods. For
HWBST, although faster than KS, and T, it has the smallest variance of e.c.d.f in all four methods. For KS, it can detect CP with the maximal distance of e.c.d.f, whereas, it needs longer computation time than HWTST, HWBST, especially when ECG sample size is bigger. For T, it needs the longest averaged computation time in all four methods, although it has bigger variance of e.c.d.f than HWBST. These results show that HWTST can capture abrupt change position from the diagnosed ECG samples more quickly and efficiently than HWBST, KS, and T. On the other hand, the detected CP is very useful to find a critical time from the diagnosed ECG time series, where a patient might encounter an important conversion between two different states of health. Therefore, HWTST is very meaningful for inspecting and diagnosing different states of health from diagnosed ECG time series more quickly and efficiently.

<figure><img src="image_9.png" /></figure>
**Fig. 2.** The results of CP detection from abnormal ECG time series of size for 2^10 to 2^15. (A1)-(A6) the abnormal ECG sample Z1-Z6; (B1)-(B6), (C1)-(C6), (D1)-(D6), (E1)-(E6) the e.c.d.f derived from two adjacent ECG segments in Z1-Z6, by HWTST, HWBST, KS, and T, respectively; (F1)-(F6) the diagram analysis of the distance of e.c.d.f, and (G1)-(G6) the computation time of HWKS, KS, HW, and T in Z1-Z6, respectively. In histograms (F)-(H), '1', '2', '3', and '4' stands for HWTST, HWBST, KS, and T, respectively.

<table><caption>Table 2. The results of CP detection from the abnormal ECG samples.</caption><thead><tr><th>Z<br>M</th><th>Size, N</th><th>2^10</th><th>2^11</th><th>2^12</th><th>2^13</th><th>2^14</th><th>2^15</th><th>Mean</th></tr></thead><tbody><tr><td rowspan="4">e-CP</td><td>HWTST</td><td>630</td><td>1478</td><td>3448</td><td>1520</td><td>9503</td><td>22640</td><td>NA</td></tr><tr><td>HWBST</td><td>614</td><td>1437</td><td>3804</td><td>1863</td><td>16167</td><td>27054</td><td>NA</td></tr><tr><td>KS</td><td>813</td><td>1153</td><td>3237</td><td>2164</td><td>8610</td><td>22361</td><td>NA</td></tr><tr><td>T</td><td>66</td><td>65</td><td>4036</td><td>8190</td><td>1</td><td>1</td><td>NA</td></tr><tr><td rowspan="4">Time</td><td>HWTST</td><td>.0060</td><td>.0060</td><td>.0070</td><td>.0060</td><td>.0090</td><td>.0140</td><td>.0080</td></tr><tr><td>HWBST</td><td>.0080</td><td>.0090</td><td>.0100</td><td>.0140</td><td>.0200</td><td>.0350</td><td>.0160</td></tr><tr><td>KS</td><td>.0430</td><td>.1320</td><td>.4100</td><td>1.409</td><td>5.294</td><td>20.46</td><td>4.625</td></tr><tr><td>T</td><td>.1450</td><td>.3170</td><td>7.440</td><td>1.855</td><td>4.685</td><td>13.02</td><td>3.461</td></tr><tr><td rowspan="3">Variance<br>of e.c.d.f</td><td>KS</td><td>.6260</td><td>.4919</td><td>.4991</td><td>.3456</td><td>.1909</td><td>.1632</td><td>.3861</td></tr><tr><td>HWTST</td><td>.1944</td><td>.3750</td><td>.2916</td><td>.1941</td><td>.2475</td><td>.1297</td><td>.2387</td></tr><tr><td>T</td><td>.6770</td><td>.5811</td><td>.0079</td><td>0</td><td>0</td><td>0</td><td>.2110</td></tr><tr><td></td><td>HWBST</td><td>.0983</td><td>.3249</td><td>.1786</td><td>.1616</td><td>.0496</td><td>.0162</td><td>.1382</td></tr></tbody></table>

# 4 Conclusion

In this paper, based on multi-level HW and ternary search tree, an improved method, named HWTST, is proposed for fast CP detection from large-scale ECG time series. In the proposed HWTST method, a ternary search tree, TSTcD, is built by adding a virtual middle-child sub-tree into TcD, which is derived from a diagnosed time series Z; and two search criteria are defined in terms of the data fluctuation in TSTcD. Then, an abrupt change is detected from root to leaf nodes of TSTcD in terms of two search criteria. Comparing with previous HWBST, KS, and T methods, the results show that the proposed HWTST is more efficient for fast detection CP from large-scale ECG time series, due to the shortest computation time, the smallest error, the highest accuracy in all four methods, and bigger variance of e.c.d.f than HWBST and T. In addition, HWTST has better performance than HWBST, especially when abrupt change occurs near the middle boundary.

**Acknowledgment:** I would like to thank my supervisor Prof. Qing. Zhang and Prof. Mohan Karunanithi in the Australia E-Health Research Centre for their assistances, supports and advices for this paper. This paper is supported by National Natural Science Foundation of China (No.61104154), and the Fundamental Research Funds for the Central Universities.

# Reference

1. R. J. Bolton and D. J. Hand, "Statistical fraud detection: A review," *Statistical Science*, pp. 235-249, 2002.

2. K. Yamanishi, et al., "On-line unsupervised outlier detection using finite mixtures with discounting learning algorithms," *Data Mining and Knowledge Discovery*, vol. 8, pp. 275-300, 2004.
3. M. E. Basseville and I. V. Nikiforov, "Detection of abrupt changes: theory and application," 1993.

4. U. Murad and G. Pinkas, "Unsupervised profiling for identifying superimposed fraud," in *Principles of Data Mining and Knowledge Discovery*, ed: Springer, 1999, pp. 251-261.

5. F. Gustafsson, *Adaptive filtering and change detection* vol. 1: Wiley New York, 2000.

6. V. Alarcon-Aquino and J. A. Barria, "Anomaly detection in communication networks using wavelets," *IEE Proceedings-Communications*, vol. 148, pp. 355-362, 2001.

7. M. Khalil and J. Duchêne, "Detection and classification of multiple events in piecewise stationary signals: comparison between autoregressive and multiscale approaches," *Signal processing*, vol. 75, pp. 239-251, 1999.

8. M. Kobayashi, "Wavelets and their applications in industry," *Nonlinear Analysis: Theory, Methods & Applications*, vol. 47, pp. 1749-1760, 2001.

9. D. B. Percival and A. T. Walden, *Wavelet methods for time series analysis* vol. 4: Cambridge University Press, 2006.

10. M. Salam and D. Mohamad, "Segmentation of Malay Syllables in connected digit speech using statistical approach," *International Journal of Computer Science and Security*, vol. 2, pp. 23-33, 2008.

11. J. Qi, et al., "Kinetic theory approach to modeling of cellular repair mechanisms under genome stress," *PloS one*, vol. 6, p. e22228, 2011.

12. V. S. Tseng, et al., "Segmentation of time series by the clustering and genetic algorithms," in *Data Mining Workshops, 2006. ICDM Workshops 2006. Sixth IEEE International Conference on*, 2006, pp. 443-447.

13. V. Alarcon-Aquino and J. Barria, "Change detection in time series using the maximal overlap discrete wavelet transform," *Latin American applied research*, vol. 39, pp. 145-152, 2009.

14. B. S. Darkhovski, "Nonparametric methods in change-point problems: A general approach and some concrete algorithms," *Lecture Notes-Monograph Series*, pp. 99-107, 1994.

15. J. S. Walker, *A primer on wavelets and their scientific applications: CRC press*, 2002.

16. J.P.Qi, Q.Zhang, and J. Qi, "A Fast Method for Change Point Detection from time series Based on Haar Wavelet and Binary Search Tree (HWBST)," presented at the The 19th World Congress of the International Federation of Automatic Control Cape Town, South Africa, to be published.

17. A. L. Goldberger, et al., "Physiobank, physiotoolkit, and physionet components of a new research resource for complex physiologic signals," *Circulation*, vol. 101, pp. e215-e220, 2000.

18. G. B. Moody, et al., "A noise stress test for arrhythmia detectors," *Computers in Cardiology*, vol. 11, pp. 381-384, 1984.

19. G. SD, "Development and analysis of a ventricular fibrillation detector," M.S. thesis, MIT Dept. of Electrical Engineering and Computer Science, 1986.