Domainshapes maschinell bestimmen


#1

Ich fände einen Ansatz, der die Form algorithmisch bestimmt attraktiv.
Das ganze sieht wie eine überschaubare Optimierungsaufgabe auf.

Erster Schritt wäre wohl eine Bewertungsfunktion zu bestimmen. D.h. wann ist eine Aufteilung “gut”?
Das wäre auch ohne automatisches Shaping vielleicht eine lohnenswerte Diskussion :wink:


Tagesordnung 10.05.2017
[RFC] Domainshaping (Domain 01)
#2

Willst du in den Algorithmus nur Knotendaten werfen? Oder auch rudimentäre topographische Informationen? Wie sieht es mit Mesh-Links aus?

Wenn man das nur auf basis der knotenpositionen löst, besteht die Gefahr, dass dann ungewöhnliche Grenzen, z. B. quer durch ein Wohngebiet bekommt.

Wenn wir das algorithmisch bestimmen, würde ich aber auch dieses ganze Auswähl-Foo, sowie die drei trillionen Firmware-Varianten wegwerfen und das so machen, wie die NWler das machen: Mehr oder weniger “automatisch” die richtige Domäne/GWs auf den Knoten wählen.


#3

Alles was du fragst betrifft die Gütefunktion, ich habe zuerst gefragt :slight_smile:


#4
  • Anzahl Knoten
  • räumliche Nähe
    • meshlinks := Bonus (multiplikator)

Vielleicht kann man ja irgendwie auf das grundlegende Konzept der SVMs aufbauen, die haben ja auch zum Ziel (im n-dimensionalen Raum) “Punktwolken” möglichst optimal zu trennen.


#5

Vielleicht geht man das Problem auch anders herum an: Man baut Domänenkandidaten aus Landmarks: Flächen, die durch Bundesstraßen/Autobahnen, Flüsse, Administrative Grenzen (>= definierter Level) und Bahntrassen abgegrenzt werden (mehrere Gleise bzw. mehrere Spuren müssten natürlich gemerged werden, etc.) . Und darüber lässt man dann eine Bewertungsfunktion laufen, wie gut die für eine Domäne geeignet sind. Damit sprengt man vermutlich nicht so schnell die Komplexitätsklasse.

Also man hat quasi dann (n-eckige) Tiles. Benachbarte Tiles fügt man so lange zusammen, bis das Ergebnis gut ist.


#6

@kgbvax für das clustern scheint k-means ein probates Mittel zu sein. Das bekommt man durch scipy in python geschenkt. Für QGIS gibt es dort auch (mindestens) zwei Möglichkeiten: Attribute based clustering (dort habe ich xcoord und ycoord testweise mal als attribute rein geworfen), welches sich aber bei mir bei mehr als einem Attribut irgendwie auf die Nase gelegt hat, bzw. unerwartete Ausgaben produzierte. Sowie das Concave Hull Plugin, welches die Funktion “Shared Nearest Neighbor Clustering” mit bringt. Die allerdings dann nur auf Basis der Koordinaten clustern kann. Hier muss man allerdings recht viel mit dem “kernel parameter” k spielen.

Nun denn, dann sollten wir wieder zurück zu deiner anfänglichen Frage und klären, welche Features wir definieren wollen.

Wir haben ja knotenspezifische Features, die wir dann in den k-means werfen wollen. Aber wir haben ja auch Anforderungen an das Ergebnis, z. B. als Domänengröße. Diese können wir nutzen, um iterativ die Gewichte der einzelnen Features anzupassen, bis das Ergebnis optimal wird.


#7

Genau. :slight_smile:
Weiteres Constraint - zumindest im Endergebniss keine Überlappung.
Und auch am Ende: Grenzen entlang von Strassen um es benutzbar zu halten.

Gibt’s da Geojason auch nur für die Dom1?

QGIS brennt mir nämlich gerade die CPU weg.


#8

Nö. Aber mach es dir doch selbst. Polygon von Dom-01: https://github.com/FreiFunkMuenster/md-fw-dl/blob/master/shapes/domaene01_highres.geojson und dann “nach position extrahieren” oder so…

Edit: natürlich kann man filtern: https://karte.freifunk-muensterland.de/data/map_ffmsd01/nodes.geojson

Allerdings sind dort alle knoten mit der firmware für dom01 drin, nicht alle knoten eie laut koordinaten in dom01 gehören.


#9

Für die “Landkarte” verwende ich bisher DBSCAN zum Clustering. Zur Aufteilung in verschiedene Bereiche zwecks gleichmäßiger Verteilung ist ein dichtebasierter Ansatz aber wohl weniger geeignet. Hier eine Gegenüberstellung, falls von Interesse: http://kontext.fraunhofer.de/haenelt/kurs/Referate/Kromm_Breithaupt_DBScanKMeans_2016.pdf

Ich hätte an dieser Stelle noch die Idee, die Aufteilung in verschiedene, gleich große Bereiche über ein Voronoi-Diagramm zu erledigen. Ein passendes Verfahren müsste man™ sich aber noch überlegen.


#10

Ein Voronoi-Diagramm habe ich bei mir als einen eher nachgelagerten Schritt verwendet, da die Anforderung war aneinander grenzende Polygone zu bekommen, schieden Hüllen (concav oder convex) aus.

Mein Vorgehen:

  1. k-means mit recht kleinem cluster (k) Parameter -> ergebnis als attribut “class” an die punkte geschrieben
  2. Voronoi-Diagramm erstellen, um aus der Punktwolke aneinander grenzende Polygone zu erhalten (class attribut wurde auf die polygone übertragen)
  3. polygone mit gleicher class dissolved

Das ist mein bisheriges Ergebnis:

Die Anzahl der Knoten innerhalb eines Polygons/Klasse wird durch die entsprechende Zahl repräsentiert.

Mein nächster Schritt wäre jetzt benachbarte Polygone solange zusammenzufügen, bis die Anzahl der Knoten im gewünschten Bereich liegt.

Mit einem Blick auf Hiltrup wird aber klar, dass das zusammenfügen von benachbarten polygonen nur auf basis eines attributs (anzahl knoten) problematisch werden könnte.

Ich werde mir dennoch mal die dichtebasierenden Ansätze anschauen. Ich werde aber auch noch mal meine Unterlagen zur Computer Vision Vorlesung durchschauen, hier scheint es eine recht große Schnittmenge (außer halt die Verfahren für Rasterdaten) zu geben.

Edit:

Ein anderer Anssatz wäre direkt mit Polygonen zu starten: Man nimmt die Informationen über Mesh-Links hinzu und wirft dann über die daraus enstehende lokale Wolke eine Hülle.

Danach könnte man iterativ vorgehen:

  • Erstelle/Vergrößere Buffer
  • Füge überlappende Polygone zusammen
  • Berechne Anzahl an Knoten innerhalb
    • Liegt Anzahl Knoten im Zielbereich --> Entferne Polygon aus dem Prozess & speichere in separat als potentielle Domäne
    • Ist Anzahl Knoten > Zielbereich --> wähle größtes (nach Anzahl Knoten in Polygon) der betreffenden Polygone aus Schritt i-1 und entferne dieses

Anmerkung: knoten != punkt


#11

Ich habe jetzt mal den k-means von openCV genutzt, also in Python. Der ist sehr viel mehr konfigurierbar. So habe ich auch cv2.KMEANS_PP_CENTERS anstatt cv2.KMEANS_RANDOM_CENTERS verwendet. Außerdem ist das teil signifikant schneller als das Teil in QGIS. Die “veredelung”, also Voronoi, malen, zahlen habe ich dann wieder mit QGIS gemacht.

Ein erster Versuch mit #clusters = 100 habe ich dann auch gleich mal auf alle Knoten los gelassen:

Daraus habe ich dann Münster ausgeschnitten:

Und hier noch mal etwas mehr im Detail:

Imho ist das Ergebnis für den Anfang echt nicht schlecht. Und das nur auf Basis der Koordinaten als Features-Vektor.

Ich denke wir haben nun einen Punkt erreicht, an dem wir die prinzipielle Machbarkeit gezeigt haben. Wir sollten nun klären ob und wie wir so etwas nutzen wollen.

PS: Hier findet sich die Übersichtsseite von openCV bzgl. Machine Learning:

http://docs.opencv.org/3.0-beta/doc/py_tutorials/py_ml/py_table_of_contents_ml/py_table_of_contents_ml.html#py-table-of-content-ml

Dort ist unter Anderem die Verwendung des k-means beschrieben.

Edit: Eine andere Idee wäre noch die zu großen Cluster einfach noch mal durch den k-means zu schieben. :smiley:


#12

Endlich mal Informatik in der Bude! :slight_smile:


#13

Ein Tipp: Verwende eine Projektion zum Clustern und auch für die Voronoi-Diagramme, die in beiden Achsen die gleiche Skalierung verwendet (z. B. EPSG:3857).


#14

Das bisherige Problem war, dass bei einer zu kleinen Anzahl an Clustern die Cluster in den Städten viel zu groß (Anzahl Knoten) und bei einer zu großen Anzahl an Clustern die Cluster in weniger besiedelten Regionen viel zu klein (Anzahl Knoten) wurden.

Daher gehe ich jetzt rekursiv vor: Ich gebe zunächst eine eine moderate Anzahl an Clustern vor. Danach prüfe ich, ob es Cluster gibt, die einen vorgegebenen Schwellenwert überschreiten. Auf diese Cluster (also nicht mehr global) führe ich dann einen erneuten k-means Durchlauf durch mit kluster-anzahl := ceil(knoten-anzahl/schwellenwert). Dieses wird solange durchgeführt, bis alle Cluster den vorgegebenen Schwellenwert unterschreiten.

Das Ergebnis sieht dann schon mal besser aus:

PS: Ich habe mal alles außerhalb des RegBez Münster entfernt.

Hier noch mal “alles”:

Edit: Der kmeans von openCV gibt einen “compactness” wert zurück. Diesen könnte man ebenfalls als Entscheidungskriterien für weitere Iterationen heranziehen.

Außerdem sollte man den Features-Vektor um einen Wert erweitern, der vermeidet, dass sehr nahe Knoten unterschiedlichen Clustern zugeordnet werden.

PS: Innerhalb des Bezirksregierung-Münster Shapes wären das sogar nur 50 Domänen. :open_mouth:


#15

Auch ulkig: