Main Content

La traducción de esta página está obsoleta. Haga clic aquí para ver la última versión en inglés.

kmeans

Cluster de k-medias

Descripción

ejemplo

idx = kmeans(X,k) lleva a cabo el cluster de k-medias para dividir las observaciones de la matriz de datos n por p X en clusters k y devuelve un vector n por 1 (idx) que contiene los índices de cluster 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 cluster.

ejemplo

idx = kmeans(X,k,Name,Value) devuelve los índices de cluster 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 clustering con nuevos valores iniciales o para utilizar cálculos paralelos.

ejemplo

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

ejemplo

[idx,C,sumd] = kmeans(___) devuelve las sumas del cluster interno 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 con el cluster de k-medias y, después, represente las regiones del cluster.

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. The axes with title Fisher's Iris Data contains an object of type line.

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

Agrupe los datos. Especifique k = 3 clusters.

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

idx es un vector de índices de cluster pronosticado que se corresponde con las observaciones en X. C es una matriz 3 por 2 que contiene las ubicaciones finales del centroide.

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 del cluster.

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. The axes with title Fisher's Iris Data contains 4 objects of type line. 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. The axes with title Randomly Generated Data contains an object of type line.

Parece que hay dos clusters en los datos.

Divida los datos en dos clusters 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 clusters y los centroides del cluster.

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. The axes with title Cluster Assignments and Centroids contains 3 objects of type line. These objects represent Cluster 1, Cluster 2, Centroids.

Se puede determinar la separación de los clusters 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 los cálculos paralelos, kmeans ejecuta (o replica) cada tarea de clustering 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.

Mu = bsxfun(@times,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

rng(1); % For reproducibility
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 con clusters de k-medias. Especifique que hay k = 20 clusters 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 'local' profile ...
connected to 6 workers.
Replicate 5, 72 iterations, total sum of distances = 7.73161e+06.
Replicate 1, 64 iterations, total sum of distances = 7.72988e+06.
Replicate 3, 68 iterations, total sum of distances = 7.72576e+06.
Replicate 4, 84 iterations, total sum of distances = 7.72696e+06.
Replicate 6, 82 iterations, total sum of distances = 7.73006e+06.
Replicate 7, 40 iterations, total sum of distances = 7.73451e+06.
Replicate 2, 194 iterations, total sum of distances = 7.72953e+06.
Replicate 9, 105 iterations, total sum of distances = 7.72064e+06.
Replicate 10, 125 iterations, total sum of distances = 7.72816e+06.
Replicate 8, 70 iterations, total sum of distances = 7.73188e+06.
Best total sum of distances = 7.72064e+06
toc % Terminate stopwatch timer
Elapsed time is 61.915955 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 clusters k-medias para dividir datos en k clusters. Cuando tenga un nuevo conjunto de datos, puede crear nuevos clusters 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++, para que pueda generar código que acepte los datos de entrenamiento, devuelva los resultados del cluster 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 clusters en MATLAB® y utilice pdist2 en el código generado para asignar nuevos datos a clusters existentes. Para la generación de código, defina una función de punto de entrada que acepte las posiciones del centroide del cluster y el nuevo conjunto de datos, y devuelva el índice del cluster 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 cluster 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 clusters con kmeans.

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

Represente los clusters y los centroides del cluster.

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. The axes contains 4 objects of type line. These objects represent Cluster 1, Cluster 2, Cluster 3, Cluster Centroid.

Asignar nuevos datos a clusters 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 con los cluster 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. The axes contains 7 objects of type line. 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 clusters 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 del centroide y nuevos datos, y encuentre el cluster 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 del 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 clusters en los datos, especificado como un entero positivo.

Tipos de datos: single | double

Argumentos de par nombre-valor

Especifique pares opcionales separados por comas de argumentos Name,Value. Name es el nombre del argumento y Value es el valor correspondiente. Name debe aparecer entre comillas. Puede especificar varios argumentos de par nombre-valor en cualquier orden como Name1,Value1,...,NameN,ValueN.

Ejemplo: 'Distance','cosine','Replicates',10,'Options',statset('UseParallel',1) especifica la distancia del coseno, 10 replica los clusters 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 clusters 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 cluster.

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 cluster.

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 cluster, 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 relacionada con el componente de los puntos en ese cluster, 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 cluster.

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

en donde I es la función del indicador.

Ejemplo: 'Distance','cityblock'

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

ValorDescripción
'error'

Trata un cluster vacío como un error.

'drop'

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

'singleton'

Crea un nuevo cluster 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 cluster 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 cluster con nuevas posiciones iniciales del centroide del cluster, especificadas 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 cluster (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 clustering 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 cluster.
'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 clustering. 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 del cluster, devueltos como un vector columna numérico. idx tiene tantas filas como X y cada fila indica la asignación del cluster de cada observación correspondiente.

Ubicaciones del centroide del cluster, devueltas como una matriz numérica. C es una matriz k por p, en la que la fila j es el centroide del cluster j.

Sumas dentro del cluster 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 cluster 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

Cluster de k-medias

Clusters 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 clusters definido por los centroides, donde k se selecciona antes de que comience el algoritmo.

El algoritmo procede de la siguiente manera:

  1. Elija k centros de cluster iniciales (centroide). Por ejemplo, seleccione k observaciones de manera aleatoria (utilizando 'Start','sample') o utilice el algoritmo de k-medias ++ para la inicialización del centro del cluster (el valor predeterminado).

  2. Calcule las distancias del punto hasta el centroide del cluster de todas las observaciones de cada centroide.

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

    • Actualización del lote: asigne cada observación al cluster con el centroide más cercano.

    • Actualización online: asigne de forma individual observaciones a un centroide diferente si la reasignación reduce la suma del cluster interno, la suma de los cuadrados de las distancias del centroide del cluster.

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

  4. Calcule la media de observaciones en cada cluster para obtener k ubicaciones del centroide nuevas.

  5. Repita los pasos 2 a 4 hasta que las asignaciones del cluster 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 clusters 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 clusters 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 elijan los centroides de k.

Arthur y Vassilvitskii [1] demuestran, con un estudio de simulación para varias orientaciones de cluster, que k-medias++ logra una convergencia más rápida para una suma inferior del cluster interior, la suma de los cuadrados de las distancias del punto hasta el centroide del cluster 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, sumado en todos los clusters de k.

    1. Esta primera fase utiliza actualizaciones de lote, donde cada iteración consta de puntos de reasignación a su centroide de cluster más cercano, a la vez, seguido de un nuevo cálculo de los centroides del cluster. 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 cluster 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. La segunda fase utiliza actualizaciones online. donde los puntos se asignan de manera individual si al hacerlo se reduce la suma de las distancias y los centroides del cluster 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, después cada worker selecciona las semillas y los clusters 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

Introducido antes de R2006a