Main Content

Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

kmeans

-significa agrupación en clústeresk

Descripción

ejemplo

idx = kmeans(X,k) Realiza -significa agrupación en clústeresk para dividir las observaciones de la matriz de datos -by- en clústeres, y devuelve un vector -by-1 ( ) que contiene índices de clúster de cada observación.npXknidx Las filas de corresponden a puntos y columnas corresponden a variables.X

De forma predeterminada, utiliza la métrica de distancia euclidiana cuadrada y lakmeans -means++ algoritmok para la inicialización del centro de clúster.

ejemplo

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

Por ejemplo, especifique la distancia del coseno, el número de veces que se repetirá la agrupación en clústeres utilizando nuevos valores iniciales o para utilizar la informática paralela.

ejemplo

[idx,C] = kmeans(___) devuelve las ubicaciones centroide del clúster en la matriz -by-.kkpC

ejemplo

[idx,C,sumd] = kmeans(___) devuelve las sumas dentro del clúster de distancias punto a centroide en el vector -by-1 .ksumd

ejemplo

[idx,C,sumd,D] = kmeans(___) devuelve distancias de cada punto a cada centroide en la matriz -by-.nkD

Ejemplos

contraer todo

Los datos del clúster mediante la agrupación en clústeres -means y, a continuación, trazan las regiones del clúster.k

Cargue el conjunto de datos de 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 clúster más grande parece dividirse en una región de varianza inferior y una región de varianza más alta. Esto podría indicar que el clúster más grande es dos clústeres superpuestos.

Enclúster los datos. Especifique 3 clústeres.k

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

utiliza el algoritmo -means++ para la inicialización centroide y la distancia euclidiana cuadrada de forma predeterminada.kmeansk Se recomienda buscar mínimos locales más bajos estableciendo el argumento de par nombre-valor.'Replicates'

es un vector de índices de clúster espredichos correspondientes a las observaciones en . es una matriz de 3 por 2 que contiene las ubicaciones centroides finales.idxXC

Se utiliza para calcular la distancia desde cada centroide a puntos de una cuadrícula.kmeans Para ello, pase los centroides ( ) y los puntos de una cuadrícula a , e implemente una iteración del algoritmo.Ckmeans

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

muestra una advertencia que indica que el algoritmo no convergió, lo que debe esperar, ya que el software solo implementó una iteración.kmeans

Trazar las regiones del clúster.

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;

Genere aleatoriamente los datos de ejemplo.

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 clústeres en los datos.

Particione los datos en dos clústeres y elija la mejor disposición de cinco inicializaciones. Visualice la salida 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 forma predeterminada, el software inicializa las réplicas por separado utilizando -means++.k

Trazar los clústeres y los centroides del clúster.

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

Puede determinar qué tan bien están los clústeres pasando a .idxsilhouette

La agrupación en clústeres de grandes conjuntos de datos puede llevar tiempo, especialmente si usa actualizaciones en línea (establecidas de forma predeterminada). Si tiene una licencia de ™ de Parallel Computing Toolbox y establece las opciones para la informática paralela, ejecute cada tarea de agrupación en clústeres (o replique) en paralelo.kmeans Y, si >1, entonces la computación paralela disminuye el tiempo a la convergencia.Replicates

Genere aleatoriamente un conjunto de datos grande a partir de un modelo de mezcla gaussiana.

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

es un modelo de 30 dimensiones con 20 componentes. es una matriz de 10000 por 30 de datos generados a partir de .MdlgmdistributionXMdl

Especifique las opciones para la informática paralela.

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

El argumento de entrada de especifica utilizar el algoritmo de generador de Fibonacci de retraso multiplicativo. es una matriz de estructura con campos que especifican opciones para controlar la estimación.'mlfg6331_64'RandStreamoptions

Agrupe los datos mediante la agrupación en clústeres -means.k Especifique que hay 20 clústeres en los datos y aumente el número de iteraciones.k Normalmente, la función objetivo contiene mínimos locales. Especifique 10 réplicas para ayudar a encontrar un mínimo local más bajo.

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 seis trabajadores disponibles. El número de trabajadores puede variar en el sistema. La ventana de comandos muestra el número de iteraciones y el valor de la función de objetivo de terminal para cada réplica. Los argumentos de salida contienen los resultados de la réplica 9 porque tiene la suma total más baja de distancias.

realiza -means clustering para particionar datos en clústeres.kmeanskk Cuando tiene un nuevo conjunto de datos en el clúster, puede crear nuevos clústeres que incluyan los datos existentes y los nuevos datos mediante .kmeans La función admite la generación de código C/C++, por lo que puede generar código que acepte datos de entrenamiento y devuelva resultados de agrupación en clústeres y, a continuación, implemente el código en un dispositivo.kmeans En este flujo de trabajo, debe pasar los datos de entrenamiento, que pueden ser de un tamaño considerable. Para ahorrar memoria en el dispositivo, puede separar el entrenamiento y la predicción mediante y , respectivamente.kmeanspdist2

Se utiliza para crear clústeres en MATLAB® y utilizar en el código generado para asignar nuevos datos a clústeres existentes.kmeanspdist2 Para la generación de código, defina una función de punto de entrada que acepte las posiciones centroide del clúster y el nuevo conjunto de datos, y devuelva el índice del clúster más cercano. A continuación, genere código para la función de punto de entrada.

La generación de código C/C++ requiere MATLAB® Coder™.

Realizar -Mediaclusteringk

Genere un conjunto de datos de entrenamiento mediante 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];

Particione los datos de entrenamiento en tres clústeres mediante .kmeans

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

Trazar los clústeres y los centroides del clúster.

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 clústeres existentes

Generar 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];

Clasificar el conjunto de datos de prueba mediante los clústeres existentes. Busque el centroide más cercano de cada punto de datos de prueba utilizando .pdist2

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

Trazar los datos de prueba y etiquetar los datos de prueba mediante .idx_testgscatter

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 clústeres existentes. Tenga en cuenta que la generación de código C/C++ requiere MATLAB® Coder™.

Defina una función de punto de entrada denominada que acepte posiciones centroides y nuevos datos y, a continuación, busque el clúster más cercano mediante .findNearestCentroidpdist2

Agregue la directiva del compilador (o pragma) a la función de punto de entrada después de la firma de la función para indicar que tiene la intención de generar código para el algoritmo MATLAB.%#codegen Al agregar esta directiva, se indica al analizador de códigos de MATLAB que le ayude a diagnosticar y corregir infracciones 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 

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

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

codegen findNearestCentroid -args {C,Xtest}
 

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

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

devuelve lógico 1 ( ), lo que significa que todas las entradas son iguales.isequaltrue La comparación confirma que la función, la función y la función MEX devuelven el mismo índice.pdist2findNearestCentroid

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

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

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

Argumentos de entrada

contraer todo

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

Si es un vector numérico, lo trata como una matriz de datos -by-1, independientemente de su orientación.Xkmeansn

El software trata s en como datos que faltan y elimina cualquier fila de que contiene al menos uno .NaNXXNaN La eliminación de filas de reduce el tamaño de la muestra.X el kmeans función devuelve el valor correspondiente en el argumento de salida .NaNidx

Tipos de datos: single | double

Número de clústeres de 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. es el nombre del argumento y es el valor correspondiente. deben aparecer entre comillas.Name,ValueNameValueName Puede especificar varios argumentos de par de nombre y valor en cualquier orden como .Name1,Value1,...,NameN,ValueN

Ejemplo: especifica la distancia del coseno, replica clústeres en diferentes valores iniciales y se utiliza la informática paralela.'Distance','cosine','Replicates',10,'Options',statset('UseParallel',1)10

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

  • — Muestra los resultados de la iteración final'final'

  • — Muestra los resultados de cada iteración'iter'

  • — No muestra nada'off'

Ejemplo: 'Display','final'

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

calcula los clústeres centroides de forma diferente para las métricas de distancia admitidas.kmeans Esta tabla resume las métricas de distancia disponibles. En las fórmulas, es una observación (es decir, una fila de ) y es un centroide (un vector de fila).xXc

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

Distancia euclidiana cuadrada (predeterminada). Cada centroide es la media de los puntos de ese clúster.

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

'cityblock'

Suma de diferencias absolutas, es decir, la distancia 1. L Cada centroide es la mediana de componentes de los puntos de ese clúster.

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 los puntos de ese cúmulo, después de normalizar esos puntos para unir la longitud euclidiana.

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

'correlation'

Uno menos la correlación de la muestra entre puntos (tratados como secuencias de valores). Cada centroide es la media de componente de los puntos de ese clúster, después de centrar y normalizar esos puntos a cero media y distancia estándar de unidad.

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

Dónde

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

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

  • 1p es un vector de fila de unos.p

'hamming'

Esta métrica solo es adecuada para datos binarios.

Es la proporción de bits que difieren. Cada centroide es la mediana de puntos en cuanto a componentes de ese clúster.

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

donde está la función del indicador.I

Ejemplo: 'Distance','cityblock'

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

ValorDescripción
'error'

Tratar un clúster vacío como un error.

'drop'

Quite los clústeres que se queden vacíos. establece los valores devueltos correspondientes en y en .kmeansCDNaN

'singleton'

Cree un nuevo clúster que consista en el 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 y un entero positivo.'MaxIter'

Ejemplo: 'MaxIter',1000

Tipos de datos: double | single

Marca de actualización en línea, especificada como el par separado por comas que consta de y o .'OnlinePhase''off''on'

Si es , realiza una fase de actualización en línea además de una fase de actualización por lotes.OnlinePhaseonkmeans La fase en línea puede llevar 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 clúster diferente aumenta la suma total de distancias.

Ejemplo: 'OnlinePhase','on'

Opciones para controlar el algoritmo iterativo para minimizar los criterios de ajuste, especificados como el par separado por comas que consta de y una matriz de estructura devuelta por .'Options'statset Los campos admitidos de la matriz de estructura especifican opciones para controlar el algoritmo iterativo.

Esta tabla resume los campos admitidos. Tenga en cuenta que los campos admitidos requieren .Parallel Computing Toolbox™

CampoDescripción
'Streams'

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

  • Tiene un grupo paralelo abierto.

  • Es.UseParalleltrue

  • Es.UseSubstreamsfalse

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

'UseParallel'
  • Si y > 1, implementa el algoritmo -means en cada réplica en paralelo.trueReplicateskmeansk

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

'UseSubstreams'Establézalo para calcular en paralelo de forma reproducible.true El valor predeterminado es .false Para calcular de forma reproducible, establezca en un tipo que permita substreams: o .Streams'mlfg6331_64''mrg32k3a'

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

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

Tipos de datos: struct

Número de veces que se repite la agrupación en clústeres utilizando nuevas posiciones centroide de clúster iniciales, especificadas como el par separado por comas que consta de un entero. devuelve la solución con el valor más bajo.'Replicates'kmeanssumd

Puede establecer implícitamente proporcionando una matriz 3D como el valor para el argumento de par nombre-valor.'Replicates''Start'

Ejemplo: 'Replicates',5

Tipos de datos: double | single

Método para elegir las posiciones centroides de clúster iniciales (o ), especificado como el par separado por comas que consta de y , , , , una matriz numérica o una matriz numérica.Semillas'Start''cluster''plus''sample''uniform' En esta tabla se resumen las opciones disponibles para elegir semillas.

ValorDescripción
'cluster'

Realice una fase de agrupación en clústeres preliminar en una submuestra aleatoria del 10% de cuando el número de observaciones en la submuestra sea mayor que .Xk Esta fase preliminar se inicializa utilizando .'sample'

Si el número de observaciones en la submuestra aleatoria del 10% es menor que , entonces el software selecciona observaciones al azar.kkX

(predeterminado)'plus'Seleccione semillas implementando elk -means++ algoritmok para la inicialización del centro de clúster.
'sample'Seleccione observaciones al azar.kX
'uniform'Seleccione puntos uniformemente al azar del rango de .kX No es válido con la distancia Hamming.
matriz numérica-por- matriz de ubicaciones de inicio centroide.kp Las filas de corresponden a semillas.Start El software deduce desde la primera dimensión de , por lo que puede pasar para .kStart[]k
matriz numérica-by- -by- matriz de ubicaciones de inicio centroide.kpr Las filas de cada página corresponden a semillas. La tercera dimensión invoca la replicación de la rutina de agrupación en clústeres. Page contiene el conjunto de semillas para replicar .jj El software deduce el número de réplicas (especificado por el argumento de par nombre-valor) del tamaño de la tercera dimensión.'Replicates'

Ejemplo: 'Start','sample'

Tipos de datos: char | string | double | single

Argumentos de salida

contraer todo

Los índices de clúster, devueltos como vector de columna numérico. tiene tantas filas como , y cada fila indica la asignación de clúster de la observación correspondiente.idxX

Ubicaciones de centroide de clúster, devueltas como una matriz numérica. es una matriz -by-, donde row es el centroide del clúster.Ckpjj

Sumas dentro del clúster de distancias punto a centroide, devueltas como un vector de columna numérico. es un vector -by-1, donde element es la suma de distancias punto a centroide dentro del clúster.sumdkjj

Distancias desde cada punto a cada centroide, devuelto como una matriz numérica. es una matriz -por-, donde el elemento ( , ) es la distancia desde la observación hasta el centroide.Dnkjmjm

Más acerca de

contraer todo

-Medios clusteringk

, o algoritmo de Lloyd, es un algoritmo iterativo de partición de datos que asigna observaciones a exactamente uno de los clústeres definidos por los centroides, donde se elige antes de que se inicie el algoritmo.k-means clustering[2]nkk

El algoritmo procede de la siguiente manera:

  1. Elija los centros de clúster iniciales ( ).kCentroide Por ejemplo, elija observaciones al azar (mediante ) o utilice elk'Start','sample' -significa algoritmo ++k para la inicialización del centro de clúster (el valor predeterminado).

  2. Calcular distancias punto a clúster-centroide de todas las observaciones a cada centroide.

  3. Hay dos formas de proceder (especificadas por ):OnlinePhase

    • Actualización por lotes: asigne cada observación al clúster con el centroide más cercano.

    • Actualización en línea: asigne observaciones individualmente a un centroide diferente si la reasignación disminuye la suma de las distancias entre clústeres y de suma de cuadrados punto a clúster-centroide.

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

  4. Calcular el promedio de las observaciones en cada clúster para obtener nuevas ubicaciones centroides.k

  5. Repita los pasos del 2 al 4 hasta que las asignaciones de clúster no cambien o se alcance el número máximo de iteraciones.

-means++ Algoritmok

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

El algoritmo -means++ elige las semillas de la siguiente manera, suponiendo que el número de clústeres sea .kk

  1. Seleccione una observación uniformemente al azar del conjunto de datos, .X La observación elegida es el primer centroide, y se denotac1.

  2. Calcular distancias desde cada observación hastac1. Denotar la distancia entrecj y la observación comom d(xm,cj).

  3. Seleccione el siguiente centroide,c2 al azar de con probabilidadX

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

  4. Para elegir el centro:j

    1. Calcular las distancias de cada observación a cada centroide, y asignar cada observación a su centroide más cercano.

    2. Para los números 1,..., y 1,..., – 1, seleccione centroide al azar con probabilidadmnpjjX

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

      Dónde Cp es el conjunto de todas las observaciones más cercanas a los centroides Cp Y Xm pertenece a Cp.

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

  5. Repita el paso 4 hasta que se elijan los centroides.k

Arthur y Vassilvitskii demuestran, utilizando un estudio de simulación para varias orientaciones de clúster, que -means++ logra una convergencia más rápida a una menor suma de distancias entre clústeres y suma de cuadrados punto a clúster-centroide que el algoritmo de Lloyd.[1]k

Algoritmos

  • utiliza un algoritmo iterativo de dos fases para minimizar la suma de distancias punto a centroide, sumadas en todos los clústeres.kmeansk

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

    2. Esta segunda fase utiliza , donde los puntos se reasignan individualmente si al hacerlo se reduce la suma de distancias y los centroides de clúster se vuelven a calcular después de cada reasignación.actualizaciones en línea Cada iteración durante esta fase consta de una pasada a través de todos los puntos. Esta fase converge a un mínimo local, aunque puede haber otros mínimos locales con menor suma total de distancias. En general, encontrar el mínimo global se resuelve mediante una selección exhaustiva de puntos de partida, pero el uso de varias réplicas con puntos de partida aleatorios normalmente da como resultado una solución que es un mínimo global.

  • Si es el número de serie 1 y es (el valor predeterminado), el software selecciona posibles conjuntos de semillas diferentes de acuerdo con elReplicatesrStartplusr -means++ algoritmok.

  • Si habilita la opción en y > 1, cada trabajador selecciona semillas y clústeres en paralelo.UseParallelOptionsReplicates

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