Chulalongkorn University Theses and Dissertations (Chula ETD)

การแทนข้อมูลแบบแฟร็กทัลสำหรับข้อมูลอนุกรมเวลาขนาดใหญ่

Other Title (Parallel Title in Other Language of ETD)

Fractal representation for large time series data

Year (A.D.)

2008

Document Type

Thesis

First Advisor

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

Faculty/College

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

Degree Name

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

Degree Level

ปริญญาโท

Degree Discipline

วิศวกรรมคอมพิวเตอร์

DOI

10.58837/CHULA.THE.2008.1424

Abstract

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

Other Abstract (Other language abstract of ETD)

Most of the time series mining tasks have focused on increasing both accuracy and speed. However, a tradeoff between accuracy and time consumption needs to be considered. Increasing accuracy of the mining task leads to higher computational cost. The dimensionality reduction techniques can reduce the time complexity of mining tasks, but it hurts the accuracy. In this research, Fractal Representation, a new dimensionality reduction technique, uses merely two real values to represent a time series sequence. To demonstrate effectiveness of fractal representation on classification problems, this research compares the proposed method with existing classification methods, i.e., Euclidean distance, Dynamic Time Warping (DTW) distance, Compression-Based Dissimilarity Measure (CDM), Symbolic Aggregate Approximation (SAX), and Clipped Data Representation, both in terms of accuracy and speed. In the experiments, when amount of time series increases, Fractal Representation greatly outperforms DTW up to 3 orders of magnitude in terms of speed. Moreover, the accuracy of Fractal Representation is comparable to DTW’s and CDM’s and outperforms the existing methods including SAX, Clipped Data Representation, and Euclidean distance.

Link to Full Text

Share

COinS