Последовательный анализ паттернов - Sequential pattern mining - Wikipedia

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

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

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

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

Обзор и систематика ключевых алгоритмов сравнения последовательностей в биоинформатике представлены Abouelhoda & Ghanem (2010), которые включают:[3]

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

Поиск предметов

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

Обзор и таксономия ключевых алгоритмов интеллектуального анализа наборов элементов представлены Han et al. (2007).[4]

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

Приложения

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

Алгоритмы

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

  • Алгоритм GSP
  • Последовательное обнаружение паттернов с использованием классов эквивалентности (SPADE)
  • FreeSpan
  • PrefixSpan
  • MAPres[6]
  • Seq2Pat (для последовательного анализа шаблонов на основе ограничений)[7]

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

Рекомендации

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

внешняя ссылка

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