Does optimal matching always use the same costs?

No. Different cost choices and variants can emphasize different aspects of sequence similarity.

Is it the same as clustering?

No. It produces comparisons between sequences. A clustering method can then use those comparisons, with additional assumptions and choices.

Can sequences have different lengths?

Basic edit-based comparisons can handle different lengths, but the meaning of length differences, missing periods and any normalization still needs careful consideration.

AI Glossary / Data science and analytics / Intermediate

Optimal matching

Definition

Optimal matching, in sequence analysis, measures how different two ordered sequences are by finding the least costly set of insertions, deletions and substitutions that transforms one into the other. The resulting edit cost depends on the analyst's chosen costs and representation.

What it means

A sequence records an ordered history, such as a person's monthly employment states or a customer's progression through service stages. Two histories can contain similar states while differing in their order, timing or duration.

Optimal matching provides a way to compare whole sequences rather than one observation at a time. The word “optimal” means that the algorithm finds a minimum under its specified edit rules. It does not mean that the resulting comparison is automatically the best scientific description of the histories.

This entry follows the sequence-analysis meaning in the source list. In other contexts, optimal matching can refer to assigning people or objects to partners under an optimization criterion. That assignment problem should not be confused with calculating edit distances between histories.

How it works

The analyst first defines the possible states, the time unit and the treatment of missing observations. Repeated states can represent duration: four monthly observations in employment describe a different history from one employed month.

A substitution changes one state into another. An insertion adds a state, and a deletion removes one. Costs can be constant or depend on the states involved. A dynamic-programming procedure compares alternatives for prefixes of the sequences and accumulates the lowest permitted total cost.

The balance of costs matters. Relatively inexpensive insertions and deletions can align similar patterns occurring at different positions. Expensive insertions and deletions place more emphasis on matching states at their existing positions.

Researchers may calculate distances for many pairs and then use them in clustering or other analyses. Those later steps are separate choices. Normalization, sequence length and alternative cost settings should be examined before interpreting groups as substantive types.

Three practical examples

A social researcher compares monthly education, employment and unemployment histories to explore recurring patterns of transition.
A service designer compares onboarding journeys to investigate whether similar stages occur in different orders or at different speeds.
A maintenance analyst compares ordered equipment states across operating cycles, after deciding whether timing shifts should count as important differences.

Think of it this way

Think of editing two strings of colored beads until their color sequences match. Replacing a bead, adding one and removing one each carry an agreed cost. The cheapest editing plan gives a comparison score.

The analogy does not imply that real histories can be changed retrospectively. The edits are mathematical comparison operations, and their costs express analytical choices rather than actual money or effort spent by the people represented.

Worked example

Consider the invented state sequences A - B - C and A - C. Let a matching state cost zero, an insertion or deletion cost 1, and a substitution cost 2.

Deleting B from the first sequence produces the second at cost 1. Because the sequences differ in length by one, at least one insertion or deletion is required under these rules. Its cost is at least 1, so the demonstrated transformation is optimal and the distance is 1.

Now compare A - B with B - A under the same costs. Substituting both positions costs 4. Deleting the first A and inserting A at the end costs 2, so the minimum is 2. The algorithm can align the shared B through editing rather than treating both positions as unrelated.

If timing at the original positions is the research priority, allowing this alignment may be inappropriate. The calculation is correct under its rules; whether the rules answer the intended question is a separate judgment.

Illustrative case study

Illustrative fictional case: Pathway Learning compares weekly student support journeys and clusters them using optimal matching. The first analysis groups some early-support and late-support histories together because insertions and deletions are inexpensive.

The team realizes that the timing of support relative to a course deadline is central to its question. It compares alternative costs and a position-sensitive comparison, reviews representative histories and documents which conclusions change.

It does not label the original clusters as proven learning styles or use them as evidence that support caused an outcome. The fictional lesson is that an algorithm's minimum cost is conditional on the representation and comparison rules. A technically valid result can still emphasize the wrong aspect of the process.

Common misconceptions and mistakes

Do not confuse a low edit distance with identical calendar timing. Do not treat software defaults as a neutral statement of substantive similarity.

Avoid interpreting clusters as natural categories without checking their stability and meaning. Missing observations should not silently become an ordinary substantive state. Finally, similarity of histories is not evidence that one event caused another or that two people faced the same opportunities and constraints.

Business use

Use optimal matching when the order and progression of states matter to the business question. Define the observation window and what each state represents before selecting costs.

Ask whether the analysis should emphasize timing, duration, transitions or broad ordering. Compare plausible settings and inspect actual sequences within any proposed group. For AI-generated descriptions of clusters, require examples and explicit uncertainty about what the patterns mean. A useful summary should explain the grouping's basis rather than giving an unsupported personality or behavioral label to its members.

Check your understanding

Two sequence clusters disappear when insertion and deletion costs change slightly. Should they be presented as unquestionable real-world types?

Answer: No. Their sensitivity is evidence that the grouping depends on the chosen comparison rules. Investigate that dependence and explain it before drawing substantive conclusions.

Related terms

Learn next

Read edit distance and longitudinal data. Hand-calculate two short sequence comparisons using two different cost schemes. Explain which scheme better represents the importance of timing in your question, then inspect whether the resulting similarities match that intention.

Sources

TraMineR, sequence dissimilarity methods and parameters: https://traminer.unige.ch/doc/seqdist.html

Gabadinho and colleagues, TraMineR user guide: https://mephisto.unige.ch/pub/TraMineR/doc/1.4/TraMineR-1.4-Users-Guide.pdf

Laurent Lesnard, Setting Cost in Optimal Matching to Uncover Contemporaneous Socio-Temporal Patterns: https://journals.sagepub.com/doi/10.1177/0049124110362526

The state calculations and learning-service case are original fictional illustrations.

Previous: Optimal experimental design Next: Optimal policy