Chulalongkorn University Theses and Dissertations (Chula ETD)

Meaningful subsequence clustering for time series data stream

Other Title (Parallel Title in Other Language of ETD)

การจัดกลุ่มลำดับย่อยของข้อมูลอนุกรมเวลาแบบกระแสอย่างมีความหมาย

Year (A.D.)

2010

Document Type

Thesis

First Advisor

Chotirat Ann Ratanamahatana

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

Doctor of Philosophy

Degree Level

Doctoral Degree

Degree Discipline

Computer Engineering

DOI

10.58837/CHULA.THE.2010.1736

Abstract

Subsequence clustering for time series data streams is one of the most challenging issues of time series data mining since subsequence clustering has been proven both theoretically and empirically that it produces meaningless clustering results, where hundreds of research works that utilize Subsequence Time Series Clustering (STSC) as a preprocessing step and a subroutine are all affected. Given a time series sequence, subsequence clustering should return cluster representatives which represent characteristics of all subsequences in time series. Therefore, if cluster representatives are always sine waves regardless of inputs, clustering results are meaningless since they do not reflect characteristics of the subsequences. The causes of meaninglessness are identified in twofold, i.e., inappropriate uses of Euclidean distance as a distance measure and Amplitude Averaging as an averaging function. To achieve meaningful clustering results, in this thesis, Shape-based Subsequence Time Series Clustering (2STSC) is proposed to use Dynamic Time Warping (DTW) distance measure and Shape-based Averaging function. Therefore, 2STSC returns more meaningful results than those from STSC. However, 2STSC cannot directly apply to data streams since 2STSC consumes large computational complexity by considering all previous subsequences for every new incoming data point. Shape-based Streaming Subsequence Time Series Clustering (3STSC) is then proposed to handle the streaming case by calculating a clustering result on a small set of stored subsequences instead of calculating from all previous subsequences. The small set of stored subsequences is updated for every new incoming data point to maintain the number of stored subsequences not to exceed the maximum allowance. 3STSC, therefore, is much faster than 2STSC, while 3STSC returns small distortions of clustering results.

Other Abstract (Other language abstract of ETD)

การจัดกลุ่มลำดับย่อยสำหรับข้อมูลอนุกรมเวลาแบบกระแสเป็นหนึ่งในปัญหาที่ท้าทายมากที่สุดของการทำเหมืองข้อมูลอนุกรมเวลาตั้งแต่การจัดกลุ่มลำดับย่อยได้ถูกแสดงให้เห็นว่าการจัดกลุ่มจะให้คำตอบที่ไร้ความหมายในเชิงการทดลองและทฤษฎี การจัดกลุ่มลำดับย่อยของข้อมูลอนุกรมเวลาที่ถูกใช้ในหลายร้อยงานวิจัยนั้นจะให้คลื่นไซน์เป็นตัวแทนกลุ่มเสมอ ถ้าให้ข้อมูลอนุกรมเวลาหนึ่ง ๆ การจัดกลุ่มลำดับย่อยของข้อมูลอนุกรมเวลาควรคืนค่าตัวแทนกลุ่มที่เป็นลักษณะของทุกลำดับย่อยในข้อมูลอนุกรมเวลา สาเหตุที่ทำให้เกิดความไร้ความหมายถูกระบุไว้มาจากสองสาเหตุได้แก่ การใช้ระยะทางยุคลิดเป็นตัววัดระยะทางที่ไม่เหมาะสมและการใช้การเฉลี่ยค่าตามแอมพลิจูดเป็นฟังก์ชันการเฉลี่ยที่ไม่เหมาะสม เพื่อที่จะได้มาซึ่งคำตอบของการจัดกลุ่มที่มีความหมาย ในวิทยานิพนธ์นี้การจัดกลุ่มลำดับย่อยของข้อมูลอนุกรมเวลาตามรูปได้ถูกเสนอโดยใช้ระยะทางไดนามิกไทม์วอร์ปปิงและการเฉลี่ยค่าตามรูปแทนระยะทางยุคลิดและการเฉลี่ยค่าตามแอมพลิจูดตามลำดับ ดังนั้นการจัดกลุ่มลำดับย่อยของข้อมูลอนุกรมเวลาตามรูปจะคืนผลลัพธ์ที่มีความหมายที่มากกว่าการจัดกลุ่มลำดับย่อยของข้อมูลอนุกรมเวลาแบบเดิม แต่อย่างไรก็ตามการจัดกลุ่มลำดับย่อยของข้อมูลอนุกรมเวลาตามรูปไม่สามารถประยุกต์ใช้กับข้อมูลแบบกระแสได้ เนื่องจากการจัดกลุ่มลำดับย่อยของข้อมูลอนุกรมเวลาตามรูปใช้เวลาในการประมวลผลนานโดยคำนวณลำดับย่อยที่ผ่านมาทั้งหมดเมื่อมีจุดข้อมูลใหม่เข้ามา การจัดกลุ่มลำดับย่อยของข้อมูลอนุกรมเวลาแบบกระแสตามรูปจึงถูกเสนอให้รองรับกรณีข้อมูลแบบกระแสโดยคำนวณบนชุดข้อมูลขนาดเล็กของลำดับย่อยที่เก็บไว้แทนที่จะคำนวณจากลำดับย่อยทั้งหมด ซึ่งชุดข้อมูลของลำดับย่อยที่เก็บไว้ถูกปรับปรุงสำหรับทุกๆจุดข้อมูลเพื่อรักษาจำนวนลำดับย่อยในชุดข้อมูลไม่ให้เกินกว่าจำนวนมากสุดที่อนุญาต ดังนั้นการจัดกลุ่มลำดับย่อยของข้อมูลอนุกรมเวลาแบบกระแสตามรูปจึงเร็วกว่าการจัดกลุ่มลำดับย่อยของข้อมูลอนุกรมเวลาตามรูปอย่างมาก

Link to Full Text

Share

COinS