Cargando…
A Fast Framework for Abrupt Change Detection Based on Binary Search Trees and Kolmogorov Statistic
Change-Point (CP) detection has attracted considerable attention in the fields of data mining and statistics; it is very meaningful to discuss how to quickly and efficiently detect abrupt change from large-scale bioelectric signals. Currently, most of the existing methods, like Kolmogorov-Smirnov (K...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Hindawi Publishing Corporation
2016
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4928006/ https://www.ncbi.nlm.nih.gov/pubmed/27413364 http://dx.doi.org/10.1155/2016/8343187 |
_version_ | 1782440356476878848 |
---|---|
author | Qi, Jin-Peng Qi, Jie Zhang, Qing |
author_facet | Qi, Jin-Peng Qi, Jie Zhang, Qing |
author_sort | Qi, Jin-Peng |
collection | PubMed |
description | Change-Point (CP) detection has attracted considerable attention in the fields of data mining and statistics; it is very meaningful to discuss how to quickly and efficiently detect abrupt change from large-scale bioelectric signals. Currently, most of the existing methods, like Kolmogorov-Smirnov (KS) statistic and so forth, are time-consuming, especially for large-scale datasets. In this paper, we propose a fast framework for abrupt change detection based on binary search trees (BSTs) and a modified KS statistic, named BSTKS (binary search trees and Kolmogorov statistic). In this method, first, two binary search trees, termed as BSTcA and BSTcD, are constructed by multilevel Haar Wavelet Transform (HWT); second, three search criteria are introduced in terms of the statistic and variance fluctuations in the diagnosed time series; last, an optimal search path is detected from the root to leaf nodes of two BSTs. The studies on both the synthetic time series samples and the real electroencephalograph (EEG) recordings indicate that the proposed BSTKS can detect abrupt change more quickly and efficiently than KS, t-statistic (t), and Singular-Spectrum Analyses (SSA) methods, with the shortest computation time, the highest hit rate, the smallest error, and the highest accuracy out of four methods. This study suggests that the proposed BSTKS is very helpful for useful information inspection on all kinds of bioelectric time series signals. |
format | Online Article Text |
id | pubmed-4928006 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2016 |
publisher | Hindawi Publishing Corporation |
record_format | MEDLINE/PubMed |
spelling | pubmed-49280062016-07-13 A Fast Framework for Abrupt Change Detection Based on Binary Search Trees and Kolmogorov Statistic Qi, Jin-Peng Qi, Jie Zhang, Qing Comput Intell Neurosci Research Article Change-Point (CP) detection has attracted considerable attention in the fields of data mining and statistics; it is very meaningful to discuss how to quickly and efficiently detect abrupt change from large-scale bioelectric signals. Currently, most of the existing methods, like Kolmogorov-Smirnov (KS) statistic and so forth, are time-consuming, especially for large-scale datasets. In this paper, we propose a fast framework for abrupt change detection based on binary search trees (BSTs) and a modified KS statistic, named BSTKS (binary search trees and Kolmogorov statistic). In this method, first, two binary search trees, termed as BSTcA and BSTcD, are constructed by multilevel Haar Wavelet Transform (HWT); second, three search criteria are introduced in terms of the statistic and variance fluctuations in the diagnosed time series; last, an optimal search path is detected from the root to leaf nodes of two BSTs. The studies on both the synthetic time series samples and the real electroencephalograph (EEG) recordings indicate that the proposed BSTKS can detect abrupt change more quickly and efficiently than KS, t-statistic (t), and Singular-Spectrum Analyses (SSA) methods, with the shortest computation time, the highest hit rate, the smallest error, and the highest accuracy out of four methods. This study suggests that the proposed BSTKS is very helpful for useful information inspection on all kinds of bioelectric time series signals. Hindawi Publishing Corporation 2016 2016-06-16 /pmc/articles/PMC4928006/ /pubmed/27413364 http://dx.doi.org/10.1155/2016/8343187 Text en Copyright © 2016 Jin-Peng Qi et al. https://creativecommons.org/licenses/by/4.0/ This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |
spellingShingle | Research Article Qi, Jin-Peng Qi, Jie Zhang, Qing A Fast Framework for Abrupt Change Detection Based on Binary Search Trees and Kolmogorov Statistic |
title | A Fast Framework for Abrupt Change Detection Based on Binary Search Trees and Kolmogorov Statistic |
title_full | A Fast Framework for Abrupt Change Detection Based on Binary Search Trees and Kolmogorov Statistic |
title_fullStr | A Fast Framework for Abrupt Change Detection Based on Binary Search Trees and Kolmogorov Statistic |
title_full_unstemmed | A Fast Framework for Abrupt Change Detection Based on Binary Search Trees and Kolmogorov Statistic |
title_short | A Fast Framework for Abrupt Change Detection Based on Binary Search Trees and Kolmogorov Statistic |
title_sort | fast framework for abrupt change detection based on binary search trees and kolmogorov statistic |
topic | Research Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4928006/ https://www.ncbi.nlm.nih.gov/pubmed/27413364 http://dx.doi.org/10.1155/2016/8343187 |
work_keys_str_mv | AT qijinpeng afastframeworkforabruptchangedetectionbasedonbinarysearchtreesandkolmogorovstatistic AT qijie afastframeworkforabruptchangedetectionbasedonbinarysearchtreesandkolmogorovstatistic AT zhangqing afastframeworkforabruptchangedetectionbasedonbinarysearchtreesandkolmogorovstatistic AT qijinpeng fastframeworkforabruptchangedetectionbasedonbinarysearchtreesandkolmogorovstatistic AT qijie fastframeworkforabruptchangedetectionbasedonbinarysearchtreesandkolmogorovstatistic AT zhangqing fastframeworkforabruptchangedetectionbasedonbinarysearchtreesandkolmogorovstatistic |