Szekvenciális mintázatok

A bevásárlókosár adatok gyakran tartalmaznak időbeli információkat arról, hogy egy adott terméket mikor vásároltak meg a vásárlók. Az ilyen információk felhasználásával összeállíthatjuk azon tranzakciók sorrendjét, melyeket egy adott vásárló hajtott végre egy adott időperiódusban. Ehhez hasonlóan a tudományos kísérletek során begyűjtött eseményalapú adatokhoz, vagy az olyan fizikai rendszerek megfigyelése során keletkezett adatokhoz is hozzátartozik a szekvenciális jelleg, mint például a telekommunikációs hálózatok, számítógéphálózatok és vezeték nélküli érzékelő hálózatok. Ez azt jelenti, hogy egy általában idő- vagy térbeli elsőbbségen alapuló sorrendi reláció áll fenn az ilyen adatokban előforduló események között. Az asszociációs mintázatok eddig tárgyalt fogalmai azonban csak az együttes előfordulást hangsúlyozzák a kapcsolatokban, és nem veszik figyelembe az adatokban rejlő szekvenciális információkat. Ez utóbbi információk hasznosak lehetnek egy dinamikai rendszer ismétlődő jellemzőinek azonosításában, vagy bizonyos események jövőbeli előfordulásainak előrejelzésében. Ebben a szakaszban a szekvenciális mintázatok és a feltárásukra kifejlesztett algoritmusok alapvető fogalmait mutatjuk be.

7.3. ábra - Példa szekvenciális adatbázisra

Példa szekvenciális adatbázisra

A probléma megfogalmazása

A szekvenciális mintázatok feltárási problémájának bemenete egy szekvenciális adatállomány, amely a 7.3. ábra bal oldalán látható. Minden sor az adott objektumhoz köthető események előfordulásait tartalmazza egy adott időpillanatban. Például az első sor a t=10 időpillanatban előfordult eseményeket tartalmazza az A objektumra. Ha az összes, az A objektumhoz tartozó eseményt sorba rendezzük az időbélyegeik szerint, akkor egy, az A objektumhoz tartozó sorozatot kapunk, ahogy az a 7.3. ábra jobb oldalán is látható.

Általánosságban elmondható, hogy egy sorozat elemek egy rendezett listája. Egy sorozatot s= e 1 e 2 e 3 e n módon jelölhetünk, ahol minden e j elem egy vagy több esemény együttese, azaz e j ={ i 1 , i 2 ,, i k } . A következőkben néhány példát adunk meg sorozatokra:

  • Egy weboldal egy látogatója által megtekintett weblapok sorozata:

{Nyitólap} {Műszaki cikkek} {Fényképezőgépek és videokamerák} {Digitális fényképezőgépek} {Bevásárlókosár} {Rendelés véglegesítése} {Vásárlás folytatása}

  • A Three-Mile Island-en történt nukleáris szerencsétlenséghez vezető események sorozata:

{gyantaelzáródás} {elvezető szelep elzáródása} {tápvízveszteség} {lezárt kondenzátor csiszoló elvezető szelep} {rásegítő szivattyú lekapcsolása} {fő vízszivattyú lekapcsolása} {fő turbina leállása} {reaktor nyomásának növekedése}

  • Egy informatikus hallgató által felvett kurzusok sorozata:

{Adatszerkezetek és algoritmusok, Bevezetés az operációs rendszerekbe} {Adatbázisrendszerek, Számítógéparchitektúrák} {Számítógéphálózatok, Szoftverfejlesztés} {Számítógépes grafika, Párhuzamos programozás}

Egy sorozatot a hosszával és az előforduló események számával írhatunk le. Egy sorozat hossza megegyezik a sorozatban lévő elemek számával, míg egy k -sorozat egy olyan sorozat, amely k eseményt tartalmaz. Az előző példa webes sorozata 7 elemet és 7 eseményt tartalmaz, a Three-Mile Island-ben történt események sorozata 8 elemből és 8 eseményből áll, a kurzusok sorozata pedig 4 elemet és 8 eseményt tartalmaz.

A 7.4. ábra különböző alkalmazási területeken definiált sorozatokra, elemekre és eseményekre mutat be példákat. Az utolsó sor kivételével az első három területhez tartozó sorrendi attribútumok mind a naptári időnek felelnek meg. Az utolsó sorban pedig a bázisok (A, C, G, T) génsorozatbeli helyének felel meg a sorrendi attribútum. Bár a szekvenciális mintázatok tárgyalása során főleg az időbeli eseményekre koncentrálunk, kitérünk arra az esetre is, amikor az eseményeknek térbeli elrendezésük van.

7.4. ábra - Példák szekvenciális adatok elemeire és eseményeire

Példák szekvenciális adatok elemeire és eseményeire

Részsorozatok

Egy t sorozat egy másik, s sorozat részsorozata, ha t minden rendezett eleme s egy rendezett elemének részhalmaza. Formálisan, a t= t 1 t 2 t m sorozat az s= s 1 s 2 s n részsorozata, ha léteznek olyan 1 j 1 j 2 j m n egész számok, hogy t 1 s j 1 , t 2 s j 2 ,, t m s j m . Ha t az s részsorozata, akkor azt mondjuk, hogy s tartalmazza t -t. A következő táblázat különböző sorozatokhoz mutat példákat a részsorozatok fogalmának szemléltetésére.

s sorozat

t sorozat

t részsorozata-e s -nek?

 {2,4}{3,5,6} {8} 

 {2} {3,6} {8} 

igen

 {2,4} {3,5,6} {8} 

 {2} {8} 

igen

 {1,2} {3,4} 

 {1} {2} 

nem

 {2,4} {2,4} {2,5} 

 {2} {4} 

igen

Szekvenciális mintázatok feltárása

Legyen D egy egy vagy több adatsorozatot tartalmazó adatállomány. Az adatsorozat kifejezés egyetlen adatobjektumhoz tartozó események egy rendezett sorozatát jelenti. A 7.3. ábrán látható adatállomány például három adatsorozatot tartalmaz, minden objektumhoz, az A -hoz, B -hez és C -hez is egyet-egyet.

Egy s sorozat támogatottsága az s -t tartalmazó adatsorozatok hányadával egyenlő. Ha s támogatottsága nagyobb vagy egyenlő, mint egy, a felhasználó által meghatározott minsup küszöbérték, akkor s -t egy szekvenciális mintázatnak (más néven gyakori sorozatnak) nyilvánítjuk.

7.1 Definíció

(Szekvenciális mintázatok feltárása) Ha adott egy D szekvenciális adatállomány, és egy a felhasználó által meghatározott minsup küszöbérték, akkor a szekvenciális mintázatok feltárásának feladata abban áll, hogy megtaláljuk az összes olyan sorozatot, amelyek támogatottsága nagyobb vagy egyenlő mint a minsup érték.

A 7.5. ábrán egy olyan adatállomány látható, amely öt adatsorozatot tartalmaz. Az {1}{2} sorozat támogatottsága 80% , mert az öt adatsorozat közül négyben fordul elő ( D kivételével minden objektumban). Ha feltesszük, hogy az alsó támogatottsági küszöb 50% , akkor szekvenciális mintázatnak tekinthetünk minden olyan sorozatot, amely legalább három adatsorozatban megjelenik. A megadott adatállományból kinyert szekvenciális mintázatok közé tartoznak például {1}{2} , {1,2} , {2,3} , {1,2}{2,3} , stb.

7.5. ábra - Egy öt adatsorozatot tartalmazó adatállományból származtatott szekvenciális mintázatok

Egy öt adatsorozatot tartalmazó adatállományból származtatott szekvenciális mintázatok

A szekvenciális mintázatok feltárásának feladata számításigény szempontjából komoly kihívást jelent, mert egy adott adatsorozat exponenciálisan sok sorozatot tartalmaz. Például az {a,b}{c,d,e}{f}{g,h,i} adatsorozat olyan sorozatokat tartalmaz, mint például az {a}{c,d}{f}{g} , {c,d,e} , {b}{g} , stb. Könnyen megmutatható, hogy egy n eseményt tartalmazó adatsorozatban összesen n k számú k -sorozat van. Így egy kilenc eseményből álló adatsorozat

( 9 1 )+( 9 2 )++( 9 9 )= 2 9 1=511

különböző sorozatot tartalmaz.

Nyers erővel megközelítve a szekvenciális mintázatok generálásának problémáját, felsorolhatjuk az összes lehetséges sorozatot és kiszámíthatjuk a hozzájuk tartozó támogatottságokat. Ha n számú esemény adott, akkor először az 1-sorozat jelölteket generáljuk, majd a 2-sorozat jelölteket, 3-sorozat jelölteket, és így tovább:

1-sorozatok:

i 1 , i 2 , , i n

2-sorozatok:

{ i 1 , i 2 } , { i 1 , i 3 } , , { i n1 , i n } ,

{ i 1 }{ i 1 } , { i 1 }{ i 2 } , , { i n1 }{ i n }

3-sorozatok:

{ i 1 , i 2 , i 3 } , { i 1 , i 2 , i 4 } , , { i 1 , i 2 }{ i 1 } , ,

{ i 1 }{ i 1 , i 2 } , , { i 1 }{ i 1 }{ i 1 } , , { i n }{ i n }{ i n }

Figyeljük meg, hogy a sorozat jelöltek száma lényegesen nagyobb, mint az elemhalmaz jelölteké. A jelöltek ezen többletének két oka van:

  1. Egy elem legfeljebb egyszer jelenhet meg egy elemhalmazban, egy esemény viszont egynél többször is előfordulhat egy sorozatban. Ha adott két elem, i 1 és i 2 , akkor csak egyetlen 2-elemhalmaz jelölt képezhető belőlük, { i 1 , i 2 } . Ezzel szemben viszont sok 2-sorozat jelölt van, mint például { i 1 , i 2 } , { i 1 }{ i 2 } , { i 2 }{ i 1 } és { i 1 , i 1 } .

  2. A sorozatokban számít a sorrend, az elemhalmazokban viszont nem. Például {1,2} és {2,1} ugyanazt az elemhalmazt jelenti, míg { i 1 }{ i 2 } és { i 2 }{ i 1 } különböző sorozatokat jelentenek, amelyeket külön kell generálni.

Az apriori-elv érvényes a szekvenciális adatokra is, mivel minden olyan adatsorozatnak, amely egy k -sorozatot tartalmaz, tartalmaznia kell annak minden (k1) -részsorozatát is. Kifejleszthetünk egy Apriori-szerű algoritmust a szekvenciális mintázatok szekvenciális adatállományokból való kinyerésére. Az eljárás alapfelépítése 1. algoritmusban látható.

7.1. algoritmus. Apriori-szerű algoritmus szekvenciális mintázatok feltárásához

1: k=1

2: F k ={i|iI σ({i}) N minsup} {az összes gyakori 1-részsorozat megkeresése}

3:repeat

4: k=k+1

5: C k =AprioriGen( F k1 ) {a k -részsorozat jelöltek generálása}

6: for minden tT részsorozatra do

7: C t =részsorozat( C k ,t) {az összes jelölt azonosítása, amelyeket t tartalmaz}

8: for minden c C t k -részsorozat jelöltre do

9: σ(c)=σ(c)+1 {a támogatottsági számláló növelése}

10: end for

11: end for

12: F k ={c|c C k σ(c) N minsup} {a gyakori k -részsorozatok kinyerése}

13: until F k =

14: Válasz = F k

Vegyük észre, hogy az algoritmus felépítése majdnem teljesen megegyezik az előző fejezetben tárgyalt a 6.1. algoritmuséval. Az algoritmus iteratív módon generálja az új k -sorozat jelölteket, lenyesi azokat a jelölteket, amelyek (k1) -részsorozatai nem gyakoriak, ezután pedig kiszámítja a fennmaradó jelöltek támogatottságát a szekvenciális mintázatok azonosításához. A következőkben ezeket a lépéseket tárgyaljuk részletesen.

Jelöltgenerálás

Két gyakori (k1) -sorozat egyesítésével hozunk létre egy k -sorozat jelöltet. Hogy elkerüljük a duplikált jelöltgenerálást, idézzük fel, hogy a hagyományos Apriori algoritmus csak akkor egyesít két gyakori k -elemhalmazt, ha azok első k1 eleme megegyezik. Ehhez hasonló megközelítést alkalmazhatunk sorozatok esetében is. A következő eljárás formájában adjuk meg a sorozatok egyesítésének feltételeit.

Sorozategyesítő eljárás

Egy s (1) sorozatot csak akkor egyesítünk egy másik, s (2) sorozattal, ha megegyeznek azok a sorozatok, amelyeket az s (1) első, illetve az s (2) utolsó eseményének elhagyásával kapunk. Az így kapott jelölt az s (1) sorozat és az s (2) utolsó eseményének konkatenációja. Az s (2) utolsó eseményét közös elemben egyesíthetjük s (1) utolsó eseményével, vagy más eseményekkel is, a következő feltételektől függően:

  1. Ha s (2) utolsó két eseménye ugyanahhoz az elemhez tartozik, akkor s (2) utolsó eseménye s (1) utolsó elemében lesz az egyesített sorozatban.

  1. Ha s (2) utolsó két eseménye különböző elemekhez tartozik, akkor s (2) utolsó eseménye különálló elemként adódik hozzá s (1) -hez az egyesített sorozatban.

A 7.6. ábra gyakori 3-sorozatok páronkénti egyesítésével kapott 4-sorozat jelöltekre mutat példákat. Az első jelöltet, {1}{2}{3}{4} -et úgy kapjuk meg, hogy az {1}{2}{3} és {2}{3}{4} sorozatokat egyesítjük. Ebben az esetben, mivel a 3-as és 4-es események a második sorozat különböző elemeihez tartoznak, az egyesített sorozatban is különböző elemekhez fognak tartozni. Másrészt viszont az {1}{5}{3} és {5}{3,4} sorozatok egyesítésével az {1}{5}{3,4} 4-sorozat jelölt jön létre. Ebben az esetben, mivel a 3-as és 4-es események a második sorozat ugyanazon eleméhez tartoznak, az egyesített sorozat ugyanazon elemében helyezzük el őket. Végül pedig az {1}{2}{3} és {1}{2,5} sorozatokat nem kell egyesítenünk, mivel ha eltávolítjuk az első sorozat első eseményét, akkor nem ugyanazt a részsorozatot kapjuk, mint a második sorozat utolsó elemének elhagyása esetén. Bár az {1}{2,5}{3} alkalmas jelölt, egy másik sorozatpár, az {1}{2,5} és a {2,5}{3} egyesítésével generáljuk. Ez a példa mutatja, hogy a sorozategyesítő eljárás teljes, azaz nem fog kihagyni egyetlen alkalmas jelöltet sem, ugyanakkor elkerüli a sorozat jelöltek duplikált generálását is.

7.6. ábra - Példa a szekvenciális mintázatokat bányászó algoritmus jelöltgenerálási és nyesési lépéseire

Példa a szekvenciális mintázatokat bányászó algoritmus jelöltgenerálási és nyesési lépéseire

A jelöltek nyesése

Egy k -sorozat jelöltet lenyesünk, ha a (k1) -részsorozatai közül legalább egy nem gyakori. Tegyük fel például, hogy {1}{2}{3}{4} egy 4-sorozat jelölt. Meg kell vizsgálnunk, hogy az {1}{2}{4} és {1}{3}{4} sorozatok gyakori 3-sorozatok-e. Mivel egyik sem gyakori, az {1}{2}{3}{4} jelöltet kizárhatjuk. Az Olvasó könnyen igazolhatja, hogy a 7.6. ábrán látható nyesési lépést csak egyetlen 4-sorozat jelölt éli túl, az {1}{2,5}{3} .

A támogatottság kiszámítása

Az algoritmus a támogatottságok kiszámítása során leszámlálja az összes, az adott adatsorozathoz tartozó k -sorozat jelöltet, és növeli ezen jelöltek támogatottságait. Támogatottságaik kiszámítása után az algoritmus azonosíthatja a gyakori k -sorozatokat és elvetheti azokat a jelölteket, amelyek támogatottsága nem éri el a minsup küszöbértéket.

Időbeli megszorítások

Ebben a szakaszban a szekvenciális mintázatok egy olyan megfogalmazását mutatjuk be, melyben a mintázatok eseményeire és elemeire időbeli megszorításokat alkalmazunk. Annak megindoklásához, hogy miért van szükség időbeli megszorításokra, tekintsük a következő olyan kurzusokból álló sorozatot, amelyeket két, az Adatbányászat kurzusra beiratkozott hallgató vett fel:

A hallgató:

 {Statisztika} {Adatbázisrendszerek} {Adatbányászat} 

B hallgató:

 {Adatbázisrendszerek} {Statisztika} {Adatbányászat} 

Az érdekes mintázat itt a  {Statisztika,Adatbázisrendszerek} {Adatbányászat}  , amely azt jelenti, hogy az Adatbányászat kurzusra beiratkozott hallgatóknak előzőleg teljesíteniük kellett a Statisztika és Adatbázisrendszerek kurzusokat. A mintázatot nyilvánvalóan mindkét hallgató támogatja, még ha nem is egyszerre vették fel a Statisztika és Adatbázisrendszerek kurzusokat. Ezzel szemben viszont nem szabad a mintázat támogatójának tekintenünk egy olyan hallgatót, aki tíz éve teljesítette a Statisztika kurzust, mert a kurzusok közötti időrés túl nagy. Mivel a szabályok az előző szakaszban bemutatott megfogalmazása nem tartalmaz időbeli megszorításokat, a szekvenciális mintázatok egy új definíciójára van szükség.

7.7. ábra - Egy szekvenciális mintázat időbeli megszorításai

Egy szekvenciális mintázat időbeli megszorításai

A 7.7. ábrán láthatunk néhányat azok közül az időbeli megszorítások közül, amelyeket egy mintázatra lehet alkalmazni. A következő szakaszokban ezen megszorítások definícióit és a szekvenciális mintázatokat feltáró algoritmusokra gyakorolt hatásukat tárgyaljuk. Megjegyezzük, hogy egy szekvenciális mintázat minden eleméhez hozzárendelünk egy [l,u] időablakot, ahol l egy esemény legkorábbi előfordulása az időablakban, míg u egy esemény legkésőbbi előfordulása az időablakban.

A maxspan megszorítás

A maxspan megszorítás a teljes sorozaton belüli legnagyobb megengedett időbeli eltérést határozza meg az események legkorábbi és legkésőbbi előfordulásai között. Tegyük fel például, hogy a következő adatsorozatok olyan eseményeket tartalmaznak, amelyek egymást követő, (1, 2, 3, ) időpontokban következnek be. Ha feltételezzük, hogy maxspan=3 , akkor egy adott adatsorozat a következő táblázatnak megfelelően fogja támogatni illetve nem támogatni a tartalmazott szekvenciális mintázatokat.

Adatsorozat ( s )

Szekvenciális mintázat ( t )

s támogatja-e t -t?

{1,3}{3,4}{4}{5}{6,7}{8}

{3}{4}

igen

{1,3}{3,4}{4}{5}{6,7}{8}

{3}{6}

igen

{1,3}{3,4}{4}{5}{6,7}{8}

{1,3}{6}

nem

Általánosságban elmondható, hogy minél nagyobb maxspan értéke, annál valószínűbb, hogy mintázatokat tárunk fel egy adatsorozatban. Azonban egy nagyobb maxspan értékkel hamis mintázatokat is feltárhatunk, mivel növeli egymástól független események időbeli kapcsolatba kerülésének esélyét. Emellett a minta tartalmazhat olyan eseményeket is, amelyek már elavultak.

A maxspan megszorítás kihat a szekvenciális mintázatokat feltáró algoritmusok támogatottságot kiszámító lépésére. Mint ahogy az előző példákban is láthattuk, a maxspan megszorítás alkalmazása után egyes adatsorozatok már nem támogatnak bizonyos mintázat jelölteket. Ha egyszerűen alg4:apriori-sequence. algoritmust alkalmazzuk, akkor egyes mintázatok támogatottsági értékeit túlbecsülhetjük. A probléma elkerüléséhez az algoritmust úgy kell módosítani, hogy hagyja figyelmen kívül az olyan eseteket, amelyekben egy adott mintázaton belül az események első és utolsó előfordulása között maxspan -nál nagyobb az eltérés.

A mingap és maxgap megszorítások

Olyan időbeli megszorításokat is megadhatunk, amelyek a sorozatok egymást követő elemei közötti időkülönséget korlátozzák. Ha a maximális időkülönbség ( maxgap ) egy hét, akkor egy elem eseményeinek az előző elem eseményeinek előfordulásától számított egy héten belül kell megtörténniük. Ha a minimális időkülönbség ( mingap ) nulla, akkor egy elem eseményeinek az előző elem eseményeinek bekövetkezte után kell lezajlaniuk. A következő táblázat a maxgap és mingap megszorításoknak megfelelő illetve nem megfelelő mintázatokra mutat példákat, azt feltéve, hogy maxgap=3 és mingap=1 .

Adatsorozat ( s )

Mintázat ( t )

maxgap

mingap

 {1,3} {3,4} {4} {5} {6,7} {8} 

 {3} {6} 

igen

igen

 {1,3} {3,4} {4} {5} {6,7} {8} 

 {6} {8} 

igen

nem

 {1,3} {3,4} {4} {5} {6,7} {8} 

 {1,3} {6} 

nem

igen

 {1,3} {3,4} {4} {5} {6,7} {8} 

 {1} {3} {8} 

nem

nem

Ezek a megszorítások a maxspan -hoz hasonlóan kihatnak a szekvenciális mintázatokat feltáró algoritmusok támogatottságot kiszámító lépésére, mivel a mingap és maxgap megszorítások megléte mellett egyes mintázat jelölteket már nem támogatnak bizonyos adatsorozatok. Ezeket az algoritmusokat módosítanunk kell ahhoz, hogy a mintázatok támogatottságának kiszámításakor biztosítsuk az időbeli megszorítások sértetlenségét. Ha ezt nem tesszük meg, egyes nem gyakori mintázatokat helytelenül gyakori mintázatoknak vehetünk.

A maxgap megszorítás alkalmazásának mellékhatása lehet az apriori-elv megsértése. Ennek érzékeltetésére tekintsük a 7.5. ábrán látható adatokat. A mingap és maxgap megszorítások nélkül a {2}{5} és {2}{3}{5} mintázatok támogatottsága is 60% -kal egyenlő, azonban ha mingap=0 és maxgap=1 , akkor a {2}{5} mintázat támogatottsága 40% -ra csökken, míg {2}{3}{5} támogatottsága 60% marad. Vagyis a sorozat eseményei számának növekedésével nőtt a támogatottság, ami ellentmond az apriori-elvnek. Az apriori-elv ezen megsértése azért fordulhat elő, mert a D objektum nem támogatja a {2}{5} mintázatot, mivel a 2-es és 5-ös események közötti időrés nagyobb, mint maxgap értéke. Ez a probléma kivédhető, ha bevezetjük az összefüggő részsorozat fogalmát.

7.2. Definíció

(Összefüggő részsorozat) Egy s sorozat a w= e 1 e 2 e k sorozat összefüggő (contiguous) részsorozata, ha teljesül a következő feltételek valamelyike:

  1. s -t úgy kapjuk w -ből, hogy e 1 -ből vagy e k -ból törlünk egy eseményt,

  2. s -t úgy kapjuk w -ből, hogy egy legalább két eseményt tartalmazó e i w -ből törlünk egy eseményt,

  3. s összefüggő részsorozata t -nek, t pedig összefüggő részsorozata w -nek.

A következő példákkal szemléltetjük az összefüggő részsorozat fogalmát:

Adatsorozat ( s )

Szekvenciális mintázat ( t )

t az s összefüggő részsorozata-e?

 {1} {2,3} 

 {1} {2} 

igen

 {1,2} {2} {3} 

 {1} {2} 

igen

 {3,4} {1,2} {2,3} {4} 

 {1} {2} 

igen

 {1} {3} {2} 

 {1} {2} 

nem

 {1,2} {1} {3} {2} 

 {1} {2} 

nem

Összefüggő részsorozatok alkalmazásával a következőképpen módosíthatjuk úgy az apriori-elvet, hogy kezelni tudja a maxgap megszorításokat:

7.3. Definíció

(Módosított apriori-elv) Ha egy k -sorozat gyakori, akkor minden összefüggő (k1) -részsorozata is gyakori. A módosított apriori-elv kisebb módosításokkal alkalmazható a szekvenciális mintázatokat feltáró algoritmusra. A jelöltek nyesése során nem kell minden k -sorozatot megvizsgálni, mivel előfordulhat, hogy néhányan közülük nem tesznek eleget a maxgap megszorításnak. Ha például maxgap=1 , akkor nem szükséges ellenőriznünk, hogy az {1}{2,3}{4}{5} jelölt {1}{2,3}{5} részsorozata gyakori-e, mivel a {2,3} és {5} elemek között eltelt idő egy időegységnél több. Ehelyett csak az {1}{2,3}{4}{5} összefüggő részsorozatait kell vizsgálnunk. Ilyen részsorozatok például az {1}{2,3}{4} , {2,3}{4}{5} , {1}{2}{4}{5} és {1}{3}{4}{5} .

Az ablakméret megszorítás

Végül, egy s j elemen belüli eseményeknek nem kell ugyanakkor bekövetkezniük. Definiálhatunk egy ws ablakméret küszöbértéket annak meghatározására, hogy legfeljebb mekkora időeltérést engedünk meg az események legkésőbbi és legkorábbi előfordulásai között egy szekvenciális mintázat bármely elemén belül. Ha az ablakméret 0, az azt jelenti, hogy egy mintázat egy elemének eseményei egyidejűleg kell, hogy előforduljanak.

A következő példában ws=2 értéket használunk annak meghatározására, hogy egy adatsorozat támogatja-e a megadott sorozatot (feltéve, hogy mingap=0 , maxgap=3 és maxspan= ).

Adatsorozat ( s )

Szekvenciális mintázat ( t )

s támogatja-e t -t?

 {1,3} {3,4} {4} {5} {6,7} {8} 

 {3,4} {5} 

igen

 {1,3} {3,4} {4} {5} {6,7} {8} 

 {4,6} {8} 

igen

 {1,3} {3,4} {4} {5} {6,7} {8} 

 {3,4,6} {8} 

nem

 {1,3} {3,4} {4} {5} {6,7} {8} 

 {1,3,4} {6,7,8} 

nem

Bár az előző példában az {1,3,4} {6,7,8} mintázat kielégíti az ablakméret megszorítást, sérti a maxgap megszorítást, mert az események maximális időkülönbsége a két elemben 5 egységnyi. Az ablakméret megszorítás a szekvenciális mintázatokat feltáró algoritmusok támogatottságot kiszámító lépésére is kihat. Ha alg4:apriori-sequence. algoritmust az ablakméret megszorítás nélkül alkalmazzuk, akkor előfordulhat, hogy egyes jelöltek támogatottságait alábecsüljük, és így érdekes mintázatokat veszthetünk el.

Különböző számítási sémák

Számos módszer áll rendelkezésre sorozatok egy adatbázisából származó k -sorozat jelöltek támogatottságának kiszámítására. Ezek szemléltetésére tekintsük a {p}{q} sorozat támogatottságának kiszámítását fig4:seq_counting. ábrán. Tegyük fel, hogy ws=0 , mingap=0 , maxgap=1 és maxspan=2 .

7.8. ábra - Különböző támogatottság kiszámítási módszerek összehasonlítása

Különböző támogatottság kiszámítási módszerek összehasonlítása

  • COBJ: objektumonként egy előfordulás.

Ez a módszer egy adott sorozat legalább egy előfordulását keresi egy objektum idővonalán. Bár a {p}{q} sorozat a 7.8. ábrán többször megjelenik az objektum idővonalán, csak egyszer számoljuk -- p -nek a t=1 időpillanatban, q -nak pedig a t=3 időpillanatban észlelt előfordulásánál.

  • CWIN: csúszó ablakonként egy előfordulás.

Ebben a megközelítésben egy rögzített ( maxspan ) szélességű csúszó ablakot mozgatunk időegységenként végig az objektum idővonalán. A támogatottsági értéket minden olyan alkalommal növeljük, amikor a csúszó ablakban észleljük a sorozatot. A 7.8. ábrán ezzel a módszerrel összesen hatszor figyelhetjük meg a {p}{q} sorozatot.

  • CMINWIN: az előfordulások minimális ablakainak száma.

Egy előfordulás minimális ablaka az a legkisebb ablak, amelyben a sorozat az időbeli megszorítások mellett előfordul. Más szóval, a minimális ablak egy olyan időintervallum, amelyben a sorozat előfordul, de annak egyetlen valódi részintervallumában sem fordul elő. Ez a definíció a CWIN egy szűkítésének tekinthető, mert hatására a CWIN által megszámlált ablakok közül néhány összezsugorodik és megszűnik. Például a {p}{q} sorozatnak négy miniális ablak előfordulása van: (1) a ( p : t=2 , q : t=3 ) pár, (2) a ( p : t=3 , q : t=4 ) pár, (3) a ( p : t=5 , q : t=6 ) pár, és (4) a ( p : t=6 , q : t=7 ) pár. A p esemény előfordulása a t=1 időpillanatban és a q esemény előfordulása a t=3 időpillanatban nem minimális ablak előfordulás, mert tartalmaz egy kisebb ablakot, benne a ( p : t=2 , q : t=3 ) párral, amely már valóban az előfordulás egy minimális ablaka.

  • CDIST_O: egyedi előfordulások az események és az időbélyegek lehetséges átfedésével.

Egy sorozat egy egyedi előfordulását esemény-időbélyeg párok egy olyan halmazaként definiáljuk, amely legalább egy új esemény-időbélyeg párban eltér a korábban számba vett előfordulásoktól. Az összes ilyen egyedi előfordulás megszámlálásával a CDIST_O módszerhez jutunk. Ha a p és q események előfordulási idejét egy (t(p),t(q)) párral jelöljük, akkor ez a módszer a {p}{q} sorozat nyolc egyedi előfordulását adja az (1,3) , (2,3) , (2,4) , (3,4) , (3,5) , (5,6) , (5,7) és (6,7) időpontokban.

  • CDIST: egyedi előfordulások az események és időbélyegek átfedésének tiltásával.

Az előbbi CDIST_O módszer esetén egy sorozat két előfordulásának lehettek átfedő esemény-időbélyeg párjai, lásd például az (1,3) és (2,3) közötti átfedést. A CDIST módszernél viszont nem engedünk meg átfedést. Ha egy esemény-időbélyeg párt tekintünk számlálásra, akkor használtként jelöljük meg, és nem használjuk később újra ugyanannak a sorozatnak a számlálásához. Például öt egyedi, nem átfedő előfordulása van a {p}{q} sorozatnak, amely fig4:seq_counting. ábra diagramján látható. Ezek az előfordulások az (1,3) , (2,4) , (3,5) , (5,6) és (6,7) időpontokban következnek be. Figyeljük meg, hogy ezek az előfordulások a CDIST_O módszernél megfigyelt előfordulások részhalmazát képezik.

Végül az merül még fel a számítási módszerekkel kapcsolatban, hogy meg kell határoznunk egy alapvonalat a támogatottsági mérték kiszámításához. A gyakori elemhalmazok bányászatánál ezt a alapvonalat a tranzakciók száma adja. Szekvenciális mintázatok bányászatánál az alapvonal a számítási módszertől függ. A COBJ módszernél a bemenő adatokban lévő objektumok számát használhatjuk alapvonalként. A CWIN és CMINWIN módszereknél az alapvonalat az objektumokban lehetséges időablakok számának összege adja. Az olyan módszereknél, mint a CDIST vagy a CDIST_O, az alapvonalat az objektumok bemenő adataiban előforduló különböző időbélyegek számának összege adja.