Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
Motif and discord discovery in time series using enhanced approximated matrix profile
Year (A.D.)
2019
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.2019.1129
Abstract
การค้นพบโมทีฟและดิสคอร์ดสำหรับอนุกรมเวลา เป็นสาขาหนึ่งของงานวิจัยการทำเหมืองข้อมูลอนุกรมเวลา ซึ่งการค้นหารูปแบบของลำดับย่อยที่เกิดขึ้นซ้ำโดยมีลักษณะคล้ายกัน และรูปแบบของลำดับย่อยที่มีความผิดปกติ คือการค้นพบโมทีฟและการค้นพบดิสคอร์ดตามลำดับ วิธีการหนึ่งที่เป็นที่นิยมสำหรับงานด้านการค้นพบโมทีฟและดิสคอร์ด คือการคำนวณหาเมทริกซ์โพรไฟล์ เนื่องจากเป็นวิธีที่รวดเร็ว และได้คำตอบที่ถูกต้องแม่นยำ แต่ถ้าหากข้อมูลอนุกรมเวลามีขนาดที่ใหญ่มาก จะส่งผลให้เวลาที่ใช้ในการคำนวณนั้นนานมากตามไปด้วย และอีกหนึ่งปัญหาที่สำคัญ คือการกำหนดค่าพารามิเตอร์ความยาว ของลำดับย่อย ที่ใช้ในการค้นหาโมทีฟ ที่ผู้ใช้ไม่สามารถทราบได้แน่ชัดว่า ควรกำหนดความยาวของลำดับย่อยเป็นเท่าใด เพื่อแก้ปัญหาที่กล่าวมาข้างต้น งานวิจัยนี้จึงได้นำเสนอเมทริกซ์โพรไฟล์แบบประมาณ ที่มีการเพิ่มสมรรถนะ สำหรับทั้งปัญหาการค้นพบโมทีฟและดิสคอร์ด ซึ่งลดเวลาในการคำนวณได้เป็นอย่างมาก และผลลัพธ์ที่ได้มีความใกล้เคียงเดิม อีกทั้งนำเสนออัลกอริทึมสำหรับการกำหนดพารามิเตอร์ค่าความยาวโมทีฟที่เหมาะสม จากผลการทดลอง อัลกอริทึมสามารถลดกระบวนการคำนวณลงได้ ส่งผลให้เวลาที่ใช้ในการคำนวณลดลงได้เป็นอย่างมาก อีกทั้งผลลัพธ์ที่ได้ มีค่าใกล้เคียงกับการใช้เมทริกซ์โพรไฟล์แบบปกติ และยังสามารถค้นพบโมทีฟได้ โดยไม่จำเป็นต้องกำหนดค่าความยาวของลำดับย่อย
Other Abstract (Other language abstract of ETD)
Time series motif and discord discovery are a branch of research in time series data mining. Finding the most similar repeated subsequences and the anomaly subsequences are the motif and the discord discovery, respectively. One of the most popular methods to discover motif and discord is by using a Matrix Profile structure because it is fast and accurate. However, if the time series data is very large, its computation time could be very long. Another important issue is the subsequence length parameter that is used to find the motif; it is difficult for the users to know exactly the proper length of the subsequence. In order to solve these problems, this research proposes an Enhanced Approximated Matrix Profile for both the motif and the discord discovery, which highly reduces the computation time, and the result is similar to the original. An algorithm for determining the optimum motif length using the Proper Length Motif discovery algorithm is used in combination with the proposed Enhanced Approximated Matrix Profile. Based on experimental results, the proposed algorithm is able to reduce the computation process, resulting in a significant reduction in computational time. In addition, the results are accurate, and the motif can be discovered without having to determine the length of the subsequence.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
อ้นวงษา, ชนะพล, "การค้นพบโมทีฟและดิสคอร์ดสำหรับอนุกรมเวลา โดยใช้เมทริกซ์โพรไฟล์แบบประมาณที่มีการเพิ่มสมรรถนะ" (2019). Chulalongkorn University Theses and Dissertations (Chula ETD). 9505.
https://digital.car.chula.ac.th/chulaetd/9505