Breve descripción del algoritmo de agrupamiento espacial
1.1 Algoritmo de agrupamiento espacial basado en partes
Algoritmo k-means: el usuario define las posiciones de los centroides de k grupos; agrega cada punto de datos a la posición del centroide más cercana Agrupación: recalcula la posición del centroide de cada grupo: repita los pasos dos y tres hasta que los centroides converjan. Su complejidad computacional es: T es el número de iteraciones en el cuarto paso, que es muy sensible a las posiciones iniciales de los puntos centrales del grupo y los puntos de ruido proporcionados por el usuario. Al mismo tiempo, el tiempo de ejecución es mayor cuando se procesan grandes cantidades de datos.
1.2 Algoritmo de agrupamiento espacial basado en jerarquías
El propósito del agrupamiento jerárquico es asignar objetos de datos en una estructura jerárquica, que sigue dos estrategias de script: agregación ascendente y división descendente. El método de agregación ascendente trata cada objeto como un grupo separado y luego agrega grupos con características similares comenzando en la parte inferior de toda la jerarquía y de forma recursiva hasta la parte superior. Por el contrario, el enfoque de división descendente trata todos los objetos de datos como el mismo grupo, y luego comienza en la parte superior de toda la jerarquía y avanza recursivamente hasta la parte inferior, dividiendo grupos con diferentes características. La complejidad del evento calculada es
1.3 Algoritmo de agrupamiento espacial basado en densidad
El algoritmo de agrupamiento basado en densidad tiene ventajas únicas para descubrir formas arbitrarias y los datos que causan y no requiere configuración inicial. Se requiere un número determinado de grupos. Estos algoritmos incluyen el algoritmo DBSCAN, el algoritmo OPTICS, el algoritmo DENCLUE, el algoritmo CURD, el algoritmo DBSCAN incremental, el algoritmo SDBDC, el algoritmo ST-DBSCAN, etc. DBSCAN es el primer algoritmo de agrupamiento basado en densidad propuesto. DBSCAN es el primer algoritmo de agrupamiento basado en densidad propuesto, que se define por dos parámetros básicos: radio espacial y umbral de densidad MinPts.
Conceptos básicos de DBSCAN:
La principal desventaja de este algoritmo es la complejidad del tiempo de cálculo, por lo que el proceso de agrupamiento de grandes cantidades de datos espaciales necesita pasar por un tiempo insoportable. proceso de consumo. Otra desventaja es que no puede admitir agrupaciones de densidad múltiple, agrupaciones incrementales y computación paralela. Se ha trabajado mucho para resolver estos problemas, que se pueden resumir en dos categorías principales: 1) mejora del algoritmo 2) paralelización del algoritmo; GirDBSCAN es conocido como el algoritmo DBSCAN más avanzado. Se basa en una estrategia de mallado y reduce en gran medida la complejidad temporal del algoritmo sin perder precisión computacional. Gracias a la estructura espacial superregular de la cuadrícula, se puede obtener fácilmente la distancia espacial más corta entre dos cuadrículas. Para un punto arbitrario, sus vecinos más cercanos solo existen dentro de un conjunto de cuadrícula fijo. En otras palabras, los puntos fuera del conjunto de cuadrícula no deben ser sus vecinos más cercanos, por lo que se puede omitir el cálculo de la distancia entre estos puntos, mejorando así la eficiencia computacional de. el algoritmo DBSCAN. Con base en esta idea, Gunawan divide toda la cuadrícula en cuadrículas con longitudes de lados para cálculos de agrupación de datos espaciales bidimensionales basados en la densidad, de modo que la distancia espacial máxima dentro de cada cuadrícula cuadrada es, por lo tanto, una vez que la cuadrícula es el número de puntos. en la cuadrícula alcanza o excede MinPts, entonces todos los puntos de la cuadrícula son puntos centrales y pertenecen al mismo grupo. Por lo tanto, un grupo se puede calcular mediante el conjunto máximo de cuadrículas conectadas por densidad y cuadrículas alcanzables por densidad, omitiendo así muchos cálculos de distancias punto a punto. También se pueden utilizar técnicas de diagrama de Voronoi para mejorar aún más la eficiencia computacional del algoritmo DBSCAN. Sin embargo, la construcción del diagrama de Voronoi requiere mucho tiempo. Con base en esta idea, Gan y Tao propusieron un algoritmo DBSCAN aproximado con respecto a p para obtener resultados de cálculo con precisión aproximada, pero solo requieren un tiempo de cálculo lineal con respecto a N, para reemplazar el algoritmo DBSCAN tradicional.
1.4 Agrupación basada en cuadrículas
El algoritmo de agrupación basada en cuadrículas divide el espacio de datos en cuadrículas separadas regulares y luego asigna todos los objetos de datos a la cuadrícula. En resumen: el espacio del objeto se cuantifica en un número limitado de celdas, formando una estructura de cuadrícula en la que se realiza toda la agrupación.
Presentaremos el algoritmo STING y el algoritmo CLIQUE.