Informatik 12/13 (G9)

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
====== Der k-Means-Algorithmus ======
===== Einführung: Unüberwachtes Lernen =====
{{ .:pasted:20260121-064234.png?500}}
30 Bürger/-innen, die in der Stadt Großschwabhausen arbeiten, wurden darüber befragt, wie weit ihre Arbeitsstätte von ihrem Wohnort entfernt ist und wie oft sie für diese Strecke das eigene Fahrzeug bzw. öffentliche Verkehrsmitteln (ÖPNV) nutzen. Die Antworten sind im Graph rechts dargestellt (je Person ein Datenpunkt).

  * a) Beschreiben Sie, in welche Gruppen (Bezeichnung, zugehörige Datenpunkte) man die Personen einteilen könnte. 
  * b) Diskutieren Sie, wie man das Wissen über diese Gruppen nutzen könnte.

<WRAP center round info 40%>
Die Aufgabe, mit der wir uns im folgenden befassen, besteht allgemein darin, 
  * die Punkte sinnvoll zu Clustern zu gruppieren und 
  * eine Zuordnungsvorschrift zu finden, mit der man ausgehend von den Koordinaten eines neuen Punktes den Cluster ermitteln kann, dem er zugeordnet wird.
Da es **keine gelabelten Trainingsdaten** gibt, spricht man von **unüberwachtem Lernen** (//unsupervised learning//).  \\ \\ 

Oft bestehen die Daten aus vielen tausend Datenpunkten im n-dimensionalen Raum mit n > 3, sodass es kaum möglich ist, die Cluster "von Hand" zu ermitteln. Ein Algorithmus, der diese Aufgabe aber meist gut erledigen kann, ist der **k-Means-Algorithmus**.

</WRAP>



===== Der k-Means-Algorithmus =====
Der k-Means-Algorithmus bekommt als **Eingabe** eine **Menge ungelabelter Datenpunkte**.
==== 1. Parameter k (Anzahl der Cluster) festlegen ====
Die Anzahl $k$ der Cluster, die der Algorithmus bilden soll, muss vor Beginn des Algorithmus festgelegt werden. In unserem Beispiel entscheiden wir uns für $k = 3$. \\ \\ 
Wie man die Anzahl der Cluster automatisiert festlegen kann, erfahren Sie etwas später in diesem Skript.

{{ .:pasted:20260118-190704.png?400}}
==== 2. Clusterzentren (zunächst) zufällig festlegen ====
Die Clusterzentren werden zunächst zufällig festgelegt. Im Beispiel fallen sie auf Orte, an denen bereits Datenpunkte liegen. Das ist aber für das Funktionieren des Algorithmus nicht notwendig.

<HTML>
<div style="clear: both">
</div>
</HTML>

==== 3. Datenpunkte den Clusterzentren zuordnen ====
{{.:pasted:20260118-191034.png?400 }}
{{ .:pasted:20260118-191134.png?400}}
Jeder Datenpunkt wird dem Cluster zugeordnet, zu dem er den kleinsten Abstand hat. In der rechten Abbildung ist die Zuordnung der Datenpunkte zu den Clusterzentren zu sehen.
Wir berechnen den Abstand zweier Punkte $A = (x_a, y_a)$ und $B = (x_b, y_b)$ mit der Ihnen bekannten euklidischen Metrik:
$$d(A, B) = \sqrt{((x_a - x_b)^2 + (y_a - y_b)^2)}$$
Es gibt auch andere Möglichkeiten, den Abstand zweier Punkte im ${\rm I\!R}^n$ zu definieren, i.d.R. kommt bei k-Means aber die euklidische Metrik zum Einsatz.
<WRAP center round tip 60%>
In der linken Abbildung sieht man gut die Raumbereiche, die den jeweiligen Clusterzentren zugeordnet sind. Überlegen Sie kurz:
  * Wie bestimmt man die Geraden, die die Raumbereiche trennen?
  * Wie sehen die Raumbereiche aus, wenn es sich um Punktmengen im dreidimensionalen Raum handelt?
</WRAP>


<HTML>
<div style="clear: both">
</div>
</HTML>


==== 4. Neue Lage der Clusterzentren berechnen ====
{{ .:pasted:20260118-192045.png?400}}
Jedes Clusterzentrum wird jetzt in den **Schwerpunkt** der ihm zugeordneten Datenpunkte verschoben. Dieser hat als Koordinaten $(x_{Zentrum},y_{Zentrum})$ den Mittelwert der Koordinaten der Datenpunkte $(x_i, y_i)$, also
$$x_{Zentrum} = \frac{1}{n} \sum_{i = 0}^{n} x_i$$
$$y_{Zentrum} = \frac{1}{n} \sum_{i = 0}^{n} y_i$$

==== Wiederholen bis Clusterzuordnung stabil ====
Man wiederholt jetzt die Schritte 3 und 4 solange, bis sich die Zuordnung der Datenpunkt zu den Clusterzentren nicht mehr ändert. In den folgenden Bildern sehen Sie die nächsten Schritte:
^Schritt^Bild^
|Clusterzuordnung |{{.:pasted:20260118-192502.png?300}}|
|Clusterzentren neu berechnen |{{.:pasted:20260118-192558.png?200}}|
|Clusterzuordnung |{{.:pasted:20260118-192640.png?200}}|
|Clusterzentren neu berechnen |{{.:pasted:20260118-192717.png?200}}|
|Clusterzuordnung |Keine Veränderung zur vorherigen Zuordnung => fertig!|

===== Online-Verfahren zum Ausprobieren =====
[[https://kex.fim.uni-passau.de/kaMin_Online/html/kaMin_Online.html|Auf dieser Seite können Sie den k-Means-Algorithmus selbst ausprobieren.]]

Auch die obigen Screenshots stammen von dieser Seite.

===== An die Arbeit: Wir implementieren den k-Means-Algorithmus in Java! =====
<HTML>

<div class="java-online" style="height: 70vh; width: 100%" data-java-online="{'withBottomPanel': true, 'id': 'kMeans1'}">

<script type="text/plain" title="k-Means.java">
KMeans k = new KMeans();
k.start(3);

class KMeans {

   Graph graph = new Graph();

   Point[] punkte = { 
      new Point(5, 95), new Point(3, 100), new Point(8, 85), new Point(2, 98), new Point(6, 90), new Point(4, 92), new Point(7, 88), new Point(3, 96), new Point(5, 94), new Point(9, 82), new Point(65, 5), new Point(45, 10), new Point(80, 2), new Point(55, 8), new Point(70, 0), new Point(50, 12), new Point(85, 5), new Point(60, 7), new Point(75, 3), new Point(58, 10), new Point(25, 55), new Point(35, 45), new Point(20, 65), new Point(30, 50), new Point(28, 48), new Point(32, 60), new Point(40, 40), new Point(22, 58), new Point(38, 52), new Point(27, 47)
   }; 

   Point[] zentren; 
   
   int[] zuordnungZuZentren = new int[punkte.length];

   KMeans() {
      for (var punkt : punkte) {
         graph.addPoint(punkt);
      }
      graph.autoScale();
   }

   void start(int anzahlZentren) {
      initialisiereZentren(anzahlZentren);

      boolean zuordnungHatSichGeändert = true;
      while (zuordnungHatSichGeändert) {
         zuordnungHatSichGeändert = ordnePunkteDenZentrenZu();
         verschiebeZentren();
      }

   }
   
   void verschiebeZentren() {
      for (int i = 0; i < zentren.length; i++) {
         double summeX = 0;
         double summeY = 0;
         double anzahlPunkte = 0;
         for (int j = 0; j < punkte.length; j++) {
            if(zuordnungZuZentren[j] == i) {
               summeX += punkte[j].x;
               summeY += punkte[j].y;
               anzahlPunkte++;
            }
         } 
         // TODO: anzahlPunkte könnte 0 sein!
         zentren[i].x = summeX / anzahlPunkte;
         zentren[i].y = summeY / anzahlPunkte;
         zentren[i].update();
      }
   }

   boolean ordnePunkteDenZentrenZu() {
      boolean zuordnungHatSichGeändert = false;
      for (int i = 0; i < punkte.length; i++) {
         Point point = punkte[i];
         double minimalerAbstand = point.abstandZu(zentren[0]);
         int zentrumsIndex = 0;
         for (int j = 1; j < zentren.length; j++) {
            double abstand = point.abstandZu(zentren[j]);
            if(abstand < minimalerAbstand) {
               zentrumsIndex = j;
               minimalerAbstand = abstand;
            }
         }
         if(zuordnungZuZentren[i] != zentrumsIndex) {
            zuordnungZuZentren[i] = zentrumsIndex;
            zuordnungHatSichGeändert = true;
         }
            point.setColorIndex(zentrumsIndex + 1);
      }

      return zuordnungHatSichGeändert;

   }

   void initialisiereZentren(int anzahlZentren) {
      zentren = new Point[anzahlZentren];
      HashSet<Integer> schonVergebeneIndices = new HashSet<>();
      for (int i = 0; i < anzahlZentren; i++) {
         int neuerPunktIndex = 0;
         do {
            neuerPunktIndex = Random.randint(0, punkte.length - 1);
         } while (schonVergebeneIndices.contains(neuerPunktIndex));

         schonVergebeneIndices.add(neuerPunktIndex);

         zentren[i] = punkte[neuerPunktIndex].clone();
         zentren[i].setPointShape(PointShape.box);
         zentren[i].setColorIndex(i + 1);
         zentren[i].setBorderColor(0xffffff);
      }
   }
}
</script>
<script type="text/plain" title="Graph.java">

class Graph {
   static int[] colors = { 0xffffff, 0xff0000, 0x00ff00, 0x0000ff, 0xffff00, 0xe100ff }; 
   ArrayList<Point> points = new ArrayList<>();

   double top = 0;
   double left = 0;
   double width = 800;
   double height = 600;

   double xMin = -1e4;
   double xMax = 1e4;
   double yMin = -1e4;
   double yMax = 1e4;

   void addPoint(Point point) {
      point.graph = this;
      point.update();
      points.add(point);
   }

   double getXScreen(double x) {
      return left + width / (xMax - xMin) * (x - xMin);
   }

   double getYScreen(double y) {
      return top + height - height / (yMax - yMin) * (y - yMin);
   }

   void autoScale() {
      if(points.size() > 0) {
         xMin = points.get(0).x;
         xMax = points.get(0).x;
         yMin = points.get(0).y;
         yMax = points.get(0).y;

         for (int i = 0; i < points.size(); i++) {
            Point point = points.get(i);
            if(point.x < xMin) xMin = point.x;
            if(point.x > xMax) xMax = point.x;
            if(point.y < yMin) yMin = point.y;
            if(point.y > yMax) yMax = point.y;
         }

         double dx = xMax - xMin;
         xMin -= dx * 0.05;
         xMax += dx * 0.05;

         double dy = yMax - yMin;
         yMin -= dy * 0.05;
         yMax += dy * 0.05;


         for (var point : points) {
            point.update();
         }
      }
   }


}



enum PointShape {
   circle, box
}

class Point {
   double x;
   double y;

   int colorIndex = 0;
   PointShape pointShape = PointShape.circle;

   FilledShape shape = null;
   Graph graph;

   Point(double x, double y) {
      this.x = x;
      this.y = y;
   }
   
   double abstandZu(Point p) {
      double dx = x - p.x;
      double dy = y - p.y;
      return Math.sqrt(dx * dx + dy * dy);
   }
   
   Point clone() {
      Point p = new Point(x, y);
      p.pointShape = pointShape;
      p.colorIndex = colorIndex;
      if(graph != null) {
         p.graph = graph;
         p.update();
      }
      return p;
   }

   public void setColorIndex(int colorIndex) {
      this.colorIndex = colorIndex;
      update();
   }

   public void setPointShape(PointShape pointShape) {
      if(shape != null) shape.destroy();
      this.pointShape = pointShape;
      switch(pointShape) {
         case circle : 
            shape = new Circle(0, 0, 8);
            break;
         case box : 
            shape = new Rectangle(-8, -9, 16, 16).rotate(45);
            break;
         default : 
      }
      shape.defineCenter(0, 0);
   }

   public void update() {
      if(shape == null) setPointShape(this.pointShape);

      shape.setFillColor(Graph.colors[colorIndex]);

      if(graph != null) {
         shape.moveTo(graph.getXScreen(x), graph.getYScreen(y));
      }

   }

   public void setBorderColor(int borderColor) {
      if(shape != null) shape.setBorderColor(borderColor);
   }

}
</script>
</div>
</HTML>

===== Aufgabe 1 =====
Bearbeiten Sie Buch S. 160/2

===== Manhattan-Metrik =====
Eine Alternative zur euklidischen Metrik ist die **Manhattan-Metrik** (auch "Manhattan-Distanz"), benannt nach dem Straßennetz von Manhattan. 
{{ .:pasted:20260121-161918.png?500 }}
Die Manhattan-Distanz zweier Punkte $A = (a_x, a_y)$ und $B = (b_x, b_y)$ ist definiert als
$$|a_x - b_x| + |a_y - b_y|$$

===== Notwendigkeit zur Normierung der Koordinaten =====
{{ .:pasted:20260123-082348.png?400}}
Im Beispiel oben sind beide Koordinaten (Pendelstrecke in km und ÖPNV-Anteil in %) ungefähr im Bereich von 1 bis 100 verteilt. Stellen Sie sich vor, eine der Koordinaten nähme nur Werte von 1 - 10 an, die andere Werte von 1 bis 100. Dann würde erstere in die Berechnung der euklidischen Distanz zweier Punkte deutlich weniger stark einfließen als letztere.

Es ist daher notwendig, die Koordinaten vor der Durchführung des k-Means-Algorithmus jeweils zu skalieren. Am einfachsten ermittelt man die kleinsten Koordinaten $x_{min}$ und $y_{min}$ sowie die größten Koordinaten $x_{max}$ und $y_{max}$ und berechnet dann die skalierten Koordinaten folgendermaßen:
$$x_{neu} = \frac{x - x_{min}}{x_{max} - x_{min}}$$
$$y_{neu} = \frac{y - y_{min}}{y_{max} - y_{min}}$$
Damit fallen dann alle Koordinaten ins Intervall $[0;\ 1]$, wobei die Werte 0 und 1 sowohl als x- als auch als y-Koordinate mindestens ein Mal vorkommen.

<WRAP center round tip 60%>
Der Graph rechts veranschaulicht die Herleitung des Terms zur Berechnung von $x_{neu}$:
  * Das Intervall $[x_{min}; x_{max}]$ wird auf das Intervall $[0;\ 1]$ abgebildet.
  * Am Dreieck kann die Steigung $\frac{1}{x_{max}-x_{min}}$ abgelesen werden.
  * Die Differenz $x - x_{min}$ bewirkt eine Verschiebung der Ursprungsgerade um $x_{min}$ nach rechts.
</WRAP>

===== Aufgabe 2 =====
  * a) Erweitern Sie das Programm oben so, dass die Koordinaten vor der Durchführung des k-Means-Algorithmus normiert werden.
  * b) Fügen Sie der Punktemenge im Programm noch 2 - 3 "Ausreißer" hinzu. Wie beeinflussen sie das Ergebnis des k-Means-Algorithmus?
  * c) Überlegen Sie sich einen Algorithmus, der vor Beginn des k-Means-Algorithmus "Ausreißer" identifizieren und entfernen kann. Fügen Sie auch diesen Algorithmus dem Programm oben hinzu und testen sie ihn mit den in b) ergänzten Ausreißern sowie mit neuen Ausreißern.


===== Automatische Ermittlung einer möglichst guten Clusteranzahl =====
Es gibt verschiedene Methoden zur automatischen Ermittlung einer möglichst guten Clusteranzahl. Eine davon soll im Folgenden vorgestellt werden:
<WRAP center round info 80%>
Zunächst braucht man ein Maß für die Güte der Einteilung einer Punktmenge in Cluster. Eine Möglichkeit besteht darin, die Abstände aller Punkte von ihrem Clusterzentrum zu berechnen und die Quadrate dieser Abstände zu addieren. 

Man führt den k-Means-Algorithmus für 2, 3, 4, ... Cluster durch und berechnet für jede Clusteranzahl dieses Gütemaß("Summe der Abstandsquadrate von den Clusterzentren"). Trägt man nun die Clusteranzahl nach rechte und das Gütemaß nach oben ab, so erkennt man in vielen Fällen ein "Knie" im Graphen oder zumindest eine Anzahl von Clustern, ab der das Maß kaum noch fällt. Diese Zahl von Clustern wird dann als die beste angesehen.
</WRAP>

===== Aufgabe 3 =====
Implementieren Sie das Verfahren zur automatischen Ermittlung der Clusteranzahl.

[[.aufgabe3loesung:start|Lösung]]