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


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


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.


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


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.


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.


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


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


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


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.


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. !!


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.


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 .


SVD

Aplicacion: Compresion de imagenes.

Imagen original A de 359× 371 k = 10


SVD

Aplicacion: Compresion de imagenes.

k = 50 k = 100


Reduccion de dimension

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


Ventajas de las factorizaciones matriciales

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

A = WH

Figura: A = WH



Ax = W (Hx)

Figura: Ax = W (Hx)

El lado derecho requiere menos multiplicaciones.



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.


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.


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



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



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.



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.


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)


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)


Algunos Algoritmos para FMNN

Mınimos Cuadrados Alternantes No Negativos.

Regla de Actualizacion Multiplicativa.

Metodos de Gradiente descendiente.

Mınimos Cuadrados Jerarquicos.


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


Bibliografıa


la importancia de las factorizaciones matriciales no...

Documents