Последовательный анализ шаблонов

Последовательный анализ шаблонов — это тема анализа данных, связанная с поиском статистически значимых шаблонов между примерами данных, где значения представлены в последовательности. ^{[1] [2]} Обычно предполагается, что значения дискретны, и поэтому анализ временных рядов тесно связан, но обычно считается другой деятельностью. Последовательный анализ шаблонов — это особый случай структурированного анализа данных .

В этой области рассматривается несколько основных традиционных вычислительных задач. К ним относятся создание эффективных баз данных и индексов для информации о последовательностях, извлечение часто встречающихся шаблонов, сравнение последовательностей на предмет сходства и восстановление отсутствующих членов последовательностей. В целом, проблемы извлечения последовательностей можно классифицировать как извлечение строк , которое обычно основано на алгоритмах обработки строк , и извлечение наборов элементов , которое обычно основано на изучении правил ассоциации . Локальные модели процессов ^[3] расширяют извлечение последовательных шаблонов до более сложных шаблонов, которые могут включать (исключающие) выборы, циклы и конструкции параллелизма в дополнение к конструкции последовательного упорядочения.

Струна майнинга

Строковый майнинг обычно имеет дело с ограниченным алфавитом для элементов, которые появляются в последовательности , но сама последовательность может быть, как правило, очень длинной. Примерами алфавита могут быть те, которые находятся в наборе символов ASCII , используемых в тексте на естественном языке, нуклеотидные основания «A», «G», «C» и «T» в последовательностях ДНК или аминокислоты для последовательностей белков . В биологических приложениях анализ расположения алфавита в строках может использоваться для изучения последовательностей генов и белков с целью определения их свойств. Знание последовательности букв ДНК или белка не является конечной целью само по себе. Скорее, основная задача состоит в том, чтобы понять последовательность с точки зрения ее структуры и биологической функции . Обычно это достигается сначала путем идентификации отдельных областей или структурных единиц в каждой последовательности, а затем назначения функции каждой структурной единице. Во многих случаях это требует сравнения данной последовательности с ранее изученными. Сравнение между строками усложняется, когда в строке происходят вставки , делеции и мутации .

Обзор и таксономия ключевых алгоритмов сравнения последовательностей для биоинформатики представлены Абуэльходой и Ганемом (2010), которые включают: ^[4]

• Задачи, связанные с повторами: которые связаны с операциями над отдельными последовательностями и могут быть основаны на методах точного или приблизительного сопоставления строк для поиска разбросанных повторов фиксированной и максимальной длины, поиска тандемных повторов и поиска уникальных подпоследовательностей и отсутствующих (незаписанных) подпоследовательностей.
• Проблемы выравнивания: которые имеют дело со сравнением строк путем предварительного выравнивания одной или нескольких последовательностей; примеры популярных методов включают BLAST для сравнения одной последовательности с несколькими последовательностями в базе данных и ClustalW для множественных выравниваний. Алгоритмы выравнивания могут быть основаны как на точных, так и на приблизительных методах, а также могут быть классифицированы как глобальное выравнивание, полуглобальное выравнивание и локальное выравнивание. См. выравнивание последовательностей .

Майнинг наборов предметов

Некоторые проблемы в последовательном майнинге позволяют обнаружить частые наборы элементов и порядок их появления, например, кто-то ищет правила вида «если {клиент покупает машину}, он или она, скорее всего, {купит страховку} в течение 1 недели», или в контексте цен на акции, «если {Nokia вверх и Ericsson вверх}, то, скорее всего, {Motorola вверх и Samsung вверх} в течение 2 дней». Традиционно, майнинг наборов элементов используется в маркетинговых приложениях для обнаружения закономерностей между часто встречающимися элементами в крупных транзакциях. Например, анализируя транзакции корзин покупок клиентов в супермаркете, можно создать правило, которое гласит: «если клиент покупает лук и картофель вместе, он или она, скорее всего, также купит мясо для гамбургера в той же транзакции».

Обзор и таксономия ключевых алгоритмов для анализа наборов элементов представлены Ханом и др. (2007). ^[5]

Двумя распространенными методами, применяемыми к базам данных секвенирования для частого извлечения наборов элементов, являются влиятельный алгоритм априори и более современный метод FP-growth .

Приложения

При большом разнообразии продуктов и покупательского поведения пользователей полка, на которой представлены продукты, является одним из важнейших ресурсов в розничной торговле. Розничные торговцы могут не только увеличить свою прибыль, но и снизить затраты за счет правильного управления распределением полочного пространства и выкладкой продуктов. Чтобы решить эту проблему, Джордж и Бину (2013) предложили подход к анализу пользовательских моделей покупок с использованием алгоритма PrefixSpan и размещению продуктов на полках в порядке, соответствующем выявленным моделям покупок. ^[6]

Алгоритмы

Обычно используемые алгоритмы включают в себя:

• алгоритм ГСП
• Последовательное обнаружение шаблонов с использованием классов эквивалентности (SPADE)
• FreeSpan
• ПрефиксSpan
• МАРПрес ^[7]
• Seq2Pat (для последовательного анализа шаблонов на основе ограничений) ^{[8] [9]}

Смотрите также

• Извлечение словосочетаний  – вычислительный метод поиска последовательностей слов
• Анализ процессов  – метод анализа данных с использованием журналов событий
• Анализ последовательности  – идентификация и изучение геномных последовательностей
• Анализ последовательностей в социальных науках  – Анализ наборов категориальных последовательностей
• Кластеризация последовательностей  – алгоритмСтраницы, отображающие описания викиданных в качестве резерваСтраницы с краткими описаниями без пробелов
• Маркировка последовательностей  – распознавание образовСтраницы, отображающие описания викиданных в качестве резерва

Ссылки

1. Mabroukeh, NR; Ezeife, CI (2010). «Таксономия алгоритмов последовательного анализа шаблонов». ACM Computing Surveys . 43 : 1–41. CiteSeerX  10.1.1.332.4745 . doi :10.1145/1824795.1824798. S2CID  207180619.
2. Бекини, А.; Бондиелли, А.; Делл'Ольо, П.; Марцеллони, Ф. (2023). «От базовых подходов к новым проблемам и приложениям в последовательном анализе шаблонов». Прикладные вычисления и интеллект . 3 (1): 44–78. doi : 10.3934/aci.2023004 .
3. Налог, Н.; Сидорова Н.; Хаакма, Р.; ван дер Аалст, Вил, член парламента (2016). «Анализ моделей локальных процессов». Журнал инноваций в цифровых экосистемах . 3 (2): 183–196. arXiv : 1606.06066 . doi :10.1016/j.jides.2016.11.001. S2CID  10872379.
4. Абуэльхода, М.; Ганем, М. (2010). «Строковый интеллектуальный анализ в биоинформатике». В Gaber, MM (ред.). Научный интеллектуальный анализ данных и обнаружение знаний . Springer. doi :10.1007/978-3-642-02788-8_9. ISBN 978-3-642-02787-1.
5. Хан, Дж.; Ченг, Х.; Синь, Д.; Янь, Х. (2007). «Изучение частых шаблонов: текущее состояние и будущие направления». Data Mining and Knowledge Discovery . 15 (1): 55–86. doi : 10.1007/s10618-006-0059-1 .
6. Джордж, А.; Бину, Д. (2013). «Подход к размещению продуктов в супермаркетах с использованием алгоритма PrefixSpan». Журнал Университета короля Сауда — компьютерные и информационные науки . 25 (1): 77–87. doi : 10.1016/j.jksuci.2012.07.001 .
7. Ахмад, Иштиак; Кази, Ваджахат М.; Куршид, Ахмед; Ахмад, Мунир; Хессли, Дэниел К.; Хаваджа, Иффат; Чоудхари, М. Икбал; Шакури, Абдул Р.; Насир-уд-Дин (1 мая 2008 г.). "MAPRes: Mining association patterns among preference amino acid residuals in the near of aminoides targeted for post-translational modifications". Протеомика . 8 (10): 1954–1958. doi :10.1002/pmic.200700657. PMID  18491291. S2CID  22362167.
8. Hosseininasab A, van Hoeve WJ, Cire AA (2019). «Последовательный анализ шаблонов на основе ограничений с диаграммами решений». Труды конференции AAAI по искусственному интеллекту . 33 : 1495–1502. arXiv : 1811.06086 . doi : 10.1609/aaai.v33i01.33011495 . S2CID  53427299.
9. "Seq2Pat: Библиотека генерации последовательностей в шаблоны". GitHub . 9 апреля 2022 г.

Внешние ссылки

• SPMF включает в себя реализации GSP, PrefixSpan, SPADE, SPAM и многих других с открытым исходным кодом.