{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T17:14:19Z","timestamp":1725988459872},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T00:00:00Z","timestamp":1676419200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T00:00:00Z","timestamp":1676419200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006211","name":"Humboldt-Universit\u00e4t zu Berlin","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006211","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Min Knowl Disc"],"published-print":{"date-parts":[[2023,5]]},"abstract":"Abstract<\/jats:title>The study of natural and human-made processes often results in long sequences of temporally-ordered values, aka time series (TS). Such processes often consist of multiple states, e.g. operating modes of a machine, such that state changes in the observed processes result in changes in the distribution of shape of the measured values. Time series segmentation (TSS) tries to find such changes in TS post-hoc to deduce changes in the data-generating process. TSS is typically approached as an unsupervised learning problem aiming at the identification of segments distinguishable by some statistical property. Current algorithms for TSS require domain-dependent hyper-parameters to be set by the user, make assumptions about the TS value distribution or the types of detectable changes which limits their applicability. Common hyper-parameters are the measure of segment homogeneity and the number of change points, which are particularly hard to tune for each data set. We present ClaSP, a novel, highly accurate, hyper-parameter-free and domain-agnostic method for TSS. ClaSP hierarchically splits a TS into two parts. A change point is determined by training a binary TS classifier for each possible split point and selecting the one split that is best at identifying subsequences to be from either of the partitions. ClaSP learns its main two model-parameters from the data using two novel bespoke algorithms. In our experimental evaluation using a benchmark of 107 data sets, we show that ClaSP outperforms the state of the art in terms of accuracy and is fast and scalable. Furthermore, we highlight properties of ClaSP using several real-world case studies.<\/jats:p>","DOI":"10.1007\/s10618-023-00923-x","type":"journal-article","created":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T17:13:29Z","timestamp":1676481209000},"page":"1262-1300","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["ClaSP: parameter-free time series segmentation"],"prefix":"10.1007","volume":"37","author":[{"ORCID":"http:\/\/orcid.org\/0000-0002-8138-3060","authenticated-orcid":false,"given":"Arik","family":"Ermshaus","sequence":"first","affiliation":[]},{"given":"Patrick","family":"Sch\u00e4fer","sequence":"additional","affiliation":[]},{"given":"Ulf","family":"Leser","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,2,15]]},"reference":[{"key":"923_CR1","unstructured":"Adams RP, MacKay DJ (2007) Bayesian online changepoint detection. arXiv preprint arXiv:0710.3742"},{"issue":"2","key":"923_CR2","first-page":"339","volume":"51","author":"S Aminikhanghahi","year":"2017","unstructured":"Aminikhanghahi S, Cook DJ (2017) A survey of methods for time series change point detection. KAIS 51(2):339\u2013367","journal-title":"KAIS"},{"key":"923_CR3","unstructured":"Bagnall A, Lines J, Bostrom A et\u00a0al (2016) The great time series classification bake off: an experimental evaluation of recently proposed algorithms. Extended Version. DMKD, pp 1\u201355"},{"issue":"9995\u201310","key":"923_CR4","first-page":"023","volume":"14","author":"O Ba\u00f1os","year":"2014","unstructured":"Ba\u00f1os O, T\u00f3th MA, Damas M et al (2014) Dealing with the effects of sensor displacement in wearable activity recognition. Sensors 14(9995\u201310):023","journal-title":"Sensors"},{"issue":"2","key":"923_CR5","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1016\/S1053-8119(03)00406-3","volume":"20","author":"M Bosc","year":"2003","unstructured":"Bosc M, Heitz F, Armspach JP et al (2003) Automatic change detection in multimodal serial mri: application to multiple sclerosis lesion evolution. NeuroImage 20(2):643\u2013656","journal-title":"NeuroImage"},{"issue":"4","key":"923_CR6","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1016\/j.csda.2004.02.006","volume":"47","author":"S Brahim-Belhouari","year":"2004","unstructured":"Brahim-Belhouari S, Bermak A (2004) Gaussian process for nonstationary time series prediction. Comput Stat Data Anal 47(4):705\u2013712","journal-title":"Comput Stat Data Anal"},{"key":"923_CR7","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF00117831","volume":"24","author":"L Breiman","year":"2004","unstructured":"Breiman L (2004) Technical note: some properties of splitting criteria. Mach Learn 24:41\u201347","journal-title":"Mach Learn"},{"key":"923_CR8","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.cie.2019.106024","volume":"137","author":"TP Carvalho","year":"2019","unstructured":"Carvalho TP, Soares F, Vita R et al (2019) A systematic literature review of machine learning methods applied to predictive maintenance. Comput Ind Eng 137:66","journal-title":"Comput Ind Eng"},{"issue":"1","key":"923_CR9","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1214\/14-AOS1269","volume":"43","author":"H Chen","year":"2015","unstructured":"Chen H, Zhang N et al (2015) Graph-based change-point detection. Ann Stat 43(1):139\u2013176","journal-title":"Ann Stat"},{"key":"923_CR10","unstructured":"ClaSP Code and Raw Results (2021) https:\/\/sites.google.com\/view\/ts-parameter-free-clasp\/"},{"key":"923_CR11","doi-asserted-by":"publisher","DOI":"10.1002\/9781119010258","volume-title":"Activity learning: discovering, recognizing, and predicting human behavior from sensor data","author":"DJ Cook","year":"2015","unstructured":"Cook DJ, Krishnan NC (2015) Activity learning: discovering, recognizing, and predicting human behavior from sensor data. Wiley, New York"},{"key":"923_CR12","doi-asserted-by":"publisher","first-page":"1293","DOI":"10.1109\/JAS.2019.1911747","volume":"6","author":"HA Dau","year":"2019","unstructured":"Dau HA, Bagnall AJ, Kamgar K et al (2019) The ucr time series archive. IEEE\/CAA J Autom Sin 6:1293\u20131305","journal-title":"IEEE\/CAA J Autom Sin"},{"key":"923_CR13","doi-asserted-by":"crossref","unstructured":"Davis LM, Theobald BJ, Lines J, et\u00a0al (2012) On the segmentation and classification of hand radiographs. Int J Neural Syst 22 5:1250020","DOI":"10.1142\/S0129065712500207"},{"key":"923_CR14","doi-asserted-by":"crossref","unstructured":"Deldari S, Smith DV, Sadri A et\u00a0al (2020) Espresso: entropy and shape aware time-series segmentation for processing heterogeneous sensor data. Proc ACM Interact Mob Wearable Ubiq Technol 4:77:1\u201377:24","DOI":"10.1145\/3411832"},{"issue":"5","key":"923_CR15","doi-asserted-by":"publisher","first-page":"1454","DOI":"10.1007\/s10618-020-00701-z","volume":"34","author":"A Dempster","year":"2020","unstructured":"Dempster A, Petitjean F, Webb GI (2020) Rocket: exceptionally fast and accurate time series classification using random convolutional kernels. Data Min Knowl Discov 34(5):1454\u20131495","journal-title":"Data Min Knowl Discov"},{"key":"923_CR16","first-page":"1","volume":"7","author":"J Dem\u0161ar","year":"2006","unstructured":"Dem\u0161ar J (2006) Statistical comparisons of classifiers over multiple data sets. J Mach Learn Res 7:1\u201330","journal-title":"J Mach Learn Res"},{"key":"923_CR17","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/j.ins.2013.02.030","volume":"239","author":"H Deng","year":"2013","unstructured":"Deng H, Runger G, Tuv E et al (2013) A time series forest for classification and feature extraction. Inf Sci 239:142\u2013153","journal-title":"Inf Sci"},{"issue":"6","key":"923_CR18","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1109\/MSP.2015.2398954","volume":"32","author":"I Dokmanic","year":"2015","unstructured":"Dokmanic I, Parhizkar R, Ranieri J et al (2015) Euclidean distance matrices: essential theory, algorithms, and applications. IEEE Signal Process Mag 32(6):12\u201330","journal-title":"IEEE Signal Process Mag"},{"key":"923_CR19","doi-asserted-by":"crossref","unstructured":"Draayer E, Cao H, Hao Y (2021) Reevaluating the change point detection problem with segment-based Bayesian online detection. In: Proceedings of the 30th ACM international conference on information & knowledge management","DOI":"10.1145\/3459637.3482167"},{"key":"923_CR20","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1109\/TKDE.2005.114","volume":"17","author":"MG Elfeky","year":"2005","unstructured":"Elfeky MG, Aref WG, Elmagarmid AK (2005) Periodicity detection in time series databases. IEEE Trans Knowl Data Eng 17:875\u2013887","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"8","key":"923_CR21","doi-asserted-by":"publisher","first-page":"861","DOI":"10.1016\/j.patrec.2005.10.010","volume":"27","author":"T Fawcett","year":"2006","unstructured":"Fawcett T (2006) An introduction to roc analysis. Pattern Recognit Lett 27(8):861\u2013874","journal-title":"Pattern Recognit Lett"},{"key":"923_CR22","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1109\/THMS.2014.2362529","volume":"45","author":"KD Feuz","year":"2015","unstructured":"Feuz KD, Cook DJ, Rosasco C et al (2015) Automated detection of activity transitions for prompting. IEEE Trans Hum Mach Syst 45:575\u2013585","journal-title":"IEEE Trans Hum Mach Syst"},{"key":"923_CR23","doi-asserted-by":"crossref","unstructured":"Gharghabi S, Ding Y, Yeh CCM et\u00a0al (2017) Matrix profile viii: domain agnostic online semantic segmentation at superhuman performance levels. In: ICDM. IEEE, pp 117\u2013126","DOI":"10.1109\/ICDM.2017.21"},{"key":"923_CR24","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/s10618-018-0589-3","volume":"33","author":"S Gharghabi","year":"2018","unstructured":"Gharghabi S, Yeh CCM, Ding Y et al (2018) Domain agnostic online semantic segmentation for multi-dimensional time series. Data Min Knowl Discov 33:96\u2013130","journal-title":"Data Min Knowl Discov"},{"key":"923_CR25","doi-asserted-by":"crossref","unstructured":"Harchaoui Z, Vallet F, Lung-Yut-Fong A et\u00a0al (2009) A regularized kernel-based approach to unsupervised audio segmentation. In: ICASSP. IEEE, pp 1665\u20131668","DOI":"10.1109\/ICASSP.2009.4959921"},{"key":"923_CR26","doi-asserted-by":"crossref","unstructured":"Heldt T, Oefinger M, Hoshiyama M et\u00a0al (2003) Circulatory response to passive and active changes in posture. In: Computers in cardiology, 2003. IEEE, pp 263\u2013266","DOI":"10.1109\/CIC.2003.1291141"},{"key":"923_CR27","doi-asserted-by":"crossref","unstructured":"Hido S, Id\u00e9 T, Kashima H et\u00a0al (2008) Unsupervised change analysis using supervised learning. In: PKDD. Springer, pp 148\u2013159","DOI":"10.1007\/978-3-540-68125-0_15"},{"key":"923_CR28","doi-asserted-by":"crossref","unstructured":"Ihler AT, Hutchins J, Smyth P (2006) Adaptive event detection with time-varying Poisson processes. In: PACM SIGKDD international conference on knowledge discovery and data mining","DOI":"10.1145\/1150402.1150428"},{"key":"923_CR29","unstructured":"Imani S, Keogh E (2021) Multi-window-finder: domain agnostic window size for time series data"},{"key":"923_CR30","doi-asserted-by":"crossref","unstructured":"Janik A, Dodd JD, Ifrim G et\u00a0al (2021) Interpretability of a deep learning model in the application of cardiac mri segmentation with an acdc challenge dataset. In: Medical imaging","DOI":"10.1117\/12.2582227"},{"key":"923_CR31","doi-asserted-by":"publisher","first-page":"4280","DOI":"10.3390\/app11094280","volume":"11","author":"ID Katser","year":"2021","unstructured":"Katser ID, Kozitsin V, Lobachev V et al (2021) Unsupervised offline changepoint detection ensembles. Appl Sci 11:4280","journal-title":"Appl Sci"},{"issue":"2","key":"923_CR32","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1002\/sam.10124","volume":"5","author":"Y Kawahara","year":"2012","unstructured":"Kawahara Y, Sugiyama M (2012) Sequential change-point detection based on direct density-ratio estimation. Stat Anal Data Min ASA Data Sci J 5(2):114\u2013127","journal-title":"Stat Anal Data Min ASA Data Sci J"},{"key":"923_CR33","unstructured":"Keogh E, Dutta Roy T, Naik U, Agrawal A (2021) Multi-dataset time-series anomaly detection competition. https:\/\/compete.hexagon-ml.com\/practice\/competition\/39\/"},{"key":"923_CR34","doi-asserted-by":"publisher","first-page":"1590","DOI":"10.1080\/01621459.2012.737745","volume":"107","author":"R Killick","year":"2012","unstructured":"Killick R, Fearnhead P, Eckley IA (2012) Optimal detection of changepoints with a linear computational cost. J Am Stat Assoc 107:1590\u20131598","journal-title":"J Am Stat Assoc"},{"key":"923_CR35","doi-asserted-by":"crossref","unstructured":"Malladi R, Kalamangalam GP, Aazhang B (2013) Online Bayesian change point detection algorithms for segmentation of epileptic activity. In: 2013 Asilomar conference on signals, systems and computers, pp 1833\u20131837","DOI":"10.1109\/ACSSC.2013.6810619"},{"key":"923_CR36","doi-asserted-by":"crossref","unstructured":"Matsubara Y, Sakurai Y, Faloutsos C (2014) Autoplait: automatic mining of co-evolving time sequences. In: SIGMOD, pp 193\u2013204","DOI":"10.1145\/2588555.2588556"},{"issue":"3","key":"923_CR37","first-page":"535","volume":"45","author":"HL Nguyen","year":"2015","unstructured":"Nguyen HL, Woon YK, Ng WK (2015) A survey on data stream clustering and classification. KAIS 45(3):535\u2013569","journal-title":"KAIS"},{"issue":"4","key":"923_CR38","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1016\/S0013-4694(97)00031-X","volume":"103","author":"RQ Quiroga","year":"1997","unstructured":"Quiroga RQ, Blanco S, Rosso O et al (1997) Searching for hidden information with gabor transform in generalized tonic-clonic seizures. Electroencephalogr Clin Neurophysiol 103(4):434\u2013439","journal-title":"Electroencephalogr Clin Neurophysiol"},{"issue":"6","key":"923_CR39","doi-asserted-by":"publisher","first-page":"1505","DOI":"10.1007\/s10618-014-0377-7","volume":"29","author":"P Sch\u00e4fer","year":"2015","unstructured":"Sch\u00e4fer P (2015) The BOSS is concerned with time series classification in the presence of noise. Data Min Knowl Discov 29(6):1505\u20131530","journal-title":"Data Min Knowl Discov"},{"key":"923_CR40","doi-asserted-by":"crossref","unstructured":"Sch\u00e4fer P, H\u00f6gqvist M (2012) SFA: a symbolic fourier approximation and index for similarity search in high dimensional datasets. In: EDBT. ACM, pp 516\u2013527","DOI":"10.1145\/2247596.2247656"},{"key":"923_CR41","doi-asserted-by":"crossref","unstructured":"Sch\u00e4fer P, Ermshaus A, Leser U (2021) Clasp\u2014time series segmentation. In: Proceedings of the 30th ACM international conference on information & knowledge management","DOI":"10.1145\/3459637.3482240"},{"key":"923_CR42","doi-asserted-by":"publisher","first-page":"507","DOI":"10.2307\/2529204","volume":"66","author":"AJ Scott","year":"1974","unstructured":"Scott AJ, Knott M (1974) A cluster analysis method for grouping means in the analysis of variance. Biometrics 66:507\u2013512","journal-title":"Biometrics"},{"key":"923_CR43","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1214\/aos\/1176343001","volume":"3","author":"AK Sen","year":"1975","unstructured":"Sen AK, Srivastava MS (1975) On tests for detecting change in mean. Ann Stat 3:98\u2013108","journal-title":"Ann Stat"},{"key":"923_CR44","unstructured":"Time Series Segmentation Benchmark (2021) https:\/\/github.com\/ermshaua\/time-series-segmentation-benchmark"},{"issue":"107","key":"923_CR45","first-page":"299","volume":"167","author":"C Truong","year":"2020","unstructured":"Truong C, Oudre L, Vayatis N (2020) Selective review of offline change point detection methods. Signal Process 167(107):299","journal-title":"Signal Process"},{"key":"923_CR46","unstructured":"Tsai YHH, Wu Y, Salakhutdinov R et\u00a0al (2020) Demystifying self-supervised learning: an information-theoretical framework. arXiv preprint arXiv:2006.05576"},{"key":"923_CR47","unstructured":"van\u00a0den Burg GJ, Williams CK (2020) An evaluation of change point detection algorithms. arXiv preprint arXiv:2003.06222"},{"key":"923_CR48","doi-asserted-by":"crossref","unstructured":"Vlachos M, Yu PS, Castelli V (2005) On periodicity detection and structural periodic similarity. In: SDM","DOI":"10.1137\/1.9781611972757.40"},{"key":"923_CR49","doi-asserted-by":"crossref","unstructured":"Wen Q, He K, Sun L et\u00a0al (2021) Robustperiod: robust time-frequency mining for multiple periodicity detection. In: Proceedings of the 2021 international conference on management of data","DOI":"10.1145\/3448016.3452779"},{"key":"923_CR50","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1186\/1471-2105-10-4","volume":"10","author":"C Yang","year":"2008","unstructured":"Yang C, He Z, Yu W (2008) Comparison of public peak detection algorithms for maldi mass spectrometry data analysis. BMC Bioinform 10:4\u20134","journal-title":"BMC Bioinform"},{"key":"923_CR51","first-page":"137","volume":"66","author":"J Zenisek","year":"2019","unstructured":"Zenisek J, Holzinger F, Affenzeller M (2019) Machine learning based concept drift detection for predictive maintenance. Comput Ind Eng 66:137","journal-title":"Comput Ind Eng"},{"key":"923_CR52","doi-asserted-by":"crossref","unstructured":"Zhao J, Itti L (2016) Decomposing time series with application to temporal segmentation. In: WACV. IEEE, pp 1\u20139","DOI":"10.1109\/WACV.2016.7477722"},{"key":"923_CR53","doi-asserted-by":"crossref","unstructured":"Zhu Y, Imamura M, Nikovski D et\u00a0al (2017) Matrix profile vii: Time series chains: a new primitive for time series data mining (best student paper award). In: 2017 IEEE international conference on data mining (ICDM), pp 695\u2013704","DOI":"10.1109\/ICDM.2017.79"},{"key":"923_CR54","doi-asserted-by":"crossref","unstructured":"Zhu Y, Yeh CCM, Zimmerman Z et\u00a0al (2018) Matrix profile xi: Scrimp++: time series motif discovery at interactive speeds. In: ICDM. IEEE, pp 837\u2013846","DOI":"10.1109\/ICDM.2018.00099"}],"container-title":["Data Mining and Knowledge Discovery"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-023-00923-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10618-023-00923-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-023-00923-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,8]],"date-time":"2023-04-08T19:05:35Z","timestamp":1680980735000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10618-023-00923-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,15]]},"references-count":54,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["923"],"URL":"https:\/\/doi.org\/10.1007\/s10618-023-00923-x","relation":{},"ISSN":["1384-5810","1573-756X"],"issn-type":[{"value":"1384-5810","type":"print"},{"value":"1573-756X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,15]]},"assertion":[{"value":"29 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 January 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 February 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors of this article have no conflict of interest to declare.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}