Resumen - Clustering de Vectores de Ranking: Teoría y Aplicaciones

Clustering de Vectores de Ranking: Teoría y Aplicaciones

2025-07-16 19:00:09

{"Ali Fattahi","Ali Eshragh","Babak Aslani","Meysam Rabiee"}

{cs.LG,cs.CC,stat.AP,stat.ME}

Este documento se adentra en el problema de la agrupación de vectores de clasificación, donde cada vector representa preferencias como una lista ordenada de enteros distintos. El enfoque está en el problema de agrupación de vectores de clasificación de k-céntricos (KRC), que tiene como objetivo dividir un conjunto de vectores de clasificación en k clusters e identificar el céntrico de cada cluster. A diferencia del algoritmo de agrupación k-medias clásico (KMC), el KRC limita tanto las observaciones como los céntricos a ser vectores de clasificación. **Puntos clave**: * **KRC vs. KMC**: El KRC es similar al KMC, pero con una restricción más estricta que tanto los puntos de datos como los céntricos deben ser vectores de clasificación. Esto introduce nuevos desafíos debido a la discretización estructurada de las variables de decisión. * **NP-hardness**: El documento establece la NP-hardness del KRC, lo que significa que encontrar la solución óptima es computacionalmente inalcanzable para grandes conjuntos de datos. * **Solución de un solo cluster**: Para el caso de un solo cluster, se deriva una solución analítica cerrada para el céntrico óptimo, que puede calcularse en tiempo lineal. * **Algoritmo KRCA**: Para abordar los desafíos computacionales del KRC, se desarrolla un algoritmo de aproximación eficiente llamado KRCA. Iterativamente refina soluciones iniciales del KMC y aprovecha la estructura única de los vectores de clasificación para mejorar la eficiencia computacional. * **Algoritmo BnB**: Se introduce un algoritmo de ramificación y límite (BnB) para la reconstrucción eficiente de clusters dentro de KRCA. Utiliza un marco de árbol de decisiones para reducir el tiempo de cómputo mientras incorpora un parámetro de control para equilibrar la calidad de la solución y la eficiencia. * **Experimentos numéricos**: Experimentos numéricos extensos en conjuntos de datos sintéticos y del mundo real demuestran que KRCA supera consistentemente las soluciones de base, proporcionando mejoras significativas en la calidad de la solución con tiempos de cómputo rápidos. **Aplicaciones**: * **Plataformas de reseñas en línea**: Personalizar calificaciones basadas en preferencias de género, mejorando la utilidad y la rentabilidad de los espectadores. * **Toma de decisiones grupales a gran escala**: Agregar diversas perspectivas y deriving soluciones de consenso que reflejen las preferencias de todos los grupos. **Significación**: Este trabajo destaca la importancia práctica del KRC para la personalización y la toma de decisiones a gran escala. Proporciona avances metodológicos e insights que pueden ser construidos en futuras investigaciones, convirtiéndose en una herramienta valiosa para resolver problemas de agrupación de vectores de clasificación en diversas aplicaciones.