इष्टतम मिलान

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

एल्गोरिथम

मान लें $S=(s_{1},s_{2},s_{3},\ldots s_{T})$ राज्यों का क्रम हो $s_{i}$ संभावित राज्यों के परिमित समुच्चय से संबंधित। आइए बताते हैं ${\mathbf {S} }$ अनुक्रम स्थान, अर्थात राज्यों के सभी संभावित अनुक्रमों का समुच्चय है।

इष्टतम मिलान एल्गोरिदम सरल ऑपरेटर बीजगणित को परिभाषित करके कार्य करते हैं जो अनुक्रमों में परिवर्तन करते हैं, अर्थात ऑपरेटरों का समुच्चय $a_{i}:{\mathbf {S} }\rightarrow {\mathbf {S} }$. सबसे सरल दृष्टिकोण में, अनुक्रमों को परिवर्तित करने के लिए मात्र तीन मूलभूत संक्रियाओं से बने समुच्चय का उपयोग किया जाता है:

• अनुक्रम $a_{s'}^{\rm {Ins}}(s_{1},s_{2},s_{3},\ldots s_{T})=(s_{1},s_{2},s_{3},\ldots ,s',\ldots s_{T})$ में स्थिति $s$ प्रविष्ट किया गया है,
• स्थिति को अनुक्रम $a_{s_{2}}^{\rm {Del}}(s_{1},s_{2},s_{3},\ldots s_{T})=(s_{1},s_{3},\ldots s_{T})$ से विस्थापित कर दिया जाता है और
• राज्य $s_{1}$ राज्य $s'_{1}$, $a_{s_{1},s'_{1}}^{\rm {Sub}}(s_{1},s_{2},s_{3},\ldots s_{T})=(s'_{1},s_{2},s_{3},\ldots s_{T})$ द्वारा प्रतिस्थापित किया जाता है।

अब कल्पना कीजिए कि व्यय $c(a_{i})\in {\mathbf {R} }_{0}^{+}$ प्रत्येक ऑपरेटर से जुड़ा है। दो अनुक्रमों $S_{1}$ और $S_{2}$ को देखते हुए, बीजगणित से ऑपरेटरों का उपयोग करके $S_{1}$ से $S_{2}$ प्राप्त करने के व्यय को मापने का विचार है। मान लें $A={a_{1},a_{2},\ldots a_{n}}$ ऑपरेटरों का अनुक्रम है जिस प्रकार इस अनुक्रम के सभी ऑपरेटरों के अनुप्रयोग $A$ को प्रथम अनुक्रम $S_{1}$ के लिए द्वितीय अनुक्रम $S_{2}$:$S_{2}=a_{1}\circ a_{2}\circ \ldots \circ a_{n}(S_{1})$ देता है, जहां $a_{1}\circ a_{2}$ कंपाउंड ऑपरेटर को दर्शाता है।

इस समुच्चय से हम व्यय $c(A)=\sum _{i=1}^{n}c(a_{i})$ को जोड़ते हैं, यह परिवर्तन के कुल व्यय का प्रतिनिधित्व करता है। इस बिंदु पर विचार करना चाहिए कि इस प्रकार के भिन्न- भिन्न क्रम उपस्थित हो सकते हैं $A$ वह परिवर्तन $S_{1}$ में $S_{2}$; इस प्रकार के दृश्यों में से सबसे अल्पमूल्य चयन करना उचित विकल्प है। हम इस प्रकार $d(S_1,S_2)=\underset{A}{min}\{c(A)\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{h}\mathrm{t}\mathrm{h}$