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.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
ปริวัฒนศักดิ์, กรกฎ, "การหาโมทีฟและดิสคอร์ดสำหรับอนุกรมเวลา โดยใช้เมทริกซ์โพรไฟล์แบบประมาณ" (2017). Chulalongkorn University Theses and Dissertations (Chula ETD). 1742.
https://digital.car.chula.ac.th/chulaetd/1742