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
Descripción
lleva a cabo el cluster de k-medias para dividir las observaciones de la matriz de datos n por p idx
= kmeans(X
,k
)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.
devuelve los índices de cluster con más opciones especificadas por uno o más argumentos de par idx
= kmeans(X
,k
,Name,Value
)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.
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 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
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
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.
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
.
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. |
|
'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. |
|
'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. |
|
'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. |
donde
|
'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. |
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. |
'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
En este caso, utilice un arreglo de celdas del mismo tamaño que el grupo paralelo. Si un grupo paralelo no está abierto, |
'UseParallel' |
|
'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 Si el número de observaciones en la submuestra aleatoria del 10% es menor que |
'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:
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).Calcule las distancias del punto hasta el centroide del cluster de todas las observaciones de cada centroide.
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.
Calcule la media de observaciones en cada cluster para obtener k ubicaciones del centroide nuevas.
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.
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.
Calcula las distancias de todas las observaciones a c1. Indica la distancias entre cj y la observación de m como .
Selecciona el siguiente centroide, c2 aleatoriamente de X con probabilidad
Para seleccionar el centro j:
Calcula las distancias de cada observación para cada centroide y asigna cada observación a su centroide más cercano.
Para m = 1,...,n y p = 1,...,j – 1, selecciona el centroide j de manera aleatoria de X con probabilidad de
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.
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 dek
.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.
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 yStart
esplus
(el valor predeterminado), el software selecciona r conjuntos posiblemente diferentes de semillas según el algoritmo k-medias++.Si activa la opción
UseParallel
enOptions
yReplicates
> 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 porstatset
. El valor predeterminado de'TolFun'
es1e-4
. La funciónkmeans
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 deX
que contengan unNaN
.Las ubicaciones del centroide del cluster en
C
pueden tener un orden diferente que en MATLAB. En este caso, los índices de cluster enidx
tienen diferencias correspondientes.Si proporciona
Display
, su valor debe ser'off'
.Si proporciona
Streams
, debe estar vacío yUseSubstreams
debe serfalse
.Cuando establece la opción
UseParallel
entrue
:Algunos cálculos pueden ejecutarse en paralelo incluso cuando
Replicates
es1
. Para conjuntos de datos grandes, cuandoReplicates
es1
, considere establecer la opciónUseParallel
entrue
.kmeans
utilizaparfor
(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 buclesparfor
como buclesfor
. 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
ypdist2
, respectivamente. Utilicekmeans
para crear clusters en MATLAB y utilicepdist2
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).
Historial de versiones
Consulte también
linkage
| clusterdata
| silhouette
| parpool
(Parallel Computing Toolbox) | statset
| gmdistribution
| kmedoids
Abrir ejemplo
Tiene una versión modificada de este ejemplo. ¿Desea abrir este ejemplo con sus modificaciones?
Comando de MATLAB
Ha hecho clic en un enlace que corresponde a este comando de MATLAB:
Ejecute el comando introduciéndolo en la ventana de comandos de MATLAB. Los navegadores web no admiten comandos de MATLAB.
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)