Ocho: Algoritmo de agrupamiento K-medias (20191223-29)
Contenido de aprendizaje: algoritmo de agrupamiento no supervisado K-Means
k-means: principio del modelo, proceso de convergencia, selección de hiperparámetros
El análisis de conglomerados es Descubra la relación entre los datos objetos en los datos y agrupar los datos Cuanto mayor sea la similitud dentro del grupo y mayor la diferencia entre los grupos, mejor será el efecto de agrupación.
Diferentes tipos de clústeres: la agrupación tiene como objetivo descubrir clústeres de objetos útiles. En realidad, utilizamos muchos tipos de clústeres y los resultados de utilizar diferentes tipos de clústeres para dividir datos son diferentes.
Basado en prototipos: un clúster es una colección de objetos, en la que la distancia entre cada objeto y el prototipo que define el clúster es menor que la distancia del prototipo de otros clústeres. El prototipo se muestra en (b). es el punto central, los datos de un grupo están más cerca de su punto central que del punto central de otro grupo. Este es un grupo común basado en el centro, y las K-Means más utilizadas son este tipo de grupo. Estos grupos tienden a ser esféricos.
Basado en densidad: los grupos son áreas de densidad de objetos. (d) muestra grupos basados en densidad. Cuando los grupos son irregulares o entrelazados y hay mañanas y valores atípicos, a menudo se utilizan grupos basados en densidad. definición de clúster.
Para obtener más información sobre los clústeres, consulte "Introducción a la minería de datos".
Algoritmo básico de análisis de conglomerados
1. K-medias: basándose en el prototipo, tecnología de distancia dividida, intenta encontrar un número (K) de conglomerados especificado por el usuario.
2. Distancia jerárquica agregada: la idea es comenzar con cada punto como un grupo de puntos únicos y luego fusionar repetidamente los dos grupos más cercanos hasta que se pruebe un grupo único que contenga todos los puntos.
3. DBSCAN: un algoritmo de división de distancia basado en la densidad. El algoritmo determina automáticamente el número de grupos. Los puntos con baja densidad se tratan como ruido y se ignoran, por lo que no produce un agrupamiento completo. .
Las diferentes medidas de distancia afectarán los resultados de distancia. Las medidas de distancia comunes son las siguientes:
Ventajas: ¿fácil de implementar?
Desventajas: posible convergencia debido a local. mínimos, la convergencia es lenta en datos a gran escala
Idea de algoritmo:
¿Seleccionar K puntos como centroides iniciales?
repetir
Asignar ¿Cada punto al centroide más cercano para formar K grupos?
¿Recalcular el centroide de cada grupo?
hasta que el grupo no cambie o se alcance el número máximo de iteraciones
p>
Aquí "recalcular el centroide de cada grupo" se calcula en función de la función objetivo, por lo que la métrica de distancia y la función objetivo deben considerarse al principio.
Teniendo en cuenta los datos de la distancia euclidiana, utilizando la suma del error cuadrático (SSE) como función objetivo de la agrupación, se generan dos grupos diferentes ejecutando K-means dos veces. Utilice el que tenga el SSE más pequeño.
k representa k centros de agrupamiento, ci representa el centro y dist representa la distancia euclidiana. ?
Hay una pregunta aquí, por eso actualizamos el centroide para que sea el promedio de todos los puntos, que está determinado por SSE.
El algoritmo k-means es muy simple y ampliamente utilizado, pero tiene dos defectos principales:
1. El valor K debe darse con anticipación y pertenece al conocimiento previo. En muchos casos, el valor K es muy difícil de estimar. Para escenarios como calcular los círculos de contacto de todos los usuarios de WeChat, es completamente imposible utilizar K-Means. Para escenarios en los que es seguro que el valor K no será demasiado grande pero el valor K exacto no está claro, se puede realizar una operación iterativa y luego se puede encontrar el valor K correspondiente a la función de costo mínimo. Este valor a menudo se puede encontrar. Describe mejor cuántos grupos hay.
2. El algoritmo K-Means es sensible al punto central de agrupamiento seleccionado inicialmente, y los resultados de agrupamiento obtenidos por diferentes puntos semilla aleatorios son completamente diferentes.
3. Los K-means El algoritmo combina no todos los tipos de datos. No puede manejar grupos no esféricos, grupos de diferentes tamaños y diferentes densidades. Silver Crown especifica un número suficientemente grande de grupos para que normalmente pueda encontrar subgrupos puros.
4. K-means también tiene problemas al agrupar datos atípicos. En este caso, la detección y eliminación de valores atípicos son de gran ayuda.
La selección del centroide inicial se analiza a continuación:
Cuando el centroide inicial se inicializa aleatoriamente, cada ejecución de K-medias producirá un SSE diferente, y el SSE será aleatorio El resultado de seleccionar el centro de masa inicial puede ser muy malo y es posible que solo sea posible obtener una solución óptima local, pero no una solución óptima global.
Ejecute varias veces, cada vez utilizando un conjunto diferente de centroides iniciales aleatorios, y elija el conjunto de clústeres con el SSE más pequeño. Esta estrategia es muy simple, pero el efecto puede no ser muy bueno, dependiendo de la cantidad de grupos que busque el conjunto de datos.
Para obtener más información, consulte "Introducción a la minería de datos".
Para superar el problema de que el algoritmo K-Means converge al mínimo local, se utiliza una K-means bisectriz ( Se propone bisectar K-medias)
Trate todos los puntos como un grupo
Cuando el grupo es menor que el número k
Para cada grupo<. /p>
Calcular el error total
Realizar agrupación de K-medias en un grupo determinado, con un valor k de 2. Calcular el error total después de dividir el grupo en dos grupos
Seleccione el que tenga el error más pequeño Divida qué grupo
En el algoritmo K-means original, todas las muestras deben participar en el cálculo de cada división. Si la cantidad de datos es muy grande, este tiempo es muy alto. , por lo que existe un algoritmo mejorado para el procesamiento por lotes.
Utilice el método Mini Batch (procesamiento por lotes) para calcular la distancia entre puntos de datos.
La ventaja de Mini Batch: no es necesario utilizar todas las muestras de datos, sino extraer una parte de las muestras de diferentes categorías para representar los tipos respectivos para el cálculo. n Dado que el tamaño de la muestra de cálculo es pequeño, el tiempo de ejecución se reducirá en consecuencia n. Sin embargo, por otro lado, el muestreo inevitablemente provocará una disminución en la precisión.
La agrupación intenta dividir las muestras de un conjunto de datos en varios subconjuntos, normalmente separados, formando cada subconjunto un "grupo". A través de dicha división, cada grupo puede corresponder a algunos conceptos potenciales (es decir, categorías). Cabe señalar que estos conceptos son desconocidos por el algoritmo de agrupación y el proceso de agrupación solo puede formar automáticamente una estructura de grupo. la semántica es captada y nombrada por el usuario.
La agrupación es un algoritmo de aprendizaje no supervisado y la clasificación es un algoritmo de aprendizaje supervisado. El llamado supervisado es un conjunto de entrenamiento con etiquetas conocidas (es decir, sabiendo de antemano a qué categoría pertenecen los datos en el conjunto de entrenamiento), el algoritmo de aprendizaje automático aprende los parámetros correspondientes en el conjunto de entrenamiento, construye un modelo y luego. lo aplica al conjunto de prueba. El algoritmo de agrupación no tiene etiquetas. Al agrupar, el objetivo que se debe lograr es agrupar cosas similares.
El propósito de la agrupación es reunir muestras similares y separar muestras diferentes, similar a "pájaros del mismo plumaje se juntan". La idea intuitiva es que la similitud en el mismo grupo debe ser lo más alta posible. , y la similitud entre los grupos debe ser lo más baja posible.
La medición del desempeño se puede dividir aproximadamente en dos categorías: una son indicadores externos y la otra son indicadores internos.
Indicadores externos: Comparar los resultados del clustering con un "modelo de referencia".
Indicadores internos: examinan directamente los resultados del clustering sin utilizar ningún modelo de referencia.
Para un conjunto de muestras determinado, divida el conjunto de muestras en K grupos de acuerdo con la distancia entre muestras. Deje que los puntos del grupo estén lo más estrechamente conectados posible y haga que la distancia entre los grupos sea lo más grande posible
Los principiantes confundirán fácilmente K-Means y KNN. De hecho, todavía existen muchas diferencias entre ellos. dos.
K-Means es un algoritmo de agrupación de aprendizaje no supervisado sin salida de muestra, mientras que KNN es un algoritmo de clasificación de aprendizaje supervisado con salida de categoría correspondiente. Básicamente, KNN no requiere entrenamiento. Para los puntos en el conjunto de prueba, solo necesita encontrar los k puntos más cercanos en el conjunto de entrenamiento y usar las categorías de los k puntos más cercanos para determinar la categoría del punto de prueba. K-Means tiene un proceso de entrenamiento obvio para encontrar el mejor centroide de k categorías, determinando así la categoría de grupo de la muestra.
Por supuesto, existen algunas similitudes entre los dos. Ambos algoritmos incluyen un proceso de encontrar el punto más cercano a un punto determinado.
Ambos utilizan la idea de vecinos más cercanos.
Ventajas:
Simple, fácil de entender e implementar, convergencia rápida, generalmente solo se necesitan de 5 a 10 iteraciones, eficiente
Desventajas:
1. Una selección diferente del valor K tendrá una gran diferencia en los resultados.
2. Es sensible a la selección de puntos iniciales y los resultados de agrupación obtenidos por diferentes puntos iniciales aleatorios pueden ser completamente diferentes. diferente
p>
3. Es difícil converger para conjuntos de datos que no son convexos
4. Es demasiado sensible al ruido porque el algoritmo se basa en la media
5. El resultado no es necesariamente La optimización global solo puede garantizar la optimización local.
6. El efecto de agrupación de los conglomerados esféricos es mejor, pero el efecto de agrupación de los conglomerados no esféricos, los conglomerados de diferentes tamaños y diferentes densidades no es bueno.
El algoritmo K-means es sencillo de entender y fácil de implementar (óptimo local), pero tiene problemas como ser sensible a puntos iniciales y puntos de ruido, además se confunde fácilmente con la clasificación de aprendizaje supervisado; algoritmo KNN.
Lectura de referencia:
1. "Comprensión profunda del algoritmo de agrupación de K-Means"
2. "K-Means"