Оптимальное соответствие

Оптимальное соответствие — это метод анализа последовательности , используемый в социальных науках для оценки несходства упорядоченных массивов токенов, которые обычно представляют собой упорядоченную по времени последовательность социально-экономических состояний, которые пережили два человека. После того, как такие расстояния рассчитаны для набора наблюдений (например, отдельных лиц в когорте классические инструменты (такие как кластерный анализ ), можно использовать ). Метод был адаптирован для социальных наук. ^[1] из метода, первоначально внедренного для изучения последовательностей молекулярной биологии (белковых или генетических) (см. Выравнивание последовательностей ). Оптимальное сопоставление использует алгоритм Нидлмана-Вунша .

Алгоритм

Позволять $S=(s_{1},s_{2},s_{3},\ldots s_{T})$ быть последовательностью состояний $s_{i}$ принадлежащий конечному множеству возможных состояний. Обозначим ${\mathbf {S} }$ пространство последовательностей, т.е. множество всех возможных последовательностей состояний.

Алгоритмы оптимального сопоставления работают путем определения простых алгебр операторов , которые манипулируют последовательностями, то есть набора операторов. $a_{i}:{\mathbf {S} }\rightarrow {\mathbf {S} }$ . В самом простом подходе используется набор, состоящий всего из трех основных операций преобразования последовательностей:

одно государство $s$ вставляется в последовательность $a_{s'}^{\rm {Ins}}(s_{1},s_{2},s_{3},\ldots s_{T})=(s_{1},s_{2},s_{3},\ldots ,s',\ldots s_{T})$
одно состояние удаляется из последовательности $a_{s_{2}}^{\rm {Del}}(s_{1},s_{2},s_{3},\ldots s_{T})=(s_{1},s_{3},\ldots s_{T})$ и
государство $s_{1}$ заменяется (заменяется) состоянием $s'_{1}$ , $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})$ .

Представьте теперь, что стоимость $c(a_{i})\in {\mathbf {R} }_{0}^{+}$ связанкаждому оператору. Даны две последовательности $S_{1}$ и $S_{2}$ ,идея состоит в том, чтобы измерить стоимость получения $S_{2}$ от $S_{1}$ с помощью операторов из алгебры. Позволять $A={a_{1},a_{2},\ldots a_{n}}$ — последовательность операторов такая, что применение всех операторов этой последовательности $A$ к первой последовательности $S_{1}$ дает вторую последовательность $S_{2}$ : $S_{2}=a_{1}\circ a_{2}\circ \ldots \circ a_{n}(S_{1})$ где $a_{1}\circ a_{2}$ обозначает составной оператор. С этим набором связываем стоимость $c(A)=\sum _{i=1}^{n}c(a_{i})$ , чтопредставляет собой общую стоимость трансформации. Здесь следует учитывать, что могут существовать разные такие последовательности. $A$ которые преобразуют $S_{1}$ в $S_{2}$ ; разумный выбор — выбрать самую дешевую из таких последовательностей. Таким образом, мырасстояние вызова
$d(S_{1},S_{2})=\min _{A}\left\{c(A)~{\rm {such~that}}~S_{2}=A(S_{1})\right\}$
то есть стоимость наименее затратного набора преобразований, которые превращают $S_{1}$ в $S_{2}$ . Обратите внимание, что $d(S_{1},S_{2})$ по определению неотрицательен, поскольку представляет собой сумму положительных затрат, и тривиально $d(S_{1},S_{2})=0$ тогда и только тогда, когда $S_{1}=S_{2}$ , то есть никаких затрат. Функция расстояния симметрична, если затраты на вставку и удаление равны. $c(a^{\rm {Ins}})=c(a^{\rm {Del}})$ ; термин «стоимость удаления» обычно относится к общей стоимости вставки и удаления.

Учитывая набор, состоящий только из трех основных операций, описанных выше, эта мера близости удовлетворяет треугольному неравенству. Однако транзитивность зависит от определения набора элементарных операций.

Критика

Хотя методы оптимального сопоставления широко используются в социологии и демографии, такие методы также имеют свои недостатки. Как отмечали ряд авторов (например, Л.Л. Ву ^[2]), основная проблема применения оптимального сопоставления состоит в правильном определении затрат $c(a_{i})$ .

Программное обеспечение

TDA — мощная программа, предлагающая доступ к некоторым последним разработкам в области анализа данных о переходном периоде.
STATA внедрила пакет для проведения анализа оптимального соответствия.
TraMineR -пакет с открытым исходным кодом — это R для анализа и визуализации состояний и последовательностей событий, включая анализ оптимального соответствия.

Ссылки и примечания

^ А. Эбботт и А. Цай, (2000) Анализ последовательностей и методы оптимального сопоставления в социологии: обзор и перспективы социологических методов и исследований], Vol. 29, 3–33. дои : 10.1177/0049124100029001001
^ ЛЛ Ву. (2000) Некоторые комментарии к статье «Анализ последовательностей и методы оптимального сопоставления в социологии: обзор и перспективы». Архивировано 24 октября 2006 г. в Wayback Machine Sociological Methods & Research, 29 41-64. дои : 10.1177/0049124100029001003

[1] А. Эбботт и А. Цай, (2000) Анализ последовательностей и методы оптимального сопоставления в социологии: обзор и перспективы социологических методов и исследований], Vol. 29, 3–33. дои : 10.1177/0049124100029001001

[2] ЛЛ Ву. (2000) Некоторые комментарии к статье «Анализ последовательностей и методы оптимального сопоставления в социологии: обзор и перспективы». Архивировано 24 октября 2006 г. в Wayback Machine Sociological Methods & Research, 29 41-64. дои : 10.1177/0049124100029001003

[1]

[2]