Optymalne dopasowanie

Nie należy mylić z maksymalnym dopasowaniem w teorii grafów lub statystycznym problemem znalezienia optymalnego dopasowania do wnioskowania przyczynowego.

Optymalne dopasowanie to metoda analizy sekwencji stosowana w naukach społecznych do oceny odmienności uporządkowanych tablic tokenów, które zwykle reprezentują uporządkowaną w czasie sekwencję stanów społeczno-ekonomicznych, których doświadczyły dwie osoby. Po obliczeniu takich odległości dla zbioru obserwacji (np. osobników w kohorcie ) można zastosować klasyczne narzędzia (takie jak analiza skupień ). Metoda została dostosowana do nauk społecznych z techniki pierwotnie wprowadzonej do badania sekwencji biologii molekularnej (białkowej lub genetycznej) (patrz dopasowanie sekwencji ). Optymalne dopasowanie wykorzystuje algorytm Needlemana-Wunscha .

Algorytm

Niech ${\ Displaystyle S = (s_ {1}, s_ {2}, s_ {3}, \ ldots s_ {T})$ } stany $skończonego$ zbioru możliwych stanów Oznaczmy przestrzeń $czyli$ zbiór wszystkich możliwych sekwencji stanów.

$.$ poprzez definiowanie prostych algebr operatorów, operatorów . W najprostszym podejściu stosuje się zestaw składający się tylko z trzech podstawowych operacji przekształcania ciągów:

• jeden stan ${\ Displaystyle a_ {s'} ^ {\ rm {Ins}} (s_ {1}, s_ {2}, s_ {3}, \ ldots s_ {T}) = (s_ {1}, s_ {2} ,s_{3},\ldots ,s',\ldots s_{T})}$ w sekwencji $s$
• jeden stan jest usuwany z sekwencji $\ Displaystyle a_ {s_ {2}} ^ {\rm {Del}}(s_{1},s_{2},s_{3},\ldots s_{T})=(s_{1},s_{3},\ldots s_{T})}$ I
• stan przez stan ${\ Displaystyle s'_ {1}$$}$ za ${\ Displaystyle 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})}$ .

Wyobraź sobie teraz, że z każdym operatorem powiązany jest koszt ${\ Displaystyle c (a_ {i}) \ in {\ mathbf {R}} _ {0} ^ {+}} .$ Biorąc pod uwagę dwie sekwencje i ${\ displaystyle S_$${2}}$ , pomysł polega na zmierzeniu $}$ { \ displaystyle $displaystyle S_ {2}} S_{1}}$ używając operatorów z algebry. niech ${\ Displaystyle A = {a_ {1}, a_ {2}, \ ldots a_ {n}}}$ będzie sekwencją operatorów taką, że zastosowanie wszystkich operatorów tej sekwencji $A}$$S_ {2}}$ do pierwszej sekwencji daje drugą sekwencję ${\$ : ${\ Displaystyle S_ {2} = a_ {1} \ circ a_ {2} \ circ \ ldots \ circ a_ {n} (S_ {1})}$ gdzie ${\ Displaystyle a_ {1}\circ a_{2}}$ oznacza operator złożony. Do tego zestawu wiążemy koszt ${\ Displaystyle c (A) = \ suma _ {i = 1} ^ {n} c (a_ {i})}$
, który reprezentuje całkowity koszt transformacji. W tym $\ displaystyle S_ {1}}$ należy wziąć pod uwagę, że mogą istnieć różne takie sekwencje $które$ się w ${$ ; rozsądnym wyborem jest wybranie najtańszego z takich ciągów. W ten sposób nazywamy odległość
${\ Displaystyle d (S_ {1}, S_ {2}) = \ min _ {A} \ lewo \ {c (A) ~ {\ rm { takie ~ że}} ~ S_ {2} = A (S_ {1}) \ prawo \}}$ , czyli koszt najtańszego zestawu przekształceń, które zamieniają ${\ displaystyle S_ {1}}$ w ${\ Displaystyle S_ {2}}$ . Zauważ, że ${\ Displaystyle d (S_ {1}, S_ {2})}$ jest z definicji nieujemna, ponieważ jest sumą kosztów dodatnich i trywialnie ${\ Displaystyle d (S_ {1}, S_ {2}) = 0}$ wtedy i tylko wtedy, gdy ${\ displaystyle S_ {1} = S_ {2}}$ , czyli nie ma żadnych kosztów. Funkcja odległości jest symetryczna , jeśli koszty wstawiania i usuwania są ${\ Displaystyle c (a ^ {\ rm {Ins}}) = c (a ^ {\ rm {Del}})}$ ; termin indel zwykle odnosi się do wspólnego kosztu wstawiania i usuwania.

Biorąc pod uwagę zbiór składający się tylko z trzech podstawowych operacji opisanych powyżej, ta miara bliskości spełnia nierówność trójkątną. Przechodniość zależy jednak od definicji zbioru operacji elementarnych.

Krytyka

Chociaż techniki dopasowywania optymalnego są szeroko stosowane w socjologii i demografii, mają one również swoje wady. Jak zauważyło kilku autorów (na przykład LL Wu), głównym problemem w stosowaniu optymalnego dopasowania jest odpowiednie zdefiniowanie kosztów do ( za ja ) {\ $i})}$ .

Oprogramowanie

• TDA to potężny program, oferujący dostęp do niektórych najnowszych osiągnięć w analizie danych przejściowych.
• STATA wdrożyła pakiet do przeprowadzania analizy optymalnego dopasowania.
• TraMineR to pakiet R typu open source do analizy i wizualizacji stanów i sekwencji zdarzeń, w tym analizy optymalnego dopasowania.