Последовательный анализ шаблонов
Последовательный анализ шаблонов — это тема интеллектуального анализа данных, связанная с поиском статистически значимых шаблонов между примерами данных, где значения доставляются в последовательности. [1] [2] Обычно предполагается, что значения дискретны, и, таким образом, анализ временных рядов тесно связан, но обычно считается другим видом деятельности. Последовательный анализ шаблонов — это особый случай интеллектуального анализа структурированных данных .
В этой области решается несколько ключевых традиционных вычислительных задач. К ним относятся создание эффективных баз данных и индексов для информации о последовательностях, извлечение часто встречающихся шаблонов, сравнение последовательностей на предмет сходства и восстановление недостающих членов последовательности. В общем, проблемы интеллектуального анализа последовательностей можно классифицировать как интеллектуальный анализ строк , который обычно основан на алгоритмах обработки строк , и интеллектуальный анализ набора элементов , который обычно основан на изучении правил ассоциации . Локальные модели процессов [3] расширить последовательный анализ шаблонов до более сложных шаблонов, которые могут включать (эксклюзивные) варианты выбора, циклы и конструкции параллелизма в дополнение к конструкции последовательного упорядочивания.
Строковый майнинг [ править ]
Строковый анализ обычно имеет дело с ограниченным алфавитом для элементов, которые появляются в последовательности , но сама последовательность обычно может быть очень длинной. Примерами алфавита могут быть символы набора символов ASCII , используемые в тексте на естественном языке, нуклеотидные основания «A», «G», «C» и «T» в последовательностях ДНК или аминокислоты для белковых последовательностей . В биологических приложениях анализ расположения алфавита в строках можно использовать для изучения последовательностей генов и белков и определения их свойств. Знание последовательности букв ДНК или белка само по себе не является конечной целью. Скорее, основная задача состоит в том, чтобы понять последовательность с точки зрения ее структуры и биологической функции . Обычно это достигается сначала путем идентификации отдельных областей или структурных единиц внутри каждой последовательности, а затем присвоения функции каждой структурной единице. Во многих случаях для этого требуется сравнение заданной последовательности с ранее изученными. Сравнение строк усложняется при вставках. , удаления и мутации в строке происходят .
Обзор и таксономия ключевых алгоритмов сравнения последовательностей для биоинформатики представлены Abouelhoda & Ghanem (2010), которые включают: [4]
- Проблемы, связанные с повторами: которые касаются операций с отдельными последовательностями и могут быть основаны на методах точного или приблизительного сопоставления строк для поиска рассредоточенных повторов фиксированной и максимальной длины, поиска тандемных повторов, а также поиска уникальных и отсутствующих подпоследовательностей (не написанных). подпоследовательности.
- Проблемы выравнивания: связаны со сравнением строк путем предварительного выравнивания одной или нескольких последовательностей; примеры популярных методов включают BLAST для сравнения одной последовательности с несколькими последовательностями в базе данных и ClustalW для множественного выравнивания. Алгоритмы выравнивания могут быть основаны на точных или приближенных методах, а также могут быть классифицированы как глобальное выравнивание, полуглобальное выравнивание и локальное выравнивание. См. выравнивание последовательности .
Добыча набора предметов [ править ]
Некоторые проблемы последовательного анализа позволяют обнаружить часто встречающиеся наборы элементов и порядок их появления, например, ищут правила вида «если {клиент покупает автомобиль}, он или она, скорее всего, {купит страховку} в течение 1 недели». «или в контексте цен на акции: «если {Nokia поднимется и Ericsson поднимется}, вполне вероятно, что {Motorola поднимется и Samsung поднимется} в течение 2 дней». Традиционно анализ набора элементов используется в маркетинговых приложениях для обнаружения закономерностей между часто встречающимися одновременно элементами в крупных транзакциях. Например, анализируя транзакции с покупательскими корзинами в супермаркете, можно создать правило, которое гласит: «Если покупатель покупает лук и картофель вместе, он или она, вероятно, также купит мясо для гамбургера в той же транзакции».
Обзор и таксономия ключевых алгоритмов интеллектуального анализа набора элементов представлены Han et al. (2007). [5]
Двумя распространенными методами, которые применяются к базам данных последовательностей для частого анализа наборов элементов, являются влиятельный априорный алгоритм и более поздний метод роста FP .
Приложения [ править ]
Учитывая большое разнообразие продуктов и покупательское поведение пользователей, полка, на которой выставлены продукты, является одним из наиболее важных ресурсов в розничной торговле. Розничные торговцы могут не только увеличить свою прибыль, но и снизить затраты за счет правильного управления распределением полочного пространства и выкладкой товаров. Чтобы решить эту проблему, Джордж и Бину (2013) предложили подход к выявлению моделей покупок пользователей с использованием алгоритма PrefixSpan и размещению продуктов на полках в соответствии с порядком выявленных моделей покупок. [6]
Алгоритмы [ править ]
Обычно используемые алгоритмы включают в себя:
- Алгоритм GSP
- Последовательное обнаружение шаблонов с использованием классов эквивалентности (SPADE)
- ФриСпан
- ПрефиксSpan
- МАПрес [7]
- Seq2Pat (для последовательного анализа шаблонов на основе ограничений) [8] [9]
См. также [ править ]
- Извлечение словосочетаний - вычислительный метод поиска последовательностей слов.
- Интеллектуальный анализ процессов — метод интеллектуального анализа данных с использованием журналов событий.
- Анализ последовательностей – идентификация и изучение геномных последовательностей.
- Анализ последовательностей в социальных науках . Анализ наборов категориальных последовательностей.
- Кластеризация последовательностей – алгоритм.
- Маркировка последовательностей – распознавание образов.
Ссылки [ править ]
- ^ Мабруке, Северная Каролина; Эзейфе, CI (2010). «Таксономия алгоритмов последовательного анализа шаблонов». Обзоры вычислительной техники ACM . 43 : 1–41. CiteSeerX 10.1.1.332.4745 . дои : 10.1145/1824795.1824798 . S2CID 207180619 .
- ^ Бечини, А.; Бондиелли, А.; Делл'Ольо, П.; Марчеллонии, Ф. (2023). «От базовых подходов к новым задачам и приложениям в последовательном анализе шаблонов» . Прикладные вычисления и интеллект . 3 (1): 44–78. дои : 10.3934/aci.2023004 .
- ^ Налог, Н.; Сидорова Н.; Хаакма, Р.; ван дер Аалст, Вил, член парламента (2016). «Анализ моделей локальных процессов». Журнал инноваций в цифровых экосистемах . 3 (2): 183–196. arXiv : 1606.06066 . дои : 10.1016/j.jides.2016.11.001 . S2CID 10872379 .
- ^ Абуэльхода, М.; Ганем, М. (2010). «Струнный майнинг в биоинформатике». В Габере, ММ (ред.). Научный анализ данных и обнаружение знаний . Спрингер. дои : 10.1007/978-3-642-02788-8_9 . ISBN 978-3-642-02787-1 .
- ^ Хан, Дж.; Ченг, Х.; Синь, Д.; Ян, X. (2007). «Майнинг частых шаблонов: текущее состояние и будущие направления» . Интеллектуальный анализ данных и обнаружение знаний . 15 (1): 55–86. дои : 10.1007/s10618-006-0059-1 .
- ^ Джордж, А.; Бину, Д. (2013). «Подход к размещению товаров в супермаркетах с использованием алгоритма PrefixSpan» . Журнал Университета короля Сауда по компьютерным и информационным наукам . 25 (1): 77–87. дои : 10.1016/j.jksuci.2012.07.001 .
- ^ Ахмад, Иштиак; Кази, Ваджахат М.; Хуршид, Ахмед; Ахмад, Мунир; Хессли, Дэниел К.; Хаваджа, Иффат; Чоудхари, М. Икбал; Шакури, Абдул Р.; Насир-уд-Дин (1 мая 2008 г.). «MAPRes: паттерны ассоциации майнинга среди предпочтительных аминокислотных остатков вблизи аминокислот, предназначенных для посттрансляционных модификаций». Протеомика . 8 (10): 1954–1958. дои : 10.1002/pmic.200700657 . ПМИД 18491291 . S2CID 22362167 .
- ^ Хоссейнинасаб А., ван Хёв В.Дж., Сире А.А. (2019). «Последовательный анализ шаблонов на основе ограничений с использованием диаграмм решений» . Материалы конференции AAAI по искусственному интеллекту . 33 : 1495–1502. arXiv : 1811.06086 . дои : 10.1609/aaai.v33i01.33011495 . S2CID 53427299 .
- ^ «Seq2Pat: библиотека генерации последовательностей в шаблоны» . Гитхаб . 9 апреля 2022 г.
Внешние ссылки [ править ]
- SPMF включает в себя реализации GSP, PrefixSpan, SPADE, SPAM и многих других с открытым исходным кодом.