अलग-अलग लंबाई के साथ समय-अनुक्रमित डेटा की समानता माप - एल्गोरिदम, गतिशील-प्रोग्रामिंग

निम्नलिखित आंकड़ों पर विचार करें।

Groundtruth      |  Dataset1         |  Dataset2         |  Dataset3
Datapoints|Time  |  Datapoints|Time  |  Datapoints|Time  |  Datapoints|Time
A     |0     |      a     |0     |      a     |0     |      a     |0
B     |10    |      b     |5     |      b     |5     |      b     |13
C     |15    |      c     |12    |      c     |12    |      c     |21
D     |25    |      d     |22    |      d     |14    |      d     |30
E     |30    |      e     |30    |      e     |17    |
|                   |      f     |27    |
|                   |      g     |30    |

इस तरह से कल्पना की गई (जैसा कि प्रत्येक पहचानकर्ता के बीच -):

Time ->
Groundtruth: A|----------|B|-----|C|----------|D|-----|E
Dataset1:    a|-----|b|-------|c|----------|d|--------|e
Dataset2:    a|-----|b|-------|c|--|d|---|e|----------|f|---|g
Dataset3:    a|-------------|b|--------|c|---------|d

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

मैं पहले से ही एक उत्पन्न करने के लिए एक जेकार्ड इंडेक्स बनाया हैबुनियादी मूल्यांकन स्कोर। लेकिन मैं अब एक मूल्यांकन पद्धति पर विचार कर रहा हूं जो डेटा पॉइंट्स की बहुतायत / अनुपस्थिति को दंडित करता है और साथ ही दूरी को एक सही डेटा पॉइंट तक सीमित करता है। यही है, b doesn "t को B से मेल खाना है, बस एक सही डेटापॉइंट के करीब होना है।

मैंने एक गतिशील प्रोग्रामिंग में देखने की कोशिश की हैवह विधि जहाँ मैंने एक डाटापॉइंट को हटाने या जोड़ने के लिए एक दंड पेश किया और साथ ही निकटतम डाटापॉइंट पर जाने के लिए दूरी का दंड दिया। मैं हालांकि, के कारण संघर्ष कर रहा हूँ: 1. मुझे प्रत्येक डेटापॉइंट को एक सही डेटापॉइंट तक सीमित करने की आवश्यकता है 2. यदि आवश्यक हो तो डिलीट करने के लिए कौन सा डेटापॉइंट करें 3. डीपी एल्गोरिदम को लागू करने के तरीके में सामान्य कमी

किसी को भी यह कैसे करना है विचार है? अगर गतिशील प्रोग्रामिंग जाने का रास्ता है, तो मुझे कुछ लिंक की सिफारिश के साथ-साथ कुछ संकेत भी मिलते हैं कि कैसे जाना चाहिए।

उत्तर:

मूल रूप से, आप लेवेंशेटिन के लिए डीपी को संशोधित कर सकते हैंअपनी समस्या के लिए दूरी की गणना करने के लिए दूरी संपादित करें। Levenshtein DP एक ऐसी चक्रीय निर्देशित ग्राफ में सबसे छोटे रास्तों को खोजने के लिए है जो इस तरह दिखता है

*-*-*-*-*
|||||
*-*-*-*-*
|||||
*-*-*-*-*

जहाँ आर्क्स बाएं-से-दाएँ ओर उन्मुख होते हैंऊपर से नीचे। DAG में पंक्तियों की संख्या 0 से m और स्तंभों की संख्या 0 से n तक है, जहाँ m पहले अनुक्रम की लंबाई है, और n की लंबाई दूसरी है। पहले अनुक्रम को दूसरे से एक-से-एक (लागत और सभी) को ऊपरी बाएं से निचले दाईं ओर के रास्तों में बदलने के लिए निर्देशों की सूची। (I, j) से (i + 1, j) का चाप i को हटाने के निर्देश से मेल खाता है^वें पहले अनुक्रम से तत्व। (I, j) से (i, j + 1) का चाप j जोड़ने के निर्देश से मेल खाता है^वें दूसरे क्रम से तत्व। (I, j) से चाप i को संशोधित करने से मेल खाती है^वें जे बनने के लिए पहले अनुक्रम का तत्व^वें दूसरे क्रम का तत्व।

आपको बस एक द्विघात-समय प्राप्त करने के लिए करना होगाआपकी समस्या के लिए एल्गोरिथ्म (i) एक डेटापॉइंट (ii) डेटापॉइंट को हटाने (iii) को जोड़ने के लिए एक डेटामैप को संशोधित करने के लिए एक और डेटापॉइंट को संशोधित करने और फिर एक में डीएजी पर सबसे छोटे रास्तों की गणना करना है। विकिपीडिया द्वारा वर्णित तरीके.

(एक तरफ के रूप में, यह एल्गोरिथ्म मानता है कि यह हैउन संशोधनों को बनाने के लिए लाभदायक नहीं है जो एक दूसरे को "पार" करते हैं। संशोधन लागतों के बारे में काफी हल्की धारणा के तहत, यह धारणा बहुत ही कम है। यदि आप अधिक जानकारी में रुचि रखते हैं, तो मेरा यह उत्तर देखें: घटनाओं की दो सूचियों का अनुमानित मिलान (अवधि के साथ) ।)