Sekwencyjne wyszukiwanie wzorców - Sequential pattern mining

Sekwencyjne eksplorowanie wzorców to temat eksploracji danych dotyczący znajdowania statystycznie istotnych wzorców między przykładami danych, w których wartości są dostarczane w sekwencji. Zazwyczaj zakłada się, że wartości są dyskretne, a zatem eksploracja szeregów czasowych jest ściśle powiązana, ale zwykle uważana za inną działalność. Sekwencyjne eksplorowanie wzorców jest szczególnym przypadkiem eksploracji danych strukturalnych .

W tej dziedzinie istnieje kilka kluczowych tradycyjnych problemów obliczeniowych. Obejmują one budowanie wydajnych baz danych i indeksów dla informacji o sekwencji, wyodrębnianie często występujących wzorców, porównywanie sekwencji pod kątem podobieństwa i odzyskiwanie brakujących elementów sekwencji. Ogólnie, problemy z eksploracją sekwencji można sklasyfikować jako eksplorację ciągów, która zazwyczaj opiera się na algorytmach przetwarzania ciągów i eksploracji zestawów przedmiotów, która zazwyczaj opiera się na uczeniu się reguł asocjacyjnych . Modele procesów lokalnych rozszerzają eksplorację wzorców sekwencyjnych na bardziej złożone wzorce, które mogą obejmować (wyłączne) wybory, pętle i konstrukcje współbieżności oprócz konstrukcji porządkowania sekwencyjnego.

Wydobywanie strun

Eksploracja ciągów zazwyczaj dotyczy ograniczonego alfabetu dla elementów, które pojawiają się w sekwencji , ale sama sekwencja może być zazwyczaj bardzo długa. Przykładami alfabetu mogą być alfabety z zestawu znaków ASCII używane w tekście w języku naturalnym, zasady nukleotydowe „A”, „G”, „C” i „T” w sekwencjach DNA lub aminokwasy w sekwencjach białkowych . W zastosowaniach biologicznych analiza ułożenia alfabetu w ciągach może być wykorzystywana do badania sekwencji genów i białek w celu określenia ich właściwości. Znajomość sekwencji liter DNA lub białka nie jest celem samym w sobie. Głównym zadaniem jest raczej zrozumienie sekwencji pod kątem jej struktury i funkcji biologicznej . Zazwyczaj osiąga się to najpierw przez zidentyfikowanie poszczególnych regionów lub jednostek strukturalnych w każdej sekwencji, a następnie przypisanie funkcji do każdej jednostki strukturalnej. W wielu przypadkach wymaga to porównania danej sekwencji z poprzednio badanymi. Porównanie między ciągami staje się skomplikowane, gdy w ciągu występują insercje , delecje i mutacje .

Przegląd i taksonomię kluczowych algorytmów porównywania sekwencji dla bioinformatyki przedstawiają Abouelhoda i Ghanem (2010), które obejmują:

  • Problemy związane z powtórzeniami: dotyczą operacji na pojedynczych sekwencjach i mogą opierać się na dokładnym dopasowaniu ciągów lub przybliżonych metodach dopasowywania ciągów w celu znalezienia rozproszonych powtórzeń o stałej i maksymalnej długości, znajdowania powtórzeń tandemowych oraz znajdowania unikalnych podciągów i brakujących (nie-pisowni) podsekwencje.
  • Problemy z wyrównaniem: dotyczą porównania między ciągami, najpierw dopasowując jedną lub więcej sekwencji; przykłady popularnych metod obejmują BLAST do porównywania pojedynczej sekwencji z wieloma sekwencjami w bazie danych oraz ClustalW do wielu dopasowań. Algorytmy wyrównania mogą być oparte na metodach dokładnych lub przybliżonych, a także mogą być klasyfikowane jako wyrównanie globalne, wyrównanie półglobalne i wyrównanie lokalne. Zobacz dopasowanie sekwencji .

Wydobywanie zestawu przedmiotów

Niektóre problemy w eksploracji sekwencji pozwalają na odkrycie częstych zestawów przedmiotów i kolejności, w jakiej się pojawiają, na przykład szukanie reguł postaci „jeśli {klient kupi samochód}, prawdopodobnie {kupi ubezpieczenie} w ciągu 1 tygodnia ”, lub w kontekście cen akcji, „jeśli {Nokia w górę i Ericsson w górę}, prawdopodobnie {Motorola w górę i Samsung w górę} w ciągu 2 dni”. Tradycyjnie eksploracja zestawów przedmiotów jest wykorzystywana w aplikacjach marketingowych do wykrywania prawidłowości między często występującymi elementami w dużych transakcjach. Na przykład, analizując transakcje koszyków zakupów klientów w supermarkecie, można stworzyć regułę, która brzmi: „jeśli klient kupuje razem cebulę i ziemniaki, prawdopodobnie w ramach tej samej transakcji kupi również mięso hamburgerowe”.

Ankieta i taksonomia kluczowych algorytmów eksploracji zestawów pozycji jest przedstawiona przez Han i in. (2007).

Dwie popularne techniki, które są stosowane do sekwencjonowania baz danych w celu częstego eksploracji zestawów elementów, to wpływowy algorytm apriori i nowsza technika wzrostu FP .

Aplikacje

Przy dużej różnorodności produktów i zachowań zakupowych użytkowników, półka, na której prezentowane są produkty, jest jednym z najważniejszych zasobów w środowisku detalicznym. Detaliści mogą nie tylko zwiększyć swoje zyski, ale także obniżyć koszty poprzez odpowiednie zarządzanie przydziałem miejsca na półkach i ekspozycją produktów. Aby rozwiązać ten problem, George i Binu (2013) zaproponowali podejście do wydobywania wzorców zakupowych użytkowników za pomocą algorytmu PrefixSpan i umieszczania produktów na półkach w oparciu o kolejność wydobywanych wzorców zakupowych.

Algorytmy

Powszechnie stosowane algorytmy obejmują:

  • Algorytm GSP
  • Sequential Pattern Discovery przy użyciu klas równoważności (SPADE)
  • FreeSpan
  • Rozpiętość przedrostka
  • MAPres
  • Seq2Pat (do eksploracji wzorców sekwencyjnych w oparciu o ograniczenia)

Zobacz też

Bibliografia

Zewnętrzne linki