Optimal matchning

Ej att förväxla med maximal matchning i grafteorin eller det statistiska problemet att hitta en optimal matchning för kausal slutledning.

Optimal matchning är en sekvensanalysmetod som används inom samhällsvetenskap , för att bedöma olikheten mellan ordnade arrayer av tokens som vanligtvis representerar en tidsordnad sekvens av socioekonomiska tillstånd som två individer har upplevt. När sådana avstånd har beräknats för en uppsättning observationer (t.ex. individer i en kohort ) kan klassiska verktyg (som klusteranalys) användas. Metoden skräddarsyddes för samhällsvetenskap från en teknik som ursprungligen introducerades för att studera molekylärbiologiska (protein eller genetiska) sekvenser (se sekvensanpassning ). Optimal matchning använder Needleman-Wunsch-algoritmen .

Algoritm

Låt $S=(s_{1},s_{2},s_{3},\ldots s_{T})$ vara en sekvens av tillstånd $s_{i}$ tillhörande en ändlig uppsättning möjliga tillstånd. Låt oss beteckna ${\mathbf {S} }$ sekvensutrymmet, dvs mängden av alla möjliga sekvenser av tillstånd.

Optimala matchningsalgoritmer fungerar genom att definiera enkla operatoralgebror som manipulerar sekvenser, dvs en uppsättning operatorer $a_{i}:{\mathbf {S} }\rightarrow {\mathbf {S} }$ . I det enklaste tillvägagångssättet används en uppsättning som består av endast tre grundläggande operationer för att transformera sekvenser:

• ett tillstånd $s$ infogas i sekvensen $a_{s'}^{\rm {Ins}}(s_{1},s_{2},s_{3},\ldots s_{T})=(s_{1},s_ {2},s_{3},\ldots,s',\ldots s_{T})$
• ett tillstånd tas bort från sekvensen $a_{s_{2}}^ {\rm {Del}}(s_{1},s_{2},s_{3},\ldots s_{T})=(s_{1},s_{3},\ldots s_{T})$ och
• ett tillstånd $s_{1}$ ersätts (ersätts) med tillstånd $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})$ .

Föreställ dig nu att en kostnad $c(a_{i})\in {\mathbf {R} }_{0}^{+}$ är associerad med varje operator. Med tanke på två sekvenser $S_{1}$ och $S_{2}$ är tanken att mäta kostnaden för att erhålla $S_{2}$ från $S_{1}$ med operatorer från algebra. Låt $A={a_{1},a_{2},\ldots a_{n}}$ vara en sekvens av operatorer så att tillämpningen av alla operatorer för denna sekvens $A$ till den första sekvensen $S_{1}$ ger den andra sekvensen $S_{2}$ : ${\displaystyle S_{2}=a_{1}\circ a_{2}\circ \ldots \circ a_{n}(S_{1})} där$ a $\displaystyle a_{ 1}\circ a_{2}}$ betecknar den sammansatta operatorn. Till denna uppsättning associerar vi kostnaden $c(A)=\summa _{i=1}^{n}c(a_{i})$ , som representerar den totala kostnaden för omvandlingen. Man bör nu tänka på att det kan finnas olika sådana sekvenser $A$ som transformerar $S_{1}$ till $S_{2}$ ; ett rimligt val är att välja den billigaste av sådana sekvenser. Vi kallar alltså distans ${\displaystyle d(S_{1},S_{2 })=\min _{A}\left\{c(A)~{\rm {sådant~att}}~S_{2}=A(S_{1})\right\}} det vill säga$ kostnaden av den billigaste uppsättningen transformationer som gör $S_{1}$ till $S_{2}$ . Lägg märke till att $d(S_{1},S_{2})$ per definition är icke-negativ eftersom det är summan av positiva kostnader, och trivialt $d(S_{1},S_{2})=0$ om och endast om $S_{1}=S_{2}$ , det vill säga att det inte kostar något. Avståndsfunktionen är symmetrisk om kostnaderna för insättning och radering är lika med $c(a^{\rm {Ins}})=c(a^{\rm {Del}})$ ; termen indelkostnad syftar vanligtvis på den gemensamma kostnaden för insättning och radering.

Med tanke på en uppsättning som endast består av de tre grundläggande operationerna som beskrivs ovan, tillfredsställer detta närhetsmått den triangulära olikheten. Transitivitet beror dock på definitionen av uppsättningen elementära operationer.

Kritik

Även om optimal matchningsteknik används i stor utsträckning inom sociologi och demografi, har sådana tekniker också sina brister. Som påpekades av flera författare (till exempel LL Wu), är huvudproblemet vid tillämpningen av optimal matchning att på lämpligt sätt definiera kostnaderna c ( $displaystyle c(a_{i})}$ .

programvara

• TDA är ett kraftfullt program som ger tillgång till några av de senaste utvecklingarna inom övergångsdataanalys.
• STATA har implementerat ett paket för att köra optimal matchningsanalys.
• TraMineR är ett R -paket med öppen källkod för att analysera och visualisera tillstånd och händelsesekvenser, inklusive optimal matchningsanalys.