Modelo Conceptual Del Conjunto De Programas C4.5

MODELO CONCEPTUAL DEL CONJUNTO DE PROGRAMAS C4.5 Tesis sometida a revici´on al Departamento de Ciencias B´asicas, Ingenier´ıa y Tecnolog´ıa de la Universidad Aut´onoma de Tlaxcala Como requisito parcial para obtener el grado de Licenciatura en Ingenier´ıa en Computaci´on

Presenta Javier Ju´arez Palma

Asesorado por: M. C. Ricardo Solano Monje

Comit´e de Revisi´on: M. C. Leticia Flores Pulido M. C. Orion Fausto Reyes Galaviz M. C. Marva Ang´elica Mora Lumbreras

Mayo del 2005

c Propiedad literaria °2005 por Javier Ju´arez Palma U.A.T. Todos los derechos reservados

Dedicatorias

A mis padres que con su esfuerzo y cari˜ no me impulsaron en mi formaci´on profesional

A mis hermanos por su apoyo y comprensi´on durante todo el tiempo que no pude estar con ellos

iii

Contenido Lista de figuras

VI

Prefacio

VI

Agradecimientos

VI

Resumen

VI

1. Preliminares

1

1.1. Introducci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2. Marco Te´ orico

1 8

2.1. Miner´ıa de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 2.2. Arboles de decisi´on . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.2.1. Representaci´on de ´arboles de decisi´on . . . . . . . . . . . . . .

9

9

2.2.2. Problemas apropiados para el aprendizaje con ´arboles de decisi´on 11 2.2.3. C4.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

2.3. El lenguaje unificado de modelado . . . . . . . . . . . . . . . . . . . .

14

2.4. Ingenier´ıa directa e inversa . . . . . . . . . . . . . . . . . . . . . . . .

17

2.5. Diagramas de clases . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

2.6. Diagramas de interacci´on . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.6.1. Diagramas de colaboraci´on . . . . . . . . . . . . . . . . . . . .

19

2.7. Diagramas de estados . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

iv

3. Estado del arte

21

3.1. Entendiendo la estructura de sistemas . . . . . . . . . . . . . . . . . .

23

3.2. Usando ingenier´ıa inversa para descubrir estructuras de software . . .

23

3.3. Experiencias del mundo real . . . . . . . . . . . . . . . . . . . . . . .

25

3.3.1. Fases de redocumentaci´on estructural . . . . . . . . . . . . . .

26

3.4. De lo procedural al paradigma orientado a objetos . . . . . . . . . . .

27

3.5. Trabajos Conexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

4. Definici´ on del problema

30

4.1. Objetivo General . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

4.1.1. Objetivos espec´ıficos . . . . . . . . . . . . . . . . . . . . . . .

31

4.2. Hip´otesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

4.3. Justificaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

5. Desarrollo

33

5.1. Planteamiento de migraci´on . . . . . . . . . . . . . . . . . . . . . . .

33

5.2. Dise˜ no del modelo orientado a objetos . . . . . . . . . . . . . . . . .

35

5.3. Proceso de dise˜ no de diagramas de clases . . . . . . . . . . . . . . . .

36

5.3.1. Identificaci´on de programas principales . . . . . . . . . . . . .

36

5.3.2. Identificaci´on de objetos, m´etodos y variables . . . . . . . . .

39

5.3.3. Identificaci´on de la relaci´on entre objetos . . . . . . . . . . . .

41

5.3.4. Acoplamiento de variables y m´etodos en el paradigma orientado a objetos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

5.4. Diagramas de colaboraci´on . . . . . . . . . . . . . . . . . . . . . . . .

47

5.5. Diagramas de estados . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

6. Conclusiones

56

6.1. Trabajos a futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A. Diagramas de colaboraci´ on

57 58

v

B. Diagramas de estado

67

vi

Lista de figuras 1.1. Comparaci´on entre la descomposic´on orientada a objetos y la descomposici´on orientada a funciones. . . . . . . . . . . . . . . . . . . . . . .

5

2.1. Un ´arbol de decisi´on para la autorizaci´on de un pr´estamo. . . . . . .

10

2.2. Definici´on de clases y atributos en el ejemplo labor-neg . . . . . . . .

14

2.3. Salida de C4.5 sobre datos labor-neg

. . . . . . . . . . . . . . . . . .

15

2.4. Forma grafica del ´arbol de decisi´on para el ejemplo labor-neg . . . . .

16

5.1. Estrategias de migraci´on al paradigma orientado a objetos. . . . . . .

34

5.2. Diagrama de secuencia para el sistema C4.5. . . . . . . . . . . . . . .

37

5.3. Lista del conjunto de programas de C4.5. . . . . . . . . . . . . . . . .

38

5.4. Relaci´on de los 4 programas principales con los dem´as programas en C4.5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

5.5. Ejemplo de transformaci´on de funciones en el formato K&R al formato de m´etodos en el POO.

. . . . . . . . . . . . . . . . . . . . . . . . .

40

5.6. Correspondencia de un archivo fuente C con un objeto. . . . . . . . .

40

5.7. Identificaci´on de las relaciones entre objetos. . . . . . . . . . . . . . .

41

5.8. Primera aproximaci´on al paradigma orientado a objetos de C4.5. . . .

43

5.9. Cambio de apuntadores por arreglos. . . . . . . . . . . . . . . . . . .

44

5.10. Eliminaci´on de variables externas. . . . . . . . . . . . . . . . . . . . .

45

5.11. Objetos derivados. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

5.12. Diagrama de clases para el generador de ´arboles de decisi´on (C4.5). .

48

5.13. Diagrama de clases para el generador de reglas de producci´on (C4.5rules). 49 vii

5.14. Diagrama de clases para el consultor de ´arboles de decisi´on (Consult).

50

5.15. Diagrama de clases para el consultor de reglas de producci´on (Consultr). 51 5.16. Correspondencia de los 4 programas principales con los diagramas de colaboraci´on. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

5.17. Proceso de obtenci´on de los diagramas de colaboraci´on. . . . . . . . .

54

5.18. Correspondencia de un diagrama de estados con el c´odigo fuente.

55

. .

A.1. Diagrama de colaboraci´on para el generador de ´arboles de decisi´on (C4.5). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

A.2. Continuaci´on del diagrama de colaboraci´on para el generador de ´arboles de decisi´on. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

A.3. Continuaci´on del diagrama de colaboraci´on para el generador de ´arboles de decisi´on. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

A.4. Continuaci´on del diagrama de colaboraci´on para el generador de ´arboles de decisi´on. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

62

A.5. Diagrama de colaboraci´on para el generador de reglas de producci´on (C4.5rules). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

A.6. Continuaci´on del diagrama de colaboraci´on para el generador de reglas de producci´on. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

64

A.7. Diagrama de colaboraci´on para el consultor de ´arboles de decisi´on (Consult). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

A.8. Diagrama de colaboraci´on para el consultor de reglas de producci´on (Consultr). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

B.1. M´etodo main de la clase C4.5 . . . . . . . . . . . . . . . . . . . . . .

68

B.2. M´etodo readName de la clase GetNames . . . . . . . . . . . . . . . .

68

B.3. M´etodo getNames de la clase GetNames . . . . . . . . . . . . . . . .

69

viii

Prefacio La cantidad de informaci´on almacenada en todo el mundo ha rebasado la capacidad humana para su an´alisis. Por tal raz´on, ha surgido un nuevo enfoque de an´alisis de informaci´on denominado miner´ıa de datos.

Motivaci´ on Personal Este trabajo de tesis surge a partir de mi inter´es en la miner´ıa de datos. Inicialmente estuve interesado en realizar un sistema para el diagnostico de enfermedades respiratorias de forma inductiva, utilizando para su programaci´on Redes Bayesianas. Sin embargo, se presentaron ciertas complicaciones para la realizaci´on de dicho sistema, entre ellas la obtenci´on de datos. Posteriormente tuve la oportunidad de iniciar un trabajo de tesis con el M. C. Ricardo Solano Monje, el cual consist´ıa en Migrar el conjunto de programas C4.5 al paradigma orientado a objetos en el lenguaje de programaci´on Java, como parte de mantenimiento al sistema. Dicho trabajo cumpl´ıa con mis intereses personales y decid´ı iniciar a leer la informaci´on necesaria para realizar el trabajo planteado. Desde luego acepte la propuesta del trabajo de tesis y continu´e con las actividades pertinentes. No obstante, durante la definici´on precisa del trabajo de tesis fue necesario realizar modificaciones que condujeron a documentar el conjunto de programas C4.5 en un modelo conceptual dando como resultado el trabajo descrito en esta tesis de licenciatura.

Organizaci´ on de la tesis Nuestro trabajo se encuentra organizado de la siguiente manera. En el Cap´ıtulo 1, damos una introducci´on que describe de manera general el inter´es de esta tesis. En el Cap´ıtulo 2, presentamos los principales conceptos necesarios para la comprensi´on ix

de los temas b´asicos tratados en nuestro trabajo. En el Cap´ıtulo 3, damos una idea de los trabajos relacionados con la evoluci´on y redocumentaci´on de sistemas. En el Cap´ıtulo 4, describimos la definici´on del problema, as´ı como tambi´en, la definici´on de objetivos. En el Cap´ıtulo 5, mostramos detalladamente lo forma de obtenci´on de un modelo conceptual para el conjunto de programas C4.5. Finalmente en el Cap´ıtulo 6, presentamos nuestras conclusiones y posibles trabajos a futuro que pueden surgir de este trabajo de tesis. Javier Ju´arez Palma Asesor: M. C. Ricardo Solano Monje Apizaco, Tlax., Junio del 2005

x

Agradecimientos

A mi t´ıo Lorenzo que con su apoyo mis estudios de licenciatura fueron m´as f´aciles de realizar

A toda mi familia por haber confiado todo el tiempo en mi

A todos mis profesores en especial a: MC. Ricardo Solano Monje, MC. Leticia Flores Pulido, MC. Orion Fausto Reyes Galaviz y MC. Marva Ang´elica Mora Lumbreras por haber dedicado un poco de su valiso tiempo en la realizaci´on de ´este trabajo

xi

Resumen La tecnolog´ıa actual ha permitido el desarrollo de aplicaciones computacionales para el apoyo en la toma de decisiones. C4.5 es una aplicaci´on que ha tenido gran ´exito para la generaci´on de modelos en forma de ´arboles de decisi´on para la toma de decisiones, dicha aplicaci´on fue desarrollada desde una perspectiva estructural. Sin embargo, este paradigma tiende a producir sistemas fr´agiles y no es factible desechar un sistema y reemplazarlo por otro totalmente nuevo en lugar de reutilizarlo, repararlo o extender su funcionalidad. Para dar mantenimiento a un sistema durante su evoluci´on, es necesario el conocimiento acerca de su arquitectura, a pesar de esto, C4.5 no cuenta con un modelo que muestre su arquitectura a nivel conceptual. Este trabajo de tesis documenta el sistema C4.5 desde una perspectiva orientada a objetos que permita mostrar las caracter´ısticas esenciales de ´este. Hemos elegido una perspectiva orientada a objetos, debido a que ha demostrando ser un concepto muy potente y unificador ofreciendo ventajas para evolucionar en el tiempo, no obstante, se requiere realizar cambios estructurales debido a las diferencias existentes entre la perspectiva estructural y la perspectiva orientada a objetos. El dise˜ no del modelo orientado a objetos toma la aproximaci´on de derivar una estructura de objetos desde la perspectiva estructural actual del sistema. El modelo generado que documenta el sistema expone la estructura interna del sistema mediante diagramas de clases, diagramas de colaboraci´on y diagramas de estados.

xii

Cap´ıtulo 1 Preliminares La toma de decisiones constituye una de las tareas m´as importantes a ser realizada en una organizaci´on, pues es f´acil suponer que al tomar decisiones correctas o incorrectas definir´an su futuro. Por ello, el uso de la tecnolog´ıa computacional ha incursionado en el desarrollo de aplicaciones de apoyo en la toma de decisiones, mediante herramientas de an´alisis de informaci´on para la identificaci´on de patrones.

1.1.

Introducci´ on

La mayor´ıa de aplicaciones que se han desarrollado para la toma de decisiones est´an basadas en la construcci´on de modelos de conocimiento, usados por un experto humano, pues en algunos casos, se considera que la tarea que un experto realiza es clasificar ejemplos asignando cosas a categor´ıas o clases determinadas por sus propiedades. Por ejemplo, Quinlan [1] cita un sistema desarrollado por American Express para asistir a autorizadores de cr´edito, en dicho sistema se considera el historial de cr´edito de un cliente en particular, y las clases correspondientes para aprobar o rechazar la transacci´on. En el sistema se analiza una autorizaci´on de cr´edito mediante la clasificaci´on del cliente y as´ı se autoriza o se rechaza el cr´edito. En un modelo de clasificaci´on, la conexi´on entre clases y propiedades puede estar 1

definida por algo tan simple como un organigrama o tan complejo y no estructurado como un manual de procedimientos. Si restringimos la discusi´on a modelos ejecutables, aquellos que puedan ser representados como un programa computacional, hay dos formas muy diferentes en las cuales pueden ser construidos. Por una parte, el modelo puede ser obtenido por entrevistar un experto o expertos; la mayor´ıa de sistemas basados en conocimiento han sido construidos de esta manera, a pesar de las dificultades bien conocidas que acompa˜ nan a este tipo de sistemas. Alternativamente, numerosos registros clasificatorios pueden ser examinados y construir un modelo inductivamente, por generalizaci´on de ejemplos espec´ıficos. Una forma de identificaci´on y representaci´on de patrones de forma sencilla en el proceso de descubrimiento de conocimiento son los ´arboles de decisi´on, cuyo proceso se basa en la partici´on del conjunto de ejemplos, seg´ un ciertas condiciones que se aplican a los valores de los atributos. Una herramienta para la generaci´on de ´arboles de decisi´on que ha tenido gran ´exito es el algoritmo ID3 desarrollado por Ross Quinlan que se basa en la creaci´on del ´arbol mediante la selecci´on de los atributos que mejor particionen a los ejemplos, mediante una medida de ganancia de informaci´on. Los nodos del ´arbol est´an etiquetados con nombres de atributos, las ramas con los posibles valores del atributo, y las hojas con las diferentes clases. Los problemas para los que funcionan los algoritmos de decisi´on deben tener las siguientes caracter´ısticas: Casos que son representados por pares atributo-valor, funciones objetivo que tienen valores de salida discretos, descripciones disyuntivas pueden ser requeridas, datos de entrenamiento que pueden contener errores y datos de entrenamiento que pueden contener valores de atributo perdidos. Sin embargo, el algoritmo ID3 tiene ciertas deficiencias, como la generaci´on de ´arboles muy extensos no comprensibles, adem´as de no considerar atributos con valores continuos y valores predidos. ID3 ha sido extendido para la eliminaci´on de estos problemas, teniendo como resultado el sistema C4.5 [1, 2]. C4.5 no es un simple algoritmo, sino m´as bien est´a integrado por un conjunto de programas escritos en el lenguaje de programaci´ on C, cuyo funcionamiento es generar

2

´arboles de decisi´on y reglas de producci´on de manera inductiva a partir de datos de entrenamiento para un problema espec´ıfico. En el proceso de generaci´on del ´arbol se consideran atributos que tienen valores continuos, adem´as de incorporar el t´ermino de poda para la reducci´on de ´arboles muy extensos. El desarrollo de software involucra enfrentarnos al manejo de cierta complejidad que se encuentra inherente al problema que intentamos solucionar, seg´ un lo menciona Booch [3], la complejidad se deriva de cuatro elementos: La complejidad del dominio del problema, la dificultad de gestionar el proceso de desarrollo, la flexibilidad que se puede alcanzar a trav´es del software y los problemas que plantea la caracterizaci´on del comportamiento de sistemas discretos. Aunado a esto, complejidad adicional es agregada debido a que los requisitos de un sistema de software cambian frecuentemente. Por otra parte tambi´en se menciona que “Cuanto m´as complejo sea el sistema, m´as abierto est´a al derrumbamiento total”, produciendo un ciclo de vida del software muy corto. No podemos permitir desechar software y reemplazarlo con uno totalmente nuevo en lugar de intentar reutilizarlo, repararlo o extender su funcionalidad, ya que un sistema grande de software es una inversi´on considerable, no es admisible el desechar un sistema existente cada vez que los requerimientos cambian. Previsto o no, los sistemas grandes tienden a evolucionar en el tiempo. Durante las ultimas dos d´ecadas, la programaci´on orientada a objetos (POO) ha llegado a ser un paradigma de programaci´on dominante. Muchos productores de software tienen inter´es en lanzar versiones orientadas a objetos de sus productos, ya que el modelo de objetos ha demostrado ser un concepto muy potente y unificador, ofreciendo ventajas tales como: la construcci´on de sistemas que sean duraderos, flexibles yu ´tiles, interes´andose los profesionales de la inform´atica en construir sistemas con este tipo de caracter´ısticas. 3

Los sistemas orientados a objetos son m´as resistentes al cambio y por lo tanto est´an mejor preparados para evolucionar en el tiempo. En realidad, la descomposici´on orientada a objetos reduce en gran medida el riesgo que representa construir sistemas de software complejos, por que est´an dise˜ nados para evolucionar de forma incremental partiendo de sistemas m´as peque˜ nos en los que ya se tiene certidumbre. Es m´as, la descomposici´on orientada a objetos resuelve la complejidad inherente al software ayudando a tomar decisiones inteligentes respecto a la separaci´on de actividades en objetos. El uso de objetos promueve la reutilizaci´on no s´olo del software, sino de dise˜ nos enteros, conduciendo a la creaci´on de marcos de desarrollo de aplicaciones reutilizables, para la mayor´ıa de los lenguajes orientados a objetos dominantes hay un gran n´ umero incremental de librer´ıas que asisten en el desarrollo de aplicaciones para muchos dominios. Se ha encontrado que los sistemas orientados a objetos son frecuentemente m´as peque˜ nos que sus implantaciones equivalentes no orientadas a objetos. Esto no s´olo significa escribir y mantener menos c´odigo, sino que la mayor reutilizaci´on del software tambi´en se traduce en beneficios de costo y planificaci´on [3]. En el software hay varias formas de enfocar un modelo. Las dos formas m´as comunes son la perspectiva orientada a objetos y la perspectiva estructural mostradas en la figura 1.1. La visi´on hasta hace algunos a˜ nos del desarrollo de software tomaba una perspectiva estructural. En este enfoque, el bloque principal de construcci´on de todo el software es el procedimiento o funci´on. Esta visi´on conduce a los desarrolladores a centrarse en cuestiones de control y de descomposici´on de algoritmos grandes en otros m´as peque˜ nos. No hay nada inherentemente malo en este punto de vista, salvo que tiende a producir sistemas fr´agiles. Cuando los requisitos cambian (¡lo har´an!) y el sistema crece (¡lo har´a!), los sistemas construidos con el enfoque algor´ıtmico se vuelven muy fr´agiles en su mantener.

4

Figura 1.1: Comparaci´on entre la descomposic´on orientada a objetos y la descomposici´on orientada a funciones. La visi´on actual del desarrollo de software toma una perspectiva orientada a objetos. En este enfoque, el principal bloque de construcci´on de todos los sistemas de software es el objeto o clase. De forma sucinta, un objeto es una cosa, generalmente extra´ıda del vocabulario del espacio del problema o del espacio de la soluci´on; una clase es una descripci´on de un conjunto de objetos similares. A lo largo de los u ´ltimos a˜ nos, la tecnolog´ıa orientada a objetos se ha desarrollado en diferentes segmentos de las ciencias de la computaci´on. La madurez de la ingenier´ıa de software ha conducido al desarrollo de m´etodos de an´alisis, dise˜ no y programaci´on orientados a objetos, todos los cuales tienen la misi´on de resolver problemas de la programaci´on a gran escala. El lenguaje unificado de modelado (UML, Unified Modeling Language) es un lenguaje gr´afico para documentar los artefactos de un sistema con gran cantidad de software. UML proporciona una forma est´andar de escribir los planos de un sistema,

5

con el fin de construir modelos para comprender mejor el sistema que se esta desarrollando. Es decir, construimos modelos de sistemas complejos porque no podemos comprender el sistema en su totalidad. Cabe mencionar que cualquier proyecto puede beneficiarse de un modelo conceptual como UML [4]. El modelado es importante, pero hay que recordar que el producto principal de un equipo de desarrollo es el software, no diagramas. Por supuesto, la raz´on por la que se crean modelos es para entregar de forma predecible, en el momento oportuno, el software adecuado que satisfaga los objetivos cambiantes de los usuarios y la empresa. Durante la evoluci´on del software se aplican cambios al c´odigo fuente, para agregar funcionalidad, reparar defectos y mejorar su calidad. En sistemas con documentaci´on pobre, el c´odigo es la u ´nica fuente de informaci´on fiable del sistema, sin embargo, el c´odigo no contiene toda la informaci´on necesaria. T´ıpicamente, el conocimiento acerca de la arquitectura, el dise˜ no y el dominio de la aplicaci´on s´olo existe en la mente del dise˜ nador, desafortunadamente con el tiempo las personas se van, los documentos decaen y la complejidad aumenta. Por consiguiente, existe un hueco en la comprensi´on de la informaci´on u ´til conocida y la informaci´on necesaria requerida para reforzar cambios en el software. El conocimiento de la arquitectura del software desde diferentes perspectivas de usuario es necesario para hacer cambios estructurales y tener la capacidad de reconstruir la arquitectura [5]. Dise˜ nar puede ser dif´ıcil, pero reconstruir y (re)documentar eficazmente el dise˜ no de un sistema de software existente es aun m´as dif´ıcil [6]. Como resultado, el proceso de ingenier´ıa inversa se ha enfocado en el entendimiento del c´odigo. El proceso de ingenier´ıa inversa identifica los componentes del sistema actual, descubre sus dependencias y genera abstracciones para dirigir la complejidad [7]. C4.5 es un sistema creado desde la perspectiva estructural y como se ha mencionado los sistemas creados desde este punto de vista tienden a ser fr´agiles. Por esta raz´on, nos interesa desarrollar un modelo orientado a objetos de C4.5 que permita mostrar las caracter´ısticas esenciales del sistema, con el fin de dar una comprensi´on mas clara de la estructura interna del sistema para prop´ositos de mantenimiento, ya

6

que no se cuenta con este modelo, este trabajo de tesis propone la extracci´on del modelo orientado a objetos a partir de la implementaci´on en C del c´odigo existente. Este proceso com´ unmente se le conoce como ingenier´ıa inversa, que es el proceso de transformar c´odigo en un modelo a trav´es de una correspondencia con un lenguaje de programaci´on espec´ıfico [4].

7

Cap´ıtulo 2 Marco Te´ orico A continuaci´on presentamos un panorama general de los principales conceptos que se utilizan en el desarrollo de esta tesis, para dar al lector una mejor comprensi´on y apreciaci´on del trabajo.

2.1.

Miner´ıa de datos

La miner´ıa de datos o descubrimiento de conocimiento en base de datos, busca proveer de m´etodos autom´aticos confiables, que puedan lidiar con la naturaleza creciente de la informaci´on y que tambi´en sean capaces de descubrir principios, mecanismos y causas que se encuentren impl´ıcitamente contenidas en los datos, de manera que podamos tener un mejor y m´as profundo conocimiento del fen´omeno bajo estudio. Para lograrlo, esta disciplina combina ideas de diversas ´areas, como bases de datos, estad´ıstica, aprendizaje autom´atico e inteligencia artificial, entre otras. Se denomina miner´ıa de datos al conjunto de t´ecnicas y herramientas aplicadas al proceso no trivial de extraer y presentar un conocimiento impl´ıcito, previamente desconocido, potencialmente u ´til y comprensible por el humano, a partir de grandes conjuntos de datos, con objeto de predecir de forma automatizada tendencias, comportamientos y describir modelos previamente desconocidos.

8

2.2.

´ Arboles de decisi´ on

El aprendizaje con ´arboles de decisi´on es uno de los m´etodos de inferencia inductiva m´as usados y practicados. El aprendizaje con ´arboles de decisi´on es un m´etodo para aproximar funciones objetivo de valores discretos, en el cual la funci´on objetivo es representada por un ´arbol de decisi´on. Los ´arboles inferidos tambi´en pueden ser rerepresentados por un conjunto de reglas If-Then-Else para mejorar la comprensi´on humana. Estos m´etodos de aprendizaje est´an entre los algortimos m´as populares de inferencia inductiva y han sido satisfactoriamente aplicados a una extensa gama de tareas de aprendizaje, desde casos de diagnostico m´edico, hasta la evaluaci´on de riesgos de cr´edito en una aplicaci´on de pr´estamo.

2.2.1.

Representaci´ on de ´ arboles de decisi´ on

Un ´arbol de decisi´on es inferido a partir de un conjunto de registros, donde cada registro tiene la misma estructura, es decir, consiste de un mismo n´ umero de pares atributo/valor. Cada atributo representa una caracter´ıstica y uno de estos atributos representa la categor´ıa del registro. En el ´arbol de decisi´on cada nodo corresponde a un atributo y cada arco o rama a un valor posible de aquel atributo. Una hoja del ´arbol especifica el valor (categor´ıa) esperado(a) para los registros descritos por la ruta seguida desde el nodo ra´ız hasta el nodo hoja. En el ´arbol de decisi´on cada nodo deber´a ser asociado a un atributo categ´orico, el cual contenga la mayor parte de informaci´on de entre los atributos aun no considerados en la ruta desde el nodo ra´ız. Un ´arbol de decisi´on es un ´arbol en el cual cada rama representa una selecci´on entre un n´ umero de alternativas, y cada nodo hoja representa una clasificaci´on o decisi´on. Los ´arboles de decisi´on clasifican ejemplos al ordenar estos en forma descendente en un ´arbol desde un nodo ra´ız a alg´ un nodo hoja, el cual proporciona la clasificaci´on del ejemplo. Cada nodo en el ´arbol especifica una prueba de alg´ un atributo del ejemplo, y cada rama descendiente del nodo corresponde a uno de los posibles valores para 9

Figura 2.1: Un ´arbol de decisi´on para la autorizaci´on de un pr´estamo. ese atributo. Un ejemplo es clasificado al realizar una serie de pruebas para cada atributo, iniciando en el nodo ra´ız del ´arbol, y siguiendo la rama del valor para el atributo especificado por este nodo, entonces se contin´ ua el proceso de prueba para el nodo que continua en la rama correspondiente al valor del atributo hasta alcanzar un nodo hoja. La figura 2.1 muestra un ´arbol de decisi´on para asistir a una instituci´on financiera en la realizaci´on de un pr´estamo a un persona. El ´arbol de decisi´on clasifica la realizaci´on del pr´estamo de acuerdo a los ingresos del aspirante, antecedentes penales, a˜ nos en su empleo y el pago de sus tarjetas de cr´edito. Por ejemplo para el caso (Ingreso del aspirante = $35000, a˜ nos en su empleo = 3, ¿paga sus tarjetas de cr´edito? = si)

10

Se realizan las pruebas en los nodos correspondientes comenzando en el nodo de ¿Ingresos del aspirante?, se sigue la rama de en medio y as´ı sucesivamente, hasta alcanzar la hoja “Prestar”, que en este caso es la categor´ıa o resultado del ´arbol. En general los ´arboles de decisi´on representan una disyunci´on de uniones de restricciones sobre los valores de los atributos de ejemplo. Cada ruta de la ra´ız del ´arbol a una hoja corresponde a una uni´on de atributos de prueba, y el ´arbol mismo a una disyunci´on de estas uniones.

2.2.2.

Problemas apropiados para el aprendizaje con ´ arboles de decisi´ on

A pesar de que una variedad de m´etodos de aprendizaje con ´arboles de decisi´on han sido desarrollados con algunas capacidades y requerimientos diferentes, el aprendizaje con ´arboles de decisi´on est´a generalmente mejor preparado para problemas con las siguientes caracter´ısticas [2]: Casos que son representados por pares atributo-valor. Los ejemplos son descritos por un conjunto fijo de atributos (p.e. Temperatura) y sus valores (p.e. caliente). La situaci´on m´as f´acil para el aprendizaje con ´arboles de decisi´on es cuando cada atributo toma un n´ umero peque˜ no de valores posibles. La funci´on objetivo tiene valores de salida discretos. Los m´etodos de ´arboles de decisi´on f´acilmente se extienden a funciones de aprendizaje con m´as de dos valores de salida. Una extensi´on m´as sustancial permite aprender funciones objetivo con valores de salida reales. Como notamos arriba, los ´arboles de decisi´on naturalmente representan expresiones disyuntivas. Los datos de entrenamiento pueden contener errores. Los m´etodos de aprendizaje con ´arboles de decisi´on son robustos a errores, tanto en errores de los

11

ejemplos de clasificaci´on, como en los valores de los atributos que describen estos ejemplos. Los datos de entrenamiento pueden contener valores de atributo omitidos. Los m´etodos de ´arboles de decisi´on pueden ser usados a´ un cuando algunos ejemplos de entrenamiento tienen valores desconocidos. Muchos problemas pr´acticos han sido encontrados para ajustar estas caracter´ısticas. El aprendizaje con ´arboles de decisi´on ha sido aplicado por consiguiente a problemas tales como aprendizaje para clasificaci´on m´edica de pacientes por sus s´ıntomas, en mal funcionamientos de equipo por sus causas, en aplicaciones de pr´estamo por sus posibilidades predefinidas de pago. Tales problemas en los cuales la tarea es la clasificaci´on de ejemplos dentro de una categor´ıa posible, de valores discretos, son referidos a menudo como problemas de clasificaci´on.

2.2.3.

C4.5

Este conjunto de programas genera un clasificador en la forma de un ´arbol de decisi´on, estructurado como sigue: Una hoja, indica una clase, o Un nodo de decisi´on que especifica una prueba a llevarse a cabo sobre un valor de atributo simple, con una rama y sub´arbol para cada salida posible de la prueba. El sistema C4.5 consiste de cuatro programas principales. 1. El generador de ´arbol de decisi´on (‘C4.5’) 2. El generador de reglas de producci´on (‘C4.5rules’) 3. El interprete de ´arboles de decisi´on (‘consult’), y

12

4. El interprete de reglas de producci´on (‘consultr’) A continuaci´on se describe un ejemplo de ejecuci´on aplicado al sistema, para mostrar al lector la forma de funcionamiento de C4.5. Ejemplo: Negociaci´ on del pago de mano de obra La Universidad de California en Irvine guarda una librer´ıa accesible p´ ublicamente de bases de datos que han sido usadas en experimentos aprendizaje-maquina.1 Una de estas, proporcionada por Stan Matwin de la Universidad de Ottawa, involucra el resultado de la negociaci´on de contratos Canadienses en 1987-1988. La informaci´on proporcionada contiene datos utilizados para describir un contrato aceptado o no. A partir de un numero de casos, el sistema puede construir un modelo de clasificaci´on que relacione la aceptabilidad de un contrato con los valores de las propiedades de los registros. Todas las tareas a ser procesadas por el sistema C4.5 necesitan un nombre breve; en este caso ha sido llamado labor-neg. El primer paso es definir las clases y los atributos en un archivo llamado labor-neg.names como se muestra en la figura 2.2. El siguiente paso es proporcionar informaci´on de los casos individuales, esto involucra separar los valores de los atributos por una coma y seguidos por la clase del caso. Tres de los casos para este ejempo son: 2,2.5,3.0,?,?,40,none,?,?,?,11,below average,?,?,?,?,bad 2,4.5,4.0,?,?,40,?,?,4,?,10,generous,?,half,?,full,good 1,6.0,?,?,?,38,?,8,3,?,9,generous,?,?,?,?,good Hay 57 casos como estos en la base de datos. En este ejemplo 40 de los casos han sido seleccionados aleatoriamente para formar un conjunto de entrenamiento desde los cuales el clasificador ser´a construido, 17 de los casos son reservados para un conjunto de prueba. Los casos de entrenamiento son colocados en el archivo labor-neg.data, y los de prueba en labor-neg.test. El comando de UNIX 1

Estas bases de datos pueden ser obtenidas en ftp://ftp.ics.uci.edu/pub/machine-learningdatabases

13

Figura 2.2: Definici´on de clases y atributos en el ejemplo labor-neg C4.5 -f labor-neg -u invoca C4.5 con la opci´on -f dando el nombre de la tarea o archivo y la opci´on -u indicando que el clasificador ser´a probado con casos inadvertidos. La salida del generador del ´arbol de decisi´on para este ejemplo aparece en la figura 2.3. Tal estructura no puede ser observada como un ´arbol, en consecuencia, mostramos una forma gr´afica m´as usual en la figura 2.4.

2.3.

El lenguaje unificado de modelado

El lenguaje unificado de modelado (UML) es un lenguaje gr´afico para visualizar, especificar, construir y documentar los artefactos de un sistema con gran cantidad de software. UML proporciona una forma est´andar de escribir los planos de un sistema, cubriendo tanto las cosas conceptuales, tales como procesos del negocio y funciones del sistema, como las cosas concretas, tales como las clases escritas en un lenguaje de programaci´on espec´ıfico, esquemas de bases de datos y componentes de software

15

Figura 2.3: Salida de C4.5 sobre datos labor-neg

Figura 2.4: Forma grafica del ´arbol de decisi´on para el ejemplo labor-neg reutilizables. UML es un lenguaje para: Visualizar Especificar Construir Documentar A trav´es del modelado, conseguimos cuatro objetivos [4]: 1. Los modelos nos ayudan a visualizar c´omo se desea que sea el sistema. 2. Los modelos nos permiten especificar la estructura o el comportamiento de un sistema.

16

3. Los modelos nos proporcionan plantillas que nos gu´ıan en la construcci´on de un sistema. 4. Los modelos documentan las decisiones que hemos adoptado. Cualquier proyecto puede beneficiarse del modelado. Incluso en el dominio de software desechable donde a veces es m´as efectivo deshacerse del software inadecuado. La productividad ofrecida por los lenguajes de programaci´on visuales ayuda al equipo de desarrollo a visualizar mejor el plano de su sistema y a permitirles desarrollar m´as r´apidamente al ayudarles a construir el producto apropiado. Todos los sistemas interesantes y u ´tiles tienen una tendencia natural a hacerse m´as complejos con el paso del tiempo. As´ı que, aunque al inicio se pueda pensar que no es necesario modelar, cuando el sistema evolucione se lamentar´a esa decisi´on y entonces ser´a demasiado tarde.

2.4.

Ingenier´ıa directa e inversa

La ingenier´ıa directa es el proceso de transformar un modelo en c´odigo a trav´es de una correspondencia con un lenguaje de implementaci´on. La ingenier´ıa directa produce una p´erdida de informaci´on, porque los modelos escritos en UML son sem´anticamente m´as ricos que cualquier lenguaje de programaci´on orientado a objetos actual. De hecho, esta es una de las razones principales por las que se necesitan modelos adem´as del c´odigo. Las caracter´ısticas estructurales, tales como las colaboraciones, y las caracter´ısticas de comportamiento, tales como las interacciones, pueden visualizarse claramente en UML, pero no tan claramente a partir de simple c´odigo fuente. La ingenier´ıa inversa es el proceso de transformar c´odigo en un modelo a trav´es de una correspondencia con un lenguaje de programaci´on espec´ıfico. La ingenier´ıa inversa produce un aluvi´on de informaci´on, alguna de la cual est´a a un nivel de detalle m´as bajo del que se necesita para construir modelos u ´tiles. Al mismo tiempo, la ingenier´ıa inversa es incompleta. Hay una p´erdida de informaci´on cuando se hace ingenier´ıa directa de modelos a c´odigo, as´ı que no se puede recrear completamente 17

un modelo a partir de c´odigo a menos que las herramientas incluyan informaci´on en los comentarios del c´odigo fuente que vaya m´as all´a de la sem´antica del lenguaje de implementaci´on. La combinaci´on de estas dos v´ıas de generaci´on de c´odigo y de ingenier´ıa inversa produce una ingenier´ıa de “ida y vuelta”, entendiendo por esto la posibilidad de trabajar en una vista grafica o textual, mientras las herramientas mantienen la consistencia entre las dos vistas.

2.5.

Diagramas de clases

Los diagramas de clases son los m´as utilizados en el modelado de sistemas orientados a objetos. Un diagrama de clases muestra un conjunto de clases, interfaces y colaboraciones, as´ı como sus relaciones. Los diagramas de clases se utilizan para modelar la vista de dise˜ no est´atica de un sistema. Principalmente, esto incluye modelar el vocabulario del sistema, modelar las colaboraciones o modelar esquemas. Los diagramas de clases son importantes no s´olo para visualizar, especificar y documentar modelos estructurales, sino tambi´en para construir sistemas ejecutables, aplicando ingenier´ıa directa e inversa. Para indicar de qu´e manera los objetos se conectan entre s´ı a trav´es de atributos, una l´ınea con una flecha en la punta indicar´a un atributo. El diagrama de clases del dise˜ no describe gr´aficamente las especificaciones de las clases de software y de las interfaces (las de Java, por ejemplo) en una aplicaci´on. Normalmente contiene la siguiente informaci´on: Clases, asociaciones y atributos Interfaces, con sus operaciones y constantes M´etodos Informaci´on sobre los tipos de los atributos

18

Navegabilidad Dependencias

2.6.

Diagramas de interacci´ on

Los diagramas de secuencia y los diagramas de colaboraci´on (ambos llamados diagramas de interacci´on) son dos de los cinco tipos de diagramas de UML que se utilizan para modelar los aspectos din´amicos de los sistemas. Un diagrama de interacci´on muestra una interacci´on, que consiste en un conjunto de objetos y sus relaciones, incluyendo los mensajes que se pueden enviar entre ellos. Los diagramas de interacci´on no son solo importantes para modelar los aspectos din´amicos de un sistema, sino tambi´en para construir sistemas ejecutables por medio de ingenier´ıa directa e inversa. Un diagrama de interacci´on muestra una interacci´on, que consta de un conjunto de objetos y sus relaciones, incluyendo los mensajes que se pueden enviar entre ellos. Un diagrama de secuencia es un diagrama de interacci´on que destaca la ordenaci´on temporal de los mensajes. Gr´aficamente, un diagrama de secuencia es una tabla que representa objetos, dispuestos a lo largo del eje X, y mensajes, ordenados seg´ un se suceden en el tiempo, a lo largo del eje Y. Un diagrama de colaboraci´ on es un diagrama de interacci´on que destaca la organizaci´on estructural de los objetos que env´ıan y reciben mensajes. Gr´aficamente, un diagrama de colaboraci´on es una colecci´on de nodos y arcos [4].

2.6.1.

Diagramas de colaboraci´ on

El dise˜ no orientado a objetos tiene por objeto definir las especificaciones l´ogicas del software que cumplan con los requisitos funcionales, bas´andose en la descomposici´on por clases de objetos. Un paso esencial de esta fase es la asignaci´on de responsabilidades entre los objetos y mostrar c´omo interact´ uan a trav´es de mensajes, expresados en

19

´ diagramas de colaboraci´on. Estos presentan el flujo de mensajes entre las instancias y la invocaci´on de m´etodos. Los diagramas de colaboraci´on explican gr´aficamente c´omo los objetos interact´ uan a trav´es de mensajes para realizar las tareas y las interacciones existentes entre las instancias (y las clases) del modelo de ´estas [4].

2.7.

Diagramas de estados

Los diagramas de estados (statechart) son uno de los cinco tipos de diagramas de UML que se utilizan para el modelado de los aspectos din´amicos de un sistema. Definici´ on 2.1 Un diagrama de estados muestra un flujo de control entre estados. Principalmente, muestra el comportamiento que especifica la secuencia de estados por las que pasa un objeto a lo largo de su vida en respuesta a eventos, junto con respuestas a esos eventos. on o situaci´on en la vida de un objeto Definici´ on 2.2 Un estado es una condici´ durante la cual satisface alguna condici´ on, realiza alguna actividad o espera alg´ un evento. Definici´ on 2.3 Un evento es la especificaci´ on de un acontecimiento significativo que ocupa un lugar en el tiempo y en el espacio. En el contexto de los diagramas de estados, un evento es la aparici´ on de un estimulo que puede activar una transici´ on de estado. Definici´ on 2.4 Una transici´on es una relaci´ on entre dos estados que indica que un objeto que est´a en el primer estado realizar´ a ciertas acciones y entrar´ a en el segundo estado cuando ocurra un evento especificado y se satisfagan algunas condiciones espec´ıficas. Las definiciones anteriores son descritas en [4] y se utilizan para la elaboraci´on de un diagrama de estados. 20

Cap´ıtulo 3 Estado del arte Diversos investigadores se han dado la tarea de explicar la importancia de contar con modelos que forman parte de la documentaci´on de los sistemas de software, debido a que la documentaci´on de un sistema, tradicionalmente juega un papel clave como ayuda en el entendimiento de programas [6]. Sin embargo, en muchas ocasiones no se cuenta con tal documentaci´on, o ´esta se encuentra dispersa en diferentes medios, aun cuando la documentaci´on es indispensable para el entendimiento de un sistema. Esto es crucial en la industria del software, para tratar efectivamente con el problema de la evoluci´on y entendimiento de sistemas de software de legado. La evoluci´on de sistemas de legado requiere de un conocimiento sustancial de conocimiento acerca del sistema. A principios de los noventa la necesidad de reingenier´ıa de sistemas de legado ha sido aguda, pero recientemente la demanda se ha incrementado significativamente [5]. En sistemas de legado de software, uno necesita la documentaci´on que describe los aspectos de alto nivel sobre la arquitectura de un sistema de software desde m´ ultiples perspectivas. Una forma de producir tal documentaci´on estructural para sistemas de software existente, es usar tecnolog´ıas de ingenier´ıa inversa. Dentro de la ingenier´ıa inversa, un modelado de objetos permite a dise˜ nadores y programadores de software, describir concisamente la esencia del dise˜ no de un sistema. Extraer autom´aticamente modelos de objetos desde c´odigo puede ser u ´til por muchas 21

razones: resume la arquitectura del sistema, puede ayudar ha resolver anomal´ıas en el dise˜ no, o a descubrir errores. Un modelado de objetos proporciona a dise˜ nadores de programas orientados a objetos una forma de documentar concisamente la esencia del dise˜ no de un sistema [8]. Un modelo de objetos es una representaci´on del estado abstracto de un programa. Este toma la forma de una grafica cuyos nodos representan un conjunto de objetos, y cuyos bordes representan relaciones o asociaciones entre objetos. Un modelo de objetos es una vista de la arquitectura de un sistema, mostrando sus componentes esenciales y c´omo ellos interact´ uan. En la fase de mantenimiento, un modelo de objetos es invaluable [9]. El prop´osito de un modelo es conservar caracter´ısticas seleccionadas de artefactos del mundo real. Los modelos son usados en la mayor´ıa de las disciplinas de ingenier´ıa. Un modelo puede ser una teor´ıa matem´atica, una entidad f´ısica, o la imagen de una gu´ıa mental en el cerebro de un dise˜ nador. El prop´osito de un dise˜ no es facilitar el an´alisis, explicita o impl´ıcitamente. El uso efectivo de abstracciones es la clave de la construcci´on satisfactoria de modelos. La construcci´on de un modelo abstracto, a su vez, es la clave del ´exito del an´alisis. Cuando se construye un modelo, un experto lo puede verificar t´ıpicamente al consultar con el dise˜ nador del sistema, que es fuente de estudio, o por una lectura extensa de la documentaci´on del sistema y en algunos casos del c´odigo fuente de la aplicaci´on, para llegar a un entendimiento del dise˜ no proyectado. Este proceso por lo menos puede tomar d´ıas, a menudo semanas y algunas veces meses [10]. Realizar el dise˜ no de un modelo suele ser dif´ıcil, no obstante reconocer abstracciones en sistemas del mundo real es tan dif´ıcil como dise˜ nar abstracciones adecuadas para un nuevo sistema. Esto es especialmente verdadero para legado de sistemas de software escritos hace 10-25 a˜ nos, los cuales est´an a menudo en condiciones de documentaci´on pobre. En la evoluci´on de sistemas de legado se requiere un conocimiento sustancial agrupado.

22

Los trabajos relacionados en el ´area de obtenci´on de modelos son variados, sin embargo, la mayor´ıa de estos tienen un enfoque similar sobre el objetivo de la obtenci´on de modelos a partir de c´odigo fuente. La mayor´ıa de trabajos relacionados manejan la obtenci´on de modelos como un proceso de ingenier´ıa inversa para el descubrimiento y la obtenci´on de artefactos del mundo real, para ser plasmados dichos artefactos en un modelo que explique desde diferentes perspectivas la arquitectura de un sistema de software.

3.1.

Entendiendo la estructura de sistemas

Es ampliamente aceptado que por encima del 50 % de trabajos en la evoluci´on de software, est´an dedicados al entendimiento de programas. La documentaci´on ha jugado tradicionalmente un papel importante en esta consideraci´on. La mayor´ıa de la documentaci´on de software describe el programa a nivel de algoritmos y estructuras de datos. El entendimiento de programas es una problem´atica especialmente para ingenieros de software, que son administradores t´ecnicos, responsables del mantenimiento de tal sistema. La documentaci´on que existe para estos sistemas usualmente describe partes aisladas de ´este; la cual no describe la arquitectura global del sistema. Por otra parte, la documentaci´on est´a a menudo dispersa en todo el sistema y sobre diferentes medios, como consecuencia, esta documentaci´on es abandonada para fines de mantenimiento [6].

3.2.

Usando ingenier´ıa inversa para descubrir estructuras de software

Estructuras de software es la colecci´on de artefactos usados por ingenieros cuando forman modelos mentales de sus sistemas. Estos artefactos incluyen componentes de software tales como procedimientos, m´odulos e interfaces; dependencias entre los 23

componentes tales como cliente-proveedor, herencia y flujo de control; y atributos tales como el tipo de componentes, tama˜ no de interfaces y longitud de interconexi´on. La estructura de un sistema es la organizaci´on y la interacci´on de estos artefactos. Una t´ecnica de apoyo computacional de la reconstrucci´on de modelos estructurales es ingenier´ıa inversa. El proceso de ingenier´ıa inversa [6]: identifica los componentes del sistema actual, descubre sus dependencias y genera abstracciones para manejar complejidad. Este entendimiento puede entonces mejorar el desarrollo subsecuente, y produce una facilidad de mantenimiento y re-ingenier´ıa. Chikofsky y Cross introducen una taxonom´ıa de ingenier´ıa inversa y descubrimiento de dise˜ nos [5]. Ellos definen ingenier´ıa inversa como “analizar un sistema objetivo para identificar sus componentes y dependencias actuales, y extraer y crear abstracciones de sistemas junto con informaci´on de su dise˜ no”. En la investigaci´on y pr´actica actual, el enfoque de ingenier´ıa inversa y directa es a nivel de c´odigo. Los procesos de ingenier´ıa directa engranan hacia producir c´odigo de calidad. Durante la evoluci´on del software, se realizan cambios al c´odigo fuente, para agregar funcionalidad, corregir defectos y mejorar su calidad. En sistemas con documentaci´on pobre es solo fiable la fuente de informaci´on del sistema. Como resultado, el proceso de ingenier´ıa inversa se ha enfocado en el entendimiento del c´odigo. Sin embargo, el c´odigo no contiene toda la informaci´on que es necesaria. T´ıpicamente, el conocimiento acerca de la arquitectura y dise˜ no se encuentran fuera del alcance del c´odigo [5]. El proceso de ingenier´ıa inversa identifica los componentes del sistema actual, descubre sus dependencias y genera abstracciones para dirigir la complejidad [7]. En sistemas con documentaci´on pobre, el c´odigo es la u ´nica fuente de informaci´on sobre el sistema, como resultado el proceso de ingenier´ıa inversa se enfoca en entender 24

el c´odigo. Sin embargo, el c´odigo no contiene toda la informaci´on que necesitamos, a menos que ´esta se encuentre codificada en el c´odigo. Por consiguiente, existe un hueco en la comprensi´on de la informaci´on u ´til conocida y la informaci´on requerida necesaria para reforzar cambios en el software [9].

3.3.

Experiencias del mundo real

Una aproximaci´on desarrollada por el proyecto Rigi –un entorno flexible para el entendimiento arquitectural– en la Universidad de Victoria [6], se ha aplicado satisfactoriamente a diversos sistemas de software del mundo real. Estos incluyen un sistema de registros f´ısicos paciente-m´edico (escrito en COBOL), un programa de control para un acelerador de part´ıculas (escrito en C), y numerosas utiler´ıas de UNIX. Esta experiencia ha demostrado que se pueden producir vistas o modelos que contienen informaci´on desde diferentes perspectivas de usuario. Los administradores t´ecnicos se han beneficiado de la documentaci´on producida por el sistema Rigi en varias formas. Primero, fue posible ver la estructura de software l´ogica previamente retenida s´olo en la mente del dise˜ nador de los sistemas. Segundo, las vistas resaltan ´areas cr´ıticas de la estructura del software que necesitan m´as atenci´on, tales como componentes centrales que tienen un gran n´ umero de dependencias casuales. Tercero, las vistas proporcionan un objetivo b´asico para discutir y mantener software, ya que ellos est´an basados en el c´odigo fuente actual. Cuarto, las vistas verifican que la estructura del software de sus sistemas fue, al menos, entendible para una experiencia de an´alisis desde afuera. Esta aproximaci´on se llego a validar efectivamente cuando tomaron el desafio de re-documentar SQL/LS, un sistema manejador de bases de datos, que contiene 25

alrededor de 1,300 unidades de compilaci´on, bruscamente esta dividido en 3 sistemas grandes (y varios peque˜ nos m´as). Los desarrolladores son forzados a especializarse en componentes particulares, aun cuando varios componentes interact´ uan. SQL/DS es un t´ıpico sistema de software de legado.

3.3.1.

Fases de redocumentaci´ on estructural

En Rigi, la primera fase de redocumentaci´on estructural es autom´atica, esta involucra un an´alisis sint´actico en el c´odigo fuente del software de legado, para almacenar los artefactos extra´ıdos en un dep´osito. Esto produce un flujo gr´afico del software. Los administradores t´ecnicos encargados del mantenimiento de software, pueden usar este flujo gr´afico de componentes para representar las dependencias estructurales de inter´es, tales como funciones de llamada y datos de acceso. Para manejar la complejidad, la segunda fase involucra patrones humanos para reconocer habilidades y caracter´ısticas de subsistemas independientes del lenguaje, compuesto de t´ecnicas para generar m´ ultiples capas jer´arquicas para niveles de abstracci´on m´as altos. Por ejemplo, el analista puede agrupar funciones dentro de subsistemas de acuerdo a reglas de negocios o al aceptar principios de software modularmente, proporcionando las m´ ultiples perspectivas alternativas necesarias para mantener el software. Los usuarios pueden especificar cuales artefactos extraer, en varios niveles de detalle. Por ejemplo, una opci´on selecciona si el an´alisis sint´actico deber´ıa extraer llamadas a rutinas del sistema. Para entender programas, es importante construir abstracciones que enfaticen temas importantes y suprima detalles irrelevantes; decidir que incluir y que ignorar es un arte.

26

3.4.

De lo procedural al paradigma orientado a objetos

El ´exito de sistemas de software procedurales llama a su continuo uso y mantenimiento. Como Wilde et al. apuntan: “Cualquier sistema de software exitoso en el futuro entra en una prolongada y costosa fase de mantenimiento, no como consecuencia de fallas, sino de ´exito. Si un sistema es exitoso, los usuarios demandaran que este sea fortalecido y actualizado” [11]. Al dise˜ nar y desarrollar programas orientados a objetos desde una perspectiva procedural, uno puede experimentar lo que es conocido como “cambio de paradigma”. Este cambio requiere que, el dise˜ nador no piense en t´erminos de los procedimientos que un sistema de software debe ejecutar, si no m´as bien, en t´erminos de las entidades u objetos que participan en el sistema. El derivar una estructura de clases desde una perspectiva estructural de un programa procedural, toma la aproximaci´on de no dise˜ nar estructuras de clases desde el principio, sino m´as bien, derivar estas desde la estructura actual del sistema. Para facilitar la transici´on de programas procedurales dentro de un estilo orientado a objetos, Ignacio Silva [11] propone derivar su estructura de clases al considerar sus estructuras de datos como objetos de alto nivel y transformando procedimientos en m´etodos, que ser´an agregados a los objetos para definir su comportamiento. Jacobson y Lindstr¨oum [12] proponen reingenier´ıa a sistemas antiguos dentro de una arquitectura orientada a objetos en dos pasos fundamentales. 1. Ingenier´ıa inversa. Modelado de los sistemas ya desarrollados mediante una derivaci´on de clases, a partir de las estructuras de datos actuales del sistema. 2. Ingenier´ıa directa. Mejoramiento del sistema usando completamente m´etodos orientados a objetos. Por otra parte, en [13] se menciona que una de las formas m´as comunes de evoluci´on de un sistema, involucra la extensi´on de un esquema existente, por la adici´on 27

de nuevas clases de objetos o la adici´on de atributos a los objetos originales. Algunas veces, la estructura de clases es reorganizada incluso cuando el conjunto de objetos no se esta cambiando. En este caso la reorganizaci´on puede presentar una optimizaci´on del sistema o s´olo un cambio en la perspectiva de usuario. En el otro extremo, una reorganizaci´on de clases no s´olo puede reflejar extensi´on y reclasificaci´on de objetos existentes, sino tambi´en cambios estructurales en los objetos originales.

3.5.

Trabajos Conexos

Johannes Martin [14] presenta en su tesis de doctorado un estudio y evaluaci´on de algunas aproximaciones actuales, para la migraci´on de c´odigo fuente a Java. Principalmente, se enfoca en el lenguaje de programaci´on C y C++ como el lenguaje fuente. Utilizando sus experiencias adquiridas en el estudio realizado, establece un n´ umero de metas para una aproximaci´on de migraci´on mejorada y para desarrollar esta aproximaci´on en el ambiente Ephedra. Proporciona diversas estrategias de transformaci´on, considerando una conversi´on de c´odigo fuente C a c´odigo fuente Java integrando las estrategias m´as apropiadas. Para cada constructor del lenguaje fuente, se plantea una estrategia de conversi´on a un constructor simulado o nativo del lenguaje objetivo (Java). Presentando un catalogo de conversi´on de los principales constructores m´as comunes usados en el lenguaje C. Considera principalmente tres fases de conversi´on: 1. Normalizaci´ on. Es esta fase se realiza una conversi´on de c´odigo C en el estilo K&R (Kernighan and Ritchie) al est´andar ANSI C. 2. Traducci´ on. Durante esta fase se realiza la traducci´on de c´odigo desde C a Java, por lo tanto, en esta fase se utiliza la aproximaci´on planteada para cada constructor del lenguaje.

28

3. Optimizaci´ on. Por u ´ltimo, esta fase realiza un mejoramiento del c´odigo fuente aplicando estrategias de reingenier´ıa. La meta de la aproximaci´on de Johannes Martin [14] es proporcionar una mejor soluci´on al problema de integraci´on de c´odigo fuente C dentro de programas Java. Esto proporciona una aproximaci´on estructurada para migrar c´odigo fuente C a la M´aquina Virtual de Java.

29

Cap´ıtulo 4 Definici´ on del problema Como se describi´o en el Cap´ıtulo 1, est´e o no previsto, los sistemas tienden a evolucionar en el tiempo, ya sea por agregar funcionalidad al sistema, reparar defectos o simplemente por dar mantenimiento y mejorar la calidad del sistema. Estamos seguros de que C4.5 es un sistema que no esta exento de cambio, sin embargo, no se cuenta con un modelo conceptual que permita observar el sistema desde diferentes perspectivas que capturen las caracter´ısticas esenciales, para la comprensi´on y mantenimiento del sistema. Por esta raz´on, nos interesa obtener el modelo orientado a objetos que muestre el comportamiento de C4.5 a nivel conceptual, enfrent´andonos a ciertas dificultades que se describen a continuaci´on. 1. Debido a que existen diferencias notables entre ambas perspectivas de programaci´on (la orientada a objetos y la estructural1 ) consideramos que no es posible obtener un modelado directo, limpio y r´apido, y que es necesaria una estructuraci´on del sistema que va desde la perspectiva estructural a la perspectiva orientada a objetos. 2. No se cuenta con informaci´on del sistema que describa las caracter´ısticas generales de su comportamiento, teniendo que enfocarnos u ´nicamente en el c´odigo de C4.5 para la obtenci´on del modelo orientado a objetos. 1

En este caso particular, C4.5 est´a desarrollado en el lenguaje C.

30

4.1.

Objetivo General

Extraer el modelo conceptual orientado a objetos a partir del c´odigo en C de C4.5 que permita documentar de forma concisa la arquitectura desde la vista de dise˜ no de C4.5.

4.1.1.

Objetivos espec´ıficos

Separar apropiadamente el conjunto de programas C4.5 en un modelo orientado a objetos, y obtener los siguientes diagramas: Diagramas de clases, Diagramas de colaboraci´on y Diagramas de estados.

4.2.

Hip´ otesis

Es posible documentar un sistema a partir de su c´odigo fuente, mediante la obtenci´on de un modelo conceptual en el paradigma orientado a objetos. Desde el principio, este modelo puede ser derivado a partir de la estructura actual del sistema haciendo uso de metodolog´ıas establecidas.

4.3.

Justificaci´ on

El modelo del conjunto de programas C4.5 en el paradigma orientado a objetos nos permitir´a obtener un software reutilizable, legible y principalmente mantenible dentro del ciclo de vida de ´este. Las caracter´ısticas estructurales, tales como las colaboraciones, y las caracter´ısticas de comportamiento, como son las interacciones, pueden visualizarse claramente en UML, pero no tan claramente a partir del c´odigo fuente simple. 31

Debido a que los modelos escritos en UML son sem´anticamente m´as ricos que cualquier lenguaje de programaci´on orientado a objetos actual, se necesitan modelos adem´as de c´odigo. Pues hay una p´erdida de informaci´on cuando se hace ingenier´ıa directa de modelos a c´odigo.

32

Cap´ıtulo 5 Desarrollo Hasta ahora hemos descrito la problem´atica que implica el no tener un modelo conceptual de C4.5 y el porque debemos de considerar tener este modelo. A partir de aqu´ı, se describe la manera en que se obtuvo el modelo conceptual a partir del c´odigo de C4.5, no sin antes mencionar porque se decidi´o plantear en primer lugar un modelo y despu´es planteamos como un trabajo a futuro la migraci´on de este modelo a un lenguaje de programaci´on orientado a objetos, como puede ser Java.

5.1.

Planteamiento de migraci´ on

Cuando iniciamos este trabajo, nuestro principal objetivo era migrar el conjunto de programas C4.5, al paradigma orientado a objetos, en el lenguaje de programaci´on Java. Sin embargo, nos encontramos con la tarea de decidir que camino de los que a continuaci´on describiremos, deber´ıamos de seguir para lograr nuestro objetivo, pues no es tan f´acil migrar de un lenguaje de programaci´on a otro, debido a las diferencias existentes en ambos lenguajes. Estas estrategias de migraci´on que planteamos son las mostradas en la figura 5.1. 1. En primer lugar consideramos que a partir del c´odigo de C4.5 en el lenguaje de programaci´on C, realiz´aramos una traducci´on autom´atica del c´odigo a Java, por 33

Figura 5.1: Estrategias de migraci´on al paradigma orientado a objetos. medio del uso de un traductor, despu´es de obtener el c´odigo en Java, realizar un mejoramiento de este c´odigo, y por ultimo la obtenci´on del modelo conceptual orientado a objetos. Sin embargo, detectamos que ninguno de los traductores desarrollados hasta el momento para dichos fines nos era de gran utilidad. 2. En segundo lugar, nos dimos a la tarea de investigar la manera en que funcionan dichos traductores y determinamos realizar un planteamiento de traducci´on para lograr una transcripci´on del c´odigo a Java, a continuaci´on de la obtenci´on del c´odigo obtendr´ıamos un modelo casi inmediato posiblemente utilizando una herramienta CASE. 3. Por u ´ltimo, nuestra decisi´on tomada y la mas conveniente a nuestro punto de vista es desarrollar en primer lugar el modelo orientado a objetos del c´odigo de C4.5 que muestre la relaci´on y colaboraci´on entre objetos, para permitir al lector una f´acil y clara comprensi´on del sistema, para que de esta manera la transcripci´on o codificaci´on del c´odigo a un lenguaje de programaci´on orientado 34

a objetos sea mas clara y precisa. Decidimos seguir la tercera aproximaci´on, debido a que es la forma en que lo exponen Jacobson y Lindstr¨oum [12], ya que como se mencion´o en la secci´on 3.4, primero derivan un modelo aplicando ingenier´ıa inversa, y despu´es, se realiza un mejoramiento del sistema usando completamente m´etodos orientados a objetos. Cabe mencionar, que en la aproximaci´on desarrollada en el proyecto Rigi de la Universidad de Victoria [6], tambi´en se realiza en primer lugar la obtenci´on de un modelo para la comprensi´on de un sistema en estudio.

5.2.

Dise˜ no del modelo orientado a objetos

Cuando se modela un sistema, su modelo puede ser realizado desde diferentes vistas, de hecho se construye el sistema simult´aneamente desde m´ ultiples dimensiones. La vista de modelado debe ser elegida apropiadamente de forma que exprese mejor la arquitectura del sistema, por medio de los artefactos que capturen los detalles esenciales de funcionamiento, en mayor´ıa de las veces, estos artefactos consistir´an de diagramas UML. Dichos diagramas pasaran a ser parte primordial de la documentaci´on del sistema. Algunas vistas de modelado mostradas en [4] son: Vista de casos de uso. • Diagramas de casos de uso. • Diagramas de actividades (para modelado del comportamiento). Vista de dise˜ no. • Diagramas de clases (para modelado estructural). • Diagramas de interacci´on (para modelado del comportamiento). • Diagramas de estados (para modelado del comportamiento). Vista de procesos. 35

• Diagramas de clases (para modelado estructural). • Diagramas de interacci´on (para modelado del comportamiento). Vista de implementaci´on. • Diagramas de componentes. Vista de despliegue. • Diagramas de despliegue. El modelado del conjunto de programas C4.5 hemos decidido realizarlo desde la vista de dise˜ no, cuyos artefactos o diagramas por los que est´a compuesta muestran las caracter´ısticas esenciales del modelo estructural y de comportamiento del sistema. Dichos diagramas fueron descritos en el Cap´ıtulo 2.

5.3.

Proceso de dise˜ no de diagramas de clases

El proceso de desarrollo para la construcci´on de los diagramas de clases se realizo mediante varias fases que son descritas a continuaci´on: 1. Identificaci´on de los 4 programas principales (c4.5, c4.5rules, consult y consultr) con su respectiva colaboraci´on con los dem´as programas, 2. Identificaci´on de posibles objetos, as´ı como tambi´en sus variables y m´etodos, 3. Identificaci´on de la colaboraci´on entre objetos y 4. Acoplamiento de variables y m´etodos en el paradigma orientado a objetos.

5.3.1.

Identificaci´ on de programas principales

Como se mencion´o en el Cap´ıtulo 2, C4.5 consiste de 4 programas principales, dichos programas colaboran con los dem´as para realizar una tarea espec´ıfica a petici´on 36

Figura 5.2: Diagrama de secuencia para el sistema C4.5. del usuario, en particular, las tareas que son ejecutadas por cada programa principal son: la generaci´on de ´arboles de decisi´on, la generaci´on de reglas de producci´on, la interpretaci´on o prueba de ´arboles de decisi´on y la interpretaci´on o prueba de reglas de producci´on. La forma en que fluyen los eventos que pasan del usuario al sistema los podemos observar en el diagrama de secuencia de la figura 5.2. En general, C4.5 consta de los programas listados en la figura 5.3. A partir de saber que el sistema consiste de 4 programas principales, nos enfocamos en la identificaci´on de la colaboraci´on de cada uno de estos con los dem´as programas, dicha identificaci´on se logro a partir del archivo makefile en el que se describen sus relaciones con los dem´as archivos o programas. Para cada uno de los 4 programas principales mostramos su relaci´on con los dem´as programas en la figura 5.4. 37

Figura 5.3: Lista del conjunto de programas de C4.5.

Figura 5.4: Relaci´on de los 4 programas principales con los dem´as programas en C4.5.

38

5.3.2.

Identificaci´ on de objetos, m´ etodos y variables

Seg´ un la aproximaci´on de Ignacio Silva [11], derivar una estructura de clases desde una perspectiva estructural, no se debe realizar desde un principio, sino m´as bien, se deriva desde la estructura actual del sistema. Por tal motivo, seguimos esta aproximaci´on para realizar el modelo conceptual de C4.5. Un objeto es una cosa, generalmente extra´ıda del vocabulario del espacio del problema o del espacio de la soluci´on,en este sentido, todo objeto tiene identidad (puede nombrarse o distinguirse de alguna manera de otros objetos), estado (generalmente hay algunos datos asociados a ´el), y el comportamiento (se le puede hacer cosas al objeto, y ´el a su vez puede hacer cosas a otros objetos). Para la identificaci´on de objetos en el dominio del sistema C4.5, nos basamos en la aproximaciones expuestas por Ignacio Silva [11] y Johannes Martin [14], en donde se expone de forma similar que un programa C consta de uno o m´as archivos de c´odigo fuente, de la misma forma, un programa en el paradigma orientado a objetos puede estar constituido por una o m´as clases. A cada archivo o programa fuente C lo asociamos con una clase u objeto, cuya identidad es el nombre del archivo fuente C, los m´etodos y variables que contiene este objeto son aquellos que se encuentran en el mismo archivo. En la fase de normalizaci´on, seguida en la aproximaci´on de Johannes Martin [14], se realiza una transformaci´on de funciones del c´odigo en el formato K&R al formato de un m´etodo, esta correspondencia de c´odigo se puede observar en la figura 5.5 y ser´a aplicada en cada una de las funciones del c´odigo fuente en C con el fin de mostrar la forma adecuada en el correspondiente diagrama de clases. La forma que ha tomado hasta aqu´ı cada clase se puede observar en la figura 5.6. Como podemos ver, a´ un no se encuentra cada clase en la manera adecuada, pr´acticamente ha sido tomado directamente del c´odigo fuente C, con la definici´on de variables apuntador, los m´etodos empiezan con may´ uscula y el nombre del objeto con min´ uscula. Una fase posterior realiza y explica la adaptaci´on de este objeto al paradigma orientado a objetos. 39

Figura 5.5: Ejemplo de transformaci´on de funciones en el formato K&R al formato de m´etodos en el POO.

Figura 5.6: Correspondencia de un archivo fuente C con un objeto.

40

Figura 5.7: Identificaci´on de las relaciones entre objetos.

5.3.3.

Identificaci´ on de la relaci´ on entre objetos

Durante esta fase, realizamos una revisi´on total del c´odigo fuente para identificar las llamadas a funciones (m´etodos) que son externas a un archivo. Es decir, aquellas funciones que no son locales y se encuentran en alg´ un otro archivo fuente pero que interact´ uan entre si para realizar una tarea o actividad espec´ıfica. Esto implica que existe una relaci´on entre estos archivos (clases en nuestro modelo orientado a objetos) como se ha planteado y que estas relaciones deben ser mostradas en el diagrama de clases. Un ejemplo de estas relaciones puede ser visualizado en la figura 5.7. Despu´es de haber realizado la identificaci´on de objetos, sus correspondientes m´etodos y variables, adem´as de la identificaci´on de sus relaciones con otros objetos, estamos

41

preparados para presentar una primera aproximaci´on al paradigma orientado a objetos. Este diagrama se presenta en la figura 5.8, sin embargo no es un diagrama de clases final, pues a´ un falta realizar un refinamiento de ´este para alcanzar un diagrama de clases concreto.

5.3.4.

Acoplamiento de variables y m´ etodos en el paradigma orientado a objetos

Durante la fase final de desarrollo de los diagramas de clase para los 4 programas principales de C4.5, principalmente nos enfocamos en el refinamiento del diagrama presentado en la figura 5.8 y los 3 diagramas correspondientes a los otros tres programas principales. En este refinamiento se considera la aproximaci´on tomada por Johannes Martin [14], para la correspondencia de los principales constructores del lenguaje C: Cambio de variables apuntador en los objetos. La correspondencia del lenguaje de programaci´on para el cual proponemos el diagrama de clases es Java. El manejo de apuntadores en C es distinto al manejo de referencias en Java. Por lo que es necesaria la eliminaci´on del uso extenso de variables apuntador, que se han integrado al diagrama de la figura 5.8. Notamos que principalmente el uso de estas variables apuntador es para la asignaci´on din´amica de memoria, y a su vez sean tratadas como arreglos. Por esta raz´on, se sustituye la definici´on de estas variables por la definici´on de arreglos como es mostrado en la figura 5.9. Eliminaci´ on de variables externas. La definici´on de variables externas en el c´odigo fuente c se realiza con la intenci´on de decir al compilador que la variable ser´a utilizada en el archivo o programa actual pero que se encuentra definida en otro archivo. Para el caso del paradigma orientado a objetos no es necesaria esta definici´on, pues solo basta con utilizar la variable externa por medio de una referencia al objeto en el que se encuentra definida, esta caracter´ıstica se 42

Figura 5.8: Primera aproximaci´on al paradigma orientado a objetos de C4.5. 43

Figura 5.9: Cambio de apuntadores por arreglos. ilustra en la figura 5.10 y por razones obvias son eliminadas del diagrama de clases en cada objeto que contiene este tipo de variables. Adem´as, el archivo extern.i al igual que el archivo buildex.i desaparecen debido a que su contenido es u ´nicamente la definici´on de variables externas. Normalizaci´ on de nombre de objetos, m´ etodos y variables. El paradigma orientado a objetos se caracteriza por estandarizar la definici´on de nombres de variables, m´etodos y objetos. Un objeto debe tener un nombre que inicie con una letra may´ uscula, un m´etodo y una variable deben iniciar con una letra min´ uscula, y en cualquier caso la uni´on de dos o m´as palabras es identificada por una may´ uscula al inicio de palabra continua. En el caso del diagrama de la figura 5.9 no se cumple con estos requerimientos y es necesaria la correcci´on mencionada. Estos se ven reflejados en los diagramas de clases finales de las figuras 5.12, 5.13, 5.14 y 5.15.

44

Figura 5.10: Eliminaci´on de variables externas. Cambio de tipos y objetos derivados. El lenguaje de programaci´on C soporta la definici´on de tipos derivados. Ambos tipos, fundamentales y derivados pueden tener nombres adicionales usando el mecanismo typedef. En el paradigma orientado a objetos, la definici´on de un tipo derivado como por ejemplo una estructura o uni´on, en la aproximaci´on de Johannes Martin [14] es transformado a un objeto y las referencias a los nombres adicionales de un tipo son cambiadas para referir a los nombres o tipos originales. En nuestro caso hemos seguido esta aproximaci´on y los tipos derivados principalmente los hemos obtenido del archivo types.i, el cual es sustituido por los objetos derivados. Un objeto m´as, derivado del conjunto de programas C4.5 es el archivo defns.i, el cual contiene la definici´on de algunas macros y constantes. Las constantes pasan a ser variables del objeto junto de algunas constantes definidas en el archivo types.i, y algunas de las macros se representa como m´etodos en el objeto. Lo descrito anteriormente lo podemos observar en la figura 5.11.

45

Figura 5.11: Objetos derivados.

46

Finalmente, despu´es de realizar los cambios mencionados anteriormente, hemos logrado desarrollar los 4 diagramas de clases para los 4 programas principales correspondientes a C4.5, estos diagramas se muestran en las figuras 5.12, 5.13, 5.14 y 5.15.

5.4.

Diagramas de colaboraci´ on

En cualquier sistema, los objetos interact´ uan entre s´ı pas´andose mensajes. Una interacci´ on es un comportamiento que incluye un conjunto de mensajes intercambiados por un conjunto de objetos dentro de un contexto para lograr un prop´ osito. Un mensaje es la especificaci´on de una comunicaci´on entre objetos que transmite informaci´ on, con la expectativa de que se desencadene una actividad. Las interacciones se utilizar´an para modelar los aspectos din´amicos de las colaboraciones, que representan sociedades de objetos que juegan roles espec´ıficos, y colaboran entre s´ı para llevar a cabo un comportamiento mayor que la suma de los comportamientos de sus elementos. Un diagrama de interacci´ on muestra una interacci´on, que consiste en un conjunto de objetos y sus relaciones, incluyendo los mensajes que se pueden enviar entre ellos. Un diagrama de colaboraci´ on es un diagrama de interacci´on que destaca la organizaci´on estructural de los objetos que env´ıan y reciben mensajes, principalmente estos mensajes provocan la invocaci´on de m´etodos entre instancias. Los diagramas de interacci´on constituyen uno de los artefactos m´as importantes que se generan en el an´alisis y el dise˜ no orientados a objetos. Por lo tanto, formal parte esencial de la documentaci´on del sistema. Seg´ un [15] el tiempo y el esfuerzo dedicados a su preparaci´on deber´ıan absorber un porcentaje considerable de la actividad total destinada del proyecto. Para elaborar un diagrama de colaboraci´on podemos encontrar en [15] las siguientes normas: Para preparar un diagrama de colaboraci´on: 1. Elabore un diagrama por cada operaci´on del sistema durante el ciclo actual de desarrollo. En cada mensaje, dibuje un diagrama incluy´endolo como mensaje inicial. 47

Figura 5.12: Diagrama de clases para el generador de ´arboles de decisi´on (C4.5). 48

Figura 5.13: Diagrama de clases para el generador de reglas de producci´on (C4.5rules). 49

Figura 5.14: Diagrama de clases para el consultor de ´arboles de decisi´on (Consult). 50

Figura 5.15: Diagrama de clases para el consultor de reglas de producci´on (Consultr). 51

2. Si el diagrama se torna complejo (por ejemplo, si no cabe holgadamente en una hoja de papel de 8.5 x 11), div´ıdalo en diagramas m´as peque˜ nos. 3. Dise˜ ne un sistema de objetos interactivos que realicen las tareas espec´ıficas. Seg´ un se plante´o en la secci´on 5.2, el modelo orientado a objetos de C4.5 tambi´en esta formado por los diagramas de colaboraci´on correspondientes al sistema, para mostrar los aspectos din´amicos de las colaboraciones entre objetos y realizar las tareas especificas en la construcci´on y consulta de ´arboles de decisi´on y reglas de producci´on. Hasta aqu´ı hemos identificado la relaci´on existente entre objetos, apreciables estas relaciones en los diagramas de clases. Ahora hemos comprendido la importancia de los diagramas de colaboraci´on en la documentaci´on de un sistema, por lo que es necesaria su obtenci´on a partir del c´odigo fuente. El dise˜ no de los diagramas de colaboraci´on consta de 4 diagramas principales, observando su correspondencia en la figura 5.16. Sin embargo cada uno de estos 4 diagramas se torna complejo y no es apropiado mostrarlo en un solo bloque. Siguiendo las normas de construcci´on de un diagrama de colaboraci´on, cada uno de ellos ha sido dividido en diagramas m´as peque˜ nos para una f´acil presentaci´on y comprensi´on. El proceso de desarrollo para la obtenci´on de estos diagramas es similar al de los diagramas de clases, al hacer una revisi´on total del c´odigo fuente e identificar las llamadas a m´etodos que no son propios del objeto, tomando en cuenta que dichos m´etodos se encuentran en otra clase, se modelan como mensajes que son intercambiados por ambos objetos. Este proceso de modelado es mostrado en la figura 5.17, agregando un fragmente de c´odigo fuente Java para ilustrar de forma concisa la localizaci´on de un m´etodo en una instancia. A continuaci´on se presentan los diagramas de colaboraci´on en las figuras A.1, A.2, A.3, A.4, A.5, A.6, A.7 y A.8. Desarrollados a partir del c´odigo fuente en C del conjunto de programas C4.5.

52

Figura 5.16: Correspondencia de los 4 programas principales con los diagramas de colaboraci´on.

5.5.

Diagramas de estados

Los diagramas de estados (statechart) se utilizan para el modelado de los aspectos din´amicos de un sistema. Un diagrama de estados muestra el flujo de control entre estados. Hemos explicado en la secci´on 2.7 las principales definiciones que involucran el desarrollo de los diagramas de estados, estas definiciones son: 2.2, 2.3 y 2.4. Al igual que los diagramas de clases y de colaboraci´on, los diagramas de estados forman parte de la vista de dise˜ no de un modelo, que es la vista de modelado que se desarrolla en este trabajo de tesis. Por lo tanto, tambi´en hemos desarrollado los diagramas de estados correspondientes al c´odigo fuente de C4.5. Estos diagramas se han desarrollado para cada m´etodo en un objeto, puesto que muestran la secuencia de estados por las que pasa cada m´etodo de un objeto a lo largo de su vida, en este caso, modelamos la secuencia de estados por la que pasa cada uno de los m´etodos en respuesta a un evento. Este procedimiento lo podemos ver en la figura 5.18. Principalmente identificamos a cada estado como aquel que realiza una actividad y satisface alguna condici´on, un 53

Figura 5.17: Proceso de obtenci´on de los diagramas de colaboraci´on.

54

Figura 5.18: Correspondencia de un diagrama de estados con el c´odigo fuente. evento como aquel acontecimiento que especifica que la tarea ha sido realizada y el estado se encuentra en espera de una transici´on, las transici´on es aquella que especifica la realizaci´on de otra actividad en un siguiente evento que cumpla las condiciones indicadas. Finalmente, los diagramas de estados obtenidos desde el c´odigo fuente C del conjunto de programas C4.5 son presentados en la siguientes p´aginas en la figura B.1.

55

Cap´ıtulo 6 Conclusiones Hemos logrado la obtenci´on del modelo conceptual orientado a objetos en la vista de dise˜ no, desde el c´odigo fuente de C4.5, que permite documentar el sistema de forma concisa, mostrando las dependencias estructurales existentes en una estructura orientada a objetos. Para la creaci´on del modelo utilizamos algunas aproximaci´on que nos han sido muy u ´tiles en la realizaci´on de nuestro trabajo, por lo tanto, no fue necesario su desarrollo desde cero. El modelo fue derivado aplicando t´ecnicas de conversi´on para las principales estructuras del lenguaje de programaci´on C al paradigma orientado a objetos. Las aproximaciones principalmente utilizadas en nuestro trabajo fueron: Obtenci´on del modelado de un sistema ya desarrollado mediante una derivaci´on de clases, a partir de las estructuras de datos actuales del sistemas, para despu´es realizar un mejoramiento del sistema usando m´etodos completamente orientados a objetos, expuesto por Jacobson y Lindstr¨oum [12]. La derivaci´on de la estructura de clase se realiz´o al considerar sus estructuras de datos como posibles objetos de alto nivel y desmontando procedimientos dentro de sentencias de c´odigo que son candidatos viables para llegar a ser m´etodos ligados a la estructura de clases, propuesto por Ignacio Silva [11].

56

Las principales estrategias de conversi´on de c´odigo fuente C a estructuras orientadas a objetos fueron obtenidas del trabajo de Johannes Martin [14], utilizando primordialmente los equivalentes para estructuras, uniones, variables externas y macros del lenguaje de programaci´on C hacia el paradigma orientado a objetos.

6.1.

Trabajos a futuro

Dado que C4.5 es un sistema que ha tenido gran ´exito en el aprendizaje artificial para el desarrollo de aplicaciones en la toma de decisiones. Ahora que contamos con un modelo conceptual que muestra la arquitectura de alto nivel del sistema, planteamos como trabajo a futuro los siguientes puntos: Mejoramiento del sistema aplicando t´ecnicas orientadas a objetos como patrones de dise˜ no, as´ı como tambi´en t´ecnicas de reingenier´ıa, las cuales realizan una modificaci´on de la estructura interna del sistema sin afectar su comportamiento. Codificaci´on del modelo conceptual de C4.5 en un lenguaje de programaci´on orientado a objetos como Java. Considerar la posibilidad de convertir la aplicaci´on C4.5 en un paquete Java, de forma tal que la tecnolog´ıa de C4.5 pueda ser incluida en aplicaciones espec´ıficas. Finalemente, podemos comentar que hemos enmarcado los trabajos a futuro como parte del mantenimiento del software C4.5.

57

Ap´ endice A Diagramas de colaboraci´ on

58

59

60 Figura A.2: Continuaci´on del diagrama de colaboraci´on para el generador de ´arboles de decisi´on.

Figura A.3: Continuaci´on del diagrama de colaboraci´on para el generador de ´arboles de decisi´on.

61

Figura A.4: Continuaci´on del diagrama de colaboraci´on para el generador de ´arboles de decisi´on.

62

63

64

Figura A.6: Continuaci´on del diagrama de colaboraci´on para el generador de reglas de producci´on.

Figura A.7: Diagrama de colaboraci´on para 65 el consultor de ´arboles de decisi´on (Consult).

Figura A.8: Diagrama de colaboraci´on para el consultor de reglas de producci´on (Consultr).

66

Ap´ endice B Diagramas de estado

67

Figura B.1: M´etodo main de la clase C4.5

Figura B.2: M´etodo readName de la clase GetNames

68

Figura B.3: M´etodo getNames de la clase GetNames

69

Referencias [1] J. R. Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, first edition, 1993. [2] Tom Mitchell. Machine Learning. McGraw Hill, 1997. [3] Grady Booch. An´ alisis y Dise˜ no orientado a objetos. Addison Wesley Longman, 2nd edition, 1996. [4] Ivar Jacobson Grady Booch, James Rumbaugh. El lenguaje unificado de modelado. Addison Wesley Iberoamericana, 1999. [5] Hausi A. Muller, Jens H. Jahnke, Dennis B. Smith, Margaret-Anne D. Storey, Scott R. Tilley, and Kenny Wong. Reverse engineering: a roadmap. In ICSE — Future of SE Track, pages 47–60, 2000. [6] Kenny Wong, Scott R. Tilley, Hausi A. M¨ uller, and Margaret-Anne D. Storey. Structural redocumentation: A case study. IEEE Software, 12(1):46–54, 1995. [7] Scott R. Tilley, Kenny Wong, Margaret-Anne D. Storey, and Hausi A. M¨ uller. Programmable reverse engineering. International Journal of Software Engineering and Knowledge Engineering, 4(4):501–520, 1994. [8] Allison Leah Waingold. Automated extraction of abstract object models. Master’s thesis, Massachusetts Institute of Technology, May 2001.

70

[9] Daniel Jackson and Allison Waingold. Lightweight extraction of object models from bytecode. In International Conference on Software Engineering, pages 194– 202, 1999. [10] G. J. Holzmann. From code to models. pages 3–10, Newcastle upon Tyne, U.K., 2001. [11] Ignacio Silva-Lepe. Techniques for Reverse-Engineering and Re-Engineering into the Object-Oriented Paradigm. Doctor of philosophy, College of Computer Science of Northeastern University, June 1994. [12] Ivar Jacobson and Fredrik Lindstr¨om. Re-engineering of old systems to an objectoriented architecture. In OOPSLA Conference, Special Issue of SIGPLAN Notices, pages 340–350, Phoenix, AZ, 1991. [13] Paul L. Bergstein. Maintenance of object-oriented systems during structural schema evolution. Theory and Practice of Object Systems, 3(3):185–212, 1997. [14] Johannes Martin. Ephedra, a C to Java Migration Environment. Doctor of philosophy, Northern Illinois University, 1996. [15] Craig Larman. UML y Patrones. Prentice Hall, primera edition, 1999.

71