Resumen de información útil sobre minería de datos (4) -Algoritmo de agrupación
¿Algoritmo de agrupamiento
?
1. Esencia
Divida los datos en diferentes categorías para que los datos similares estén en la misma categoría y los datos diferentes estén en categorías diferentes.
?
2. ¿Qué problemas se utilizan para resolver los algoritmos de clasificación?
La agrupación de texto, la agrupación de imágenes y la agrupación de productos pueden descubrir fácilmente patrones y resolver el problema de la escasez de datos.
3. Conocimientos básicos del algoritmo de agrupamiento
1. ¿Agrupación jerárquica? ¿vs? Agrupación no jerárquica
–¿Existe una relación de inclusión entre diferentes categorías?
2. ¿Agrupación difícil? ¿vs? Agrupación suave
–Agrupación dura: cada objeto pertenece a una sola clase.
–Agrupación suave: Cada objeto pertenece a cada clase con una probabilidad determinada.
3. Utilice vectores para representar objetos
Cada objeto está representado por un vector, que puede considerarse como un punto en un espacio de alta dimensión.
–Todos los objetos forman un espacio de datos (matriz)
–Cálculo de similitud: coseno, producto escalar y distancia centroide.
4. Utiliza una matriz para enumerar las distancias y similitudes entre objetos.
5. Utilice un diccionario para guardar la matriz anterior (ahorre espacio)
D={(1,1):0, (1,2):2, (1, 3) :6...(5,5):0}
6. Método de evaluación
–Método de evaluación interna:
? ¿Sin normas externas ni supervisión
? Si la misma categoría es similar y si es diferente entre categorías.
Cuanto menor sea el valor de DB, mejor será el efecto de agrupación; de lo contrario, peor será.
–Método de evaluación externa:
? Precisión: (c 11+c22)/(c 11+c 12+c 21+c22)
? Precisión: c 11/(c 11+c 21)
? Recordemos:c 11/(c 11+c 12)
? Valor F (valor F):
β representa la importancia otorgada a la precisión p. Cuanto mayor es el valor, más importante es. La configuración predeterminada es 1, lo que significa que se convierte en el valor de f. Cuanto mayor sea f, mejor será el efecto de agrupación.
4. ¿Qué algoritmos de clustering existen?
Se divide principalmente en algoritmo de agrupamiento jerárquico, algoritmo de agrupamiento de particiones, algoritmo de agrupamiento basado en densidad, algoritmo de agrupamiento basado en cuadrícula, algoritmo de agrupamiento basado en modelos, etc.
4.1 Algoritmo de agrupamiento jerárquico
También conocido como algoritmo de agrupamiento en árbol, divide o agrega datos repetidamente a través de una estructura jerárquica. Los algoritmos típicos incluyen el algoritmo BIRCH, el algoritmo CURE, el algoritmo CHAMELEON, el algoritmo de agrupamiento aproximado de datos de secuencia, el algoritmo de promedio entre grupos, el algoritmo del vecino más lejano, el algoritmo del vecino más cercano, etc.
Agrupación jerárquica cohesiva:
Primero trate cada objeto como un grupo y luego combine estos grupos atómicos en grupos cada vez más grandes hasta que todos los objetos estén en un grupo o cumplan una determinada condición de terminación. .
Proceso del algoritmo:
1. Trate cada objeto como una clase y calcule la distancia mínima entre dos objetos.
2. en Dos clases se fusionan en una nueva clase
3. Vuelva a calcular la distancia entre la nueva clase y todas las clases
4. una clase.
Características:
1. Algoritmo simple
2. La jerarquía se utiliza para la agrupación de conceptos (generando árboles jerárquicos de conceptos y documentos).
3. Ambas representaciones de objetos de clúster son aplicables.
4. Manejar conglomerados de diferentes tamaños
5. El paso de selección de conglomerados es después de generar el dendrograma.
4.2 Algoritmo de agrupamiento de particiones
Especifique previamente el número de grupos o centros de grupos, reduzca gradualmente el valor de error de la función objetivo mediante la iteración hasta la convergencia y obtenga el resultado final. K-means, k-modes-Huang, k-means-CP, cluster, clustering difuso ponderado por características, CLARANS, etc.
K-means clásico:
Proceso algorítmico:
1. Seleccione aleatoriamente k objetos, cada objeto representa inicialmente el centro de un grupo;
2. Para cada objeto restante, asígnelo al grupo más cercano en función de su distancia al centro de cada grupo;
3. Vuelva a calcular el promedio de cada grupo y actualice al nuevo centro del grupo. ;
4. Repita 2 y 3 hasta que la función estándar converja.
Características:
Selecciona 1. K
2. Selección del punto central
–Aleatorio
–Múltiples rondas de aleatorización: seleccione el WCSS más pequeño.
3. Ventajas
–El algoritmo es simple y efectivo.
–Complejidad del tiempo: O(nkt)
4. Desventajas
–No apto para procesar datos esféricos.
-Los clusters de diferentes densidades y tamaños están limitados por K, lo que dificulta encontrar clusters naturales.
4.3 Algoritmo de agrupamiento basado en modelos
Suponga un modelo para cada grupo para encontrar el mejor ajuste de los datos al modelo dado. Los datos de la misma "clase" pertenecen a la misma distribución de probabilidad, es decir, se supone que los datos se generan de acuerdo con la distribución de probabilidad subyacente. Existen principalmente métodos basados en modelos estadísticos y modelos de redes neuronales, especialmente métodos basados en modelos probabilísticos. Los algoritmos basados en modelos pueden localizar conglomerados mediante la construcción de funciones de densidad que reflejan la distribución espacial de los puntos de datos. La agrupación basada en modelos intenta optimizar el ajuste entre los datos dados y algún modelo de datos.
Algoritmo de red neuronal SOM;
Este algoritmo supone que existe una determinada estructura o secuencia topológica en el objeto de entrada y puede realizar la transformación desde el espacio de entrada (n-dimensional) al plano de salida (bidimensional) Mapeo de reducción de dimensionalidad. Este mapeo tiene propiedades que preservan las características topológicas y tiene fuertes vínculos teóricos con el procesamiento cerebral real.
La red SOM incluye una capa de entrada y una capa de salida. La capa de entrada corresponde a un vector de entrada de alta dimensión y la capa de salida consta de una serie de nodos ordenados organizados en una cuadrícula bidimensional. Los nodos de entrada y los nodos de salida están conectados por vectores de peso. Durante el proceso de aprendizaje, se encuentra y actualiza la unidad de la capa de salida con la distancia más corta, es decir, la unidad ganadora. Al mismo tiempo, los pesos de las regiones adyacentes se actualizan para mantener las características topológicas del vector de entrada.
Proceso del algoritmo:
1. Inicialización de la red, asigne un valor inicial al peso de cada nodo en la capa de salida
2. muestras Seleccione el vector de entrada para encontrar el vector de peso con la distancia más pequeña desde el vector de entrada;
Defina la unidad ganadora y ajuste el peso cerca de la unidad ganadora para acercarlo al vector de entrada;<. /p>
4. Proporcione nuevas muestras y realice capacitación;
5. Reduzca el radio del vecindario, reduzca la tasa de aprendizaje, repita hasta que sea menor que el valor permitido y genere los resultados de la agrupación.
4.4 Algoritmo de agrupamiento basado en densidad
Siempre que la densidad (número de objetos o puntos de datos) de las áreas adyacentes exceda un cierto umbral, el agrupamiento continuará y es bueno para resolver irregularidades. formas Problemas de agrupamiento, ampliamente utilizados en el procesamiento de información espacial, SGC, GCHL, algoritmo DBSCAN, algoritmo OPTICS y algoritmo DENCLUE.
Escaneo de Base de Datos:
Funciona bien para áreas concentradas. Para encontrar clústeres con formas arbitrarias, este método trata los clústeres como regiones de objetos densos en el espacio de datos separados por regiones de baja densidad. Un método de agrupamiento basado en densidad basado en regiones conectadas de alta densidad divide regiones de densidad suficientemente alta en grupos para encontrar grupos de formas arbitrarias en datos espaciales ruidosos.
4.5 Algoritmo de agrupamiento basado en cuadrículas
Los métodos basados en cuadrículas cuantifican el espacio del objeto en un número limitado de unidades para formar una estructura de cuadrícula. Todas las operaciones de agrupación se realizan en esta estructura de cuadrícula (es decir, espacio cuantificado). ¿La principal ventaja de este método es su procesamiento? Es muy rápido y su velocidad de procesamiento no tiene nada que ver con la cantidad de objetos de datos, solo con la cantidad de unidades en cada dimensión en el espacio cuantificado. Sin embargo, la mejora de la eficiencia de este algoritmo se produce a expensas de la precisión de los resultados de la agrupación. A menudo se utiliza junto con algoritmos basados en densidad. Los algoritmos representativos incluyen el algoritmo STING, el algoritmo CLIQUE, el algoritmo WAVE-CLUSTER, etc.
?