Szekvenciális minta bányászat - Sequential pattern mining

Sorozatos minta bányászat a téma adatbányászati érintett megtalálása statisztikailag releváns minták közötti adatok példák, ahol az értékek szállítjuk sorrendben. Általában azt feltételezik, hogy az értékek diszkrétek, és így az idősoros bányászat szorosan összefügg, de általában más tevékenységnek számít. A szekvenciális mintázatú bányászat a strukturált adatbányászat különleges esete .

Ezen a területen számos kulcsfontosságú hagyományos számítási probléma foglalkozik. Ezek közé tartozik a hatékony adatbázisok és indexek építése a szekvenciainformációkhoz, a gyakran előforduló minták kinyerése, a szekvenciák hasonlósági összehasonlítása és a hiányzó szekvenciatagok helyreállítása. Általában szekvencia bányászat problémák közé sorolható húr bányászat , amely tipikusan alapul húr algoritmusok és tételkészlet bányászat , amely tipikusan alapuló asszociációs szabály tanulás . A helyi folyamatmodellek a szekvenciális mintabányászatot bonyolultabb mintákra is kiterjesztik, amelyek tartalmazhatnak (kizárólagos) választásokat, ciklusokat és párhuzamos konstrukciókat a szekvenciális rendezési konstrukción kívül.

Húrbányászat

A karakterlánc -bányászat általában korlátozott ábécével foglalkozik a sorozatban megjelenő elemek esetében , de maga a sorozat általában nagyon hosszú lehet. Példák egy ábécé azok lehetnek, amelyeket az ASCII karakterkészletet használt természetes nyelvi szövegben, nukleotid bázisokat az „A”, „G”, „C” és a „T” a DNS-szekvenciák , vagy az aminosavak esetében fehérjeszekvenciák . A biológiai alkalmazásokban az ábécé karakterláncokba sorolásának elemzése használható gén- és fehérje -szekvenciák vizsgálatára, hogy meghatározzák azok tulajdonságait. A DNS vagy a fehérje betűsorának ismerete önmagában nem végső cél. A fő feladat inkább a szekvencia megértése, szerkezete és biológiai funkciója szempontjából . Ezt általában úgy érik el, hogy minden egyes sorozaton belül azonosítják az egyes régiókat vagy szerkezeti egységeket, majd minden egyes szerkezeti egységhez rendelnek egy funkciót. Sok esetben ehhez szükség van egy adott szekvencia összehasonlítására a korábban tanulmányozottakkal. A karakterláncok összehasonlítása bonyolulttá válik, ha beillesztések , deléciók és mutációk fordulnak elő egy karakterláncban.

A bioinformatika szekvencia -összehasonlításának kulcsfontosságú algoritmusainak felmérését és rendszertanát Abouelhoda és Ghanem (2010) ismerteti, amelyek a következők:

  • Ismétléssel kapcsolatos problémák: az egyes szekvenciákon végzett műveletekre vonatkoznak, és pontos karakterlánc-illesztési vagy hozzávetőleges karakterlánc-egyeztetési módszereken alapulhatnak a szétszórt rögzített és maximális hosszúságú ismétlések megtalálására, a tandemismétlések megkeresésére, valamint az egyedi alsorozatok és hiányzó (helyesírás nélküli) keresésére részsorozatok.
  • Igazítási problémák: a karakterláncok összehasonlításával foglalkoznak, először egy vagy több szekvencia igazításával; a népszerű módszerek példái közé tartozik a BLAST egyetlen szekvencia összehasonlításához több szekvenciával az adatbázisban, és a ClustalW több igazításhoz. Az igazítási algoritmusok pontos vagy hozzávetőleges módszereken alapulhatnak, és globális igazítások, félig globális igazítások és helyi igazítások közé is sorolhatók. Lásd a sorozat beállítását .

Elemkészlet bányászat

A sorozatos bányászat bizonyos problémái gyakran felfedezik a gyakori tételeket és a megjelenési sorrendet, például a következő formájú szabályokat keresi: "ha {ügyfél vásárol egy autót}, akkor valószínűleg 1 héten belül {vásárol biztosítást} ", vagy a tőzsdei árfolyamok összefüggésében:" ha {a Nokia felfelé, az Ericsson pedig felfelé}, akkor valószínű, hogy {Motorola felfelé, a Samsung pedig felfelé} 2 napon belül ”. Hagyományosan az itemet bányászatot használják a marketing alkalmazásokban, hogy felfedezzék a nagy tranzakciók gyakran előforduló tételei közötti szabályszerűségeket. Például egy szupermarketben a vásárlói kosarak tranzakcióinak elemzésével olyan szabályt lehet létrehozni, amely így szól: "ha az ügyfél együtt vesz hagymát és burgonyát, akkor valószínűleg hamburgerhúst is vásárol ugyanazon ügylet során".

Az elemhalmaz -bányászat legfontosabb algoritmusainak felmérését és rendszertanát mutatják be Han és mtsai. (2007).

A szekvencia-adatbázisoknál a gyakori tételekbányászat során alkalmazott két általános technika a befolyásos apriori algoritmus és az újabb FP-növekedési technika.

Alkalmazások

A termékek és a vásárlási szokások nagy változatossága miatt a polc, amelyen a termékek láthatók, az egyik legfontosabb erőforrás a kiskereskedelmi környezetben. A kiskereskedők nemcsak a nyereségüket növelhetik, hanem a költségeket is csökkenthetik a polcfelosztás és a termékek megjelenítésének megfelelő kezelésével. Ennek a problémának a megoldására George és Binu (2013) javaslatot tettek egy megközelítésre a bányászati ​​felhasználók vásárlási mintáinak PrefixSpan algoritmusa segítségével, és a termékeket a bányászott beszerzési minták sorrendje alapján helyezik el a polcokon.

Algoritmusok

A leggyakrabban használt algoritmusok a következők:

  • GSP algoritmus
  • Szekvenciális mintafelismerés egyenértékűségi osztályok (SPADE) használatával
  • FreeSpan
  • ElőtagSpan
  • MAPres
  • Seq2Pat (kényszer alapú szekvenciális minta bányászathoz)

Lásd még

Hivatkozások

Külső linkek

  • Az SPMF a GSP, PrefixSpan, SPADE, SPAM és sok más nyílt forráskódú megvalósítását tartalmazza.