इष्टतम मिलान

Not to be confused with maximum matching in graph theory or the statistical problem of finding an optimal match for causal inference.

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

एल्गोरिथम

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

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

• एक राज्य $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})$
• एक स्थिति को क्रम से हटा दिया जाता है $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_{2}$ से $S_{1}$ बीजगणित से ऑपरेटरों का उपयोग करना। होने देना $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})=\min _{A}\left\{c(A)~{\rm {such~that}}~S_{2}=A(S_{1})\right\}$
अर्थात, रूपांतरणों के कम से कम खर्चीले सेट की लागत $S_{1}$ में $S_{2}$. नोटिस जो $d(S_{1},S_{2})$ परिभाषा के अनुसार गैर-ऋणात्मक है क्योंकि यह सकारात्मक लागतों का योग है, और तुच्छ रूप से $d(S_{1},S_{2})=0$ अगर और केवल अगर $S_{1}=S_{2}$यानी कोई कीमत नहीं है। यदि सम्मिलन और विलोपन लागत समान हैं, तो दूरी फ़ंक्शन सममित है $c(a^{\rm {Ins}})=c(a^{\rm {Del}})$; इंडेल लागत शब्द आमतौर पर सम्मिलन और विलोपन की सामान्य लागत को संदर्भित करता है।

ऊपर वर्णित केवल तीन मूल संक्रियाओं से बने एक सेट को ध्यान में रखते हुए, यह निकटता माप त्रिकोणीय असमानता को संतुष्ट करता है। सकर्मक संबंध हालांकि, प्रारंभिक संक्रियाओं के समुच्चय की परिभाषा पर निर्भर करता है।

आलोचना

यद्यपि इष्टतम मिलान तकनीकों का व्यापक रूप से समाजशास्त्र और जनसांख्यिकी में उपयोग किया जाता है, ऐसी तकनीकों में भी उनकी खामियां हैं। जैसा कि कई लेखकों द्वारा इंगित किया गया था (उदाहरण के लिए एलएल वू), इष्टतम मिलान के आवेदन में मुख्य समस्या लागतों को उचित रूप से परिभाषित करना है $c(a_{i})$.

सॉफ्टवेयर

• TDA एक शक्तिशाली कार्यक्रम है, जो संक्रमण डेटा विश्लेषण में कुछ नवीनतम विकासों तक पहुंच प्रदान करता है।
• STATA ने इष्टतम मिलान विश्लेषण चलाने के लिए एक पैकेज लागू किया है।
• TraMineR एक ओपन सोर्स R (प्रोग्रामिंग लैंग्वेज)-पैकेज है, जो स्थितियों और घटनाओं के अनुक्रमों का विश्लेषण और कल्पना करने के लिए है, जिसमें इष्टतम मिलान विश्लेषण भी शामिल है।