algorithm
गतिशील समय ताना

डायनामिक टाइम वारिंग का परिचय

डायनेमिक टाइम वार्पिंग (DTW) दो अस्थायी अनुक्रमों के बीच समानता को मापने के लिए एक एल्गोरिथ्म है जो गति में भिन्न हो सकता है। उदाहरण के लिए, चलने में समानता का पता डीटीडब्ल्यू का उपयोग करके लगाया जा सकता है, भले ही एक व्यक्ति दूसरे की तुलना में तेजी से चल रहा हो, या अवलोकन के दौरान त्वरण और गिरावट हो। इसका उपयोग दूसरों के साथ एक नमूना वॉयस कमांड को मैच करने के लिए किया जा सकता है, भले ही वह व्यक्ति पहले से तय नमूना आवाज की तुलना में तेज या धीमी बात करता हो। DTW को वीडियो, ऑडियो और ग्राफिक्स डेटा के अस्थायी अनुक्रमों पर लागू किया जा सकता है-वास्तव में, किसी भी डेटा को एक रैखिक अनुक्रम में बदल दिया जा सकता है, जिसका विश्लेषण DTW के साथ किया जा सकता है।

सामान्य तौर पर, DTW एक ऐसी विधि है जो कुछ निश्चित प्रतिबंधों के साथ दो दिए गए अनुक्रमों के बीच एक इष्टतम मैच की गणना करती है। लेकिन चलो यहाँ सरल बिंदुओं से चिपके रहते हैं। मान लीजिए, हमारे पास दो ध्वनि अनुक्रम नमूने और परीक्षण हैं , और हम जांचना चाहते हैं कि ये दो क्रम मेल खाते हैं या नहीं। यहां वॉयस सीक्वेंस आपकी आवाज के परिवर्तित डिजिटल सिग्नल को दर्शाता है। यह आपकी आवाज़ का आयाम या आवृत्ति हो सकती है जो आपके द्वारा कहे गए शब्दों को दर्शाता है। चलो मान लो:

Sample = {1, 2, 3, 5, 5, 5, 6}
Test   = {1, 1, 2, 2, 3, 5}

हम इन दो अनुक्रमों के बीच इष्टतम मैच का पता लगाना चाहते हैं।

सबसे पहले, हम दो बिंदुओं के बीच की दूरी को परिभाषित करते हैं, d (x, y) जहां x और y दो बिंदुओं का प्रतिनिधित्व करते हैं। चलो,

d(x, y) = |x - y|     //absolute difference

आइए इन दो अनुक्रमों का उपयोग करके 2 डी मैट्रिक्स तालिका बनाएं। हम परीक्षण के हर बिंदु के साथ नमूना के प्रत्येक बिंदु के बीच की दूरी की गणना करेंगे और उनके बीच इष्टतम मिलान पाएंगे।

+------+------+------+------+------+------+------+------+
|      |   0  |   1  |   1  |   2  |   2  |   3  |   5  |
+------+------+------+------+------+------+------+------+
|   0  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   1  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   2  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   3  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   6  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+

यहां, टेबल [i] [j] दो अनुक्रमों के बीच की इष्टतम दूरी का प्रतिनिधित्व करता है यदि हम नमूना [i] और परीक्षण [j] तक के अनुक्रम पर विचार करते हैं, तो उन सभी इष्टतम दूरी पर विचार करते हैं जिन्हें हमने पहले देखा था।

पहली पंक्ति के लिए, यदि हम नमूना से कोई मूल्य नहीं लेते हैं, तो इस और टेस्ट के बीच की दूरी अनंत होगी। इसलिए हमने पहली पंक्ति में अनन्तता रखी। वही पहले कॉलम के लिए जाता है। यदि हम टेस्ट से कोई मूल्य नहीं लेते हैं, तो इस एक और नमूना के बीच की दूरी भी अनंत होगी। और 0 और 0 के बीच की दूरी बस 0 हो जाएगा। हमें मिला,

+------+------+------+------+------+------+------+------+
|      |   0  |   1  |   1  |   2  |   2  |   3  |   5  |
+------+------+------+------+------+------+------+------+
|   0  |   0  |  inf |  inf |  inf |  inf |  inf |  inf |
+------+------+------+------+------+------+------+------+
|   1  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   2  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   3  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   6  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+

अब प्रत्येक चरण के लिए, हम चिंता में प्रत्येक बिंदुओं के बीच की दूरी पर विचार करेंगे और इसे अब तक मिली न्यूनतम दूरी के साथ जोड़ेंगे। यह हमें उस स्थिति तक दो अनुक्रमों की इष्टतम दूरी देगा। हमारा सूत्र होगा,

Table[i][j] := d(i, j) + min(Table[i-1][j], Table[i-1][j-1], Table[i][j-1])

पहले एक के लिए, डी (1, 1) = 0 , टेबल [0] [0] न्यूनतम का प्रतिनिधित्व करता है। तो तालिका [1] [१] का मान ० + ० = ० होगा । दूसरे के लिए, डी (1, 2) = 0 । तालिका [1] [१] न्यूनतम का प्रतिनिधित्व करती है। मान होगा: तालिका [1] [२] = ० + ० = ० । यदि हम इस तरह जारी रखते हैं, तो परिष्करण के बाद, तालिका इस तरह दिखाई देगी:

+------+------+------+------+------+------+------+------+
|      |   0  |   1  |   1  |   2  |   2  |   3  |   5  |
+------+------+------+------+------+------+------+------+
|   0  |   0  |  inf |  inf |  inf |  inf |  inf |  inf |
+------+------+------+------+------+------+------+------+
|   1  |  inf |   0  |   0  |   1  |   2  |   4  |   8  |
+------+------+------+------+------+------+------+------+
|   2  |  inf |   1  |   1  |   0  |   0  |   1  |   4  |
+------+------+------+------+------+------+------+------+
|   3  |  inf |   3  |   3  |   1  |   1  |   0  |   2  |
+------+------+------+------+------+------+------+------+
|   5  |  inf |   7  |   7  |   4  |   4  |   2  |   0  |
+------+------+------+------+------+------+------+------+
|   5  |  inf |  11  |  11  |   7  |   7  |   4  |   0  |
+------+------+------+------+------+------+------+------+
|   5  |  inf |  15  |  15  |  10  |  10  |   6  |   0  |
+------+------+------+------+------+------+------+------+
|   6  |  inf |  20  |  20  |  14  |  14  |   9  |   1  |
+------+------+------+------+------+------+------+------+

तालिका [7] [6] का मान इन दोनों दिए गए अनुक्रमों के बीच की अधिकतम दूरी को दर्शाता है। यहाँ 1 नमूना और परीक्षण के बीच की अधिकतम दूरी का प्रतिनिधित्व करता है 1 ।

अब अगर हम अंतिम बिंदु से पीछे हटते हैं, तो सभी रास्ते शुरू (0, 0) बिंदु की ओर लौटते हैं, हमें एक लंबी रेखा मिलती है जो क्षैतिज, लंबवत और तिरछे चलती है। हमारे पीछे हटने की प्रक्रिया होगी:

if Table[i-1][j-1] <= Table[i-1][j] and Table[i-1][j-1] <= Table[i][j-1]
    i := i - 1
    j := j - 1
else if Table[i-1][j] <= Table[i-1][j-1] and Table[i-1][j] <= Table[i][j-1]
    i := i - 1
else
    j := j - 1
end if

हम (0, 0) तक पहुंचने तक इसे जारी रखेंगे। प्रत्येक चाल का अपना अर्थ होता है:

• एक क्षैतिज चाल विलोपन का प्रतिनिधित्व करती है। इसका मतलब है कि इस अंतराल के दौरान हमारे टेस्ट अनुक्रम में तेजी आई है।
• एक ऊर्ध्वाधर चाल सम्मिलन का प्रतिनिधित्व करती है। इसका मतलब है कि इस अंतराल के दौरान टेस्ट सीक्वेंस को घटा दिया गया है।
• एक विकर्ण चाल मैच का प्रतिनिधित्व करती है। इस अवधि के दौरान परीक्षण और नमूना समान थे।

हमारा छद्म कोड होगा:

Procedure DTW(Sample, Test):
n := Sample.length
m := Test.length
Create Table[n + 1][m + 1]
for i from 1 to n
    Table[i][0] := infinity
end for
for i from 1 to m
    Table[0][i] := infinity
end for
Table[0][0] := 0
for i from 1 to n
    for j from 1 to m
        Table[i][j] := d(Sample[i], Test[j])
                       + minimum(Table[i-1][j-1],      //match
                                 Table[i][j-1],        //insertion
                                 Table[i-1][j])        //deletion
    end for
end for
Return Table[n + 1][m + 1]

हम एक स्थानीयता बाधा भी जोड़ सकते हैं। यही है, हमें यह आवश्यक है कि यदि Sample[i] का मिलान Test[j] , तो |i - j| w से बड़ा कोई विंडो पैरामीटर नहीं है।

जटिलता:

DTW कंप्यूटिंग की जटिलता O (m * n) है जहाँ m और n प्रत्येक अनुक्रम की लंबाई का प्रतिनिधित्व करते हैं। DTW कंप्यूटिंग के लिए तेज़ तकनीकों में PrunedDTW, SparseDTW और FastDTW शामिल हैं।

अनुप्रयोग:

• बोला शब्द मान्यता
• सहसंबंध शक्ति विश्लेषण