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.

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.