¿Cuáles son los algoritmos de agrupamiento utilizados para la minería de datos y cuáles son sus ventajas?

1. Algoritmo de agrupamiento jerárquico

1.1 Agrupación de agregación

1.1.1 La similitud depende de la distancia: enlace único: distancia más cercana, enlace completo: distancia más lejana , Average-Link: distancia promedio

1.1.2 El algoritmo más representativo

1) Algoritmo CURE

Características: un número fijo de representantes Los puntos con el mismas características representan la misma clase

Ventajas: identifica grupos con formas complejas y diferentes tamaños, y filtra puntos aislados

2) Algoritmo ROCK

Características: Mejora de el algoritmo CURE

Ventajas: Igual que el anterior, y aplicable a datos con atributos de categoría

3) Algoritmo CHAMELEON

Características: Utiliza tecnología de modelado dinámico

1.2 Descomposición y agrupación

1.3 Ventajas y desventajas

Ventajas: Adecuado para conjuntos de datos de cualquier forma y atributos, control flexible de la granularidad de la agrupación en diferentes niveles, fuerte capacidad de agrupación;

Desventajas: prolonga en gran medida el tiempo de ejecución del algoritmo y no puede retroceder el procesamiento

2. Algoritmo de agrupamiento dividido

2.1 Clase de agrupamiento basado en densidad

2.1.1 Características

Conecta áreas adyacentes con suficiente densidad para manejar eficazmente datos anormales, utilizados principalmente para agrupar datos espaciales

2.1.2 Algoritmos típicos

1) DBSCAN: regiones de crecimiento continuo con densidad suficientemente alta

2) DENCLUE: agrupación según la densidad de puntos de datos en el espacio de atributos, la densidad y combinación de cuadrícula y procesamiento

3) OPTICS, DBCLASD, CURD: todos tienen DBSCAN mejorado de acuerdo con las diferentes densidades de datos presentados en el espacio

2.2 Clase de agregación basada en cuadrícula

2.2.1 Características

Utilice la estructura de datos de cuadrícula multidimensional del espacio de atributos para dividir el espacio en un número limitado de unidades para formar una estructura de cuadrícula;

1) Ventajas: el tiempo de procesamiento no tiene nada que ver con la cantidad de objetos de datos y el orden de entrada de los datos. Puede procesar cualquier tipo de datos.

2) Desventajas: El tiempo de procesamiento está relacionado con la cantidad de unidades divididas en cada dimensión del espacio. hasta cierto punto, la calidad y precisión de la agrupación se reducen

2.2.2 Algoritmo típico

1) STING: basado en la resolución múltiple de la cuadrícula, el espacio se divide en unidades cuadradas, correspondiente a diferentes resoluciones

2) STING: STING mejorado, utilizado para procesar datos espaciales que evolucionan dinámicamente

3) CLIQUE: combinando las ideas de agrupación de cuadrícula y densidad, puede manejar grandes escalar datos de alta dimensión

4) WaveCluster: basado en ideas de procesamiento de señales

2.3 Agrupación basada en teoría de grafos

2.3.1 Características

Convierta a un problema de optimización combinatoria y utilice la teoría de grafos y algoritmos heurísticos relacionados para resolverlo, construya el número de generación mínimo del conjunto de datos y luego elimine gradualmente el borde más largo

1) Ventajas: No se requiere similitud Cálculo

2.3.2 Dos formas de aplicación principales

1) Partición basada en hipergráficos

2) Partición de gráficos basada en espectros

2.4 Agrupación de redistribución iterativa basada en error al cuadrado

2.4.1 Idea

Optimice gradualmente los resultados de la agrupación y mueva continuamente el conjunto de datos objetivo a cada centro de clúster Redistribuya para obtener la solución óptima

2.4.2 Algoritmo específico

1) Algoritmo de agrupamiento probabilístico

Maximización de expectativas, capaz de manejar datos heterogéneos y Procesa registros con estructuras complejas, puede procesar continuamente lotes de datos, tiene capacidades de procesamiento en línea y produce resultados de agrupación que son fáciles de interpretar

2) Algoritmo de agrupación de vecinos más cercanos: ***algoritmo de vecino más cercano compartido SNN

Características: Combinación métodos basados ​​en densidad e ideas ROCK, reteniendo K más cercano

Número y matriz de similitud simplificados del vecino

Desventaja: la complejidad del tiempo aumentó a O(N^2)

3) Algoritmo K-Medioids

Características: Utilice un cierto punto en la clase para representar el clúster

Ventajas: puede manejar cualquier tipo de atributos no sensibles a datos anormales

4) Algoritmo K-Means

1 》Características: el centro de agrupación está representado por el promedio de todos los datos en cada categoría

2》Defectos del algoritmo K-Means original: la calidad de los resultados depende de la selección del centro de agrupación inicial, fácil Al caer en una solución óptima local, no hay criterios a seguir para la selección de valores K, es sensible a datos anormales, solo puede procesar datos con atributos numéricos y la estructura de agrupamiento puede estar desequilibrada

3》K-Means cambia el cuerpo

Bradley y Fayyad et al.: reducen la dependencia del centro y se puede aplicar a conjuntos de datos a gran escala

Dhillon et al.: ajustan el método del centro de recálculo durante el proceso de iteración para mejorar el rendimiento

Zhang et al.: proceso de optimización iterativa de ajuste de asignación suave de peso

Sarafis: aplicación de algoritmo genético a la construcción de la función objetivo

Berkh in et al.: La aplicación se extiende a la clase de agrupamiento distribuido

También hay: utilizar la idea divisoria de la teoría de grafos para equilibrar los resultados del agrupamiento y la función objetivo correspondiente en el algoritmo original a un modelo de mezcla gaussiana isotrópica

5) Desventajas óptimas

Ventajas: la velocidad de convergencia rápida más utilizada se puede extender a conjuntos de datos a gran escala

Desventajas: tiende a identificar distribución convexa, tamaño y densidad similares. La selección del centro y la agrupación de ruido tienen un gran impacto en los resultados.

Algoritmo de agrupación basado en restricciones

Restricciones sobre objetos individuales, Restricciones sobre parámetros de agrupamiento; todas provienen del conocimiento empírico en campos relacionados

3.2 Aplicaciones importantes

Agrupación de datos en un espacio bidimensional con datos de obstáculos, como COD (agrupación con distancia obstruida): la distancia de obstáculos entre dos puntos reemplaza la distancia euclidiana general

3.3 Deficiencias

Por lo general, solo se pueden manejar datos específicos necesidades en campos de aplicación específicos

4. Algoritmo de agrupamiento para datos de alta dimensión

4.1 Factores de origen de dificultad

1) La aparición de atributos irrelevantes hace que los datos se pierdan la tendencia a la agrupación

2) El límite de distinción se vuelve borroso

4.2 Solución

1) Reducción de la dimensionalidad de los datos originales

2 ) Agrupación subespacial

CACTUS: Proyección del espacio original en un plano bidimensional

CLIQUE: Combinando las ideas de agrupación basadas en densidad y cuadrícula, basándose en el algoritmo Apriori

3) Tecnología de agrupamiento conjunto

Características: Agrupación simultánea de puntos de datos y atributos

Texto: Método algebraico basado en un gráfico de partición bidireccional y su partición mínima

4.3 Deficiencias: inevitablemente provoca la pérdida de información de datos originales y la reducción de la precisión de la agrupación