Adatfolyam bányászati algoritmus

Az elméleti számítógép-tudomány , a adatfolyamot bányászati algoritmus vagy algoritmus streaming a streaming algoritmus angol, egy algoritmus figyelembe véve egy folyamatos terméket. Ezeknek az algoritmusoknak általában kevés memória áll rendelkezésükre (jóval kevesebb, mint a bemeneti kötet mérete), és kevés az idő, hogy az egyes elemeket kiosztják.

Ezek a korlátok azt jelentheti, hogy egy ilyen algoritmus egy közelítő válasz alapján a használata egy összefoglaló ( „ összefoglalói ” ) az adatfolyam a memóriában.

Modell

Leírás

Különbségek az online algoritmusoktól

A modell megoszt bizonyos szempontokat az online algoritmusokkal , de a két modell különbözik egymástól. Streaming algoritmusokban a válasz késleltetett módon adható meg, és a nehézséget a kevés rendelkezésre álló hely jelenti, akár több adatot is tovább lehet adni. Éppen ellenkezőleg, az online algoritmusok esetében a döntéseket az információ beérkezésekor kell meghozni, és az erőforrások a térben és a számítási időben nem korlátozottak.

Példák a problémákra

Frekvencia keresés

Az adatfolyamban gyakori elemek megkeresésére kétféle algoritmus létezik: a számlálásokon alapuló algoritmusok és az összefoglalókon alapuló algoritmusok ( „ Sketch ” ).

Számol

A ragadós mintavétel és a veszteségszámolás két fontos algoritmus ezen a területen, már csak azért is, mert referenciaértékek. Mindkettő hamis-pozitív orientált algoritmus ( " hamis-pozitív " ), vagyis megengedik maguknak, hogy ennek eredményeként gyakori elemeket vagy tételeket mutassanak be, amikor még nem, de egyetlen hamis negatív sem feledkezik meg.

Veszteséges számlálás

A Lossy-Counting az egyik első algoritmus, amely a zászlóablakok modelljét ( " landmark windows model " ) használva kutatja az adatfolyamokat . Ez egy olyan paraméteres algoritmus, amely két paramétert fogad el a felhasználótól: és hol van a hibaarány és az elemző által kívánt támogatási küszöb. Ha N a most érkezett elemkészletek száma, akkor az algoritmus 1 / hosszú ablakokat használ . Az algoritmus kialakítása biztosítja, hogy minden olyan tétel (elemkészlet), amelynek tényleges gyakorisága nagyobb, mint sN (az i támogatása az N számszerűség halmazában egyenlő ), szerepeljen a kimeneti listában, és egyetlen olyan elemkészlet sem, amelynek tényleges frekvenciája kisebb, mint a kimeneti listában vannak, és a becsült frekvenciákat csak legfeljebb egy tényező tolja el a tényleges frekvenciáktól . $\ epsilon \ in [0,1]$ $s \ in [0,1] ~ {\ text {}} ~ ~ epsilon \ ll s-vel$ $\ epsilon$ $\ epsilon$ $ha}$ ${\ frac {f_ {i}} {N}}$ $sN- \ epsilon N$ $\ epsilon N$

Ragadós mintavétel

A Sticky Sampling rögzített hosszúságú ablakokat és r mintavételi gyakoriságot használ, azaz egyenlő valószínűségű elemet választ . Három paramétert - a hibaarányt - használ a támogatási küszöb, és az elemző által kívánt kudarc valószínűsége. Ha az t első érkezést 1-gyel egyenlő r-rel, a következő 2t-t 2-vel egyenlő arányban választjuk meg. Ha az elemző az s küszöb feletti elemek (tételkészletek) kilépését kéri, l Az algoritmus kimeneti az elemek, beleértve a frekvenciát is . $\ frac {1} {r}$ $\ epsilon$ $\delta$ $t = {\ frac {1} {\ epsilon}} \ log (\ epsilon ^ {{- 1}} \ delta ^ {{{- 1}})$ $f \ geq (s- \ epsilon) N$

DSM-FI

A Data Stream Mining for Frequent Itemset egy algoritmus, amelyet Hua-Fu Li, Suh-Yin Lee és Man-Kwan Shan hozott létre a gyakori elemkészletek feltárására egy adatfolyamban.

Döntési fák

VFDT

A " Nagyon gyors döntési fák tanulója " csökkenti a nagy növekményes adathalmazok tanulási idejét az adatfolyam részmintavételével. A VFDT egy Hoeffding fát használ.

CVFDT

A „ koncepcióhoz igazodó, nagyon gyors döntési fák tanulója ” az előző algoritmus továbbfejlesztése, mivel figyelembe veszi a fogalmi sodródást ( „ Concept drift ” ).

Hoeffding fa

A Hoeffding-fa inkrementális és örökös döntési fa algoritmus, amely képes masszív adatfolyamból tanulni, azzal a feltevéssel, hogy a minták eloszlása nem változik az idő függvényében - nincs elmozdulás fogalmi ( „ Concept drift ” ). Ez az algoritmus növekményesen épít egy fát, elegendő információt gyűjtve a levelekben ahhoz, hogy egy adott pillanatban kiválaszthassa, melyik a legjobb tulajdonság a levelek csomópontokká alakításához. A levél felosztását - amely a levelet csomóponttá alakítja át - két allevélre a Hoeffding-egyenlőtlenség ( " Hoeffding-kötött " ) felhasználásával végezzük , amely statisztikai mérőszám lehetővé teszi, hogy hány minta alapján becsüljön meg egy becslő közel a valószínűséggel becsült változó valódi értékéhez , ha eleve megadjuk magunkat. $1- \ delta$ $\delta$

Szegmentálás

NYÍR

A BIRCH ( „ kiegyensúlyozott iteratív redukálás és klaszterezés hierarchiák segítségével ” ) egy felügyelet nélküli adatbányászati algoritmus, amelyet különösen nagy adatmennyiségek hierarchikus szegmentálásának előállítására használnak. Ez az algoritmus olyan szegmensjellemző vektorokat ( „ Clustering Feature ” ) használ , amelyek mindegyike egy-egy vektor, és összefoglalja a mikroszegmenseket ( „ mikroklaszter ” ), hogy kiegyensúlyozott fát hozzon létre ezekből a mikroszegmensekből. A CF vektorban található információ elegendő az átlag, a variancia, a centridák és bizonyos távolságok becslésének kiszámításához. A CF-fának három paramétere van: B az elágazási tényező, T a küszöb, L az utolsó csomópontok alatti levelek maximális száma. A lapok prec és követő mutatókkal vannak összekötve egymással. Az algoritmus három fázisban zajlik: az első az adatok kiolvasásából és a CF fa felépítéséből áll a rendelkezésre álló memória határain belül. A második fázist az aberrációk ( " outlier " ) kiküszöbölésére, a szegmensek algoritmusát a harmadik fázisban a levelek szegmentálására használják. $(\ mathrm {N}, \ sum _ {{k = 1}} ^ {\ mathrm {N}} \ mathrm {X} _ {i} ^ {2}, \ sum _ {{k = 1}} ^ {\ mathrm {N}} \ mathrm {X} _ {i})$ $\ Chi_i$

Alsó kapcsok

Alacsonyabb határokat lehet kiszámítani a streaming algoritmusokhoz , különösen a kommunikáció komplexitásának eredményeinek felhasználásával .

Megjegyzések és hivatkozások

(fr) Ez a cikk részben vagy egészben venni a Wikipedia cikket angolul című „ Streaming algoritmus ” ( lásd a szerzők listáját ) .

ENST , MIDAS projekt
Claire Mathieu , „ támogatása során»algoritmusok adatáramlás«a College de France, január 16, 2018 ” , a College de France .
Nishad Manerikar, Themis Palpanas, Gyakori tételek az adatfolyamokban: A korszerű technika kísérleti értékelése
Gurmeet Singh Manku, Rajeev Motwani , Hozzávetőleges frekvencia számít felett adatfolyamok
Hervé Bronnimann, „ Mintavételi és geometriai problémák online ” ( Archívum • Wikiwix • Archive.is • Google • Mit kell tenni? )
Hua-Fu Li, Suh-Yin Lee és Man-Kwan, Shan „ Hatékony algoritmus a gyakori elemek bányászatához az adatfolyamok teljes története során ” ( Archívum • Wikiwix • Archive.is • Google • Mit kell tenni? )
Pedro Domingos, Geoff Hulten, Nagysebességű adatfolyamok bányászata
Pedro Domingos, Laurie Spencer, Geoff Hulten, Mining Time-Changing Data Streams
Pedro Domingos, Geoff Hulten, Nagysebességű adatfolyamok bányászata
Albert Bifet, Geoff Holmes, Bernhard Pfahringer, Richard Kirkby, Ricard Gavaldà, Új együttes módszerek az adatfolyamok fejlődéséhez , 4. oldal
Geoff Holmes, Bernhard Pfahringer, Richard Kirkby, Nyakkendőtörés a Hoeffding-fákban , 2. oldal
Tian Zhang, Raghu Ramakrishnan, Miron Livny, BIRCH: Hatékony adatcsoportosítási módszer nagyon nagy adatbázisokhoz
Chun Wei, Adatfolyamok csoportosítása

Lásd is

Bibliográfia

R. Agrawal, SP Ghosh, T. Imielinski, BR Iyer és AN Swami. Intervallum-osztályozó adatbázis-bányászati alkalmazásokhoz. In VLDB '92, 560-573. Oldal, 1992.
R. Agrawal, T. Imielinski és A. Swami. Adatbázis-bányászat: Teljesítmény-perspektíva. IEEE Trans. a Knowl-en. és Data Eng., 5 (6): 914-925, 1993.
A. Asuncion és D. Newman. UCI gépi tanulástár, 2007

Külső linkek

(en) BIRCH az angol Wiki oldalon

Kapcsolódó cikkek

Bloom szűrő , egy elem jelenlétének tesztelésére bizonyos algoritmusokban
Flajolet - Martin algoritmus

Adatfolyam bányászati ​​algoritmus