Main Content

La traducción de esta página aún no se ha actualizado a la versión más reciente. Haga clic aquí para ver la última versión en inglés.

kmeans

Agrupamiento de k-medias

Descripción

ejemplo

idx = kmeans(X,k) lleva a cabo el agrupamiento de k-medias para dividir las observaciones de la matriz de datos n por p X en k grupos y devuelve un vector n por 1 (idx) que contiene los índices de grupo de cada observación. Las filas de X se corresponden con los puntos y las columnas se corresponden con variables.

De manera predeterminada, kmeans utiliza la métrica de distancia euclidiana cuadrada y el algoritmo k-medias++ para la inicialización del centro del grupo.

ejemplo

idx = kmeans(X,k,Name,Value) devuelve los índices de grupo con más opciones especificadas por uno o más argumentos de par Name,Value.

Por ejemplo, especifique la distancia del coseno, el número de veces que repetir el agrupamiento con nuevos valores iniciales o para utilizar cálculos paralelos.

ejemplo

[idx,C] = kmeans(___) devuelve las ubicaciones del centroide del grupo k en la matriz k por p, C.

ejemplo

[idx,C,sumd] = kmeans(___) devuelve las sumas dentro del grupo de las distancias del punto hasta el centroide en el vector k por 1, sumd.

ejemplo

[idx,C,sumd,D] = kmeans(___) devuelve las distancias desde cada punto hasta todos los centroides en la matriz n por k, D.

Ejemplos

contraer todo

Agrupe datos usando el agrupamiento de k-medias y, después, represente las regiones de grupos.

Cargue el conjunto de datos Iris de Fisher. Utilice las longitudes y anchuras de los pétalos como predictores.

load fisheriris
X = meas(:,3:4);

figure;
plot(X(:,1),X(:,2),'k*','MarkerSize',5);
title 'Fisher''s Iris Data';
xlabel 'Petal Lengths (cm)'; 
ylabel 'Petal Widths (cm)';

Figure contains an axes object. The axes object with title Fisher's Iris Data, xlabel Petal Lengths (cm), ylabel Petal Widths (cm) contains a line object which displays its values using only markers.

El mayor grupo parece estar dividido en una región de variaciones menor y otra mayor. Esto podría indicar que el grupo más grande son dos grupos superpuestos.

Agrupe los datos. Especifique k = 3 grupos.

rng(1); % For reproducibility
[idx,C] = kmeans(X,3);

idx es un vector de índices de grupos pronosticados que se corresponde con las observaciones en X. C es una matriz 3 por 2 que contiene las ubicaciones finales de los centroides.

Utilice kmeans para calcular la distancia de cada centroide a los puntos en una cuadrícula. Para hacerlo, pase los centroides (C) y los puntos en una cuadrícula a kmeans e implemente una iteración del algoritmo.

x1 = min(X(:,1)):0.01:max(X(:,1));
x2 = min(X(:,2)):0.01:max(X(:,2));
[x1G,x2G] = meshgrid(x1,x2);
XGrid = [x1G(:),x2G(:)]; % Defines a fine grid on the plot

idx2Region = kmeans(XGrid,3,'MaxIter',1,'Start',C);
Warning: Failed to converge in 1 iterations.
    % Assigns each node in the grid to the closest centroid

kmeans muestra una advertencia indicando que el algoritmo no ha convergido, lo cual es de esperar ya que el software solo ha implementado una iteración.

Represente las regiones de grupos.

figure;
gscatter(XGrid(:,1),XGrid(:,2),idx2Region,...
    [0,0.75,0.75;0.75,0,0.75;0.75,0.75,0],'..');
hold on;
plot(X(:,1),X(:,2),'k*','MarkerSize',5);
title 'Fisher''s Iris Data';
xlabel 'Petal Lengths (cm)';
ylabel 'Petal Widths (cm)'; 
legend('Region 1','Region 2','Region 3','Data','Location','SouthEast');
hold off;

Figure contains an axes object. The axes object with title Fisher's Iris Data, xlabel Petal Lengths (cm), ylabel Petal Widths (cm) contains 4 objects of type line. One or more of the lines displays its values using only markers These objects represent Region 1, Region 2, Region 3, Data.

Genere de manera aleatoria los datos de muestra.

rng default; % For reproducibility
X = [randn(100,2)*0.75+ones(100,2);
    randn(100,2)*0.5-ones(100,2)];

figure;
plot(X(:,1),X(:,2),'.');
title 'Randomly Generated Data';

Figure contains an axes object. The axes object with title Randomly Generated Data contains a line object which displays its values using only markers.

Parece que hay dos grupos en los datos.

Divida los datos en dos grupos y seleccione el mejor arreglo de las cinco inicializaciones. Muestre el resultado final.

opts = statset('Display','final');
[idx,C] = kmeans(X,2,'Distance','cityblock',...
    'Replicates',5,'Options',opts);
Replicate 1, 3 iterations, total sum of distances = 201.533.
Replicate 2, 5 iterations, total sum of distances = 201.533.
Replicate 3, 3 iterations, total sum of distances = 201.533.
Replicate 4, 3 iterations, total sum of distances = 201.533.
Replicate 5, 2 iterations, total sum of distances = 201.533.
Best total sum of distances = 201.533

De manera predeterminada, el software inicia las réplicas por separado utilizando k-medias++.

Represente los grupos y sus centroides.

figure;
plot(X(idx==1,1),X(idx==1,2),'r.','MarkerSize',12)
hold on
plot(X(idx==2,1),X(idx==2,2),'b.','MarkerSize',12)
plot(C(:,1),C(:,2),'kx',...
     'MarkerSize',15,'LineWidth',3) 
legend('Cluster 1','Cluster 2','Centroids',...
       'Location','NW')
title 'Cluster Assignments and Centroids'
hold off

Figure contains an axes object. The axes object with title Cluster Assignments and Centroids contains 3 objects of type line. One or more of the lines displays its values using only markers These objects represent Cluster 1, Cluster 2, Centroids.

Se puede determinar la separación de los grupos pasando idx a silhouette.

Agrupar grandes conjuntos de datos puede llevar mucho tiempo, particularmente si utiliza las actualizaciones online (establecidas de manera predeterminada). Si tiene una licencia de Parallel Computing Toolbox™ y establece las opciones para realizar cálculos paralelos, kmeans ejecuta (o replica) cada tarea de agrupamiento en paralelo. Y, si Replicates >1, los cálculos paralelos reducen el tiempo de convergencia.

Genere de manera aleatoria un gran conjunto de datos de un modelo de mezcla gausiano.

rng(1); % For reproducibility
Mu = ones(20,30).*(1:20)'; % Gaussian mixture mean
rn30 = randn(30,30);
Sigma = rn30'*rn30; % Symmetric and positive-definite covariance
Mdl = gmdistribution(Mu,Sigma); % Define the Gaussian mixture distribution

X = random(Mdl,10000);

Mdl es un modelo gmdistribution de 30 dimensiones con 20 componentes. X es una matriz de datos 10000 por 30 generada de Mdl.

Especifique las opciones de cálculos paralelos.

stream = RandStream('mlfg6331_64');  % Random number stream
options = statset('UseParallel',1,'UseSubstreams',1,...
    'Streams',stream);

El argumento de entrada 'mlfg6331_64' de RandStream especifica el uso del algoritmo de generación de Fibonacci retardado multiplicativo. options es un arreglo de estructura con campos que especifican opciones para controlar la estimación.

Agrupe los datos usando el agrupamiento de k-medias. Especifique que hay k = 20 grupos en los datos y aumente el número de iteraciones. Típicamente, la función objetivo contiene unos mínimos locales. Especifique 10 réplicas para ayudar a encontrar un mínimo local inferior.

tic; % Start stopwatch timer
[idx,C,sumd,D] = kmeans(X,20,'Options',options,'MaxIter',10000,...
    'Display','final','Replicates',10);
Starting parallel pool (parpool) using the 'Processes' profile ...
Connected to the parallel pool (number of workers: 6).
Replicate 4, 79 iterations, total sum of distances = 7.62412e+06.
Replicate 2, 56 iterations, total sum of distances = 7.62036e+06.
Replicate 3, 76 iterations, total sum of distances = 7.62583e+06.
Replicate 6, 96 iterations, total sum of distances = 7.6258e+06.
Replicate 5, 103 iterations, total sum of distances = 7.61753e+06.
Replicate 1, 94 iterations, total sum of distances = 7.60746e+06.
Replicate 10, 66 iterations, total sum of distances = 7.62582e+06.
Replicate 8, 113 iterations, total sum of distances = 7.60741e+06.
Replicate 9, 80 iterations, total sum of distances = 7.60592e+06.
Replicate 7, 77 iterations, total sum of distances = 7.61939e+06.
Best total sum of distances = 7.60592e+06
toc % Terminate stopwatch timer
Elapsed time is 72.873647 seconds.

La ventana de comandos indica que hay disponibles seis workers. El número de workers puede variar en su sistema. La ventana de comandos muestra el número de iteraciones y el valor de la función objetivo terminal para cada réplica. Los argumentos de salida contienen los resultados de la réplica 9 porque tiene la menor suma total de distancias.

kmeans lleva a cabo agrupamiento de k-medias para dividir datos en k grupos. Cuando tenga un nuevo conjunto de datos que agrupar, puede crear nuevos grupos que incluyan los datos existentes y los nuevos datos utilizando kmeans. La función kmeans es compatible con la generación de código C/C++, de modo que puede generar código que acepte los datos de entrenamiento, devuelva los resultados del agrupamiento y, después, implemente el código en un dispositivo. En este flujo de trabajo, debe pasar los datos de entrenamiento, que pueden tener un tamaño considerable. Para ahorrar memoria en el dispositivo, puede separar el entrenamiento y la predicción por uso de kmeans y pdist2, respectivamente.

Utilice kmeans para crear grupos en MATLAB® y utilice pdist2 en el código generado para asignar nuevos datos a grupos existentes. Para la generación de código, defina una función de punto de entrada que acepte las posiciones de los centroides de los grupos y el nuevo conjunto de datos, y devuelva el índice del grupo más cercano. Después, genere código para la función de punto de entrada.

Generar código C/C++ requiere MATLAB® Coder™.

Llevar a cabo agrupamiento de k-medias

Genere un conjunto de datos de entrenamiento con tres distribuciones.

rng('default') % For reproducibility
X = [randn(100,2)*0.75+ones(100,2);
    randn(100,2)*0.5-ones(100,2);
    randn(100,2)*0.75];

Divida los datos de entrenamiento en tres grupos con kmeans.

[idx,C] = kmeans(X,3);

Represente los grupos y sus centroides.

figure
gscatter(X(:,1),X(:,2),idx,'bgm')
hold on
plot(C(:,1),C(:,2),'kx')
legend('Cluster 1','Cluster 2','Cluster 3','Cluster Centroid')

Figure contains an axes object. The axes object contains 4 objects of type line. One or more of the lines displays its values using only markers These objects represent Cluster 1, Cluster 2, Cluster 3, Cluster Centroid.

Asignar nuevos datos a grupos existentes

Genere un conjunto de datos de prueba.

Xtest = [randn(10,2)*0.75+ones(10,2);
    randn(10,2)*0.5-ones(10,2);
    randn(10,2)*0.75];

Clasifique el conjunto de datos de prueba usando los grupos existentes. Encuentre el centroide más cercano de cada punto de datos de prueba con pdist2.

[~,idx_test] = pdist2(C,Xtest,'euclidean','Smallest',1);

Represente los datos de prueba y etiquete los datos de prueba con idx_test utilizando gscatter.

gscatter(Xtest(:,1),Xtest(:,2),idx_test,'bgm','ooo')
legend('Cluster 1','Cluster 2','Cluster 3','Cluster Centroid', ...
    'Data classified to Cluster 1','Data classified to Cluster 2', ...
    'Data classified to Cluster 3')

Figure contains an axes object. The axes object contains 7 objects of type line. One or more of the lines displays its values using only markers These objects represent Cluster 1, Cluster 2, Cluster 3, Cluster Centroid, Data classified to Cluster 1, Data classified to Cluster 2, Data classified to Cluster 3.

Generar código

Genere código C que asigne nuevos datos a los grupos existentes. Tenga en cuenta que generar código C/C++ requiere MATLAB® Coder™.

Defina una función de punto de entrada llamada findNearestCentroid que acepte las posiciones de los centroides y nuevos datos, y encuentre el grupo más cercano con pdist2.

Añada la directiva del compilador (o pragma) %#codegen a la función de punto de entrada después de la firma de la función para indicar que intenta generar código para el algoritmo de MATLAB. Añadir esta directiva instruye al analizador de código de MATLAB para ayudarle a diagnosticar y arreglar brechas que provocarían errores durante la generación de código.

type findNearestCentroid % Display contents of findNearestCentroid.m
function idx = findNearestCentroid(C,X) %#codegen
[~,idx] = pdist2(C,X,'euclidean','Smallest',1); % Find the nearest centroid

Nota: si hace clic en el botón ubicado en la zona superior derecha de esta página y abre este ejemplo en MATLAB®, MATLAB® abrirá la carpeta de ejemplo. Esta carpeta incluye el archivo de función de punto de entrada.

Genere código mediante codegen (MATLAB Coder). Dado que C y C++ son lenguajes de tipado estático, debe determinar las propiedades de todas las variables de la función de entrada en tiempo de compilación. Para especificar los tipos de datos y el tamaño de arreglo de las entradas de findNearestCentroid, pase una expresión de MATLAB que represente el conjunto de valores con un tipo de datos y un tamaño de arreglo determinado con la opción -args. Para obtener más detalles, consulte Specify Variable-Size Arguments for Code Generation.

codegen findNearestCentroid -args {C,Xtest}
Code generation successful.

codegen genera la función MEX de findNearestCentroid_mex con una extensión dependiente de la plataforma.

Compruebe el código generado.

myIndx = findNearestCentroid(C,Xtest);
myIndex_mex = findNearestCentroid_mex(C,Xtest);
verifyMEX = isequal(idx_test,myIndx,myIndex_mex)
verifyMEX = logical
   1

isequal devuelve una lógica 1 (true), que implica que todas las entradas son iguales. La comparación confirma que la función pdist2, la función findNearestCentroid y la función MEX vuelven al mismo índice.

También puede generar código optimizado CUDA® con GPU Coder™.

cfg = coder.gpuConfig('mex');
codegen -config cfg findNearestCentroid -args {C,Xtest}

Para obtener más información sobre generación de código, consulte General Code Generation Workflow. Para obtener más información sobre GPU coder, consulte Get Started with GPU Coder (GPU Coder) y Supported Functions (GPU Coder).

Argumentos de entrada

contraer todo

Datos, especificados como matriz numérica. Las filas de X corresponden a observaciones y las columnas corresponden a variables.

Si X es un vector numérico, kmeans lo trata como una matriz de datos n por 1, independientemente de la orientación.

El software trata NaN en X como datos faltantes y elimina cualquier fila de X que contiene al menos un NaN. Eliminar filas de X reduce el tamaño de la muestra. La función kmeans devuelve NaN para el valor correspondiente en el argumento idx de salida.

Tipos de datos: single | double

Número de grupos en los datos, especificado como un entero positivo.

Tipos de datos: single | double

Argumentos de par nombre-valor

Especifique pares de argumentos opcionales Name1=Value1,...,NameN=ValueN, donde Name es el nombre del argumento y Value es el valor correspondiente. Los argumentos nombre-valor deben aparecer después de otros argumentos, pero el orden de los pares no importa.

En versiones anteriores a R2021a, use comas para separar cada nombre y valor y encierre Name entre comillas.

Ejemplo: 'Distance','cosine','Replicates',10,'Options',statset('UseParallel',1) especifica la distancia del coseno, 10 replica los grupos en diferentes valores iniciales y para utilizar cálculos paralelos.

Nivel de salida que mostrar en la Ventana de comandos, especificado como el par separado por comas que consta de 'Display' y una de las siguientes opciones:

  • 'final': muestra los resultados de la iteración final

  • 'iter': muestra los resultados de cada iteración

  • 'off': no muestra nada

Ejemplo: 'Display','final'

Métrica de distancia, en espacio p-dimensional, que se utilizó para la minimización, especificada como el par separado por comas que consta de 'Distance' y 'sqeuclidean', 'cityblock', 'cosine', 'correlation' o 'hamming'.

kmeans procesa los grupos del centroide de manera diferente para las métricas de distancia compatibles. La siguiente tabla resume las métricas de distancias disponibles. En las fórmulas, x es una observación (es decir, una fila de X) y c es un centroide (un vector fila).

Métrica de distanciaDescripciónFórmula
'sqeuclidean'

Distancia euclidiana cuadrada (valor predeterminado). Cada centroide es la media de puntos en ese grupo.

d(x,c)=(xc)(xc)

'cityblock'

Suma de las diferencias absolutas, es decir, la distancia L1. Cada centroide es la media relacionada con los componentes de los puntos en ese grupo.

d(x,c)=j=1p|xjcj|

'cosine'

Uno menos el coseno del ángulo incluido entre puntos (tratados como vectores). Cada centroide es la media de puntos en ese grupo, después de normalizar esos puntos en una unidad de longitud euclidiana.

d(x,c)=1xc(xx)(cc)

'correlation'

Uno menos la correlación de la muestra entre los puntos (tratados como secuencias de valores). Cada centroide es la media por componentes de los puntos en ese grupo, después de centrar y normalizar esos puntos a una media de cero y una desviación estándar de la unidad.

d(x,c)=1(xx¯)(cc¯)(xx¯)(xx¯)(cc¯)(cc¯),

donde

  • x¯=1p(j=1pxj)1p

  • c¯=1p(j=1pcj)1p

  • 1p es un vector fila de p unos.

'hamming'

Esta métrica es solo adecuada para datos binarios.

Es la proporción de bits lo que cambia. Cada centroide es la media relacionada con los componentes de puntos en ese grupo.

d(x,y)=1pj=1pI{xjyj},

en donde I es la función del indicador.

Ejemplo: 'Distance','cityblock'

Acción a realizar si un grupo pierde todas sus observaciones de miembro, especificada como el par separado por comas que consta de 'EmptyAction' y una de las siguientes opciones.

ValorDescripción
'error'

Trata un grupo vacío como un error.

'drop'

Elimina cualquier grupo que se queda vacío. kmeans establece los valores de devolución correspondientes en C y D como NaN.

'singleton'

Crea un nuevo grupo que consta del punto más alejado de su centroide (predeterminado).

Ejemplo: 'EmptyAction','error'

Número máximo de iteraciones, especificado como el par separado por comas que consta de 'MaxIter' y un entero positivo.

Ejemplo: 'MaxIter',1000

Tipos de datos: double | single

Indicador de actualización online, especificado como el par separado por comas que consta de 'OnlinePhase' y 'off' o 'on'.

Si OnlinePhase es on, kmeans actúa como una fase de actualización online además de una fase de actualización del lote. La fase online puede consumir mucho tiempo para grandes conjuntos de datos, pero garantiza una solución que es un mínimo local del criterio de distancia. En otras palabras, el software encuentra una partición de los datos en la que mover cualquier punto a un grupo diferente aumenta la suma total de distancias.

Ejemplo: 'OnlinePhase','on'

Opciones para controlar el algoritmo iterativo para minimizar los criterios de ajuste, especificado como el par separado por comas que consta de 'Options' y un arreglo de estructura devuelto por statset. Los campos compatibles del arreglo de la estructura especifican las opciones de control del algoritmo iterativo.

Esta tabla resume los campos compatibles. Tenga en cuenta que los campos compatibles precisan Parallel Computing Toolbox™.

CampoDescripción
'Streams'

Un objeto de RandStream o arreglo de celdas de dichos objetos. Si no especifica Streams, kmeans utiliza la secuencia o secuencias predeterminadas. Si especifica Streams, utilice un solo objeto excepto cuando todas las siguientes condiciones existan:

  • Tiene un grupo paralelo abierto.

  • UseParallel es true.

  • UseSubstreams es false.

En este caso, utilice un arreglo de celdas del mismo tamaño que el grupo paralelo. Si un grupo paralelo no está abierto, Streams debe proporcionar una secuencia de números aleatorios única.

'UseParallel'
  • Si true y Replicates > 1, kmeans implementa el algoritmo de k-medias en cada réplica en paralelo.

  • Si Parallel Computing Toolbox no se ha instalado, el cálculo se produce en serie. El valor predeterminado es false, lo que indica cálculo en serie.

'UseSubstreams'Establezca el valor en true para calcular en paralelo de una manera que se pueda reproducir. El valor predeterminado es false. Para calcular de una manera que se pueda reproducir, establezca Streams en un tipo que permita subsecuencias: 'mlfg6331_64' o 'mrg32k3a'.

Para garantizar unos resultados más predecibles, utilice parpool (Parallel Computing Toolbox) y cree de manera explícita un grupo paralelo antes de invocar kmeans y establecer 'Options',statset('UseParallel',1).

Ejemplo: 'Options',statset('UseParallel',1)

Tipos de datos: struct

Número de veces que repetir el agrupamiento con nuevas posiciones iniciales del centroide del grupo, especificado como el par separado por comas que consta de 'Replicates' y un valor entero. kmeans devuelve la solución con la sumd más baja.

Puede establecer 'Replicates' de manera implícita proporcionando un arreglo 3D como el valor para el argumento de par nombre-valor 'Start'.

Ejemplo: 'Replicates',5

Tipos de datos: double | single

Método para elegir las posiciones iniciales del centroide del grupo (o semillas), especificado como el par separado por comas que consta de 'Start' y 'cluster', 'plus', 'sample', 'uniform', una matriz numérica o un arreglo numérico. Esta tabla resume las opciones disponibles para elegir semillas.

ValorDescripción
'cluster'

Lleva a cabo una fase de agrupamiento preliminar en una submuestra aleatoria del 10% de X cuando el número de observaciones en la submuestra sea superior a k. Esta fase preliminar se inicializa a su vez con 'sample'.

Si el número de observaciones en la submuestra aleatoria del 10% es menor que k, el software selecciona k observaciones de X de forma aleatoria.

'plus' (valor predeterminado)Selecciona k semillas implementando el algoritmo de k-medias++ para la inicialización del centro del grupo.
'sample'Selecciona k observaciones de X de manera aleatoria.
'uniform'Selecciona k puntos de modo uniforme de manera aleatoria desde el rango de X. No válido con la distancia de Hamming.
matriz numéricaMatriz k por p de las ubicaciones iniciales del centroide. Las filas de Start se corresponden con las semillas. El software infiere k de la primera dimensión de Start, para que pueda pasar [] por k.
arreglo numéricoArreglo k por p por r de las ubicaciones iniciales del centroide. Las filas de cada página se corresponden con las semillas. La tercera dimensión invoca la replicación de la rutina de agrupamiento. La página j contiene el conjunto de semillas para replicar j. El software infiere el número de réplicas (especificado por el argumento de par nombre-valor 'Replicates') del tamaño de la tercera dimensión.

Ejemplo: 'Start','sample'

Tipos de datos: char | string | double | single

Argumentos de salida

contraer todo

Índices de grupo, devueltos como un vector columna numérico. idx tiene tantas filas como X y cada fila indica la asignación de grupo de cada observación correspondiente.

Ubicaciones del centroide del grupo, devueltas como una matriz numérica. C es una matriz k por p, en la que la fila j es el centroide del grupo j. La localización de un centroide depende de la métrica de distancia especificada por el argumento nombre-valor Distance.

Sumas dentro del grupo de las distancias del punto hasta el centroide, devueltas como un vector columna numérico. sumd es un vector k por 1, donde el elemento j es la suma de las distancias del punto hasta el centro dentro del grupo j. De manera predeterminada, kmeans utiliza la distancia euclidiana cuadrada (consulte las métricas de 'Distance').

Distancias desde cada punto a cada centroide, devueltas como una matriz numérica. D es una matriz n por k, donde el elemento (j,m) es la distancia desde la observación j hasta el centroide m. De manera predeterminada, kmeans utiliza la distancia euclidiana cuadrada (consulte las métricas de 'Distance').

Más acerca de

contraer todo

Agrupamiento de k-medias

El agrupamiento de k-medias, o algoritmo de Lloyd [2], es un algoritmo de división de datos iterativo que asigna n observaciones a exactamente uno de k grupos definido por los centroides, donde k se selecciona antes de que comience el algoritmo.

El algoritmo procede de la siguiente manera:

  1. Elige k centros de grupos iniciales (centroide). Por ejemplo, selecciona k observaciones de manera aleatoria (utilizando 'Start','sample') o utiliza el algoritmo de k-medias ++ para la inicialización del centro del grupo (predeterminado).

  2. Calcula las distancias del punto hasta el centroide del grupo de todas las observaciones de cada centroide.

  3. Existen dos maneras de proceder (especificadas por OnlinePhase):

    • Actualización por lotes: asigna cada observación al grupo con el centroide más cercano.

    • Actualización en línea: asigna de forma individual observaciones a un centroide diferente si la reasignación reduce la suma dentro del grupo, la suma de los cuadrados de las distancias del punto al centroide del grupo.

    Para obtener más información, consulte Algoritmos.

  4. Calcula la media de observaciones en cada grupo para obtener k ubicaciones de centroides nuevas.

  5. Repite los pasos 2 a 4 hasta que las asignaciones de grupos no cambien o se alcance el número máximo de iteraciones.

Algoritmo de k-medias++

El algoritmo de k-medias++ utiliza una heurística para encontrar las semillas del centroide para el agrupamiento de k-medias. Según Arthur y Vassilvitskii [1], k-medias ++ mejora el tiempo de ejecución del algoritmo de Lloyd y la calidad de la solución final.

El algoritmo de k-medias++ selecciona semillas de la siguiente manera, asumiendo que el número de grupos es k.

  1. Selecciona una observación de manera uniforme aleatoriamente del conjunto de datos, X. La observación elegida es el primer centroide y se indica con c1.

  2. Calcula las distancias de todas las observaciones a c1. Indica la distancias entre cj y la observación de m como d(xm,cj).

  3. Selecciona el siguiente centroide, c2 aleatoriamente de X con probabilidad

    d2(xm,c1)j=1nd2(xj,c1).

  4. Para seleccionar el centro j:

    1. Calcula las distancias de cada observación para cada centroide y asigna cada observación a su centroide más cercano.

    2. Para m = 1,...,n y p = 1,...,j – 1, selecciona el centroide j de manera aleatoria de X con probabilidad de

      d2(xm,cp){h;xhCp}d2(xh,cp),

      en donde Cp es el conjunto de todas las observaciones más cercanas al centroide cp y xm pertenece a Cp.

      Es decir, selecciona cada centro subsiguiente con una probabilidad proporcional a la distancia desde el mismo hasta el centro más cercano que usted ya haya elegido.

  5. Repite el paso 4 hasta que se hayan elegido k centroides.

Arthur y Vassilvitskii [1] demuestran, con un estudio de simulación para varias orientaciones de grupos, que k-medias++ logra una convergencia más rápida para una suma inferior dentro del grupo, la suma de los cuadrados de las distancias del punto hasta el centroide del grupo, que el algoritmo de Lloyd.

Algoritmos

  • kmeans utiliza un algoritmo iterativo de dos fases para minimizar la suma de las distancias del punto al centroide, sumadas en todos los k grupos.

    1. Esta primera fase utiliza actualizaciones por lotes, donde cada iteración consiste en la reasignación de puntos a su centroide de grupo más cercano, todos a la vez, seguida de un nuevo cálculo de los centroides de los grupos. Esta fase en ocasiones no converge a la solución que es un mínimo local. Es decir, una partición de los datos en la que mover cualquier punto a un grupo diferente aumenta la suma total de distancias. Esto es más probable para los conjuntos de datos pequeños. La fase de lotes es rápida, pero potencialmente solo se aproxima a una solución como punto de partida para la segunda fase.

    2. Esta segunda fase utiliza actualizaciones en línea, donde los puntos se asignan de manera individual si haciéndolo se reduce la suma de las distancias y los centroides de los grupos se calculan de nuevo después de cada nueva asignación. Cada iteración de esta fase consiste en una pasada por todos los puntos. Esta fase converge en un mínimo local, aunque puede haber otros mínimos locales con una suma total inferior de las distancias. En general, la búsqueda del mínimo global se resuelve mediante una elección exhaustiva de los puntos iniciales, pero el uso de varias réplicas con puntos de partida aleatorios suele dar como resultado una solución que es un mínimo global.

  • Si Replicates = r > 1 y Start es plus (el valor predeterminado), el software selecciona r conjuntos posiblemente diferentes de semillas según el algoritmo k-medias++.

  • Si activa la opción UseParallel en Options y Replicates > 1, entonces cada worker selecciona las semillas y los grupos en paralelo.

Referencias

[1] Arthur, David, and Sergi Vassilvitskii. “K-means++: The Advantages of Careful Seeding.” SODA ‘07: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. 2007, pp. 1027–1035.

[2] Lloyd, Stuart P. “Least Squares Quantization in PCM.” IEEE Transactions on Information Theory. Vol. 28, 1982, pp. 129–137.

[3] Seber, G. A. F. Multivariate Observations. Hoboken, NJ: John Wiley & Sons, Inc., 1984.

[4] Spath, H. Cluster Dissection and Analysis: Theory, FORTRAN Programs, Examples. Translated by J. Goldschmidt. New York: Halsted Press, 1985.

Capacidades ampliadas

Historial de versiones

Introducido antes de R2006a