Pseudometrics for time series data classification using the nearest neighbor algorithm

เมตริกเทียมสำหรับการจำแนกประเภทข้อมูลอนุกรมเวลาโดยใช้อัลกอรึทึมเนียเรสท์เนเบอร์

Name: Teesid Korsrilabutr

ThaSH: Sequence

ThaSH: Time series

ThaSH: Metric

Abstract: We propose that pseudometric, a subadditive distance measure, has sufficient properties to be a good structure to perform nearest neighbor pattern classification. There exist some theoretical results that asymptotically guarantee the classification accuracy of k-nearest neighbor when the sample size grows larger. These results hold true under the assumption that the distance measure is a metric. The results still hold for pseudometrics up to some technicality. Whether the results are valid for the non-subadditive distance measures is still left unanswered. Pseudometric is also practically appealing. Once we have a subadditive distance measure, the measure will have at least one significant advantage over the non-subadditive; one can directly plug such distance measure into systems which exploit the subadditivity to perform faster nearest neighbor search techniques. This work focuses on pseudometrics for time series. We propose two frameworks for studying and designing subadditive distance measures and a few examples of distance measures resulting from the frameworks. One framework is more general than the other and can be used to tailor distances from the other framework to gain better classification performance. Experimental results of nearest neighbor classification of the designed pseudometrics in comparison with well-known existing distance measures including Dynamic Time Warping showed that the designed distance measures are practical for time series classification.

Abstract: เรานำเสนอว่าเมตริกเทียม ซึ่งเป็นมาตรวัดระยะห่างที่ซับแอดดิทีฟ มีคุณสมบัติเพียงพอที่จะเป็นโครงสร้างที่ดีสำหรับกระทำการจำแนกแบบอย่างด้วยเนียเรสท์เนเบอร์ มีผลทางทฤษฎีจำนวนหนึ่งที่รับประกันความถูกต้องของเคเนียเรสท์เนเบอร์แบบเชิงเส้นกำกับ เมื่อจำนวนตัวอย่างสอนโตขึ้น ผลเหล่านี้เป็นจริงภายใต้เงื่อนไขว่า มาตรวัดระยะห่างเป็นเมตริก ผลเหล่านี้ยังเป็นจริงสำหรับเมตริกเทียมหลังจากการปรับแต่งทางเทคนิค ณ ขณะนี้ยังไม่มีคำตอบว่าผลเหล่านี้สามารถเป็นจริงสำหรับมาตรวัดระยะห่างที่ไม่ซับแอดดิทีฟหรือไม่ เมตริกเทียมยังมีประโยชน์ในทางปฏิบัติอีกด้วย หากเรามีมาตรวัดระยะห่างที่ซับแอดดิทีฟแล้ว มาตรวัดนั้นจะมีความได้เปรียบมาตรวัดที่ไม่ซับแอดดิทีฟอย่างน้อยหนึ่งประการ กล่าวคือ เราสามารถนำมาตรวัดดังกล่าวไปใช้ได้โดยตรงในระบบที่ใช้ประโยชน์จากคุณสมบัติซับแอดดิทีฟเพื่อทำให้การค้นหาเพื่อนบ้านใกล้ที่สุดเร็วขึ้น งานนี้มุ่งเน้นที่เมตริกเทียมสำหรับอนุกรมเวลา เราเสนอสองกรอบงานเพื่อศึกษาและออกแบบมาตรวัดระยะห่างซับแอดดิทีฟและตัวอย่างจำนวนหนึ่งของมาตรวัดระยะห่างที่ออกแบบได้จากกรอบงานทั้งคู่ กรอบงานหนึ่งมีความทั่วไปสูงกว่าอีกหนึ่งกรอบงานและสามารถใช้เพื่อปรับแต่งมาตรวัดจากอีกกรอบงานหนึ่งเพื่อให้ประสิทธิภาพในการจำแนกประเภทสูงขึ้นได้ ผลการทดลองจำแนกประเภทโดยใช้เนียเรสท์เนเบอร์ร่วมกับฟังก์ชันที่ออกแบบได้ เปรียบเทียบกับมาตรวัดระยะห่างที่เป็นที่รู้จักดีรวมถึง Dynamic Time Warping แสดงให้เห็นว่ามาตรวัดระยะห่างที่ออกแบบขึ้นใช้งานได้จริงสำหรับการจำแนกประเภทข้อมูลอนุกรมเวลา

Chulalongkorn University. Center of Academic Resources

Address: BANGKOK

Email: cuir@car.chula.ac.th

Name: Boonserm Kijsirikul

Role: Advisor

Created: 2007

Modified: 2553-11-29

Issued: 2010-11-27

วิทยานิพนธ์/Thesis

application/pdf

eng

DegreeName: Master of Engineering

Level: Master's Degree

Descipline: Computer Engineering

Grantor: Chulalongkorn University

©copyrights Chulalongkorn University

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	Teesid_Ko.pdf	719.27 KB	129	2026-05-26 18:16:01

ใช้เวลา

0.023513 วินาที