最適なマッチング

最適マッチングは、社会科学において用いられる配列分析手法であり、通常、2人の個人が経験した社会経済的状態の時系列シーケンスを表すトークンの順序付けられた配列の類似度を評価するために使用されます。一連の観測値（例えば、コホート内の個人）についてこのような距離が計算されると、クラスター分析などの従来のツールを使用できます。この手法は、もともと分子生物学（タンパク質または遺伝子）の配列（配列アライメントを参照）を研究するために導入された手法を社会科学向けにカスタマイズしたものです^[1]。最適マッチングでは、ニードルマン・ヴンシュアルゴリズムが用いられます。

アルゴリズム

状態列を有限個の可能な状態集合に属する状態列とします。状態列空間、すなわちすべての可能な状態列の集合を と 表します。${\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パッケージです。

参考文献と注釈

1. A. AbbottとA. Tsay（2000）「社会学におけるシーケンス分析と最適マッチング法：レビューと展望」『社会学的方法と研究』第29巻、3-33頁。doi ： 10.1177/0049124100029001001
2. LL Wu. (2000) 「社会学におけるシーケンス分析と最適マッチング法：レビューと展望」に関するコメント、2006年10月24日アーカイブ、Wayback Machine、Sociological Methods & Research、29、41-64。doi : 10.1177/0049124100029001003