ग्राफिकल टाइम वार्पिंग (GTW) समय श्रृंखलाओं या अनुक्रमों के कई जोड़ों को संयुक्त रूप से संरेखित करने के लिए एक ढांचा है। डायनामिक टाइम वार्पिंग (DTW) के विपरीत, जो प्रत्येक जोड़ी को स्वतंत्र रूप से केवल दिए गए जोड़ी में दो अनुक्रमों के बीच की दूरी को न्यूनतम करके संरेखित करता है, GTW प्रत्येक अनुक्रम जोड़ी की संरेखण सटीकता और जोड़ों के बीच समानता दोनों पर विचार करता है। यह संयुक्त अनुकूलन GTW को बेहतर संरेखण प्रदर्शन प्राप्त करने की अनुमति देता है जब जोड़ों के बीच समानता की अपेक्षा होती है, जो DTW को एक विशेष मामले के रूप में सामान्यीकृत करता है।
यह ढांचा किसी भी डेटा पर लागू होता है जो परस्पर निर्भर समय श्रृंखलाओं या अनुक्रमों के साथ संरचित होता है। अनुप्रयोगों में समय-चूक बायो-इमेजिंग डेटा में सिग्नल प्रसार विश्लेषण, हस्ताक्षर पहचान, दूरबीन स्टीरियो गहराई गणना, और प्रोटियोमिक्स डेटा विश्लेषण में लिक्विड क्रोमैटोग्राफी-मास स्पेक्ट्रोमेट्री(LC-MS) प्रोफाइल संरेखण शामिल हैं। इन सेटिंग्स में, आसन्न या संबंधित अनुक्रम अक्सर समान वार्पिंग पैटर्न प्रदर्शित करते हैं, जिसका GTW संरेखण गुणवत्ता में सुधार के लिए लाभ उठाता है।
सूत्रीकरण
GTW संयुक्त संरेखण समस्या को वार्पिंग पथों के एक सेट पर न्यूनतमकरण के रूप में सूत्रबद्ध करता है। दिए गए \(N\) समय श्रृंखलाओं के जोड़े \((x_n, y_n)\) के लिए \(n = 1, 2, ..., N\), प्रत्येक जोड़ी का एक संगत वार्पिंग पथ \(P_n\) होता है। कुछ वार्पिंग पथों के जोड़े समान होने के लिए जाने जाते हैं, जिन्हें सेट \(Neib\) द्वारा दर्शाया गया है। उद्देश्य न्यूनतम करना है:
\[\min_{\{P_n\}}} \left( \sum_{n=1}^{N} cost(P_n)) + \kappa \sum_{(m,n) \in Neib} dist(P_m, P_n) \right)\]
यहाँ, \(cost(P_n)\) \(x_n\) और \(y_n\) के बीच की दूरी है जो वार्पिंग फ़ंक्शन \(P_n\) के साथ संरेखण के बाद है। शब्द \(dist(P_m, P_n)\) दो वार्पिंग पथों के बीच की दूरी को मापता है, जिसे \(P_m\) और \(P_n\) द्वारा घिरे क्षेत्र के क्षेत्रफल के रूप में परिभाषित किया गया है। हाइपरपैरामीटर \(\kappa\) संरेखण लागत शब्द और वार्पिंग फ़ंक्शन दूरी शब्द को संतुलित करता है। समानता की ताकत अनुप्रयोग-विशिष्ट हो सकती है; विभिन्न संबंधित जोड़ों \((m, n)\) के लिए, विभिन्न पैरामीटर \(\kappa_{(m,n)}\) सेट किए जा सकते हैं।
डायनामिक टाइम वार्पिंग से संबंध
डायनामिक टाइम वार्पिंग दो समय श्रृंखलाओं को संरेखित करने के लिए एक शास्त्रीय तकनीक है जो संचयी दूरी को न्यूनतम करने वाले एक इष्टतम वार्पिंग पथ को खोजती है। DTW प्रत्येक जोड़ी को स्वतंत्र रूप से मानता है, एक ग्रिड में सबसे छोटा पथ समस्या को हल करता है। GTW इसका विस्तार करता है कई वार्पिंग पथों को उनकी जोड़ीवार दूरियों पर एक दंड के माध्यम से जोड़कर। जब \(\kappa = 0\), GTW प्रत्येक जोड़ी के लिए स्वतंत्र DTW में कम हो जाता है। जब \(\kappa > 0\), वार्पिंग पथों को समान होने के लिए प्रोत्साहित किया जाता है, जो लाभकारी है जब अंतर्निहित अनुक्रम सामान्य अस्थायी विकृतियों को साझा करते हैं।
अधिकतम प्रवाह के माध्यम से समाधान
GTW DTW-समतुल्य सबसे छोटा पथ समस्या को द्वैत ग्राफ में अधिकतम प्रवाह समस्या में बदल देता है। वार्पिंग पथों के बीच बाधाएं या समानताएं अतिरिक्त किनारों या क्षमताओं के रूप में मॉडल की जाती हैं। यह द्वैत ग्राफ सूत्रीकरण संयुक्त अनुकूलन को मानक अधिकतम-प्रवाह एल्गोरिदम का उपयोग करके हल करने की अनुमति देता है। हालांकि, बड़े डेटासेट के लिए, सामान्य अधिकतम-प्रवाह एल्गोरिदम समय-ग्राही और मेमोरी-गहन हो जाते हैं।
स्केलेबिलिटी को संबोधित करने के लिए, एक कुशल एल्गोरिदम जिसे बिडायरेक्शनल पुशिंग विथ लीनियर कंपोनेंट ऑपरेशंस(BILCO) कहा जाता है, विशेष रूप से GTW के लिए विकसित किया गया था। BILCO द्वैत ग्राफ की संरचना का लाभ उठाता है और GTW अनुप्रयोगों में अत्याधुनिक सामान्य अधिकतम प्रवाह एल्गोरिदम की तुलना में औसत 10-गुना सुधार प्राप्त करता है गणना समय और मेमोरी उपयोग दोनों में।
अनुप्रयोग
GTW कई डोमेन में लागू किया गया है जहां परस्पर निर्भर समय श्रृंखलाएं उत्पन्न होती हैं:
- समय-चूक बायो-इमेजिंग में सिग्नल प्रसार विश्लेषण: आसन्न पिक्सेल अक्सर समान प्रसार पैटर्न दिखाते हैं, जिससे GTW वेवफ्रंट्स या सेलुलर सिग्नल्स को ट्रैक करने के लिए उपयुक्त बनाता है।
- हस्ताक्षर पहचान: हस्तलिखित हस्ताक्षर अनुक्रमों के रूप में माने जा सकते हैं; कई हस्ताक्षरों को संयुक्त रूप से संरेखित करने से पहचान में सुधार होता है।
- दूरबीन स्टीरियो गहराई गणना: बाएं और दाएं छवियों से विसंगति मानचित्रों को GTW के साथ संरेखित किया जा सकता है गहराई अनुमान में सुधार के लिए।
- प्रोटियोमिक्स में LC-MS प्रोफाइल संरेखण: कई नमूनों से क्रोमैटोग्राफिक और मास स्पेक्ट्रोमेट्रिक प्रोफाइल प्रतिधारण समय बदलावों को सही करने के लिए संयुक्त संरेखण से लाभान्वित होते हैं।
इन अनुप्रयोगों में साझा गुण यह है कि अनुक्रम स्वतंत्र नहीं हैं बल्कि स्थानिक या अस्थायी सहसंबंध प्रदर्शित करते हैं जिनका GTW लाभ उठाता है।