Sikerült 2.5 nagyságrenddel gyorsítanom az anomália detektáló megoldásomat különböző heurisztikus trükkökkel. Egy sztochasztikus működést be kellett tennem, de nem a határérték elemzésbe.
Rosszabb a megoldás értelemszerűen mint a lassú verzió, viszont még így is jobbnak tűnik, mint az Izolációs erdő teszteléseim alapján. Lásd például:
d = (1..1000).map{ (1..100).map{ rand }}; d[0][0] = 999;
anomaly d
=> []
anomaly2 d
=> [[0, 27.556902928189164]]
anomaly2 d, flag_fast:true
=> [[0, 28.01593503143584]]
Az IF algo nem találja meg az egyértelmű devianciát, mely statisztikailag szinte végtelen erősen szignifikáns. Saját eljárásom megtalálja mindkét esetben.
Gyors megoldásom hátrányai:
- Míg a lassú verzió tökéletes a határérték megállapításának szempontjából is, a gyors verzióban torzul ez a határérték, így IF-hez hasonlóan nem megállapítható, hogy hol van a pontos elválasztó vonala az anomáliáknak és a normál értékeknek.
- A lassú verzióm tökéletesen megtalál úgymond belső struktúrában lévő anomáliákat is (pl egy nagy dimenziójú gömb vagy tórusz felhő belsejében), addig a gyors verzió nem tudja.
Mégis, ha nagy adat elemzéséről van szó, arra megfelelő, hogy gyors iránymutatást adjon arra nézve, hogy van-e várhatóan anomália az adatban.
- sinexton blogja
- A hozzászóláshoz be kell jelentkezni
- 206 megtekintés
Hozzászólások
Ha nagyon nagy adatrol lenne szo , akkor valoszinuleg egy terbeli hash-t csinalnek (hisztogram, vagy fix pontos kozelites), hogy gyorsitsam. Kell amugy a gyorsitas ? (mondjuk en sokat toltok optimalizalassal, szoval "thumbs up")
Hulye kerdes, de ha 10x, 100x annyi adat van, akkor is megtalalja ugyanezt a 28 szigmas pontot, vagy egy 4-5 szigmara levot?
- A hozzászóláshoz be kell jelentkezni
Köszi, ezt végig gondolom amit írtál és majd válaszolok.
Ha jól gondolom, akkor a hisztogram is ugyanaz amit csinálok, mert az extrém ritka távolságokat veszem. Tehát ott is egy eloszlás (távolságok eloszlása) extrémáit kerestetem meg. Hash alatt mit értesz ebben a kontextusban?
A gyorsítás nagyon kell. 100x annyi adatnál a lassú 1 hétig is futhat vagy akár hónapokig, a gyors meg óra akár. Ha négyzetesen számoljuk az időt durván, akkor ami 1 óra alatt fut, ott 100x annyi adatnál 100^2 szeres lesz az idő, vagyis 10 ezer óra, ami kicsit több mint 1 év.
Igen megtalálja a pontokat. De csak a "külső" anomáliákat. Belső struktúrában lévőket nem. Például egy gömb belsejében lévőt nem. A lassú viszont igen.
Azért foglalkoztat ez a terület is, mert az IF hiába gyors ha rossz és nem talál meg kulcs pontokat.
- A hozzászóláshoz be kell jelentkezni
Kiegészítés: A gyors megoldás további hiánya - ahogy feljebb írtam - hogy többet gondolhat anomáliának. Tehát kisebb szigma értékeket is hoz. Mert torzul a tökéletes matematikai limit a gyorsító heurisztika miatt. Sajnos.
De mivel a top-tól kezdjük a legextrémebbel a vizsgálatot, így iránymutatásnak jó.
- A hozzászóláshoz be kell jelentkezni
Ha jol ertem, akkor az egzakt megoldasban vegig mesz az osszes adatparon, es kiszamolod a tavolsagukat.
Van egy "spatial hash" nevu elv, sok fele keppen meg lehet valositani, de a te esetedben egyfajta "sparse histogram" kell. Adott x adatpontnal, ha vegig kell menni az osszes masik y-on, akkor sokszor eleg csak a floor(y) kozelitett erteke, vagy hasonlo binezes, es ha atlagot is kell szamolni minden y-ra, akkor az adott bin tartalma n*floor(y)-t veszed figyelembe. Fuggvenyeknel, mint pl. a Sum (x-y)^2 -nel, eleg a Sum n*(x-floor(y))^2 -et figyelembe venni. Azoknal a y-oknal, amire erzekeny a szamolas, mondjuk aminel x-y kicsi, lehet az egzakt y-nal szamolni, de olyan bineknel, aminel n nagy, eleg csak az atlagos n * floor(y)-t hasznalni.
A spatial hash arra kell, hogy ha nagyon ritkan vannak a pontjaid, akkor azonositds, hogy mik vannak kozel.
- A hozzászóláshoz be kell jelentkezni
Köszi. Ez tetszik heurisztikus szempontból. Kicsit mást csinálok, mindjárt leírom.
Viszont az egzakt megoldást nagyon szeretem, mert maximálisan elérhető "minőséget" ad a válaszban. Nem marad ki semmi, nem torzul semmilyen statisztikai és matematikai "arány". És a limit kiértékeléséhez szükséges infó is teljes. Tehát tökéletes a megoldás.
Sajnos gyorsítani kell. Én több dolognál egy olyan heurisztikát dolgoztam ki, melynél összekeverem a pontokat, és egyszer megyek végig az egymás mellé esőkön. Másképp fogalmazva, véletlen mintavételezek egyenként és a szomszédosak távolságát vizsgálom.
Ez egy olyan statisztikát segít előállítani, mely "erősen" fog hasonlítani arra, amit akkor kapnánk, ha végig megyünk az összes négyzetes kombináción. Ez nem más, mint a távolságok átlaga és szórása. Természetesen adott mértékben torzul ez is, de van egy alap "gravitációja". És ha sikerül tovább vinni a megoldást úgy, hogy elégséges legyen az ezzel járó bizonytalanság (még mindig egy kívánt szintű megbízhatóságon belül maradva), akkor egy "elégséges" minőségű heurisztikát kaphatunk.
Az általad ajánlott bin-ezésnél - ha jól gondolom - fordított az igény. Nekem nem a nagyon közelieket kell azonosítanom, hanem a nagyon távoliakat. De ráadául nem csak a globális tömegtől távoliakat, hanem a lokális tömegtől is. Tehát belső struktúrákban lévő leszakadókat is ki kell tudnia emelnie a megoldásnak.
Jól gondolom, hogy a belső leszakadás detektálására túl torz a spatial hash?
Belső leszakadás például egy tórusz felső belsejében, arányaiban túl távoli pont, mely arányosan sokkal távolabb van a körülötte lévőktől, mint a körülötte lévők egymástól.
- A hozzászóláshoz be kell jelentkezni
Magat a hash-t lehet tobb fele keppen hasznalni. Pl. arra is jo, hogy ha nagy adatbol ki akarod valasztani, hogy mik a te pontodhoz legkozelebbiek, akkor nem a pontokon megsz vegig eloszor, hanem a hash-en. Kidobod a kelloen tavoliakat, es vegul azokat a pontokat vizsgalod, amik a kozeli hash-ekben vannak. Vegeredmenyben igy nem kell vegigmenni az osszes ponton, csak a hasheken es a kozeli pontokon. A trukk presze mindig az, hogy hogyan generalj olyan felbontast, aminel a hash-ek szama kevesebb mint a pontok szama (vagyis a legtobb kijelolt terfogatban tobb mint egy pont van).
Igy akar belso leszakadasra is hasznos lehet, bar nem tudom pontosan mit szamolsz. Ha egy vizsgalt pontnal hash-sel ki tudod szorni a nagyon tavoli pontokat, es csak a kozelieken mesz vegig, az talan gyorsit. Ugy remlik a spatial hash-t jatekokban, szimulaciokban utkozes-detektalasra is szoktak hasznalni. Kidobjak elso korben, amivel biztos nincs utkozes, es megdoljak a kenyszer-egyenleteket azokra a targyakra, amiknel esetleg van (mert ugye delta-t lepeskozonkent sok minden tortenhet)
- A hozzászóláshoz be kell jelentkezni
Mindenképpen jó ötlet.
Most azon gondolkodok, hogy a hash felbontást hogyan határoznám meg. Például dimenziónkénti relatív sűrűséget számolok és ahhoz képest. Tehát a sűrűbb halmazhoz határozom meg. Például a sűrűbb halmaz középpontjától számított 1 szigma távolságot osztok fel egy értékkel és ez lesz a hash felbontása. Ezen érték legyen delta. Így ennek az értékét keresem most.
A sűrűség középpontja pedig lehet a koordináták középértéke kétszer számolva. Elsőre kiszámolom így, majd eltávolítom a 2 szigmánál távolabbra lévőket. Majd újra számolom ezt a középértéket. Így még inkább a tömeg középpontja felé tolódik. Majd ezen halmazra újra számolok szórást. És az 1 szóráson belül eső értékeket tekintem a vizsgált halmaz elemeinek.
Nem tudjuk, hogy mi a távolságok pontos eloszlása, melyből jobban tudnánk számolni deltát. Eleve ezt az eloszlást keressük.
Lehetne delta értéke az ezen halmazban lévő pontok növekvő sorrendjén vett szomszédos távolságok mediánja vagy átlaga. Gondolkodok rajt hogy melyik hordoz jobb tulajdonságot a probléma szempontjából. Ha egy magasabb percentilis értéket választunk (vagy quadratic mean vagy hasonló, az eloszlás felső részéből választott értéket), akkor durvább felbontást kapunk gyorsabb futással, de megbízhatatlanabb eredménnyel.
A középérték biztosítja azt, hogy az átlagostól sokkal nagyobbak külön hash cellára essenek. És tudjuk, hogy az outlier-ek mindenképpen az átlagostól eltérőek lesznek. Így ez elsőre jónak tűnik.
Első nekifutásra kevés gondolkodással ez egy nem rossz modell szerintem, mert így minden paraméter adaptív. Persze sokat kell még dolgozni rajt, bejárva a teljes megoldás teret, hogy nincs-e jobb paraméter választás adaptív szempontból.
Mennyivel gyorsulhat a számítás?
N pontnál a lépések száma teljes bejárással n^2. Ha a hash felbontása k-val osztja minden dimenzióban a vizsgálandó elemek számát, akkor (n/k)^2 ami n^2/k^2, tehát négyzetesen visszaosztódik. De volt benne még egy sorba rendezés, még szorzódik n log(n)-el mint worst case. Tehát n log(n) / k^2 -el szorzódik ha mindent jól gondolok. Mivel n száma adott, így csak k nő, és mivel n log n közel lineáris, k pedig négyzetesen nő, így vonzó lehet az eredmény sok esetben talán.
- A hozzászóláshoz be kell jelentkezni
Kiegészítés: amit viszont a fenti nem old meg, az az, hogy az anomáliákat a távolságok egy olyan határértékéből számolom az egzakt megoldásnál, mely az összes távolság kombináció eloszlásából ered.
A spatial hash-nél így a közeli pontokhoz való távolságok lesznek ismertek. Ennek még vizsgálni kell az implikációit.
- A hozzászóláshoz be kell jelentkezni