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

Sintaxis

idx = kmeans(X,k)

idx = kmeans(X,k,Name,Value)

[idx,C] = kmeans(___)

[idx,C,sumd] = kmeans(___)

[idx,C,sumd,D] = kmeans(___)

Descripción

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.

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.

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

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

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

Ejemplos

Entrenar un algoritmo de cluster de k-medias

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

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;

Dividir los datos en dos clusters

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';

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

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

Agrupar datos con los cálculos paralelos

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.

Asignar nuevos datos a clusters existentes y generar código C/C++

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

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

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

X — Datos

matriz numérica

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

k — Número de clusters

entero positivo

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.

Display — Nivel de salida que mostrar

'off' (predeterminado) | 'final' | 'iter'

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'

Distance — Métrica de distancia

'sqeuclidean' (predeterminado) | 'cityblock' | 'cosine' | 'correlation' | 'hamming'

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 distancia	Descripción	Fórmula
'sqeuclidean'	Distancia euclidiana cuadrada (valor predeterminado). Cada centroide es la media de puntos en ese cluster.	$$d(x,c)=(x-c)(x-c{)}^{\prime }$$
'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)={\displaystyle \sum _{j=1}^p\left|x_j-c_j\right|}$$
'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)=1-\frac{xc\prime }{\sqrt{\left(x{x}^{\prime }\right)\left(cc\prime \right)}}$$
'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-\frac{\left(x-\overrightarrow{\overline{x}}\right){\left(c-\overrightarrow{\overline{c}}\right)}^{\prime }}{\sqrt{\left(x-\overrightarrow{\overline{x}}\right){\left(x-\overrightarrow{\overline{x}}\right)}^{\prime }}\sqrt{\left(c-\overrightarrow{\overline{c}}\right){\left(c-\overrightarrow{\overline{c}}\right)}^{\prime }}},$$ donde $$\overrightarrow{\overline{x}}=\frac{1}{p}\left({\displaystyle \sum _{j=1}^p{x}_j}\right){\overrightarrow{1}}_p$$ $$\overrightarrow{\overline{c}}=\frac{1}{p}\left({\displaystyle \sum _{j=1}^p{c}_j}\right){\overrightarrow{1}}_p$$ $${\overrightarrow{1}}_p$$ 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)=\frac{1}{p}{\displaystyle \sum }_{j=1}^{p}I\left\{x_j\ne y_j\right\},$$ en donde I es la función del indicador.

Ejemplo: 'Distance','cityblock'

EmptyAction — Acción a realizar si el cluster pierde todas las observaciones de miembro

'singleton' (predeterminado) | 'error' | 'drop'

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.

Valor	Descripció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'

MaxIter — Número máximo de iteraciones

100 (predeterminado) | entero positivo

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

OnlinePhase — Indicador de actualización online

'off' (predeterminado) | 'on'

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'

Options — Opciones para el algoritmo iterativo controlador para minimizar los criterios de ajuste

[] (predeterminado) | arreglo de estructura devuelto por statset

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

Campo	Descripció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

Replicates — Número de veces que repetir el cluster con nuevas posiciones iniciales del centroide del cluster

1 (predeterminado) | entero positivo

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

Start — Método para elegir las posiciones iniciales del centroide del cluster

'plus' (predeterminado) | 'cluster' | 'sample' | 'uniform' | matriz numérica | arreglo numérico

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.

Valor	Descripció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érica	Matriz 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érico	Arreglo 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

idx — Índices del cluster

vector columna numérico

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

C — Ubicaciones del centroide del cluster

matriz numérica

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.

sumd — Sumas del cluster interno de las distancias desde el punto hasta el centroide

vector columna numérico

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

D — Distancias desde cada punto a cada centroide

matriz numérica

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

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 c₁.

2. Calcula las distancias de todas las observaciones a c₁. Indica la distancias entre c_j y la observación de m como $$d\left(x_m,c_j\right)$$.

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

   $$\frac{d^2\left(x_m,c_1\right)}{{\displaystyle \sum }_{j=1}^n{d}^2\left(x_j,c_1\right)}.$$

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

      $$\frac{d^2\left(x_m,c_p\right)}{{\displaystyle \sum }_{\{h;x_h\in C_p\}}^{}{d}^2\left(x_h,c_p\right)},$$

      en donde C_p es el conjunto de todas las observaciones más cercanas al centroide c_p y x_m pertenece a C_p.

      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

Arreglos altos

Realice cálculos con arreglos que tienen más filas de las que caben en la memoria.

Notas y limitaciones de uso:

• Las sintaxis compatibles son:

  • idx = kmeans(X,k)

  • [idx,C] = kmeans(X,k)

  • [idx,C,sumd] = kmeans(X,k)

  • [___] = kmeans(___,Name,Value)

• Los argumentos de par de nombre valor compatibles y cualquier diferencia son:

  • 'Display': el valor predeterminado es 'iter'.

  • 'MaxIter'

  • 'Options': admite solo el campo 'TolFun' del arreglo de estructura creado por statset. El valor predeterminado de 'TolFun' es 1e-4. La función kmeans utiliza el valor de 'TolFun' como una tolerancia de finalización para las sumas del cluster interno de las distancias del punto al centroide. Por ejemplo, puede especificar 'Options',statset('TolFun',1e-8).

  • 'Replicates'

  • 'Start': solo es compatible con 'plus', 'sample' y un arreglo numérico.

Para obtener más información, consulte Arreglos altos para datos con memoria insuficiente.

Generación de código C/C++

Genere código C y C++ mediante MATLAB® Coder™.

Notas y limitaciones de uso:

• Si el método Start utiliza selecciones aleatorias, las posiciones del cluster de centroide inicial puede que no coincidan con MATLAB^®.

• Si el número de filas en X se fija, la generación de código no elimina las filas de X que contengan un NaN.

• Las ubicaciones del centroide del cluster en C pueden tener un orden diferente que en MATLAB. En este caso, los índices de cluster en idx tienen diferencias correspondientes.

• Si proporciona Display, su valor debe ser 'off'.

• Si proporciona Streams, debe estar vacío y UseSubstreams debe ser false.

• Cuando establece la opción UseParallel en true:

  • Algunos cálculos pueden ejecutarse en paralelo incluso cuando Replicates es 1. Para conjuntos de datos grandes, cuando Replicates es 1, considere establecer la opción UseParallel en true.

  • kmeans utiliza parfor (MATLAB Coder) para crear bucles que se ejecutan en paralelo en plataformas multinúcleo de memoria compartida ejecutables. Los bucles que se ejecutan en paralelo pueden ser más rápidos que los bucles que se ejecutan en un solo proceso. Si su compilador no es compatible con la interfaz de la aplicación de multiprocesamiento abierto (OpenMP) o desactiva la biblioteca OpenMP, MATLAB Coder™ trata los bucles parfor como bucles for. Para encontrar compiladores compatibles, consulte compiladores compatibles.

• Para ahorrar memoria en el dispositivo en el que implementa el código generado, puede separar el entrenamiento y la predicción con 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. Para ver un ejemplo, consulte Asignar nuevos datos a clusters existentes y generar código C/C++.

• A partir de la versión R2020a, kmeans devuelve un índice de tipo de valor entero (int32), en vez de índices de precisión doble, en código C/C++ independiente generado. Por lo tanto, la función permite un soporte de precisión simple más estricto cuando utiliza entradas de precisión simple. Para la generación de código MEX, la función sigue devolviendo índices de precisión doble para igualar el comportamiento de MATLAB.

Para obtener más información sobre la generación de código, consulte Introduction to Code Generation y General Code Generation Workflow.

Soporte paralelo automático

Acelere código mediante la ejecución automática de cálculo paralelo mediante Parallel Computing Toolbox™.

Para ejecutar en paralelo, especifique el argumento de nombre valor 'Options' en la llamada a esta función y establezca el campo 'UseParallel' de la estructura de las opciones en true con statset.

Por ejemplo: 'Options',statset('UseParallel',true)

Para obtener más información acerca del cálculo en paralelo, consulte Run MATLAB Functions with Automatic Parallel Support (Parallel Computing Toolbox).

Arreglos GPU

Acelere código mediante la ejecución en una unidad de procesamiento gráfico (GPU) mediante Parallel Computing Toolbox™.

Esta función es totalmente compatible con los arreglos de GPU. Para obtener más información, consulte Run MATLAB Functions on a GPU (Parallel Computing Toolbox).

Consulte también

linkage | clusterdata | silhouette | parpool (Parallel Computing Toolbox) | statset | gmdistribution | kmedoids

Temas

• Compare k-Means Clustering Solutions
• Introduction to k-Means Clustering

Introducido antes de R2006a

×

Abrir ejemplo

Tiene una versión modificada de este ejemplo. ¿Desea abrir este ejemplo con sus modificaciones?

No, sobrescribir la versión modificada Sí