Algoritmos de la familia FOREL

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 14 de enero de 2020; la verificación requiere 1 edición .

FOREL (Formal Element) es un algoritmo de agrupamiento basado en la idea de combinar objetos en un solo grupo en las áreas de mayor concentración.

Propósito de la agrupación

Divida la muestra en tal número (previamente desconocido) de taxones para que la suma de las distancias desde los objetos del grupo hasta los centros del grupo sea mínima para todos los grupos. Es decir, nuestra tarea es identificar grupos de objetos lo más cerca posible entre sí, que, en virtud de la hipótesis de similitud, formarán nuestros clústeres.

El funcional de calidad minimizado por el algoritmo

F=\sum_{{j=1}}^{k}\sum_{{x\in K_{j}}}\rho (x,W_{j}),

donde la primera suma es sobre todos los conglomerados de muestra, la segunda suma es sobre todos los objetos que pertenecen al conglomerado actual , y es el centro del conglomerado actual, y es la distancia entre los objetos. $X$ $K_{j}$ $W_j$ $\rho (x, y)$

Requisitos previos para el trabajo

Cumplimiento de la hipótesis de la compacidad , que supone que los objetos cercanos entre sí con una alta probabilidad pertenecen al mismo grupo (taxón).
La presencia de un espacio lineal o métrico de objetos agrupados.

Datos de entrada

Muestreo por conglomerados

Se puede especificar mediante descripciones de características de objetos: un espacio lineal o una matriz de distancias por pares entre objetos.
Nota: en tareas reales, a menudo es imposible o inútil almacenar todos los datos, por lo que los datos necesarios se recopilan en el proceso de agrupación.

El parámetro R es el radio de búsqueda de concentraciones locales.

Puede configurarse tanto a partir de consideraciones a priori (conocimiento del diámetro del racimo) como ajustarse mediante un control deslizante.

En modificaciones, es posible introducir el parámetro k — el número de grupos.

Pie de imprenta

Agrupación en un número previamente desconocido de taxones.

Cómo funciona

En cada paso, seleccionamos aleatoriamente un objeto de la muestra, inflamos una esfera de radio R a su alrededor, elegimos el centro de gravedad dentro de esta esfera y lo convertimos en el centro de la nueva esfera. Es decir, en cada paso movemos la esfera en la dirección de la concentración local de objetos de muestra, es decir, tratamos de capturar tantos objetos de muestra como sea posible con una esfera de radio fijo. Después de que el centro de la esfera se estabilice, marcamos todos los objetos dentro de la esfera con este centro como agrupados y los descartamos de la muestra. Repetimos este proceso hasta agrupar toda la muestra.

Algoritmo

Seleccionamos aleatoriamente el objeto actual de la selección;
Marcamos los objetos de muestra ubicados a una distancia menor que R del actual;
Calculamos su centro de gravedad, marcamos este centro como un nuevo objeto actual;
Repita los pasos 2 y 3 hasta que el nuevo objeto actual coincida con el antiguo;
Marcamos los objetos dentro de la esfera de radio R alrededor del objeto actual como agrupados, los descartamos de la selección;
Repita los pasos 1 a 5 hasta que toda la muestra esté agrupada.

Pseudocódigo del algoritmo en un lenguaje tipo C :

# define R 30 // ancho de búsqueda de agrupamiento local : parámetro de entrada del algoritmo clusterization_not_finished () ; // están todos los objetos agrupados get_random_object (); // devuelve un objeto arbitrario no agrupado get_neighbour_objects ( tipo * objeto ); // devuelve una matriz de objetos ubicados <= R desde el centro_de_objetos actual ( tipo * masa_de_objetos ) ; // devuelve el centro de gravedad de los objetos especificados delete_objects ( tipo * mass_of_objects ); // elimina los objetos especificados de la selección ( ya los hemos agrupado ) while ( clusterisation_not_finished ( )) { objeto_actual = obtener_objeto_aleatorio ( ); vecinos_objetos = obtener_vecinos_objetos ( actual_objeto ); objeto_centro = centro_de_objetos ( objetos_vecinos ); while ( center_object ! = current_object ) // hasta que el centro de gravedad se estabilice { current_object = center_object ; vecinos_objetos = obtener_vecinos_objetos ( actual_objeto ); objeto_centro = centro_de_objetos ( objetos_vecinos ); } eliminar_objetos ( objetos_vecinos ); }

Heurística del centro de gravedad

En el espacio lineal, el centro de masa;
En un espacio métrico, un objeto, cuya suma de distancias es mínima, entre todas dentro de la esfera;
Un objeto que, dentro de una esfera de radio R, contiene el número máximo de otros objetos de toda la selección (lento);
El objeto que contiene el máximo número de objetos dentro de una esfera de radio pequeño (de una esfera de radio R).

Observaciones

Se prueba la convergencia del algoritmo en un número finito de pasos;
En el espacio lineal, el centro de gravedad puede ser un punto arbitrario en el espacio, en el espacio métrico, solo el objeto de la muestra;
Cuanto menor sea R, más taxones (grupos);
En el espacio lineal, la búsqueda del centro ocurre en el tiempo O(n), en el espacio métrico O(n²);
El algoritmo logra los mejores resultados en muestras con buen cumplimiento de las condiciones de compacidad;
Al repetir iteraciones, es posible disminuir el parámetro R, para la convergencia más rápida;
La agrupación depende en gran medida de la aproximación inicial (selección del objeto en el primer paso);
Se recomienda volver a ejecutar el algoritmo para eliminar la situación de agrupamiento "malo", debido a una elección fallida de los objetos iniciales.

Beneficios

La precisión de minimizar el funcional de calidad (con una selección exitosa del parámetro R);
Visualización de visualización de agrupamiento;
Convergencia del algoritmo;
La posibilidad de operaciones en los centros de los grupos: se conocen en el curso del algoritmo;
Capacidad para calcular funcionales de calidad intermedia, por ejemplo, la longitud de una cadena de concentraciones locales;
Posibilidad de probar hipótesis de similitud y compacidad en el proceso de operación del algoritmo.

Desventajas

Rendimiento relativamente bajo (se soluciona la introducción de la función de recalcular la búsqueda del centro al añadir 1 objeto dentro de la esfera);
Mala aplicabilidad del algoritmo con poca separabilidad de la muestra en conglomerados;
Inestabilidad del algoritmo (dependencia de la elección del objeto inicial);
Partición arbitraria por número en grupos;
La necesidad de un conocimiento a priori sobre el ancho (diámetro) de los racimos.

Complementos

Después de que el algoritmo haya trabajado en el agrupamiento terminado, puede realizar algunas acciones:

Selección de los objetos más representativos (representativos) de cada clúster. Puede elegir los centros de los conglomerados, puede elegir varios objetos de cada conglomerado, teniendo en cuenta un conocimiento previo sobre la representatividad requerida de la muestra. Así, de acuerdo con el agrupamiento terminado, tenemos la oportunidad de construir la muestra más representativa;
Recálculo de clustering (multinivel) utilizando el método KNI.

Alcance

Resolver problemas de agrupamiento;
Resolución de problemas de clasificación de una muestra.

Véase también

análisis de conglomerados

Literatura

Vorontsov K. V. Conferencias sobre agrupamiento y algoritmos de escalado multidimensional , Universidad Estatal de Moscú, 2007
Zagoruiko N. G., Yolkina V. N., Lbov G. S. Algoritmos para detectar patrones empíricos. - Novosibirsk: Nauka, 1985. - 999 p.
Zagoruiko NG Métodos aplicados de análisis de datos y conocimiento. - Novosibirsk: IM SO RAN, 1999. - 270 p. - ISBN 5-86134-060-9 .