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

Не путать с максимальное соответствие.

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

Алгоритм

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

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

• одно государство ${displaystyle s}$ вставляется в последовательность ${displaystyle a_{s'}^{m {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}}^{m {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}}^{m {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)~{m {such~that}}~S_{2}=A(S_{1})ight}}$
то есть стоимость наименее дорогостоящего набора преобразований, ${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^{m {Ins}})=c(a^{m {Del}})}$; период, термин индель Стоимость обычно относится к общей стоимости вставки и удаления.

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

Критика

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

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

Оптимальное соответствие - также термин, используемый в статистическом моделировании причинные эффекты. В этом контексте он относится к сопоставлению «случаев» с «элементами управления» и полностью отделен от смысла анализа последовательностей.

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

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

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

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