Optimal matching

Let $S\; =\; (s\_1,\; s\_2,\; s\_3,\; \backslash ldots\; s\_T)$ be a sequence of states $s\_i$ belonging to a finite set of possible states. Let us denote $\{\backslash mathbf\; S\}$ the sequence space, i.e. the set of all possible sequences of states.

Optimal matching algorithms work by defining simple operator algebras that manipulate sequences, i.e. a set of operators $a\_i:\; \{\backslash mathbf\; S\}\; \backslash rightarrow\; \{\backslash mathbf\; S\}$. In the most simple approach, a set composed of only three basic operations to transform sequences is used:

• one state $s$ is inserted in the sequence $a^\{\backslash rm\; Ins\}\_\{s\text{'}\}\; (s\_1,\; s\_2,\; s\_3,\; \backslash ldots\; s\_T)\; =\; (s\_1,\; s\_2,\; s\_3,\; \backslash ldots,\; s\text{'},\; \backslash ldots\; s\_T)$
• one state is deleted from the sequence $a^\{\backslash rm\; Del\}\_\{s\_2\}\; (s\_1,\; s\_2,\; s\_3,\; \backslash ldots\; s\_T)\; =\; (s\_1,\; s\_3,\; \backslash ldots\; s\_T)$ and
• a state $s\_1$ is replaced (substituted) by state $s\text{'}\_1$, $a^\{\backslash rm\; Sub\}\_\{s\_1,s\text{'}\_1\}\; (s\_1,\; s\_2,\; s\_3,\; \backslash ldots\; s\_T)\; =\; (s\text{'}\_1,\; s\_2,\; s\_3,\; \backslash ldots\; s\_T)$.

Imagine now that a cost $c(a\_i)\; \backslash in\; \{\backslash mathbf\; R\}^+\_0$ is associated

to each operator. Given two sequences $S\_1$ and $S\_2$,

the idea is to measure the cost of obtaining $S\_2$ from $S\_1$

using operators from the algebra. Let $A=\{a\_1,\; a\_2,\; \backslash ldots\; a\_n\}$ be a sequence of operators such that the application of all the operators of this sequence $A$ to the first sequence $S\_1$ gives the second sequence $S\_2$:

$S\_2\; =\; a\_1\; \backslash circ\; a\_2\; \backslash circ\; \backslash ldots\; \backslash circ\; a\_\{n\}\; (S\_1)$ where $a\_1\; \backslash circ\; a\_2$ denotes the compound operator.

To this set we associate the cost $c(A)\; =\; \backslash 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$ that transform $S\_1$ into $S\_2$; a reasonable choice is to select the cheapest of such sequences. We thus

call distance

$d(S\_1,S\_2)=\; \backslash min\_A\; \backslash left\; \backslash \{\; c(A)~\{\backslash rm\; such~that\}~S\_2\; =\; A\; (S\_1)\; \backslash right\; \backslash \}$

that is, the cost of the least expensive set of transformations that turn $S\_1$ into $S\_2$. Notice that $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$ if and only if $S\_1=S\_2$, that is there is no cost. The distance function is symmetric if insertion and deletion costs are equal $c(a^\{\backslash rm\; Ins\})\; =\; c(a^\{\backslash rm\; Del\})$; the term indel cost usually refers to the common cost of insertion and deletion.

Considering a set composed of only the three basic operations described above, this proximity measure satisfies the triangular inequality. Transitivity however, depends on the definition of the set of elementary operations.

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. WuL. L. Wu. (2000) [http://smr.sagepub.com/cgi/content/refs/29/1/41 Some Comments on "Sequence Analysis and Optimal Matching Methods in Sociology: Review and Prospect"] {{Webarchive|url=https://web.archive.org/web/20061024143211/http://smr.sagepub.com/cgi/content/refs/29/1/41 |date=2006-10-24 }} Sociological Methods & Research, 29 41-64. {{doi|10.1177/0049124100029001003}}), the main problem in the application of optimal matching is to appropriately define the costs $c(a\_i)$.

• [http://www.stat.ruhr-uni-bochum.de/tda.html TDA] is a powerful program, offering access to some of the latest developments in transition data analysis.
• [http://ideas.repec.org/a/tsj/stataj/v6y2006i4p435-460.html STATA] has implemented a package to run optimal matching analysis.
• [http://traminer.unige.ch/ TraMineR] is an open source R-package for analyzing and visualizing states and events sequences, including optimal matching analysis.

Category:Data mining

Category:Statistical distance

Category:Quantitative research