PDF de programación - Tesis: Jesus Carrasco - Clasificadores Basados en Conjuntos de Representantes

CIIT"O D£ INVE. STIG.t.CttW Y IU:

ESH1n:cs '-VA~?J. !ItS &EL

I. P. N.

11 18 LIOT E:GA
'!I!GENIERIA ELECTRICA

Centro de Investigacion y Estudios A vanzados

Departamento de lngenierfa Electrica

Seccion de Computacion

Uffl•t 0! IWV[Sli6 >.CIIN T .,

r~ o::,·:5 "-Y.l'\:ZH I S tEl

L r·. N .

ia lid: L I C)T.:_~- C A

Clasificad~i~§~~~a~bc;~ftAConjuntos de

Representantes

Tesis que para obtener el grado de

Maestro en Ciencias

con especialidad en

lngenieria Electrica

Presenta

JesUs Ariel Carrasco Ochoa

1994

.... ,,

1 "'" nr-1'{ 'il(,
,, :H.-. 11- t:"ero, q_.r
I •1-{l 0.:0

.DO IV ~ -

Agradecimientos

A Lucia Angelica De Ia Vega Doria, par su apoyo durante Ia realizaci6n de este

trabajo, durante toda Ia maestria y durante toda Ia vida.

Ami madre Guadalupe Ochoa Vda. de Carrasco, par su esfuerzo y apoyo durante

toda Ia vida.

A Jose Ruiz Shulcloper por haber dirigido el trabajo de tesis y por el apoyo

brindado hasta Ia culminaciOn del mismo.

A Sergio Victor Chapa Vergara y Jose Oscar Olmedo Aguirre por sus valiosos

consejos, los cuales ayudaron a mejorar el resultado de esta tesis.

AI lnstituto Nacional de Astrofisica Optica y Electronica (INAOE), por habenne
permitido ingresar en su plan de superaci6n academica y por su apoyo durante
los dos aiios de Ia maestria.

AI Consejo Nacional de Ciencia y Tecnologia (CONACYT), por el apoyo
econ6mico que me brind6 a traves de su programa de becas para estudios de
posgrado.

Contenido

Introducci6n

I. Reconocimiento de Patrones

1.1. Modelaci6n Matem3.rica
1.2. Planteamiento Fonnal
1.3. Funci6n de Semejanza y Criterio de Comparaci6n
1.4. lntroducci6n a Ia Teoria de Testores
1.5. Relevancia 1nformaciona1
1.6. Algoritmos de Votaci6n
I. 7. Subconjuntos Difusos
1.8. ConclusiOn

2. Clasificaci6n usando Conjuntos de Representantes

2.1. Definicion

2.1.1. Caso Booleano

2. I. I. I. Representantes
2. 1.1.2. Clasificacion

2.1.2. Caso Metrico

2. 1.2. 1. Representantes
2.1.2.2. Clasificacion

2. 1.3. Ejemplo

2.2. Limitaciones

2.2.1. Tipo de Problemas
2.2.2. Restricciones
2.2.3. Semejanza y Comparaci6n lmplicitas

2.3. Conclusion

3. Estimaci6n de Par3metros

3. 1. Construccion de los Sistemas de Conjuntos de Apoyo {Q}j

3.1.1. Caso Booleano
3. I. 2. Caso General

3.2. Determinacion de los Umbrales £~
3.3. Estimaci6n de los Pesos lnforrnacionales
3.4. DeterminaciOn de los Parametres 1'\j
3.5. Conclusion

(.l!'! ~ , ~ f-'-

l !\~[ ST 11P- Ci8M l' ti

£S •• :3

' ,z••ss en

I. P. N.

&l ! 8 L
,., r >NiERIA ELEC TRIC.l

l f.::- T E 0 A

1
2
3
5
8
9
11
16
18

19
19
20
21
22
23
23
24
25
28
28
29
29
29

31
31
31
3 5
35
36
37
39

4. Extensiones aJ Metoda de Clasificaci6n

4.1. Rasgos en Espacios no Metricos

4.1.1. Distintos Criterios de Comparaci6n de Semejanza

4.2. Distinta Funci6n de Semejanza
4.3. Clases Difusas
4.4. Ami.lisis de Complejidad
4.5. ConclusiOn

5. Estimaci6n de Parametres con Distinta Funci6n de Semejanza

5.1. Construccion de los Sistemas de Con juntos de Apoyo {Q} j
5.2. Estimaci6n de los Pesos lnfonnacionales
5.3. Determinacion de los Parametres Tlj y oi
5.4. Analisis de Complejidad

5.4.1. Estimacion de {Q}j
5.4.2. Estimaci6n de Pesos Informacionales
5.4.3. EstimaciOn de los Panimetros Tlj y 8j

5.5. ConclusiOn

6. Estimaci6n de Par8metros con Clases Difusas

6.1. Construccion de los Sistemas de Conjuntos de Apoyo {Q}j
6.2. Estimaci6n de los Pesos lnfonnacionales
6.3. Determinacion de los Parametros 'lj y oi
6.4. An:ilisis de Complejidad

6.4.1. Estimacion de {Q}j
6.4.2. EstimaciOn de Pesos lnfonnacionales
6.4.3. Estimacion de los Parametres 'lj y oi

6.5. ConclusiOn

7. Sistema C-REP. Implementaci6n

7.1. Organizaci6n del Sistema
7.2. Caracteristicas del Sistema
7.3. Guia del Usuario

7.3. 1. Datos
7.3.2. Parametros
7.3.3. Representantes
7.3.4. Clasificacion
7.3.5. Ayuda

7.4. Formato de los Archives
7.5. Estructuras de Datos
7.6. ConclusiOn

40
40
41
42
44
49
50

52
52
55
57
58
58
59
61
62

63
63
66
67
68
69
70
72
73

74
74
76
77
77
78
79
79
80
80
84
90

Conclusiones

A Datos de los Ejemplos

A 1. Datos para Bllsqueda de Hidrocarburos
A.2. Datos del Ejemplo de Circunferencias

Referencias

91

97
97
101

103

lntroduccion

Los especialistas de algunas ciencias poco formalizadas, tales como Ia
Geologia, Ia Medicina, etc, frecuentemente se enfrentan al problema de
discriminar objetos de diferentes clases y ocupan para Ia descripci6n de los
mismos, variables de diferentes tipos, las cuales pueden ser cualitativas o
cuanritativas. Las clases entre las que se tiene que discriminar pueden o no ser
mutuamente exc1uyentes, o incluso los objetos pueden pertenecer con diferentes
grados a cada una de estas clases, ademils puede ser que en algunos de los objetos
de muestra se desconozcan los valores de uno o mas de los atributos que los
describen. En adelante, los atributos o caracteristicas que se utilizan para describir
a los objetos senin llamados rasgos.

Por si fuera poco, el proceso que siguen los especialistas, para realizar esta
discriminaci6n, nonnalmente no es muy clara, o peor aim, muchas veces se
desconoce Ia forma de hacerlo. De aqui que con lo Unico que se cuenta para tratar
de encontrar Ia manera de detenninar a que clase pertenece un cierto objeto, es una
muestra de objetos, para los cuales ya se conoce Ia clase a Ia que pertenecen.

Partiendo de Ia suposici6n de que se tiene una muestra de objetos ya
clasificados, es decir, un problema de clasificaci6n supervizada, los cuales en
adelante senin llamados problemas de clasificaci6n con aprendizaje, existen varios
metodos para realizar Ia clasificaci6n de nuevas objetos, en particular estaremos
interesados en el enfoque 16gico combinatoric, dentro del cual existen algunos
algoritmos, por ej emplo los algorihnos de votaci6n.

El

trabajo de esta tesis se enmarca en Ia

teoria matem3tica de
Reconocimiento de Patrones y sus aphcaciones, dentro del enfoque 16gico
combinatoric, centr<indose en Ia soluci6n de problemas de clasificaci6n con
aprendizaje. Se basa en el metodo de clasificaci6n propuesto por L. V. Baskakova
y Yu. L Zhuravliov (I].

El metoda de clasificaci6n usando conjuntos de representantes de
Baskakova y Zhuravliov(l ], trabaja con una muestra de objetos descritos en
tenninos de rasgos que toman valores en espacios metricos, agrupados en clases no
necesariamente disjuntas y con un criterio de semejanza booleano. Este metoda

pennite clasificar nuevos objetos en una o mas de estas clases, indicando
imicamente a cua.J.es clases pertenece, el objeto en cuestiOn, y a cuales no
pertenece.

El metodo propuesto por Baskakova y Zhuravliov[ 1], se basa en Ia idea de
que algunas combinaciones de valores, para ciertos rasgos, pueden dar informaciOn
a favor, o en contra, acerca de Ia pertenencia de un objeto a alguna clase, por lo
cual, primero se extraen las combinaciones de valores, para ciertos con juntos de
rasgos, que son capaces de proporcionar informaciOn a favor, o en contra, las
cuales seran llamadas representantes positives y negatives respectivamente. Una
vez hecho esto, cuando se quiere clasificar un nuevo objeto, se compara contra
todos los representantes positives y negatives, de cada clase, y basandose en Ia
cantidad de informaciOn obtenida, a favor y en contra, se decide a cuat o cuciles de
las clases pertenece el objeto.

El trabajo de esta tesis consiste en desarrollar el metodo de clasificaci6n
usando con juntos de representantes, de manera que pueda aplicarse en condiciones
menos restricrivas, por ejemplo, penniriendo trabajar con distinta funciOn de
semejanza, con clases difusas, etc, lo cual permite realizar una modelaciOn, de
problemas de clasificaciOn con aprendizaje, mis cercana a Ia realidad, y de esta
manera obtener resultados mils confiables para el espccialista, puesto que Ia
representaci6n de su problema es mas parecida a su modelo de Ia realidad. Con
todo esto se amplia el area de aplicaciOn del metoda de clasificaciOn usando
con juntos de representantes.

El metoda de clasificaciOn usando conjuntos de representantes se exriende
para que trabaje con rasgos que tomen valores en espacios no restringidos, y
empleando distintos ripos de funciones de semejanza, no necesariamente
booleanas, especial mente aquellas que toman valores en el intervale [0, 1]. Ademis
se extiende para que trabaje con clases difusas, con esto Ultimo se pennite que el
resultado indique no solamente a cuales clases pertenece, el objeto a clasificar,
sino tambien el grado con el cual pertenece a cada una de estas. Con todo esto, cl
especialista tiene que distorsionar en menor grado, su forma de ver el problema
que quiere solucionar, durante el proceso de modelaciOn matematica del mismo, y
de esta manera se pueden obtener mejores resultados, con respecto a Ia calidad de
Ia clasificaciOn, los cuales a Ia vez son mas confiables.

Adicionalmente a! desarrollo conceptual del modele de clasificaciOn usando
conjuntos de representantes, se realiz6 una implementaciOn computacional del
metodo, incluyendo las caracteristicas nuevas, las cuales permiten tener un sistema
automatizado mils versatil, para Ia soluci6n de problemas de clasificaciOn con
aprendizaje.

En el capitulo 1 se dan