Particionamiento de grafos bipartitos y agrupamiento de datos

Muchos tipos de datos que surgen de aplicaciones de minería de datos pueden ser modelados como grafos bipartitos, ejemplos incluyen términos y documentos en un corpus de texto, clientes y artículos de compra en el análisis de cestas de mercado y revisores y películas en un sistema de recomendación de películas. En este artículo, proponemos un nuevo método de agrupamiento de datos basado en la partición del grafo bipartito subyacente. La partición se construye minimizando una suma normalizada de pesos de aristas entre pares de vértices no emparejados del grafo bipartito. Mostramos que se puede obtener una solución aproximada al problema de minimización mediante el cálculo de una descomposición en valores singulares (SVD) parcial de la matriz de pesos de aristas asociada al grafo bipartito. Señalamos la conexión de nuestro algoritmo de agrupamiento con el análisis de correspondencia utilizado en el análisis multivariante. También discutimos brevemente el problema de asignar objetos de datos a múltiples grupos. En los resultados experimentales, aplicamos nuestro algoritmo de agrupamiento al problema de agrupamiento de documentos para ilustrar su efectividad y eficiencia.