algoritmo basado en estimacion de...

3

ALGORITMO BASADO EN ESTIMACION DE DISTRIBUCION (EDA)

PARA DETERMINAR CAUSAS DE LA DESERCIÓN ESCOLAR

YENCID ALEXANDRA MOJICA DIMATE

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS

FACULTAD TECNOLOGICA

PROYECTO CURRICULAR TECNOLOGIA

SISTEMATIZACION DE DATOS

BOGOTA D.C.

2015

4

ALGORITMO BASADO EN ESTIMACION DE DISTRIBUCION (EDA)

PARA DETERMINAR CAUSAS DE LA DESERCIÓN ESCOLAR

YENCID ALEXANDRA MOJICA DIMATE

TESIS DE GRADO

Director:

Ing. JORGE RODRIGUEZ

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS

FACULTAD TECNOLOGICA

PROYECTO CURRICULAR

TECNOLOGIA SISTEMATIZACION DE DATOS

BOGOTA D.C.

2015

5

TABLA DE CONTENIDO

RESUMEN ................................................................................................................ 11

ABSTRACT ................................................................................................................ 12

INTRODUCCIÓN........................................................................................................ 13

1.1. DESCRIPCIÓN DEL PROBLEMA ................................................................................. 14

1.2. ALCANCES Y DELIMITACIONES ................................................................................. 14

1.2.1. ALCANCES .............................................................................................................. 14

1.2.2. DELIMITACIONES ..................................................................................................... 14

1.3. OBJETIVOS ........................................................................................................ 15

1.3.1. OBJETIVO GENERAL.................................................................................................. 15

1.3.2. OBJETIVOS ESPECÍFICOS ............................................................................................ 15

1.4. JUSTIFICACIÓN.................................................................................................... 15

1.5. MARCO CONCEPTUAL, TECNOLÓGICO Y METODOLÓGICO.............................................. 16

1.5.1. SELECCIÓN DE VARIABLES .......................................................................................... 16

1.5.2. ALGORITMOS DE OPTIMIZACIÓN EDA .......................................................................... 19

1.5.3. ALGORITMOS DE SELECCIÓN DE VARIABLES ................................................................... 20

1.5.4. DISCRETIZACIÓN DE VARIABLES .................................................................................. 21

1.5.5. BINARIZACIÓN DE VARIABLES DISCRETAS ...................................................................... 22

1.5.6. HERRAMIENTAS TECNOLÓGICAS: SOFTWARE ORANGE- GOLDENBERRY .............................. 22

1.5.7. METODOLOGÍA DE MINERÍA DE DATOS CRISP .............................................................. 29

1.5.8. DESERCIÓN ESCOLAR ................................................................................................ 31

1.6. FACTIBILIDAD ..................................................................................................... 32

1.6.1. TÉCNICA................................................................................................................. 32

1.6.2. OPERATIVA ............................................................................................................. 33

1.6.3. ECONÓMICA ........................................................................................................... 33

1.6.4. LEGAL .................................................................................................................... 34

1.7. DIAGRAMA DE ACTIVIDADES .................................................................................. 34

2. ESTUDIO Y SELECCIÓN DEL ALGORITMO WKIERA RESPECTO A OTROS

ALGORITMOS ........................................................................................................... 35

2.1. SELECCIÓN DE WIDGET PARA ALGORITMO EDA .......................................................... 36

2.2. COMPARACIÓN Y SELECCIÓN DEL ALGORITMO A USAR PARA LA DESERCIÓN ESCOLAR........... 43

2.3. DISCUSIÓN DE RESULTADOS ................................................................................... 47

3. SELECCIÓN DE VARIABLES DEL CONJUNTO DE DATOS PARA DETERMINAR

DESERCIÓN ESCOLAR ................................................................................................ 48

6

3.1. DISCRETIZACIÓN DE VARIABLES .............................................................................. 48

3.2. DESCRIPCIÓN DE DATOS ........................................................................................ 49

3.3. EXPERIMENTACIÓN .............................................................................................. 50

3.3.1. ITERACIÓN 1 ........................................................................................................... 50

3.3.2. ITERACIÓN 2 ........................................................................................................... 52

3.3.3. ITERACIÓN 3 ........................................................................................................... 53

3.3.4. ITERACIÓN 4 ........................................................................................................... 54

3.4. DISCUSIÓN DE RESULTADOS COLEGIO OFELIA URIBE DE ACOSTA ..................................... 55

4. CONJUNTO DE LIBRERÍAS DE ORANGE PARA LA SELECCIÓN DE VARIABLES .......... 56

5. ANÁLISIS DE PRUEBAS Y RESULTADOS ................................................................ 59

6. CONCLUSIONES Y TRABAJO FUTURO .................................................................. 64

7. BIBLIOGRAFÍA .................................................................................................... 65

7

LISTA DE FIGURAS

Figura 1. 1: Representación gráfica del método wrapper (envoltura). El predictor es la

forma de hacer aprendizaje computacional, los subconjuntos de variables son evaluados

por el predictor . -------------------------------------------------------------------------------------- 17

Figura 1. 2: Se observa como los datos son mapeados por una función que inserta los

datos dentro de un espacio de variables donde un patrón no lineal es transformado en un

patrón lineal . ----------------------------------------------------------------------------------------- 19

Figura 1. 3: Pseudo código algoritmo EDA. ----------------------------------------------------- 19

Figura 1. 4: Flujo de algoritmo EDA . ------------------------------------------------------------ 20

Figura 1. 5: Diagrama de flujo del algoritmo wKIERA . -------------------------------------- 21

Figura 1. 6: Arboles de clasificación creados por programación con componentes visuales

de Orange . -------------------------------------------------------------------------------------------- 23

Figura 1. 7: Widget de Orange . ------------------------------------------------------------------- 24

Figura 1. 8: Selección de atributos . --------------------------------------------------------------- 25

Figura 1. 9: Programación por componentes de Goldenberry en Orange . ----------------- 28

Figura 1. 10: Fases de CRISP-DM. Las flechas indican las más importantes y frecuentes

dependencias entre las clases. El circulo exterior representa la naturaleza cíclica de la

metodología de minería de datos, donde los algoritmos que se van a usar en el proyecto se

integran a la fase de modelo . ---------------------------------------------------------------------- 30

Figura 1. 11: Diagrama de Actividades. ---------------------------------------------------------- 34

Figura 2. 1: Grupo de herramientas de minería de datos Orange. Plataforma Principal de

Orange. 35

Figura 2. 2: Algunos componentes de programación visual Orange . ----------------------- 36

Figura 2. 3: Salida de la función Kernel Builder. Plataforma Principal de Orange. ------- 37

Figura 2. 4: Función que se usa para el algoritmo. Plataforma Principal de Orange. ----- 37

Figura 2. 5: Variables componente visual Kernel perceptrón. Plataforma Principal de

Orange. ------------------------------------------------------------------------------------------------ 37

Figura 2. 6: Entradas y salidas del componente visual Data Sampler. Plataforma Principal

de Orange. --------------------------------------------------------------------------------------------- 38

Figura 2. 7: Salida del componente visual File. Plataforma Principal de Orange. --------- 38

Figura 2. 8: Entradas y salidas del componente visual Wrapper Cost Function. Plataforma

Principal de Orange. --------------------------------------------------------------------------------- 39

8

Figura 2. 9: Entrada y salida del componente visual del algoritmo TILDA. Plataforma

principal de Orange. --------------------------------------------------------------------------------- 40

Figura 2. 10: Entrada y salida del componente visual del algoritmo PBIL. Plataforma


Figura 2. 11: Entrada y salida del componente visual del algoritmo UMDA. Plataforma


Figura 2. 12: Representación gráfica de componentes visuales en Orange utilizados para

la experimentación en los conjuntos de prueba. Plataforma Principal de Orange. -------- 43

Figura 2. 13: Resultados Black Box Tester para la Prueba 1. Plataforma Principal de

Orange. ------------------------------------------------------------------------------------------------ 44


Orange. ------------------------------------------------------------------------------------------------ 45


Orange. ------------------------------------------------------------------------------------------------ 46

Figura 3. 1: Modelado por Componentes de la Iteración 1. ……………………. ……..51

Figura 4. 1: Ejemplo carga de datos de un archivo .txt ………………………57

Figura 4. 2: Configuración del Widget Kernel Builder. Plataforma Principal de Orange. 58

Figura 4. 3: Script de la function Gaussian Kernel. Plataforma Principal de Orange. ---- 58

Figura 5. 1: Pseudo código del algoritmo UMDA ……...……………………………….59

Figura 5. 2: Pseudo código de un Árbol de Decisión. ------------------------------------------ 61

9

LISTA DE TABLAS

Tabla 1. 1: Tabla de binarización de variable X con valores posibles {A, B, C, D}. ____ 22

Tabla 1. 2: Lista de componentes de Goldenberry 1.0. __________________________ 26

Tabla 1. 3: Lista de componentes de Goldenberry 1.0. __________________________ 27

Tabla 1. 4: Factibilidad Económica. ________________________________________ 33

Tabla 3. 1: Los 4 grupos de variables discretas. ……………………………………….48

Tabla 3. 2: Experimentos a realizar por variable clase para identificación de variables de

deserción escolar Base de datos Colegio Ofelia Uribe de Acosta. __________________ 49

Tabla 3. 3: Diccionario de datos de las variables escogidas para el estudio de deserción

escolar del Colegio Ofelia Uribe de Acosta. VP= Valores Posibles. ________________ 49

Tabla 3. 4: Descripción archivos de trabajo iteración 1. _________________________ 50

Tabla 3. 5: Configuración de componentes visuales realizada para la Iteración 1. _____ 51

Tabla 3. 6: Variables halladas en la Iteración 1. _______________________________ 52

Tabla 3. 7: Descripción archivos de trabajo Iteración 2. _________________________ 52

Tabla 3. 8: Variables halladas en la Iteración 2. _______________________________ 53

Tabla 3. 9: Descripción archivos de trabajo Iteración 3. _________________________ 53

Tabla 3. 10: Variables halladas en la Iteración 3. ______________________________ 54

Tabla 3. 11: Descripción archivos de trabajo Iteración 4. ________________________ 54

Tabla 3. 12: Variables halladas en la Iteración 4. ______________________________ 55

Tabla 5. 1: Algoritmo UMDA. ………………………………………………………...60

Tabla 5. 2: Árbol de Decisión. ____________________________________________ 62

10

Dedico este trabajo al Espíritu Santo, por su guianza

su misericordia, su compañía y a mis padres que con

su apoyo, confianza y ayuda lo hicieron posible.

11

RESUMEN

Los Algoritmos Basados en Estimación de Distribución (EDAs), ofrecen un nuevo

paradigma de algoritmos evolutivos, en donde se hace uso de un modelo probalístico el

cual va aprendiendo de las soluciones más prometedoras para guiar el proceso de

búsqueda, esta búsqueda se realiza en una gran cantidad de datos suministrados para este

caso, por un colegio oficial de Bogotá, y con el fin de determinar las causas principales de

la deserción escolar dentro de este plantel.

El desarrollo de los EDAs en los últimos años, se ha realizado usando una plataforma

gráfica; llamada Orange, es importante resaltar que no se necesita tener conocimientos

previos de programación para hacer uso de esta herramienta, la cual a través de los widget

que la componen permite interactuar y realizar diferentes uniones entre los elementos,

para así formar nuevos modelos que faciliten el manejo de los datos.

Específicamente en el caso de estudio del colegio Ofelia Uribe de Acosta, se obtuvo un

mejor comportamiento por parte de las variables binarias respecto a las variables

discretas. De ahí la importancia del pre procesamiento de los datos con anterioridad,

buscando obtener mejores resultados para la selección de variables, teniendo en cuenta el

algoritmo que se va a usar, ya que esta plataforma permite personalizar el algoritmo de

acuerdo a las necesidades particulares del usuario.

En cuanto a tiempo y cantidad de variables halladas para determinar la deserción escolar,

el widget UMDA que hace parte del modelo del algoritmo wKIERA, empleado para el

desarrollo de este proyecto, presento mejores resultados confirmando su superioridad

respecto a otros algoritmos de selección de atributos usados tradicionalmente.

12

ABSTRACT

The algorithms Based distribution estimation (EDA), offer a new paradigm of

evolutionary algorithms, where using a probalistic model, which learns from the more

promising solutions to guide the search process, It is search is performed in a lot of data

supplied for this case by an College of Bogota, and in order to determine the main causes

of school dropouts within this place.

The Development of the EDAs in the last years, has been performed using a graphics

platform; Orange call, is important to note that not need to have prior programming

knowledge for tool use, which is Through the widget that the compose it can interact and

perform different connections between the elements, thereby forming new models to

facilitate handling of data.

Specifically in the case study school Ofelia Uribe, it was obtained best behavior of binary

variables respect of the discrete variables wings. Hence the importance of pre Data

Processing before, searching better results for the selection of variables, taking into

account the algorithm of use, as this platform allows you to customize the algorithm

according to the particular needs of User.

In terms of time and number of variables found to determine the school dropout , the

UMDA widget that is part of the algorithm wKIERA model , used for the development of

this project , presented better results confirming its superiority over other selection

algorithms of variables used traditionally.

13

INTRODUCCIÓN

Los avances de la computación han hecho crecer la generación y consumo de grandes

cantidades de datos así como la necesidad de realizar un proceso de análisis inteligente de

los mismos; este es el contexto o entorno de la minería de datos DM (´´ Data Mining´´).

El objetivo de la minería de datos se puede describir de manera simple: descubrir el

conocimiento oculto de los datos.

Una manera de descubrir conocimiento es identificar las variables relevantes de un

fenómeno observado, lo cual es más útil aun en aplicaciones cuyos conjuntos de datos son

de miles e incluso de millones de variables, lo que implica complejos tareas de

clasificación en espacios dimensionales grandes. En este sentido los métodos de selección

de variables se convierten en una herramienta eficaz aplicable a problemas compuestos de

grandes cantidades de datos. El objetivo principal de la selección de variables se resume

en: mejorar la precisión de los predictores, proveer un predictor más rápido y más

rentable, y facilitar un mejor entendimiento de los procesos subyacentes que generan los

datos [1].

Este proyecto va enfocado a conocer las principales causas de la deserción escolar, en el

Colegio Ofelia Uribe de Acosta teniendo como insumo los datos suministrados por el

rector de la institución, usando un algoritmo basado en estimación de distribución (EDA)

llamado wKIERA.

En el capítulo, 1 se expone los objetivos y la motivación del desarrollo del proyecto, se da

a conocer los diferentes temas, conceptos y metodologías que son necesarios para

conocer y entender el desarrollo del mismo.

En el capítulo 2, se analizó los algoritmos que están implementados en el lienzo de

Orange con el fin de escoger el indicado, basándose en la relación tiempo respecto a

cantidad de variables encontradas en cada ejecución, de esta manera se escogió el

algoritmo indicado para usar en este caso de estudio.

En el capítulo 3, se realizó la preparación de los datos usando la discretización de

variables, ya que para obtener resultados verídicos con los algoritmos EDA es necesario

preparar los datos y usar variables binarias.

En el capítulo 4, se hizo referencia a algunas librerías principales que utiliza Orange, para

el desarrollo de problemas de minería de datos; en el capítulo 5, se comparó el algoritmo

UMDA usado en el diseño del algoritmo wKIERA con otros algoritmos de selección de

variables, buscando determinar cuál era mejor en cuanto a complejidad computacional y

eficiencia.

Y para culminar en el capítulos 6, se colocaron las conclusiones finales de todo el

desarrollo del proyecto y se mencionaron algunos trabajos futuros.

14

1.1. Descripción del problema

¿Cómo usar un Algoritmo basado en estimación de distribución (EDA) para determinar

causas de la deserción escolar?

El colegio Ofelia Uribe cuenta con 2.440 estudiantes de las dos jornadas diurnas, los

grados van desde Preescolar hasta grado once, está ubicado al sur de la ciudad de Bogotá,

pertenece a la red de colegios públicos del distrito [26].

De la cantidad de estudiantes para los que el colegio tiene capacidad, aproximadamente

desertan entre 200 y 300 anualmente, de los cursos de preescolar a once de ahí surge la

necesidad de conocer las motivaciones que llevan a los jóvenes y niños a dejar de

estudiar, y plantear proyectos y soluciones para lograr disminuir esta cantidad [27].

La deserción se puede dar de distintas formas, según su duración es temporal o definitiva,

según su alcance, es decir; los estudiantes son trasladados, y según la temporalidad, que

hace referencia al nivel educativo en el que se presente la deserción [27].

Algunas consecuencias que trae la deserción escolar afecta al Estado, las instituciones

educativas, los niños, los jóvenes y sus familias. En Colombia, según los estudios

recientes, la educación es el factor más relevante para explicar las diferencias en los

ingresos y por cada año de educación los ingresos de las personas aumentan más del 15%

en promedio [27].

1.2. Alcances y delimitaciones

1.2.1. Alcances

- Los algoritmos EDAs están orientados a resolver problemas de aprendizaje

supervisado; por lo tanto no se contemplan algoritmos dentro del aprendizaje no

supervisado.

- La propuesta aportará características importantes para la toma de decisiones

respecto a la deserción escolar en el colegio Ofelia Uribe de Acosta, tomando

este colegio como referente.

1.2.2. Delimitaciones

- Los resultados producto de este proyecto se aplicaran en el colegio Ofelia Uribe

de Acosta.

- El análisis de la selección de características relevantes en el problema planteado

se basará en la implementación de un algoritmo EDA; mas no en el desarrollo de

15

un software. Lo anterior, con lleva a que no es necesario evaluar plataformas ni

herramientas de desarrollo.

1.3. Objetivos

1.3.1. Objetivo General

Usar un algoritmo basado en la estimación de distribución (EDA) para determinar causas

de la deserción escolar.

1.3.2. Objetivos Específicos

- Analizar y seleccionar un algoritmo basado en la estimación de distribución para

determinar causas de la deserción escolar.

- Seleccionar y preparar un conjunto de datos referente a deserción escolar con el

fin de aplicar los algoritmos seleccionados.

- Seleccionar y utilizar un conjunto de librerías dentro de la suite de Orange

Canvas empleados para la selección de atributos.

- Comparar el algoritmo EDA en cuanto a complejidad computacional y

efectividad se refiere, con otros algoritmos de selección de atributos usados

tradicionalmente.

1.4. Justificación

Se conoce que en las propuestas de los dirigentes bogotanos y colombianos se plantea el

interés en el estudio de jóvenes y niños, aportando también a que el índice de

analfabetismo disminuya, por esto se hace necesario dar soluciones a esta problemática,

que no solo beneficiara al joven que cambiara su futuro, sino a su familia, a la ciudad y al

país.

No se usarán algoritmos tradicionales de aprendizaje supervisado porque utilizan un

mayor espacio de memoria, no usan gran cantidad de variables y el tiempo en dar

respuesta es mayor, por tal razón se plantea el uso de nuevos algoritmos de selección de

variables.

Los algoritmos de selección de variables son una técnica de aprendizaje automático para

reducción de la dimensionalidad de grandes conjuntos de datos, donde datos irrelevantes

o ruido son parte de algunos obstáculos para su aplicación. Los algoritmos de selección

ofrecen gran apoyo en la investigación porque proveen la explicación de grandes

conjuntos de datos mediante patrones de fácil comprensión, adicionalmente estos

16

métodos permiten a los investigadores enfocar su trabajo en la información que es

realmente importante, provocando así una reducción en el costo o consumo de tiempo de

experimentos o investigaciones.

Algunas técnicas de selección de variables asumen que estas son independientes entre sí,

algoritmos como wKIERA [8] y TILDA [9] han demostrado buenos resultados en tareas

de clasificación de conjuntos grandes de variables con un reducido consumo de memoria,

y con buen desempeño en sus predicciones.

En lugar de utilizar operaciones genéticas, estos algoritmos se basan en técnicas

estadísticas bien conocidas para estimar los parámetros de una función de distribución, y

la evolución es guiada por el muestreo de la evolución del modelo probabilístico.

La complejidad del algoritmo reside en la robustez de este modelo de probabilidad y en la

forma en que se estima de forma iterativa. Los modelos probabilísticos pueden ser tan

simples como una distribución marginal o tan complejo como una distribución

multivariante conjunta expresando las interacciones de alto orden entre las variables

observadas.

Los algoritmos anteriormente descritos han sido implementados en un entorno grafico de

programación mediante el proyecto Goldenberry [10], dentro de la plataforma de Orange

[3], lo cual ha permitido experimentación de estos algoritmos en entornos controlados.

Los estudios previos en relación a estos algoritmos y a la herramienta Goldenberry han

planteado como trabajo futuro estudiar su aplicación y desempeño en problemas de datos

reales.

Con el planteamiento de aplicar los algoritmos en problemas reales, surge la idea de

realizar un estudio con los datos suministrados por el Colegio Ofelia Uribe de Acosta,

estos datos están compuestos por 2.703 registros con aproximadamente 65 variables,

haciendo de este caso de estudio un proyecto interesante; ayudando a la toma de

decisiones por parte de las directivas del plantel, buscando frenar la deserción escolar en

esta institución.

1.5. Marco Conceptual, Tecnológico y Metodológico

En este marco se presenta una introducción a los diferentes temas que se involucran en el

desarrollo del proyecto.

1.5.1. Selección de Variables

Métodos de envoltura (´´Wrapper’’)

Permite tomar el problema de selección de variables, sin importar el tipo de aprendizaje

computacional, es decir es un método de tipo black box de entrada y salida.

17

El método wrapper usa el rendimiento de predicción de una máquina de aprendizaje para

evaluar la utilidad relativa de los subconjuntos de variables, y así encontrar las variables

relevantes, un inconveniente que surge con este método es más demanda de recursos

computacionales [1].

Figura 1. 1: Representación gráfica del método wrapper (envoltura). El predictor es la

forma de hacer aprendizaje computacional, los subconjuntos de variables son evaluados

por el predictor [1].

Máquinas de Vectores de Soporte

Conocidas generalmente como SVM, son una técnica de clasificación de variables. Una

tarea de clasificación usualmente implica la separación de los datos o muestras en dos

subconjuntos: de entrenamiento (training) y de prueba (testing). Cada instancia en el

conjunto de entrenamiento contiene un ´´Valor Objetivo´´ (variable clase) y una serie de

´´Atributos´´ (variables); la función principal del SVM es producir un modelo (basado en

el conjunto de entrenamiento) el cual predice el valor objetivo del subconjunto de prueba

solo con los atributos o variables.

Dado un conjunto de entrenamiento de pares variable etiqueta (xi, yi), i = 1, …, l donde

xi n y y {1, -1}l , las SVM requiere la solución para el problema de optimización

de la ecuación (1.1):

∑

Sujeto a ( ( ) ) (1.1)

Aquí los vectores de entrenamiento son mapeados en un más grande (tal vez infinito)

espacio dimensional por la función . SVM encuentra un hiperplano lineal donde

18

es el parámetro de penalización del término de error, donde en la ecuación 1.2 es llamada

la función Kernel [11].

( ) ( ) ( ) (1.2)

Máquinas de Kernel

En la búsqueda de patrones de datos o conjuntos de variables son deseables dos

características principales: eficiencia computacional y estabilidad estadística. En el

enfoque kernel de análisis de patrones primero los datos son introducidos en un espacio

apropiado de variables donde luego por medio de algoritmos basados en algebra lineal,

geometría y estadística se descubren los patrones en el espacio de variables, ampliando el

concepto se dice que los métodos de kernel están compuestos por dos partes: un módulo

que mapea dentro de un espacio de variables y en segundo lugar un algoritmo de

aprendizaje diseñado para descubrir patrones lineales en dicho espacio de variables. Gran

parte del éxito de los métodos kernel es debido a la detección de relaciones lineales que

son características deseadas de varias metodologías, lo que permite la representación de

grandes espacios dimensionales en patrones lineales [14].

Dos funciones de kernel reconocidas son el kernel RBF (Funciones de base radial) (1.3) y

el kernel polinomio (1.4) que son respectivamente:

( ) ( ∑ ( )

) (1.3)

( ) ⟨ ⟩ (1.4)

19

Figura 1. 2: Se observa como los datos son mapeados por una función que inserta los

datos dentro de un espacio de variables donde un patrón no lineal es transformado en un

patrón lineal [21].

Donde ⟨ ⟩ representa el espacio de entrada y representa el número de

variables o dimensiones. El parámetro y definen la anchura de RBF y el kernel

polinomio respectivamente. Versiones modificadas de estos kernel introducen pesos a los

factores escalares para darle peso que contribuye cada dimensión al total de la

operación, de esta manera se redefine el Kernel RBF (1.5) y el kernel polinomio (1.6):

( ) ( ∑ ( )

) (1.5)

( ) (∑ ( )

) (1.6)

1.5.2. Algoritmos de optimización EDA

Los Algoritmos evolutivos de búsqueda se han convertido en el eje esencial de las

herramientas para la solución de problemas en espacios multidimensionales, como por

ejemplo el caso de la bioinformática. Los Algoritmos genéticos (GA), es la técnica más

reconocida de la búsqueda de forma evolutiva, ha sido objeto de la mayor parte de estas

aplicaciones. Los Algoritmos de Estimación de Distribución (EDA) ofrecen un nuevo

paradigma de algoritmos evolutivos, en donde hace uso de un modelo probalistico el cual

va aprendiendo de las soluciones más prometedoras para guiar el proceso de búsqueda.

Las principales ventajas de los EDA sobre los algoritmos genéticos son: la ausencia de

varios parámetros de ajuste (como por ejemplo probabilidades de cruce o mutación) y un

mejor modelo probalístico de búsqueda [1]. A continuación la Figura 1.3 muestra el

algoritmo EDA. En la Figura 1.4 Se ilustra el funcionamiento del algoritmo.

Figura 1. 3: Pseudo código algoritmo EDA [7].

20

Figura 1. 4: Flujo de algoritmo EDA [7].

EDA UNIVARIADO

Los algoritmos EDAs son categorizados como univariados- discretos porque estos

asumen que las variables binarias son independientes, en este grupo se hallan los

algoritmos cGA, UMDA y PBIL, entre otros [1], en el caso de PBIL usa la probabilidad

del modelo factorizado como el producto de las distribuciones marginales univariadas

independientes (ver ecuaciones (1.3), (1.4)).

( ) ∏ ( ) (1.7)

( ) {

(1.8)

El parámetro de distribución es estimado de el conjunto de candidatos , donde la

ecuación 1.5 es usada como actualizador de la estimación.

∑ (1.9)

1.5.3. Algoritmos de selección de Variables

wKIERA

En los métodos de selección de variables de tipo envoltura o Wrapper se usa un

clasificador para evaluar variables según su poder de contribución a la predicción, en este

caso se hará uso de un vector de peso (´´weight vector´´) que será el instrumento con el

que se hará la selección de las variables significativas.

El algoritmo wKIERA (´´weighted Kernel-based Iterative Estimation of Relevance´´)

combina búsqueda estocástica de estimación de distribución con un kernel de

reconocimiento de patrones, el kernel usado es el Perceptron [8].

En la Figura 1.5 se observa como dos subconjuntos son tomados de , donde el primer

subconjunto es para el entrenamiento del Kernel perceptron y el segundo es usado para la

21

función de score junto con la salida del perceptron, esta función otorga los pesos al vector

→ que es la salida del algoritmo.

Figura 1. 5: Diagrama de flujo del algoritmo wKIERA [8].

1.5.4. Discretización de Variables

Los algoritmos de aprendizaje computacional, son utilizados en muchas tareas de

clasificación con datos del mundo real correspondientes a variables continuas,

frecuentemente no pueden ser aplicados hasta que dichas variables continuas sean

transformadas a discretas; lo que se observa en este caso de estudio, donde el algoritmo

seleccionado para este trabajo requiere que la variable clase sea discreta y que además

esta clase solo tenga dos valores [4].

22

1.5.5. Binarización de Variables Discretas

Junto con la discretizacion, la binarización favorece el resultado de los clasificadores, en

particular para este trabajo el clasificador SVM [6]. Para este caso de estudio de las

variables de la base de datos de los estudiantes del Colegio Ofelia Uribe de Acosta al

discretizar las variables, se tienen ahora por cada variable un número de posibles

valores, para el proceso de binarización se toma de cada variable discreta y se separa en

variables nuevas de cada uno de sus valores posibles, donde se asigna 1 en donde este la

presencia de cada variable correspondiente; es decir, por ejemplo, para la variable X con

posibles valores discretos A,B,C,D, la variable X se elimina pero se divide en 4 nuevas

variables AX, BX, CX, DX, cada una con valores posibles de [0,1] donde 1 indica la

presencia de la variable y 0 la ausencia de esta (ver tabla 1.1).

VARIABLE

DISCRETA

VARIABLES BINARIAS

Tabla 1. 1: Tabla de binarización de variable X con valores posibles {A, B, C, D}.

1.5.6. Herramientas Tecnológicas: Software Orange- Goldenberry

Orange: Plataforma abierta de minería de datos por componentes

Orange [3] es una herramienta de minería de datos y de aprendizaje computacional para

análisis de datos a través de codificación en Phyton y programación visual; el software

está basado en el análisis interactivo de los datos y el ensamblado mediante componentes

de procesos de minería de datos.

Las librerías de Orange están organizadas jerárquicamente en herramientas o

componentes de minería de datos. Los procedimientos de bajo nivel jerárquico pueden ser

ensamblados con otros componentes de alto nivel, los principales componentes son [3]:

Data management and preprocessing: para entradas y salidas de datos, filtrado

de datos y muestras de datos, acompañado de herramientas de manipulación de

variables y selección de variables.

X AX BX CX DX

A 1 0 0 0

B 0 1 0 0

C 0 0 1 0

D 0 0 0 1

B 0 1 0 0

A 1 0 0 0

C 0 0 1 0

23

Classification: Está compuesto de varios algoritmos de aprendizaje automático

supervisados como: Bayesian aproaches, tress, forest, entre otros.

Regression: Contiene regresiones lineales cuadradas, arboles de regresión entre

otros.

Association: Reglas de asociación entre los diferentes componentes.

Ensembles: Implementación como envoltura para boosting, forest tres, entre

otros.

Clustering: Incluye k- means y enfoques de agrupamiento jerárquico.

Evaluation: Compuesto de funciones de puntaje de desempeño de los métodos

de predicción.

Projections: Análisis de componentes, con escalamiento multidimensional.

Una de las características más sobresaliente de Orange es su plataforma de programación

visual es con un lienzo gráfico de usuario donde se permite la interacción de los

diferentes componentes.

Figura 1. 6: Arboles de clasificación creados por programación con componentes

visuales de Orange [20].

Pero uno de los puntos más sobresalientes de Orange es que se pueden crear componentes

nuevos y ser totalmente integrados, interactuando con los demás componentes lo que

permite crear soluciones a la medida.

Los Widgets de Orange son bloques de construcción de flujos de trabajo de análisis de

datos que se ensamblan en el entorno de programación visual de Orange.

24

Figura 1. 7: Widget de Orange [20].

Los Widgets se agrupan en clases de acuerdo a su función. Un flujo de trabajo típico

puede mezclar widgets para entrada de datos y filtrado, la visualización y la minería de

datos predictiva.

o SELECCIÓN DE ATRIBUTOS

Entrada: Conjunto de datos de atributos de valor.

Salidas: Atributo de valor conjunto de datos compuesta utilizando la especificación de

dominio desde el widget.

Seleccionar atributos widget se utiliza para componer manualmente el dominio de

datos. El usuario puede decidir qué atributos se utilizarán y cómo usarlos. Orange

distingue entre los atributos predictivos y atributos clase. Por ejemplo, para la

construcción de un modelo de clasificación, el dominio se compone de un conjunto de

atributos predictivos y un atributo de clase de tipo discreta.

Los atributos en Orange pueden ser discretos, continuos o cadena de caracteres. El tipo de

atributo está marcado con un símbolo que aparece antes del nombre del atributo (D, C, S,

respectivamente).

A continuación se muestra, la Figura 1.8, donde se muestra el lienzo básico que usa

Orange en la selección de atributos.

1. Los atributos que se muestran en la parte izquierda del lienzo, son atributos de

entrada; los cuales no pueden presentarse como atributos clase (parte derecha del

lienzo).

2. Atributos en el nuevo conjunto de datos.

3. Indica la clase atributo.

4. Para el caso de meta datos, estos se incluyen en el conjunto de datos, pero no se

consideran en el análisis de datos.

25

5. Aplicar el cambios al conjunto de datos y los envía al conjunto de datos al de

salida.

6. Carga un nuevo conjunto de datos de entrada.

7. Genera un reporte de resultados.

Figura 1. 8: Selección de atributos [20].

Goldenberry: Suite de componentes de Optimización y selección de variables para

Orange

Es un add-on para Orange, Goldenberry integra nuevas funcionalidades o componentes a

Orange, algunos de sus componentes están basados en EDAs (ver sección 1.6.2.) como

PBIL, cGA, UMDA y BMDA; en complemento se crearon también funciones de costo

cost function que son requeridas por los EDAs, componentes correspondientes a

algoritmos genéticos como Genetic Algorithm, Annealing, Mutation, Crossover;

26

además se creó un componente BlackBoxTester el cual permite hacer pruebas de los

EDAs creados en el framework [9,20]. A continuación en la Tabla 1.2 y la Tabla 1.3, la

lista de componentes que conforman Goldenberry 2.0 [5]:

Tabla 1. 2: Lista

de componentes

de Goldenberry

1.0 [5].

Optimization - EDA’s (Goldenberry 1.0)

Feature Subset and Dependences: Sirve para

Visualizar las respuestas de los algoritmos de

seleccion de variables.

Kernel Perceptron: Es el responsable de proveer un

kernel listo para ejecución.

cGA: Optimizador genetico compacto.

UMDA: Optimizador EDA univariado.

TILDA: Optimizador univariado basado

cGA y PBILc.

BMDA: Optimizador EDA bivariado.

SVM: Es un kernel basado en el SVM

Nativo de Orange.

PBILc: Optimizador de poblacion

univariado compacto

UMDAc: Optimizador univariado compacto

Wrapper Cost Function: Es un componente

de configuracion para asignar el número de

repeticiones de entrenamiento y prueba.

27

Optimización - GA’s (Goldenberry 2.0)

Cost Function Builder: Permite la

definición de la función para ser optimizada.

Solution Representation:

Es usado para definir la codificacion de las

soluciones candidatas en cromosomas, es decir

es un componente de mapeo.

Initial Population: Se usa para definir

estrategias para la generación de una

población inicial.

Genetic Algorithm: Es el componente

principal de ejecución de GA, tiene 6 interfaces

de entrada, además de una interface con opciones

de configuración.

Black Box Tester: Es usado para visualizar

y comparar resultados entre múltiples

ejecuciones de optimizadores.

Selection: Establece el operador de

seleccion, con dos criterios: roulette wheel y

stochastic tournament.

Mutation: Es similar al componnete

crossover pero se enfoca en la definición del

operador de mutación.

Crossover: Define la configuración para el

operador de recombinación.

Tabla 1. 3: Lista de componentes de Goldenberry 1.0 [5].

28

Figura 1. 9: Programación por componentes de Goldenberry en Orange [7].

29

1.5.7. Metodología de Minería de Datos CRISP

La metodología CRISP- DM fue creada en 1996 por tres grandes empresas de la joven e

inmadura industria de minería de datos, Daimler Chrisler (Daimler – Benz), SPSS (ISL) y

NCR. En esos tiempos la minería de datos aún se encontraba en crecimiento y en

desarrollo y todavía había cierta incertidumbre sobre si ya era aplicable a los procesos de

negocio. Después de unos años las empresas formaron un consorcio creando el acrónimo

CRISP-DM (´´CRoss-Industry Standard Process for Data Mining´´), lo cual fue

financiado por la comisión europea. La idea de CRISP-DM fue crear una herramienta

industrial con aplicación neutral que tuviera gran aplicación muy amplia en la industria

[2].

La elección de la metodología CRISP-DM para aplicación en este proyecto radica en que

es no propietaria, libremente distribuida y puede ser utilizada tanto para la industria como

por profesionales interesados en la metodología [2], además es uno de los procesos de

minería de datos más ampliamente usado en la industria [11]. El modelo de referencia

contiene una descripción rápida de todas las fases del proyecto de minería, sus respectivas

tareas y las relaciones entre ellas, aunque en este nivel no es posible identificar todas las

relaciones.

El ciclo de vida de un proyecto de minería de datos está compuesto de seis fases (ver

Figura 1.10). La secuencia de estas fases no es estrictamente la descrita, el flujo entre

diferentes fases es característico del modelo. La minería de datos no termina cuando una

solución se implementa, las lecciones aprendidas durante el proceso y la implementación

de la solución puede desencadenar nuevas o más específicas preguntas sobre el negocio.

A continuación se va a explicar brevemente cada una de las fases que componen la

metodología CRISP-DM:

Entendimiento del negocio (´´Business understanding´´)

Esta fase inicial consiste en comprender los objetivos y requerimientos del proyecto

desde el punto de vista del negocio, luego se convierte el conocimiento adquirido en la

definición del problema de minería de datos y en la creación de un plan preliminar para el

alcance de objetivos.

30

Figura 1. 10: Fases de CRISP-DM. Las flechas indican las más importantes y frecuentes

dependencias entre las clases. El circulo exterior representa la naturaleza cíclica de la

metodología de minería de datos, donde los algoritmos que se van a usar en el proyecto se

integran a la fase de modelo [19].

Entendimiento de los datos (´´ Data Understanding´´)

Es la fase donde se hace la recolección de los datos y un reconocimiento de los mismos,

se identifican problemas como la calidad de los datos, se buscan subconjuntos de datos

para formar hipótesis de información oculta.

Preparación de los datos (´´ Data Preparation´´)

Esta fase cubre todas las actividades encargadas de construir el conjunto de datos final, es

decir, el conjunto de datos que será trabajado en la fase de modelado. Las tareas de

preparación de datos pueden ser ejecutadas múltiples veces sin seguir un orden

especifico, ejemplos de tareas como selección de variables, transformación y filtrado de

datos, entre otras.

31

Modelamiento (´´Modeling´´)

En esta fase varias herramientas de modelado son seleccionadas y son calibradas según el

problema de minería de datos. Frecuentemente son aplicadas diversas técnicas para un

problema de minería de datos, donde cada técnica requiera una entrada de datos

específica lo que hace algunas veces recurrir nuevamente a la etapa de preparación de

datos.

Evaluación (´´Evaluation´´)

En esta etapa se ha construido un modelo o varios modelos que podrían tener gran calidad

desde el punto de vista de análisis de datos. Antes de seguir con la etapa de

implementación es importante revisar con detalle los modelos realizados y hacer una

revisión de los pasos ejecutados en la construcción del modelo para tener certeza de que

los modelos consiguen lograr los objetivos del negocio.

Implementación (´´Deployment’’)

La creación del modelo generalmente no es el fin del proyecto. El objetivo del modelado

es incrementar el conocimiento que tenemos sobre los datos, este conocimiento adquirido

debe ser organizado y presentado al cliente. La fase puede ser tan simple como la

generación de un informe o puede ser tan complicado como la creación de un nuevo

proceso de minería de datos.

1.5.8. Deserción Escolar

La Coalición Colombiana por el Derecho a la Educación, informó que Colombia es uno

de los países con más alto índice de deserción escolar, cerca del 50% de los jóvenes dejan

la educación secundaria [21].

La inseguridad, las drogas, las peleas estudiantes son otros factores influyentes para la

deserción escolar, el colegio Ofelia Uribe de Acosta se encuentra dentro de los 14 centros

educativos más inseguros que pertenecen a la localidad de Usme [22].

La deserción escolar en América Latina es una tragedia de la que se habla muy poco. No

solo enfrentamos el desafío de los alumnos que siguen dejando la escuela todos los años,

sino de los millones de adultos que están en su vida profesional sin estudios secundarios

http://www.eluniversal.com.co/cartagena/educacion/el-50-de-los-jovenes-en-colombia-deja-la-secundaria-121775

32

en una sociedad en la que cada vez es más difícil encontrar un empleo sin tener

formación.

A pesar de que esta tragedia sea acuciante para el futuro de nuestras sociedades, sabemos

poco sobre los jóvenes que dejan las escuelas. Existen escasos estudios profundos,

locales, sobre las causas y consecuencias de la deserción escolar. Sabemos que la

necesidad de ingresos, las situaciones familiares y la falta de una escuela de interés para

los jóvenes son de las principales causas del abandono, pero no tenemos mayores

precisiones estadísticas, ni políticas claras de cómo combatirla [23].

Convertir nuestra sociedad en una nación próspera y justa no parece ser tarea fácil. Se

requerirían de muchos ingredientes: la erradicación de la corrupción, el fin del conflicto,

la creación de nuevos empleos, planes para disminuir la pobreza y la compensación a las

víctimas del conflicto, entre otros.

Sin embargo, hay un ingrediente que no puede faltar. El factor decisivo para lograr el

utópico proyecto de una Colombia mejor es la educación. La educación promotora de

cultura y conocimiento es vital para lograr los habitantes ideales de la Colombia soñada:

ilustrados y cultos que piensen críticamente y que no permitan que las élites los utilicen

[24].

La preocupación por la educación se puede ver incluso en la Constitución Política de

Colombia de 1.991, en su Artículo 67 dice: “El Estado, la sociedad y la familia son

responsables de la educación, que será obligatoria entre los cinco y los quince años de

edad y que comprenderá como mínimo, un año de preescolar y nueve de educación

básica” [25].

1.6. Factibilidad

1.6.1. Técnica

Recurso Hardware: Computador portátil con especificaciones técnicas mínimas:

Procesador dual core de 1.5 GHZ y Memoria RAM de 2 GB.

Recurso Software: Orange Canvas Herramienta libre.

Recurso Humano:

- Estudiante: Estudiante de Tecnología en sistematización de datos, en la

Universidad Distrital Francisco José de Caldas; con conocimiento en el uso de

lenguajes de programación.

- Docente: Ingeniero de sistemas con maestría en Ingeniería de sistemas.

Experiencia en el uso e implementación de algoritmos de aprendizaje

computacional.

33

1.6.2. Operativa

El proyecto se realiza buscando beneficios no solo personales, locales y nacionales,

puesto que el hecho de buscar soluciones para evitar que los jóvenes y niños no deserten

del colegio beneficia en todos los ámbitos a Colombia. Desde lo económico hasta lo

cultural.

En esta actividad se procedió a hablar con el Rector del colegio Ofelia Uribe de Acosta, el

señor Luis Mario Lanza, el cual indico las cifras y la problemática que presenta la

deserción escolar en los dos últimos años consecutivos dentro de la institución.

Con esta información se busca seleccionar las características más relevantes que rodean

esta problemática para dar soluciones, a las diferentes características que rodean la

deserción escolar dentro del plantel y así disminuir la cantidad que se tiene actualmente.

1.6.3. Económica

Recurso Descripción Cantidad Costo

Hardware Computador portátil con especificaciones técnicas mínimas: -Procesador dual core de 1.5 GHZ. -Memoria RAM de 2 GB

1 $ 1.500.000

Software Orange Canvas Herramienta libre

1 $ 0,00

Humano Estudiante 1 $20.000 hora 500x20.000 Total: $10´000.000

Profesor 1 $30.000 hora 32x30.000 Total: $96.000

Otros • Papelería, • Fotocopias, • Transporte, • Medios magnéticos de

almacenamiento • Acceso a internet • Bibliografía

$300.000

Total $ 10´896.000 Tabla 1. 4: Factibilidad Económica.

34

1.6.4. Legal

En cuanto a aspectos legales los equipos utilizados cuentan con las licencias de Microsoft

Windows necesarias, Las demás herramientas a utilizar son de libre distribución por lo

tanto no necesitarían algún licenciamiento al ser software libre.

Ley 11723: es una ley compuesta por 89 artículos, sancionada en 1933 (y todavía

vigente), conocida como "Ley de Propiedad Intelectual" o también como "Ley de

Propiedad Científica, Literaria y Artística". Esta ley regula todo lo referente a derecho de

propiedad de una obra artística, científica o literaria, derechos de coautor, enajenación o

cesión de una obra, licencias, etc. Además, establece sanciones tanto pecuniarias (multa)

como privativas de la libertad (prisión) a quienes violen sus normas. Su última reforma

data de Noviembre de 1998, cuando por Ley 25036 se le introdujeron modificaciones

referidas al software, para darle fin a las discusiones doctrinarias y jurisprudenciales

sobre la cuestión de si el software estaba o no bajo el amparo de esta ley. Ahora establece

expresamente en su Art. 1 que "... las obras científicas, literarias y artísticas comprenden

los escritos de toda naturaleza y extensión, entre ellos los programas de computación

fuente y objeto; las compilaciones de datos o de otros materiales, ..." y en su art. 55 bis

que "La explotación de la propiedad intelectual sobre los programas de computación

incluirá entre otras formas los contratos de licencia para su uso o reproducción".

Proyecto de ley sobre Software Libre: es un proyecto presentado en Marzo de 2001 por

Marcelo Luis Dragan, Diputado Nacional por la provincia de Tierra del Fuego, del

Partido Acción por la República. Originalmente lleva el nombre de Utilización de

Software Libre por el Estado Nacional", y establece la obligación de usar prioritariamente

Software Libre en todas las dependencias de la Administración Publica Nacional, salvo

excepciones. Entre los aspectos que motivaron el proyecto, se destacan el económico (por

el costo de las licencias y por la libertad de copiar que otorga el Software Libre), el moral

(es conocido que en todos los ámbitos de la Administración Publica se utiliza Software

Ilegal, ya sea por cuestiones de costos, negligencia, etc., lo cual coloca al Estado como

uno de los principales infractores a la Ley 11723), el cultural, el educativo, el de

seguridad nacional, etc. Actualmente este proyecto se encuentra en estudio en la comisión

de Legislación General y Comunicación.

1.7. Diagrama de Actividades

Figura 1. 11: Diagrama de Actividades.

http://www.monografias.com/trabajos28/propiedad-intelectual-comentarios-tendencias-recientes/propiedad-intelectual-comentarios-tendencias-recientes.shtml

http://www.monografias.com/trabajos28/derechos-propiedad-poder-mercado/derechos-propiedad-poder-mercado.shtml

http://www.monografias.com/trabajos28/derechos-propiedad-poder-mercado/derechos-propiedad-poder-mercado.shtml

http://www.monografias.com/trabajos29/concepto-enajenacion/concepto-enajenacion.shtml

http://www.monografias.com/trabajos4/leyes/leyes.shtml

http://www.monografias.com/trabajos12/derjuic/derjuic.shtml

http://www.monografias.com/trabajos36/naturaleza/naturaleza.shtml

http://www.monografias.com/trabajos14/propiedadmateriales/propiedadmateriales.shtml

http://www.monografias.com/trabajos6/cont/cont.shtml

http://www.monografias.com/trabajos/reproduccion/reproduccion.shtml

http://www.monografias.com/trabajos12/pmbok/pmbok.shtml

http://www.monografias.com/trabajos11/tierreco/tierreco.shtml

http://www.monografias.com/trabajos35/categoria-accion/categoria-accion.shtml

http://www.monografias.com/trabajos12/elorigest/elorigest.shtml

http://www.monografias.com/trabajos36/administracion-y-gerencia/administracion-y-gerencia.shtml

http://www.monografias.com/trabajos15/etica-axiologia/etica-axiologia.shtml

http://www.monografias.com/Administracion_y_Finanzas/index.shtml

http://www.monografias.com/trabajos12/elorigest/elorigest.shtml

http://www.monografias.com/trabajos12/fundteo/fundteo.shtml

35

2. ESTUDIO Y SELECCIÓN DEL ALGORITMO

wKIERA RESPECTO A OTROS ALGORITMOS

En este capítulo de selección del Algoritmo, se va a comparar y a estudiar los elementos

que componen cada uno de los algoritmos a evaluar, y se definirá cual es el más correcto

para darle uso en la determinación de las variables de deserción escolar en la base de

datos del Colegio Ofelia Uribe de Acosta.

Dentro de la plataforma de Orange se encuentra un menú desplegable en la parte

izquierda de la ventana principal, en ella se encuentran las clases y la clasificación de los

Widget que son los componentes encargados cada uno de una tarea en particular para un

problema de minería de datos.

Como se muestra en la figura 2.1, las clases están distribuidas en Data, Visualize,

Classify, Regression, Evaluate, Unsupervised, Associate, estas clases con cada uno de sus

componentes pertenecen a Orange, quien en su distribución original no ofrecía

componentes para algoritmos de optimización; recientemente se desarrolló una extensión

para Algoritmos de Estimación de Distribuciones conocidos como EDA.

A continuación de las clases de Orange, se encuentran dos clases más Learners y

Optimization (ver figura 2.1), estas pertenecen a un nuevo desarrollo llamado

Goldenberry, este es una caja de herramientas de Orange que contiene los componentes

visuales de EDA para la optimización basada en búsqueda estocástica. Su objetivo

principal es proporcionar un entorno de trabajo fácil de usar para los investigadores y

profesionales, basándose en el lienzo versátil de Orange y la reutilización de gran alcance

basado en componentes de desarrollo de software. [10]

Figura 2. 1: Grupo de herramientas de minería de datos Orange. Plataforma Principal de

Orange.

36

Ahora se utilizaran los widget necesarios para selección de variables, algunos de ellos se

visualizan en la figura 2.2

Figura 2. 2: Algunos componentes de programación visual Orange [20].

Ya identificados los grupos de herramientas, será necesario explorar componentes

visuales que cada una de las clases contiene; al decir explorar se refiere a identificar cada

componente visual; su función, variables, sus entradas/salidas y su interacción con los

demás componentes.

2.1. Selección de Widget para Algoritmo EDA

El primer factor a considerar es que los datos para ser trabajados en Orange Goldenberry

como requisito básico deben estar estructurados en forma de tabla, donde las columnas

representan variables y las filas representan muestras; con lo anterior se quiere decir que

la recolección de los datos debe hacerse estructuradamente en forma de tabla (ver figura

2.6).

37

Figura 2. 3: Salida de la función Kernel Builder. Plataforma Principal de Orange.

Figura 2. 4: Función que se usa para el algoritmo. Plataforma Principal de Orange.

Figura 2. 5: Variables componente visual Kernel perceptrón. Plataforma Principal de

Orange.

38

Figura 2. 6: Entradas y salidas del componente visual Data Sampler. Plataforma

Principal de Orange.

Los datos son cargados a través de un widget llamado File (ver figura 2.7), este es el

reproductor de archivos; es decir lee el archivo de datos de entrada (tabla de datos con

instancias de datos) y envía los datos que figuran en su canal de salida. Este adicional

mantiene un historial de los archivos abiertos recientemente. El Widget lee los datos de

los archivos delimitados por tabuladores o separados por comas simples.

Figura 2. 7: Salida del componente visual File. Plataforma Principal de Orange.

La función de envoltura es una función de costo multiobjetivo para evaluar el número

de variables y su buena calidad para producir un predictor más exacto. Este componente

actúa como intermediario entre el algoritmo optimizador y el aprendizaje computacional.

39

Figura 2. 8: Entradas y salidas del componente visual Wrapper Cost Function.

Plataforma Principal de Orange.

ALGORITMO TILDA

(Tiny Incremental Learning Density Estimation Algorithm) es una mezcla de cGAc

(compact Genetic Algoritm) y PBILc (continuous-domain Population Based Incremental

Learning), la idea principal del algoritmo es modelar con una distribución conjunta

gaussiana multivariante (ver ecuación (2.1)) donde sus parámetros ( ) se

estiman es un marco compacto [9].

( ∑) ∏ ( ) (2.1)

Se asume que se tiene una población P de candidatos (xi, x2) ~ ( ∑) donde es

un torneo de dos caminos (dos candidatos de P son aleatoriamente elegidos sin

reemplazo, y el ganador substituye el perdedor). Si se toma W como ganadores y L como

perdedores, la nueva población es ( ) . Luego, la estimación promedio de

máxima verosimilitud de la nueva población, que es = ( ) , puede ser

expresado en forma vectorizada como:

∑ (2.2)

Por lo tanto, con una fracción de cada ganador del torneo, el parámetro del modelo de

probabilidad puede actualizarse incrementalmente, según la fórmula de la ecuación

siguiente:

(2.3)

40

Ahora, la misma lógica se puede aplicar a la estimación de la varianza ∑ = ( , …,

)

en una forma vectorizada:

∑ (

)

. (2.4)

Figura 2. 9: Entrada y salida del componente visual del algoritmo TILDA. Plataforma

principal de Orange.

ALGORITMO PBIL

Es el componente que representa el algoritmo optimizador PBIL, junto con los demás

componentes mencionados, se define como Población incrementada basada en el

algoritmo, que asume que las variables se distribuyen normalmente de forma

independiente. (Ver página 14). En la Figura 2.10 y la Tabla 2.1, se observa

detalladamente información acerca de este algoritmo.

Figura 2. 10: Entrada y salida del componente visual del algoritmo PBIL. Plataforma


41

Algoritmo PBIL

Obtener un vector inicial de probabilidades ( )

while no convergencia do

begin

Usando ( ) obtener individuos:

Evaluar y ordenar

Seleccionar los ( ) mejores individuos:

Actualizar el vector de probabilidades ( ) ( ) ( ))

for i=1, … do

( ) = ( ) ( )

∑

end

Fin algoritmo

Tabla 2. 1: Pseudo código del algoritmo PBIL [15].

El algoritmo funciona de la siguiente manera. En cada generación, usando el vector de

probabilidades, ( ) , se obtienen individuos. Cada uno de estos individuos es

evaluado y los mejores ( ) son seleccionados. Estos individuos seleccionados

son usados para actualizar el vector de probabilidades, nótese que PBIL tan solo puede

verse como una instancia de los EDAs en el caso en que . En tal caso PBIL

coincida con UMDA.

ALGORITMO UMDA

Es el componente que representa el algoritmo optimizador UMDA, junto con los demás

componentes mencionados representa el algoritmo wKIERA (Ver página 14). Tal y como

puede verse en el pseudocódigo de la Tabla 2.2, el modelo probabilístico utilizado por el

algoritmo UMDA (Univariate Marginal Distribution Algorithm) es el más simple posible.

En concreto, en cada generación la distribución de probabilidad conjunta, ( ), que sirve

para estimar el comportamiento de los individuos seleccionados, se factoriza como un

producto de distribuciones marginales univariantes e independientes. Es decir:

( ) ( | ) ∏ ( )

(2.5)

42

Algoritmo UMDA

Generar M individuos al azar

For hasta M

Seleccionar individuos

For hasta

For hasta

( ) ( |

)

Fin For

Fin For

= Muestra M individuos

Fin For

Fin UMDA

Tabla 2. 2: Pseudo código del algoritmo UMDA [15].

Cada distribución marginal se estima a partir de las frecuencias marginales:

( ) ∑ ( |

)

(2.6)

Donde

( |

) {

(2.7)

Figura 2. 11: Entrada y salida del componente visual del algoritmo UMDA. Plataforma


43

2.2. Comparación y Selección del Algoritmo a usar para la Deserción Escolar

En este capítulo se hizo descripción del experimento y los resultados obtenidos a partir

del uso de los diferentes algoritmos buscando obtener y seleccionar el más adecuado para

usarlo en la selección de variables de deserción escolar en la base de datos del Colegio

Ofelia Uribe de Acosta.

En la Tabla 2.3, se describen los datos que se usaron en todos los algoritmos, para realizar

la respectiva comparación.

Experimentos Registros Variables

Prueba 1 100 6

Prueba 2 500 8

Prueba 3 1000 10

Tabla 2. 3: Conjunto de Datos de Prueba.

A continuación el modelo que se va a usar en todas las pruebas para la selección del

Algoritmo.

Figura 2. 12: Representación gráfica de componentes visuales en Orange utilizados para

la experimentación en los conjuntos de prueba. Plataforma Principal de Orange.

Prueba 1

Usando el modelo de la figura 2.12, se mostraran los resultados obtenidos en la Prueba 1

sobre el conjunto de datos (ver tabla 2.3), en la tabla 2.4 se encuentra la configuración de

los componentes visuales de la prueba.

44

Configuración Prueba 1

Componente Visual Descripción

Kernel Builder GaussianKernel, con gamma=1.0

Kernel Perceptron Learning Rage= 1.0 y Epochs= 1.0

Wrapper Cost Function Training Folds= 2, Test Folds= 10, con Normalizedata=

Activado

UMDA, TILDA, PBIL El número de candidatos se configura por 4 veces el

número de variables relevantes (ver Rodríguez [7])

#Candidates = 24 y el número de evaluaciones no se

limita se asigna un valor grande para que el algoritmo

itere las veces que sea necesario.

Black Box Tester 20 repeticiones.

Tabla 2. 4: Configuración de componentes visuales realizada para la Prueba 1.

En la figura 2.13 se muestra los resultados obtenidos en el Black Box Tester, en el cual se

muestra Costo máximo, el costo promedio, Evaluaciones realizadas promedio y el tiempo

promedio de cada algoritmo en ejecución.


Orange.

Prueba 2




45






Activado












Orange.

Prueba 3




46






Activado












Orange.

47

2.3. Discusión de Resultados

En la tabla 2.7 se puede observar la comparación del rendimiento de los tres algoritmos

trabajados con datos sintéticos durante la selección del más adecuado para usarlo en la

base de datos reales del Colegio Ofelia Uribe de Acosta. Donde se observa que el

algoritmo UMDA fue el que presento mejor rendimiento durante las pruebas.

Experimentos

TILDA PBIL UMDA

# Eval Tiempo(s) # Eval Tiempo(s) # Eval Tiempo(s)

Prueba 1 103 0,2594 97 0,1652 98,2 0,1794

Prueba 2 103 0.3058 129 0.2879 129 0.2472

Prueba 3 103 0,3396 121 0,3173 121 0.2777

Tabla 2. 7: # Eval= Numero promedio de evaluaciones del algoritmo. Rendimiento de

los algoritmos TILDA, PBIL y UMDA, en los tres conjuntos de pruebas.

Debido a que el algoritmo UMDA, realizo más evaluaciones respecto a los otros dos

algoritmos, es decir; fue el que presento mejor rendimiento en un tiempo menor se

concluye que el algoritmo más apropiado para usar en el caso de estudio del Colegio

Ofelia Uribe de Acosta, es el algoritmo wKIERA (ver sección 1.6.3).

48

3. SELECCIÓN DE VARIABLES DEL CONJUNTO DE

DATOS PARA DETERMINAR DESERCIÓN

ESCOLAR

Este trabajo tiene dentro de sus objetivos encontrar las variables que influyen la deserción

escolar de los estudiantes del Colegio Ofelia Uribe de Acosta. Pero ¿Cómo se puede

interpretar la deserción escolar dentro del conjunto de datos a trabajar? La deserción son

las variables que contienen notas o información personal y económica de cada

estudiante almacenada en la base de datos, dentro de estas variables se seleccionara una

que agrupa el acumulado final de las cuatro notas promedio de cada periodo [12].

3.1. Discretización de Variables

El algoritmo wKIERA en el entorno Orange- Goldenberry clasifica las muestras basado

de una sola variable llamada Clase; esta solo puede tener dos valores y ser de tipo

discreto; con lo dicho anteriormente para hacer la tarea de clasificación de la Base de

datos del Colegio Ofelia Uribe de Acosta se hará la transformación de la variable Clase.

Tabla de Valores Discretos

Superior

Alto

Básico

Bajo

Tabla 3. 1: Los 4 grupos de variables discretas.

En la Tabla 3.1 se observan las 4 clases: Superior, Alto, Básico, Bajo, que tenemos en la

base de datos, pero esta información aun presenta complicaciones para su aplicación en el

aplicativo porque debe tener dos clases discretas necesarias para el algoritmo y se tienen

cuatro; para resolver este problema se realizan cuatro experimentos diferentes para así

identificar las variables relevantes de las 4 clases:

49

Clases

Discretas

Experimento 1

Experimento 2

Experimento 3

Experimento 4

Superior

Demás Datos

Demás Datos

Demás Datos

Superior

Alto Alto

Demás Datos

Básico Básico

Demás

Datos Bajo Bajo Demás Datos

Tabla 3. 2: Experimentos a realizar por variable clase para identificación de variables de

deserción escolar Base de datos Colegio Ofelia Uribe de Acosta.

Con esto se tiene 4 experimentos posibles, para la variable clase escogida, llamada Nivel.

3.2. Descripción de datos

Los datos provistos por el Colegio Ofelia Uribe de Acosta se encuentran en formato de

Microsoft Excel 2010. Para el desarrollo de este trabajo se seleccionó la información final

del año 2014.

Más en detalle los datos corresponden a 2.703 registros o muestras, los cuales fueron

revisados, cruzados y filtrados para eliminación de inconsistencias, lo cual dejo una

muestra para trabajar de 2.575 registros; analizando los datos obtenemos la tabla 3.3

Tabla 3. 3: Diccionario de datos de las variables escogidas para el estudio de deserción

escolar del Colegio Ofelia Uribe de Acosta. VP= Valores Posibles.

Grupo Variable Tipo/Rango Descripción

Estudiante

ESTADO

SEDE

JORNADA

GRADO

GENERO

EDAD

VP= 2

VP= 2

VP= 2

VP= 12 [ 0 – 11 ]

VP= 2

VP= 16 [ 4 – 19 ]

Estado de matricula

Sede a la cual pertenece

Jornada del estudiante

Grado que está cursando

Genero del estudiante

Edad del estudiante

Económico

ESTRATO

VP=2 [ 0,1 ]

Estrato Social

Tema

NIVEL

VP= 4 [SUPERIOR,ALTO,

BASICO,BAJO]

Nivel Final de cada Estudiante

50

3.3. Experimentación

En esta sección se describirán los pasos que se realizaron para la experimentación, este

proceso se llevará a cabo usando iteraciones las cuales serán guiadas por el proceso

CRISP-DM de minería de datos.

3.3.1. Iteración 1

Comprensión del Negocio 1

El objetivo es encontrar las variables que determinan la deserción escolar en el Colegio

Ofelia Uribe de Acosta en el año 2014 usando el Algoritmo wKIERA.

En cuanto al desempeño del Algoritmo en la etapa de evaluación se determinará si las

variables encontradas por el algoritmo son las que mejor analizan y dan a conocer las

variables importantes de la deserción escolar.

Comprensión de los Datos 1

Se tienen 2.575 registros con 33 variables más una variable tema, llamada NIVEL.

Preparación de los datos 1

La preparación de los datos se ha iniciado como se indicó en la sección anterior de

discretización (ver sección 3.1), donde las cuatro variables discretas fueron reducidas a

dos variables discretas para el correcto funcionamiento del algoritmo.

La variable NIVEL será la variable clase, es decir; se tiene un archivo de 33 variables

más una variable correspondiente a la variable clase y por tanto a los datos se les adicionó

una columna haciendo distinción de dos clases; la clase ALTO y la clase DEMAS

DATOS como se observa en el Experimento 3 (ver tabla 3.2). Para este experimento se

creo un archivo con las características descritas anteriormente y con las 2.575 muestras

validas (ver tabla 3.4).

Archivos Iteración 1

Nombre Filtros V. Clase Clase # Variables # Muestras

Archivo # 1

Datos

Validos

NIVEL

ALTO

33

2.575

Tabla 3. 4: Descripción archivos de trabajo iteración 1.

51

Modelado 1

Se tomo el conjunto de datos el cual se clasificara utilizando el algoritmo wKIERA (ver

Tabla 3.5). El modelo por componentes se puede ver en la Figura 3.2, y será el que se

usara en las cuatro Iteraciones.

Figura 3. 1: Modelado por Componentes de la Iteración 1.

Evaluación 1

El algoritmo wKIERA, arrojo 6 variables que determinarían la deserción escolar, como se

muestra en la Tabla 3.6

Configuración Iteración 1

Componente Visual

Descripción

FILE Un archivo de 2.575 registros con 33 variables más la variable

Tema NIVEL (ver tabla 3.4).

DATA SAMPLER (2) Se escogieron inicialmente 773 instancias, donde se seleccionó

el 30% para entrenamiento y el 70% de los datos restantes para

pruebas.

Kernel Builder El método kernel se trabajó con GaussianKernel en gamma=1.0

Wrapper Cost

Function

Se seleccionó Training Folds= 5, Test Folds=5, con

Normalizedata= Activado

UMDA El número de candidatos se configura con #Candidates = 10 y

el número de evaluaciones se limita Evaluations = 40.

Tabla 3. 5: Configuración de componentes visuales realizada para la Iteración 1.

52

Variables Determinantes de Iteración 1

Sede

G1= Grado Primero

G4= Grado Cuarto

G8= Grado Octavo

E10= 13 Años

Nivel

Tabla 3. 6: Variables halladas en la Iteración 1.

3.3.2. Iteración 2


En la anterior Iteración se encontraron 6 variables relevantes, por lo cual en esta iteración

se trabajó sobre un conjunto de datos con la variable clase NIVEL diferente a la anterior.






más una variable correspondiente a la variable clase y por tanto a los datos se les

adicionará una columna haciendo distinción de dos clases; la clase BAJO y la clase

DEMAS DATOS como se observa en el Experimento 1 (ver tabla 3.2). Para este

experimento se creó un archivo con las características descritas anteriormente y con las

2.575 muestras validas (ver tabla 3.7).



Archivo # 2

Datos

Validos

NIVEL

BAJO

33

2.575

Tabla 3. 7: Descripción archivos de trabajo Iteración 2.

53

Evaluación 2




G7= Grado Séptimo

G11= Grado Once

Genero

E6= 9 Años

E8= 11 Años


3.3.3. Iteración 3


En la Iteración 2 se encontraron 5 variables relevantes, una variable menos que en la

Iteración 1, y ninguna de las variables ha coincidido. Al igual que en la Iteración 2, en la

Iteración 3 se trabajara sobre un conjunto de datos con la variable clase NIVEL diferente

a la anterior.







adicionara una columna haciendo distinción de dos clases; la clase BASICO y la clase






Archivo # 3

Datos

Validos

NIVEL

BASICO

33

2.575


54

Evaluación 3




G0= Grado Transición

E3= 6 Años

E14= 17 Años

E15= 18 Años


3.3.4. Iteración 4


En la Iteración 2 se encontraron 5 variables relevantes, una variable menos que en la

Iteración 1, en la Iteración 3 se encontraron solo 4 variables, y ninguna de las variables ha

coincidido. Al igual que en la Iteración 2 y 3 en la Iteración 4 se trabajará sobre un

conjunto de datos con la variable clase NIVEL diferente a la anterior.







adicionara una columna haciendo distinción de dos clases; la clase SUPERIOR y la clase






Archivo # 4

Datos

Validos

NIVEL

SUPERIOR

33

2.575


55

Evaluación 4

El algoritmo wKIERA, arrojó 9 variables que determinarían la deserción escolar, como

se muestra en la Tabla 3.12


Jornada

G7= Grado Séptimo

Estrato

E4= 7 Años

E5= 8 Años

E9= 12 Años E14= 17 Años

E16= 19 Años

Nivel


3.4. Discusión de Resultados Colegio Ofelia Uribe de Acosta

Esta experimentación dio como tendencia, en su resultado que la variable NIVEL, E14

(17 años), G7 (grado séptimo), son las mejores candidatas para calificar el conjunto de

variables del Colegio Ofelia Uribe de Acosta. Al asociar estas variables daría una

conclusión muy importante, el G7 es uno de los niveles académicos en el cual más

estudiantes desertan, y los jóvenes entre 17 y 19 años (E14 y E16) son quienes toman la

decisión de abandonar el colegio.

En cuanto a la variable NIVEL, que es la variable clase, confirmo la teoría que los

estudiantes abandonan el colegio debido al bajo rendimiento académico [12], como se

evidencia en las Iteraciones 1 y 4, lo hallado en estas Iteraciones es que el NIVEL ALTO

y el NIVEL SUPERIOR son las variables o componentes que mejor interpretan la

deserción escolar en esta institución.

56

4. CONJUNTO DE LIBRERÍAS DE ORANGE PARA LA

SELECCIÓN DE VARIABLES

En la plataforma de Orange, los componentes de Goldenberry se entrelazan de manera

visual, permitiendo personalizar el algoritmo a las necesidades particulares del usuario,

ajustar los parámetros de ejecución y visualizar los resultados de una manera gráfica y

entendible. Alternativamente Goldenberry también ofrece la posibilidad de configurar los

programas a través de una interfaz de comandos o scripts.

Los componentes de software en Orange se denominan Widget y son los encargados de

procesar las entradas que reciben a través de interfaces de requerimientos y generar los

resultados del procesamiento mediante interfaces de provisión. Estas interfaces pueden

alambrarse para construir programas con un enfoque similar al de los dispositivos

electrónicos que se construyen mediante el acoplamiento de elementos prefabricados.

Orange tiene una arquitectura multi-capa apropiada para diferentes tipos de usuarios,

desde aquellos que no tienen conocimientos de programación, mediante un lienzo gráfico

(pizarra) que permite el alambrado visual de componentes, hasta para usuarios

experimentados en programación, ofreciendo una interfaz para scripts de comandos.

Posee una librería de objetos y rutinas en C++ que incluyen una gran variedad de

algoritmos estándares para minería de datos que permiten rápidamente desarrollar

prototipos de esquemas de experimentación y análisis de datos; adicionalmente cuenta

con una colección de módulos basados en PYTHON [15] que actúan como núcleo del

sistema.

Goldenberry consiste de un conjunto de componentes de software para optimización sin

restricciones basados en algoritmos, incluye componentes utilitarios para la generación de

la función de costo y visualizar los resultados. Cada componente visual de Goldenberry

(widget) puede ser arrastrado a la pizarra de Orange y ser alambrado con otros

componentes a través de sus interfaces de provisión y requerimiento para completar una

tarea de optimización a través de algoritmos. Los Widget son unidades computacionales

independientes, representan el consumo y provisión de servicios encapsulados en cada

Widget.

De manera intuitiva, el paradigma de programación por componente se asemeja a la

construcción de sistemas de circuitos de hardware, en los cuales el usuario inicia

alambrando y configurando las unidades de hardware que hacen parte del circuito antes

de encender y utilizar el dispositivo final.

Dentro de los requerimientos básicos para el funcionamiento de Goldenberry aparece la

instalación de la última versión de Python en este caso Python 2.7., dentro de este

encuentra la Librería para Python numpy 1.5., numpy es el paquete fundamental para la

computación científica con Python, además de sus usos científicos; numpy también puede

ser utilizado como un contenedor multi-dimensional eficiente de los datos genéricos.

Esto permite integrar sin problemas Numpy con una variedad de bases de datos.

57

Numpy es el encargado de añadir toda la capacidad matemática y vectorial a Python

haciendo posible operar con cualquier dato numérico. Incorpora operaciones tan básicas

como la suma o la multiplicación u otras mucho más complejas como la transformada de

Fourier o el álgebra lineal. Además incorpora herramientas que nos permiten incorporar

código fuente de otros lenguajes de programación como C/C++ o Fortran lo que

incrementa notablemente su compatibilidad e implementación. En la figura 4.1 se puede

observar un ejemplo con el comando “loadtxt” que permite cargar los datos contenidos en

un archivo de texto.

>>> import numpy as np # Importamos numpy como el alias np

# Cargamos los datos de archivo.txt en datos. En este caso el

delimitador es la coma.

>>> datos = numpy.loadtxt('C:\ruta\a\tu\archivo.txt', delimiter =

',')

Figura 4. 1: Ejemplo carga de datos de un archivo .txt [15].

Otra librería indispensable para el correcto funcionamiento de los widget de Orange y

Goldenberry dentro de la pizarra es: sciPy 0.11, esta es un conjunto de paquetes

donde cada uno de ellos ataca un problema distinto dentro de la computación científica y

el análisis numérico. Algunos de los paquetes que incluye, son:

o sciPy.integrate: Proporciona diferentes funciones para resolver

problemas de integración numérica.

o sciPy.linalg: Proporciona funciones para resolver problemas de algebra

lineal.

o sciPy.optimize: Se usa para problemas de optimización y minimización.

o sciPy.signal: Se usa para el análisis y procesamiento de señales.

o sciPy.sparse: Se usa para matrices dispersas y solucionadores de sistemas

lineales dispersos.

o sciPy.stats: Se usa para el análisis de estadística y probabilidades.

Una de las librerías más importantes que se usó dentro del desarrollo de este trabajo es

scikit-learn, es una librería especializada en algoritmos para data Mining

(Minería de Datos) y machine learning (Aprendizaje Automático). Algunos de los

problemas que se pueden resolver usando las herramientas de scikit-learn son:

o Clasificaciones: Identifica las categorías en que cada observación del conjunto de

datos pertenece.

o Regresiones: Predice el valor continuo para cada nuevo ejemplo.

o Agrupaciones: Agrupación automática de objetos similares en un conjunto.

http://scikit-learn.org/stable/modules/clustering.html#clustering

58

o Reducción de dimensiones: Reducir el número de variables aleatorias a

considerar.

o Selección de Modelos: Comparar, validar y elegir parámetros y modelos.

o Pre procesamiento: Extracción de características a analizar y normalización de

datos.

Para formar el algoritmo wKIERA, se seleccionó el Widget Kernel Builder (ver figura

4.2), dentro de este se seleccionó la función GaussianKernel, la cual se usó dentro del

desarrollo de este proyecto (ver sección 1.6.1), y trabaja con un script, que se puede

observar en la figura 4.3.

Figura 4. 2: Configuración del Widget Kernel Builder. Plataforma Principal de Orange.

____________________________________

def GaussianKernel(x, y): gamma = 1.0 val = (x-y) return np.exp(-val.dot(val.T)/gamma)

____________________________________________ def my_kernel_function(x, y): return np.sum(x*y) ____________________________________

Figura 4. 3: Script de la function Gaussian Kernel. Plataforma Principal de Orange.

http://scikit-learn.org/stable/modules/decomposition.html#decompositions

http://scikit-learn.org/stable/model_selection.html#model-selection

http://scikit-learn.org/stable/modules/preprocessing.html#preprocessing

59

5. ANÁLISIS DE PRUEBAS Y RESULTADOS

En el desarrollo de un programa computacional resulta necesario definir criterios para

medir su rendimiento o comportamiento. Estos criterios se centran principalmente en su

simplicidad y en el uso eficiente de los recursos.

Respecto al uso eficiente de los recursos, éste suele medirse en función de dos

parámetros: el espacio, es decir, memoria que utiliza, y el tiempo, lo que tarda en

ejecutarse. Ambos representan los costes que supone encontrar la solución al problema

planteado mediante un algoritmo. Dichos parámetros van a servir además para comparar

algoritmos entre sí, permitiendo determinar el más adecuado de entre varios que

solucionan un mismo problema.

En el análisis de algoritmos, el tiempo empleado por el algoritmo se mide en pasos, el

coste depende del tamaño de los datos y para evaluar este coste se dan tres posibles casos;

El caso promedio (la situación inicial de los datos no sigue ningún patrón preestablecido

que aporte ventajas o desventajas, El caso Mejor ( se refiere a la situación inicial de los

datos que genera una ejecución del algoritmo con una menor complejidad computacional)

y El caso Peor (se refiere a la situación inicial de los datos que genera una ejecución del

algoritmo con una complejidad computacional mayor). Para evaluar el algoritmo UMDA

respecto a un Árbol de decisión, en cuanto a la complejidad que cada uno tiene se medirá

teniendo en cuenta el caso Peor.

Algoritmo UMDA

Generar M individuos al azar

For hasta M

Seleccionar individuos

For hasta

For hasta

( ) ( |

)

Fin For

Fin For


Fin For

Fin UMDA

Figura 5. 1: Pseudo código del algoritmo UMDA [15].

60

Algoritmo Costo Número de Veces

Algoritmo UMDA

Generar M individuos al azar 1

For hasta M

Seleccionar

individuos

For hasta

∑

For hasta

∑∑

( ) ( |

)

∑∑( )

Fin For

Fin For


Fin For

Fin UMDA

Tabla 5. 1: Algoritmo UMDA.

Para calcular el ( ) se suman los productos de costo y el número de veces para obtener

[18]:

( )= + ( )+ + ∑ + ∑ ∑

+

∑ ∑ ( )

+

Definimos , , reemplazando los valores obtenemos:

( )= + ( )+ + ∑ ( ) + ∑ ∑ ( )

+

∑ ∑ ( )

+

61

( )= + ( )+ + ( ) + + ( ) +

( )= + + + + + + +

Sustituyendo los valores de MnN:

( )= + + + + ( ) + ( )( )( ) + ( ) ( ) +

( )= + + + + +

+

+

( ) ( ) ( - )

( )

Así, el tiempo de ejecución para el peor caso puede ser expresado como:

En notación asintótica este algoritmo para el peor caso, ( ).

Algoritmo para generar un Árbol de Decisión.

Para cada (valor_atributo (nodo)

p = generar_nueva_particion_de_datos (nodo, valor_atributo (nodo))

desorden = desorden (p)

SI (desorden == verdadero)

a=atributo_menor_desorden (p)

Adicionar _ hijo (Árbol, a, p)

GENERAR_ARBOL (Arbol, a)

SINO Crear_hoja (Árbol,nodo, valor_clase (p))

Fin GENERAR_ARBOL

Figura 5. 2: Pseudo código de un Árbol de Decisión.

62

Algoritmo Costo Número de Veces

Algoritmo Generar Arbol (Arbol, Nodo)

Para cada (valor_atributo (nodo) p = generar_nueva_particion_de_datos (nodo, valor_atributo (nodo))

desorden = desorden (p)

SI (desorden == verdadero)

∑

a=atributo_menor_desorden (p)

∑( )

Adicionar _ hijo (Árbol, a, p) C6 ∑( )

GENERAR_ARBOL (Arbol, a) C7

∑( )

SINO Crear_hoja (Árbol,nodo, valor_clase (p))

C8 n-1

Fin Para cada C9

∑

Fin GENERAR_ARBOL

Tabla 5. 2: Árbol de Decisión.

( ) ( ) ( ) ∑ ∑ ( )

∑ ( ) ∑ ( )

( ) ∑

Definimos , reemplazando los valores obtenemos:

( ) ( ) ( ) ∑ ∑ ( )

∑ ( ) ∑ ( )

( ) ∑

( ) ( ) ( ) ( ) ( ) ( )

( ) ( ) ( )

( )

Agrupando términos:

( ) ( ) ( )

Así, el tiempo de ejecución para el peor caso puede ser expresado como:

63

La Complejidad Computacional en el peor caso construye un árbol completo en el cual

cada camino en el árbol prueba cada característica, En cada nivel, i, en el árbol, se debe

examinar las m-i características que quedan para cada instancia en ese nivel para calcular

las ganancias de información.

∑

( )

En la practica un árbol es raramente completo (número de hojas es ) y la complejidad

es lineal en (m y n) [17].

Dentro de los algoritmos que se evaluaron para seleccionar el más adecuado para el uso

de la base de datos del Colegio Ofelia Uribe de Acosta, se evaluó el algoritmo TILDA, La

complejidad de este se encuentra en la robustez del modelo de probabilidad y en cómo se

calcula iterativamente, los modelos probalísticos pueden ser tan simples como una

distribución marginal o tan complejo como una distribución multivariante conjunta

expresando interacciones de orden superior ente las variables observadas. Es así que en el

peor de los casos la complejidad de TILDA, es ( ) siendo un escenario favorable para aplicaciones a gran escala [7].

En conclusión TILDA, respecto a UMDA y a un Árbol de Decisión, es el algoritmo que

menos costo computacional consume.

Para el árbol de decisión, haciendo uso de la herramienta WEKA 3.6 y usando el

algoritmo del árbol Id3 se obtuvieron los siguientes resultados; las variables más

determinantes en su orden fueron 10 y son: Estado, G0 (Grado cero), E1 (5 años),

Jornada, Estrato, Género, G3 (Grado Tercero), E7 (10 años), G1(Grado Primero) y G9

(Grado Noveno).

Dentro del algoritmo UMDA, en la Iteración 4 (ver sección 3.3.4) se obtuvo la mayor

cantidad de variables respecto a las otras iteraciones, las 7 variables obtenidas fueron;

Jornada, Estrato, G7 (Grado Séptimo), E4 (8 años), E5 (9 años), E9 (12 años), E14 (17

años), E16 (19 años), Nivel.

Así se concluye que UMDA obtuvo una menor cantidad de variables pero con una mayor

efectividad determinando las variables más relevantes dentro de la deserción escolar,

teniendo en cuenta la discusión de resultados (ver sección 3.4), respecto a un árbol de

decisión.

64

6. CONCLUSIONES Y TRABAJO FUTURO

Lo observado en el experimento de selección del algoritmo a usar para el caso de estudio:

Deserción escolar en el Colegio Ofelia Uribe de Acosta, es que el algoritmo PBIL da

resultados muy similares al algoritmo UMDA, el único déficit de PBIL es que demora un

poco más de tiempo en ejecución respecto a UMDA. Se puede proponer un estudio al

Widget de PBIL, buscando mejorar el tiempo que gasta en cada iteración.

En el desarrollo de la preparación de los datos (capitulo 3), se encontró que el pre

procesamiento de los datos es fundamental para las tareas de selección de variables, en

especial para la herramienta Orange- Goldenberry, si no se realiza el tratamiento previo

de datos se obtendrán resultados no concluyentes e imprecisos. En este caso, los

algoritmos de selección de variables presentaron mejor comportamiento, en las variables

binarias en lugar de las variables discretas.

Dentro de la búsqueda de las librerías con las que el algoritmo wKIERA, se ejecuta

dentro de la pizarra de Orange, se encontró que Orange esta implementado en C++ por

rapidez y se requiere de Python por la flexibilidad, de ahí que no se necesita tener

conocimientos previos de programación para hacer uso de la herramienta Orange.

El costo computacional de UMDA en el peor caso, fue mayor respecto a un árbol de

decisión y a otros algoritmos usados para la selección de atributos, pero en cuanto a

efectividad en encontrar las variables relevantes en el caso de estudio, UMDA demostró

ser el algoritmo más adecuado para trabajar con variables independientes.

Como trabajo futuro se propone realizar un estudio que contenga variables Dependientes,

ya que estas representan mejor casos reales, adicional implementar una arquitectura para

disminuir el costo computacional, ya que durante algunas pruebas el tiempo que

demoraba en terminar de realizar las iteraciones era de larga duración.

También se propone programar algunos Widget para técnicas de selección de atributos

usando filtros y que estos permitan el alambrado dentro de la pizarra de Orange, dejando

la ventaja que para una persona empírica y sin conocimiento de programación; no sea de

difícil comprensión el uso de estos nuevos elementos dentro del menú.

Debido a la poca información que se encuentra de la caja de herramientas de

Goldenberry, realizar una documentación detallada, acerca de cada uno de los Widget,

sus funciones, el código que contiene y lo usos que se le puede dar a cada uno de ellos.

De tal forma que se genere propuestas de nuevos elementos dentro de Goldenberry.

65

7. BIBLIOGRAFÍA

[1] Armañanzas, R., Inza, I., Santana, R., Saeys, Y., Flores, J. L., Lozano, J. A., Peer, Y.

V. D., Blanco, R., Robles, V., Bielza, C., & Larrañagañaga, P. (2008). A review of

estimation of distribution algorithms in bioinformatics. BioData Mining.

[2] Chapman, P., Clinton, J., Kerber, R., Khabaza, T., Reinartz, T., Shearer, C., & Wirth,

R. (1999, 2000). Crisp – dm 1.0 step-by-step data mining guide.

[3] Demsar, J., Cruk, T., Erjavec, A., Crt Gorup, Hocevar, T., Milutinovic, M., Mozina,

M., Polajnar, M., Toplak, M., Staric, A., Stajdohar, M., Umek, L., Zagar, L., Zbontar, J.,

Zitnik, M., & Zupan, B. (2013). Orange: Data mining toolbox in phyton. Journal of

Machine Learning Research, 14, 2349 - 2353.

[4] Dougherty, J., Kohavi, R., & Sahami, M. (1995). Supervised and unsupervised

discretización of continuous features. Computer Science Department.

[5] Garzón, L., Rojas-Galeano, S., & Diosa, H. (2015). Deconstructing GAs into visual

Genetic ans Evolutionary Computation Conference, GECCO ´15: ACM.

[6] Hsu, C., Chang, C. C., & Lin, C. J. (2010). A practical guide to support vector

classification.

[7] Rodriguez, N. (2013). Feature relevance estimation by envolving probalistic

dependency networks with weighted kernel machines. Master´s thesis, Universidad

Distrital Francisco Jose de Caldas, Bogota D.C., Colombia.

[8] Rojas, S., Hsieh, E., Agranoff, D., Krishna, S., & Fernandez – Reyes, D. (2008).

Estimation of relevant variables on high – dimensional biological patterns using iterated

weighted kernel functions. PLoS ONE, 3(3).

[9] Rojas, S. & Rodriguez, N. (2012). A memory efficient and continuous valued

compact eda for large scale problems. In Proceedings of the Fourteenth International

Conference on Genetic and Evolutionary Computation Conference, GECCO´12. New

York, NY, USA: ACM.

[10] Rojas, S. & Rodriguez, N. (2013). Goldenberry: Eda visual programming in Orange.

In Proceeding of the Fourteenth Annual Conference Companion, GECCO´13.

Companion. New York, NY, USA: ACM.

[11] Shearer, C. (2000). The crisp model: the new blue print for data mining. In Journal

of Data Warehousing, volume 5.

[12] Enríquez, C. (2008). Factores de Riesgo Asociados a Bajo Rendimiento Académico

en Escolares de Dos Instituciones Educativas Públicas de Bogotá. Tesis de Magister,

Universidad CES, Medellín, Colombia.

66

[13] Moujahid A., I naki Inza & Larra P. Algoritmos de Estimación de Distribuciones.

Departamento de Ciencias de la Computación e Inteligencia Artificial. Universidad del

País Vasco–Euskal Herriko Unibertsitate.

[14] Shawe – Taylor, J. & Cristianini, N. (2004). Kernel Methods for Pattern Analysis.

New York, NY, USA: Cambriadge University Press.

[15] Python Software Foundation: Pagina web oficial de Python. Recuperado el 4 de

diciembre, 2014, de http://www.python.org/, 2014.

[16] López R. (2014). Python – Librerías Esenciales para el Análisis de Datos. Realizado

el 28 Mayo 2014, de http://relopezbriega.github.io/blog/2014/05/28/python-librerias-

esenciales-para-el-analisis-de-datos/, 2014.

[17] Arredondo Tomas (2008), Arboles de decisión, Complejidad Computacional.

[18] Salas, Roberto E. & Rodríguez R., Jorge E. (2005) Análisis de Complejidad

Algorítmica. Revista vínculos Universidad Distrital Francisco José de Caldas. Vol. 1,

Núm. 2 Investigación y Desarrollo.

[19] Fases de la metodología CRISP,

https://www.google.com.co/search?q=fases+de+la+metodolog%C3%ADa+crisp-

dm&source=lnms&tbm=isch&sa=X&ved=0ahUKEwjJ5q-

ghqrJAhXKLB4KHXgYD4YQ_AUIBygB&biw=1366&bih=643#tbm=isch&q=Fases+d

e+la+metodologia+CRISP&imgrc=1cqpzfbLjd0GEM%3A, 2009.

[20] Documentación de Orange, Catalogo de Widget, Página principal,

http://docs.orange.biolab.si/widgets/rst/index.html

[21] Periódico El Universal, El 50% de los jóvenes en Colombia deja la secundaria,

Bogotá, 2013.

[22] Periódico El Tiempo, En Usme esta uno de cuatro entornos escolares inseguros,

Redacción Bogotá, 2014.

[23] Sánchez Gabriel & García Jorge, Prediciendo la deserción escolar, Revista Semana –

Educación, 2014.

[24] Quiroz Santiago, Deserción Escolar en Colombia – La muerte de nuestra sociedad,

Pontificia Universidad Javeriana, Lenguas Modernas, 2010.

[25] Constitución Política de Colombia, Panamericana Editorial Bogotá, 1998 P. 74.

[26] Página Principal del ministerio de Educación, Un nuevo colegio para Usme con

nombre de mujer, http://www.mineducacion.gov.co/cvn/1665/article-120684.html, 2007.

[27] Ministerio de Educación Nacional – Republica de Colombia, Las 10 preguntas sobre

la deserción escolar en Colombia, 2012.

algoritmo basado en estimacion de...

Documents