det konkave skrog

oprettelse af en klyngegrænse ved hjælp af en k-nærmeste nabo tilgang

for et par måneder siden skrev jeg her på Medium en artikel om kortlægning af Storbritanniens trafikulykker hot spots. Jeg var mest bekymret for at illustrere brugen af dbscan clustering algoritmen på geografiske data. I artiklen brugte jeg geografiske oplysninger offentliggjort af den britiske regering om rapporterede trafikulykker. Mit formål var at køre en tæthedsbaseret klyngeproces for at finde de områder, hvor trafikulykker rapporteres hyppigst. Slutresultatet var oprettelsen af et sæt geo-hegn, der repræsenterer disse hot spots for ulykker.

ved at samle alle punkter i en given klynge kan du få en ide om, hvordan klyngen ville se ud på et kort, men du mangler et vigtigt stykke information: klyngens ydre form. I dette tilfælde taler vi om en lukket polygon, der kan repræsenteres på et kort som et geo-hegn. Ethvert punkt inde i geo-hegnet kan antages at tilhøre klyngen, hvilket gør denne form til et interessant stykke information: du kan bruge det som en diskriminatorfunktion. Alle nyligt samplede punkter, der falder inde i polygonen, kan antages at tilhøre den tilsvarende klynge. Som jeg antydede i artiklen, kunne du bruge sådanne polygoner til at hævde din kørselsrisiko ved at bruge dem til at klassificere din egen samplede GPS-placering.

spørgsmålet er nu, hvordan man opretter en meningsfuld polygon ud af en sky af punkter, der udgør en bestemt klynge. Min tilgang i den første artikel var noget na pristve og afspejlede en løsning, som jeg allerede havde brugt i produktion kode. Denne løsning indebar at placere en cirkel centreret ved hvert af klyngens punkter og derefter flette alle cirkler sammen for at danne en skyformet polygon. Resultatet er ikke særlig flot eller realistisk. Ved at bruge cirkler som basisform til opbygning af den endelige polygon vil disse også have flere point end en mere strømlinet form, hvilket øger lageromkostningerne og gør inklusionsdetekteringsalgoritmerne langsommere at køre.

på den anden side har denne tilgang fordelen ved at være beregningsmæssigt enkel (i det mindste fra udviklerens perspektiv), da den bruger Shapely ‘ s cascaded_union – funktion til at flette alle cirkler sammen. En anden fordel er, at polygonens form implicit defineres ved hjælp af alle punkter i klyngen.

for mere sofistikerede tilgange skal vi på en eller anden måde identificere klyngens grænsepunkter, dem der synes at definere punktskyformen. Interessant nok kan du med nogle dbscan-implementeringer faktisk gendanne grænsepunkterne som et biprodukt af klyngeprocessen. Desværre er disse oplysninger (tilsyneladende) ikke tilgængelige på SciKit Learn ‘ s implementering, så vi er nødt til at gøre det.

den første tilgang, der sprang i tankerne, var at beregne det konvekse skrog af sæt af punkter. Dette er en velkendt algoritme, men lider af problemet med ikke at håndtere konkave former, som denne:

denne form fanger ikke korrekt essensen af de underliggende punkter. Blev det brugt som diskriminator, ville nogle punkter fejlagtigt klassificeres som værende inde i klyngen, når de ikke er det. Vi har brug for en anden tilgang.

det konkave Skrogalternativ

heldigvis er der alternativer til denne situation: vi kan beregne et konkav skrog. Sådan ser det konkave skrog ud, når det anvendes på det samme sæt punkter som i det foregående billede:

eller måske denne:

som du kan se, og i modsætning til det konvekse skrog, er der ingen enkelt definition af, hvad det konkave skrog af et sæt punkter er. Med den algoritme, som jeg præsenterer her, foretages valget af, hvor konkav du vil have dine skrog, gennem en enkelt parameter: k — antallet af nærmeste naboer, der overvejes under skrogberegningen. Lad os se, hvordan dette fungerer.

algoritmen

algoritmen, jeg præsenterer her, blev beskrevet for over et årti siden af Adriano Moreira og Maribel Yasmina Santos fra University of Minho, Portugal . Fra det abstrakte:

dette papir beskriver en algoritme til beregning af konvolutten for et sæt punkter i et plan, der genererer konveks på ikke-konvekse skrog, der repræsenterer det område, der er besat af de givne punkter. Den foreslåede algoritme er baseret på en k-nærmeste nabo tilgang, hvor værdien af k, den eneste algoritmeparameter, bruges til at styre “glatheden” af den endelige løsning.

fordi jeg vil anvende denne algoritme på geografisk information, måtte der foretages nogle ændringer, nemlig ved beregning af vinkler og afstande . Men disse ændrer ikke på nogen måde kernen i algoritmen, der kan beskrives bredt ved følgende trin:

1. Find punktet med den laveste y (breddegrad) koordinat og gør det til det nuværende.
2. Find k-nærmeste punkter til det aktuelle punkt.
3. fra K-nærmeste punkter skal du vælge den, der svarer til den største højre drejning fra den forrige vinkel. Her vil vi bruge begrebet leje og starte med en vinkel på 270 grader (ret vest).
4. Kontroller, om det ved at tilføje det nye punkt til den voksende linjestreng ikke skærer sig selv. Hvis det gør det, skal du vælge et andet punkt fra K-nærmeste eller genstarte med en større værdi på k.
5. gør det nye punkt til det aktuelle punkt og fjern det fra listen.
6. efter k iterationer tilføj det første punkt tilbage til listen.
7. Loop til nummer 2.

algoritmen synes at være ret simpel, men der er en række detaljer, der skal overholdes, især fordi vi har at gøre med Geografiske koordinater. Afstande og vinkler måles på en anden måde.

koden

her udgiver jeg er en tilpasset version af den forrige artikels kode. Du vil stadig finde den samme klyngekode og den samme skyformede klyngegenerator. Den opdaterede version indeholder nu en pakke med navnet geomath.hulls hvor du kan finde ConcaveHull klassen. For at oprette dine konkave skrog skal du gøre som følger:

i koden ovenfor er points en række dimensioner (N, 2), hvor rækkerne indeholder de observerede punkter, og kolonnerne indeholder de geografiske koordinater (længdegrad, breddegrad). Det resulterende array har nøjagtig den samme struktur, men indeholder kun de punkter, der hører hjemme i klyngens polygonale form. Et filter af slags.

fordi vi vil håndtere arrays er det kun naturligt at bringe NumPy ind i kampen. Alle beregninger blev behørigt vektoriseret, når det var muligt, og der blev gjort en indsats for at forbedre ydeevnen, når du tilføjer og fjerner genstande fra arrays (spoiler: de flyttes slet ikke). En af de manglende forbedringer er kodeparallelisering. Men det kan vente.

jeg organiserede koden omkring algoritmen som eksponeret i papiret, selvom nogle optimeringer blev foretaget under oversættelsen. Algoritmen er bygget op omkring en række subrutiner, der er tydeligt identificeret af papiret, så lad os få dem ud af vejen lige nu. For din læsekomfort vil jeg bruge de samme navne som brugt i papiret.

CleanList-rengøring listen over punkter udføres i klassen konstruktør:

som du kan se, implementeres listen over punkter som et NumPy-array af præstationsårsager. Rengøringen af listen udføres på linje 10, hvor kun de unikke punkter opbevares. Datasættet array er organiseret med observationer i rækker og Geografiske koordinater i de to kolonner. Bemærk, at jeg også opretter et boolsk array på linje 13, der vil blive brugt til at indeksere i hoveddatasætarrayet, lette opgaven med at fjerne elementer og en gang imellem tilføje dem tilbage. Jeg har set denne teknik kaldet en” maske ” på numpy-dokumentationen, og den er meget kraftig. Hvad angår primtal, vil jeg diskutere dem senere.

FindMinYPoint-dette kræver en lille funktion:

denne funktion kaldes med datasæt array som argument og returnerer indekset for det punkt med den laveste breddegrad. Bemærk, at rækker er kodet med længdegrad i den første kolonne og breddegrad i den anden.

RemovePoint
AddPoint — disse er no-brainers på grund af brugen af indices array. Dette array bruges til at gemme de aktive indekser i hoveddatasætarrayet, så det er et øjeblik at fjerne elementer fra datasættet.

selvom algoritmen som beskrevet i papiret kræver tilføjelse af et punkt til det array, der udgør skroget, implementeres dette faktisk som:

senere tildeles variablen test_hull tilbage til hull, når linjestrengen betragtes som ikke-krydsende. Men jeg kommer foran spillet her. Fjernelse af et punkt fra datasæt array er så simpelt som:

self.indices = False

tilføjelse af det tilbage er bare et spørgsmål om at vende den array-værdi ved det samme indeks tilbage til sand. Men al denne bekvemmelighed kommer med prisen for at skulle holde vores faner på indekserne. Mere om dette senere.

Nærmestepunkter-ting begynder at blive interessante her, fordi vi ikke har at gøre med plane koordinater, så ud med Pythagoras og ind med Haversine:

Bemærk, at den anden og tredje parameter er arrays i datasætformatet: længdegrad i den første kolonne og breddegrad i den anden. Som du kan se, returnerer denne funktion en række afstande i meter mellem punktet i det andet argument og punkterne i det tredje argument. Når vi har disse, Vi kan få de k-nærmeste naboer på den nemme måde. Men der er en specialiseret funktion til det, og det fortjener nogle forklaringer:

funktionen starter ved at oprette et array med basisindekserne. Dette er indekserne for de punkter, der ikke er fjernet fra datasætarrayet. For eksempel, hvis vi på en ti-punkts klynge startede med at fjerne det første punkt, ville basisindeksarrayet være . Dernæst beregner vi afstandene og sorterer de resulterende arrayindekser. Den første k ekstraheres og bruges derefter som en maske til at hente basisindekserne. Det er lidt forvrænget, men fungerer. Som du kan se, returnerer funktionen ikke en række koordinater, men en række indekser i datasætarrayet.

SortByAngle — der er flere problemer her, fordi vi ikke beregner enkle vinkler, vi beregner lejer. Disse måles som nul grader ret nord, med vinkler stigende med uret. Her er kernen i koden, der beregner lejerne:

funktionen returnerer en række lejer målt fra det punkt, hvis indeks er i det første argument, til de punkter, hvis indeks er i det tredje argument. Sortering er enkel:

på dette tidspunkt indeholder kandidatarrayet indekserne for de k-nærmeste punkter sorteret efter faldende rækkefølge.

kryds — i stedet for at rulle mine egne linjekrydsningsfunktioner henvendte jeg mig til Shapely for at få hjælp. Faktisk, mens vi bygger polygonen, håndterer vi i det væsentlige en linjestreng, der tilføjer segmenter, der ikke skærer hinanden med de foregående. Test for dette er simpelt: vi henter skrogarrayet under konstruktion, konverterer det til et formet linjestrengobjekt og tester, om det er enkelt (ikke selvskærende) eller ej.

i en nøddeskal bliver en formet linjestreng kompleks, hvis den selv krydser, så prædikatet is_simple bliver falsk. Let.

PointInPolygon — dette viste sig at være den sværeste at gennemføre. Tillad mig at forklare ved at se på koden, der udfører den endelige hull polygon Validering (kontrollerer, om alle punkter i klyngen er inkluderet i polygonen):

Shapely ‘ s funktioner til at teste for kryds og inklusion burde have været nok til at kontrollere, om den endelige skrogpolygon overlapper alle klyngens punkter, men det var de ikke. Hvorfor? Shapely er koordinat-agnostiker, så det vil håndtere Geografiske koordinater udtrykt i breddegrader og længdegrader nøjagtigt på samme måde som koordinater på et kartesisk plan. Men verden opfører sig anderledes, når du bor på en kugle, og vinkler (eller lejer) er ikke konstante langs en geodesisk. Eksemplet med henvisning til en geodesisk linje, der forbinder Bagdad med Osaka, illustrerer dette perfekt. Det sker således, at algoritmen under visse omstændigheder kan omfatte et punkt baseret på lejekriteriet, men senere, ved hjælp af Shapely ‘ s plane algoritmer, betragtes som nogensinde så lidt uden for polygonen. Det er, hvad den lille afstandskorrektion gør der.

det tog mig et stykke tid at finde ud af dette. Min fejlsøgningshjælp var et godt stykke gratis program. Ved hvert trin i de mistænkelige beregninger ville jeg udlæse dataene i et CSV-fil, der skal læses i som et lag. En rigtig livredder!

endelig, hvis polygonen ikke dækker alle klyngens punkter, er den eneste mulighed at øge k og prøve igen. Her tilføjede jeg lidt af min egen intuition.

Prime k

artiklen antyder, at værdien af k øges med en, og at algoritmen udføres igen fra bunden. Mine tidlige tests med denne mulighed var ikke særlig tilfredsstillende: køretider ville være langsomme på problematiske klynger. Dette skyldtes den langsomme stigning i k, så jeg besluttede at bruge en anden stigningsplan: en tabel med primtal. Algoritmen starter allerede med k=3, så det var en nem udvidelse at få den til at udvikle sig på en liste over primtal. Dette er hvad du ser ske i det rekursive opkald:

jeg har en ting for primtal, du ved…

sprænge

de konkave skrogpolygoner genereret af denne algoritme har stadig brug for yderligere behandling, fordi de kun vil diskriminere punkter inde i skroget, men ikke tæt på det. Løsningen er at tilføje noget polstring til disse tynde klynger. Her bruger jeg nøjagtig samme teknik som brugt før, og her er hvordan det ser ud:

her brugte jeg Shapely ‘ S buffer funktion til at gøre tricket.

funktionen accepterer en velformet Polygon og returnerer en oppustet version af sig selv. Den anden parameter er radius i meter af den tilsatte polstring.

kører koden

Start med at trække koden fra GitHub-depotet ind i din lokale maskine. Den fil, du vil udføre, er ShowHotSpots.py i hovedmappen. Ved første udførelse vil koden læse i de britiske trafikulykkedata fra 2013 til 2016 og klynge den. Resultaterne cachelagres derefter som en CSV-fil til efterfølgende kørsler.

du vil derefter blive præsenteret for to kort: den første genereres ved hjælp af de skyformede klynger, mens den anden bruger den konkave klyngealgoritme, der diskuteres her. Mens polygongenereringskoden udføres, kan du se, at der rapporteres om et par fejl. For at hjælpe med at forstå, hvorfor algoritmen ikke opretter et konkavt skrog, skriver koden klyngerne til CSV-filer til mappen data/out/failed/. Som sædvanlig kan du bruge KGI ‘ er til at importere disse filer som lag.

i det væsentlige fejler denne algoritme, når den ikke finder nok punkter til at “gå rundt” formen uden selvskærende. Dette betyder, at du skal være klar til enten at kassere disse klynger eller anvende en anden behandling på dem (konveks skrog eller sammenvoksede bobler).

Konkaveness

det er en indpakning. I denne artikel præsenterede jeg en metode til efterbehandling DBSCAN genererede geografiske klynger i konkave former. Denne metode kan give en bedre passende udvendig polygon til klyngerne sammenlignet med andre alternativer.

Tak fordi du læste og nyd at tinker med koden!

Krishna M., Lasek P. (2010) TI-DBSCAN: klyngedannelse med DBSCAN ved hjælp af trekanten ulighed. In: S. M., S. M., Ramanna S., Jensen R., Hu S. (eds) rå sæt og aktuelle tendenser inden for Computing. RSCTC 2010. Forelæsningsnotater i datalogi, bind 6086. Springer, Berlin, Heidelberg

Scikit-Lær: maskinlæring i Python, Pedregosa et al., JMLR 12, s. 2825-2830, 2011

Moreira, A. og Santos, M. Y., 2007, konkave skrog: en K-nærmeste nabo tilgang til beregning af regionen besat af et sæt punkter

Beregn afstand, leje og mere mellem Breddegrad/Længdegradspunkter

GitHub repository