Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Optimal matching
open-in-new
<h2 id="algorithm">Algorithm</h2> <p>Let S = ( s 1 , s 2 , s 3 , … s T ) {\displaystyle S=(s_{1},s_{2},s_{3},\ldots s_{T})} be a sequence of states s i {\displaystyle s_{i}} belonging to a finite set of possible states. Let us denote S {\displaystyle {\mathbf {S} }} the sequence space, i.e. the set of all possible sequences of states. </p><p>Optimal matching algorithms work by defining simple operator <a href="/facts/Algebras/8T8ulWJb">algebras</a> that manipulate sequences, i.e. a set of operators a i : S → S {\displaystyle a_{i}:{\mathbf {S} }\rightarrow {\mathbf {S} }} . In the most simple approach, a set composed of only three basic operations to transform sequences is used: </p> <ul><li>one state s {\displaystyle s} is inserted in the sequence a s ′ I n s ( s 1 , s 2 , s 3 , … s T ) = ( s 1 , s 2 , s 3 , … , s ′ , … s T ) {\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})} </li> <li>one state is deleted from the sequence a s 2 D e l ( s 1 , s 2 , s 3 , … s T ) = ( s 1 , s 3 , … s T ) {\displaystyle a_{s_{2}}^{\rm {Del}}(s_{1},s_{2},s_{3},\ldots s_{T})=(s_{1},s_{3},\ldots s_{T})} and</li> <li>a state s 1 {\displaystyle s_{1}} is replaced (substituted) by state s 1 ′ {\displaystyle s'_{1}} , a s 1 , s 1 ′ S u b ( s 1 , s 2 , s 3 , … s T ) = ( s 1 ′ , s 2 , s 3 , … s T ) {\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})} .</li></ul> <p>Imagine now that a <i>cost</i> c ( a i ) ∈ R 0 + {\displaystyle c(a_{i})\in {\mathbf {R} }_{0}^{+}} is associated to each operator. Given two sequences S 1 {\displaystyle S_{1}} and S 2 {\displaystyle S_{2}} , the idea is to measure the <i>cost</i> of obtaining S 2 {\displaystyle S_{2}} from S 1 {\displaystyle S_{1}} using operators from the algebra. Let A = a 1 , a 2 , … a n {\displaystyle A={a_{1},a_{2},\ldots a_{n}}} be a sequence of operators such that the application of all the operators of this sequence A {\displaystyle A} to the first sequence S 1 {\displaystyle S_{1}} gives the second sequence S 2 {\displaystyle S_{2}} : S 2 = a 1 ∘ a 2 ∘ … ∘ a n ( S 1 ) {\displaystyle S_{2}=a_{1}\circ a_{2}\circ \ldots \circ a_{n}(S_{1})} where a 1 ∘ a 2 {\displaystyle a_{1}\circ a_{2}} denotes the compound operator. To this set we associate the cost c ( A ) = ∑ i = 1 n c ( a i ) {\displaystyle c(A)=\sum _{i=1}^{n}c(a_{i})} , that represents the total cost of the transformation. One should consider at this point that there might exist different such sequences A {\displaystyle A} that transform S 1 {\displaystyle S_{1}} into S 2 {\displaystyle S_{2}} ; a reasonable choice is to select the cheapest of such sequences. We thus call distance d ( S 1 , S 2 ) = min A { c ( A ) s u c h t h a t S 2 = A ( S 1 ) } {\displaystyle d(S_{1},S_{2})=\min _{A}\left\{c(A)~{\rm {such~that}}~S_{2}=A(S_{1})\right\}} that is, the cost of the least expensive set of transformations that turn S 1 {\displaystyle S_{1}} into S 2 {\displaystyle S_{2}} . Notice that d ( S 1 , S 2 ) {\displaystyle d(S_{1},S_{2})} is by definition nonnegative since it is the sum of positive costs, and trivially d ( S 1 , S 2 ) = 0 {\displaystyle d(S_{1},S_{2})=0} if and only if S 1 = S 2 {\displaystyle S_{1}=S_{2}} , that is there is no cost. The distance function is <a href="/facts/Symmetric/hpu7DK8p">symmetric</a> if insertion and deletion costs are equal c ( a I n s ) = c ( a D e l ) {\displaystyle c(a^{\rm {Ins}})=c(a^{\rm {Del}})} ; the term <i>indel</i> cost usually refers to the common cost of insertion and deletion. </p><p>Considering a set composed of only the three basic operations described above, this proximity measure satisfies the triangular inequality. <a href="/facts/Transitive_relation/9r90y50r">Transitivity</a> however, depends on the definition of the set of elementary operations. </p> <h2 id="criticism">Criticism</h2> <p>Although optimal matching techniques are widely used in sociology and demography, such techniques also have their flaws. As was pointed out by several authors (for example L. L. Wu<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>), the main problem in the application of optimal matching is to appropriately define the costs c ( a i ) {\displaystyle c(a_{i})} . </p> <h2 id="software">Software</h2> <ul><li><a href="http://www.stat.ruhr-uni-bochum.de/tda.html">TDA</a> is a powerful program, offering access to some of the latest developments in transition data analysis.</li> <li><a href="http://ideas.repec.org/a/tsj/stataj/v6y2006i4p435-460.html">STATA</a> has implemented a package to run optimal matching analysis.</li> <li><a href="http://traminer.unige.ch/">TraMineR</a> is an open source <a href="/facts/R_(programming_language)/LSrkr8K8">R</a>-package for analyzing and visualizing states and events sequences, including optimal matching analysis.</li></ul> <h2 id="references-and-notes">References and notes</h2> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>A. Abbott and A. Tsay, (2000) Sequence Analysis and Optimal Matching Methods in Sociology: Review and Prospect Sociological Methods & Research], Vol. 29, 3-33. doi:10.1177/0049124100029001001 <a href="http://smr.sagepub.com/cgi/content/abstract/29/1/3" target="_blank">http://smr.sagepub.com/cgi/content/abstract/29/1/3</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>L. L. Wu. (2000) Some Comments on "Sequence Analysis and Optimal Matching Methods in Sociology: Review and Prospect" Archived 2006-10-24 at the Wayback Machine Sociological Methods & Research, 29 41-64. doi:10.1177/0049124100029001003 <a href="http://smr.sagepub.com/cgi/content/refs/29/1/41" target="_blank">http://smr.sagepub.com/cgi/content/refs/29/1/41</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> </ol>