최적 매칭

최적 매칭은 일반적으로 두 개인이 경험한 사회경제적 상태의 시간순서를 나타내는 순서가 다른 토큰 배열의 차이를 평가하기 위해 사회과학에서 사용되는 시퀀스 분석 방법이다.일단 그러한 거리가 관측치 집합(예: 코호트의 개인)에 대해 계산되면 고전적 도구(군집 분석 등)를 사용할 수 있다.이 방법은 원래 분자생물학(단백질 또는 유전체) 시퀀스(순서 정렬 참조)를 연구하기 위해 도입된 기법에서 사회과학에^[1] 맞춘 것이다.최적의 매칭은 니들맨-운슈 알고리즘을 사용한다.null

알고리즘.

Let $S{\displaystyle }$=${\displaystyle }$( ${\displaystyle {1\mathrm{}}_{}}$, ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle {}_{}{3\mathrm{}}_{}}$ ,${\displaystyle {}_{}}$…${\displaystyle T_{}}$ )${\displaystyle S=(s_{1},s_{2},s_{3},\ldots s_{{{{}}}}$$T}}$은(는) 가능한 상태의 유한 집합에 속하는$$ 상태 ${\displaystyle s_{}}$ $i{\displaystyle {}_{}}$ ${\$의 시퀀스다$$.$S{\displaystyle \mathbf{}}$ ${\$ 시퀀스$$ 공간, 즉 가능한 모든 상태 시퀀스 집합을 나타내자.null

최적의 일치 알고리즘은 시퀀스를 조작하는 간단한 연산자 알헤브라를 정의하여 작동한다. 즉 ${\displaystyle {연산자}_{}}$ $a{\displaystyle {}_{}}$: ${\displaystyle s\mathbf{}}$→ ${\displaystyle S\mathbf{}}$ ${\$${\mathbf {S}}\오른쪽$ 화살표 ${\mathbf {S$ 가장 간단한 접근법에서는 시퀀스 변환을 위한 세 가지 기본 연산만으로 구성된 세트를 사용한다.

• one state ${\displaystyle s}$ is inserted in the sequence ${\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}}$
• one state is deleted from the sequence ${\displaystyle a_{s_{2}}^{\rm {Del}}(s_{1},s_{2},s_{3},\ldots s_{T})=(s_{1},s_{3},\ldots s_{$$T$$}}$ 및
• a state ${\displaystyle s_{1}}$ is replaced (substituted) by state ${\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}}$ $.$

이제 비용 ${\displaystyle }$( ${\displaystyle i_{}}$) ${\displaystyle \in }$ ${\displaystyle {\mathbf{}}_{}^{}}$ ${\displaystyle 0_{\mathrm{}}^{}}$+ ${\$가 각 운영자와 연관되어 있다고 상상해 보십시오.두 시퀀스 $S{\displaystyle {}_{}}$ ${\$}과$$ S ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}을 대수의 연산자를 이용하여$$ S ${\displaystyle {1\mathrm{}}_{}}$ ${\$}로부터$$ S ${\displaystyle {2\mathrm{}}_{}}$ ${\$${$$1$}를 얻는 비용을 측정하는 것이다$.$Let ${\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 ${\displaystyle A}$ to the first sequence ${\displaystyle S_{1}}$ gives the second sequence ${\displaystyle S_{2}}$: ${\displaystyle S_2}$${\displaystyle =}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}{}_{}\circ }$ … ${\displaystyle n_{}}$ (${\displaystyle {}_{}{S\mathrm{}}_{}}$ $){\displaystyle S_{2}=a_{1}}\circle a_{2}\circlots \circlots$ \$circirc a_{n$$}($$S_{1})},$ 여기서$$ $은$ 복합 연산자를 나타낸다$$.이 집합에 변환의 총 비용을 나타내는 $비용{\displaystyle }$ c${\displaystyle }$(${\displaystyle A}$) =${\displaystyle \underset{i}{\overset{}{}}}$i = ${\displaystyle {}_{}}$ c${\displaystyle }$( ${\displaystyle i_{}}$) ${\displaystyle c(A)=\sum _{i=1}^{n(a_{i}})$을 연결한다$.$${\displaystyle {이\mathrm{}}_{}}$ 시점에서 S$$1 {\$displaystyle S_{$1}를 S$$2 {\$displaystyle S_{1$}로$$ 변환하는$$ 다른 시퀀스 $A{\displaystyle }$ ${\displaystyle A}$이(가) 존재할 수 있음을 고려해야 한다$.$ 합리적인 선택은 그러한 시퀀스 중 가장 저렴한 것을 선택하는 것이다.그러므로 우리는 거리라고 부른다.
${\displaystyle d(S_{1},S_{2})=\min _{A}\left\{c(A)~{\rm {sufficious~}{2}=A(S_{1}}\right\}}}}}}}$
that is, the cost of the least expensive set of transformations that turn ${\displaystyle S_{1}}$ into ${\displaystyle S_{2}}$. Notice that ${\displaystyle d(S_{1},S_{2})}$ is by definition nonnegative since it is the sum of positive costs, and trivially ${\$${\displaystyle {}_{}}$ $스타일 d$${\displaystyle {}_{}}$$S_{1}, S_{2$$\}\}=$$0},$ S 1 = S 2 {\$displaystyle S_{1}=S_{2$}}인 경우에만$$ 비용이 들지 않는다.거리 함수는 삽입 및 삭제 비용이 $c{\displaystyle (}$ ${\displaystyle {\mathrm{In}}^{}}$ s${\displaystyle {}^{}}$)${\displaystyle }$= ${\displaystyle c({D\mathrm{}}^{}}$ ${\displaystyle {\mathrm{e}}^{}}$ ${\displaystyle {\mathrm{l}}^{}}$) ${\displaystyle c(a^{\rm {Ins})=c(a^{\rm {Del})}$일 경우 대칭이며$,$ 일반적으로 지워지지 않는 비용이라는 용어는 삽입 및 삭제의 공통 비용을 가리킨다.null

위에서 설명한 3가지 기본 연산만으로 구성된 세트를 고려하면, 이 근접 측정은 삼각 불평등을 만족시킨다.그러나 transitability는 기본 운영 세트의 정의에 따라 달라진다.null

비판

사회학과 인구통계학에서는 최적의 매칭 기법이 널리 사용되고 있지만, 그러한 기법도 그 결점이 있다.여러 저자(예: L. L. Wu^[2])가 지적한 바와 같이, 최적 매칭 적용의 주요 문제는 비용 $c{\displaystyle }$( $){\displaystyle c(a_{i}})$를 적절하게 정의하는 것이다$.$

인과적 모델링에서 최적의 일치

최적 일치는 또한 인과적 효과의 통계적 모델링에 사용되는 용어다.이 맥락에서 "사례"와 "통제"를 일치시키는 것을 말하며, 시퀀스 분석적 감각과는 완전히 별개다.null

소프트웨어

• TDA는 전환 데이터 분석의 최신 개발 중 일부를 제공하는 강력한 프로그램이다.
• STATA는 최적의 일치 분석을 실행하기 위해 패키지를 구현했다.
• TraMineR은 최적의 매칭 분석을 포함한 상태 및 이벤트 시퀀스를 분석 및 시각화하기 위한 오픈 소스 R-패키지다.

참조 및 참고 사항