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 clusteringk

Descripción

ejemplo

idx = kmeans(X,k) Realiza -significa clusteringk para dividir las observaciones de la matriz-por-datos 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 con los nuevos valores iniciales o el uso de la computación paralela.

ejemplo

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

ejemplo

[idx,C,sumd] = kmeans(___) Devuelve las sumas dentro del clúster de las distancias de 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.nkD

Ejemplos

contraer todo

Los datos de clúster que utilizan-significan clustering y, a continuación, trazan las regiones del clúster.k

Cargue el conjunto de datos de iris de Fisher. Utilice las longitudes y anchos de pétalo 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 más baja y una región de desviación más alta. Esto podría indicar que el clúster más grande es dos clústeres superpuestos.

Agrupar los datos. Especifique = 3 clústeres.k

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

utiliza el algoritmo-Means + + para la inicialización de centroide y la distancia euclidiana cuadrada por defecto.kmeansk Es una buena práctica buscar valores mínimos locales inferiores estableciendo el argumento de par nombre-valor.'Replicates'

es un vector de los índices de clúster previstos correspondientes a las observaciones en. es una matriz de 3 por 2 que contiene las ubicaciones del centroide final.idxXC

Se utiliza para calcular la distancia desde cada centroide hasta los puntos de una rejilla.kmeans Para ello, pase los centroides () y los puntos en una rejilla 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 convertía, que usted debe esperar puesto que el software implementó solamente una iteración.kmeans

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

Particionar los datos en dos clústeres y elegir 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 usando-Means + +.k

Trace 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 separados están los clústeres pasando a.idxsilhouette

Agrupar conjuntos de datos grandes puede llevar tiempo, especialmente si usa actualizaciones en línea (establecidas de forma predeterminada). Si tiene una licencia de Parallel Computing Toolbox™ y establece las opciones para la computación paralela, ejecutará cada tarea de clustering (o réplica) en paralelo.kmeans Y, si > 1, entonces la computación paralela disminuye el tiempo a la convergencia.Replicates

Genere aleatoriamente un conjunto de datos de gran tamaño 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 10000-by-30 de datos generados a partir de.MdlgmdistributionXMdl

Especifique las opciones para la computación paralela.

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

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

Agrupar los datos usando-significa clustering.k Especifique que hay = 20 clústeres en los datos y aumente el número de iteraciones.k Normalmente, la función objetivo contiene los mínimos locales. Especifique 10 réplicas para ayudar a encontrar un mínimo local menor.

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 su 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-significa clustering para dividir los 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 el uso.kmeans La función admite la generación de código de C/C++, por lo que puede generar código que acepte datos de entrenamiento y devuelva resultados de clustering y, a continuación, implementar 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 la formación y la predicción mediante y, respectivamente.kmeanspdist2

Se utiliza para crear clústeres en MATLAB® y utilizarlos en el código generado para asignar nuevos datos a los clústeres existentes.kmeanspdist2 Para la generación de código, defina una función de punto de entrada que acepte las posiciones de centroide de 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-significa clusteringk

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

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

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

Trace 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

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 utilizando los clústeres existentes. Busque el centroide más cercano de cada punto de datos de prueba mediante.pdist2

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

Trace los datos de prueba y etiquete los datos de prueba utilizando.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 de centroide 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 pretende generar código para el algoritmo de MATLAB.%#codegen La adición de esta directiva indica al analizador de código de MATLAB que le ayudará a diagnosticar y corregir infracciones que provocarán 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 pulsa 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.

Genere código mediante.codegen Dado que C y C++ son lenguajes con tipos estáticos, debe determinar las propiedades de todas las variables en la función de punto de entrada en tiempo de compilación. Para especificar el tipo de datos y el tamaño de la matriz de las entradas, pase una expresión de 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.Especifique argumentos de tamaño variable para la generación de código

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 Logical 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.Flujo de trabajo de generación de código general Para obtener más información sobre el codificador de GPU, consulte y.Getting 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 las observaciones, y las columnas corresponden a las variables.X

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

Tipos de datos: single | double

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

Tipos de datos: single | double

Argumentos de par nombre-valor

Especifique pares de argumentos separados por comas opcionales. es el nombre del argumento y es el valor correspondiente. deben aparecer dentro de las cotizaciones.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 los clústeres en diferentes valores de inicio y utiliza la computación paralela.'Distance','cosine','Replicates',10,'Options',statset('UseParallel',1)10

Nivel de salida que se muestra en la ventana de comandos, especificado como el par separado por comas que consta de 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'

Distancia métrica, espacio en dimensiones, utilizado para la minimización, especificado como el par separado por comas que consta de y,,, o.p'Distance''sqeuclidean''cityblock''cosine''correlation''hamming'

calcula los clústeres de centroide de manera diferente para las diferentes 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

Distancia métricaDescripciónFórmula
'sqeuclidean'

Distancia euclidiana cuadrada (por defecto). Cada centroide es la media de los puntos en ese cluster.

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

'cityblock'

Suma de las diferencias absolutas, es decir, la distancia de 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 los puntos (tratado como vectores). Cada centroide es la media de los puntos en ese Cluster, después de normalizar esos puntos a la longitud euclidiana de la unidad.

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

'correlation'

Uno menos la correlación de muestra entre los puntos (tratados como secuencias de valores). Cada centroide es la media de componentes de los puntos en ese Cluster, después de centrar y normalizar esos puntos a cero media y la desviación estándar de la 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 ese clúster.

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

donde está la función indicadora.I

Ejemplo: 'Distance','cityblock'

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

ValorDescripción
'error'

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

'drop'

Quite los clústeres que estén vacíos. establece los valores devueltos correspondientes en y para.kmeansCDNaN

'singleton'

Cree un nuevo cluster consistente en un punto más alejado de su centroide (predeterminado).

Ejemplo: 'EmptyAction','error'

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

Ejemplo: 'MaxIter',1000

Tipos de datos: double | single

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

Si es así, 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 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 el que mover un solo punto a un clúster diferente aumenta la suma total de las 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.

En esta tabla se resumen los campos admitidos. Tenga en cuenta que los campos admitidos requieren.Parallel Computing Toolbox™

CampoDescripción
'Streams'

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

  • Tiene una piscina paralela abierta.

  • 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 suministrar un único flujo de números aleatorios.Streams

'UseParallel'
  • IF y > 1, a continuación, implementa el algoritmo-Means en cada réplica en paralelo.trueReplicateskmeansk

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

'UseSubstreams'Se establece en para computar en paralelo de una manera reproducible.true El valor predeterminado es.false Para calcular reproduciblemente, establezca un tipo que permita subsecuencias: o.Streams'mlfg6331_64''mrg32k3a'

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

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

Tipos de datos: struct

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

Puede establecer implícitamente proporcionando una matriz 3-D 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 de centroide de clúster iniciales (o), especificadas como el par separado por comas que consiste en y,,,, una matriz numérica o una matriz numérica.Semillas'Start''cluster''plus''sample''uniform' Esta tabla resume las opciones disponibles para elegir las semillas.

ValorDescripción
'cluster'

Realice una fase preliminar de clustering en una submuestra aleatoria del 10% cuando el número de observaciones en la submuestra sea mayor que.Xk Esta fase preliminar es en sí misma inicializada utilizando.'sample'

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

predeterminado'plus'Seleccione las semillas implementando elk -Means + + algoritmok para la inicialización del centro de clúster.
'sample'Seleccione las observaciones de al azar.kX
'uniform'Seleccione puntos uniformemente al azar desde el rango de.kX No es válido con la distancia de Hamming.
matriz numérica-por-matriz de ubicaciones de inicio de centroide.kp Las filas corresponden a las semillas.Start El software deduce de la primera dimensión de, por lo que puede pasar por.kStart[]k
matriz numérica-por-matriz de ubicaciones de inicio de centroide.kpr Las filas de cada página corresponden a las 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 (especificadas 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

Nota

El software trata a s como datos faltantes y elimina cualquier fila de que contenga al menos uno.NaNXNaN La eliminación de filas reduce el tamaño de la muestra.X

Argumentos de salida

contraer todo

Índices de clúster, devueltos como un 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 un-por-matriz, donde Row es el centroide del cluster.Ckpjj

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

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

Más acerca de

contraer todo

-Significa clusteringk

, o el 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 las observaciones al azar (mediante el uso) o utilice elk'Start','sample' -significa + + algoritmok para la inicialización del centro de clúster (valor predeterminado).

  2. Calcule las distancias punto a Cluster-centroide de todas las observaciones a cada centroide.

  3. Hay dos maneras 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 individualmente observaciones a un centroide diferente si la reasignación disminuye la suma de las distancias de punto a Cluster-centroide dentro del clúster, de suma de cuadrados.

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

  4. Calcule el promedio de las observaciones de cada clúster para obtener nuevas ubicaciones de centroide.k

  5. Repita los pasos 2 a 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 las semillas centroides para-significa clustering.k-Means + + algoritmok Según Arthur y Vassilvitskii,-significa + + mejora el tiempo de funcionamiento 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 es.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. Calcule Distancias desde cada observación hastac1. Denotan 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. Calcule las distancias de cada observación a cada centroide y asigne cada observación a su centroide más cercano.

    2. Para = 1,..., y = 1,..., – 1, seleccione el centroide al azar de con la probabilidadmnpjjX

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

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

      Es decir, seleccione cada centro subsiguiente con una probabilidad proporcional a la distancia de sí mismo al centro más cercano que ya eligió.

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

Arthur y Vassilvitskii demuestran, utilizando un estudio de simulación para varias orientaciones de cluster, que-significa + + logra una convergencia más rápida a una suma menor de distancias dentro del cluster, suma de cuadrados punto a Cluster-centroide que el algoritmo de Lloyd.[1]k

Algoritmos

  • utiliza un algoritmo iterativo de dos fases para minimizar la suma de las distancias de punto a centroide, sumados a 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, todo a la vez, seguido de un nuevo cálculo de los centroides del clúster.actualizaciones por lotes Esta fase no convergen ocasionalmente en una solución que es un mínimo local. Es decir, una partición de los datos donde mover un único punto a un clúster diferente aumenta la suma total de las distancias. Esto es más probable para pequeños conjuntos de datos. La fase de lote 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 las distancias y los centroides del clúster se recalculan después de cada reasignación.actualizaciones en línea Cada iteración durante esta fase consiste en una pasada, aunque todos los puntos. Esta fase converge a un mínimo local, aunque puede haber otros mínimos locales con una suma de distancias total menor. 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 suele tener como resultado una solución que es un mínimo global.

  • Si = > 1 y es (el valor predeterminado), entonces el software selecciona posiblemente diferentes conjuntos de semillas de acuerdo con elReplicatesrStartplusr -Means + + algoritmok.

  • Si habilita la opción en y > 1, cada trabajador selecciona las semillas y los 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