Método k-medias

El método k -means es el método de agrupamiento más popular . Fue inventado en la década de 1950 por el matemático Hugo Steinhaus [1] y casi simultáneamente por Stuart Lloyd [2] . Ganó particular popularidad después del trabajo de McQueen [3] .

La acción del algoritmo es tal que busca minimizar la desviación cuadrática total de los puntos de conglomerados desde los centros de estos conglomerados:

V=\sum_{i=1}^{k}\sum_{x\in S_{i}}(x-\mu_{i})^{2}

donde es el número de grupos, son los grupos resultantes , y son los centros de masa de todos los vectores del grupo . $k$ $Si}$ $i=1,2,\puntos,k$ $\mu _{i}$ $X$ $Si}$

Por analogía con el método de los componentes principales , los centros de los conglomerados también se denominan puntos principales , y el método en sí se denomina método de los puntos principales [4] y se incluye en la teoría general de los objetos principales que proporcionan la mejor aproximación de datos [5] .

Algoritmo

El algoritmo es una versión del algoritmo EM , también utilizado para separar una mezcla de gaussianas . Divide el conjunto de elementos del espacio vectorial en un número preconocido de grupos k .

La idea principal es que en cada iteración se recalcula el centro de masa de cada grupo obtenido en el paso anterior, luego los vectores se dividen en grupos nuevamente de acuerdo con cuál de los nuevos centros resultó estar más cerca según la métrica elegida.

El algoritmo termina cuando no hay cambios en la distancia intracluster en alguna iteración. Esto sucede en un número finito de iteraciones, ya que el número de particiones posibles de un conjunto finito es finito, y en cada paso la desviación cuadrática total V disminuye, por lo que es imposible hacer un bucle.

Como muestran David Arthur y Sergey Vasilvitsky, en algunas clases de conjuntos , la complejidad del algoritmo en términos del tiempo requerido para la convergencia es [6] . $2^{\Omega ({\sqrt {n)))}$

Demostración del algoritmo

Acción del algoritmo en el caso bidimensional. Los puntos de partida se eligen al azar.

Problemas con k-medias

No se garantiza el logro del mínimo global de la desviación estándar total V , sino solo uno de los mínimos locales.
El resultado depende de la elección de los centros de conglomerados iniciales; se desconoce su elección óptima.
El número de conglomerados debe conocerse de antemano.

Extensiones y variaciones

La implementación de la red neuronal de K-means es ampliamente conocida y utilizada: una red de cuantificación vectorial de señales (una de las versiones de las redes neuronales de Kohonen ).

Existe una extensión k-means++ , que tiene como objetivo la elección óptima de los valores iniciales de los centros de conglomerados.

Aplicaciones para aprendizaje profundo y visión artificial

En los algoritmos de aprendizaje profundo , el método k-means a veces no se usa para el propósito previsto (clasificación por agrupamiento), sino para crear los llamados filtros (núcleos de convolución, diccionarios). Por ejemplo, para el reconocimiento de imágenes, el algoritmo k-means se alimenta con pequeñas piezas aleatorias de imágenes de muestra de entrenamiento, digamos, de tamaño 16x16, como un vector lineal, cada elemento del cual codifica el brillo de su punto. El número de conglomerados k es grande, por ejemplo, 256. El método de k-medias entrenado, bajo ciertas condiciones, produce centros de conglomerados (centroides), que son bases convenientes en las que se puede descomponer cualquier imagen de entrada. Dichos centroides "entrenados" se utilizan además como filtros, por ejemplo, para una red neuronal convolucional como núcleos de convolución u otros sistemas de visión artificial similares [8] . Así, el aprendizaje no supervisado se lleva a cabo utilizando el método k-means.

Enlaces

↑ Steinhaus H. (1956). Sur la division des corps materiels en parties. Toro. Academia Polon. Esc., C1. III volumen IV: 801-804.
↑ Lloyd S. (1957). Cuantificación por mínimos cuadrados en PCM's. Papel de Bell Telephone Laboratories.
↑ MacQueen J. (1967). Algunos métodos de clasificación y análisis de observaciones multivariadas. En Proc. 5º Simposio de Berkeley. en Matemáticas. Estadística y Probabilidad, páginas 281-297.
↑ Flury B. (1990). puntos principales. Biometrika, 77, 33-41.
↑ Gorban AN, Zinovyev AY (2009). Gráficos principales y variedades , cap. 2 en: Manual de investigación sobre aplicaciones y tendencias del aprendizaje automático: algoritmos, métodos y técnicas, Emilio Soria Olivas et al. (eds), IGI Global, Hershey, Pensilvania, EE. UU., págs. 28-59.
↑ David Arthur y Sergei Vassilvitskii (2006). "¿Qué tan lento es el método k-means?" (PDF) . Actas del Simposio de 2006 sobre Geometría Computacional (SoCG) . Archivado (PDF) desde el original el 24 de enero de 2009 . Consultado el 20 de abril de 2008 . Parámetro obsoleto utilizado |deadlink=( ayuda )
↑ EM Mirkes, K-means y K-medoids applet Archivado el 29 de mayo de 2013 en Wayback Machine . Universidad de Leicester, 2011.
↑ Adam Coates y Andrew Y. Ng. Representaciones de características de aprendizaje con K-means Archivado el 21 de junio de 2015 en Wayback Machine , Universidad de Stanford, 2012

Demostración y visualización

J. Tu, R. Gonzalez "Principles of Pattern Recognition", Mir Publishing House, Moscú 1978, pp. 109-112 (descripción del algoritmo con un ejemplo numérico).
K-means y K-medoids ( un subprograma que demuestra el funcionamiento del algoritmo y le permite explorar y comparar dos métodos), E. Mirkes y la Universidad de Leicester
Un applet interactivo que demuestra cómo funciona el algoritmo.

Aprendizaje automático y minería de datos
Tareas	Problema de clasificación Aprender sin un maestro Aprendizaje asistido por profesores Análisis de regresión AutoML reglas de asociación Extracción de características entrenamiento de rasgos Entrenamiento de clasificación Derivación gramatical Aprender en línea
Aprendiendo con un maestro	método del k-vecino más cercano Clasificador bayesiano ingenuo árbol de decisión Máquinas de vectores soporte Regresión lineal Regresión logística perceptrón conjuntos de modelos Harpillera impulsar bosque aleatorio Método de vector relevante
análisis de conglomerados	método k-medias método de agrupamiento difuso Agrupación jerárquica algoritmo EM ABEDUL CURAR DBSCAN ÓPTICA Desplazamiento medio
Reducción de dimensionalidad	Análisis factorial Método de componentes principales CCA ACI LDA Expansión de matriz no negativa t-SNE
Pronóstico estructural	Graficar modelo probabilístico red bayesiana Modelo oculto de Markov FRC
Detección de anomalías	método del k-vecino más cercano Nivel de emisión local
Graficar modelos probabilísticos	red bayesiana Red de Markov Modelo oculto de Markov
Redes neuronales	Máquina Boltzmann limitada mapa autoorganizado Función de activación Sigmoideo softmax Funcion de base radial Método de propagación hacia atrás Aprendizaje profundo perceptrón multicapa Red neuronal recurrente memoria a corto plazo Bloque recurrente controlado Red neuronal convolucional U-red Codificador automático
Aprendizaje reforzado	proceso de Markov Ecuación de Bellman Algoritmo codicioso Q-aprendizaje SARAS Diferencia temporal (DT)
Teoría	Teoría de Vapnik-Chervonenkis Dilema de dispersión de sesgo Teoría del aprendizaje computacional Minimización empírica del riesgo El aprendizaje de Occam aprendizaje PAC Teoría del aprendizaje estadístico
revistas y congresos	NeurIPS ICML ML JMLR ArXiv:cs.LG