التواء زمني ديناميكي

في تحليل السلاسل الزمنية ، يُعدّ التواء الزمن الديناميكي ( DTW ) خوارزمية لقياس التشابه بين سلسلتين زمنيتين، قد تختلفان في السرعة. على سبيل المثال، يمكن الكشف عن أوجه التشابه في المشي باستخدام DTW، حتى لو كان أحد الأشخاص يمشي أسرع من الآخر، أو إذا كانت هناك تسارعات وتباطؤات أثناء الملاحظة. طُبّق DTW على السلاسل الزمنية لبيانات الفيديو والصوت والرسومات - في الواقع، يمكن تحليل أي بيانات يمكن تحويلها إلى سلسلة أحادية البعد باستخدام DTW. من التطبيقات المعروفة التعرف التلقائي على الكلام ، للتعامل مع سرعات الكلام المختلفة. تشمل التطبيقات الأخرى التعرف على المتحدث والتعرف على التوقيعات عبر الإنترنت . كما يمكن استخدامه في تطبيقات مطابقة الأشكال الجزئية.

بشكل عام، DTW هي طريقة لحساب التطابق الأمثل بين سلسلتين معطيتين (مثل السلاسل الزمنية ) مع قيود وقواعد معينة:

• يجب مطابقة كل فهرس من التسلسل الأول مع فهرس واحد أو أكثر من التسلسل الآخر، والعكس صحيح.
• يجب مطابقة الفهرس الأول من التسلسل الأول مع الفهرس الأول من التسلسل الآخر (ولكن ليس بالضرورة أن يكون هو التطابق الوحيد).
• يجب مطابقة الفهرس الأخير من التسلسل الأول مع الفهرس الأخير من التسلسل الآخر (ولكن ليس بالضرورة أن يكون هو التطابق الوحيد).
• يجب أن يكون ربط المؤشرات من التسلسل الأول بالمؤشرات من التسلسل الآخر متزايدًا بشكل رتيب، والعكس صحيح، أي إذا${\displaystyle j>i}$إذا كانت المؤشرات من التسلسل الأول، فلا بد من عدم وجود مؤشرين.${\displaystyle l>k}$في التسلسل الآخر، بحيث يكون المؤشر${\displaystyle i}$يتم مطابقته مع الفهرس${\displaystyle l}$والفهرس${\displaystyle j}$يتم مطابقته مع الفهرس${\displaystyle k}$والعكس صحيح

يمكننا رسم كل تطابق بين التسلسلات${\displaystyle 1:M}$و${\displaystyle 1:N}$كمسار في${\displaystyle M\times N}$المصفوفة من${\displaystyle (1,1)}$ل${\displaystyle (M,N)}$بحيث تكون كل خطوة واحدة من${\displaystyle (0,1),(1,0),(1,1)}$في هذه الصيغة، نرى أن عدد التطابقات الممكنة هو عدد ديلانوي .

يُشار إلى التطابق الأمثل بالتطابق الذي يفي بجميع القيود والقواعد والذي له أقل تكلفة، حيث يتم حساب التكلفة على أنها مجموع الفروق المطلقة ، لكل زوج متطابق من المؤشرات، بين قيمها.

تُشوّه المتتاليات بشكل غير خطي في بُعد الزمن لتحديد مقياس تشابهها بمعزل عن بعض التغيرات غير الخطية في بُعد الزمن. تُستخدم طريقة محاذاة المتتاليات هذه غالبًا في تصنيف السلاسل الزمنية. مع أن DTW يقيس كمية شبيهة بالمسافة بين متتاليتين معطيتين، إلا أنه لا يضمن تحقق متباينة المثلث .

إضافةً إلى قياس التشابه بين التسلسلين (ينتج عنه ما يُسمى "مسار التشويه")، يُمكن من خلال التشويه وفقًا لهذا المسار محاذاة الإشارتين زمنيًا. تُحوَّل الإشارة ذات المجموعة الأصلية من النقاط X (الأصلية)، Y (الأصلية) إلى X (المشوهة)، Y (المشوهة). يُستخدم هذا في مزامنة التسلسلات الجينية والصوتية. في تقنية ذات صلة، يُمكن حساب متوسط ​​التسلسلات ذات السرعات المختلفة باستخدام هذه التقنية، انظر قسم التسلسل المتوسط .

وهذا يشبه من الناحية المفاهيمية خوارزمية نيدلمان-وونش .

يوضح هذا المثال تطبيق خوارزمية مطابقة الوقت الديناميكية عندما تكون المتتاليتان s و t عبارة عن سلاسل من الرموز المنفصلة. بالنسبة للرمزين x و y ،${\displaystyle d(x,y)}$المسافة بين الرموز، على سبيل المثال،${\displaystyle d(x,y)=|xy|}$.

int DTWDistance(s: array [1..n], t: array [1..m]) { DTW := array [0..n, 0..m] من أجل i := 0 إلى n من أجل j := 0 إلى m DTW[i, j] := ما لا نهاية DTW[0, 0] := 0 من أجل i := 1 إلى n لكل j := 1 إلى m التكلفة := د(s[i]، ت[j]) DTW[i, j] := cost + minimum(DTW[i-1, j ], // إدراج DTW[i , j-1], // حذف DTW[i-1, j-1]) // تطابق أعد DTW[n, m] }

أين DTW[i, j]تقع المسافة بينهما s[1:i]مع t[1:j]أفضل محاذاة؟

نرغب أحيانًا في إضافة قيد مكاني. أي أننا نشترط أنه إذا s[i]تطابق مع t[j]، فإن${\displaystyle |ij|}$لا يتجاوز حجمه w ، وهو مُعامل نافذة.

يمكننا بسهولة تعديل الخوارزمية المذكورة أعلاه لإضافة قيد الموضع (الاختلافات).ملحوظومع ذلك، فإن التعديل المذكور أعلاه لا يعمل إلا إذا${\displaystyle |nm|}$لا تتجاوز قيمة قيمة w ، أي أن نقطة النهاية تقع ضمن طول النافذة من القطر. ولجعل الخوارزمية تعمل، يجب تعديل معلمة النافذة w بحيث${\displaystyle |nm|\leq w}$(انظر السطر المميز بعلامة (*) في الكود).

int DTWDistance(s: array [1..n], t: array [1..m]، w: عدد صحيح) { DTW := array [0..n, 0..m] w := max(w, abs(nm))// تعديل حجم النافذة (*) من أجل i := 0 إلى n من أجل j:= 0 إلى m DTW[i, j] := ما لا نهاية DTW[0, 0] := 0 من أجل i := 1 إلى nfor j := max(1, iw) to min(m, i+w)DTW[i, j] := 0 من أجل i := 1 إلى n for j :=max(1, iw) to min(m, i+w) التكلفة := د(s[i]، ت[j]) DTW[i, j] := cost + minimum(DTW[i-1, j ], // إدراج DTW[i , j-1], // حذف DTW[i-1, j-1]) // تطابق أعد DTW[n, m] }

تُنتج خوارزمية DTW مطابقة منفصلة بين العناصر الموجودة في سلسلة ما وأخرى. بعبارة أخرى، لا تسمح بتغيير المقياس الزمني للقطاعات داخل التسلسل. بينما تسمح طرق أخرى بالتشويه المستمر. على سبيل المثال، يقسم التشويه الأمثل بالارتباط (COW) التسلسل إلى قطاعات متساوية يتم تغيير مقياسها زمنيًا باستخدام الاستيفاء الخطي، لإنتاج أفضل مطابقة ممكنة. يؤدي تغيير مقياس القطاعات إلى إمكانية إنشاء عناصر جديدة، من خلال تغيير المقياس الزمني للقطاعات إما بالزيادة أو النقصان، وبالتالي ينتج عنه تشويه أكثر حساسية من المطابقة المنفصلة للعناصر الأصلية في خوارزمية DTW.

التعقيد الزمني لخوارزمية DTW هو${\displaystyle O(NM)}$، أين${\displaystyle N}$و${\displaystyle M}$يمثلان طولَي سلسلتي الإدخال. وقد تم تجاوز الحد الزمني التربيعي الذي دام 50 عامًا في عام 2016: إذ مكّنت خوارزمية من ابتكار غولد وشارير من حساب DTW في${\displaystyle O({N^{2}}/\log \log N)}$الوقت والمساحة اللازمين لتسلسلين من المدخلات بطول${\displaystyle N}$[ ^{2 ] يمكن أيضًا تكييف هذه الخوارزمية مع متواليات ذات أطوال مختلفة. على الرغم من هذا التحسين، فقد تبين أن زمن التشغيل شبه} التربيعي القوي من الشكل${\displaystyle O(N^{2-\epsilon })}$بالنسبة للبعض${\displaystyle \epsilon >0}$لا يمكن أن يوجد إلا إذا فشلت فرضية الزمن الأسي القوي . ^{[ 3 ] [ 4 ]}

بينما تتطلب خوارزمية البرمجة الديناميكية لـ DTW${\displaystyle O(NM)}$في تطبيق بسيط، يمكن تقليل استهلاك المساحة إلى${\displaystyle O(\min(N,M))}$باستخدام خوارزمية هيرشبيرج .

تشمل التقنيات السريعة لحساب DTW كلاً من PrunedDTW، ^{[ 5 ]} وSparseDTW، ^{[ 6 ]} و FastDTW، ^{[ 7 ]} وMultiscaleDTW. ^{[ 8 ] [ 9 ]}

يمكن تسريع مهمة شائعة، وهي استرجاع السلاسل الزمنية المتشابهة، باستخدام حدود دنيا مثل LB_Keogh، ^{[ 10 ]} وLB_Improved، ^{[ 11 ]} أو LB_Petitjean. ^{[ 12 ]} ومع ذلك، فإن خوارزمية Early Abandon and Pruned DTW تقلل من درجة التسريع التي توفرها الحدود الدنيا، وفي بعض الأحيان تجعلها غير فعالة.

في دراسة استقصائية، أفاد وانغ وزملاؤه بتحقيق نتائج أفضل قليلاً باستخدام الحد الأدنى المُحسَّن (LB_Improved) مقارنةً بالحد الأدنى كيو (LB_Keogh)، ووجدوا أن التقنيات الأخرى غير فعّالة. ^{[ 13 ]} وبعد هذه الدراسة، طُوِّر الحد الأدنى المُعزَّز (LB_Enhanced) الذي يُعدّ دائمًا أدق من الحد الأدنى كيو (LB_Keogh) وأكثر كفاءة في الحساب. ^{[ 14 ]} ويُعدّ الحد الأدنى بيتيجان (LB_Petitjean) أدق حد أدنى معروف يُمكن حسابه في وقت خطي. ^{[ 12 ]}

تُعدّ عملية حساب المتوسط ​​في تقنية مطابقة الوقت الديناميكية (DTW) مسألة إيجاد متوسط ​​تسلسل لمجموعة من التسلسلات. تُعتبر خوارزمية NLAAF ^{[ 15 ]} طريقة دقيقة لحساب متوسط ​​تسلسلين باستخدام DTW. أما بالنسبة لأكثر من تسلسلين، فتُصبح المسألة مُرتبطة بمسألة المحاذاة المتعددة وتتطلب استخدام طرق استدلالية. تُعتبر خوارزمية DBA ^{[ 16 ]} حاليًا طريقة مرجعية لحساب متوسط ​​مجموعة من التسلسلات بما يتوافق مع DTW. بينما تُجري خوارزمية COMASA ^{[ 17 ]} عملية بحث عشوائية فعّالة عن متوسط ​​التسلسل، باستخدام DBA كعملية تحسين محلية.

يمكن لمصنف أقرب جار أن يحقق أداءً متطوراً عند استخدام تقنية مطابقة الوقت الديناميكية كمقياس للمسافة. ^{[ 18 ]}

تُعدّ تقنية Amerced Dynamic Time Warping (ADTW) نسخةً مُعدّلة من تقنية DTW، مُصممة لتحسين التحكم في مدى تساهل DTW في عمليات المحاذاة المسموح بها. ^{[ 19 ]} تستخدم تقنية DTW التقليدية نوافذًا تُقيّد عمليات المحاذاة، مما يُضيف دالة خطوة . يُسمح بأي تشويه للمسار داخل النافذة، ولا يُسمح بأي تشويه خارجها. في المقابل، تستخدم ADTW عقوبةً تراكمية تُفرض في كل مرة يُشوّه فيها المسار. يُسمح بأي مقدار من التشويه، ولكن كل عملية تشويه تُفرض عليها عقوبة مباشرة. تتفوق ADTW بشكل ملحوظ على DTW مع استخدام النوافذ عند تطبيقها كمصنف أقرب جار على مجموعة من مهام تصنيف السلاسل الزمنية المعيارية. ^{[ 19 ]}

في تحليل البيانات الوظيفية ، تُعتبر السلاسل الزمنية بمثابة تجزئة لدوال زمنية سلسة (قابلة للتفاضل). من خلال النظر إلى العينات المرصودة عند هذه الدوال السلسة، يمكن استخدام الرياضيات المتصلة لتحليل البيانات. ^{[ 20 ]} يمكن الحصول على سلاسة ورتابة دوال تشويه الزمن، على سبيل المثال، عن طريق تكامل دالة أساسية شعاعية متغيرة مع الزمن، وبالتالي تكون تماثلًا تفاضليًا أحادي البعد . ^{[ 21 ]} تُحسب دوال تشويه الزمن غير الخطية المثلى عن طريق تقليل مقياس المسافة بين مجموعة الدوال ومتوسطها المشوه. يمكن إضافة حدود جزاء الخشونة لدوال التشويه، على سبيل المثال، عن طريق تقييد حجم انحنائها. دوال التشويه الناتجة سلسة، مما يسهل المعالجة اللاحقة. وقد طُبق هذا النهج بنجاح لتحليل أنماط وتغيرات حركات الكلام. ^{[ 22 ] [ 23 ]}

ومن الأساليب الأخرى ذات الصلة نماذج ماركوف المخفية (HMM)، وقد ثبت أن خوارزمية فيتربي المستخدمة للبحث عن المسار الأكثر احتمالاً عبر نموذج ماركوف المخفي تعادل خوارزمية DTW العشوائية. ^{[ 24 ] [ 25 ] [ 26 ]}

تُستخدم تقنية DTW وطرق التشويه ذات الصلة عادةً كخطوات تمهيدية أو لاحقة في تحليلات البيانات. إذا احتوت التسلسلات المرصودة على تباين عشوائي في قيمها وشكلها، بالإضافة إلى عدم محاذاة زمنية عشوائية، فقد يُفرط التشويه في ملاءمة البيانات للضوضاء، مما يؤدي إلى نتائج متحيزة. يُعدّ نموذج التزامن، الذي يتضمن تباينًا عشوائيًا في كلٍّ من القيم (الرأسية) والمعاملات الزمنية (الأفقية)، مثالًا على نموذج التأثيرات المختلطة غير الخطي . ^{[ 27 ]} في تحليل حركة الإنسان، أظهرت نماذج التأثيرات المختلطة غير الخطية المتزامنة نتائج أفضل مقارنةً بتقنية DTW. ^{[ 28 ]}

• تقوم مكتبة tempo C ++ مع روابط Python بتنفيذ Early Abandoned and Pruned DTW بالإضافة إلى Early Abandoned and Pruned ADTW و DTW lower bounds LB_Keogh و LB_Enhanced و LB_Webb.
• تقوم مكتبة UltraFastMPSearch Java بتنفيذ خوارزمية UltraFastWWSearch ^{[ 29 ]} لضبط نافذة التشويه السريع.
• تُنفّذ مكتبة lbimproved C++ خوارزميات استرجاع الجوار الأقرب السريع بموجب رخصة جنو العمومية (GPL). كما توفر تطبيقًا بلغة C++ لتقنية مطابقة الوقت الديناميكية، بالإضافة إلى حدود دنيا متنوعة.
• مكتبة FastDTW هي تطبيق جافا لخوارزمية DTW، وهي تطبيق FastDTW يوفر محاذاة مثالية أو شبه مثالية بتعقيد زمني وذاكرة من رتبة O ( N )، على عكس متطلبات O ( N² ) لخوارزمية DTW القياسية. تستخدم FastDTW منهجًا متعدد المستويات يقوم بإسقاط الحل بشكل متكرر من دقة أقل ^، ثم يُحسّن الحل المُسقط.
• تم نشر نسخة معدلة من FastDTW (جافا) على Maven Central.
• time-series-classification (Java) هي حزمة لتصنيف السلاسل الزمنية باستخدام DTW في Weka.
• توفر مجموعة DTW لحزم Python ( dtw-python ) و R ( dtw ) تغطية شاملة لأفراد عائلة خوارزمية DTW، بما في ذلك مجموعة متنوعة من قواعد التكرار (تسمى أيضًا أنماط الخطوات) والقيود ومطابقة السلاسل الفرعية.
• تُنفذ مكتبة mlpy الخاصة بلغة بايثون تقنية DTW.
• تقوم مكتبة pydtw Python بتنفيذ مقاييس DTW ذات النكهة المانهاتن والإقليدية بما في ذلك الحدود الدنيا LB_Keogh.
• تقوم مكتبة cudadtw C++/CUDA بتنفيذ محاذاة التسلسل الفرعي لـ DTW بنكهة إقليدية والمسافة الإقليدية المعيارية z على غرار UCR-Suite الشائعة على مسرعات CUDA.
• تُنفذ مكتبة JavaML للتعلم الآلي DTW .
• تُنفذ مكتبة ndtw C# تقنية DTW بخيارات متنوعة.
• يستخدم Sketch-a-Char برنامج Greedy DTW (المُنفذ بلغة JavaScript ) كجزء من برنامج تصنيف الرموز LaTeX.
• يقوم MatchBox بتطبيق DTW لمطابقة معاملات sepstral ذات التردد mel لإشارات الصوت.
• متوسط ​​التسلسل : تطبيق جافا مرخص بموجب رخصة جنو العمومية لـ DBA. ^{[ 16 ]}
• مجموعة أدوات التعرف على الإيماءات | GRT C++ مجموعة أدوات التعرف على الإيماءات في الوقت الحقيقي تنفذ DTW.
• تقوم حزمة برامج PyHubs بتنفيذ مصنفات DTW ومصنفات أقرب جار، بالإضافة إلى امتداداتها (مصنفات مدركة للمركزية).
• تُطبّق مكتبة simpledtw في بايثون خوارزمية البرمجة الديناميكية الكلاسيكية O ( NM ) وتعتمد على مكتبة Numpy . تدعم المكتبة قيمًا من أي بُعد، بالإضافة إلى استخدام دوال معيارية مخصصة للمسافات. وهي مرخصة بموجب ترخيص MIT .
• تقوم مكتبة tslearn Python بتنفيذ DTW في سياق السلاسل الزمنية.
• تُنفذ مكتبة cuTWED CUDA Python أحدث تقنيات Time Warp Edit Distance باستخدام الذاكرة الخطية فقط مع تسريع هائل.
• DynamicAxisWarping.jl هو تطبيق بلغة جوليا لخوارزمية DTW والخوارزميات ذات الصلة مثل FastDTW و SoftDTW و GeneralDTW و DTW barycenters.
• تقوم Multi_DTW بتنفيذ DTW لمطابقة مصفوفتين أحاديتي الأبعاد أو ملفين صوتيين ثنائيي الأبعاد (مصفوفة ثنائية الأبعاد).
• تتضمن حزمة dtwParallel (بايثون) الوظائف الرئيسية المتوفرة في مكتبات DTW الحالية ووظائف جديدة مثل المعالجة المتوازية، وحساب قيم التشابه (القائمة على النواة)، والنظر في البيانات ذات أنواع مختلفة من الميزات (الفئوية، والحقيقية، وما إلى ذلك). ^{[ 30 ]}

• مسافة ليفنشتاين
• مطابقة مرنة
• محاذاة التسلسل
• محاذاة التسلسل المتعدد
• خوارزمية فاغنر-فيشر
• خوارزمية نيدلمان-وونش
• مسافة فريشيه
• نموذج التأثيرات المختلطة غير الخطي

• مراجعة خوارزمية مطابقة الوقت الديناميكية لبافل سينين
• فينتسيوك، تي كيه (1968). “تمييز الكلام عن طريق البرمجة الديناميكية”. كيبرنتيكا . 4 : 81 - 88.
• ساكو، هـ.؛ تشيبا (1978). "تحسين خوارزمية البرمجة الديناميكية للتعرف على الكلمات المنطوقة". معاملات IEEE في الصوتيات والكلام ومعالجة الإشارات . 26 (1): 43-49 . doi : 10.1109/tassp.1978.1163055 . S2CID 17900407 . 
• مايرز، سي إس؛ رابينر، إل آر (1981). "دراسة مقارنة لعدة خوارزميات ديناميكية لتشويه الزمن للتعرف على الكلمات المتصلة". مجلة بيل سيستم التقنية . 60 (7): 1389-1409 . doi : 10.1002/j.1538-7305.1981.tb00272.x . ISSN 0005-8580 . S2CID 12857347 .  
• رابينر، لورانس؛ جوانغ، بينغ-هوانغ (1993). "الفصل 4: تقنيات مقارنة الأنماط". أساسيات التعرف على الكلام . إنجلوود كليفس، نيوجيرسي: بي تي آر برنتيس هول. ISBN 978-0-13-015157-5.
• مولر، مينارد (2007). مطابقة الوقت الديناميكية. في استرجاع المعلومات للموسيقى والحركة، الفصل 4، الصفحات 69-84 . سبرينغر. doi : 10.1007/978-3-540-74048-3_4 . ISBN 978-3-540-74047-6.
• راكثانمانون، ثاناوين (سبتمبر 2013). "معالجة سلاسل البيانات الزمنية الضخمة: استخراج تريليونات من التسلسلات الفرعية للسلاسل الزمنية في ظل تقنية مطابقة الوقت الديناميكية" . مجلة ACM للمعاملات في اكتشاف المعرفة من البيانات . 7 (3): 10:1–10:31. doi : 10.1145/2513092.2500489 . PMC 6790126. PMID 31607834 .