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

Анализ последовательности в социальных науках

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

Алгоритм

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

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

• одно состояние вставляется в последовательность ${\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})}$
• одно состояние удаляется из последовательности и ${\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})}$

Представьте теперь, что с каждым оператором связана стоимость . При наличии двух последовательностей и идея состоит в том, чтобы измерить стоимость получения из использования операторов из алгебры. Пусть будет последовательностью операторов, такой, что применение всех операторов этой последовательности к первой последовательности дает вторую последовательность : где обозначает составной оператор. С этим набором мы связываем стоимость , которая представляет собой общую стоимость преобразования. На этом этапе следует учитывать, что могут существовать различные такие последовательности , которые преобразуются в ; разумным выбором является выбор самой дешевой из таких последовательностей. Таким образом, мы называем расстояние , то есть стоимостью наименее дорогостоящего набора преобразований, которые превращаются в . Обратите внимание, что по определению неотрицательно, поскольку является суммой положительных стоимостей, и тривиально тогда и только тогда , когда , то есть нет стоимости. Функция расстояния симметрична, если стоимости вставки и удаления равны ; термин стоимость вставки обычно относится к общей стоимости вставки и удаления. ${\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 {such~that}}~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}})}$

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

Критика

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

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

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

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

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