最適なマッチング

最適マッチングは社会科学で使用されるシーケンス分析方法であり、通常、2 人の個人が経験した社会経済的状態の時系列シーケンスを表すトークンの順序付けられた配列の非類似性を評価します。一連の観察 (コホート内の個人など)についてこのような距離が計算されると、従来のツール (クラスター分析など) を使用できます。この方法は、もともと分子生物学 (タンパク質または遺伝子) シーケンス (シーケンスアライメントを参照) を研究するために導入された手法から社会科学に合わせて調整されました^[1]。最適マッチングでは、Needleman-Wunsch アルゴリズムが使用されます。

可能な状態の有限集合に属する状態のシーケンスを とします。シーケンス空間、つまりすべての可能な状態シーケンスの集合を 表します。${\displaystyle S=(s_{1},s_{2},s_{3},\ldots s_{T})}$${\displaystyle s_{i}}$${\displaystyle {\mathbf {S}}}$

最適マッチング アルゴリズムは、シーケンスを操作する単純な演算子代数、つまり演算子のセットを定義することによって機能します。最も単純なアプローチでは、シーケンスを変換するための 3 つの基本操作のみで構成されるセットが使用されます。 ${\displaystyle a_{i}:{\mathbf {S} }\rightarrow {\mathbf {S} }}$

• シーケンスに1つの状態が挿入される${\displaystyle s}$${\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})}$
• シーケンスから1つの状態が削除され、${\displaystyle a_{s_{2}}^{\rm {Del}}(s_{1},s_{2},s_{3},\ldots s_{T})=(s_{1},s_{3},\ldots s_{T})}$
• 状態は状態 によって置き換えられます (置換されます) 。${\displaystyle s_{1}}$${\displaystyle s'_{1}}$${\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})}$

ここで、各演算子にコスト が関連付けられていると想像してください。2 つのシーケンスとが与えられている場合、 代数の演算子を使用してから を 取得する コストを測定するという考え方です。を演算子のシーケンスとし、このシーケンスのすべての演算子を最初のシーケンスに適用すると、 2 番目のシーケンス が得られます。ここで、 は複合演算子を表します。このセットに、変換の総コストを表すコスト を関連付けます。この時点で、に変換する さまざまなシーケンスが存在する可能性があることを考慮する必要があります。合理的な選択は、そのようなシーケンスの中で最もコストがかからないものを選択することです。したがって、 に変わる変換の最も安価なセットのコストである距離 をと呼びます。 は定義により非負であることに注意してください。これは正のコストの合計であるためです。また、 の場合に限り、コストがないことは明らかです。挿入コストと削除コストが等しい場合、距離関数は対称です。挿入コストという用語は通常、挿入と削除の共通コストを指します。 ${\displaystyle c(a_{i})\in {\mathbf {R} }_{0}^{+}}$${\displaystyle S_{1}}$${\displaystyle S_{2}}$${\displaystyle S_{2}}$${\displaystyle S_{1}}$${\displaystyle A={a_{1},a_{2},\ldots a_{n}}}$${\displaystyle A}$${\displaystyle S_{1}}$${\displaystyle S_{2}}$${\displaystyle S_{2}=a_{1}\circ a_{2}\circ \ldots \circ a_{n}(S_{1})}$${\displaystyle a_{1}\circ a_{2}}$${\displaystyle c(A)=\sum _{i=1}^{n}c(a_{i})}$${\displaystyle A}$${\displaystyle S_{1}}$${\displaystyle S_{2}}$
${\displaystyle d(S_{1},S_{2})=\min _{A}\left\{c(A)~{\rm {そのような~である}}~S_{2}=A(S_{1})\right\}}$
${\displaystyle S_{1}}$${\displaystyle S_{2}}$${\displaystyle d(S_{1},S_{2})}$${\displaystyle d(S_{1},S_{2})=0}$${\displaystyle S_{1}=S_{2}}$${\displaystyle c(a^{\rm {Ins}})=c(a^{\rm {Del}})}$

上記の 3 つの基本演算のみで構成されるセットを考えると、この近接測度は三角不等式を満たします。ただし、推移性は基本演算のセットの定義に依存します。

最適マッチング技術は社会学や人口統計学で広く使用されていますが、この技術にも欠点があります。何人かの著者（例えばLL Wu ^[2]）が指摘したように、最適マッチングの適用における主な問題は、コストを適切に定義することです。 ${\displaystyle c(a_{i})}$

• TDA は、遷移データ分析の最新の開発の一部にアクセスできる強力なプログラムです。
• STATA は最適マッチング分析を実行するためのパッケージを実装しました。
• TraMineR は、最適マッチング分析を含む状態とイベントのシーケンスを分析および視覚化するためのオープンソースのRパッケージです。