Wie kann man bei K-Means den "Elbow" berechnen?
Hey zusammen,
ich betreibe Clustering mit K-Means.
Nun weiß ich zuvor leider nicht wie viele Cluster vorhanden sind. Eine Lösung dafür ist die sogenannte Elbow Method. Leider basiert die Methode immer darauf einen Graphen zu Plotten und diesen wortwörtlich anzusehen.
Ich möchte den Elbow aber natürlich rechnerisch ermitteln. Jemand eine Idee?
Mein erster Versuch war die größte Differenz zwischen einen Punkt und dem nächsten zu berechnen, leider funktioniert das offenbar nicht so toll. Was ist also ein "Elbow" rechnerisch?
https://predictivehacks.com/k-means-elbow-method-code-for-python/
Hier so ein Elbow, bei dem würde die größte Differenz funktionieren. Der "Elbow" liegt bei 4:
Bei diesem Beispiel liegt der Elbow allerdings bei 4 und die größte Differenz funktioniert hier nicht:
Durch Hinsehen würde man aber schon sagen, dass 4 der "Elbow" ist. Ich nehme an, irgendwie kann man das auch berechnen, wenn man es "sehen" kann.
Wenn ich google Bemühe, dass werden zwar alle möglichen Implementierungen für die Methode vorgeschlagen. Aber alle arbeiten damit den Graphen zu plotten und anzusehen.
Gruß
3 Antworten
Du nimmst die Steigung.
Steigung = flach -> nach dem Knick.
Oder du verwendest einfach ein Verfahren bei dem die Anzahl der Cluster nicht vorgegeben werden muss.
Du musst halt einen sinnvollen Grenzwert für die Steigung finden. Steigung = 0 gibt es nur wenn k = Anzahl der Daten.
wie gesagt : lang her : man muss "echte" statistische Verfahren anwenden.
Ich empfehle daher erst mal
https://en.wikipedia.org/wiki/Elbow_method_%28clustering%29
und
normalerweise macht man das mit einem Statistikprogramm. Aber du willst es selbst machen , was keine Kosten verursacht und du kannst es sogar verkaufen :))
und dieses wirst du schon kennen
K-Means habe ich natürlich schon, der funktioniert auch wunderbar.
Interessant, dass bei der Elbow-Method auch dort geschrieben wird, dass man die Daten plottet und dann selbst wählt. Aber vielleicht geht das ja über einen prozentualen Schwellwert wie das in der Grafik erklärt wird.
Gruß
To determine the optimal number of clusters, we have to select the value of k at the “elbow” ie the point after which the distortion/inertia start decreasing in a linear fashion.
Was bedeutet das? Naja, das bedeutet, dass das Optimale k genau dann gegeben ist, wenn du von diesem Punkt aus alle weiteren Werte durch ein lineares Modell einigermaßen erklären kannst. Im Code würde ich das wie folgt lösen
import numpy as np
from sklearn.linear_model import LinearRegression
from sklearn.metrics import mean_squared_error
import matplotlib.pyplot as plt
def find_elbow(inertia, eps=10e-3):
current = 0
kmax = inertia.shape[0]
ks = np.arange(kmax)
for k in range(kmax):
ks = np.arange(k, kmax).reshape(-1,1)
vals = inertia[ks].reshape(-1,1)
reg = LinearRegression().fit(ks, vals)
err = mean_squared_error(vals, reg.predict(ks))
if err < eps:
return k
return ks[-1]
def main():
# We create some synthetic data
inertia = [210., 150., 20.]
kfirst, klast = len(inertia), 10
# Generate data by interpolating between values
yfirst, ylast = inertia[-1], 1.
ks = np.arange(kfirst, klast+1)
interpoalted = (ylast-yfirst)/(klast-kfirst) * (ks-kfirst) + yfirst
interpoalted = interpoalted[1:]
# Add some noise
interpoalted += np.random.normal(0, 10e-3, interpoalted.shape[0])
# Concat to previous values
inertia += interpoalted.tolist()
inertia = np.array(inertia)
optimal_k = find_elbow(inertia)
print(optimal_k)
plt.plot(np.arange(len(inertia)), np.array(inertia), marker='o')
plt.vlines(optimal_k, 0, np.max(inertia), linestyles='dashed')
plt.show()
if __name__ == '__main__':
main()
Diese Lösung geht im Wesentlichen durch alle ks und versucht eine Gerade durch die Punkte zu legen. Das erste k, für das der Fehler kleiner als ein gewisses Epsilon wird, wird von der Funktion zurückgegeben. Natürlich hat dieser Ansatz einige Schwächen, in jedem Fall kann es zu Skalenproblemen kommen (d.h. wenn die Werte bereits sehr klein sind). Außerdem ist die Wahl des richtigen Epsilons entscheidend, d.h. du handelst dir einen zusätzlichen Hyperparameter ein. Der Idee nach sollte das aber einigermaßen funktionieren, wenn man die Suche nach dem optimalen k denn unbedingt automatisieren möchte.
Ich habe das jetzt nur für diese künstlichen Beispiel getestet. Du kannst gerne mal probieren, deine eigenen Daten in den Algorithmus zu stecken.
Ah nice, werde ich gerne testen.
Mein Ansatz (der super primitiv ist) findet aktuell bei 4 deutlich erkennbaren Klustern nur 2, verbindet also jeweils 2 Kluster.
Gruß
sinnvoll? gerne : hier : https://de.wikipedia.org/wiki/Cluster
Clusteranalyse ist lang her bei mir ..............genau wie Faktorenanalyse fand ich sie immer recht willkürlich ............
Jetzt habe ich so schön k-mean implementiert (naja, eine Lib benutzt) und langsam bekomme ich das Gefühl ich müsste ein anderes Verfahren nutzen, eines welches auch die Anzahl optimiert
-.-°
Gruß
Dann wäre im ersten Beispiel 8 der Elbow, was nicht stimmt.