Resumen de información útil sobre minería de datos (4): algoritmo de agrupación

Este artículo tiene 2680 palabras y el tiempo estimado de lectura es de 7 minutos

Algoritmo de agrupamiento

Yo, Naturaleza

? p>

p>

Dividir los datos en diferentes categorías, de modo que los datos similares se clasifiquen en la misma categoría y los datos diferentes se clasifiquen en diferentes categorías

? 2. Algoritmo de clasificación Qué problemas se utilizan para resolver

La agrupación de texto, la agrupación de imágenes y la agrupación de productos facilitan el descubrimiento de patrones y resuelven el problema de los datos dispersos

, conceptos básicos de los algoritmos de agrupación

1. Clustering jerárquico vs clustering no jerárquico

- Inclusión entre diferentes categorías

2. Clustering duro vs clustering suave

3. Agrupación suave

- Agrupación dura: cada objeto pertenece a una sola clase

- Agrupación suave: cada objeto pertenece a cada clase con una cierta probabilidad

3. Representar objetos como vectores

: cada objeto se representa como un vector, que puede considerarse como un punto en un espacio de alta dimensión.

: cada objeto se representa como un vector. Espacio

- Todos los objetos forman un espacio de datos (matriz)

- Cálculo de similitud: coseno, producto escalar, distancia entre centros de masa

4. En la lista de matrices las distancias y similitudes entre objetos

5. Guarde la matriz anterior en un diccionario (guarde espacio)

D={(1, 1): 0, (1 , 2): 2, (1, 3): 6... (5, 5): 0}

6. Método de evaluación

- Evaluación interna:

? Sin estándares externos, sin supervisión

?Si las categorías similares son similares y las categorías heterogéneas son diferentes

Cuanto menor sea el valor de DB, mejor será el efecto de agrupación y viceversa

- Evaluación Externa:

Precisión: (C11 C22) / (C11 C12 C21 C22)

Precisión: C11 / (C11 C21 )

? Tasa de recuperación: C11 / (C11 C12)

?Medida F:

β representa la importancia de la precisión P. Cuanto mayor sea el valor, más importante es Configuración predeterminada Cuándo. es 1, se convierte en el valor F. Cuanto mayor sea el valor F, mejor será el efecto de agrupación.

4. ¿Qué son los algoritmos de agrupamiento?

Se dividen principalmente en algoritmos de agrupamiento jerárquico, algoritmos de agrupamiento de demarcación, algoritmos de agrupamiento basados ​​en densidad, algoritmos de agrupamiento y algoritmos de agrupamiento. Algoritmo de agrupamiento basado en densidad, algoritmo de agrupamiento basado en cuadrícula, algoritmo de agrupamiento basado en modelos, etc.

4.1 Algoritmos de agrupamiento jerárquico

Estos algoritmos, también conocidos como algoritmos de agrupamiento en árbol, segmentan o agregan datos repetidamente de forma jerárquica. Por lo general, existen algoritmos BIRCH, algoritmo CURE, algoritmo CHAMELEON, algoritmo de agrupamiento aproximado de datos de secuencia, algoritmo de promedio entre grupos, algoritmo del vecino más lejano, algoritmo del vecino más cercano, etc.

Agrupación jerárquica cohesiva:

Primero, cada objeto se trata como un grupo, y luego estos grupos atómicos se fusionan en grupos cada vez más grandes hasta que todos los objetos están en un grupo, o se reúnen. una determinada condición final.

Proceso del algoritmo:

1. Trate cada objeto como una clase y calcule la distancia mínima entre ellos.

2. Minimice la distancia Las dos clases de son; fusionado en una nueva clase;

3. Vuelva a calcular la distancia entre la nueva clase y todas las clases

4. Repita 2 y 3 hasta que todas las clases finalmente se fusionen para una clase;

Características:

1. Algoritmo simple

2. Estructura jerárquica para agrupación de conceptos (generación de árboles de conceptos, árboles jerárquicos de documentos)

3. Ambos métodos de representación de objetos de clúster son aplicables

4. Manejo de clústeres de diferentes tamaños

5. El paso de selección de clúster sigue el árbol de generación

4.2 Limitado algoritmo de agrupamiento

Especifique el número de grupos o centros de grupos de antemano y reduzca iterativamente el valor de error de la función objetivo hasta la convergencia para obtener el resultado final. K-means, K-modes-huang, K-means-cp, mds_cluster. Característica de agrupamiento difuso ponderado, CLARANS, etc.

K-means clásico:

Proceso del algoritmo:

1. Seleccione aleatoriamente k objetos, cada objeto representa inicialmente el centro de un grupo

p>

2. Para cada objeto restante, asígnelo al grupo más cercano en función de su distancia desde el centro de cada grupo

3. Vuelva a calcular el valor promedio de cada grupo y actualícelo; como el nuevo centro del grupo;

4. Repita 2 y 3 hasta que la función de criterio converja.

Características:

1. Selección de K

2. Selección del punto central

- Aleatorización

- 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 grupos de diferentes densidades y tamaños están limitados por K, lo que dificulta la búsqueda de datos naturales. clusters

4.3 Algoritmo de agrupamiento basado en modelos

Supongamos que cada cluster tiene un modelo para encontrar el mejor ajuste de los datos a un modelo determinado, donde los datos del mismo " clase" Pertenecen a la misma distribución de probabilidad, es decir, suponen que los datos se generaron de acuerdo con la distribución de probabilidad subyacente. Existen principalmente métodos basados ​​en modelos estadísticos y métodos basados ​​en modelos de redes neuronales, entre los cuales los métodos basados ​​en modelos probabilísticos son los principales. 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 un modelo de datos específico.

Algoritmo de red neuronal SOM:

Este algoritmo supone que existe alguna estructura topológica u ordenamiento en el objeto de entrada, y puede lograr la transformación desde el espacio de entrada (n dimensiones) al plano de salida (2 dimensiones) Mapeo de reducción de dimensionalidad, el mapeo tiene propiedades de preservación de características topológicas, lo que tiene estrechas conexiones teóricas con el procesamiento cerebral real.

La red SOM consta de 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 están conectados a los nodos de salida a través de 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 que los nodos de salida mantengan las características topológicas del vector de entrada.

Proceso del algoritmo:

1. Inicialice la red y asigne un valor inicial al peso de cada nodo en la capa de salida

2. Seleccione aleatoriamente entre; la muestra de entrada Seleccione el vector de entrada y encuentre el vector de peso con la distancia más pequeña desde el vector de entrada

3. Defina la unidad ganadora y ajuste el peso del área adyacente de la unidad ganadora para hacer; más cerca del vector de entrada;

4. Proporcionar nuevas muestras y realizar entrenamiento

5. Reducir el radio de vecindad, reducir la tasa de aprendizaje, repetir hasta que sea menor que el vector de entrada; valor permitido y generar 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á. Los problemas de agrupamiento de formas regulares se utilizan ampliamente en el procesamiento de información espacial, SGC y GCHL. Algoritmo DBSCAN, algoritmo OPTICS, algoritmo DENCLUE.

DBSCAN:

Funciona mejor para áreas concentradas. Para encontrar grupos de formas arbitrarias, este método trata los grupos como áreas de objetos densas divididas por áreas de baja densidad en el espacio de datos. ;Basado en el método de agrupamiento de densidad de áreas conectadas de alta densidad, este algoritmo divide áreas con densidad suficientemente alta en grupos y encuentra 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 celdas 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 que la velocidad de procesamiento es muy rápida y su velocidad de procesamiento no tiene nada que ver con la cantidad de objetos de datos, sino solo con la cantidad de unidades en cada dimensión del espacio de cuantificación. Sin embargo, esta mejora en la eficiencia del 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.