Punktgenau

Data Analytics in der Praxis – Teil 3: Clusteranalyse
Keine Kommentare

In den vergangenen beiden Artikeln der Serie haben wir uns mit der Regression und Klassifikation zwei Verfahren des überwachten Lernens angeschaut. Beide basieren darauf, dass es eine möglichst große Anzahl an Daten gibt, für die das Ergebnis bereits feststeht. Im dritten Teil der Serie beschäftigen wir uns dagegen mit einem Verfahren des unüberwachten Lernens, der Clusteranalyse.

Generell unterscheiden sich Verfahren des überwachten und des unüberwachten Lernens dadurch, dass beim überwachten Lernen ein Modell so angepasst wird, dass es bereits bekannte Ergebnisse möglichst gut auf Basis des Inputs voraussagt. Im Gegensatz dazu wird beim unüberwachten Lernen auf Basis eines Modells und seiner Parametrierung direkt ein Ergebnis erzeugt, ohne dass Wissen über bekannte Ergebnisse vorhanden ist.

Artikelserie

Bei der Clusteranalyse wird eine Menge an Eingabedaten in unterschiedliche Klassen eingeteilt. Das Ziel der Clusteranalyse ist es somit, die Daten anhand ihrer Ähnlichkeit zu gruppieren. Ebenso kann die Analyse aber auch dazu dienen, für eine fest vorgegebene Anzahl an Clustern die Positionen der Clusterzentren zu bestimmen. Um diese abstrakten Beispiele mit Leben zu füllen, wollen wir sie direkt an echten Daten nachvollziehen. Dazu beschäftigen wir uns in diesem Artikel mit Tracking-Daten aus dem Basketball, genauer der NBA. Unser Ziel ist es, zu analysieren, von welcher Stelle aus dem Spielfeld heraus die Spieler besonders gut punkten. Wir möchten außerdem versuchen, ohne weitere Informationen die Zwei- von den Dreipunktewürfen zu unterscheiden.

Wie üblich finden Sie die Skripte zur Auswertung in Kombination mit den verwendeten Daten auf unserer Homepage.

Der Datensatz

Seit 2014 gibt es über das Stats-API der NBA Daten über die präzise Position jedes Wurfversuchs aller Spieler. Die meisten dieser Daten stehen zur freien Verfügung und können für detaillierte Analysen einzelner Teams oder Spieler genutzt werden. Für die Clusteranalyse rufen wir die Daten der Top-3-NBAWerfer der Saison 2016/2017 unter Verwendung des Python-Requests-Moduls ab und führen sie direkt in einem Pandas-Dataframe zusammen (Listing 1).

import pandas as pd
import requests as r
players = {201566: 'Russell Westbrook', 201935:'James Harden', 202738:'Isaiah Thomas'}
shots_df = pd.DataFrame()
for player_id, _ in players.items():
  # non default request parameters
  req_params = { 'ContextMeasure': 'FGA', 'LeagueID': '00',
    'PlayerID': player_id, 'Season': '2016-17’, 'SeasonType': 'Regular Season' (...) }
  res = r.get('http://stats.nba.com/stats/shotchartdetail', params=req_params, headers=headers)
  res_json = res.json()
  # column names
  rows = res_json['resultSets'][0]['headers']
  # row content
  shots_data = res_json['resultSets'][0]['rowSet']
  shots_df = pd.concat([shots_df, pd.DataFrame(shots_data, columns=rows)], ignore_index=True)

Im resultierenden Datensatz (shots_df) ist jede Zeile ein Wurfversuch. Die Position (‚LOC_X‚, ‚LOC_Y’) des Wurfversuchs ist in 10*Fuß, relativ zum Korbmittelpunkt (0,0), angegeben. Neben der Position beinhaltet der Datensatz mit dem ‚SHOT_TYPE‚ die wichtige Information, ob es sich bei einem Wurf um einen ‚Missed Shot‚ oder einen ‚Made Shot‚ handelt. Darüber hinaus beinhaltet der Datensatz Informationen zur Art des Wurfs, zum Spielzeitpunkt, dem Abstand des Werfers usw.

Zeichnen des Felds

Um eine Grundlage für die visuelle Inspektion der Daten zu schaffen, zeichnen wir uns im ersten Schritt ein Basketballfeld.

Genau wie in den vergangenen Teilen verwenden wir zum Plotten Matplotlib. Die Einheit der Positionsdaten ist 10*Fuß, entsprechend müssen die Feldmarkierungen der Grafik mit dem Faktor 10 multipliziert werden. Die Feldmarkierungen können direkt mit den von Matplotlib zur Verfügung gestellten Patches gezeichnet werden. An dieser Stelle ist aus Platzgründen nur ein kurzes Beispiel aus der vollständigen Zeichnung gegeben (Listing 2).

# OUTER LINES
ax.add_patch( mpl.patches.Rectangle([-250, -47.5], 500, 470, **opts) )
# BASKETBALL HOOP
ax.add_patch( mpl.patches.Circle([0, 0], radius=7.5, **opts) )
# THREE-POINT LINE (RIGHT)
ax.add_line( mpl.lines.Line2D([220, 220], [-47.5, 92.5], **lopts) )
# THREE-POINT ARC
ang1 = np.rad2deg(np.tan(92.5/239))
ax.add_patch( mpl.patches.Arc([0, 0], 2*239, 2*239, theta1=ang1, theta2=180-ang1, **opts) )

Auf der Basis des gezeichneten Felds ist es einfach möglich, alle erfolgreichen Würfe der Spieler gut nachvollziehbar zu visualisieren. Hierzu wird die Zeichnung des Felds als Hilfsfunktion benutzt, die eine neue Grafik (als Figure-Objekt) mit einer Matrix von Basketballfeldern erzeugt. In die einzelnen Felder kann anschließend gezielt gezeichnet werden. So können wir uns erst einmal die erfolgreichen Würfe (shots_df.EVENT_TYPE==’Made Shot’) für alle Spieler visualisieren, genauso wie die erfolgreichen Würfe der einzelnen Spieler (shots_df.PLAYER_ID == pid) (Listing 3, Abb. 1).

axs = court.draw_court_figure(1, 4)
st = axs[0,0].get_figure().suptitle('Made Shots')
shots_df[shots_df.EVENT_TYPE=='Made Shot'].plot.scatter(x='LOC_X', y='LOC_Y', title='All Players', c='#00FF0088', ax=axs[0, 0])
for (pid, name), ax in zip(players.items(), axs[0, 1:]):
  shots_df[(shots_df.PLAYER_ID == pid) & (shots_df.EVENT_TYPE=='Made Shot')].plot.scatter(x='LOC_X', y='LOC_Y', title=name,color='#00FF0088', ax=ax)

Abb. 1: Erfolgreiche Würfe

Eine erste Erkenntnis der Visualisierung sind die Ausreißer in den Wurfpositionen: die einzelnen erfolgreichen Würfe weit hinter der 3-Punkte-Linie. Da sowohl die meisten Clusteralgorithmen als auch die meisten Machine-Learning-Algorithmen nicht gut mit Ausreißern umgehen können, möchten wir sie für unsere ersten Clustering-Versuche herausfiltern.

Ein gemeinsames Merkmal der Ausreißer ist der große Abstand zum Korb. Entsprechend könnte die Distanz der Punkte ein gutes Indiz für die Ausreißerfilterung bieten. Dies können wir schnell bewerten, indem wir die Punkte als Histogramm der Entfernungen plotten. Die Distanz müssen wir hierfür nicht selbst berechnen, weil sie bereits im Datensatz als ‚SHOT_DISTANCE‚ enthalten ist (Abb. 2):

shots_df[shots_df.EVENT_TYPE=='Made Shot']['SHOT_DISTANCE'].plot.hist(bins=100, title='All player shot distances')
Abb. 2: Histogramm der Distanzen aller erfolgreichen Würfe

Abb. 2: Histogramm der Distanzen aller erfolgreichen Würfe

Das Histogramm zeigt sehr schön, dass die Spieler nach Möglichkeit nicht mit mehr Abstand als 30 Fuß (ca. 9,2 m) zum Korb werfen. Somit können wir hier die Grenze für unsere Ausreißerfilterung anlegen. Und damit kommen wir zur Anwendung unserer ersten Clusteralgorithmen: K-Means und DBSCAN.

K-Means

K-Means ist der verbreitetste Clusteralgorithmus. Er wird mit einer vorgegebenen Anzahl an zu bestimmenden Clustern gestartet. Daraufhin werden ebenso viele Punkte aus den Daten zufällig als Clusterzentren ausgewählt. Nun werden alle übrigen Punkte dem jeweils nächsten Clusterzentrum zugeordnet. Diese Zuordnung bildet die Grundlage, um die Clusterzentren neu zu bestimmen, sodass sie die Summe aller quadratischen Abweichungen minimieren. Dadurch ergibt sich eine neue Zuordnung der Datenpunkte zu den Clusterzentren.

Beide Schritte werden so lange wiederholt, bis die Clusterzentren sich nicht mehr verschieben. Es gibt zahlreiche Erweiterungen und Abwandlungen von K-Means, die z. B. die initialen Clusterzentren gleichverteilt wählen, oder die Manhattan- statt der Euklidischen Distanz für die Bestimmung der Clusterzentren verwenden.

DBSCAN

DBSCAN ist ein dichtebasierter Clusteralgorithmus, der einen vorgegebenen Maximalabstand zwischen zwei Datenpunkten und eine Mindestanzahl von Punkten pro Cluster verwendet, um die Zuordnung der Datenpunkte zu verschiedenen Clustern zu bestimmen. Der Algorithmus bestimmt die Cluster iterativ, indem er an einem beliebigen Punkt startet und von dort alle verbundenen Punkte mit einem Abstand kleiner dem Maximalabstand bestimmt. Sind dies weniger als die Mindestanzahl, wird der Punkt als „Rauschen“ markiert. Andernfalls sucht der Algorithmus alle Punkte nach weiteren verbundenen Punkten. Sind alle Punkte einem Cluster zugeordnet oder als Rauschen markiert, endet der Algorithmus und gibt die Clusterzuordnung zurück, woraus sich wiederum die Anzahl an unterschiedlichen Clustern bestimmen lässt.

Analyse des Wurfverhaltens

Für die Clusterung setzen wir Scikit-Learn ein, die bekannte Python-Bibliothek für Machine Learning. Wir denieren hierzu eine Funktion, die ein K-Means-Objekt erzeugt, das im Aufruf fit_predict(X) für jedes Eingabedatum eine Clusterzuordnung zurückgibt. Die Zuordnung zeichnen wir als Scatterplot in das übergebene Axes-Objekt, wobei jedes Cluster einer Farbe entspricht. Der Aufruf der Funktion erfolgt mit den gleichen Datenfilterungen wie im obigen Beispiel, wobei jeweils noch die Anzahl der zu bestimmenden Cluster übergeben wird (Listing 4).

from sklearn import cluster

def calc_plot_cluster(df, num_cluster, ax, name):
  kmeans = cluster.KMeans(init='k-means++', n_clusters=num_cluster)
  X = df[['LOC_X', 'LOC_Y']].values
  y_pred = kmeans.fit_predict(X)
  ax.scatter(X[:, 0], X[:, 1], c=y_pred)

axs = court.draw_court_figure(rows=4, cols=4)
for i, nc in enumerate(range(2,6)):
  calc_plot_cluster(shots_df[(shots_df.EVENT_TYPE == 'Made Shot')  & (shots_df.SHOT_DISTANCE <= 30)], nc, axs[i, 0], 'All Player')
  for j, (pid, name) in enumerate(players.items()):
    calc_plot_cluster(shots_df[(shots_df.PLAYER_ID == pid) & (shots_df.EVENT_TYPE == 'Made Shot')  & (shots_df.SHOT_DISTANCE <= 30)], nc, axs[i, j+1], name)

In der gleichen Art kann auch die Clusterunterteilung von DBSCAN berechnet werden. Die Umsetzung findet sich aus Platzgründen im Quellcode zum Artikel.

Unser erstes Ziel ist es, zu schauen, wie K-Means die Daten in Cluster einteilt, und ob uns die Einteilung bei der Bewertung der Wurfpräferenzen einzelner Spieler hilft. Dazu verwenden wir K-Means, um nach 2 – 5 Clustern zu suchen, und DBSCAN, um alle Cluster mit einem Punktabstand von maximal 1,5 – 3 Fuß (0,45m – 0,9m) mit mindestens drei Punkten zu suchen (Abb. 3 und 4). Für K-Means wurde die Initialisierungsvariante K-Means++ verwendet, die auf die initialen Clusterzentren die Clusterzentren geometrisch gleichverteilt.

Abb. 3: K-Means-Clusterung der Wurfdaten

Abb. 3: K-Means-Clusterung der Wurfdaten

Abb. 4: DBSCAN-Clusterung der Wurfdaten

Abb. 4: DBSCAN-Clusterung der Wurfdaten

Die Clusterzuordnungen zeigen, dass K-Means mit zwei Clustern keine sinnvollen Rückschlüsse zulässt, da die Cluster eher zufällig durch die Datenpunkte gezogen sind. Mit zunehmender Clusterzahl können allerdings immer besser geometrisch zusammenhängende Feldbereiche unterschieden werden, die je nach Spieler stärker oder schwächer ausgeprägt sind. Die Farben selbst werden durch den K-Means-Algorithmus zufällig zugeordnet und haben keine besondere Bedeutung. Sie dienen uns nur zur Unterscheidung der Cluster. Die Unterteilung für alle Spieler bildet eine gute Referenz, weil sie schon nah an eine Gleichverteilung der Wurfpunkte heranreicht. Vor allem für die Unterteilung in vier Cluster ergibt sich eine gute Indikation, welche Angriffsrichtung vom Spieler bevorzugt (Isaiah Thomas rechts) wird und wie stark ausgeprägt die Angriffe über das Zentrum nah am Korb sind (Isaiah Thomas, James Harden).

Im Gegensatz zum K-Means-Algorithmus zeigt sich beim DBSCAN ein deutlich anderes Bild. Die Gruppierung nach zusammenhängenden Punkten und die Hervorhebung der Ausreißer in Lila führt dazu, dass wir mit der richtigen Parametrierung viel besser erkennen können, aus welchen Bereichen ein Spieler besonders erfolgreich war. Für Russel Westbrook kann bei einer maximalen Punktdistanz von 2,5 Fuß (0,75m) gut erkannt werden, dass im Innenbereich fast jede Position zum Erfolg geführt hat, während es für die anderen Spieler deutlich mehr Lücken zwischen den erfolgreichen Positionen gibt.

Unterscheidung der Punktezonen

In der Praxis wird oft versucht, durch eine Clusteranalyse eine vermutete Relation in den Eingabedaten auszudrücken. Allgemein wäre das z. B. die Vermutung, dass die Hunde einer Hunderasse Ähnlichkeit in Gewicht, Größe und Haarlänge haben. Würden wir uns also einen Datensatz mit diesen drei Messwerten für verschiedene Hunde anschauen, wäre unsere Vermutung, dass man mit geeigneter Clusterbildung die darin enthaltenen Hunderassen voneinander trennen kann.

Um dieses Beispiel auf unseren NBA-Datensatz zu übertragen, müssen wir uns vorstellen, die Daten nur mit dem Wissen auszuwerten, dass man beim Basketball von unterschiedlichen Positionen Punkte erzielen kann. Darüber hinaus haben wir, zusätzlich zu unserem Datensatz, die Information, wie viele Punkte durch unsere Spieler in einem Spiel erzielt wurden. Ebenso haben wir schnell festgestellt, dass die Anzahl der Würfe nicht gleich der Anzahl an Punkten ist. Darum fragen wir uns jetzt auf Basis der Auswertung, wie die Bepunktung aussehen könnte.

Interessanterweise können wir als Mensch visuell auch ohne die eingezeichneten Linien alleine anhand der Daten eine Unterscheidung treffen, weil wir im Plot sehen, dass die Spieler sehr selten aus den Randbereichen der 2-Punkte-Zone werfen. Somit ergibt sich eine Lücke zum 3-Punkte-Bereich. Würden wir das Spiel kennen, wäre das für uns natürlich einfach erklärbar, weil die Spieler lieber einen Schritt zurückgehen und einen 3-Punkte-Wurf versuchen, als am Rande der 2-Punkte-Zone einen Korb zu werfen.

Anhand der Visualisierung sehen wir aber auch, dass eine direkte Unterscheidung zwischen den Würfen der von uns visuell erkannten Zonen mit den beiden Clusteralgorithmen nicht ohne Weiteres möglich ist. Die Cluster des K-Means schließen fast alle die beiden Zonen mit ein, und die Cluster des DBSCAN lassen eine Unterscheidung nur zu, wenn es an jeder Stelle eine Lücke zwischen beiden Zonen gibt. Ein Beispiel hierfür ist die Clusterung von Russell Westbrook mit einer maximalen Distanz von 25.

Wollen wir also die beiden Zonen anhand der Daten unterscheiden, müssen wir uns über eine geeignete Transformation der Daten Gedanken machen und kommen ganz natürlich wieder auf die Distanz zum Korb. In Abbildung 2 war schon deutlich erkennbar, dass zum Abstand der 3-Punkte-Line hin bei 23 Fuß ein starker Abfall der Anzahl der Würfe besteht. Warum also nicht ein Cluster auf diesen eindimensionalen Daten durchführen? Hierzu müssen wir lediglich die Zeile zum Bestimmen des Clusters in der Funktion austauschen:

y_pred = kmeans.fit_predict(df[['SHOT_DISTANCE']])
Abb. 5: K-Means-Clusterung anhand der Distanzen

Abb. 5: K-Means-Clusterung anhand der Distanzen

Das Ergebnis zeigt zwar für zwei Cluster noch nicht den gewünschten Erfolg, es wird aber schnell klar, dass spätestens ab drei Clustern eine immer bessere Unterscheidung der 3-Punkte-Würfe möglich wird. Genauso wie die sehr nah am Korb stattfindenden Würfe, sind die 3-Punkte-Würfe in einem Cluster, das sich auch bei zunehmender Clusterzahl kaum verändert. In der Clusteranalyse weisen solche Cluster auf einen starken Zusammenhang der Daten hin und bieten eine stabile Unterscheidungsmöglichkeit.

Auf Basis der Unterscheidung könnten wir an dieser Stelle weitergehen und z. B. ein lineares Regressionsmodell trainieren (siehe auch Teil 1 der Artikelserie), das uns erlaubt, die Würfe aus verschiedenen Clustern für jedes Spiel mit verschiedenen Koeffizienten zu gewichten. Der Code hierzu ist in den Sourcen zum Artikel enthalten. Als Ergebnis erhalten wir für die K-Means-Clusterung aller erfolgreichen Würfe folgende Gewichtungen:

Zwei Cluster : [ 2.61672885  2.0295238 ]
Drei Cluster : [ 2.92932838  1.98245918  2.02778373 ]
Vier Cluster : [ 2.97647691  2.01352384  1.97774059  1.9998526 ]
Fünf Cluster : [ 3.  2.  2.  2.  2.]

Diese bestätigen unseren visuellen Eindruck, dass die Unterscheidung zwischen der 2-Punkte- und 3-Punkte-Zone mit zunehmender Clusteranzahl immer genauer wird.

Fazit

Im Rahmen des Artikels haben wir die Grundzüge der Clusteranalyse mit zwei weit verbreiteten Clusteralgorithmen kennen gelernt. Ebenso haben wir uns angeschaut, wie eine Datentransformation zu einem besseren Unterscheidungsmerkmal führen kann.

Wie in diesem Artikel gezeigt, hat eine Clusteranalyse auch in der Praxis viel mit Ausprobieren und Optimieren zu tun. Das Wichtigste dabei: Möglichst alle Ausreißer entfernen und dann auf einer geeigneten Datentransformation die richtigen Parameter des Clusteralgorithmus zum Trennen der Eingabedaten suchen. Wir wünschen viel Spaß dabei!

Unsere Redaktion empfiehlt:

Relevante Beiträge

Hinterlasse einen Kommentar

Hinterlasse den ersten Kommentar!

avatar
400
  Subscribe  
Benachrichtige mich zu:
X
- Gib Deinen Standort ein -
- or -