Chulalongkorn University Theses and Dissertations (Chula ETD)

Other Title (Parallel Title in Other Language of ETD)

TIME SERIES MOTIF AND DISCORD DISCOVERY USING APPROXIMATED MATRIX PROFILE

Year (A.D.)

2017

Document Type

Thesis

First Advisor

โชติรัตน์ รัตนามหัทธนะ

Faculty/College

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

Department (if any)

Department of Computer Engineering (ภาควิชาวิศวกรรมคอมพิวเตอร์)

Degree Name

วิทยาศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

วิทยาศาสตร์คอมพิวเตอร์

DOI

10.58837/CHULA.THE.2017.1252

Abstract

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

Other Abstract (Other language abstract of ETD)

Time series motif discovery, a procedure of finding patterns in a long time series sequence, has become one of the most prevalent time series mining tasks as it could be applied in various domains. Meanwhile, time series discord discovery, a procedure of detecting abnormality in a time series data, has also become the most popular technique in anomaly detection problem. Recently, matrix profile has become the competitive method for motif and discord discovery because if matrix profile is given, both time series problems can easily solve. However, its computation takes too much time for large time series data. Moreover, the parameter of motif and discord length has to be defined but it can not be trivially done. This dissertation proposes an approximated version of the matrix profile for both problems, which reduces time computation and still get impressively correct motif results and also proposes a parameter-free algorithm for motif discovery task that solves the pre-parameter-defined problem. The experiment results on both synthetic and real datasets reconfirm that our approximated matrix profile can speed up the computation by a large margin and still obtain the motif and discord similar to the motif from the full matrix profile. Also, our parameter-free algorithm can give the reasonable motif results with proper length.

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.