Detecting Metachanges in Data Streams from the Viewpoint of the MDL Principle
This paper addresses the issue of how we can detect changes of changes, which we call <i>metachanges</i>, in data streams. A metachange refers to a change in patterns of when and how changes occur, referred to as “metachanges along time” and “metachanges alo...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-11-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/21/12/1134 |
| _version_ | 1817996500093894656 |
|---|---|
| author | Shintaro Fukushima Kenji Yamanishi |
| author_facet | Shintaro Fukushima Kenji Yamanishi |
| author_sort | Shintaro Fukushima |
| collection | DOAJ |
| description | This paper addresses the issue of how we can detect changes of changes, which we call <i>metachanges</i>, in data streams. A metachange refers to a change in patterns of when and how changes occur, referred to as “metachanges along time” and “metachanges along state”, respectively. Metachanges along time mean that the intervals between change points significantly vary, whereas metachanges along state mean that the magnitude of changes varies. It is practically important to detect metachanges because they may be early warning signals of important events. This paper introduces a novel notion of metachange statistics as a measure of the degree of a metachange. The key idea is to integrate metachanges along both time and state in terms of “code length” according to the minimum description length (MDL) principle. We develop an online metachange detection algorithm (MCD) based on the statistics to apply it to a data stream. With synthetic datasets, we demonstrated that MCD detects metachanges earlier and more accurately than existing methods. With real datasets, we demonstrated that MCD can lead to the discovery of important events that might be overlooked by conventional change detection methods. |
| first_indexed | 2024-04-14T02:23:01Z |
| format | Article |
| id | doaj.art-608990d7eba94205ab36aec72b075599 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-04-14T02:23:01Z |
| publishDate | 2019-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-608990d7eba94205ab36aec72b0755992022-12-22T02:17:58ZengMDPI AGEntropy1099-43002019-11-012112113410.3390/e21121134e21121134Detecting Metachanges in Data Streams from the Viewpoint of the MDL PrincipleShintaro Fukushima0Kenji Yamanishi1Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku 113-8656, JapanDepartment of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku 113-8656, JapanThis paper addresses the issue of how we can detect changes of changes, which we call <i>metachanges</i>, in data streams. A metachange refers to a change in patterns of when and how changes occur, referred to as “metachanges along time” and “metachanges along state”, respectively. Metachanges along time mean that the intervals between change points significantly vary, whereas metachanges along state mean that the magnitude of changes varies. It is practically important to detect metachanges because they may be early warning signals of important events. This paper introduces a novel notion of metachange statistics as a measure of the degree of a metachange. The key idea is to integrate metachanges along both time and state in terms of “code length” according to the minimum description length (MDL) principle. We develop an online metachange detection algorithm (MCD) based on the statistics to apply it to a data stream. With synthetic datasets, we demonstrated that MCD detects metachanges earlier and more accurately than existing methods. With real datasets, we demonstrated that MCD can lead to the discovery of important events that might be overlooked by conventional change detection methods.https://www.mdpi.com/1099-4300/21/12/1134change detectionchange of changedata streamminimum description length principlecode length |
| spellingShingle | Shintaro Fukushima Kenji Yamanishi Detecting Metachanges in Data Streams from the Viewpoint of the MDL Principle Entropy change detection change of change data stream minimum description length principle code length |
| title | Detecting Metachanges in Data Streams from the Viewpoint of the MDL Principle |
| title_full | Detecting Metachanges in Data Streams from the Viewpoint of the MDL Principle |
| title_fullStr | Detecting Metachanges in Data Streams from the Viewpoint of the MDL Principle |
| title_full_unstemmed | Detecting Metachanges in Data Streams from the Viewpoint of the MDL Principle |
| title_short | Detecting Metachanges in Data Streams from the Viewpoint of the MDL Principle |
| title_sort | detecting metachanges in data streams from the viewpoint of the mdl principle |
| topic | change detection change of change data stream minimum description length principle code length |
| url | https://www.mdpi.com/1099-4300/21/12/1134 |
| work_keys_str_mv | AT shintarofukushima detectingmetachangesindatastreamsfromtheviewpointofthemdlprinciple AT kenjiyamanishi detectingmetachangesindatastreamsfromtheviewpointofthemdlprinciple |