ISOMAP
ISOMAP
ISOMAP
131-150
Comparacin de Mtodos de Reduccin de Dimensin
Basados en Anlisis por Localidades
Juliana Valencia-Aguirre
1
Genaro Daza-Santacoloma
2
Carlos D. Acosta
3
Germn Castellanos-Domnguez
4
Resumen
En este trabajo se realiza una comparacin de las principales
tcnicas de reduccin de dimensin no lineal basadas en anlisis
por localidades, tales como: Locally linear embedding, Isometric
feature mapping y Maximum variance unfolding. El estudio
pretende determinar, bajo criterios objetivos, cul de las tcnicas
consideradas conserva de mejor manera las propiedades locales de
la variedad, y la estructura global de los datos de entrada al
realizar un mapeo a un espacio de menor dimensin. Los mtodos
son especialmente analizados en aplicaciones de visualizacin. Las
inmersiones obtenidas son evaluadas por medio de dos criterios:
Error de Conservacin de Vecindarios y Promedio de Vecinos
Conservados. Para la validacin experimental se utilizan bases de
datos artificiales y reales que permiten confirmar visualmente la
calidad de las inmersiones obtenidas. Con base en los resultados se
observa que la tcnica Maximum variance unfolding presenta
inmersiones de mejor calidad, debido a que la tcnica de
optimizacin de este algoritmo preserva exactamente las
1 Grupo de Control y Procesamiento Digital de Seales, Universidad Nacional de
Colombia sede Manizales, jvalenciaag@unal.edu.co
2 Grupo de Control y Procesamiento Digital de Seales, Universidad Nacional de
Colombia sede Manizales, gdazas@unal.edu.co
3 Grupo de Control y Procesamiento Digital de Seales, Universidad Nacional de
Colombia sede Manizales, cdacostam@unal.edu.co
4 Grupo de Control y Procesamiento Digital de Seales, Universidad Nacional de
Colombia sede Manizales, cgcastellanosd@unal.edu.co
Fecha de recepcin: 16 de Agosto de 2010
Fecha de aceptacin: 04 de Noviembre de 2010
[132] Comparacin de Mtodos de Reduccin de Dimensin Basados en Anlisis por
Localidades
Revista Tecno Lgicas
distancias entre puntos cercanos en el espacio de baja dimensin,
conservando la estructura global de la variedad analizada.
Palabras clave
Anlisis por localidades, isometric feature mapping, locally
linear embedding, maximum variance unfolding, reduccin de
dimensin.
Abstract
In this paper, a comparison of methods for nonlinear
dimensionality reduction is proposed in order to determine which
technique preserves better the local properties, without losing the
overall structure of the original data. We seek to establish which of
these methods is the most appropriate for visualization tasks. The
embeddings obtained with each technique are evaluated by two
criteria Preservation Neighborhood Error and Preserved
Neighbors Average. The methodologies were tested on artificial
and real-world data sets which allow us to visually confirm the
quality of the embedding. The results obtained show that
Maximum variance unfolding computes high quality embeddings,
because the optimization problem pretends to preserve exactly the
local pair-wise distance between neighbors and conserve the global
manifold structure.
Keywords
Dimensionality reduction, isometric feature mapping, local
analysis, locally linear embedding, maximum variance unfolding.
Revista Tecno Lgicas No. 25, Diciembre de 2010 [133]
1. INTRODUCCIN
La reduccin de dimensin es una de las etapas ms
importantes en problemas de reconocimiento de patrones, pues
permite revelar la estructura intrnseca de los datos y extraer la
informacin ms relevante del problema en estudio, mejorando el
desempeo tanto en tareas de visualizacin como de clasificacin.
Entre los mtodos tradicionales de reduccin de dimensin se
encuentran el anlisis de componentes principales PCA (Jolliffe,
2002), y escalado multidimensional - MDS (Cox & Cox, 1994). En
PCA se calculan las proyecciones lineales que posean la mayor
varianza a partir de los vectores propios asociados a los valores
propios ms grandes de la matriz de covarianza de los datos. En
MDS, se calcula la inmersin al espacio de baja dimensin que
mejor conserve las distancias entre pares de puntos de los datos de
entrada. No obstante, los mtodos lineales de reduccin de
dimensin no son apropiados para descubrir estructuras
subyacentes de datos que residen en variedades no lineales. Con el
fin de solucionar este inconveniente, en la ltima dcada se han
desarrollado nuevos mtodos, cuyo objetivo principal es realizar un
mapeo no lineal a un espacio de baja dimensin a partir de
informacin local de los datos de alta dimensin, proyectndolos de
manera que se preserve la geometra local y la estructura global
de los datos originales. Entre los mtodos propuestos se
encuentran: Locally linear embedding - LLE (Saul & Roweis,
2003), Isometric feature mapping Isomap (Tenenbaum, 1998) y
Maximum variance unfoldin - MVU (Weinberger & Saul, 2006),
etc.
Todos los mtodos que efectan anlisis por localidades tienen
en comn la sintonizacin de un parmetro libre: el nmero
vecinos (usualmente denotado como k), el cual tiene gran
influencia en la calidad de la inmersin resultante, por lo que es
de gran importancia determinar un valor apropiado para dicho
parmetro.
Ante la diversidad de mtodos de reduccin de dimensin no
lineal que han surgido, elegir una tcnica especfica para analizar
datos que residen en variedades no lineales y que presentan
estructuras complejas, se ha convertido en una tarea difcil, pues
[134] Comparacin de Mtodos de Reduccin de Dimensin Basados en Anlisis por
Localidades
Revista Tecno Lgicas
es necesario estudiar a fondo cada uno de los mtodos para
evaluar su efectividad y desempeo. Por tal motivo, en este trabajo
se realiza una comparacin de tres tcnicas de reduccin de
dimensin no lineal: LLE, Isomap y MVU, evaluando los
resultados obtenidos con cada una de ellas por medio de dos
criterios que permiten determinar la calidad de la inmersin
resultante, e identificar posibles traslapes y prdida de la
estructura global de los datos de alta dimensin. Se realizan
pruebas con cada una de las tcnicas sobre dos bases de datos
artificiales conocidas en la literatura y sobre dos bases de datos de
imgenes.
En la primera seccin de este trabajo se exponen las tcnicas
de reduccin de dimensin a utilizar, realizando una breve
descripcin de su fundamentacin matemtica. En la segunda
seccin se presentan los criterios utilizados para medir la calidad
de las inmersiones obtenidas y se realiza una descripcin de las
bases de datos utilizadas en las pruebas. En la tercera y cuarta
seccin se presentan los resultados y la discusin. Finalmente se
presentan las conclusiones de la comparacin entre las tcnicas de
reduccin de dimensin no lineal.
2. TCNICAS DE REDUCCIN DE DIMENSIN
2.1 Locally Linear Embedding LLE
LLE es un algoritmo de aprendizaje no supervisado que realiza
un mapeo de los datos a un subespacio de baja dimensin
preservando la geometra local del espacio de datos de alta
dimensin (Saul & Roweis, 2003).
Sea X la matriz de datos de entrada de tamao n p donde se
tienen los vectores observacin , 1, ,
p
i
R i n e = x . Se asume que los
datos viven en una variedad no lineal, adecuadamente
muestreada, donde cada dato y sus respectivos k-vecinos ms
cercanos se encuentran ubicados sobre una regin lineal de la
variedad. De esta manera, los puntos del espacio de alta
dimensin pueden ser aproximados como combinaciones lineales
ponderadas de sus vecinos ms cercanos y posteriormente
Revista Tecno Lgicas No. 25, Diciembre de 2010 [135]
mapeados a un espacio de menor dimensin m donde se conserve
la geometra local de los datos (Polito & Perona, 2001). Como
salida se tienen n puntos , 1, ,
m
i
R i n e = y donde m < p.
El algoritmo LLE consta de 3 etapas. En primer lugar, para
cada
i
x se calculan los k vecinos ms cercanos empleando
distancia Eucldea. Despus de determinar los vecindarios, se
encuentran los pesos de reconstruccin W que minimicen
( )
2
1 1
n n
i ij j
i j
w c
= =
=
W x x
(1)
La ecuacin (1) est sujeta a dos restricciones: la restriccin de
dispersin 0
ij
w = si
j
x no es vecino de
i
x , y la restriccin de
invarianza
1
1
n
ij
j
w
=
=
y
, y
1
1
n
T
i i m m n
i
=
=
y y I
. Donde
n m
Y es la matriz
de datos mapeados al espacio de baja dimensin. Ahora bien, sea
( )( )
T
n n n n
= M I W I W
, se puede reescribir (2) como
( ) ( )
T
n 1 1
1
0
tr sujeto a
m
T
T
m m
n
u =
=
1 Y
Y Y MY
Y Y I
(3)
Para encontrar Y que minimice la expresin (3) se calculan los
m+1 vectores propios de M, asociados a los m+1 valores propios
ms pequeos. El primer vector propio es excluido. Los restantes
m vectores propios producen la inmersin final Y.
[136] Comparacin de Mtodos de Reduccin de Dimensin Basados en Anlisis por
Localidades
Revista Tecno Lgicas
2.2 Isometric Feature Mapping Isomap
Isomap es una tcnica de reduccin de dimensin no lineal
basada en MDS clsico. Su objetivo es preservar la geometra
intrnseca de los datos reflejada en las distancias geodsicas de la
variedad. La clave es encontrar una forma eficiente de calcular la
verdadera distancia geodsica entre observaciones, dada
solamente su distancia Eucldea en el espacio de alta dimensin
(Tenenbaum et al., 2000).
Para puntos vecinos, la distancia Eucldea del espacio de alta
dimensin proporciona una buena aproximacin a la distancia
geodsica. Para puntos lejanos, la distancia geodsica puede ser
aproximada aadiendo una secuencia saltos entre puntos vecinos
(Tenenbaum et al., 2000). Es otras palabras, Isomap asume que la
distancia entre puntos en el espacio de caractersticas es una
medida precisa de la distancia en la variedad slo a nivel local y
que estas distancias deben integrarse en caminos o trayectorias en
la variedad con el fin de obtener distancias globales.
En Isomap se asume que los datos se encuentran en una
variedad S desconocida, en un espacio de alta dimensin. Se busca
realizar un mapeo del espacio original a un espacio de menor
dimensin, que preserve lo mejor posible la estructura intrnseca
de las observaciones.
El algoritmo de Isomap se compone de tres pasos
fundamentales. En primer lugar se determina que puntos son
vecinos en la variedad S. Con este propsito es posible utilizar dos
criterios simples: el punto i se considera vecino del punto j si
pertenece a los k vecinos ms cercanos de j o si se encuentra a una
distancia menor de un radio . A partir de los vecindarios
establecidos se construye un grafo G sobre todos los datos de
entrada, y se establecen las longitudes de las aristas como ( )
x
d ij
entre puntos vecinos.
En segundo lugar se realiza el clculo de los caminos ms
cortos, estimando las distancias geodsicas ( , )
S
d i j entre todos los
pares de puntos en S y calculando las distancias de los caminos o
trayectorias ms cortas ( , )
G
d i j en el grafo G. Inicialmente
Revista Tecno Lgicas No. 25, Diciembre de 2010 [137]
( , ) ( , )
G X
d i j d i j = si i ,
j
estn conectados por una arista. En otro
caso, es decir si el punto i y el punto j no se encuentran conectados
G
d = . La matriz
{ } ( , )
G G
D d i j =
contiene las distancias de los
caminos ms cortos entre todos los pares de puntos en el grafo G.
Por ltimo se aplica MDS clsico a la matriz de distancias del
grafo
{ } ( , )
G G
D d i j =
construyendo una inmersin de los datos a un
espacio de dimensin m que preserva de mejor manera la
geometra intrnseca de la variedad original. Los puntos
i
y del
espacio de salida se eligen de manera que se minimice la funcin
de costo
( ) ( )
2 G Y
L
E t t = D D
(4)
donde
Y
D es la matriz de distancias Eucldeas
( )
( )
,
Y i j
d i j = y y
, y
2
L
A
la norma
2
L de la matriz
2
,
ij
i j
A
. El
operador t en (4) convierte las distancias en productos internos, el
cual caracteriza de forma nica la geometra de los datos y que
permite una optimizacin eficiente. El nico parmetro libre es el
factor de vecindario k o , el cual aparece en el primer paso del
algoritmo. Dicho parmetro influye sobre el desempeo la tcnica,
por lo que es importante elegir un valor apropiado para el tamao
del vecindario.
2.3 Maximum Variance Unfolding MVU
MVU es un algoritmo de reduccin de dimensin no lineal cuyo
objetivo principal es llevar a cabo la inmersin de los datos a un
espacio de baja dimensin, realizando un anlisis de localidades,
de manera que se preserven exactamente las distancias y ngulos
entre puntos cercanos (Weinberger & Saul, 2006). Este mtodo se
fundamenta en la nocin de simetra, donde simetra se entiende
como un mapeo suave e invertible que localmente luce como una
rotacin ms traslacin. Considere dos conjuntos de datos
{ }
1
n
i
i=
= X x
y
{ }
1
n
i
i=
= Y y
que tienen correspondencia uno a uno, y sea
[138] Comparacin de Mtodos de Reduccin de Dimensin Basados en Anlisis por
Localidades
Revista Tecno Lgicas
O una matriz binaria de tamao nn que indica una relacin de
vecindarios entre X y Y, tal que
j
x se considera vecino de
i
x si y
slo si 1
ij
O = (de igual forma para
j
y y
i
y ). Se dice que X y Y son
localmente isomtricos bajo la relacin de vecindarios O, si para
cada punto
i
x , existe una rotacin, reflexin y/o traslacin que
mapea precisamente
i
x y sus vecinos, en
i
y y sus vecinos.
Considere que el mapeo local entre vecindarios existir, si y
slo si se preservan exactamente las distancias y los ngulos entre
los puntos y sus vecinos. Esta restriccin se puede expresar en
trminos de producto punto. Sean
ij i j
G = x x y
ij i j
K = y y , los
elementos de las matrices de Gram de la entrada G y salida K,
respectivamente. Expresando la condicin de isometra local en
trmino de las matrices de Gram se tiene que
ii jj ij ji ii jj ij ji
K K K K G G G G + = +
(5)
Dados n puntos de entrada
p
i
R e x , es posible encontrar
m
i
R e y , donde m < p, de forma tal que los puntos de entrada y los
puntos de salida sean localmente isomtricos, y es posible plantear
el problema en trminos de matrices de Gram, es decir, se puede
encontrar una matriz
ij
K que satisfaga las restricciones de (5).
Adems de la condicin de isometra local, las salidas
i
y deben
estn centradas en el origen, de manera que se elimina un grado
de libertad de traslacin de la solucin final, as
2
0
i i j ij
i ij ij
K = = =
y y y
.
Debido a que las restricciones geomtricas de las salidas
i
y
pueden expresarse en trminos de la matriz de Gram
ij
K , se
considera el problema como una optimizacin sobre las matrices
de Gram
ij
K en lugar de los vectores
i
y . Sin embargo, slo
matrices simtricas, con valores propios positivos se pueden
interpretar como matrices de Gram y se debe restringir la
optimizacin para el cono de matrices semidefinidas (Weinberger
Revista Tecno Lgicas No. 25, Diciembre de 2010 [139]
& Saul, 2004). De esta manera el problema de optimizacin de
MVU se resume como
( ) { }
max tr
semidefinida positiva
. 0
1
ij
ij
ii jj ij ji ii jj ij ji ij
sujeto a K
K K K K G G G G ij
+ = + O =
K
K
(6)
A partir de la matriz de Gram K obtenida en el problema de
optimizacin de (6) es posible recuperar las salidas
i
y , realizando
una descomposicin de valores singulares, es decir, a partir de los
m valores propios ms grandes de la matriz K.
3. CRITERIOS DE EVALUACIN DE CALIDAD DE LA INMERSIN
En tareas de visualizacin, el principal objetivo es realizar un
mapeo de los datos a un espacio (de una, dos o tres dimensiones)
que preserve lo mejor posible su estructura intrnseca. Por esta
razn, cuando se aplica una tcnica de reduccin de dimensin es
importante establecer un criterio que permita conocer la calidad
de la transformacin y evaluar si los resultados obtenidos son
adecuados. La forma ms simple de evaluar los resultados de una
inmersin es por medio de confirmacin visual, sin embargo, esta
estrategia es subjetiva y poco fiable. Idealmente la calidad de una
inmersin a la salida puede ser juzgada a partir de la comparacin
de la misma con la estructura de la variedad original, pero
generalmente la estructura de dicha variedad no est dada y es
difcil de establecer de forma precisa. Por tal motivo, una medida
de calidad de inmersin ideal no se puede implementar en forma
general, siendo necesario entonces establecer alguna medida
alternativa.
En este trabajo se emplean dos criterios de evaluacin con el
fin de calificar objetivamente el desempeo de los resultados de
inmersin obtenidos al aplicar tres tcnicas diferentes de
reduccin de dimensin no lineal. A partir de los resultados de la
[140] Comparacin de Mtodos de Reduccin de Dimensin Basados en Anlisis por
Localidades
Revista Tecno Lgicas
reduccin se busca determinar cul mtodo preserva de mejor
manera la estructura intrnseca de los datos originales.
3.1 Error de Conservacin de Vecindarios ECV
El ECV est basado en la conservacin de la geometra local y
la co-ubicacin de los vecindarios logrando identificar posibles
traslapes en el espacio de baja dimensin (Valencia-Aguirre et al.,
2009).
( )
( ) ( )
2 2
( , ) ( , ) ( , ) ( , )
1 1 1
1 1 1
, .
2
n
i j i j i j i j
k n k
i j j
n
ECV D D D D
n k k
= = =
= +
`
)
x y x y
X Y
(7)
En la ecuacin (7) D corresponde a la distancia Eucldea
estandarizada para obtener un valor mximo igual a 1 y q
corresponde al conjunto de vecinos ms cercanos de cada punto en
el espacio de entrada, una vez realizada la inmersin, para cada
m
i
R e y se calcula el conjunto | de sus k vecinos ms cercanos y se
encuentra el conjunto correspondiente a las proyecciones de q.
Los vecinos estimados en | que no son vecinos en q conforman un
nuevo conjunto de tamao
n
k , el cual se define como
( ) =
(Fig. 1). Adems, las proyecciones de los elementos
de en X generan el conjunto con
n
k elementos. En una
inmersin ideal
( ) 0 ECV =
(Daza-Santacoloma et al., 2010,
Valencia-Aguirre et al., 2009).
3.2 Promedio de Vecinos Preservados PVC
El segundo criterio utilizado para evaluar la calidad de la
inmersin se basa en calcular el nmero de observaciones que se
preservan como parte de los vecindarios tras la inmersin. De esta
manera, teniendo en cuenta los conjuntos explicados
anteriormente, es posible calcular el promedio de vecinos
preservados como
Revista Tecno Lgicas No. 25, Diciembre de 2010 [141]
1
1
,
n
i i
i
i
PVC
n k
=
=
(8)
En la ecuacin (8) se denota la cardinalidad del conjunto como