Последовательный анализ шаблонов - это тема интеллектуального анализа данных, связанная с поиском статистически значимых шаблонов между примерами данных, где значения доставляются в последовательности. [1] Обычно предполагается, что значения дискретны, и, таким образом, анализ временных рядов тесно связан, но обычно рассматривается как другой вид деятельности. Последовательный анализ шаблонов - это особый случай исследования структурированных данных .
В этой области решаются несколько ключевых традиционных вычислительных задач. К ним относятся создание эффективных баз данных и индексов для информации о последовательностях, извлечение часто встречающихся шаблонов, сравнение последовательностей на предмет сходства и восстановление отсутствующих членов последовательностей. В общем, проблемы интеллектуального анализа последовательности можно классифицировать как интеллектуальный анализ строк, который обычно основан на алгоритмах обработки строк и интеллектуальный анализ набора элементов, который обычно основан на изучении правил ассоциации . Модели локальных процессов [2] расширяют последовательный анализ шаблонов до более сложных шаблонов, которые могут включать (исключительные) варианты выбора, циклы и конструкции параллелизма в дополнение к конструкции последовательного упорядочения.
Струнный майнинг
Анализ строк обычно имеет дело с ограниченным алфавитом для элементов, которые появляются в последовательности , но сама последовательность обычно может быть очень длинной. Примерами алфавита могут быть алфавиты в наборе символов ASCII, используемом в тексте на естественном языке, нуклеотидные основания «A», «G», «C» и «T» в последовательностях ДНК или аминокислоты для последовательностей белков . В приложениях биологии анализ расположения алфавита в строках может использоваться для изучения последовательностей генов и белков для определения их свойств. Знание последовательности букв ДНК или белка не является самоцелью. Скорее, основная задача - понять последовательность с точки зрения ее структуры и биологической функции . Обычно это достигается сначала путем идентификации отдельных регионов или структурных единиц в каждой последовательности, а затем присвоения функции каждой структурной единице. Во многих случаях это требует сравнения заданной последовательности с ранее изученными. Сравнение между строками усложняется, когда в строке происходят вставки , удаления и мутации .
Обзор и систематика ключевых алгоритмов сравнения последовательностей для биоинформатики представлены Abouelhoda & Ghanem (2010), которые включают: [3]
- Проблемы , связанные с повторами : которые имеют дело с операциями с отдельными последовательностями и могут быть основаны на точном сопоставлении строк или методах приблизительного сопоставления строк для поиска рассредоточенных повторов фиксированной длины и максимальной длины, нахождения тандемных повторов, а также нахождения уникальных подпоследовательностей и отсутствующих (без написания) подпоследовательности.
- Проблемы выравнивания: которые касаются сравнения между строками путем первого выравнивания одной или нескольких последовательностей; Примеры популярных методов включают BLAST для сравнения одной последовательности с множеством последовательностей в базе данных и ClustalW для множественных выравниваний. Алгоритмы выравнивания могут быть основаны либо на точных, либо на приближенных методах, а также могут быть классифицированы как глобальные выравнивания, полуглобальные выравнивания и локальные выравнивания. См. Выравнивание последовательностей .
Майнинг наборов предметов
Некоторые проблемы в последовательном майнинге позволяют обнаруживать частые наборы элементов и порядок, в котором они появляются, например, кто-то ищет правила вида «если {клиент покупает машину}, он или она, вероятно, {купит страховку} в течение 1 недели. ", или в контексте цен на акции," если {Nokia подорожает, а Ericsson подорожает}, вполне вероятно, что {Motorola подорожает, а Samsung подорожает} в течение 2 дней "». Традиционно интеллектуальный анализ наборов элементов используется в маркетинговых приложениях для обнаружения закономерностей между часто встречающимися элементами в крупных транзакциях. Например, анализируя транзакции покупательских корзин в супермаркете, можно создать правило, которое гласит: «Если клиент покупает лук и картофель вместе, он или она, вероятно, также купит мясо для гамбургеров в той же транзакции».
Обзор и таксономия ключевых алгоритмов интеллектуального анализа наборов элементов представлены Han et al. (2007). [4]
Два общих метода, которые применяются к базам данных последовательностей для частого анализа наборов элементов, - это влиятельный априорный алгоритм и новейший метод FP-роста .
Приложения
С большим разнообразием продуктов и покупательского поведения пользователей полка, на которой выставлены продукты, является одним из самых важных ресурсов в розничной среде. Розничные торговцы могут не только увеличить свою прибыль, но и снизить затраты за счет правильного управления распределением полочного пространства и выкладкой товаров. Чтобы решить эту проблему, Джордж и Бину (2013) предложили подход к поиску шаблонов покупок пользователей с использованием алгоритма PrefixSpan и размещению продуктов на полках в соответствии с порядком найденных шаблонов покупок. [5]
Алгоритмы
Обычно используемые алгоритмы включают:
- Алгоритм GSP
- Последовательное обнаружение паттернов с использованием классов эквивалентности (SPADE)
- FreeSpan
- PrefixSpan
- MAPres [6]
- Seq2Pat (для последовательного анализа шаблонов на основе ограничений) [7]
Смотрите также
Рекомендации
- ^ Mabroukeh, NR; Эзейфе, CI (2010). «Таксономия алгоритмов последовательного анализа шаблонов». ACM Computing Surveys . 43 : 1–41. CiteSeerX 10.1.1.332.4745 . DOI : 10.1145 / 1824795.1824798 . S2CID 207180619 .
- ^ Налог, N .; Сидорова, Н .; Haakma, R .; ван дер Аалст, Wil MP (2016). «Горные модели локальных процессов». Журнал инноваций в цифровых экосистемах . 3 (2): 183–196. arXiv : 1606.06066 . DOI : 10.1016 / j.jides.2016.11.001 . S2CID 10872379 .
- ^ Abouelhoda, M .; Ганем, М. (2010). «Струнный анализ в биоинформатике». В Габере, М.М. (ред.). Научный анализ данных и открытие знаний . Springer. DOI : 10.1007 / 978-3-642-02788-8_9 . ISBN 978-3-642-02787-1.
- ^ Han, J .; Cheng, H .; Xin, D .; Ян, X. (2007). «Частый поиск паттернов: текущее состояние и будущие направления» . Интеллектуальный анализ данных и обнаружение знаний . 15 (1): 55–86. DOI : 10.1007 / s10618-006-0059-1 .
- ^ Джордж, А .; Бину Д. (2013). «Подход к размещению товаров в супермаркетах с использованием алгоритма PrefixSpan» . Журнал Университета Короля Сауда - Компьютерные и информационные науки . 25 (1): 77–87. DOI : 10.1016 / j.jksuci.2012.07.001 .
- ^ Ахмад, Иштиак; Qazi, Wajahat M .; Хуршид, Ахмед; Ахмад, Мунир; Hoessli, Daniel C .; Хаваджа, Иффат; Чоудхари, М. Икбал; Shakoori, Abdul R .; Насир-уд-Дин (1 мая 2008 г.). «MAPRes: паттерны ассоциации между предпочтительными аминокислотными остатками рядом с аминокислотами, предназначенными для посттрансляционных модификаций». Протеомика . 8 (10): 1954–1958. DOI : 10.1002 / pmic.200700657 . PMID 18491291 . S2CID 22362167 .
- ^ Хоссейнинасаб А, ван Хов В.Дж., Сире А.А. (2019). «Последовательный анализ шаблонов на основе ограничений с помощью диаграмм принятия решений» . Труды конференции AAAI по искусственному интеллекту . 33 : 1495–1502. DOI : 10.1609 / aaai.v33i01.33011495 . S2CID 53427299 .
Внешние ссылки
- SPMF включает реализации с открытым исходным кодом GSP, PrefixSpan, SPADE, SPAM и многие другие.