Det Konkave Skroget

Opprette en klyngegrense ved hjelp Av en k-nærmeste naboer tilnærming

for et par måneder siden skrev jeg her På Medium en artikkel om kartlegging AV STORBRITANNIAS trafikkulykker. Jeg var mest opptatt av å illustrere bruken AV dbscan clustering algoritmen på geografiske data. I artikkelen brukte jeg geografisk informasjon publisert AV DEN BRITISKE regjeringen om rapporterte trafikkulykker. Min hensikt var å kjøre en tetthetsbasert klyngeprosess for å finne de områdene der trafikkulykker rapporteres hyppigst. Sluttresultatet var opprettelsen av et sett med geo-gjerder som representerer disse ulykkeshottene.

ved å samle alle punkter i en gitt klynge, kan du få en ide om hvordan klyngen vil se ut på et kart, men du vil mangle en viktig del av informasjonen: klyngen ytre form. I dette tilfellet snakker vi om en lukket polygon som kan representeres på et kart som et geo-gjerde. Ethvert punkt inne i geo-gjerdet kan antas å tilhøre klyngen, noe som gjør denne formen til et interessant stykke informasjon: du kan bruke den som en diskriminatorfunksjon. Alle nylig samplede punkter som faller inne i polygonen, kan antas å tilhøre den tilsvarende klyngen. Som jeg antydet i artikkelen, kan du bruke slike polygoner for å hevde din kjørerisiko, ved å bruke dem til å klassifisere din egen samplet GPS-posisjon.

spørsmålet er nå hvordan man lager en meningsfull polygon ut av en sky av punkter som utgjør en bestemt klynge. Min tilnærming i den første artikkelen var noe naï og reflekterte en losning som jeg allerede hadde brukt i produksjonskoden. Denne løsningen innebar å plassere en sirkel sentrert på hver av klyngens punkter og deretter slå sammen alle sirkler sammen for å danne et skyformet polygon. Resultatet er ikke veldig hyggelig, heller ikke realistisk. Ved å bruke sirkler som basisform for å bygge den endelige polygonen, vil disse også ha flere poeng enn en mer strømlinjeformet form, og dermed øke lagringskostnadene og gjøre inkluderingsdeteksjonsalgoritmene langsommere å kjøre.

på den annen side har denne tilnærmingen fordelen av å være beregningsmessig enkel (i hvert fall fra utviklerens perspektiv), da Den bruker Shapely ‘ s cascaded_union – funksjon for å slå sammen alle sirkler sammen. En annen fordel er at polygonens form er implisitt definert ved hjelp av alle punkter i klyngen.

for mer sofistikerte tilnærminger må vi på en eller annen måte identifisere klyngens grensepunkter, de som synes å definere punktskyformen. Interessant, med noen dbscan implementeringer kan du faktisk gjenopprette grensepunktene som et biprodukt av klyngeprosessen. Dessverre er denne informasjonen (tilsynelatende) ikke tilgjengelig på SciKit Learn implementering,så vi må gjøre det.

den første tilnærmingen som sprang i tankene var å beregne det konvekse skroget til settet av poeng. Dette er en godt forstått algoritme, men lider av problemet med å ikke håndtere konkave former, som denne:

denne formen fanger ikke essensen av de underliggende punktene riktig. Ble det brukt som diskriminator, ville noen poeng bli feilaktig klassifisert som å være inne i klyngen når de ikke er det. Vi trenger en annen tilnærming.

Det Konkave Skrogalternativet

Heldigvis finnes det alternativer til denne tilstanden: vi kan beregne et konkavt skrog. Slik ser det konkave skroget ut når det brukes på samme sett med punkter som i forrige bilde:

Eller kanskje denne:

som du kan se, og i motsetning til det konvekse skroget, er det ingen enkelt definisjon av hva det konkave skroget til et sett med punkter er. Med algoritmen som jeg presenterer her, er valget av hvor konkav du vil at skrogene skal være, gjort gjennom en enkelt parameter: k-antall nærmeste naboer som vurderes under skrogberegningen. La oss se hvordan dette fungerer.

Algoritmen

algoritmen jeg presenterer her ble beskrevet over et tiår siden Av Adriano Moreira Og Maribel Yasmina Santos fra Universitetet I Minho, Portugal . Fra det abstrakte:

dette papiret beskriver en algoritme for å beregne konvolutten til et sett med punkter i et plan, som genererer konveks på ikke-konvekse skrog som representerer området okkupert av de gitte punktene. Den foreslåtte algoritmen er basert på en k-nærmeste nabo tilnærming, hvor verdien av k, den eneste algoritmeparameteren, brukes til å kontrollere “glattheten” av den endelige løsningen.

Fordi jeg vil bruke denne algoritmen til geografisk informasjon, måtte det gjøres noen endringer, nemlig ved beregning av vinkler og avstander . Men disse endrer ikke på noen måte kjernen til algoritmen, som i stor grad kan beskrives ved hjelp av følgende trinn:

1. Finn punktet med den laveste y (latitude) koordinaten og gjør den den nåværende.
2. Finn de k-nærmeste punktene til gjeldende punkt.
3. fra de k-nærmeste punktene, velg den som tilsvarer den største høyre sving fra forrige vinkel. Her vil vi bruke begrepet lager og starte med en vinkel på 270 grader (rett Vest).
4. Kontroller om det ved å legge til det nye punktet i den voksende linjestrengen ikke krysser seg selv. Hvis den gjør det, velger du et annet punkt fra k-nærmeste eller starter på nytt med en større verdi på k.
5. Gjør det nye punktet gjeldende punkt og fjern det fra listen.
6. etter k iterasjoner legger du det første punktet tilbake til listen.
7. Sløyfe til nummer 2.

algoritmen ser ut til å være ganske enkel, men det er en rekke detaljer som må ivaretas, særlig fordi vi har å gjøre med geografiske koordinater. Avstander og vinkler måles på en annen måte.

Koden

Her publiserer jeg en tilpasset versjon av forrige artikkels kode. Du vil fortsatt finne den samme klyngekoden og den samme skyformede klyngegeneratoren. Den oppdaterte versjonen inneholder nå en pakke som heter geomath.hulls hvor du kan finne ConcaveHull – klassen. For å lage dine konkave skrog gjør du som følger:

i koden ovenfor er points en rekke dimensjoner (N, 2), hvor radene inneholder de observerte punktene og kolonnene inneholder de geografiske koordinatene (lengdegrad, breddegrad). Den resulterende matrisen har nøyaktig samme struktur, men inneholder bare punktene som tilhører klyngens polygonale form. Et slags filter.

Fordi Vi skal håndtere arrays, er det bare naturlig å bringe NumPy inn i fray. Alle beregninger ble behørig vektorisert, når det var mulig, og det ble gjort anstrengelser for å forbedre ytelsen når du legger til og fjerner elementer fra arrays (spoiler: de er ikke flyttet i det hele tatt). En av de manglende forbedringene er kodeparallellisering. Men det kan vente.

jeg organiserte koden rundt algoritmen som eksponert i papiret, selv om noen optimaliseringer ble gjort under oversettelsen. Algoritmen er bygget rundt en rekke subrutiner som er tydelig identifisert av papiret, så la oss få dem ut av veien akkurat nå. For din lesekomfort vil jeg bruke de samme navnene som brukes i papiret.

CleanList-rengjøring listen over poeng utføres i klassen konstruktøren:

som du kan se, er listen over poeng implementert som Et NumPy array av ytelseshensyn. Rengjøring av listen utføres på linje 10, hvor bare de unike punktene holdes. Datasettet array er organisert med observasjoner i rader og geografiske koordinater i de to kolonnene. Merk at jeg også lager En Boolsk array på linje 13 som vil bli brukt til å indeksere inn i hoveddatasettet, lette arbeidet med å fjerne elementer og, en gang imellom, legge dem tilbake. Jeg har sett denne teknikken kalt en “maske” på numpy dokumentasjonen, og den er veldig kraftig. Når det gjelder primtallene, vil jeg diskutere dem senere.

FindMinYPoint-dette krever en liten funksjon:

denne funksjonen kalles med datasett-matrisen som argument og returnerer indeksen for punktet med laveste breddegrad. Merk at rader er kodet med lengdegrad i den første kolonnen og breddegrad i den andre.

RemovePoint
AddPoint — Disse er no-brainers, på grunn av bruken av indices – arrayet. Denne matrisen brukes til å lagre de aktive indeksene i hoveddatasettet, så det er enkelt å fjerne elementer fra datasettet.

selv om algoritmen som beskrevet i papiret krever å legge til et punkt i matrisen som utgjør skroget, er dette faktisk implementert som:

senere blir test_hull – variabelen tilordnet tilbake til hull når linjestrengen anses som ikke-kryssende. Men jeg kommer foran spillet her. Å fjerne et punkt fra datasettet er så enkelt som:

self.indices = False

Å Legge den tilbake er bare et spørsmål om å vende den matriseverdien på samme indeks tilbake til sann. Men all denne bekvemmeligheten kommer med prisen på å måtte holde våre faner på indeksene. Mer om dette senere.

NearestPoints-Ting begynner å bli interessante her fordi vi ikke har å gjøre med plane koordinater, så ut med Pythagoras og inn Med Haversine:

Legg Merke til at andre og tredje parametere er arrays i datasettformatet: lengdegrad i den første kolonnen og breddegrad i den andre. Som du kan se, returnerer denne funksjonen en rekke avstander i meter mellom punktet i det andre argumentet og punktene i det tredje argumentet. Når vi har disse, kan vi få k-nærmeste naboer den enkle måten. Men det er en spesialisert funksjon for det, og det fortjener noen forklaringer:

funksjonen starter ved å lage en matrise med basisindeksene. Dette er indeksene til punktene som ikke er fjernet fra datasettet. For eksempel, hvis vi på en ti punktsklynge startet ved å fjerne det første punktet, ville basisindeksene være. Deretter beregner vi avstandene og sorterer de resulterende arrayindeksene. Den første k blir ekstrahert og deretter brukt som en maske for å hente basisindeksene. Det er litt forvrengt, men fungerer. Som du kan se, returnerer funksjonen ikke en rekke koordinater, men en rekke indekser i datasettet.

SortByAngle — Det er flere problemer her fordi vi ikke beregner enkle vinkler, vi beregner lagrene. Disse måles som null grader mot Nord, med vinkler som øker med klokken. Her er kjernen i koden som beregner lagrene:

funksjonen returnerer en rekke lagre målt fra punktet hvis indeks er i det første argumentet, til punktene hvis indekser er i det tredje argumentet. Sortering er enkel:

på dette punktet inneholder kandidatarrayet indeksene til k-nærmeste poeng sortert etter synkende rekkefølge av lager.

IntersectQ-I Stedet for å rulle mine egne linjekryssfunksjoner, vendte jeg Meg Til Å Få Hjelp. Faktisk, mens vi bygger polygonen, håndterer vi i hovedsak en linjestreng, legger til segmenter som ikke krysser med de forrige. Testing for dette er enkelt: vi plukker opp skroget under konstruksjon, konverterer det til Et Formet linjestrengobjekt, og tester om det er enkelt (ikke selvkryssende) eller ikke.

I et nøtteskall blir En Velskapt linjestreng kompleks hvis den krysser seg selv, slik at is_simple – predikatet blir falskt. Enkel.

PointInPolygon-dette viste seg å være den vanskeligste å implementere. Tillat meg å forklare ved å se på koden som utfører den endelige skrog polygon validering (kontrollerer om alle punktene i klyngen er inkludert i polygonen):

Shapely ‘ s funksjoner for å teste for kryss og inkludering burde vært nok til å sjekke om den endelige skrogpolygonen overlapper alle klyngens punkter, men de var ikke. Hvorfor? Shapely er koordinat-agnostisk, så den vil håndtere geografiske koordinater uttrykt i breddegrader og lengder på nøyaktig samme måte som koordinater på Et Kartesisk plan. Men verden oppfører seg annerledes når du bor på en sfære, og vinkler (eller lagre) er ikke konstante langs en geodesisk. Eksemplet på referanse av en geodetisk linje som forbinder Bagdad Til Osaka illustrerer dette perfekt. Det skjer slik at algoritmen under noen omstendigheter kan inkludere et punkt basert på lagerkriteriet, men senere, ved Hjelp Av Shapely ‘ s plane algoritmer, anses aldri så litt utenfor polygonen. Det er hva den lille avstandskorreksjonen gjør der.

Det tok meg en stund å finne ut dette. Min debugging hjelp VAR QGIS, et flott stykke fri programvare. Ved hvert trinn i de mistenkelige beregningene vil jeg sende dataene I WKT-format til EN CSV-fil som skal leses inn som et lag. En ekte livredder!

Til Slutt, hvis polygonen ikke dekker alle klyngens poeng, er det eneste alternativet å øke k og prøve igjen. Her har jeg lagt til litt av min egen intuisjon.

Prime k

artikkelen antyder at verdien av k økes med en og at algoritmen utføres igjen fra bunnen av. Mine tidlige tester med dette alternativet var ikke veldig tilfredsstillende: kjøretider ville være sakte på problematiske klynger. Dette skyldtes den langsomme økningen av k, så jeg bestemte meg for å bruke en annen økningsplan: et bord med primtall. Algoritmen starter allerede med k = 3, så det var en enkel utvidelse for å få det til å utvikle seg på en liste over primtall. Dette er hva du ser skjer i rekursiv samtale:

jeg har en ting for primtall, du vet…

Blås Opp

de konkave skrogpolygonene generert av denne algoritmen trenger fortsatt litt videre behandling, fordi de bare vil diskriminere punkter inne i skroget, men ikke nær det. Løsningen er å legge til litt polstring til disse tynne klyngene. Her bruker jeg nøyaktig samme teknikk som brukt før, og her er hva det ser ut som:

her brukte Jeg Shapely ‘ s bufferfunksjon for å gjøre trikset.

funksjonen aksepterer En Velskapt Polygon og returnerer en oppblåst versjon av seg selv. Den andre parameteren er radiusen i meter av den tilsatte polstringen.

Kjør Koden

Start med å trekke koden fra GitHub-depotet til din lokale maskin. Filen du vil kjøre er ShowHotSpots.py i hovedkatalogen. Ved første utførelse vil koden lese I BRITISKE trafikkulykkedata fra 2013 til 2016 og klynge den. Resultatene blir deretter bufret SOM EN CSV-fil for påfølgende kjøringer.

du vil da bli presentert med to kart: den første genereres ved hjelp av skyformede klynger mens den andre bruker den konkave klyngealgoritmen diskutert her. Mens polygongenerasjonskoden utfører, kan du se at noen feil er rapportert. For å forstå hvorfor algoritmen ikke klarer å skape et konkavt skrog, skriver koden klyngene TIL CSV-filer til katalogen data/out/failed/. SOM vanlig kan DU bruke QGIS til å importere disse filene som lag.

I Hovedsak mislykkes denne algoritmen når den ikke finner nok poeng til å “gå rundt” formen uten selvkryssing. Dette betyr at du må være klar til å enten kaste disse klyngene, eller å bruke en annen behandling for dem (konveks skrog eller koaleserte bobler).

Konkaveness

Det er en wrap. I denne artikkelen presenterte jeg en metode for etterbehandling DBSCAN generert geografiske klynger i konkave former. Denne metoden kan gi en bedre passform utenfor polygon for klyngene i forhold til andre alternativer.

Takk For at du leser og liker å tinkere med koden!

Kryszkiewicz M., Lasek P. (2010) TI-Dbscan: Clustering MED DBSCAN ved Hjelp av Trekanten Ulikhet. I: Szczuka M., Kryszkiewicz M., Ramanna S., Jensen R., Hu Q. (eds) Grove Sett og Dagens Trender Innen Databehandling. RSCTC 2010. Forelesningsnotater I Informatikk, vol 6086. Springer, Berlin, Heidelberg

Scikit-lær: Maskinlæring i Python, Pedregosa et al., JMLR 12, pp. 2825-2830, 2011

Moreira, a. og Santos, M. Y., 2007, Konkav Skrog: en k-nærmeste naboer tilnærming for beregning av regionen okkupert av et sett med poeng

Beregn avstand, peiling og mer mellom Breddegrad / Lengdegrad poeng

GitHub repository