Agrupamiento espectral restringido flexible

El agrupamiento restringido ha sido bien estudiado para algoritmos como K-means y agrupamiento jerárquico aglomerativo. Sin embargo, cómo codificar restricciones en el agrupamiento espectral sigue siendo un área en desarrollo. En este trabajo, proponemos un marco flexible y generalizado para el agrupamiento espectral restringido. A diferencia de algunos esfuerzos previos que codifican implícitamente las restricciones Must-Link y Cannot-Link modificando el Laplaciano del grafo o el espacio propio resultante, presentamos una formulación más natural y fundamentada, que preserva el Laplaciano original y codifica explícitamente las restricciones. Nuestro método ofrece varias ventajas prácticas: puede codificar el grado de creencia (peso) en las restricciones Must-Link y Cannot-Link; garantiza un límite inferior sobre qué tan bien se satisfacen las restricciones dadas usando un umbral especificado por el usuario; y puede resolverse de manera determinista en tiempo polinómico a través de una descomposición propia generalizada. Además, al heredar la función objetivo del agrupamiento espectral y codificar explícitamente las restricciones, gran parte del análisis existente de las técnicas de agrupamiento espectral sigue siendo válido. En consecuencia, nuestro trabajo puede plantearse como una extensión natural al agrupamiento espectral no restringido e interpretarse como la búsqueda del corte mínimo normalizado de un grafo etiquetado. Validamos la efectividad de nuestro enfoque mediante resultados empíricos en conjuntos de datos del mundo real, con aplicaciones a la segmentación de imágenes restringida y conjuntos de datos de referencia de agrupamiento con restricciones tanto binarias como de grado de creencia.