Jump to content

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

Последовательный анализ шаблонов — это тема интеллектуального анализа данных, связанная с поиском статистически значимых шаблонов между примерами данных, где значения доставляются в последовательности. [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]

См. также [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

  • SPMF включает в себя реализации GSP, PrefixSpan, SPADE, SPAM и многих других с открытым исходным кодом.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 0ca6dc72272b18cb9a9b2da893dd3d29__1702308480
URL1:https://arc.ask3.ru/arc/aa/0c/29/0ca6dc72272b18cb9a9b2da893dd3d29.html
Заголовок, (Title) документа по адресу, URL1:
Sequential pattern mining - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)