GSP algoritm
GSP-algoritm ( Generalized Sequential Pattern Algorithm) är en algoritm som används för sekvensutvinning . Algoritmerna för att lösa sekvensminingproblem är mestadels baserade på apriori (nivåmässigt) algoritmen. Ett sätt att använda det nivåmässiga paradigmet är att först upptäcka alla vanliga föremål på ett nivåmässigt sätt. Det betyder helt enkelt att man räknar förekomsten av alla singleton-element i databasen. Sedan filtreras transaktionerna genom att de icke frekventa objekten tas bort. I slutet av detta steg består varje transaktion endast av de frekventa element som den ursprungligen innehöll. Denna modifierade databas blir en indata till GSP-algoritmen. Denna process kräver en gång över hela databasen .
GSP-algoritm gör flera databaspass. I det första passet räknas alla enstaka föremål (1-sekvenser). Från de frekventa objekten bildas en uppsättning kandidat 2-sekvenser, och ytterligare ett pass görs för att identifiera deras frekvens. De frekventa 2-sekvenserna används för att generera kandidat 3-sekvenserna, och denna process upprepas tills inga fler frekventa sekvenser hittas. Det finns två huvudsteg i algoritmen.
- Kandidatgeneration. Givet uppsättningen av frekventa (k-1)-frekventa sekvenser Fk -1 , genereras kandidaterna för nästa pass genom att förena F(k-1) med sig själv. En beskärningsfas eliminerar varje sekvens, vars åtminstone en av följderna inte är frekventa.
- Stödräkning. Normalt används en hashträdbaserad sökning för effektiv stödräkning. Slutligen tas icke-maximalt frekventa sekvenser bort.
Algoritm
F 1 = mängden frekventa 1-sekvens k=2, gör medan F k-1 != Null; Generera kandidatmängder C k (uppsättning av kandidat-k-sekvenser); För alla ingångssekvenser s i databasen D do Öka antalet a i C k om s stöder en End do Fk = {a ∈ C k så att dess frekvens överstiger tröskeln} k = k+1; End do Result = Uppsättning av alla frekventa sekvenser är föreningen av alla F k :n
Algoritmen ovan ser ut som Apriori-algoritmen . En huvudskillnad är dock genereringen av kandidatuppsättningar. Låt oss anta att:
- A → B och A → C
är två frekventa 2-sekvenser. Objekten som är involverade i dessa sekvenser är (A, B) respektive (A,C). Kandidatgenereringen i en vanlig Apriori-stil skulle ge (A, B, C) som en 3-postuppsättning, men i föreliggande sammanhang får vi följande 3-sekvenser som ett resultat av att sammanfoga ovanstående 2-sekvenser
- A → B → C, A → C → B och A → BC
Kandidatgenereringsfasen tar hänsyn till detta. GSP-algoritmen upptäcker frekventa sekvenser, vilket tillåter tidsbegränsningar såsom maximalt gap och minsta gap mellan sekvenselementen. Dessutom stöder den föreställningen om ett glidande fönster, dvs. ett tidsintervall inom vilket föremål observeras som tillhörande samma händelse, även om de härrör från olika händelser.
Se även
- R. Srikant och R. Agrawal. 1996. Mining Sequential Patterns: Generalizations and Performance Improvements . I Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology (EDBT '96), Peter MG Apers, Mokrane Bouzeghoub och Georges Gardarin (Eds.). Springer-Verlag, London, Storbritannien, Storbritannien, 3–17.
- Pujari, Arun K. (2001). Datautvinningstekniker . Universitetspressen. ISBN 81-7371-380-4 . (sid. 256-260) , sid. 256, på Google Books
- Zaki, MJ Machine Learning (2001) 42: 31 .
externa länkar
- SPMF inkluderar en öppen källkodsimplementering av GSP-algoritmen samt PrefixSpan , SPADE, SPAM, ClaSP, CloSpan och BIDE.