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ż
- Wydobywanie procesów
- Analiza sekwencji (bioinformatyka)
- Analiza sekwencji społecznej
- Grupowanie sekwencji
- Etykietowanie sekwencji
Bibliografia
Zewnętrzne linki
- SPMF zawiera implementacje open-source GSP, PrefixSpan, SPADE, SPAM i wiele innych.