© Branko Jovanovic / 123RF.com

Im ersten Teil dieser Artikelserie ging es um die Navigation in einem Gebäude mithilfe verschiedener WLAN-Hotspots und Methoden des überwachten maschinellen Lernens. Diesmal untersuchen wir, was mit unüberwachtem Lernen möglich ist.

In unserem Beispielszenario sucht Maja nach Tom, der sich verlaufen hat. Zum Glück zeigt ihm sein Smartphone die Signalstärke von sieben Hotspots aus seiner Umgebung an. Maja wiederum verfügt über einen Datensatz aus acht Spalten: den Signalstärken der sieben WLAN-Hotspots, gemessen mit einem Handy, und den Ort der Messungen. Nach 500 Messungen an vier festen Orten stehen 2000 Einträge bereit. Maja weiß, dass sich Tom nur an einem dieser vier Orte befinden kann – aber an welchem?

Eine direkte Berechnung des Aufenthaltsorts von Tom (analytische Lösung) ist unmöglich. Das liegt vor allem an der Dämpfung: Jedes Hindernis schwächt das Signal und täuscht eine ortsabhängig variierende Entfernung vor. Außerdem kennt Maja die Koordinaten und die Leistung der Sender nicht. Damit lassen sich aus der von Tom gemessenen Signalstärke nicht direkt Entfernungen berechnen, die zusammen seinen Standort verraten würden. Stattdessen versucht es Maja mit maschinellem Lernen – in Teil 1 [1] mit überwachtem Lernen, diesmal mit Methoden des unüberwachten Lernens.

Unüberwachtes Lernen

Bislang dachte Maja, sie würde für jede Messung auch den Ort kennen. Was aber, wenn sie beim Notieren der Räume nachlässig war? Das unüberwachte Lernen sucht nach Aussagen, die sich widerspruchsfrei aus den Daten ableiten lassen. Im geschilderten Fall würde es ähnliche Messungen zusammenfassen und einen gemeinsamen Ursprung vermuten. Ob es sich dabei aber um die Küche oder das Wohnzimmer handelt, bleibt unbestimmt.

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
fn = "images/wifi_localization.txt"
#fn = "https://archive.ics.uci.edu/ml/machine-learning-databases/00422/wifi_localization.txt"
Xu = np.loadtxt(fn)[:,:-1]

Ähnlich wie in den Listings 1 und**3 aus dem ersten Teil landen die Daten in einem Array (Listing 1). Zur Unterscheidung trägt es den Namen »Xu« statt »X«. Die eckigen Klammern »[:,:-1]« löschen die Zielgröße in der letzten Spalte. Um die Daten miteinander zu vergleichen, greifen wir später auf den Pandas-Dataframe »df« des überwachten Lernens zurück.

Bei unseren Experimenten beschränken wir uns hier auf den k-Means-Klassifizierer. Der Buchstabe k bringt die Ähnlichkeit zum k-Nearest-Neighbour-Algorithmus zum Ausdruck. Dieser sucht die k nächsten Nachbarn, wobei k für die Anzahl steht. k-Means teilt die Daten in k-Klassen ein. Es optimiert die Zahl von k Schwerpunkten so, dass die Summe der quadratischen Abstände der Punkte zu ihrem jeweiligen Schwerpunkt minimal bleibt. Was etwas abstrakt klingt, ist dank Scikit-learn [2] in wenigen Zeilen programmiert (Listing 2).

from sklearn.cluster import KMeans
clusters = 4
kmeans = KMeans(n_clusters=clusters, init='k-means++', max_iter=300, n_init=10, random_state=0)
kmeans.fit(Xu)
y_pred = kmeans.predict(Xu)
clusterCenters = kmeans.cluster_centers_

Die erste Zeile in Listing 2 importiert den Klassifizierer, die dritte richtet die Hyperparameter ein. Die Anzahl der Cluster muss man dem Klassifizierer mitteilen; wir wählen zunächst »4«. Bei den anderen Parametern handelt es sich um Standardwerte. »k-means++« hilft der Software, gute Startwerte zu finden, die sie in »max_iter« Schritten optimiert. Sie unternimmt »n_init« Anläufe und wählt die beste Lösung aus. »random_state« startet den Pseudo-Zufallsgenerator an einer definierten Stelle. Deshalb liefert jede Wiederholung der Rechnung ein identisches Ergebnis.

Die Früchte der Arbeit liefert Zeile 5. Die trainierte Methode ordnet mittels »kmeans.predict(Xu)« die Messungen den Clustern zu, bei vier Clustern also eine der Zahlen 0, 1, 2 oder 3. Die sieben Koordinaten der Schwerpunkte der vier Cluster stehen in der Methodenvariablen »cluster_centers_«.

Listing 3 visualisiert das Ergebnis (Abbildung 1). Genaugenommen handelt es sich nur um eine Projektion des siebendimensionalen Eigenschaftsraums auf eine zweidimensionale Zeichenebene. Die Wahl der Spalten »0« und »4« in Zeile 1 ist nicht ganz zufällig: Sie enthalten die hochpriorisierten Eigenschaften, die beim überwachten Lernen gefunden wurden. Mit PCA [3] lernen wir später noch ein anderes, ebenfalls unüberwachtes Verfahren für die Auswahl kennen.

x1, x2 = 4, 0
colormap = np.array(['purple', 'green', 'blue', 'orange'])
plt.figure(figsize=(6,4), dpi=120)
plt.scatter(Xu[:,x1], Xu[:,x2], s= 10, c=colormap[y_pred])
plt.scatter(clusterCenters[:, x1], clusterCenters[:, x2], s=180, c='red', marker = 'X')
for i, p in enumerate(clusterCenters):
  plt.annotate(f'$\\bf{i}$', (p[x1]+1, p[x2]+3))
plt.show()

Abbildung 1: Die Visualisierung der vier Cluster, die k-Means findet.

Die Anweisung »plt.scatter« druckt alle Messwerte, wobei sie die Farben aus »colormap« auswählt (Zeile 4). Als Index für die Farbe dient das in Listing 2 gesetzte »y_pred«. Die Schwerpunkte markiert der zweite Scatter-Befehl in Zeile 5 als rote Kreuze.

Das unüberwachte Lernen teilt die Daten in Gruppen auf; die Zuordnung wählt es zufällig aus. Würde man in Listing 2 den Startwert des Zufallsgenerators »random_state« nicht fixieren, erhielten die Gruppen bei jedem Durchlauf unterschiedliche Ziffern – darauf kommen wir später noch zurück.

Verborgene Räume

Listing 4 liefert statistische Informationen über die Qualität der Zuordnung; einen typischen Output zeigt Listing*5. Die Trägheit (Inertia) sagt etwas über die Kompaktheit eines Clusters aus; die Punkte sollten sich möglichst dicht um den Schwerpunkt des Clusters scharen. Je kleiner bei gleicher Anzahl von Punkten der Wert, desto besser. Der Umriss (Silhouette) berücksichtigt auch den Abstand zu den Nachbar-Clustern. Je weiter sie entfernt liegen, desto klarer ist die Abgrenzung eines Clusters. Der Wert liegt zwischen 1 (optimal) und -1 (möglicherweise falsch gesetzter Clusterschwerpunkt). Beide Größen beschreiben die Tendenz im Vergleich mit verschiedenen Clustergrößen bei identischen Ausgangsdaten.

from sklearn.metrics import silhouette_score
print(f'Input data shape: {Xu.shape}')
print(f'Inertia:  {kmeans.inertia_:3.1f}')
print(f'Silhouette: {silhouette_score(X, kmeans.labels_)}')
print(f'New labels: {np.unique(kmeans.labels_)}')
clusterCenters = kmeans.cluster_centers_
print(f'Center of gravity: {clusterCenters}' )

Input data shape: (2000, 7)
Inertia: 246771.6
Silhouette: 0.41023382751730914
New labels: [0 1 2 3]
Center of gravity: [[-35.43058824 ...]

Listing 6 berechnet Trägheiten für verschiedene Cluster, Abbildung 2 plottet die Werte. Optimal ist eine kleine Trägheit bei möglichst kleiner Clustergröße. Die Ellenbogenmethode sucht den Knick (Ellenbogen), an dem der steile Abfall der Trägheit in eine flache Steigung übergeht. Mit Wohlwollen liegt dieser Knick bei einer Clusterzahl von 4 oder 5. Ähnliches erledigt das Listing 7; Abbildung 3 zeigt das Resultat. Die besten Werte liegen auch hier bei 4 und 5.

wcss = []
for i in range(2, 11):
  kmeans = KMeans(n_clusters=i, init='k-means++', max_iter=300, n_init=10, random_state=0)
  kmeans.fit(Xu)
  wcss.append(kmeans.inertia_)
plt.plot(range(2, 11), wcss)
plt.title('Elbow Method')
plt.xlabel('Number of clusters')
plt.ylabel('WCSS')
plt.show()

Abbildung 2: Elbow-Methode zur Suche der optimalen Clustergröße.

from sklearn.metrics import silhouette_score
kmeansk = [KMeans(n_clusters=k, random_state=2).fit(Xu) for k in range(1, 10)]
inertias = [model.inertia_ for model in kmeansk]
silhouette_scores = [silhouette_score(Xu, model.labels_)  for model in kmeansk[1:]]
plt.figure(figsize=(4,3), dpi=120)
plt.plot(range(2, 10), silhouette_scores, "bo-")
plt.xlabel("Number of clusters")
plt.ylabel("Silhouette score", fontsize=12)
plt.show()

Abbildung 3: Silhouette-Methode zur Suche der optimalen Clustergröße.

In Abbildung 4 erhält jede Clustergruppe von k=3 bis k=8 ein eigenes Teildiagramm. Die Mittelwerte kennzeichnet eine senkrechte rote Linie. Darüber hinaus erscheint der Silhouette-Wert jedes einzelnen Datensatzes als horizontale Linie, der Größe nach sortiert. Je spitzer das rechte Ende aussieht, desto größer ist die Variation der Werte und desto uneinheitlicher das Cluster.

Abbildung 4: Die Silhouette-Werte der einzelnen Datensätze, nach Größe sortiert.

Bei fünf Clustern liegen die Maximalwerte auf einem einheitlichen Niveau bei fast 0,6. Der zweite schmale Balken lässt vermuten, dass die Daten neben den vier großen Clustern einen kleinen enthalten. Erweitert man in Listing 2 die Zahl der Cluster auf fünf, also »clusters = 5«, identifiziert Kmeans die Punktmenge am oberen Bildrand von Abbildung 1 als eigene Gruppe.

Das unüberwachte Lernen findet Zusammenhänge, die beim überwachten Lernen verborgen geblieben wären. Vieles deutet darauf hin, dass die Daten nicht in vier verschiedenen Räumen aufgenommen wurden, sondern in fünf.

Datenbereinigung

Gibt es einen eindeutigen Zusammenhang zwischen den Eigenschaften und der Zielgröße, sind die Daten redundant. Das unüberwachte Lernen findet heraus, ob die Redundanz gebrochen wird, beispielsweise durch einen Schreibfehler bei der Aufzeichnung der Daten.

Die erste Zeile in Listing 8 überführt die Eingangsdaten in einen Pandas-Dataframe, die zweite ordnet die Daten einem der vier Cluster zu. Die anonymen Werte 0 bis 3 entsprechen den Räumen, die wir beim überwachten Lernen kennengelernt haben – nur welchen?

dfu = pd.DataFrame(Xu, columns = [0, 1, 2, 3, 4, 5, 6])
dfu['Target'] = kmeans.predict(Xu)
kList = classifier.predict(clusterCenters)
transD = {i: el for i, el in enumerate(kList)}
dfu['Target'] = dfu['Target'].map(transD)

Die dritte Zeile aus Listing 8 transformiert die vier k-Means-Clusterzentren mit dem im ersten Teil trainierten Random-Forest-Klassifizierer »classifier« zurück zu den Zielwerten des überwachten Lernens, den Bezeichnern für die Räume. Zeile 4 bereitet ein Dictionary für die Übersetzung vor (»{0: “Raum_x”, 2: “Raum_y” …}«), das mit »map« in der letzten Zeile die Zahlen durch Raumnamen ersetzt.

Jetzt kann Maja die Werte vergleichen: Stimmt die Zuordnung der Räume aus den Ausgangsdaten mit den Clustern überein, die k-Means gefunden hat? Dazu erweitern wir in Listing 9 das Dataframe-Objekt der Ausgangsdaten um eine zusätzliche Spalte »Targetu«. Das neue Dataframe-Objekt »dfgroup« übernimmt nur die Werte, die sich in den Target-Spalten unterscheiden. Der Befehl aus der letzten Zeile zählt die Abweichungen.

dfDu = df.copy()
dfDu['Targetu']= dfu['Target']
dfDu[dfDu['Target'] != dfDu ['Targetu']].iloc[:,-2:]
dfgroup = dfDu[dfDu['Target'] != dfDu ['Targetu']].iloc[:,-2:]
dfgroup.groupby(['Target', 'Targetu'])['Targetu'].count()

Den Output sehen Sie im Listing 10. k-Means erkennt in 75 Fällen, dass die Diele besser ins Wohnzimmer passt, vier Mal passiert das bei der Küche. Wir sahen bereits beim überwachten Lernen, dass die Diele acht Mal als Wohnzimmer interpretiert wurde.

Target      Targetu
Diele       Wohnzimmer    75
Küche       Wohnzimmer     4
Terrasse    Küche          2
            Wohnzimmer     2
Wohnzimmer  Küche          2
            Terrasse       6

Weitere Vorschläge, die Daten zu bereinigen, seien hier nur angedeutet. Fehler bei den Zuordnungen treten im Beispiel nur bei benachbarten Positionen auf. Die Unterscheidung zwischen Diele und Wohnzimmer fällt besonders schwer, im geringen Maße auch die zwischen Wohnzimmer und Terrasse. Wenig deutet auf Flüchtigkeitsfehler hin, also völlig falsch zugeordnete Räume.

Im weiteren Verlauf betrachtet man die Entscheidungsstatistik des überwachten Lernens und entfernt die unklaren Werte; der Klassifizierer lernt dann besser. Für die Auswertung definiert man einen Schwellwert, wodurch weitere Kategorien entstehen. Die Daten werden dann beispielsweise als “vermutlich Wohnzimmer oder Diele” klassifiziert, statt eine vermeintlich eindeutige, tatsächlich aber unsichere Aussage zu treffen.

Dimensionsreduktion

Zweidimensionale Diagramme zeigen die Abhängigkeit von zwei Parametern, drei Parameter spannen einen dreidimensionalen Raum auf. Die vierte Dimension wird häufig durch einen Zeitstempel auf fortlaufenden Diagrammen veranschaulicht. Hier haben wir es mit sieben Eigenschaftswerten zu tun. Um dennoch die Abhängigkeit zu einer Zielgröße darstellen zu können, griffen wir oben zwei Eigenschaftswerte heraus.

Das geschah mit Bedacht: Aus dem überwachten Lernen kennen wir die Eigenschaften mit der höchsten Priorisierung. Die Hauptkomponentenanalyse (engl. Principal Component Analysis, PCA) verdichtet die Informationen der Eigenschaften und reduziert die Dimensionen ohne Kenntnis der Zielwerte. Es handelt sich um ein mächtiges Verfahren, das auch Ausreißer aufspürt. Wir beschränken uns auf wenige Anwendungen.

Listing 11 fällt weitgehend selbsterklärend aus. Nach dem Import der PCA-Bibliothek reduziert der Code die Zahl der Eigenschaften, in diesem Fall von sieben auf sieben – damit ist zunächst nichts gewonnen. Die Methode gibt jedoch das Attribut »explained_variance_ratio_« zurück, die Funktion »cumsum« die kumulative Summe. Aus Abbildung 5 lässt sich ablesen, dass bereits eine einzelne Eigenschaft 65 Prozent der Ergebnisse richtig wiedergibt, zwei sogar 85 Prozent.

from sklearn.decomposition import PCA
pca_7 = PCA(n_components=7)
pca_7.fit(Xu)
x = list(range(1,8))
plt.grid()
plt.plot(x, np.cumsum(pca_7.explained_variance_ratio_ * 100))
plt.xlabel('Number of components')
plt.ylabel('Explained variance')
plt.show()

Abbildung 5: Die Bedeutung der Eigenschaften.

Mit »clusters = 4«, also vier Clustern, generiert Listing 12 in Abbildung 5 eine Clusterverteilung, die jener aus Abbildung 1 ähnelt, ohne Kenntnis der priorisierten Eigenschaften. Die Achsen haben ihre alten Eigenschaften verloren. Aus sieben Signalstärken entstehen in diesem Fall zwei neue Skalen mit neuen Metriken. Die leicht verzerrten Punktwolken sind spiegelverkehrt angeordnet.

from scipy.spatial import Voronoi, voronoi_plot_2d
from matplotlib import cm
x1, x2 = 1, 0
# clusters = 4
clusters = 16
Xur = pca_2_reduced
kmeansp = KMeans(n_clusters=clusters, init='k-means++', max_iter=300, n_init=10, random_state=0)
kmeansp.fit(Xur)
y_pred = kmeansp.predict(Xur)
ccp = kmeansp.cluster_centers_[:,[x1, x2]]
fig, ax1 = plt.subplots(figsize=(4,5), dpi=120)
vor = Voronoi(ccp)
voronoi_plot_2d(vor, ax = ax1, line_width = 1)
plt.scatter(Xur[:,x1], Xur[:,x2], s= 3, c=y_pred, cmap = plt.get_cmap('viridis'))
plt.scatter(ccp[:, 0], ccp[:, 1], s=150, c='red', marker = 'X')
for i, p in enumerate(ccp):
  plt.annotate(f'$\\bf{i}$', (p[0]+1, p[1]+2))

Abbildung 6: Voronoi-Plot mit vier Clustern.

Während Entscheidungsbäume keine Metriken erfordern, vergleichen k-Means und PCA Abstände zwischen den Datenpunkten. Üblicherweise hebt ein Vorprozessieren die Skalen auf ein vergleichbares Niveau. Der Fehler durch Unterlassung bleibt an dieser Stelle relativ klein, da die Signalstärken aller Attribute eine ähnliche Größe aufweisen.

Dass die Vorüberlegungen zum Abschätzen der Zahl der Cluster eine wichtige Rolle spielen, veranschaulicht Abbildung 7. Das Ändern nur einer Variablen, »clusters = 18«, zeichnet ein ganz neues Bild. Wegen der Voronoi-Linien [4] und der Einfärbungen sieht das Diagramm recht überzeugend aus, hat aber mit unserer Fragestellung wenig zu tun.

Abbildung 7: Voronoi-Plot mit 18 Clustern.

Dreidimensionale Voronoi-Muster formen beispielsweise sich berührende Seifenblasen oder polykristalline Metallgefüge (Abbildung 8) – alles Fragen, die wir an dieser Stelle nicht vertiefen können.

Abbildung 8: Zinkkristallite einer Korrosionsschutzschicht.

Künstliche Intelligenz

Wenn Bequemlichkeit ein Ausdruck für Intelligenz ist, gehören die hier gezeigten Verfahren in diese Kategorie. Ein Beispiel bietet das automatische Zählen von Euro-Münzen. Entweder bestimmt man den Durchmesser und das Gewicht und schaut in Tabellen nach, welchen Münzwert es zuzuordnen gilt – oder man lässt KI die Arbeit übernehmen.

Die Münzen fallen zu Boden, wobei sie zunächst einen Luftstrom passieren und anschließend ein Magnetfeld. Man misst dabei die Ablenkung und Lichtreflexion in beliebigen Einheiten. Halbüberwachtes Lernen ordnet jeder Klasse einen Münzwert zu. Bei Ausreißern – etwa Münzen, die besonders weit fliegen – handelt es sich vermutlich um beschädigte Exemplare oder um Fremdwährung. Die Handarbeit des präzisen, zehntelmillimetergenauen Ausmessens entfällt. Eine analytische Lösung wäre bei diesem Versuchsaufbau auch nicht möglich.

Die hier besprochenen Methoden zählen zu den Verfahren der schwachen künstlichen Intelligenz. Bislang gibt es noch keine Ansätze für eine starke künstliche Intelligenz, also für ein System, das über sich selbst reflektiert.

Fazit

Ein Datenpool mit 2000 Datensätzen, jeweils sieben Eigenschaften und einer Zielgröße bildet den roten Faden dieses Artikels. Klassische Verfahren der künstlichen Intelligenz werten ihn aus.

Der Klassifizierer Random Forest als Muster für überwachtes Lernen aus Teil 1 dieses Artikels ordnet neue Daten in bekannte Kategorien ein. k-Means als Beispiel für unüberwachtes Lernen sieht sich Daten ohne Zielgröße an, findet innere Zusammenhänge und bewertet die Qualität der Daten. Gemeinsam schlüsseln sie nur teilweise mit Zielgrößen versehene Datensätze durch halbüberwachtes Lernen auf.

Die Scikit-learn-Bibliotheken in Python erlauben einen schnellen Einstieg in die Programmierung von Maschinenlernverfahren. Damit bleibt den Anwendern mehr Zeit, die Randbedingungen zu untersuchen und die Abhängigkeiten der Ergebnisse zu verstehen (jcb/jlu).