K-Means Clustering: Techniken zum Finden der optimalen Cluster (2024)

In diesem Artikel erhalten Sie ein Verständnis für

• Was ist K-Means-Clustering?
• Wie funktioniert K-Means?
• Anwendungen von K-Means-Clustering
• Implementierung von K-Means-Clusterings in Python
• Finden optimaler Cluster mit der Elbow-Methode, Silhouette-Score und Gap Statistics

Der K-Means-Algorithmus zielt darauf ab, kohäsive Cluster basierend auf der definierten Anzahl von Clustern K zu haben. Er erzeugt kohäsive kompakte Cluster durch Minimieren der gesamten Intra-Cluster-Variation, die als Quadratsumme innerhalb des Clusters (WCSS) bezeichnet wird.

Der K-Means-Algorithmus beginnt mit zufällig ausgewählten Schwerpunkten für die angegebene Anzahl von Clustern . Schwerpunkte sind das Zentrum der Cluster. Die Schwerpunkte müssen strategisch gewählt werden, da die verschiedenen Positionen zu unterschiedlichen Ergebnissen führen.

Der Algorithmus verfeinert dann iterativ die Schwerpunktorte, indem er jeden Datenpunkt basierend auf seiner Nähe zu einem bestimmten Cluster im Vergleich zu allen anderen Clustern einem Cluster zuweist . Die Nähe eines Datenpunkts zu einem Schwerpunkt basiert auf ihrem euklidischen quadratischen Abstand.

K-Means-Clustering kann eines der folgenden Entfernungsmaße verwenden use

• Euklidische Entfernung
• Manhattan-Entfernung
• Eine quadrierte euklidische Distanz
• Kosinusabstand

K-Means findet iterativ die besten Schwerpunkte für einen Cluster, indem abwechselnd zwischen

• Zuweisen von Datenpunkten zu Clustern basierend auf ihrer Nähe zu den aktuellen Schwerpunkten und
• Neuberechnung der Schwerpunkte basierend auf der aktuellen Zuordnung von Datenpunkten zu Clustern.

• Die Clusterschwerpunkte haben sich stabilisiert, wenn sich der Datenpunkt zu einem Cluster nicht mehr ändert oder
• Der Algorithmus hat seine angegebene Anzahl von Iterationen abgeschlossen.

• Anomalieerkennung wie eine Betrugserkennung
• Segmentierung wie Kundensegmentierung, Bildsegmentierung
• Data-Mining

Mall-Kundendatensatz

Lesen Sie die CSV-Datei in einem Datenrahmen, konvertieren Sie die kategoriale Variable in einen numerischen Datentyp und reduzieren Sie dann die Dimension mit PCA (Principal Component Analysis)

# Import the required librariesimport numpy as np import pandas as pd import matplotlib.pyplot as pltimport seaborn as snsfrom sklearn.cluster import KMeansfrom sklearn.preprocessing import LabelBinarizerfrom sklearn.decomposition import PCA# Read he dataset into a dtafarmaedataset = pd.read_csv('Mall_Customers.csv',index_col='CustomerID')# Drop duplicatesdataset.drop_duplicates(inplace=True)# Converting categorical column Genre to onehot vectorlabel_binarizer = LabelBinarizer() #use LabelBinarizer for genderlabel_binarizer_output = label_binarizer.fit_transform( dataset['Genre'])#Adding the categorical and the main dataframe into one dataframeresult_df = pd.DataFrame(label_binarizer_output, columns=['Gender_1'])dataset_1= pd.concat([dataset, result_df], axis=1, join='inner')# Creating the input variableX= dataset_1.iloc[:, [1,2,3,4]].values# reducing the input dimension using PCAreduced_data = PCA(n_components=2).fit_transform(X)

kmeans = KMeans(init="k-means++", n_clusters=5, n_init=4)kmeans.fit(X)

Es gibt 3 beliebte Methoden, um den optimalen Cluster für den KMeans-Clustering-Algorithmus zu finden.

Ellbogenmethode

Bei der Elbow-Methode wird der K-Means-Algorithmus für unterschiedliche Anzahlen von Clustern ausgeführt, um die Summe der quadratischen Abstände jedes Datenpunkts vom Schwerpunkt des Clusters zu ermitteln, die auch als Quadratsumme innerhalb des Clusters bezeichnet wird.

Plotten Sie das WCSS zusammen mit der Anzahl der K-Cluster. Wählen Sie den K-Wert auf dem Diagramm aus, bei dem das WCSS anfängt, sich abzuflachen oder plötzlich zu fallen, und das Hinzufügen eines weiteren Clusters verbessert sich nicht wesentlich und bildet einen Ellbogen . Der Ellenbogen gilt als Indikator für den optimalen Cluster für den Datensatz.

# Using the elbow method to find the optimal number of clustersmax_k=11 # max no. of clusters to be evaluatedwcss = []for i in range(1, max_k): kmeans = KMeans(n_clusters = i, init = 'k-means++', random_state = 42) kmeans.fit(reduced_data) # inertia method returns wcss for that model wcss.append(kmeans.inertia_)#plotting the data plt.figure(figsize=(5,3))sns.lineplot(range(1, max_k), wcss,marker='o',color='red')plt.title('The Elbow Method')plt.xlabel('Number of clusters')plt.ylabel('WCSS')plt.show() 
 Elbow method — the circle shows the optimal number of the cluster for the dataset. 

Der Silhouette-Score ist eine weitere Metrik, um die Kompaktheit des Clusters zu überprüfen, um festzustellen, ob der Cluster gut ist .

Der Silhouette-Score berechnet den mittleren Intra-Cluster-Abstand wie bei der Elbow-Methode und auch den mittleren nächsten Cluster . Dies stellt dar, wie ähnlich ein Datenpunkt seinem eigenen Cluster im Vergleich zu allen anderen Clusterschwerpunkten ist. Daher misst der Silhouette-Score sowohl die Kompaktheit mit demselben Cluster als auch die Trennung mit anderen Clustern .

Wenn der Wert für die Silhouettenbewertung für alle Datenpunkte beträchtlich hoch ist, ergibt dies den optimalen Wert für die Cluster . Der Silhouette-Score verwendet die Minkowski-Distanz oder die Euklidische Distanz, und ihr Wert reicht von [-1, 1]

Der folgende Code ist angepasst von https://scikit-learn.org/stable/auto_examples/cluster/plot_kmeans_silhouette_analysis.html#

Der Code wird modifiziert, um die reduzierte Datendimension mit PCA zu verwenden

from sklearn.metrics import silhouette_samples, silhouette_scoreimport matplotlib.cm as cmfor n_clusters in range(2, max_k): # Create a subplot with 1 row and 2 columns fig, (ax1, ax2) = plt.subplots(1, 2) fig.set_size_inches(18, 7)# The 1st subplot is the silhouette plot # The silhouette coefficient can range from -1, 1 but in this example all # lie within [-0.1, 1] ax1.set_xlim([-0.1, 1]) # The (n_clusters+1)*10 is for inserting blank space between silhouette # plots of individual clusters, to demarcate them clearly. ax1.set_ylim([0, len(reduced_data) + (n_clusters + 1) * 10])# Initialize the clusterer with n_clusters value and a random generator # seed of 10 for reproducibility. clusterer = KMeans(n_clusters=n_clusters, random_state=10) cluster_labels = clusterer.fit_predict(reduced_data)# The silhouette_score gives the average value for all the samples. # This gives a perspective into the density and separation of the formed # clusters silhouette_avg = silhouette_score(reduced_data, cluster_labels) print("For n_clusters =", n_clusters,"The average silhouette_score is :", silhouette_avg)# Compute the silhouette scores for each sample sample_silhouette_values = silhouette_samples(reduced_data, cluster_labels)y_lower = 10 for i in range(n_clusters): # Aggregate the silhouette scores for samples belonging to # cluster i, and sort them ith_cluster_silhouette_values = \ sample_silhouette_values[cluster_labels == i]ith_cluster_silhouette_values.sort()size_cluster_i = ith_cluster_silhouette_values.shape[0] y_upper = y_lower + size_cluster_icolor = cm.nipy_spectral(float(i) / n_clusters) ax1.fill_betweenx(np.arange(y_lower, y_upper), 0, ith_cluster_silhouette_values, facecolor=color, edgecolor=color, alpha=0.7)# Label the silhouette plots with their cluster numbers at the middle ax1.text(-0.05, y_lower + 0.5 * size_cluster_i, str(i))# Compute the new y_lower for next plot y_lower = y_upper + 10 # 10 for the 0 samplesax1.set_title("The silhouette plot for the various clusters.") ax1.set_xlabel("The silhouette coefficient values") ax1.set_ylabel("Cluster label")# The vertical line for average silhouette score of all the values ax1.axvline(x=silhouette_avg, color="red", linestyle="--")ax1.set_yticks([]) # Clear the yaxis labels / ticks ax1.set_xticks([-0.1, 0, 0.2, 0.4, 0.6, 0.8, 1])# 2nd Plot showing the actual clusters formed colors = cm.nipy_spectral(cluster_labels.astype(float) / n_clusters) ax2.scatter(reduced_data[:, 0], reduced_data[:, 1], marker='.', s=30, lw=0, alpha=0.7, c=colors, edgecolor='k')# Labeling the clusters centers = clusterer.cluster_centers_ # Draw white circles at cluster centers ax2.scatter(centers[:, 0], centers[:, 1], marker='o', c="white", alpha=1, s=200, edgecolor='k')for i, c in enumerate(centers): ax2.scatter(c[0], c[1], marker='$%d$' % i, alpha=1, s=50, edgecolor='k')ax2.set_title("The visualization of the clustered data.") ax2.set_xlabel("Feature space for the 1st feature") ax2.set_ylabel("Feature space for the 2nd feature")plt.suptitle(("Silhouette analysis for KMeans clustering on sample data " "with n_clusters = %d" % n_clusters), fontsize=14, fontweight='bold')plt.show() 
 Silhouette score — showing 5 is the optimal number of clusters 

Sowohl die Elbow-Methode als auch der Silhouette-Score ergeben optimale Cluster als 5

Ausführen von KMeans mit dem optimalen Cluster als 5 und anschließendes Zeichnen des Streudiagramms unter Verwendung optimaler Cluster auf den reduzierten_Daten, um den Cluster zu visualisieren

# Fitting K-Means to the datasetkmeans = KMeans(n_clusters = 5, init = 'k-means++', random_state = 42)y_kmeans = kmeans.fit_predict(reduced_data)#Visualising the clustersplt.figure(figsize=(15,7))sns.scatterplot(reduced_data[y_kmeans == 0, 0], reduced_data[y_kmeans == 0, 1], color = 'yellow', label = 'Cluster 1',s=50)sns.scatterplot(reduced_data[y_kmeans == 1, 0], reduced_data[y_kmeans == 1, 1], color = 'blue', label = 'Cluster 2',s=50)sns.scatterplot(reduced_data[y_kmeans == 2, 0], reduced_data[y_kmeans == 2, 1], color = 'green', label = 'Cluster 3',s=50)sns.scatterplot(reduced_data[y_kmeans == 3, 0], reduced_data[y_kmeans == 3, 1], color = 'grey', label = 'Cluster 4',s=50)sns.scatterplot(reduced_data[y_kmeans == 4, 0], reduced_data[y_kmeans == 4, 1], color = 'orange', label = 'Cluster 5',s=50)sns.scatterplot(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], color = 'red', label = 'Centroids',s=300,marker=',')plt.grid(False)plt.title('Clusters of customers')plt.xlabel('PC-1')plt.ylabel('PC-2')plt.legend()plt.show() 

Die Gap-Statistik ist eine weitere beliebte Methode zur Bestimmung der optimalen Anzahl von Clustern und kann auf jede Clustering-Methode angewendet werden.

Die Idee der Gap-Statistik besteht darin, die Clusterträgheit der Daten mit ihrer Erwartung unter einem geeigneten Null-Referenzdatensatz zu vergleichen. Die Null-Referenzdatensätze können aus einer Normalverteilung oder einer Gleichverteilung entnommen werden. Die optimale Wahl von K ist ein Wert, der die Lückenstatistik zwischen der Trägheit innerhalb des Clusters des Datasets und des nullreferenzierten Datasets maximiert.

Gap Statistics ist die Differenz zwischen E ₙ, der Erwartung der nullreferenzierten Daten, die als Logarithmus der Gesamtsumme innerhalb der Intra-Cluster-Variation berechnet wird, und der Gesamtsumme innerhalb der Intra-Cluster-Variation für den Datensatz data

Der folgende Code ist inspiriert und angepasst von https://glowingpython.blogspot.com/2019/01/a-visual-introduction-to-gap-statistics.html

Der nullreferenzierte Datensatz ist ein gleichmäßig verteilter Satz von Punkten

from sklearn.datasets import make_blobsfrom sklearn.metrics import pairwise_distances# creating a uniform distributed null refernced datasetreference = np.random.rand(100, 2)plt.figure(figsize=(12, 3))for k in range(1,6): kmeans = KMeans(n_clusters=k) a = kmeans.fit_predict(reference) plt.subplot(1,5,k) plt.scatter(reference[:, 0], reference[:, 1], c=a) plt.xlabel('k='+str(k))plt.tight_layout()plt.show()

def compute_inertia(a, X): W = [np.mean(pairwise_distances(X[a == c, :])) for c in np.unique(a)] return np.mean(W)def compute_gap(clustering, data, k_max=5, n_references=5): if len(data.shape) == 1: data = data.reshape(-1, 1) # The Null Reference dataset that is uniformly distributed reference = np.random.rand(*data.shape) reference_inertia = [] # Calculate the WCSS for the null refrenced data for k in range(1, k_max+1): local_inertia = [] for _ in range(n_references): clustering.n_clusters = k assignments = clustering.fit_predict(reference) local_inertia.append(compute_inertia(assignments, reference)) reference_inertia.append(np.mean(local_inertia)) # Calculate the WCSS for the data ondata_inertia = [] for k in range(1, k_max+1): clustering.n_clusters = k assignments = clustering.fit_predict(data) ondata_inertia.append(compute_inertia(assignments, data)) # Calculate the gao statistics between the WCSS for the null referenced data and the WCSS for the data gap = np.log(reference_inertia)-np.log(ondata_inertia) return gap, np.log(reference_inertia), np.log(ondata_inertia)gap, reference_inertia, ondata_inertia = compute_gap(KMeans(), reduced_data, k_max)plt.plot(range(1, k_max+1), gap, '-o')plt.ylabel('gap')plt.xlabel('k') 

Ausführen von KMeans für 10 Cluster und anschließendes Visualisieren der Cluster in einem Streudiagramm.

# Visualising the clustersplt.figure(figsize=(15,7))sns.scatterplot(reduced_data[y_kmeans == 0, 0], reduced_data[y_kmeans == 0, 1], color = 'yellow', label = 'Cluster 1',s=50)sns.scatterplot(reduced_data[y_kmeans == 1, 0], reduced_data[y_kmeans == 1, 1], color = 'blue', label = 'Cluster 2',s=50)sns.scatterplot(reduced_data[y_kmeans == 2, 0], reduced_data[y_kmeans == 2, 1], color = 'green', label = 'Cluster 3',s=50)sns.scatterplot(reduced_data[y_kmeans == 3, 0], reduced_data[y_kmeans == 3, 1], color = 'grey', label = 'Cluster 4',s=50)sns.scatterplot(reduced_data[y_kmeans == 4, 0], reduced_data[y_kmeans == 4, 1], color = 'orange', label = 'Cluster 5',s=50)sns.scatterplot(reduced_data[y_kmeans == 5, 0], reduced_data[y_kmeans == 5, 1], color = 'pink', label = 'Cluster 6',s=50)sns.scatterplot(reduced_data[y_kmeans == 6, 0], reduced_data[y_kmeans == 6, 1], color = 'magenta', label = 'Cluster 7',s=50)sns.scatterplot(reduced_data[y_kmeans == 7, 0], reduced_data[y_kmeans == 7, 1], color = 'cyan', label = 'Cluster 8',s=50)sns.scatterplot(reduced_data[y_kmeans == 8, 0], reduced_data[y_kmeans == 8, 1], color = 'purple', label = 'Cluster 9',s=50)sns.scatterplot(reduced_data[y_kmeans == 9, 0], reduced_data[y_kmeans == 9, 1], color = 'brown', label = 'Cluster 10',s=50)sns.scatterplot(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], color = 'red', label = 'Centroids',s=300,marker=',')plt.grid(False)plt.title('Clusters of customers')plt.xlabel('PC-1')plt.ylabel('PC-2')plt.legend()plt.show() 

K-Means-Clustering ist ein

• Ein unüberwachter Algorithmus für maschinelles Lernen
• Ein iterativer Algorithmus zum Auffinden von Datengruppen mit ähnlichen Eigenschaften für einen unbeschrifteten Datensatz

• Ellenbogenmethode : Bei der WCSS beginnt sich plötzlich abzuflachen und das Hinzufügen eines weiteren Clusters verbessert sich nicht wesentlich und bildet einen Ellbogen.
• Silhouette-Score : Misst sowohl die Kompaktheit mit demselben Cluster als auch die Trennung mit anderen Clustern
• Gap Statistics: Die maximale Lücke zwischen der Trägheit innerhalb des Clusters des Datasets und des nullreferenzierten Datasets ist gleichmäßig verteilt.

https://stanford.edu/~cpiech/cs221/handouts/kmeans.html

https://arxiv.org/ftp/arxiv/papers/1912/1912.00643.pdf

Schätzung der Anzahl von Clustern in einem Datensatz anhand der Gap-Statistik von R. Tibshirani, G. Walther und T. Hastie (Standford University, 2001) .

https://glowingpython.blogspot.com/2019/01/a-visual-introduction-to-gap-statistics.html