miniaturadeimagen|400x400px|Ilustración de una factorización no negativa matricial aproximada: la matriz V está representado por las dos matrices más pequeñas W y H, las cuales, cuándo se multiplican, aproximadamente reconstruyen V.

Factorización matricial no negativa (NMF o NNMF), también aproximación matricial no negativa, es un grupo de algoritmos en análisis multivariante y álgebra lineal donde una matriz V se factoriza en (habitualmente) dos matrices W y H, con la propiedad de que las tres matrices no tienen elementos negativos. Esta no negatividad hace que las matrices resultantes sean más fáciles de inspeccionar. Además, en aplicaciones tales como el procesamiento de espectrogramas de audio o actividad muscular, la no negatividad es inherente a los datos que se consideran. Dado que el problema en general no se puede resolver exactamente, comúnmente se aproxima numéricamente.

NMF encuentra aplicaciones en campos tales como visión por computadora, agrupación de documentos, quimiometría, procesamiento de señal de audio y sistemas de recomendación.

Historia En quimiometría, la factorización matricial no negativa tiene un largo historial bajo el nombre de "resolución de curva de auto modelado". En este marco, los vectores en la matriz derecha son curvas continuas en lugar de vectores discretos. Un grupo de investigadores finlandeses realizaron a mediados de la década de 1990 un trabajo temprano sobre factorizaciones de matrices no negativas bajo el nombre de factorización de matriz positiva. Se hizo más conocido como factorización nonegativa de matrices después de que Lee y Seung investigaron las propiedades del algoritmo y publicaron algunos algoritmos simples y útiles para dos tipos de factorizaciones.

Bases Sea la matriz V el producto de las matrices W y H,

La multiplicación de matrices se puede implementar computando los vectores columnas de V como combinaciones lineales de los vectores columnas en W usando coeficientes proporcionados por columnas de H. Es decir, cada columna de V se puede calcular de la siguiente manera:

donde vi es el i-ésimo vector columna de la matriz producto V y hi es el i-ésimo vector columna de la matriz H.

Cuando se multiplican matrices, las dimensiones de las matrices de factores pueden ser significativamente más pequeñas que las de la matriz producto y es esta propiedad la que forma la base de NMF. NMF genera factores con dimensiones significativamente reducidas en comparación con la matriz original. Por ejemplo, si V es una matriz m × n, W es una matriz m × p, y H es una matriz p × n, entonces p puede ser significativamente menor que m y n. .

Este es un ejemplo basado en una aplicación de minería de texto: Tenemos que la matriz de entrada (la matriz a factorizar) sea V con 10000 filas y 500 columnas donde las palabras están en las filas y los documentos están en las columnas. Es decir, tenemos 500 documentos indexados por 10000 palabras. Esto significa que un vector columna v en V representa un documento. Supongamos que pedimos al algoritmo que encuentre 10 características para generar una matriz de características W con 10000 filas y 10 columnas y una matriz de coeficientes H con 10 filas y 500 columnas. El producto de W y H es una matriz con 10000 filas y 500 columnas, la misma forma que la matriz de entrada V y, si la factorización funcionó, es una aproximación razonable a la matriz de entrada V. Del tratamiento de la multiplicación matricial anterior, se destaca que cada columna en la matriz de productos WH es una combinación lineal de los 10 vectores columnas en la matriz de características W con coeficientes suministrados por la matriz de coeficientes H. Este último punto es la base de NMF porque podemos considerar cada documento original en nuestro ejemplo como construido a partir de un pequeño conjunto de características ocultas. NMF genera estas características.

Es útil pensar en cada característica (vector columna) en la matriz de características W como un arquetipo de documento que comprende un conjunto de palabras en el que el valor de la celda de cada palabra define el rango de la palabra en la característica: cuanto mayor sea el valor de la celda de una palabra mayor será el rango de la palabra en la característica. Una columna en la matriz de coeficientes H representa un documento original con un valor de celda que define el rango del documento para una característica. Ahora podemos reconstruir un documento (vector columna) de nuestra matriz de entrada mediante una combinación lineal de nuestras características (vectores columnas en W) donde cada característica se ponderará por el valor de la celda de característica de la columna del documento en H.

Propiedad de agrupamiento(clúster) NMF tiene una propiedad inherente de agrupamiento, es decir, agrupa automáticamente las columnas de datos de entrada .Es esta propiedad la que impulsa la mayoría de las aplicaciones de NMF.

Más específicamente, la aproximación de por se logra minimizando la función de error sujeto a

Además, el computado proporciona el indicador de grupo, es decir ,si , el hecho de que pertenezca al grupo . Y el computado proporciona el centroide del grupo, es decir, las columnas proporcionan el centroide del grupo de cluster. Esta representación del centroide se puede mejorar significativamente con NMF convexa.

Cuando la ortogonalidad no se impone explícitamente, la ortogonalidad se mantiene en gran medida, y la propiedad de agrupación también se mantiene. La agrupación en grupos (clúster) es el objetivo principal de la mayoría de las aplicaciones de minería de datos de NMF.

Cuando la función de error que se utilizará es la divergencia Kullback-Leibler, NMF es idéntica al análisis semántico latente probabilístico, un método popular de agrupación de documentos.C Ding, T Li, W Peng, " On the equivalence between non-negative matrix factorization and probabilistic latent semantic indexing" Computational Statistics & Data Analysis 52, 3913-3927

Tipos

Aproximada factorización no negativa de matrices Habitualmente, en NMF se selecciona el número de columnas de W y el número de filas de H, de modo que el producto WH se convertirá en una aproximación a V. La descomposición completa de V entonces equivale a las dos matrices no negativas W y H, así como a una matriz U residual, tal que: V = WH + U. Los elementos de la matriz residual pueden ser negativos o positivos.

Cuando W y H son más pequeños que V, se vuelven más fáciles de almacenar y manipular. Otra razón para factorizar V en matrices más pequeñas W y H es que si se pueden representar aproximadamente los elementos de V con datos significativamente menores, entonces se debe inferir alguna estructura latente en los datos.

Factorización convexa no negativa de matrices En la NMF estándar, la matriz factor , es decir, puede ser cualquier cosa en ese espacio. La NMF convexaC Ding, T Li, MI Jordan, Convex and semi-nonnegative matrix factorizations, IEEE Transactions on Pattern Analysis and Machine Intelligence, 32, 45-55, 2010 restringe las columnas de a combinaciones convexas de los vectores de datos de entrada . Esto mejora en muy alto grado la calidad de la representación de . Es más, la matriz factor resultante es más dispersa y ortogonal.

Factorización de rango no negativa En caso de que el rango no negativo de V sea igual a su rango real, V = WH se denomina factorización de rango no negativo. El problema de encontrar la NRF de V, si existe, se sabe que es NP-duro.

Diferentes funciones de costo y regularizaciones Existen diferentes tipos de factorizaciones no negativas de matrices. Los diferentes tipos surgen del uso de diferentes funciones de costo para medir la divergencia entre V y WH y posiblemente mediante la regularización de las matrices W y/o H.

Dos simples funciones de divergencia estudiadas por Lee y Seung son el error cuadrado (o norma Frobenius) y una extensión de la divergencia Kullback-Leibler a matrices positivas (la divergencia Kullback-Leibler original se define en las distribuciones de probabilidad). Cada divergencia conduce a un algoritmo de NMF diferente, por lo general minimizando la divergencia usando reglas de actualización iterativa.

El problema de factorización en la versión de error cuadrado de NMF puede establecerse como: Dado una matriz V, encuentre matrices no negativas W y H que minimicen la función

Otro tipo de NMF para las imágenes se basa en la norma de variación total.

Cuando se agrega L1 regularización (similar a Lasso) a NMF con la función de costo de error cuadrático medio, el problema resultante se puede llamar codificación dispersa no negativa debido a la similitud con el problema de codificación dispersa, aunque también se conoce como NMF.

NMF en línea Muchos algoritmos de NMF estándar analizan todos los datos juntos; es decir, toda la matriz está disponible desde el principio. Esto puede ser insatisfactorio en aplicaciones en las que hay demasiados datos para caber en la memoria o donde los datos se proporcionan de forma continua. Uno de estos usos es el filtrado colaborativo en los sistemas de recomendación, donde puede haber muchos usuarios y muchos artículos para recomendar, y sería ineficiente volver a calcular todo cuando se agrega al sistema un usuario o un elemento. La función de costo para la optimización en estos casos puede o no ser la misma que para el NMF estándar, pero los algoritmos necesitan ser bastante diferentes.http://www.ijcai.org/papers07/Papers/IJCAI07-432.pdfhttp://portal.acm.org/citation.cfm?id=1339264.1339709

Algoritmos Hay varias formas en que se puede encontrar y : la regla de actualización multiplicativa de Lee y Seung ha sido un método popular debido a la simplicidad de implementación. Este algoritmo es: Inicializa: < and no negativo. Luego actualizar los valores en y computando alternativamente:

and

Hasta que y sean estables. Tenga en cuenta que las actualizaciones se realizan de elemento en elemento, no de una multiplicación matricial.

Observamos que el factor multiplicativo W y H es la matriz identidad cuando V = W H.

Desde entonces, se han desarrollado algunos otros enfoques algorítmicos. Algunos algoritmos exitosos se basan en alternar mínimos cuadrados no negativos : en cada paso de dicho algoritmo, primero H se fija y W se encuentra mediante un solucionador de mínimos cuadrados no negativo, entonces W se fija y H se encuentra de manera análoga. Los procedimientos utilizados para resolver W y H pueden ser los mismos o diferentes, ya que algunas variantes de NMF regularizan una de las dos matrices W y H. Los enfoques específicos incluyen los métodos de descenso de gradiente proyectados, el método de conjunto activo, el método de gradiente óptimo, y el método de pivote principal del bloque entre varios otros.

Los algoritmos actualmente disponibles son subóptimos ya que solo pueden garantizar la búsqueda de un mínimo local, en lugar de un mínimo global de la función de costo. Un algoritmo probablemente óptimo es improbable en el futuro cercano ya que se ha demostrado que el problema generaliza el problema de la agrupación k-means que se conoce como NP-completo. Sin embargo, como en muchas otras aplicaciones de minería de datos, un mínimo local aún puede resultar útil.

Exacto NMF