Dynamic time warping
![]() | ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |

ไดนามิกไทม์วอร์ปปิง (อังกฤษ: Dynamic time warping : DTW) เป็นขั้นตอนวิธีสำหรับการเปรียบเทียบความคล้ายของลำดับที่มีความแตกต่างกันในด้านเวลาหรือความเร็ว เช่น รูปแบบการเดินของคนๆหนึ่งจะถูกนับว่ามีความคล้าย ไม่ว่าคนๆนั้นจะเดินอย่างรวดเร็ว เดินอย่างเชื่องช้า หรือแม้แต่เดินด้วยความเร่ง เมื่อพิจารณาจากผู้สังเกตเดียวกัน ซึ่งไดนามิกไทม์วอร์ปปิงสามารถนำไปประยุกต์ได้กับวิดีโอ เสียง และภาพ รวมไปถึงข้อมูลต่างๆที่สามารถแปลงให้อยู่ในรูปของข้อมูลเชิงเส้นได้ ตัวอย่างหนึ่งของการประยุกต์ขั้นตอนวิธีนี้ไปใช้คือ การรู้จำคำพูด โดยใช้ไดนามิกไทม์วอร์ปปิง เพื่อจัดการกับคำพูดที่มีความเร็วไม่เท่ากัน แม้จะสื่อความหมายเดียวกัน
แนวคิดเบื้องต้น[แก้]
โดยทั่วไปไดนามิกไทม์วอร์ปปิงเป็นวิธีที่ทำให้คอมพิวเตอร์สามารถหาการจับคู่ที่เหมาะสมของลำดับสองชุดได้ภายใต้ข้อจำกัด ลำดับเหล่านั้นจะถูกบิดเบือน (warp) แบบไม่คงที่ในหน่วยของเวลา เพื่อที่จะพิจารณาความคล้ายจากการกระจายแบบไม่คงที่ในหน่วยของเวลา โดยจะให้ผลลัพธ์ออกมาเป็นระยะทางและวิถีการปรับแนว (alignment) ที่ดี่สุด ซึ่งวิธีการพิจารณาลำดับเช่นนี้พบได้บ่อยครั้งใน แบบจำลองฮิดเดนมาร์คอฟ (hidden Markov models)
ขั้นตอนวิธี[แก้]
เป้าหมายของไดนามิกไทม์วอร์ปปิง คือ เพื่อเปรียบเทียบลำดับที่ขึ้นอยู่กับเวลาสองชุด
- ด้วยความยาว ซึ่งเป็นจำนวนเต็ม
- ด้วยความยาว ซึ่งเป็นจำนวนเต็ม
โดยลำดับเหล่านี้อาจจะเป็นสัญญาณที่ไม่ต่อเนื่อง (อนุกรมเวลา) หรือ ลำดับของลักษณะเฉพาะ (feature) ที่ถูกสร้างขึ้นตามช่วงเวลา กำหนดให้ปริภูมิของลักษณะเฉพาะแทนด้วย ดังนั้น สำหรับ และ เพื่อที่จะเปรียบเทียบลักษณะเฉพาะ จึงจำเป็นที่จะต้องคำนวณต้นทุนเฉพาะส่วน (local cost measure) หรือเรียกอีกอย่างได้ว่า การคำนวณระยะทางเฉพาะส่วน (local distance measure) ซึ่งนิยามได้เป็นฟังก์ชัน ซึ่งโดยทั่วไป จะมีค่าน้อย ถ้า และ มีความคล้ายกันมาก ซึ่งสำหรับแต่ละคู่ของลำดับทั้งสอง นำไปสร้าง เมทริกซ์ต้นทุน (cost matrix) นิยามด้วย ดังรูป

โดยเป้าหมายต่อไปคือการหาวิถีการปรับแนวระหว่าง และ ที่มีต้นทุนรวมน้อยที่สุด โดยปกติแล้ว วิถีการปรับแนว จะวิ่งไปตามทางที่ต้นทุนต่ำภายในเมทริกซ์ต้นทุน ด้วยรูปแบบดังนี้
เส้นทางบิดเบือน เป็นลำดับ และ สำหรับ จะสนใจเงื่อนไขดังต่อไปนี้
- เงื่อนไขขอบเขต (Boundary condition) : และ
- เงื่อนไขทางเดียว (Monotonicity condition) : และ
- เงื่อนไขขนาดการเดิน (step size condition) : สำหรับ
ซึ่งจะได้ตัวอย่างของเส้นทางบิดเบือนแบบต่างๆภายใต้เงื่อนไขดังรูป
โดยต้นทุนทั้งหมดของเส้นทางบิดเบือน ระหว่าง และ ซึ่งเกี่ยวเนื่องกับการวัดต้นทุนเฉพาะส่วน จะถูกนิยามด้วย
สำหรับ เส้นทางบิดเบือนที่เหมาะสมระหว่าง และ คือระยะทางบิดเบือน ซึ่งมีต้นทุกต่ำที่สุดเมื่อเทียบกับเส้นทางบิดเบือนทั้งหมดที่เป็นไปได้ ระยะทางไดนามิกไทม์วอร์ปปิง ระหว่าง และ จะถูกนิยามเป็นต้นทุนทั้งหมดของ โดย
เป็นเส้นทางบิดเบือน |
ซึ่งสุดท้ายแล้วจะได้ระยะทางบิดเบือนที่เหมาะสมดังรูป

ความซับซ้อนเชิงเวลา[แก้]
ขั้นตอนวิธีไดนามิกไทม์วอร์ปปิงแบบทั่วไปจะมีอัตราการเติบโตแบบชี้กำลัง แต่เมื่อใช้กำหนดการพลวัตในการแก้ปัญหาจะมีความซับซ้อนเชิงเวลาเป็น เมื่อ และ แทนความยาวของข้อมูลในแต่ละลำดับ
การประยุกต์ใช้และโอเพนซอร์ซที่เกี่ยวข้อง[แก้]
- lbimproved ไลบรารีภาษา C++ ได้นำเอาขั้นตอนวิธี Fast Nearest-Neighbor Retrieval มาใช้ภายใต้ไดนามิกส์ไทม์วอร์ปปิง (GPL) อีกทั้งยังได้จัดเตรียมไดนามิกส์ไทม์วอร์ปปิงไว้ให้ใช้ด้วยภาษา C++
- R package dtw ได้นำเอาขั้นตอนวิธีในตระกูลไดนามิกไทม์วอร์ปปิงหลากหลายรูปแบบมาใช้งาน รวมไปถึงกฎการเรียกซ้ำ และการจับคู่สายอักขระย่อย
- mlpy เก็บถาวร 2011-09-19 ที่ เวย์แบ็กแมชชีน ไลบรารี ภาษา Python ซึ่งได้นำเอาขั้นตอนวิธีไดนามิกไทม์วอร์ปปิงมาใช้
- kinectdtw เก็บถาวร 2011-09-25 ที่ เวย์แบ็กแมชชีน โอเพนซอร์ซ เกี่ยวกับการรู้จำท่าทางที่ได้นำเอาขั้นตอนวิธีไดนามิกไทม์วอร์ปปิงมาใช้
- Chula Engineering Newsletter เก็บถาวร 2016-03-05 ที่ เวย์แบ็กแมชชีน วารสารทางวิชาการของคณะวิศวกรรมศาสตร์ จุฬาลงกรณ์มหาวิทยาลัย ซึ่งได้กล่าวถึงการนำไดนามิกไทม์วอร์ปปิงไปประยุกต์ใช้ในด้านต่างๆ เช่น ค้นหาฐานข้อมูล การรู้จำเสียงพูด วิเคราะห์ข้อมูลทางสถิติ
ดูเพิ่ม[แก้]
อ้างอิง[แก้]
- Sakoe, H. and Chiba, S., Dynamic programming algorithm optimization for spoken word recognition, IEEE Transactions on Acoustics, Speech and Signal Processing, 26 (1) pp. 43- 49, 1978, ISSN: 0096-3518
- C. S. Myers and L. R. Rabiner.
A comparative study of several dynamic time-warping algorithms for connected word recognition.
The Bell System Technical Journal, 60 (7) :1389-1409, September 1981. - L. R. Rabiner and B. Juang.
Fundamentals of speech recognition.
Prentice-Hall, Inc., 1993 (Chapter 4) - Müller, Meinard, Information Retrieval for Music and Motion, 2007 (Chapter 4)
- เทคนิคการใช้ไดนามิกไทม์วอร์ปปิงในการทำเหมืองข้อมูลอนุกรมเวลา Time Series Mining using Dynamic Time Warping Technique, Chula Engineering Newsletter เก็บถาวร 2016-03-05 ที่ เวย์แบ็กแมชชีน