Please use this identifier to cite or link to this item: http://cuir.car.chula.ac.th/handle/123456789/52820
Title: การจัดกลุ่มลำดับย่อยของข้อมูลอนุกรมเวลาโดยปราศจากพารามิเตอร์
Other Titles: Parameter-free subsequence time series clustering
Authors: นวิน มาดิการ
Advisors: โชติรัตน์ รัตนามหัทธนะ
Other author: จุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์
Advisor's Email: Chotirat.R@Chula.ac.th
Subjects: การวิเคราะห์อนุกรมเวลา
การวิเคราะห์อนุกรมเวลา -- โปรแกรมคอมพิวเตอร์
การวิเคราะห์จัดกลุ่ม
Time-series analysis
Time-series analysis -- Computer programs
Cluster analysis
Issue Date: 2556
Publisher: จุฬาลงกรณ์มหาวิทยาลัย
Abstract: การจัดกลุ่มลำดับย่อยของข้อมูลอนุกรมเวลา เป็นการจัดกลุ่มรูปแบบหนึ่งในส่วนของงานวิจัยในด้านการทำเหมืองข้อมูลอนุกรมเวลา ซึ่งจะทำการพิจารณาบนข้อมูลอนุกรมเวลาหนึ่ง ๆ และจัดกลุ่มให้กับลำดับย่อยภายในข้อมูลอนุกรมเวลานั้น โดยวิเคราะห์จากความคล้ายคลึงกันของข้อมูล ลำดับย่อยที่มีความคล้ายคลึงกันของข้อมูลสูงจะถูกจัดอยู่ในกลุ่มเดียวกัน ในขณะที่ลำดับย่อยที่มีความคล้ายคลึงกันของข้อมูลต่ำจะถูกจัดอยู่ในกลุ่มที่ต่างออกไป โดยมีหลักเกณฑ์ที่สำคัญคือ ลำดับย่อยทุกลำดับไม่จำเป็นต้องถูกจัดกลุ่มทั้งหมด และ ลำดับย่อยที่ถูกจัดกลุ่มจะต้องไม่มีการซ้อนทับกัน ในงานวิจัยที่ผ่านมาทั้งหมดเกี่ยวกับการจัดกลุ่มลำดับย่อยของข้อมูลอนุกรมเวลา มีความจำเป็นที่จะต้องระบุพารามิเตอร์สำหรับกำหนดค่าความยาวของลำดับย่อยก่อนที่จะทำการจัดกลุ่ม ซึ่งก่อให้เกิดปัญหาสำคัญสองประการ คือ 1. เป็นการยากที่ผู้ใช้จะทราบค่าที่เหมาะสมในการจัดกลุ่มได้ บางครั้งต้องอาศัยความรู้จากผู้เชี่ยวชาญเฉพาะด้านของข้อมูลประเภทนั้น หรือแย่ไปกว่านั้นในกรณีที่ข้อมูลมีความซับซ้อนมาก ๆ แม้แต่ผู้เชี่ยวชาญเองก็ไม่สามารถระบุค่าที่เหมาะสมได้ และ 2. ความยาวของลำดับย่อยในการจัดกลุ่มจะถูกจำกัดโดยค่าพารามิเตอร์ที่กำหนดลงไปนี้ ทำให้ขาดอิสระในการจัดกลุ่มที่แท้จริง เพราะโดยทั่วไปแล้วในข้อมูลอนุกรมเวลาหนึ่ง ๆ ไม่จำเป็นที่ลำดับย่อยในแต่ละกลุ่มจะต้องมีความยาวเท่ากัน ทั้งสองปัญหานี้นำไปสู่ความไม่แม่นยำในการจัดกลุ่ม จึงเป็นที่มาของการนำเสนอการจัดกลุ่มลำดับย่อยของข้อมูลอนุกรมเวลาโดยปราศจากพารามิเตอร์ เพื่อให้ได้การจัดกลุ่มลำดับย่อยที่ง่ายต่อการใช้งานและอิสระ ครอบคลุมการจัดกลุ่มในทุกความยาว โดยการนำหลักของการค้นพบโมทีฟความยาวเหมาะสมสาหรับข้อมูลอนุกรมเวลามาประยุกต์ใช้สำหรับสร้างกลุ่มตั้งต้นที่มีความยาวเหมาะสม ซึ่งอาจประกอบด้วยความยาวเท่าใดก็ได้ ก่อนที่จะทำการคัดเลือกลำดับย่อยในความยาวที่เหมาะสมเหล่านี้มาทำการจัดกลุ่มต่อไป ทั้งนี้ได้ทำการทดลองเพื่อวัดประสิทธิภาพในแง่ของความแม่นยำเทียบกับวิธีการก่อนหน้าที่ต้องกำหนดพารามิเตอร์ โดยกำหนดพารามิเตอร์ที่ค่าจริงให้กับอัลกอริทึม เพื่อให้เห็นว่าวิธีการที่นำเสนอก็สามารถให้ผลลัพธ์ที่ดีใกล้เคียงกัน มากไปกว่านั้นยังได้ผลลัพธ์ที่เหนือกว่าอย่างเห็นได้ชัดในกรณีที่ข้อมูลอนุกรมเวลาประกอบด้วยกลุ่มของลำดับย่อยที่มีความยาวหลากหลาย
Other Abstract: Subsequence time series clustering, or STS Clustering, is one of the clustering methods in time series mining research. STS clustering considers a single time series and decomposes it to several subsequences. Then, it clusters similar subsequences together in a same group while the different subsequences are placed in distinct groups. The process runs with some constraints where not all subsequences in the time series need to be clustered (some subsequences are ignored) and the subsequences in any clusters must not overlap with each other. In prior research of STS clustering, all of them need at least one predefined parameter to define the width of the subsequences to be clustered that causes 2 major problems. First, it is a hard task for user to know the proper width of the subsequences to be clustered. Sometimes, they need some information from a domain expert, or to make things worse, even the domain expert cannot define what the proper width is if the time series is very complicated. Second, the width of the subsequences to be clustered is fixed by the predefined parameter. This limits the ability of the clustering to be inaccurate because the width of the subsequences should be allowed to be freely variant. Thus, the parameter-free STS Clustering algorithm is proposed in this thesis to solve the above problems. The proper length motif discovery algorithm is applied to find the initial clusters of the proper widths which can be any values, and then the rest of the subsequences are determined after (to be assigned into the initial groups or to be created as a new group). Absolutely, there are the experimental results in supporting this algorithm. The results show that the clustering’s accuracy of this algorithm is comparable to the prior algorithm which requires predefined parameter, even when the actual parameter is given. Moreover, this algorithm clearly outperforms the prior one in case of the time series containing subsequences of variable widths.
Description: วิทยานิพนธ์ (วศ.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2556
Degree Name: วิศวกรรมศาสตรมหาบัณฑิต
Degree Level: ปริญญาโท
Degree Discipline: วิศวกรรมคอมพิวเตอร์
URI: http://cuir.car.chula.ac.th/handle/123456789/52820
Type: Thesis
Appears in Collections:Eng - Theses

Files in This Item:
File Description SizeFormat 
navin_ma.pdf2.34 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.