Agrupamiento central con valores atípicos en ventanas deslizantes
Autores: Pellizzoni, Paolo; Pietracaprina, Andrea; Pucci, Geppino
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Agrupamiento central con valores atípicos en ventanas deslizantes
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Fundamental
Aprendizaje no supervisado
Valores atípicos
Modelo de transmisión
Ventana deslizante
Aproximación
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 37
Citaciones: Sin citaciones
La agrupación centrada en métricas es un primitivo fundamental de aprendizaje no supervisado. Aunque ampliamente utilizado, este primitivo se ve fuertemente afectado por el ruido en los datos, por lo que una variante más sensata busca la mejor solución que desestime un número dado de puntos del conjunto de datos, llamados valores atípicos. Proporcionamos algoritmos eficientes para esta variante importante en el modelo de transmisión bajo la configuración de ventana deslizante, donde, en cada paso de tiempo, el conjunto de datos a agrupar es la ventana de los elementos de datos más recientes. Para espacios métricos generales, nuestros algoritmos logran una aproximación y, notablemente, requieren una memoria de trabajo lineal en y solo logarítmica en . Para espacios de dimensión de duplicación limitada, la aproximación puede hacerse arbitrariamente cercana a 3. Para estos últimos espacios, mostramos, como un subproducto, cómo estimar el diámetro efectivo de la ventana, que es una medida de la dispersión de los puntos de la ventana, desestimando una fracción dada de distancias ruidosas. También proporcionamos evidencia experimental de la viabilidad práctica de los algoritmos mejorados de agrupación y estimación de diámetro.
Descripción
La agrupación centrada en métricas es un primitivo fundamental de aprendizaje no supervisado. Aunque ampliamente utilizado, este primitivo se ve fuertemente afectado por el ruido en los datos, por lo que una variante más sensata busca la mejor solución que desestime un número dado de puntos del conjunto de datos, llamados valores atípicos. Proporcionamos algoritmos eficientes para esta variante importante en el modelo de transmisión bajo la configuración de ventana deslizante, donde, en cada paso de tiempo, el conjunto de datos a agrupar es la ventana de los elementos de datos más recientes. Para espacios métricos generales, nuestros algoritmos logran una aproximación y, notablemente, requieren una memoria de trabajo lineal en y solo logarítmica en . Para espacios de dimensión de duplicación limitada, la aproximación puede hacerse arbitrariamente cercana a 3. Para estos últimos espacios, mostramos, como un subproducto, cómo estimar el diámetro efectivo de la ventana, que es una medida de la dispersión de los puntos de la ventana, desestimando una fracción dada de distancias ruidosas. También proporcionamos evidencia experimental de la viabilidad práctica de los algoritmos mejorados de agrupación y estimación de diámetro.