Eksploracja wzorców sekwencyjnych
Eksploracja wzorców sekwencyjnych to temat eksploracji danych , którego celem jest znalezienie statystycznie istotnych wzorców między przykładami danych, w których wartości są dostarczane w sekwencji. Zwykle zakłada się, że wartości są dyskretne, a zatem szeregów czasowych jest ściśle powiązana, ale zwykle uważana za inną działalność. Eksploracja wzorców sekwencyjnych to szczególny przypadek eksploracji danych strukturalnych .
Istnieje kilka kluczowych tradycyjnych problemów obliczeniowych rozwiązywanych w tej dziedzinie. Obejmują one budowanie wydajnych baz danych i indeksów informacji o sekwencjach, 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 rzecz biorąc, problemy eksploracji sekwencji można sklasyfikować jako eksplorację ciągów znaków , która zazwyczaj opiera się na algorytmach przetwarzania ciągów znaków, oraz eksplorację zestawów elementów , która zwykle opiera się na uczeniu się reguł asocjacyjnych . Lokalne modele procesów rozszerzyć 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 sekwencyjnego porządkowania.
Wydobywanie strun
Eksploracja ciągów zwykle dotyczy ograniczonego alfabetu elementów, które pojawiają się w sekwencji , ale sama sekwencja może być zazwyczaj bardzo długa. Przykładami alfabetu mogą być te w ASCII używanym w tekście języka naturalnego, zasady nukleotydowe „A”, „G”, „C” i „T” w sekwencjach DNA lub aminokwasy w sekwencjach białek . W biologicznych analiza ułożenia alfabetu w ciągach może być wykorzystana do badania genów i sekwencje 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 względem jej struktury i funkcji biologicznej . Zwykle osiąga się to najpierw poprzez identyfikację poszczególnych regionów lub jednostek strukturalnych w obrębie 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 wstawia się , delecje i mutacje występują w łańcuchu.
Przegląd i taksonomię kluczowych algorytmów porównywania sekwencji dla bioinformatyki przedstawia Abouelhoda i Ghanem (2010), które obejmują:
- Problemy związane z powtórzeniami: które dotyczą operacji na pojedynczych sekwencjach i mogą być oparte na dokładnych lub przybliżonych metodach dopasowywania ciągów w celu znajdowania rozproszonych powtórzeń o stałej i maksymalnej długości, znajdowania powtórzeń tandemowych oraz znajdowania unikalnych podsekwencji i brakujących (niepisanych) podsekwencje.
- Problemy z wyrównaniem: które dotyczą porównywania ciągów poprzez najpierw wyrównanie jednej 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 dopasowywania mogą opierać się na metodach dokładnych lub przybliżonych, a także można je sklasyfikować jako dopasowania globalne, dopasowania półglobalne i dopasowania lokalne. Zobacz wyrównanie sekwencji .
Eksploracja zestawów przedmiotów
Niektóre problemy w eksploracji sekwencji nadają się do odkrywania częstych zestawów przedmiotów i kolejności, w jakiej się pojawiają, na przykład szuka się reguł w postaci „jeśli {klient kupuje samochód}, prawdopodobnie {kupuje ubezpieczenie} w ciągu 1 tygodnia "lub w kontekście cen akcji, "jeśli {Nokia w górę i Ericsson w górę}, jest prawdopodobne, że {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 odkrywania prawidłowości między często występującymi przedmiotami w dużych transakcjach. Na przykład, analizując transakcje koszyków zakupowych klientów w supermarkecie, można stworzyć regułę, która brzmi: „jeśli klient kupuje razem cebulę i ziemniaki, prawdopodobnie kupi również mięso do hamburgerów w tej samej transakcji”.
Ankieta i taksonomia kluczowych algorytmów eksploracji zestawów przedmiotów została przedstawiona przez Han i in. (2007).
Dwie popularne techniki, które są stosowane w bazach danych sekwencji w celu eksploracji częstych zestawów pozycji, 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 handlowym. Detaliści mogą nie tylko zwiększyć swoje zyski, ale także obniżyć koszty poprzez odpowiednie zarządzanie alokacją 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ść wydobytych wzorców zakupowych.
Algorytmy
Powszechnie stosowane algorytmy obejmują:
- Algorytm GSP
- Sekwencyjne wykrywanie wzorców przy użyciu klas równoważności (SPADE)
- FreeSpan
- Rozpiętość przedrostka
- MAPrez
- Seq2Pat (do eksploracji wzorców sekwencyjnych w oparciu o ograniczenia)
Zobacz też
- Ekstrakcja kolokacji - technika obliczeniowa do znajdowania sekwencji słów
- Eksploracja procesów — technika eksploracji danych z wykorzystaniem dzienników zdarzeń
- Analiza sekwencji - proces analizy jednej lub więcej znanych sekwencji biologicznych
- Analiza sekwencji w naukach społecznych
- Grupowanie sekwencji – algorytm
- Znakowanie sekwencji
Linki zewnętrzne
- SPMF obejmuje implementacje typu open source GSP, PrefixSpan, SPADE, SPAM i wiele innych.