python - valor - Cálculo del porcentaje de medida de varianza para k-means?

valor medio python

Question

En la página de Wikipedia , se describe un método de codo para determinar la cantidad de conglomerados en k-means. El método incorporado de scipy proporciona una implementación, pero no estoy seguro de entender cómo se calcula la distorsión como la llaman.

Más precisamente, si graficas el porcentaje de varianza explicado por los clusters contra el número de clusters, los primeros clusters agregarán mucha información (explican mucha varianza), pero en algún punto la ganancia marginal caerá, dando un ángulo en el grafico.

Suponiendo que tengo los siguientes puntos con sus centroides asociados, ¿cuál es una buena forma de calcular esta medida?

points = numpy.array([[ 0,  0],
       [ 0,  1],
       [ 0, -1],
       [ 1,  0],
       [-1,  0],
       [ 9,  9],
       [ 9, 10],
       [ 9,  8],
       [10,  9],
       [10,  8]])

kmeans(pp,2)
(array([[9, 8],
   [0, 0]]), 0.9414213562373096)

Estoy buscando específicamente calcular la medida 0.94 .. dado solo los puntos y los centroides. No estoy seguro si se puede usar alguno de los métodos incorporados de scipy o si tengo que escribir el mío. ¿Alguna sugerencia sobre cómo hacer esto de manera eficiente para una gran cantidad de puntos?

En resumen, mis preguntas (todas relacionadas) son las siguientes:

• Dada una matriz de distancia y un mapeo de qué punto pertenece a qué clúster, ¿cuál es una buena forma de calcular una medida que se puede usar para dibujar la gráfica del codo?
• ¿Cómo cambiaría la metodología si se usa una función de distancia diferente, como la similitud del coseno?

EDICION 2: distorsión

from scipy.spatial.distance import cdist
D = cdist(points, centroids, ''euclidean'')
sum(numpy.min(D, axis=1))

La salida para el primer conjunto de puntos es precisa. Sin embargo, cuando pruebo un conjunto diferente:

>>> pp = numpy.array([[1,2], [2,1], [2,2], [1,3], [6,7], [6,5], [7,8], [8,8]])
>>> kmeans(pp, 2)
(array([[6, 7],
       [1, 2]]), 1.1330618877807475)
>>> centroids = numpy.array([[6,7], [1,2]])
>>> D = cdist(points, centroids, ''euclidean'')
>>> sum(numpy.min(D, axis=1))
9.0644951022459797

Supongo que el último valor no coincide porque kmeans parece estar dividiendo el valor entre el número total de puntos en el conjunto de datos.

EDICION 1: Varianza porcentual

Mi código hasta el momento (se debe agregar a la implementación de K-means de Denis):

centres, xtoc, dist = kmeanssample( points, 2, nsample=2,
        delta=kmdelta, maxiter=kmiter, metric=metric, verbose=0 )

print "Unique clusters: ", set(xtoc)
print ""
cluster_vars = []
for cluster in set(xtoc):
    print "Cluster: ", cluster

    truthcondition = ([x == cluster for x in xtoc])
    distances_inside_cluster = (truthcondition * dist)

    indices = [i for i,x in enumerate(truthcondition) if x == True]
    final_distances = [distances_inside_cluster[k] for k in indices]

    print final_distances
    print np.array(final_distances).var()
    cluster_vars.append(np.array(final_distances).var())
    print ""

print "Sum of variances: ", sum(cluster_vars)
print "Total Variance: ", points.var()
print "Percent: ", (100 * sum(cluster_vars) / points.var())

Y a continuación está la salida para k = 2:

Unique clusters:  set([0, 1])

Cluster:  0
[1.0, 2.0, 0.0, 1.4142135623730951, 1.0]
0.427451660041

Cluster:  1
[0.0, 1.0, 1.0, 1.0, 1.0]
0.16

Sum of variances:  0.587451660041
Total Variance:  21.1475
Percent:  2.77787757437

En mi conjunto de datos real (¡no me parece correcto!):

Sum of variances:  0.0188124746402
Total Variance:  0.00313754329764
Percent:  599.592510943
Unique clusters:  set([0, 1, 2, 3])

Sum of variances:  0.0255808508714
Total Variance:  0.00313754329764
Percent:  815.314672809
Unique clusters:  set([0, 1, 2, 3, 4])

Sum of variances:  0.0588210052519
Total Variance:  0.00313754329764
Percent:  1874.74720416
Unique clusters:  set([0, 1, 2, 3, 4, 5])

Sum of variances:  0.0672406353655
Total Variance:  0.00313754329764
Percent:  2143.09824556
Unique clusters:  set([0, 1, 2, 3, 4, 5, 6])

Sum of variances:  0.0646291452839
Total Variance:  0.00313754329764
Percent:  2059.86465055
Unique clusters:  set([0, 1, 2, 3, 4, 5, 6, 7])

Sum of variances:  0.0817517362176
Total Variance:  0.00313754329764
Percent:  2605.5970695
Unique clusters:  set([0, 1, 2, 3, 4, 5, 6, 7, 8])

Sum of variances:  0.0912820650486
Total Variance:  0.00313754329764
Percent:  2909.34837831
Unique clusters:  set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

Sum of variances:  0.102119601368
Total Variance:  0.00313754329764
Percent:  3254.76309585
Unique clusters:  set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

Sum of variances:  0.125549475536
Total Variance:  0.00313754329764
Percent:  4001.52168834
Unique clusters:  set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])

Sum of variances:  0.138469402779
Total Variance:  0.00313754329764
Percent:  4413.30651542
Unique clusters:  set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])

Answer 1

La distorsión, en lo que respecta a Kmeans , se usa como criterio de detención (si el cambio entre dos iteraciones es menor que algún umbral, suponemos convergencia)

Si desea calcularlo a partir de un conjunto de puntos y centroides, puede hacer lo siguiente (el código está en MATLAB utilizando la función pdist2 , pero debería ser sencillo reescribir en Python / Numpy / Scipy):

% data
X = [0 1 ; 0 -1 ; 1 0 ; -1 0 ; 9 9 ; 9 10 ; 9 8 ; 10 9 ; 10 8];

% centroids
C = [9 8 ; 0 0];

% euclidean distance from each point to each cluster centroid
D = pdist2(X, C, ''euclidean'');

% find closest centroid to each point, and the corresponding distance
[distortions,idx] = min(D,[],2);

el resultado:

% total distortion
>> sum(distortions)
ans =
           9.4142135623731

EDIT # 1:

Tuve algo de tiempo para jugar con esto ... Aquí hay un ejemplo de clúster de KMeans aplicado en el ''Fisher Iris Dataset'' (4 características, 150 instancias). Realizamos una iteración sobre k=1..10 , k=1..10 la curva del codo, seleccionamos K=3 como el número de conglomerados, y mostramos una gráfica de dispersión del resultado.

Tenga en cuenta que incluí varias formas de calcular las varianzas dentro del clúster (distorsiones), dados los puntos y los centroides. La función scipy.cluster.vq.kmeans devuelve esta medida de forma predeterminada (calculada con Euclidean como una medida de distancia). También puede usar la función scipy.spatial.distance.cdist para calcular las distancias con la función de su elección (siempre que haya obtenido los centroides del grupo utilizando la misma medida de distancia: @Denis tiene una solución para eso), luego calcule la distorsión desde ese.

import numpy as np
from scipy.cluster.vq import kmeans,vq
from scipy.spatial.distance import cdist
import matplotlib.pyplot as plt

# load the iris dataset
fName = ''C://Python27//Lib//site-packages//scipy//spatial//tests//data//iris.txt''
fp = open(fName)
X = np.loadtxt(fp)
fp.close()

##### cluster data into K=1..10 clusters #####
K = range(1,10)

# scipy.cluster.vq.kmeans
KM = [kmeans(X,k) for k in K]
centroids = [cent for (cent,var) in KM]   # cluster centroids
#avgWithinSS = [var for (cent,var) in KM] # mean within-cluster sum of squares

# alternative: scipy.cluster.vq.vq
#Z = [vq(X,cent) for cent in centroids]
#avgWithinSS = [sum(dist)/X.shape[0] for (cIdx,dist) in Z]

# alternative: scipy.spatial.distance.cdist
D_k = [cdist(X, 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)/X.shape[0] for d in dist]

##### plot ###
kIdx = 2

# 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'')

# scatter plot
fig = plt.figure()
ax = fig.add_subplot(111)
#ax.scatter(X[:,2],X[:,1], s=30, c=cIdx[k])
clr = [''b'',''g'',''r'',''c'',''m'',''y'',''k'']
for i in range(K[kIdx]):
    ind = (cIdx[kIdx]==i)
    ax.scatter(X[ind,2],X[ind,1], s=30, c=clr[i], label=''Cluster %d''%i)
plt.xlabel(''Petal Length'')
plt.ylabel(''Sepal Width'')
plt.title(''Iris Dataset, KMeans clustering with K=%d'' % K[kIdx])
plt.legend()

plt.show()

EDIT # 2:

En respuesta a los comentarios, doy a continuación otro ejemplo completo utilizando el conjunto de datos de dígitos escritos a mano del NIST : tiene 1797 imágenes de dígitos del 0 al 9, cada uno de tamaño 8 por 8 píxeles. Repito el experimento anterior ligeramente modificado: el Análisis de Componentes Principales se aplica para reducir la dimensionalidad de 64 a 2:

import numpy as np
from scipy.cluster.vq import kmeans
from scipy.spatial.distance import cdist,pdist
from sklearn import datasets
from sklearn.decomposition import RandomizedPCA
from matplotlib import pyplot as plt
from matplotlib import cm

##### data #####
# load digits dataset
data = datasets.load_digits()
t = data[''target'']

# perform PCA dimensionality reduction
pca = RandomizedPCA(n_components=2).fit(data[''data''])
X = pca.transform(data[''data''])

##### cluster data into K=1..20 clusters #####
K_MAX = 20
KK = range(1,K_MAX+1)

KM = [kmeans(X,k) for k in KK]
centroids = [cent for (cent,var) in KM]
D_k = [cdist(X, 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]

tot_withinss = [sum(d**2) for d in dist]  # Total within-cluster sum of squares
totss = sum(pdist(X)**2)/X.shape[0]       # The total sum of squares
betweenss = totss - tot_withinss          # The between-cluster sum of squares

##### plots #####
kIdx = 9        # K=10
clr = cm.spectral( np.linspace(0,1,10) ).tolist()
mrk = ''os^p<dvh8>+x.''

# elbow curve
fig = plt.figure()
ax = fig.add_subplot(111)
ax.plot(KK, betweenss/totss*100, ''b*-'')
ax.plot(KK[kIdx], betweenss[kIdx]/totss*100, marker=''o'', markersize=12, 
    markeredgewidth=2, markeredgecolor=''r'', markerfacecolor=''None'')
ax.set_ylim((0,100))
plt.grid(True)
plt.xlabel(''Number of clusters'')
plt.ylabel(''Percentage of variance explained (%)'')
plt.title(''Elbow for KMeans clustering'')

# show centroids for K=10 clusters
plt.figure()
for i in range(kIdx+1):
    img = pca.inverse_transform(centroids[kIdx][i]).reshape(8,8)
    ax = plt.subplot(3,4,i+1)
    ax.set_xticks([])
    ax.set_yticks([])
    plt.imshow(img, cmap=cm.gray)
    plt.title( ''Cluster %d'' % i )

# compare K=10 clustering vs. actual digits (PCA projections)
fig = plt.figure()
ax = fig.add_subplot(121)
for i in range(10):
    ind = (t==i)
    ax.scatter(X[ind,0],X[ind,1], s=35, c=clr[i], marker=mrk[i], label=''%d''%i)
plt.legend()
plt.title(''Actual Digits'')
ax = fig.add_subplot(122)
for i in range(kIdx+1):
    ind = (cIdx[kIdx]==i)
    ax.scatter(X[ind,0],X[ind,1], s=35, c=clr[i], marker=mrk[i], label=''C%d''%i)
plt.legend()
plt.title(''K=%d clusters''%KK[kIdx])

plt.show()

Puede ver cómo algunos clústeres corresponden realmente a dígitos distinguibles, mientras que otros no coinciden con un solo número.

Nota: Se incluye una implementación de K-means en scikit-learn (así como en muchos otros algoritmos de clúster y varias métricas de clustering ). Here hay otro ejemplo similar.

Answer 2

Una medida de clúster simple:
1) dibujar rayos "sunburst" desde cada punto hasta su centro de clúster más cercano,
2) observe las longitudes - distancia (punto, centro, métrica = ...) - de todos los rayos.

Para metric="sqeuclidean" y 1 clúster, la longitud-cuadrado promedio es la varianza total X.var() ; para 2 clusters, es menos ... hasta N clusters, longitudes 0. "El porcentaje de varianza explicado" es 100% - este promedio.

Código para esto, en @Denis :

def distancestocentres( X, centres, metric="euclidean", p=2 ):
    """ all distances X -> nearest centre, any metric
            euclidean2 (~ withinss) is more sensitive to outliers,
            cityblock (manhattan, L1) less sensitive
    """
    D = cdist( X, centres, metric=metric, p=p )  # |X| x |centres|
    return D.min(axis=1)  # all the distances

Como cualquier larga lista de números, estas distancias se pueden ver de varias maneras: np.mean (), np.histogram () ... Trazar, visualizar, no es fácil.
Ver también stats.stackexchange.com/questions/tagged/clustering , en particular
¿Cómo saber si los datos están "agrupados" lo suficiente para que los algoritmos de agrupamiento produzcan resultados significativos?