Proper length motif discovery for time series data using MDL principle
Thesis (M.Eng.)--Chulalongkorn University, 2012
Saved in:
Main Author: | |
---|---|
Other Authors: | , |
Format: | Book |
Published: |
Chulalongkorn University,
2014-05-06T03:23:40Z.
|
Subjects: | |
Online Access: | http://cuir.car.chula.ac.th/handle/123456789/42308 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
MARC
LEADER | 00000 am a22000003u 4500 | ||
---|---|---|---|
001 | repochula_42308 | ||
042 | |a dc | ||
100 | 1 | 0 | |a Sorrachai Yingchareonthawornchai |e author |
245 | 0 | 0 | |a Proper length motif discovery for time series data using MDL principle |
246 | 3 | 3 | |a การค้นพบโมทีฟความยาวเหมาะสมสำหรับข้อมูลอนุกรมเวลาโดยใช้หลักการเอ็มดีแอล |
260 | |b Chulalongkorn University, |c 2014-05-06T03:23:40Z. | ||
500 | |a http://cuir.car.chula.ac.th/handle/123456789/42308 | ||
520 | |a Thesis (M.Eng.)--Chulalongkorn University, 2012 | ||
520 | |a As one of the most essential data mining tasks, finding of frequently occurring patterns, i.e., motif discovery, has drawn a lot of attention in the past decade. Despite successes in speedup of motif discovery, most of the existing algorithms still require predefined parameters. The critical and most cumbersome one is time series motif length since it is difficult to manually determine the proper length of the motifs-even for the domain experts. In addition, with variability in the motif lengths, ranking among these motifs becomes another major problem, not to mention possible redundancy of sub-motifs. Ultimately, running all possible ranges of parameter is computationally expensive. There are some attempts to deal with the parameter issue. However, they cannot truly eliminate parameters. There is a work that is considered the first parameter-free motif discovery, but it is not as efficient due to scalability problem and solution quality. These problems inspired this work to introduce a novel parameter-free time series motif discovery based on MDL (Minimum Description Length) principle. This work requires no parameter as input. The output is ranked classes of motifs or "K-compression Motif," that are based on MDL principle. The experiments have been designed to correspond to the objectives: parameter-freeness, correctness, and speed. The proposed algorithm manages to discover proper length of motifs with consistently high accuracy. In addition, the proposed algorithm manages to discover "unexpected" motifs of time series. As for speed, the proposed algorithm is a few magnitudes faster than previous work. | ||
520 | |a การค้นพบโมทีฟสำหรับข้อมูลอนุกรมเวลาเป็นสาขาหนึ่งของงานวิจัยการทำเหมืองข้อมูลอนุกรมเวลาซึ่งได้รับความสนใจเป็นอย่างมากในทศวรรษที่ผ่านมา งานวิจัยด้านการค้นพบโมทีฟที่ผ่านมาประสบความสำเร็จในการค้นพบโมทีฟได้อย่างรวดเร็ว แต่งานวิจัยเหล่านั้นจะต้องกำหนดค่าของพารามิเตอร์ต่างๆ พารามิเตอร์หนึ่งที่สำคัญอย่างยิ่งและยากในการกำจัดคือความยาวโมทีฟที่จะค้นหา เพราะความยาวที่เหมาะสมของโมทีฟนั้นหาได้ยากแม้กระทั่งสำหรับผู้เชี่ยวชาญในสาขานั้นๆ ก็ตาม ถึงแม้ผู้ใช้จะสามารถระบุค่าความยาวโมทีฟมากกว่าหนึ่งค่าได้ การนำโมทีฟที่ได้ในได้ละความยาวมาจัดอันดับเพื่อนำไปใช้งานจริงนั้นเป็นอีกปัญหาที่ท้าทายเนื่องจากโมทีฟที่ได้อาจเหลื่อมล้ำและซ้ำซ้อนกันได้ และยิ่งกว่านั้นการเลือกทุกความยาวที่เป็นไปได้สำหรับการดำเนินอัลกอริทึมนั้นทำให้การทำงานช้ามาก อย่างไรก็ตามมีงานวิจัยน้อยมากที่ได้กล่าวถึงปัญหาความยาวของโมทีฟและนำเสนออัลกอริทึมในการแก้ปัญหา แต่งานเหล่านั้นไม่สามารถกำจัดพารามิเตอร์ไปได้ทั้งหมด มีอีกงานวิจัยที่สามารถกำจัดพารามิเตอร์ทั้งหมดได้ แต่มีปัญหาทางด้านความสามารถในการปรับขนาดได้ในกรณีข้อมูลที่มีขนาดใหญ่ และคุณภาพของโมทีฟที่ค้นพบ ปัญหาข้างต้นเป็นแรงบันดาลใจของการค้นพบโมทีฟความยาวเหมาะสมที่ปราศจากพารามิเตอร์โดยใช้หลักการเอ็มดีแอล (ความยาวเชิงการพรรณาน้อยสุด) โดยให้ผลลัพธ์สุดท้ายเป็นเซตของ "การบีบอัดโมทีฟ" จากหลักการเอ็มดีแอล โดยมีวิธีการวัดคุณภาพของผลลัพธ์โมทีฟและประสิทธิภาพของอัลกอริทึมที่ชัดเจนตามวัตถุประสงค์อันได้แก่ ความปราศจากพารามิเตอร์ ความถูกต้อง และความเร็ว อัลกอริทึมที่นำเสนอนั้นสามารถค้นพบโมทีฟที่ความยาวเหมาะสมได้โดยมีความแม่นยำสูง ยิ่งกว่านั้นอัลกอริทึมยังสามารถค้นพบโมทีฟที่นอกเหนือความคาดหมายได้ และงานนี้เร็วกว่างานก่อนหน้าเป็นอันดับขนาดเล็กน้อย | ||
540 | |a Chulalongkorn University | ||
546 | |a en | ||
690 | |a Time-series analysis | ||
690 | |a Data mining | ||
690 | |a การวิเคราะห์อนุกรมเวลา | ||
690 | |a ดาต้าไมนิง | ||
655 | 7 | |a Thesis |2 local | |
100 | 1 | 0 | |a Chotirat Ratanamahatana |e contributor |
100 | 1 | 0 | |a Chulalongkorn University. Faculty of Engineering |e contributor |
787 | 0 | |n http://doi.org/10.14457/CU.the.2012.505 | |
856 | 4 | 1 | |u http://cuir.car.chula.ac.th/handle/123456789/42308 |