NEUMANN JÁNOS INFORMATIKAI KAR
Baleseti góchelyazonosítás klaszterezéssel a DBSCAN s˝ur˝uségalapú eljárás implementálása
OE-NIK 2015
Hallgató neve: Hallgató törzskönyvi száma:
Sári Zoltán Tamás T/001728/FI12904/N
Kivonat A közúti biztonság megteremtése szempontjából kiemelt feladat a baleseti góchelyek azonosítása. A baleseti góchelyek olyan útszakaszok vagy csomópontok, ahol valamilyen okból kifolyólag az elvárhatónál szignifikánsan magasabb gyakorisággal fordulnak el˝o közúti balesetek. A közlekedésbiztonsági szakért˝ok feladata ezeket a helyeket megtalálni, a fellelhet˝o okokat megszüntetni, vagy kedvez˝otlen hatásukat mérsékelni. A gócpontok keresése során a hazai gyakorlat korábban az útszelvényekre (útszám/km/m) alapuló úgynevezett csúszó ablakos (sliding window) technikára támaszkodott. Az eljárás a szakért˝o által megadott útszakasz-hossznak megfelel˝o méret˝u ablakot tol végig a közútakon. Ha egy ablakban adott id˝oszak alatt több baleset figyelhet˝o meg, mint egy meghatározott küszöbérték, az útszakasz góchelynek min˝osül. A módszer hátránya, hogy csak egy útszakaszt vizsgál, az útkeresztez˝odésekben, ahol a balesetek több útszakaszon rögzítettek, nem alkalmazható. Az eljárás figyelmen kívül hagyja az azonos okra visszavezethet˝o, de különböz˝o útak szelvényszámán rögzített baleseteket. Magyországon a közelmúltban a balesetek adatainak felvétele kiegészült a GPS koordináták rögzítésével, amely új góchelyazonosítási eljárások felhasználását tette lehet˝ové. A GPS koordinátákra alapuló eljárások hatékonyan alkalmazhatók az útkeresztez˝odések, körforgalmak illetve egyéb, nem egyetlen úthoz kapcsolódó góchelyek azonosításában. A GPS alapú azonosítás elterjedésével el˝otérbe kerül a klaszterezési technikák alkalmazása. A dolgozat bemutatja a GPS koordinátákon alapuló releváns góchelyazonosítási módszereket, értékeli azok alkalmazhatóságának el˝onyeit és hátrányait. A következ˝o fejezet részletesen ismerteti az elemzési célhoz legjobban igazodó DBSCAN s˝ur˝uség alapú eljárást. Végül egy alkalmazási példán keresztül kerül illusztrálásra az algoritmus implementációja.
Tartalomjegyzék 1. GPS alapú módszerek áttekintése 1.1. Rácsalapú módszerek . . . . . 1.2. Kernel módszer . . . . . . . . 1.3. K-means eljárás . . . . . . . . 1.4. S˝ur˝uség alapú módszerek . . .
. . . .
. . . .
. . . .
2. DBSCAN algoritmus
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
1 1 2 3 4 6
3. Implementáció
10
Irodalomjegyzék
12
i
1. fejezet GPS alapú módszerek áttekintése Han et. al[1] átfogó áttekintést nyújt a térbeli adatok (spatial data) klaszterezési módszereir˝ol. Az eljárások önmagukban is alkalmazhatók a góchelyek azonosítására, de szolgálhatnak olyan további elemzések (pl.: osztályozás) alapjául, amelyek a klaszterek adataival dolgoznak. Számos sztenderd (particionáló, hierarchikus, s˝ur˝uség vagy rács alapú) klaszterezési algoritmus adaptálható a góchelyazonosításra[3], azonban ezek hatékonyságát, számítás- és tárgigényét illet˝oen jelent˝os eltérések mutatkoznak.
1.1.
Rácsalapú módszerek
A térbeli adatok felhasználására egy lehet˝oséget jelentenek a szakaszolás logikájához hasonló rács alapú eljárások (Sting, WaveCluster, CLIQUE). A rácsmódszer esetében a geográfiai tér meghatározott méret˝u cellákra kerül felosztásra, majd minden cellához hozzárendelésre kerül az általa lefedett terület baleset el˝ofordulásainak száma (1.1. ábra). A góchelyazonosítás a cellák balesetgyakoriság szerinti rangsorolásán alapul.
1.1. ábra. A rács-alapú s˝ur˝uség[2] 1
FEJEZET 1. GPS ALAPÚ MÓDSZEREK ÁTTEKINTÉSE A módszer gyors (O(n)), de a vizsgált terület fix méret˝u cellákra osztása miatt ugyanazokkal, a rácsméret meghatározásából ered˝o hátrányokkal rendelkezik, mint a szakaszoló csúszóablak eljárás. További probléma, hogy téglalap alakú góchelyeket ismer fel.
1.2.
Kernel módszer
A kernel becslési eljárás[5] egy fix sugarú kör által lefedett területet vizsgál. A kör a tér összes lehetséges pozícióját felveszi és az adott középponthoz mérve kiszámítja a balesetgyakoriságot.
1.2. ábra. A kernel becslési eljárás[4] A súlyozott balesetgyakoriságot meghatározása a 1.1 függvénnyel történik, amely az ablak által lefedett baleseteket a középponttól mért távolság alapján veszi figyelembe. n X 1 s − si λτ (s) = k τ2 τ i=1 ahol: s ∈ R ⊂ R2 s1 , s2 , . . . , sn ∈ R τ >0 λτ (s) : R × R → R+ 0 + 2 k : R → R0
helyvektor n megfigyelt esemény helyvektora simítási tényez˝o s intenzitás értéke kernel súlyozási függvény
2
(1.1)
FEJEZET 1. GPS ALAPÚ MÓDSZEREK ÁTTEKINTÉSE A kernel súlyozási függvény általában [0, 1] intervallumban standardizál, ahol 1 a vizsgált pontban elhelyezked˝o súly és 0 a vizsgált környezet határán alkalmazott tényez˝o. A függvény paramétereinek tipikus megválasztása a quartic-kernel(1.2). X 3 1 − d2 2 i λτ (s) = 2 2 πτ τ d ≤τ
(1.2)
i
ahol: di
a távolság s és si között
Kernel függvényként elterjedt a Gauss függvény használata(1.3), amely a DENCLUE (Density-based Clustering) elnevezés˝u s˝ur˝uség alapú klaszterezési eljárás[2]. λτ (s) =
n X
d2 i
e− 2τ 2
(1.3)
i=1
A góchelyek a függvény lokális maximumaiban találhatók. A lokális maximumok irányába történ˝o elmozdulás (folytonos és deriválható függvény esetén) a gradiens módszerrel határozható meg. A kernel módszer az eljárás id˝oigénye a tér bejárása és a nagy számú távolságszámítás miatt magas. Az O(n2 ) számítási id˝o a rácsalapú módszerekkel kombinálva javítható, azonban ekkor számolni kell a hatékonyság romlásával. Az algoritmus els˝o sorban s˝ur˝u közúti hálózatok esetén bizonyul hasznosnak.
1.3.
K-means eljárás
A térbeli adatok elemzése szempontjából felmerül a más alkalmazási területeken széles körben használt k-means eljárás vizsgálata. A k-means és k-medoid particionáló eljárások célja a balesetek k db klaszter valamelyikébe sorolása. A módszerek alapelve a balesethelyszínek és az adott klaszterét reprezentáló helyvektor (centroid, medoid) távolság összegének (1.4) minimalizálása. SSE =
k X X
d(p − mi )2
i=1 p∈Ci
ahol: p ∈ Rn Ci mi ∈ Rn
egy balesetet reprezentáló vektor egy potenciáis góchely (klaszter) egy potenciáis góchely reprezentáns eleme
3
(1.4)
FEJEZET 1. GPS ALAPÚ MÓDSZEREK ÁTTEKINTÉSE Az optimalizálás (klaszter reprezentáns iteratív áthelyezése) megpróbálja az eredményül kapott klasztereket a lehet˝o legtömörebbé és legjobban elkülönül˝ové alakítani. A globális optimum megkeresése azonban NP-teljes feladat, ezért az eljárás implementációi lokális optimumot adnak eredményül. Az algoritmus számítási bonyolultsága O(nkt), ahol n az elemek, k a klaszterek, t pedig az iterációk száma[6]. A módszer nagy adathalmazokra, magas dimenziójú, folytonos attribútumokra is kiterjeszthet˝o. Mindemellett a k-means eljárásnak több alapvet˝o hiányossága mutatkozik. Az eljárás alkalmazási hatékonysága er˝osen függ a paraméterként várt klaszterszám meghatározásától. A k értéket a szakért˝onek kell megadnia, a rosszul megválasztott klaszterszám azonban negatívan befolyásolja az eredményt. Az eljárás érzékeny a zajos adatok kezelésére, néhány széls˝oséges érték jelent˝osen eltéríti a klasztert reprezentáló elemet. További hátrány, hogy a módszer a távolság alapú csoportosításból fakadóan csak gömb (kör) alakú klasztereket ismer fel. A hátrányok miatt a baleseti góchelyazonosítás szempontjából a k-means eljárás alkalmazása nehézkes. A góchelyazonosítás célja a zajos, egyedülálló pontok kizárása. Ezzel ellentétes a k-means m˝uködési elve, hiszen minden balesetet klaszterbe sorol. Az eredmények interpretációját pedig hátráltatja, hogy a zajos adatok miatt a góchelyeket reprezentáló elemek távol eshetnek a góchely értelmezhet˝o középpontjától (messze az úttól). A k-means algoritmus javítását több módszer is célozza (PAM, CLARA, CLARANS)[6], azonban az algoritmus alapproblémáival a góchelyazonosítást célzó felhasználás során ezek esetében is számolni kell.
1.4.
Sur ˝ uség ˝ alapú módszerek
A klaszterezési technikák közül a térbeli adatok elemzéséhez hatékonynak bizonyulnak a s˝ur˝uség alapú (density-based) módszerek[1]. A s˝ur˝uség alapú technikák a klaszter megítélése során a távolság helyett egy összefügg˝o régió s˝ur˝uségét veszik figyelembe. Az eljárások a s˝ur˝u területeket tekintik klaszternek, amelyeket a zajokat jelent˝o (nem kell˝oen s˝ur˝u) régiók választanak el egymástól. Az eljárások alapelve, hogy egy adott klaszterben található elemek s˝ur˝uségének szignifikánsan magasabbnak kell lennie, mint a klaszteren kívüli elemeké. Az algoritmus a klasztert fokozatosan növeli, amíg elemei kell˝oen s˝ur˝u területet alkotnak. Az eljárás el˝onye, hogy bármilyen alakú (akár nem konvex) gócot felismer és megkülönbözteti a zajt, azaz a góchelyhez nem tartozó baleseteket. Alapvet˝o s˝ur˝uség alapú eljárás a DBSCAN (Density-based Spatial Clustering of Applications with Noise) módszer. A góchelyek azonosítására való alkalmasság jól érzékelhet˝o a k-means és a DBSCAN összehasonlításával (1.1.táblázat).
4
FEJEZET 1. GPS ALAPÚ MÓDSZEREK ÁTTEKINTÉSE
jellemz˝o
k-means
DBSCAN
alapelv teljeskör˝uség klaszter alak
prototípus alapú minden elemet klaszterhez rendel gömb alakú klasztereket ismer fel
s˝ur˝uség alapú zajokat nem klaszterez különböz˝o alakú klaszterek felismerése érzékenység a zajok jelent˝osen torzítják a klaszter nem érzékeny a kiugró értékekre zajra reprezentánsokat determiniszkezdeti középpontok véletlenszer˝u minden futtatásnál ugyanazokat a tikusság inicializálása miatt nem ugyanazo- klasztereket állítja el˝o (ugyanazon kat a klasztereket állítja el˝o paraméterek mellett) klaszterek paraméterként kell megadni automatikusan határozza meg szám id˝obonyolultság O(n) legrosszabb esetben O(n2 ), térbeli indexek használatával O(n log n) tárbonyolultság O(n) O(n)
1.1. táblázat. A k-means és a DBSCAN összehasonlítása [2]
5
2. fejezet DBSCAN algoritmus Az algoritmus a s˝ur˝uség meghatározásához 2 paramétert használ: – sugár jelleg˝u küszöb – M inP ts elemszám küszöb Az algoritmus m˝uködésének bemutatásához szükséges néhány fogalom[6]: – q ∈ D bels˝o elem: q elem -környezete legalább M inP ts darab elemet tartalmaz – p ∈ D közvetlenül s˝ur˝un elérhet˝o q ∈ D-ból: ha q bels˝o elem és p a q -sugarú környezetében van – p s˝ur˝un elérhet˝o q-ból -ra és M inP ts-re vonatkozóan: ha létezik p1 , . . . , pn sorozat, hogy p1 = q, pn = p és pi+1 közvetlenül s˝ur˝un elérhet˝o pi -b˝ol minden i-re 1 ≤ i < n, pi ∈ D – p s˝ur˝un összekötött q-val -ra és M inP ts-re vonatkozóan: ha létezik olyan r ∈ D, amelyb˝ol p és q is s˝ur˝un elérhet˝o A s˝ur˝un elérhet˝oség a közvetlenül s˝ur˝un elérhet˝oség tranzitív lezártja. A reláció nem szimmetrikus, csak a bels˝o elemekre lehet a s˝ur˝un elérhet˝oség kölcsönös, a s˝ur˝un összekötöttség viszont szimmetrikus reláció. A klaszter a s˝ur˝un összekötött elemek olyan halmaza, amely maximális a s˝ur˝un elérhet˝oségre vonatkozóan. Minden klaszteren kívüli elem zajnak tekinthet˝o.
6
FEJEZET 2. DBSCAN ALGORITMUS
2.1. ábra. Két klaszter azonosítása a DBSCAN eljárással[1] A DBSCAN úgy keresi meg a klasztereket, hogy megvizsgálja az adatbázis minden pontjának sugarú környezetét. Ha egy p pont bels˝o elem, akkor egy új klasztert hoz létre p bels˝o ponttal. Az algoritmus ezután iteratív módon összegy˝ujti a bels˝o pontokból közvetlenül s˝ur˝un elérhet˝o elemeket, ami a s˝ur˝un elérhet˝o klaszter összevonásával jár. Az iteráció akkor ér véget, ha már nem tud egyik klaszterhez sem új elemet hozzáadni. Az algoritmus számítási bonyolultsága alapesetben O(n2 ), azonban térbeli index (spatial index) használatával a bonyolultság O(n log n), ahol n az adatelemek száma. A magyarországi baleseti adatok GPS koordinátáit felhasználva a DBSCAN algoritmus felhasználásával gyors eljárást implementált Szénási és Csiba[7]. A szerz˝ok két baleseti helyszín közötti távolságot a koordináták Euklideszi távolságával határozták meg. A klaszters˝ur˝uségként a klaszterbe es˝o balesetszámok kimenetel alapján súlyozott összege és a klaszterterület arányát tekintették. A klaszterterületet annak a legkisebb konvex poligonnak a területével definiálták, amely körülhatárolja a klaszterbe tartozó baleseteket. A DBSCAN algoritmus futtatásával kapott góchelyek a s˝ur˝uség alapján kerültek rangsorolásra. A magyaroszági baleseti adatbázis méretére tekintettel az eljárás elfogadható futási id˝ot igényelt, azonban lényegesen nagyobb méret˝u adathalmaz feldolgozása esetén az algoritmus térbeli indexek alkalmazását igényli. A DBSCAN a paraméterekre érzékeny eljárás, alapesetben a megfelel˝o paraméterek megválasztása a szakért˝o felel˝ossége. A probléma kezelésére segítségül hívható az OPTICS (Ordering Points To Identify the Clustering Structure) algoritmus[6]. A módszer a DBSCAN eljárás általánosítása. Az algoritmus nem egy konkrét klaszterezést ad meg, hanem a klaszterezések egy rendezett sorozatát. Egyenérték˝u a DBSCAN eljárás sok paraméterbeállítással történ˝o elvégzésével. Az OPTICS logikája, hogy a M inP ts konstans megválasztása esetén a kisebb értékek megválasztása (nagyobb s˝ur˝uség) esetén kapott klaszterek részhalmazát képezik a kisebb s˝ur˝uség esetén kapott klasztereknek. A algoritmus annak érdekében, hogy a különböz˝o s˝ur˝uség˝u klasztereket egyidej˝uleg létrehozza, az elemeket egy speciális sorrendben dolgozza 7
FEJEZET 2. DBSCAN ALGORITMUS
Algorithm 1 A DBSCAN módszer algoritmusa Require: B[] a balesetek adatai Require: távolságküszöb Require: MinPts gócmin˝osítési küszöb Ensure: G[] góchelyek Ensure: N[], N’[] szomszédos pontok Ensure: b, b’ baleset 1: for all b ∈ B[] do 2: if NemLátogatott(b) then 3: LátogatottnakJelöl(b) 4: N [] = SzomszédosPontok(b, ) 5: if SzomszédosPontokSzáma(N []) < M inP ts then 6: ZajosElemnekJelöl(b) 7: else 8: Következ˝oGóchelyInicializálás(G[]) 9: GóchelyhezHozzáad(G[], b) 10: for all b0 ∈ N [] do 11: if NemLátogatott(b0 ) then 12: LátogatottnakJelöl(b0 ) 13: N 0 [] = SzomszédosPontok(b0 , ) 14: if SzomszédosPontokSzáma(N 0 []) ≥ M inP ts then 15: N [] = N [] ∪N 0 [] 16: end if 17: if NemGócPont(b0 ) then 18: GóchelyhezHozzáad(G[], b0 ) 19: end if 20: end if 21: end for 22: end if 23: end if 24: end for 25: return G[]
8
FEJEZET 2. DBSCAN ALGORITMUS fel. A sorrend kialakítása az paraméter folyamatos növelését jelenti, ezzel biztosítható, hogy a s˝ur˝ubb klaszterek jönnek el˝obb létre. Az alkalmazáshoz minden elemre el kell tárolni a bels˝o (2.1) és az elérhet˝o távolságot(2.2). ( dcore ,M inP ts (p) ( dreachability ,M inP ts (p,q)
ahol: N (p) qM inP ts
=
=
definiálatlan d(p, qM inP ts )
definiálatlan max(dcore ,M inP ts (p), d(p, q))
ha|N (p)| < M inP ts egyébként
(2.1)
ha|N (p)| < M inP ts egyébként
(2.2)
p ∈ D elem -sugarú környezetében található elemek halmaza a M inP ts-dik legközelebbi elem
A bels˝o távolság az a legkisebb 0 érték, amely mellett p bels˝o elem lesz (ha nem bels˝o elem, akkor nincs definiálva). A q elem elérhet˝oségi távolsága a p elemre vonatkozóan a p elem bels˝o távolságának és a p és q közötti euklidészi távolság maximuma (ha p nem bels˝o elem, akkor nincs definiálva). Az algoritmus az elemek egy sorrendjét készíti el minden elem bels˝o és elérhet˝oségi távolságának tárolásával. Az információk elegend˝oek az összes olyan klaszter el˝oállításához, ahol 0 ≤ . Az OPTICS felépítéség tekintve ekvivalens a DBSCAN algoritmussal, így bonyolultsága is megegyezik, térbeli indexek használata esetén O(n log n) A klaszterezési algoritmusok felhasználására támaszkodó góchelyazonosítás eredménye a baleseti adatbázis információinak tömörítése. A nem gócgyanús helyszínekhez kapcsolható balesetek eltávolításával lehet˝oség nyílik az adatbázis redukálására. Az elemzési szempontból releváns gócgyanús baleseti adatok klaszterekbe szervezése támogatja a korszer˝u góchelyelemzési technikák alkalmazását.
9
3. fejezet Implementáció Az algoritmus .NET 4.5 környezetben, C# nyelven került implementálásra. A program kizárólag a .NET standard könyvtáraira támaszkodik. A megvalósítás moduláris felépítését a 3.1. táblázat mutatja be. modul
funkcionalitás
elemek
felhasználói felület (GUI) import (Import)
grafikus felület a felhasználói interakcióhoz adatállomány beolvasása
adatmodell (DataModel) algoritmus (DBSCAN)
a térbeli adatok modellje
windows u˝ rlap és vezérl˝o elemek .csv fájlolvasó, adat transzformátor GPS koordináta, térbeli adatmodell algoritmus, adatmodell, paraméterek, távolságfüggvény térképmodell, grafikus eszközök
megjelenítés (Presentation)
a DBSCAN eljárás és a szorosan kapcsolódó komponensek elemzési adatok és eredmények térképen szemléltetése
3.1. táblázat. A fejlesztett program moduláris felépítése és funkcionalitása Az algoritmus validálása az R statisztikai szoftverkörnyezet dbscan[8] és fpc[9] csomagjainak megfelel˝o eljrásaira támaszkodott. A fejlesztett program és az R csomagok azonos eredményt szolgáltattak. A 3.1. ábra az eljárás egy futtatásának eredményét szemlélteti ( = 50 méter, MinPts = 3).
10
FEJEZET 3. IMPLEMENTÁCIÓ
3.1. ábra. Az algoritmus eredménye bels˝o Óbudán A mintaállomány és a program forráskódja a dolgozat mellékletét képezi. Az algoritmus továbbfejlesztésének els˝odleges irányait a térbeli indexek használata (kdtree, R* tree) és az algoritmus párhuzamosítása jelentik. Mindkét fejlesztés a szomszédos elemek felkutatása terén eredményez hatékonyságjavulást.
11
Irodalomjegyzék [1] J. Han, M Kamber, A.K.H Tung: Spatial Clustering Methods in Data Mining: A Survey, In: H.J. Miller and J. Han (Eds.) Geographic Data Mining and knowledge discovery (pp. 33-50) [2] P.N. Tan, M. Steinbach, V. Kumar: Adatbányászat alapvetés, Panem, 2012 [3] S. Skekhar, M. R. Evans, J. M. Kang, P. Mohan: Identifying Patterns in Spatial Information: a Survey of Methods, John Wiley and Sons, Inc. vol 1., 2011 [4] A. Gatrell, T. Bailey, P. Diggle, B. Rowlingson: Spatial Point Pattern Analysis and its Application in Geographical Epidemiology, Transactions of the Institute of British Geographers, 21:256-274, 1996. [5] D. Steil, A. Parrish: HIT: A GIS-Based Hotspot Identification Taxonomy, IJCA, Vol. 16, No. 2, 2009 [6] J. Han, M. Kamber: Adatbányászat. Koncepciók és technikák, Panem, 2004 [7] S. Szenasi,P. Csiba: Clustering Algorithm in Order to Find Accident Black Spots Identified by GPS Cooridnates, 14th Geoconference in Informatics, Geoinformatics and Remote Sensing, 2014 [8] https://cran.r-project.org/web/packages/dbscan/ [9] https://cran.r-project.org/web/packages/fpc/
12
