K bedeutet inkohärentes Verhalten bei Auswahl von K mit Ellbogenmethode, BIC, Varianzerklärung und Silhouette

23

Ich versuche, einige Vektoren mit 90 Merkmalen mit K-Mitteln zu gruppieren. Da dieser Algorithmus mich nach der Anzahl der Cluster fragt, möchte ich meine Wahl mit einer guten Mathematik bestätigen. Ich erwarte 8 bis 10 Cluster. Die Funktionen sind Z-Score-skaliert.

Ellbogenmethode und Varianz erklärt

from scipy.spatial.distance import cdist, pdist
from sklearn.cluster import KMeans

K = range(1,50)
KM = [KMeans(n_clusters=k).fit(dt_trans) for k in K]
centroids = [k.cluster_centers_ for k in KM]

D_k = [cdist(dt_trans, cent, 'euclidean') for cent in centroids]
cIdx = [np.argmin(D,axis=1) for D in D_k]
dist = [np.min(D,axis=1) for D in D_k]
avgWithinSS = [sum(d)/dt_trans.shape[0] for d in dist]

# Total with-in sum of square
wcss = [sum(d**2) for d in dist]
tss = sum(pdist(dt_trans)**2)/dt_trans.shape[0]
bss = tss-wcss

kIdx = 10-1

# elbow curve
fig = plt.figure()
ax = fig.add_subplot(111)
ax.plot(K, avgWithinSS, 'b*-')
ax.plot(K[kIdx], avgWithinSS[kIdx], marker='o', markersize=12, 
markeredgewidth=2, markeredgecolor='r', markerfacecolor='None')
plt.grid(True)
plt.xlabel('Number of clusters')
plt.ylabel('Average within-cluster sum of squares')
plt.title('Elbow for KMeans clustering')

fig = plt.figure()
ax = fig.add_subplot(111)
ax.plot(K, bss/tss*100, 'b*-')
plt.grid(True)
plt.xlabel('Number of clusters')
plt.ylabel('Percentage of variance explained')
plt.title('Elbow for KMeans clustering')

Ellenbogen-Methode Varianz

Aus diesen beiden Bildern geht hervor, dass die Anzahl der Cluster niemals aufhört: D. Seltsam! Wo ist der Ellbogen? Wie kann ich K wählen?

Bayesianisches Informationskriterium

Diese Methode stammt direkt von X-means und verwendet den BIC , um die Anzahl der Cluster zu bestimmen. eine andere ref

    from sklearn.metrics import euclidean_distances
from sklearn.cluster import KMeans

def bic(clusters, centroids):
    num_points = sum(len(cluster) for cluster in clusters)
    num_dims = clusters[0][0].shape[0]
    log_likelihood = _loglikelihood(num_points, num_dims, clusters, centroids)
    num_params = _free_params(len(clusters), num_dims)
    return log_likelihood - num_params / 2.0 * np.log(num_points)


def _free_params(num_clusters, num_dims):
    return num_clusters * (num_dims + 1)


def _loglikelihood(num_points, num_dims, clusters, centroids):
    ll = 0
    for cluster in clusters:
        fRn = len(cluster)
        t1 = fRn * np.log(fRn)
        t2 = fRn * np.log(num_points)
        variance = _cluster_variance(num_points, clusters, centroids) or np.nextafter(0, 1)
        t3 = ((fRn * num_dims) / 2.0) * np.log((2.0 * np.pi) * variance)
        t4 = (fRn - 1.0) / 2.0
        ll += t1 - t2 - t3 - t4
    return ll

def _cluster_variance(num_points, clusters, centroids):
    s = 0
    denom = float(num_points - len(centroids))
    for cluster, centroid in zip(clusters, centroids):
        distances = euclidean_distances(cluster, centroid)
        s += (distances*distances).sum()
    return s / denom

from scipy.spatial import distance
def compute_bic(kmeans,X):
    """
    Computes the BIC metric for a given clusters

    Parameters:
    -----------------------------------------
    kmeans:  List of clustering object from scikit learn

    X     :  multidimension np array of data points

    Returns:
    -----------------------------------------
    BIC value
    """
    # assign centers and labels
    centers = [kmeans.cluster_centers_]
    labels  = kmeans.labels_
    #number of clusters
    m = kmeans.n_clusters
    # size of the clusters
    n = np.bincount(labels)
    #size of data set
    N, d = X.shape

    #compute variance for all clusters beforehand
    cl_var = (1.0 / (N - m) / d) * sum([sum(distance.cdist(X[np.where(labels == i)], [centers[0][i]], 'euclidean')**2) for i in range(m)])

    const_term = 0.5 * m * np.log(N) * (d+1)

    BIC = np.sum([n[i] * np.log(n[i]) -
               n[i] * np.log(N) -
             ((n[i] * d) / 2) * np.log(2*np.pi*cl_var) -
             ((n[i] - 1) * d/ 2) for i in range(m)]) - const_term

    return(BIC)



sns.set_style("ticks")
sns.set_palette(sns.color_palette("Blues_r"))
bics = []
for n_clusters in range(2,50):
    kmeans = KMeans(n_clusters=n_clusters)
    kmeans.fit(dt_trans)

    labels = kmeans.labels_
    centroids = kmeans.cluster_centers_

    clusters = {}
    for i,d in enumerate(kmeans.labels_):
        if d not in clusters:
            clusters[d] = []
        clusters[d].append(dt_trans[i])

    bics.append(compute_bic(kmeans,dt_trans))#-bic(clusters.values(), centroids))

plt.plot(bics)
plt.ylabel("BIC score")
plt.xlabel("k")
plt.title("BIC scoring for K-means cell's behaviour")
sns.despine()
#plt.savefig('figures/K-means-BIC.pdf', format='pdf', dpi=330,bbox_inches='tight')

Bildbeschreibung hier eingeben

Gleiches Problem hier ... Was ist K?

Silhouette

    from sklearn.metrics import silhouette_score

s = []
for n_clusters in range(2,30):
    kmeans = KMeans(n_clusters=n_clusters)
    kmeans.fit(dt_trans)

    labels = kmeans.labels_
    centroids = kmeans.cluster_centers_

    s.append(silhouette_score(dt_trans, labels, metric='euclidean'))

plt.plot(s)
plt.ylabel("Silouette")
plt.xlabel("k")
plt.title("Silouette for K-means cell's behaviour")
sns.despine()

Bildbeschreibung hier eingeben

Alleluja! Hier scheint es Sinn zu machen und das ist, was ich erwarte. Aber warum unterscheidet sich das von den anderen?

Marcodena
quelle
1
Um Ihre Frage zum Knie im Varianzfall zu beantworten: Es sieht so aus, als ob es bei 6 oder 7 liegt. Sie können es sich als Bruchstelle zwischen zwei linearen Approximationssegmenten zur Kurve vorstellen. Die Form des Diagramms ist nicht ungewöhnlich. Die prozentuale Varianz nähert sich häufig asymptotisch 100%. Ich würde k in Ihr BIC-Diagramm als etwas niedriger einsetzen, um 5.
image_doctor
aber ich sollte (mehr oder weniger) in allen methoden die gleichen ergebnisse haben, oder?
Marcodena
Ich glaube nicht, dass ich genug weiß, um es zu sagen. Ich bezweifle sehr, dass die drei Methoden mit allen Daten mathematisch äquivalent sind, da sie sonst nicht als unterschiedliche Techniken existieren und die Vergleichsergebnisse datenabhängig sind. Zwei der Methoden geben die Anzahl der Cluster an, die nahe beieinander liegen, die dritte ist höher, aber nicht enorm. Haben Sie a priori Informationen über die tatsächliche Anzahl von Clustern?
image_doctor
Ich bin nicht 100% sicher, aber ich erwarte 8 bis 10 Cluster
Marcodena
2
Sie befinden sich bereits im Schwarzen Loch von "Curse of Dimensionality". Nichts funktioniert vor einer Dimensionsreduktion.
Kasra Manshaei

Antworten:

7

Posten Sie einfach eine Zusammenfassung der obigen Kommentare und einige weitere Gedanken, damit diese Frage aus "unbeantworteten Fragen" entfernt wird.

Der Kommentar von Image_doctor ist richtig, dass diese Graphen typisch für k-means sind. (Ich bin jedoch nicht mit dem "Silhouette" -Maß vertraut.) Es wird erwartet, dass die Varianz innerhalb des Clusters mit zunehmendem k kontinuierlich abnimmt. Am Ellbogen biegt sich die Kurve am meisten. (Vielleicht denken Sie "2. Ableitung", wenn Sie etwas mathematisches wollen.)

Im Allgemeinen ist es am besten, k mit der letzten Aufgabe auszuwählen. Verwenden Sie keine statistischen Kennzahlen Ihres Clusters, um Ihre Entscheidung zu treffen, sondern nutzen Sie die End-to-End-Leistung Ihres Systems als Entscheidungshilfe. Verwenden Sie die Statistik nur als Ausgangspunkt.

Joachim Wagner
quelle
5

Das Finden des Ellbogens kann durch Berechnen der Winkel zwischen den aufeinanderfolgenden Segmenten erleichtert werden.

Ersetzen Sie Ihre:

kIdx = 10-1

mit:

seg_threshold = 0.95 #Set this to your desired target

#The angle between three points
def segments_gain(p1, v, p2):
    vp1 = np.linalg.norm(p1 - v)
    vp2 = np.linalg.norm(p2 - v)
    p1p2 = np.linalg.norm(p1 - p2)
    return np.arccos((vp1**2 + vp2**2 - p1p2**2) / (2 * vp1 * vp2)) / np.pi

#Normalize the data
criterion = np.array(avgWithinSS)
criterion = (criterion - criterion.min()) / (criterion.max() - criterion.min())

#Compute the angles
seg_gains = np.array([0, ] + [segments_gain(*
        [np.array([K[j], criterion[j]]) for j in range(i-1, i+2)]
    ) for i in range(len(K) - 2)] + [np.nan, ])

#Get the first index satisfying the threshold
kIdx = np.argmax(seg_gains > seg_threshold)

und du wirst etwas sehen wie: Bildbeschreibung hier eingeben

Wenn Sie die seg_gains visualisieren, sehen Sie etwa Folgendes: Bildbeschreibung hier eingeben

Ich hoffe du findest jetzt den kniffligen Ellbogen :)

Sahloul
quelle
3

Ich habe eine Python- Bibliothek erstellt , die versucht, den Kneedle-Algorithmus zu implementieren , um den Punkt der maximalen Krümmung in Funktionen wie dieser zu ermitteln. Es kann mit installiert werden pip install kneed.

Code und Ausgabe für vier verschiedene Formen von Funktionen:

from kneed.data_generator import DataGenerator
from kneed.knee_locator import KneeLocator

import numpy as np

import matplotlib.pyplot as plt

# sample x and y
x = np.arange(0,10)
y_convex_inc = np.array([1,2,3,4,5,10,15,20,40,100])
y_convex_dec = y_convex_inc[::-1]
y_concave_dec = 100 - y_convex_inc
y_concave_inc = 100 - y_convex_dec

# find the knee points
kn = KneeLocator(x, y_convex_inc, curve='convex', direction='increasing')
knee_yconvinc = kn.knee

kn = KneeLocator(x, y_convex_dec, curve='convex', direction='decreasing')
knee_yconvdec = kn.knee

kn = KneeLocator(x, y_concave_inc, curve='concave', direction='increasing')
knee_yconcinc = kn.knee

kn = KneeLocator(x, y_concave_dec, curve='concave', direction='decreasing')
knee_yconcdec = kn.knee

# plot
f, axes = plt.subplots(2, 2, figsize=(10,10));
yconvinc = axes[0][0]
yconvdec = axes[0][1]
yconcinc = axes[1][0]
yconcdec = axes[1][1]

yconvinc.plot(x, y_convex_inc)
yconvinc.vlines(x=knee_yconvinc, ymin=0, ymax=100, linestyle='--')
yconvinc.set_title("curve='convex', direction='increasing'")

yconvdec.plot(x, y_convex_dec)
yconvdec.vlines(x=knee_yconvdec, ymin=0, ymax=100, linestyle='--')
yconvdec.set_title("curve='convex', direction='decreasing'")

yconcinc.plot(x, y_concave_inc)
yconcinc.vlines(x=knee_yconcinc, ymin=0, ymax=100, linestyle='--')
yconcinc.set_title("curve='concave', direction='increasing'")

yconcdec.plot(x, y_concave_dec)
yconcdec.vlines(x=knee_yconcdec, ymin=0, ymax=100, linestyle='--')
yconcdec.set_title("curve='concave', direction='decreasing'");

Bildbeschreibung hier eingeben

Kevin
quelle