Selección de variables y análisis de clasi cación en datos

Selección de variables y análisis de clasi�cación en datosde alta dimensión

Tejeda, Y.E.1, Valenzuela, C.2, Nazabal, M.2, Fernández, J.R.2,Guerra,

V.3,Sánchez, J.E.3

1Departamento de Bioinformática

Universidad de las Ciencias Informáticas

2Ensayos Clínicos

Centro de Ingeniería Genética y Biotecnología

3Departamento de Matemática

Instituto de Cibernética, Matemática y Física

II Encuentro Cuba-México de Métodos Numéricos y Optimización

Tejeda, et al. (UCI, CIGB, ICIMAF) 1 / 23

Índice

1 Motivación

El problema básico que estudiamos

2 Descomposición matricial CUR

Ideas generales de CUR

Algoritmo ColumnSelect

3 Modelo de clasi�cación

Análisis Discriminante Lineal

4 Resultados y discusión

Descripción de los datos

Método de trabajo

Resultados y discusión

5 Conclusiones

Tejeda, et al. (UCI, CIGB, ICIMAF) 2 / 23

Motivación

En la minería de datos el especialista se enfrenta a menudo conmatrices donde el número de �las o columnas son muy grandes

Un área de la minería de datos es la expresión de genes en datosmicroarray que permite el monitoreo simultáneo de miles deexpresiones de genes por muestra

Una aplicación importante de la expresión de genes en datosmicroarray es la clasi�cación de muestras en categorías talescomo el tipo de tumor

Tejeda, et al. (UCI, CIGB, ICIMAF) 3 / 23

Motivación Problema básico

Índice

1 Motivación

El problema básico que estudiamos

2 Descomposición matricial CUR

Ideas generales de CUR

Algoritmo ColumnSelect

3 Modelo de clasi�cación

Análisis Discriminante Lineal

4 Resultados y discusión

Descripción de los datos

Método de trabajo

Resultados y discusión

5 Conclusiones

Tejeda, et al. (UCI, CIGB, ICIMAF) 4 / 23

Motivación Problema básico

Ensayos Clínicos

Detectar genes con niveles de expresión diferentes en ratonesC57BL6 tratados para modelar la enfermedad Esclerosis Múltiple.

Alta dimensionalidad (pocas replicas y muchas variables)

Altos niveles de ruido

Variación biológica, experimental, sistemática y al azar

Mismos genes participan en varios procesos y rutas

Tejeda, et al. (UCI, CIGB, ICIMAF) 5 / 23

Motivación Problema básico

Ensayos Clínicos

Detectar genes con niveles de expresión diferentes en ratonesC57BL6 tratados para modelar la enfermedad Esclerosis Múltiple.

Alta dimensionalidad (pocas replicas y muchas variables)

Altos niveles de ruido

Variación biológica, experimental, sistemática y al azar

Mismos genes participan en varios procesos y rutas

Tejeda, et al. (UCI, CIGB, ICIMAF) 5 / 23

Descomposición matricial CUR Ideas generales de CUR

Índice

1 Motivación

El problema básico que estudiamos

2 Descomposición matricial CUR

Ideas generales de CUR

Algoritmo ColumnSelect

3 Modelo de clasi�cación

Análisis Discriminante Lineal

4 Resultados y discusión

Descripción de los datos

Método de trabajo

Resultados y discusión

5 Conclusiones

Tejeda, et al. (UCI, CIGB, ICIMAF) 6 / 23

Descomposición matricial CUR Ideas generales de CUR

Descomposición matricial CUR

La descomposición matricial CUR permite obteneraproximaciones matriciales de menor rango para una matriz dedatos

La descomposición matricial CUR consiste en descomponer unamatriz Am×n por el producto de tres matrices C, U y R

Tejeda, et al. (UCI, CIGB, ICIMAF) 7 / 23

Descomposición matricial CUR Algoritmo ColumnSelect

Índice

1 Motivación

El problema básico que estudiamos

2 Descomposición matricial CUR

Ideas generales de CUR

Algoritmo ColumnSelect

3 Modelo de clasi�cación

Análisis Discriminante Lineal

4 Resultados y discusión

Descripción de los datos

Método de trabajo

Resultados y discusión

5 Conclusiones

Tejeda, et al. (UCI, CIGB, ICIMAF) 8 / 23

Descomposición matricial CUR Algoritmo ColumnSelect

Algoritmo ColumnSelect (Mahoney & Drineas, 2009)

πj =1

k∑kξ=1

(v

ξ

j

)21 Calcular los k principales vectores singulares derechos de A y πj

2 Mantener la j-ésima columna de A con probabilidadpj =min

{1, c ·πj

}∀ j ∈ {1, . . . , n}

3 Retornar la matriz C que consiste en las columnas seleccionadasde A

‖ A−PCA ‖F≤ (1+ ε/2) ‖ A−Ak ‖F

Tejeda, et al. (UCI, CIGB, ICIMAF) 9 / 23

Descomposición matricial CUR Algoritmo ColumnSelect

Algoritmo ColumnSelect (Mahoney & Drineas, 2009)

πj =1

k∑kξ=1

(v

ξ

j

)21 Calcular los k principales vectores singulares derechos de A y πj

2 Mantener la j-ésima columna de A con probabilidadpj =min

{1, c ·πj

}∀ j ∈ {1, . . . , n}

3 Retornar la matriz C que consiste en las columnas seleccionadasde A

‖ A−PCA ‖F≤ (1+ ε/2) ‖ A−Ak ‖F

Tejeda, et al. (UCI, CIGB, ICIMAF) 9 / 23

Descomposición matricial CUR Algoritmo ColumnSelect

Algoritmo ColumnSelect (Mahoney & Drineas, 2009)

πj =1

k∑kξ=1

(v

ξ

j

)21 Calcular los k principales vectores singulares derechos de A y πj

2 Mantener la j-ésima columna de A con probabilidadpj =min

{1, c ·πj

}∀ j ∈ {1, . . . , n}

3 Retornar la matriz C que consiste en las columnas seleccionadasde A

‖ A−PCA ‖F≤ (1+ ε/2) ‖ A−Ak ‖F

Tejeda, et al. (UCI, CIGB, ICIMAF) 9 / 23

Descomposición matricial CUR Algoritmo ColumnSelect

Otros algoritmos

paquete rCUR

Ihaka R. & Gentleman R.R: a language for data analysis and graphics

1 random

2 exact.num.random

3 top.scores

4 ortho.top.scores

5 highest.ranks

Tejeda, et al. (UCI, CIGB, ICIMAF) 10 / 23

Modelo de clasi�cación Análisis Discriminante Lineal

Índice

1 Motivación

El problema básico que estudiamos

2 Descomposición matricial CUR

Ideas generales de CUR

Algoritmo ColumnSelect

3 Modelo de clasi�cación

Análisis Discriminante Lineal

4 Resultados y discusión

Descripción de los datos

Método de trabajo

Resultados y discusión

5 Conclusiones

Tejeda, et al. (UCI, CIGB, ICIMAF) 11 / 23

Modelo de clasi�cación Análisis Discriminante Lineal

(Boulesteix, A.-L., 2004)

Análisis Discriminante Lineal (LDA)Mínimos Cuadrados Parciales (PLS) (Wold, 1975)

Cuando el número de grupos es 2, entonces se pueden ranguear las

variables según su importancia en la clasi�cación (Boulesteix, 2004)Tejeda, et al. (UCI, CIGB, ICIMAF) 12 / 23

Modelo de clasi�cación Análisis Discriminante Lineal

(Boulesteix, A.-L., 2004)

Análisis Discriminante Lineal (LDA)Mínimos Cuadrados Parciales (PLS) (Wold, 1975)

Cuando el número de grupos es 2, entonces se pueden ranguear las

variables según su importancia en la clasi�cación (Boulesteix, 2004)Tejeda, et al. (UCI, CIGB, ICIMAF) 12 / 23

Resultados y discusión Descripción de los datos

Índice

1 Motivación

El problema básico que estudiamos

2 Descomposición matricial CUR

Ideas generales de CUR

Algoritmo ColumnSelect

3 Modelo de clasi�cación

Análisis Discriminante Lineal

4 Resultados y discusión

Descripción de los datos

Método de trabajo

Resultados y discusión

5 Conclusiones

Tejeda, et al. (UCI, CIGB, ICIMAF) 13 / 23

Resultados y discusión Descripción de los datos

Tejeda, et al. (UCI, CIGB, ICIMAF) 14 / 23

Resultados y discusión Método de trabajo

Índice

1 Motivación

El problema básico que estudiamos

2 Descomposición matricial CUR

Ideas generales de CUR

Algoritmo ColumnSelect

3 Modelo de clasi�cación

Análisis Discriminante Lineal

4 Resultados y discusión

Descripción de los datos

Método de trabajo

Resultados y discusión

5 Conclusiones

Tejeda, et al. (UCI, CIGB, ICIMAF) 15 / 23

Resultados y discusión Método de trabajo

Tejeda, et al. (UCI, CIGB, ICIMAF) 16 / 23

Resultados y discusión Resultados y discusión

Índice

1 Motivación

El problema básico que estudiamos

2 Descomposición matricial CUR

Ideas generales de CUR

Algoritmo ColumnSelect

3 Modelo de clasi�cación

Análisis Discriminante Lineal

4 Resultados y discusión

Descripción de los datos

Método de trabajo

Resultados y discusión

5 Conclusiones

Tejeda, et al. (UCI, CIGB, ICIMAF) 17 / 23

Resultados y discusión Resultados y discusión

Resultados: todas las variables

Tejeda, et al. (UCI, CIGB, ICIMAF) 18 / 23

Resultados y discusión Resultados y discusión

Resultados: las primeras 1000 variables

Tejeda, et al. (UCI, CIGB, ICIMAF) 19 / 23

Conclusiones

Conclusiones

Se presenta un método de trabajo para seleccionar variables endatos microarray usando la descomposición matricial CUR

La descomposición matricial CUR por los métodos top.scores yortho.top.scores son mejores que por el método random cuandose toman todas las variables

La descomposición matricial CUR por el método random es mejorque por los métodos top.scores y ortho.top.scores cuando seseleccionan las primeras 1000 variables

Recomendaciones

Obtener un modelo de clasi�cación con las variablesseleccionadasGenerar las matrices aleatorias por programación paralelausando el paquete snow

Tejeda, et al. (UCI, CIGB, ICIMAF) 20 / 23

Conclusiones

Conclusiones

Se presenta un método de trabajo para seleccionar variables endatos microarray usando la descomposición matricial CUR

La descomposición matricial CUR por los métodos top.scores yortho.top.scores son mejores que por el método random cuandose toman todas las variables

La descomposición matricial CUR por el método random es mejorque por los métodos top.scores y ortho.top.scores cuando seseleccionan las primeras 1000 variables

Recomendaciones

Obtener un modelo de clasi�cación con las variablesseleccionadasGenerar las matrices aleatorias por programación paralelausando el paquete snow

Tejeda, et al. (UCI, CIGB, ICIMAF) 20 / 23

Conclusiones

Conclusiones

Se presenta un método de trabajo para seleccionar variables endatos microarray usando la descomposición matricial CUR

La descomposición matricial CUR por los métodos top.scores yortho.top.scores son mejores que por el método random cuandose toman todas las variables

La descomposición matricial CUR por el método random es mejorque por los métodos top.scores y ortho.top.scores cuando seseleccionan las primeras 1000 variables

Recomendaciones

Obtener un modelo de clasi�cación con las variablesseleccionadasGenerar las matrices aleatorias por programación paralelausando el paquete snow

Tejeda, et al. (UCI, CIGB, ICIMAF) 20 / 23

Conclusiones

Conclusiones

Se presenta un método de trabajo para seleccionar variables endatos microarray usando la descomposición matricial CUR

La descomposición matricial CUR por los métodos top.scores yortho.top.scores son mejores que por el método random cuandose toman todas las variables

La descomposición matricial CUR por el método random es mejorque por los métodos top.scores y ortho.top.scores cuando seseleccionan las primeras 1000 variables

Recomendaciones

Obtener un modelo de clasi�cación con las variablesseleccionadasGenerar las matrices aleatorias por programación paralelausando el paquete snow

Tejeda, et al. (UCI, CIGB, ICIMAF) 20 / 23

Apéndice Lecturas complementarias

Lecturas complementarias I

Boulesteix, A. L.

PLS dimensional reduction for classi�cation with high-dimensional

microarray data.

Statistical Applications in Genetics and Moleculas Biology, vol. 3, 1,

Article 33, 2004

Boulesteix, A.-L. & Strimmer, K.

Partial Least Squares: A Versatile Tool for the Analysis of High-

dimensional Genomic Data.

Bioinformatics. 8(1):32�44, 2006

Mahoney, M. W. & Drineas, P.

CUR matrix decompositions for improved data analysis.

PNAS. 106(3):697�702, 2009

Tejeda, et al. (UCI, CIGB, ICIMAF) 21 / 23

Apéndice Lecturas complementarias

Lecturas complementarias II

Bodor, A., Csabai, I., Mahoney, M. & Solymosi, N.

rCUR:an R package for CUR matrix decomposition.

BMC Bioinformatics. 13:103, 2012

Tejeda, et al. (UCI, CIGB, ICIMAF) 22 / 23

Apéndice Lecturas complementarias

GRACIAS

Tejeda, et al. (UCI, CIGB, ICIMAF) 23 / 23