Computacion

Clasificadores eficaces basados en
algoritmos r´pidos de b´squeda del
a
u
vecino m´s cercano
a
Departamento de Lenguajes y Sistemas Inform´ticos
a
Universidad de Alicante

Francisco Moreno Seco

Dirigida por: Luisa Mic´ Andr´s
o
e
Jose Oncina Carratal´
a
24 de febrero de 2004

II

´
Indice general
Pr´logo
o

1

I

5

Introducci´n
o

1. Reconocimiento de formas yclasificaci´n
o
1.1. Dise˜o de un sistema de Reconocimiento de Formas
n
1.1.1. An´lisis de datos . . . . . . . . . . . . . . . .
a
1.1.2. Dise˜o del clasificador . . . . . . . . . . . . .
n
1.1.3. Evaluaci´n del clasificador . . . . . . . . . . .
o
1.2. Mejoras en la regla NN . . . . . . . . . . . . . . . . .
1.3. Esquema de situaci´n del trabajo de la tesis . . . . .
o

.
.
.
.
..

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

7
7
10
10
13
14
15

2. B´ squeda del vecino m´s cercano
u
a
2.1. Espacios de representaci´n . . . . . . . . . . . . . . . . . . . .
o
2.2. B´squeda por aproximaci´n y eliminaci´n . . . . . . . . . . .
u
o
o
2.3. Algoritmos r´pidos de b´squeda . . . . . . . . . . . . . . . . .
a
u
2.3.1.K-Dimensional Tree (k-d tree) . . . . . . . . . . . . .
2.3.2. Algoritmo de Fukunaga y Narendra . . . . . . . . . .
2.3.3. Vantage Point Tree (vp-tree) . . . . . . . . . . . . . .
2.3.4. Geometric Near-neighbor Access Tree (GNAT) . . . .
2.4. La familia AESA . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.1. Approximation and Elimination Search Algorithm (AESA) . . . . . . . . . . . . . . . .. . . . . . . . . . . .
2.4.2. Linear AESA (LAESA) . . . . . . . . . . . . . . . . .
2.4.3. Tree LAESA (TLAESA) . . . . . . . . . . . . . . . . .
2.5. B´squeda r´pida de los k vecinos m´s cercanos . . . . . . . .
u
a
a

17
18
20
21
23
24
28
34
37

II

53

Aportaciones

40
43
44
48

3. Mejoras del LAESA para clasificaci´n
o
55
3.1. Ak -LAESA (versi´n 1) . . . . . . .. . . . . . . . . . . . . . . 56
o
3.1.1. Resultados preliminares . . . . . . . . . . . . . . . . . 57

´
Indice general

IV

3.1.2. Experimentos y resultados
3.2. Ak -LAESA (versi´n 2) . . . . . .
o
3.2.1. Resultados preliminares .
3.2.2. Experimentos y resultados
3.3. Ak -LAESA (versi´n 3) . . . . . .
o
3.3.1. Experimentos y resultados
3.4. Ak -LAESA (versi´n 4) . . . . . .
o3.4.1. Resultados preliminares .
3.4.2. Experimentos y resultados

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
..
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

60
63
64
67
68
71
77
79
81

4. La regla de los k vecinos seleccionados m´s cercanos
a
4.1. Aplicabilidad de la regla . . . . . . . . . . . . . . . . . . . . .
4.2. Algoritmos ampliados con la regla k -NSN . . . . . . . . . . .
4.3. Experimentos yresultados . . . . . . . . . . . . . . . . . . . .
4.3.1. Resultados con la base de datos SINTE . . . . . . . .
4.3.2. Resultados con la base de datos CROMOSOMAS . . .
4.3.3. Resultados con la base de datos UCI . . . . . . . . . .
4.3.4. Resultados con la base de datos PHONEME . . . . .
4.4. Estudio de coincidencias entre los k -NSN y los k -NN . . . . .
4.4.1. Estudio seg´n aumenta ladimensi´n . . . . . . . . . .
u
o
4.4.2. Estudio seg´n aumenta el tama˜o del conjunto de enu
n
trenamiento . . . . . . . . . . . . . . . . . . . . . . . .

89
89
91
92
95
99
103
103
104
104
107

5. B´ squeda aproximada
u
111
5.1. B´squeda aproximada usando una cola de prioridad . . . . . 112
u
5.2. B´squeda aproximada con el algoritmo de Fukunaga y Narendra113
u
5.3. B´squeda...