la importancia de las factorizaciones matriciales no...

La importancia de las factorizaciones matriciales nonegativas en la minerıa de datos y el procesamiento de

imagenes

Humberto Madrid, Irma Garcıa, Federico Garza

Centro de Investigacion en Matematicas AplicadasUniversidad Autonoma de Coahuila

II Encuentro Mexico-Cuba de Metodos Numericos yOptimizacion Enero 2013

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 1 / 33

Matrices

Actualmente en diversas aplicaciones se manejan grandes cantidades dedatos que son almacenados en forma matricial.

Algunos ejemplos:

Datos de censos poblaciones de INEGI

Imagenes digitales

Matrices termino-documento para realizar busquedas en internet

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 2 / 33

Ejemplos

Figura: Caption for datosinegiMadrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 3 / 33

Ejemplos

252 255 245 255 246 255 255 255255 255 254 46 52 242 251 252239 255 29 141 125 42 255 255255 17 149 131 147 157 20 24934 39 39 50 23 42 28 54

255 101 80 90 100 81 106 249240 89 255 81 108 49 80 255255 95 96 94 88 43 82 255

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 4 / 33

Introduccion

Con los datos en su representacion matricial, es posible empleartecnicas de Algebra Lineal para extraer informacion relevante.

Se utilizan en muchas ocasiones factorizaciones matriciales.

Sin embargo, debido a la gran cantidad de informacion en las basesde datos actuales, las factorizaciones clasicas no son adecuadas paratrabajar con matrices de grandes dimensiones.

Es necesario trabajar con nuevas factorizaciones: Factorizacionesmatriciales no negativas.

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 5 / 33

Factorizaciones clasicas

Factorizacion LU: La matriz A se descompone en el producto de dosmatrices triangulares.

A = LU

Es quizas la factorizacion matricial mas conocida y utilizada en laresolucion de sistemas de ecuaciones lineales.

Si Ax = b entoncesLUx = b

El sistema original se transforma en la solucion de dos sistemastriangulares

Ly = b, Ux = y

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 6 / 33

LU

Si A = LU, entonces

(a1, a2, · · · , an) = (Lu1, Lu2, · · · , Lun)

de donde

ai = Lui

= ui1l1 + ui2l2 + uinln

Podemos pensar que las columnas de L forman una base del espaciocolumna de A.

Las coordenadas de cada columna de A en la base L son los elementos dela correspondiente columna de U.

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 7 / 33

QR

Pero si hablamos de bases del espacio columna... son mejores las basesortogonales.

Factorizacion QR.

A = QR

Q ortonormal, R triangular superior.

Las columnas de Q forman una base ortogonal del espacio columnade A.

Aplicacion mas comun: mınimos cuadrados.

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 8 / 33

QR

Aplicaciones de la factorizacion QR: Motores de busqueda.

Ejemplo:

Documentos Terminos

1. Club Monarcas Morelia en el futbol de Mexico 1. monarca2. Ecologıa de la mariposa monarca 2. Morelia3. Lista de monarcas de Espana 3. futbol4. Fundacion santuario de la mariposa monarca 4. Espana5. El equipo de la fuerza Monarcas Morelia 5. mariposa6. Federacion Mexicana de futbol asociacion 6. ecologıa7. Instituto Nacional de Ecologıa

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 9 / 33

QR

La matriz termino–documento asociada es

D1 D2 D3 D4 D5 D6 D7

T1 1 1 1 1 1 0 0T2 1 0 0 0 1 0 0T3 1 0 0 0 0 1 0T4 0 0 1 0 0 0 0T5 0 1 0 1 0 0 0T6 0 1 0 0 0 0 1

,

Terminos1.monarca2.Morelia3.futbol4.Espana5.mariposa6.ecologıa

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 10 / 33

QR

Una peticion de busqueda se representa como un vector de m × 1 de laforma

q = (q1 q2 . . . qm)t

donde

qi =

{1 si el termino Ti aparece en la peticion0 en otro caso

Por ejemplo si queremos buscar documentos conteniendo las palabrasclave mariposa y monarca, la peticion se representa como el vector

q = (1 0 0 0 1 0)t

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 11 / 33

QR

Una forma de realizar la busqueda es formando el producto del vectorpeticion con la matriz termino documento, esto es, calcular

pt = qtA

en el ejemplopt = (1, 2, 1, 2, 1, 0, 0)

Si A es la matriz termino-documento de Internet, el computo de qtAresulta prohibitivo en operaciones.Conviene economizar la busqueda, una forma de hacerlo es utilizar lafactorizacion QR.

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 12 / 33

QR

Si A tiene rango r , entonces Q es m × r y R es r × n.El total de multiplicaciones para el producto qtA es de mn.

qtA = qtQR

el numero de multiplicaciones que se requieren para formar este producto:

Multiplicaciones

qtQ mr

(qtQ)R r(r+1)2 + r(n − r − 1)

TOTAL mr + r(r+1)2 + r(n − r − 1)

Ejemplo, si m = 100, n = 1000 y r = 10, tenemos que

mr +r(r + 1)

2+ r(n − r − 1) = 10045 y mn = 100000

uu Ahorro de casi el 90 % de multiplicaciones. !!

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 13 / 33

SVD

Factorizacion SVD (Singular Value Decomposition)

A = UΣV t

U base ortonormal del espacio columnaV base ortonormal del espacio renglon

Σ =

σ1

σ2

. . .

σr0

0

σ1 ≥ σ2 ≥ · · · ≥ σr ≥ 0, r es el rango de A.

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 14 / 33

SVD

Se tiene queAr = UrΣrV

tr = A

Donde considera las primeras r columnas de cada matriz.

A se puede aproximar por Ak , k < r .

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 15 / 33

SVD

Aplicacion: Compresion de imagenes.

Imagen original A de 359× 371 k = 10

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 16 / 33

SVD

Aplicacion: Compresion de imagenes.

k = 50 k = 100

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 17 / 33

Reduccion de dimension

En lugar de Ar se trabaja con Ak , k < r , con esto se trabaja en un espaciode dimension menor.

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 18 / 33

Ventajas de las factorizaciones matriciales

Sean Am×n, Wm×r , Hr×n, con r =rango(A) y

A = WH

Figura: A = WH

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 19 / 33

Ventajas de las factorizaciones matriciales

Ax = W (Hx)

Figura: Ax = W (Hx)

El lado derecho requiere menos multiplicaciones.

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 20 / 33

Ventajas de las factorizaciones matriciales

Supongamos r =rango(A)

aj = Whj = hj1w1 + hj2w2 + · · ·+ hjrwr

Esto nos dice que las columnas de W son una base para el espaciocolumna de A.

Ax = W (Hx)

nos dice que Hx son las coordenadas de Ax en la base W .En el fondo estamos trabajando en un subespacio de dimension menor.

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 21 / 33

Al trabajar con bases ortogonales se tienen elementos positivos y negativos.

En muchas aplicaciones los elementos negativos no tienen unarepresentacion en el contexto del problema.

Serıa conveniente contar con factorizaciones matriciales donde todos loselementos sean no-negativos.

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 22 / 33

Factorizaciones matriciales no negativas

A = WH

Con A ≥ 0, W ≥ 0, H ≥ 0.Ejemplo matriz termino-documento

A =

1 1 1 1 1 0 01 0 0 0 1 0 01 0 0 0 0 1 00 0 1 0 0 0 00 1 0 1 0 0 00 1 0 0 0 0 1

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 23 / 33

Factorizaciones matriciales no negativas

W =

0.0000 0.6441 0.6836 0.0000 0.36880 0.6441 0 0.0000 00 0.0000 0 0.4312 00 0 0 0 0.3688

0.0000 0 0.6836 0 00.5600 0 0.0000 0 0

H =

0 1.7858 0 0 0 0 1.7858

1.5527 0.0000 0.0000 0.0000 1.5527 0 00.0000 1.4629 0.0000 1.4629 0.0000 0 02.3191 0 0 0 0 2.3191 00.0000 0.0000 2.7113 0.0000 0.0000 0 0

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 24 / 33

Factorizaciones matriciales no negativas

a1 = W ∗ h1 = W

0

1.55270.00002.31910.0000

= 1.5527w2 + 2.3191w4

Como podemos observar la primera columna de H que corresponde alprimer documento depende de los vectores base dos y cuatro de W , lasegunda columna de W tiene las entradas uno y dos distintas de cero, esdecir esta relacionado con los terminos “monarca” y “Morelia”.El vector cuatro de W esta relacionado unicamente con el termino“futbol”, ya que solo su entrada tres es distinta de cero, estos sonprecisamente los terminos que se encuentran originalmente en eldocumento uno.De forma analoga para los otros vectores documento.

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 25 / 33

Factorizaciones matriciales no negativas

Componentes 6= 0 de H Columnas de H Terminos TemaGrupo 1 2 o 4 1, 5 y 6 Futbol, Monarcas y Morelia. Deporte.Grupo 2 1 o 3 2, 4 y 7 Ecologia, Mariposa y Monarca. Preservacion de la fauna.Grupo 3 5 3 Espana y Monarcas. Monarquıa.

Nos podemos dar cuenta que las factorizaciones no negativas de matricestambien pueden funcionar como una herramienta de agrupamiento dedocumentos.

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 26 / 33

Factorizaciones matriciales no negativas

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 27 / 33

Factorizacion Matricial No Negativa.

Dada una matriz AAAm×n, encontrar WWW ,HHH tales que:

AAA = WWWHHH

o

mınW≥0,H≥0

‖AAA−WWWHHH‖F

‖ · ‖F representa la norma de Frobenius.Donde,

WWWm×k ,HHHk×n

WWW ≥ 0,HHH ≥ 0

k ≤ min(m, n)

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 28 / 33

Algunas Aplicaciones

Restauracion de imagenes.

Agrupamiento de datos.

Minerıa de textos.

Inspeccion de correo electronico.

Reconocimiento de rostros.

Reconocimiento de escritura a mano.

Clasificacion de texturas.

Bioinformatica (Expresion de genes, microarreglos de ADN)

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 29 / 33

Algunos Algoritmos para FMNN

Mınimos Cuadrados Alternantes No Negativos.

Regla de Actualizacion Multiplicativa.

Metodos de Gradiente descendiente.

Mınimos Cuadrados Jerarquicos.

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 30 / 33

Restauracion de imagenes

Imagen Original

−→

252 255 245 255 246 255 255 255255 255 254 46 52 242 251 252239 255 29 141 125 42 255 255255 17 149 131 147 157 20 24934 39 39 50 23 42 28 54

255 101 80 90 100 81 106 249240 89 255 81 108 49 80 255255 95 96 94 88 43 82 255

Datos ausentes.

−→

252 255 245 255 246 × × ×255 255 254 46 52 × × ×239 255 29 141 125 × × ×255 17 149 131 147 157 20 24934 39 39 50 23 42 28 54

255 101 80 90 100 81 106 249240 89 255 81 108 49 80 255255 95 96 94 88 43 82 255

↓

Imagen Restaurada ←− Matriz “Restaurada”Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 31 / 33

Restauracion de imagenes

Imagen Original Datos ausentes

Imagen restaurada

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 32 / 33

Bibliografıa

Madrid, Garcıa, Garza (UAdeC) FMNN minerıa datos y procesamiento imag. Enero 2013 33 / 33