a homorú hajótest
klaszterhatár létrehozása K-legközelebbi szomszédok megközelítésével
pár hónappal ezelőtt itt írtam a Medium-on egy cikket az Egyesült Királyság közlekedési baleseteinek forró pontjainak feltérképezéséről. Leginkább a dbscan klaszterezési algoritmus földrajzi adatokon való használatának szemléltetése miatt aggódtam. A cikkben az Egyesült Királyság Kormánya által közzétett földrajzi információkat használtam a bejelentett közlekedési balesetekről. Célom az volt, hogy sűrűségalapú klaszterezési folyamatot hajtsak végre, hogy megtaláljam azokat a területeket, ahol a közlekedési baleseteket leggyakrabban jelentik. A végeredmény egy olyan geo-kerítés létrehozása volt, amely ezeket a baleseti forró pontokat képviseli.
egy adott klaszter összes pontjának összegyűjtésével képet kaphat arról, hogy a klaszter hogyan nézne ki a térképen, de hiányzik egy fontos információ: a klaszter külső alakja. Ebben az esetben egy zárt sokszögről beszélünk, amelyet a térképen földrajzi kerítésként lehet ábrázolni. A geo-kerítés bármely pontja feltételezhető, hogy a klaszterhez tartozik, ami ezt a formát érdekes információvá teszi: diszkriminátor funkcióként használhatja. Minden újonnan mintavételezett pont, amely a sokszög belsejébe esik, feltételezhető, hogy a megfelelő klaszterhez tartozik. Ahogy a cikkben utaltam, ilyen sokszögeket használhat a vezetési kockázat érvényesítésére, felhasználva őket a saját mintavételezett GPS-helyének osztályozására.
a kérdés most az, hogyan lehet értelmes sokszöget létrehozni egy adott fürtöt alkotó pontfelhőből. Az első cikkben szereplő megközelítésem kissé na KB volt, és egy olyan megoldást tükrözött, amelyet már használtam a gyártási kódban. Ez a megoldás magában foglalta egy kör középpontba helyezését a klaszter minden pontján, majd az összes kör egyesítését felhő alakú sokszöggé alakítva. Az eredmény nem túl szép, sem reális. Továbbá, ha köröket használunk alapformaként a végső sokszög felépítéséhez, ezeknek több pontja lesz, mint egy egyszerűbb alakzatnak, ezáltal növelve a tárolási költségeket, és a befogadás-észlelési algoritmusok futtatása lassabb lesz.
másrészt ennek a megközelítésnek az az előnye, hogy számítási szempontból egyszerű (legalábbis a fejlesztő szempontjából), mivel a Shapely cascaded_union funkcióját használja az összes kör egyesítésére. További előny, hogy a sokszög alakját implicit módon definiálják a fürt összes pontjának felhasználásával.
a kifinomultabb megközelítésekhez valahogy meg kell határoznunk a klaszter határpontjait, azokat, amelyek látszólag meghatározzák a pontfelhő alakját. Érdekes, hogy néhány DBSCAN implementációval valóban helyreállíthatja a határpontokat a klaszterezési folyamat melléktermékeként. Sajnos ez az információ (látszólag) nem áll rendelkezésre a SciKit Learn megvalósításában, ezért meg kell tennünk.
az első megközelítés, amely eszembe jutott, a pontok halmazának konvex testének kiszámítása volt. Ez egy jól érthető algoritmus, de szenved attól a problémától, hogy nem kezeli a konkáv alakzatokat, mint ez:
pontok konkáv halmazának konvex teste ez az alakzat nem megfelelően rögzíti az alapul szolgáló pontok lényegét. Ha diszkriminátorként használják,néhány pontot helytelenül osztályoznának a klaszter belsejében, amikor nem. Más megközelítésre van szükségünk.
a konkáv hajótest alternatívája
szerencsére vannak alternatívák ennek a helyzetnek: kiszámolhatunk egy konkáv hajótestet. Így néz ki a konkáv hajótest, ha ugyanarra a pontkészletre alkalmazzák, mint az előző képen:
vagy talán ez:
mint látható, és ellentétben a konvex hajótesttel, nincs egyetlen meghatározás arra, hogy mi a konkáv hajótest egy ponthalmaz. Az itt bemutatott algoritmussal egyetlen paraméter segítségével választhatjuk meg, hogy milyen homorú legyen a hajótest: k-a hajótest számításakor figyelembe vett legközelebbi szomszédok száma. Lássuk, hogy működik ez.
az algoritmus
az itt bemutatott algoritmust több mint egy évtizeddel ezelőtt írta le Adriano Moreira és Maribel Yasmina Santos a Minho Egyetemről, Portugáliából . Az absztraktból:
ez a cikk egy algoritmust ír le egy síkban lévő ponthalmaz borítékának kiszámítására, amely konvexet generál a nem konvex hajótesteken, amelyek az adott pontok által elfoglalt területet képviselik. A javasolt algoritmus a K-legközelebbi szomszédok megközelítés, ahol a k, az egyetlen algoritmus paraméter, a végső megoldás “simaságának” szabályozására szolgál.
mivel ezt az algoritmust a földrajzi információkra fogom alkalmazni, néhány változtatást kellett végrehajtani, nevezetesen a szögek és távolságok kiszámításakor . De ezek semmilyen módon nem változtatják meg az algoritmus lényegét, amelyet a következő lépésekkel lehet nagyjából leírni:
- keresse meg a legalacsonyabb y (szélességi) koordinátájú pontot, és tegye az Aktuálissá.
- keresse meg az aktuális ponthoz legközelebbi k-pontokat.
- a K-legközelebbi pontok közül válassza ki azt, amelyik az előző szögből a legnagyobb jobb oldali fordulatnak felel meg. Itt a csapágy fogalmát fogjuk használni, és 270 fokos szöggel kezdjük (nyugat felé).
- ellenőrizze, hogy az új pont hozzáadásával a növekvő vonal karakterlánchoz nem keresztezi-e önmagát. Ha igen, válasszon egy másik pontot a K-legközelebbi pontból, vagy indítsa újra nagyobb k értékkel.
- tegye az új pontot aktuális pontnak, majd távolítsa el a listából.
- k iterációk után adja hozzá az első pontot a listához.
- hurok a 2.számhoz.
az algoritmus meglehetősen egyszerűnek tűnik, de számos részletet figyelembe kell venni, különösen azért, mert földrajzi koordinátákkal foglalkozunk. A távolságokat és a szögeket más módon mérik.
a kód
itt publikálok az előző cikk kódjának adaptált változata. Továbbra is ugyanazt a klaszterkódot és ugyanazt a felhő alakú klasztergenerátort fogja találni. A frissített verzió most egy geomath.hullsnevű csomagot tartalmaz, ahol megtalálható a ConcaveHull osztály. A konkáv hajótestek létrehozásához tegye a következőket:
a fenti kódban a points dimenziók tömbje (N, 2), ahol a sorok tartalmazzák a megfigyelt pontokat, az oszlopok pedig a földrajzi koordinátákat (hosszúság, szélesség). A kapott tömb felépítése pontosan megegyezik, de csak azokat a pontokat tartalmazza, amelyek a fürt sokszög alakjához tartoznak. Egyfajta szűrő.
mivel tömböket fogunk kezelni, természetes, hogy NumPy-t hozzuk a harcba. Minden számítást megfelelően vektorizáltak, amikor csak lehetséges, és erőfeszítéseket tettek a teljesítmény javítására, amikor elemeket adtak hozzá és távolítottak el a tömbökből (spoiler: egyáltalán nem mozognak). Az egyik hiányzó fejlesztés a kód párhuzamosítása. De az várhat.
a kódot az algoritmus köré szerveztem, amint az a cikkben látható, bár a fordítás során néhány optimalizálás történt. Az algoritmus számos olyan szubrutin köré épül, amelyeket a papír egyértelműen azonosít, tehát most tegyük el ezeket az útból. Az olvasás kényelme érdekében ugyanazokat a neveket fogom használni, mint a papírban.
CleanList —a tisztítás a pontok listáját végzik az osztály Kivitelező:
mint látható, a pontok listáját teljesítmény okokból NumPy tömbként hajtják végre. A lista tisztítása a 10. sorban történik,ahol csak az egyedi pontokat tartják. Az adathalmaz tömbje sorokba rendezett megfigyelésekkel, a két oszlopban pedig földrajzi koordinátákkal van rendezve. Ne feledje, hogy a 13.sorban egy logikai tömböt is létrehozok, amelyet a fő adatkészlet-tömb indexelésére használnak, megkönnyítve az elemek eltávolítását, majd egyszer-egyszer hozzáadását. Láttam ezt a “maszknak” nevezett technikát a NumPy dokumentációjában, és nagyon erős. Ami a prímszámokat illeti, később megvitatom őket.
FindMinYPoint-ez egy kis funkciót igényel:
ezt a függvényt az adatkészlet tömb argumentumaként hívják meg, és a legalacsonyabb szélességű pont indexét adja vissza. Vegye figyelembe, hogy a sorok az első oszlopban a hosszúsággal, a másodikban a szélességgel vannak kódolva.
RemovePoint
AddPoint — ezek nem agyak, a indices tömb használata miatt. Ez a tömb az aktív indexek tárolására szolgál a fő adatkészlet tömbben, így az elemek eltávolítása az adatkészletből egy pillanat alatt történik.
bár a cikkben leírt algoritmus egy pont hozzáadását kéri a hajótestet alkotó tömbhöz, ez valójában a következőképpen valósul meg:
később a test_hull változó vissza lesz rendelve hull-hez, ha a vonal karakterláncot nem keresztezőnek tekintik. De előrébb járok a játéknál. Egy pont eltávolítása az adatkészlet tömbből olyan egyszerű, mint:
self.indices = False
visszaadás csak egy kérdés essek, hogy a tömb értéke ugyanabban az indexben vissza igaz. De mindez a kényelem azzal az árral jár, hogy fülünket az indexeken kell tartani. Erről bővebben később.
NearestPoints-a dolgok kezdenek érdekes itt, mert nem foglalkozunk síkbeli koordináták, így ki Pythagoras és be Haversine:
vegye figyelembe, hogy a második és a harmadik paraméter tömbök az adatkészlet formátumában: hosszúság az első oszlopban, szélesség a másodikban. Mint látható, ez a függvény a második argumentum pontja és a harmadik argumentum pontjai közötti távolság tömbjét adja vissza méterben. Ha ezek megvannak, a k-legközelebbi szomszédokat könnyen megszerezhetjük. De erre van egy speciális funkció, amely magyarázatot érdemel:
a funkció egy tömb létrehozásával kezdődik az alapindexekkel. Ezek azoknak a pontoknak az indexei, amelyeket nem távolítottak el az adatkészlet tömbből. Például, ha egy tízpontos klaszteren az első pont eltávolításával kezdtük, akkor az alapindex tömb lenne . Ezután kiszámítjuk a távolságokat és rendezzük a kapott tömbindexeket. Az első k-t kivonják, majd maszkként használják az alapindexek lekérésére. Kicsit eltorzult, de működik. Amint láthatja, a függvény nem koordináták tömbjét adja vissza, hanem indexek tömbjét az adatkészlet tömbjébe.
SortByAngle-itt több baj van, mert nem egyszerű szögeket számolunk, hanem csapágyakat. Ezeket észak felé nulla fokként mérik, a szögek az óramutató járásával megegyező irányban növekednek. Itt van a kód lényege, amely kiszámítja a csapágyakat:
a függvény a csapágyak tömbjét adja vissza attól a ponttól mérve, amelynek indexe az első argumentumban van, azokhoz a pontokhoz, amelyek indexei a harmadik argumentumban vannak. A válogatás egyszerű:
ezen a ponton a jelöltek tömb tartalmazza a K-legközelebbi pontok indexeit csökkenő csapágyrend szerint rendezve.
IntersectQ — ahelyett, hogy gördülő saját vonal metszéspont funkciók, fordultam Shapely segítségért. Valójában a sokszög felépítése során lényegében egy vonalas karakterláncot kezelünk, olyan szegmenseket fűzünk hozzá, amelyek nem metszik egymást az előzőekkel. Ennek tesztelése egyszerű: felvesszük az építés alatt álló hajótest tömböt, átalakítjuk formás vonalas karakterlánc objektummá, és megvizsgáljuk, hogy egyszerű-e (nem önmetsző) vagy sem.
dióhéjban egy formás vonalas karakterlánc összetetté válik, ha önmagát keresztezi, így a is_simple predikátum hamis lesz. Nyugi.
PointInPolygon — ez kiderült, hogy a legnehezebb megvalósítani. Engedje meg, hogy elmagyarázzam a kódot, amely elvégzi a végső hajótest sokszög érvényesítését (ellenőrzi, hogy a fürt összes pontja szerepel-e a sokszögben):
Shapely függvényei a metszéspont és a befogadás teszteléséhez elegendőnek kellett volna lenniük annak ellenőrzéséhez, hogy a végső hajótest sokszög átfedi-e a klaszter összes pontját, de nem voltak. Miért? A Shapely koordináta-agnosztikus, tehát a földrajzi koordinátákat szélességben és hosszúságban pontosan ugyanúgy kezeli, mint a derékszögű sík koordinátáit. De a világ másképp viselkedik, ha egy gömbön élsz, és a szögek (vagy csapágyak) nem állandóak egy geodéziai mentén. A Bagdadot Oszakával összekötő geodéziai vonal hivatkozási példája tökéletesen szemlélteti ezt. Előfordul, hogy bizonyos körülmények között az algoritmus tartalmazhat egy pontot a csapágykritérium alapján, de később, Shapely síkbeli algoritmusainak felhasználásával, mindig kissé a sokszögen kívülinek tekinthető. Ez az, amit a kis távolság korrekció csinál ott.
eltartott egy ideig, mire rájöttem. A hibakeresési segítségem a QGIS volt, egy nagyszerű szabad szoftver. A gyanús számítások minden lépésénél az adatokat WKT formátumban egy CSV fájlba írnám, amelyet rétegként kell olvasni. Egy igazi életmentő!
végül, ha a sokszög nem fedi le a klaszter összes pontját, akkor az egyetlen lehetőség a K növelése és az újbóli próbálkozás. Itt hozzáadtam egy kicsit a saját intuíciómat.
prím k
a cikk azt javasolja, hogy a K értékét eggyel növeljük, és az algoritmust újra a nulláról hajtsuk végre. Az ezzel az opcióval végzett korai tesztjeim nem voltak túl kielégítőek: a futási idő lassú lenne a problémás klasztereknél. Ennek oka a k lassú növekedése volt, ezért úgy döntöttem, hogy egy másik növekedési ütemtervet használok: a prímszámok táblázatát. Az algoritmus már K=3-mal indul, így könnyű kiterjesztés volt, hogy a prímszámok listáján fejlődjön. Ez az, amit látsz történik a rekurzív hívás:
van egy dolgom a prímszámokkal, tudod…
felrobbantani
az algoritmus által generált homorú hajótest sokszögek még további feldolgozásra szorulnak, mert csak a hajótest belsejében lévő pontokat különböztetik meg, de nem közel hozzá. A megoldás az, hogy hozzáadunk néhány párnát ezekhez a vékony klaszterekhez. Itt pontosan ugyanazt a technikát használom, mint korábban, és itt van, hogy néz ki:
itt Shapely buffer funkcióját használtam a trükk elvégzéséhez.
a függvény Elfogad egy formás sokszöget, és visszaadja önmagának felfújt változatát. A második paraméter a hozzáadott padding sugara méterben.
a kód futtatása
először húzza ki a kódot a GitHub adattárból a helyi gépbe. A végrehajtani kívánt fájl ShowHotSpots.py a fő könyvtárban. Az első végrehajtáskor a kód beolvassa az Egyesült Királyság 2013-2016-os közlekedési baleseteinek adatait, és csoportosítja azokat. Az eredményeket ezután CSV-fájlként gyorsítótárazzák a későbbi futtatásokhoz.
ezután két térképet mutat be: az első a felhő alakú klaszterek, míg a második az itt tárgyalt konkáv klaszterezési algoritmust használja. A sokszöggeneráló kód végrehajtása közben előfordulhat, hogy néhány hibát jelentenek. Annak megértése érdekében, hogy az algoritmus miért nem hoz létre konkáv hajótestet, a kód a fürtöket CSV fájlokba írja a data/out/failed/ könyvtárba. Mint általában, a QGIS segítségével ezeket a fájlokat rétegként importálhatja.
lényegében ez az algoritmus kudarcot vall, ha nem talál elegendő pontot az alakzat” megkerüléséhez ” anélkül, hogy önmagát keresztezné. Ez azt jelenti, hogy készen kell állnia arra, hogy eldobja ezeket a klasztereket, vagy más kezelést alkalmazzon rájuk (konvex hajótest vagy összeolvadt buborékok).
Konkávság
ez egy wrap. Ebben a cikkben bemutattam egy módszert a dbscan által generált földrajzi klaszterek konkáv alakzatokká történő utófeldolgozására. Ez a módszer más alternatívákhoz képest jobban illeszkedő külső sokszöget biztosíthat a klaszterek számára.
Köszönjük, hogy elolvasta és élvezze a kód bütykölését!
Kryskiewicz M., Lasek P. (2010) TI-DBSCAN: klaszterezés a Dbscan segítségével a háromszög egyenlőtlenség. In: Szczuka M., Kryskiewicz M., Ramanna S., Jensen R., Hu Q. (Szerk.) durva halmazok és aktuális trendek a számítástechnikában. 2010. Előadás jegyzetek a számítástechnikában, vol 6086. Springer, Berlin, Heidelberg
Scikit-learn: Gépi tanulás Pythonban, Pedregosa et al., JMLR 12, pp. 2825-2830, 2011
Moreira, A. and Santos, M. Y., 2007, homorú hajótest: a K-legközelebbi szomszédok megközelítés a számítás a régió által elfoglalt egy sor pontot
Számítsuk távolság, csapágy és több közötti szélességi / hosszúsági pontok
GitHub repository
