Genetic
algorithm for the generation of prediction rules in mo=
odle
courses.
<=
/span>
Recibido: 13-09-2017 / Revisado: 07-11-2017 Aceptado: 05-12-2017/
Publicado: 01-01-2018
Abstract.
The development of new technologies of educa=
tion and communication has made possible the use of the Internet and more s=
pecifically the World Wide Web in distance education, giving rise to the denonimada Web-based Education or elearning. This implies a new conception of education by incorpora=
ting new technologies into the teaching and learning process. The objective=
of the research was to apply a Genetic Algorithm for the analysis of how s=
tudents learn on the web, starting from their navigation patterns and makin=
g use of virtual platforms in the university context. The proposed algorith=
m allowed optimizing and customizing the structure of Moodle courses. administrative models that manage the informationa=
l asset, and allow proposing actions, programs and projects to implement bu=
siness intelligence systems.
Keywords: Genetic Algorithms, Moodle, Navigation Patterns.=
Resumen.
El desarrollo de las nuevas tecnología=
s de
la educación y la comunicación han hecho posible la utilización de Internet=
y
más concretamente la WWW (World Wide Web) en la
educación a distancia, dando lugar a la denominada Educación basada en Web o
e-learning. Esto supone una nueva concepción de la educación mediante la
incorporación de nuevas tecnologías al proceso de enseñanza y aprendizaje. =
En
la investigación realizada se propuso como objetivo aplicar un Algoritmo
Genético para el análisis de como los estudiantes aprenden en el web, partiendo de sus
patrones de navegación y haciendo uso de las plataformas virtuales en el
contexto universitario. El algoritmo propuesto permitió optimizar y
personalizar la estructura de los cursos del Moodle.
Palabras Claves:
Algoritmos Genéticos, Moodle, patrones de navegac=
ión.
Introducción.
El
desarrollo de las nuevas tecnologías de la educación y la comunicación han
hecho posible la utilización de Internet y más concretamente la WWW (World Wide Web) en la educación a distancia, dando lu=
gar a
la denonimada Educación basada en Web o e-learn=
ing
(Horton, 2000). En los últimos años, e-learning supone una nueva concepción=
de
la educación mediante la incorporación de nuevas tecnologías al proceso de
enseñanza y aprendizaje. Esta plataforma educativa proporciona tanto a doce=
ntes
como alumnos una importante variedad de recursos, lo que en muchas ocasiones
esto suele ser una desventaja.
Esto
hace que el alumno se encuentre desorientando frente a la elección de recur=
sos
diseñados. Este problema requiere una reestructuración de cómo el docente ha
diseñado la asignatura, con el objetivo que ese diseño se adapte mejor mane=
ra a
las características e intereses de los alumnos (Corso
and Alfaro, 2007).
El
uso de ambientes virtuales basados en la web, como herramienta de apoyo al
proceso educativo, se ha expandido en los últimos años, gracias al desarrol=
lo
de nuevos enfoques y modalidades de educación, como el e-learning y el b-learning. Estas nuevas formas de utilización de la tecnología como apoyo
al proceso de enseñanza aprendizaje, han incentivado la aparición de softwa=
re
especializado en proveer los mecanismos que facilitan el desarrollo del tra=
bajo
autónomo del estudiante, su interacción con el docente, y el uso de
herramientas colaborativas y de comunicación para el trabajo grupal (Aponte=
et
al., 2012).
Estas técnicas de minería de datos o dat=
a mining (DM) ya se han aplicado con éxito en sistemas =
de
comercio electrónico o e-commerce, para compren=
der el
comportamiento de clientes en línea de sistemas de comercio electrónico y <=
span
class=3DGramE>poder incrementar las
ventas (Srivastava et al., 2000). Para consegui=
r su
objetivo, las herramientas de DM utilizan técnicas de extracción de
conocimiento para descubrir información útil en la mejora del sistema. Aunq=
ue
los métodos de descubrimiento de información utilizados en ambas áreas (e-<=
span
class=3DSpellE>commerce y elearning) son
similares, los objetivos finales tienen matices totalmente diferentes debid=
o a
que en e-commerce el objetivo es guiar a los cl=
ientes
durante la compra para maximizarla, mientras que en e-learning el objetivo =
es
guiar a los estudiantes durante su aprendizaje para maximizarlo. Por lo tan=
to,
cada uno tiene unas características específicas que requieren de un tratami=
ento
diferente dentro del problema de minería de Web.
En esta investigación se presenta un alg=
oritmo
genético cuyo objetivo es obtener un conjunto de reglas de asociación que
permitan la realización de predicciones en cuanto al comportamiento de los
usuarios y aporten conocimiento interesante sobre un problema con relaciones
desconocidas entre las variables. El algoritmo tiene capacidad para extraer
reglas difusas o nítidas en función de que las variables del problema sean
continuas o nominales. Estas reglas pueden permitir extraer conclusiones y
planificar de mejor manera la organización de los cursos en Moodle.
2-Desarrollo.
En
los últimos años, el aprendizaje electrónico o conocido también por el
anglicismo, e-learning, ha generado una nueva concepción de la educación
mediante la incorporación de nuevas tecnologías al proceso de enseñanza y
aprendizaje. El e-learning ha posibilitado que los estudiantes puedan
comunicarse y colaborar con otros estudiantes y docentes (profesores, tutor=
es,
mentores, entre otros), de forma síncrona o asíncrona, sin limitaciones
espacio-temporales. En otras palabras, el e-learning se comporta como una m=
odalidad
de aprendizaje dentro de la educación a distancia en la que se utilizan las
redes de datos como medios (internet, intranets, entre otros), las herramie=
ntas
o aplicaciones hipertextuales como soporte (correo electrónico, web, chat,
entre otros) y los contenidos y/o unidades de aprendizaje en línea como
materiales formativos (desde simples imágenes, audio, video, documentos, en=
tre
otros, hasta complejas producciones multimedia, así como contenidos constru=
idos
de forma colaborativa), entre otros (García
et al., 2008).
El
aumento de la utilización de las plataformas e-learning ha generado en los
últimos años una fuerte tendencia por parte de las universidades e institut=
os
de enseñanza en el uso de plataformas educativas basadas en la web, centran=
do
su uso para cursos a distancia, semipresenciales y presenciales. Según (Pal=
ma,
2013) el uso de estas plataformas virtuales han posibil=
itado
además, la incorporación de herramientas tecnológicas en las aulas de clase=
s,
lo cual constituye un enriquecimiento del currículo educativo en el cual, el
docente pasa de cumplir sólo un rol de transmisor de conocimientos a ser un
facilitador del proceso enseñanza – aprendizaje, dejando de constituir la
fuente principal de información.
Al realizar una navegación por la web, l=
os
usuarios dejan huellas digitales, tales como direcciones de Protocolo de
Internet o dirección IP (Internet Protocol por =
sus
siglas en inglés), navegador empleado, cookies, url
de los sitios visitados, entre otros datos que los servidores almacenan aut=
omáticamente
en una bitácora de accesos (logs). El análisis de ficheros logs de los
servidores web puede proporcionar variedad de información valiosa que
permitiría mejorar la estructura de un sitio web, así como permite estudiar=
el
comportamiento de los usuarios al visitar estos sitios con el objetivo
principal de crear una navegación más efectiva y un acceso más eficiente.
Para el análisis de estos ficheros log e=
n el
siguiente artículo se propone la aplicación de un algoritmo genético (Agrawal and Srikant)
multiobjetivo para la extracción de reglas de asociación.
2-1. Reglas de Predic=
ción.
El
modelado de dependencias (Klösgen and Zytkow, 2002), también denominado por algunos autores=
como
inducción de reglas de predicción o reglas generalizadas tiene como cuyo
objetivo el descubrimiento de reglas interesantes para mostrárselas al usua=
rio.
Estas reglas, que representan relaciones de dependencia importantes entre l=
os
datos y que se pueden utilizar para la posterior toma de decisiones, presen=
tan
el siguiente formato:
SI Cond1, Y…Condi… Y Condm ENTONCES <=
span
class=3DSpellE>Pred.
Donde cada condición Condi
y la predicción de la regla Pred están formados=
por
una tripleta: (Atributo, Operador, Valor). Este tipo de reglas muestra la
relación existente entre el antecedente, que contiene las condiciones sobre los val=
ores de
los atributos predictores, y el consecuente, que contiene la predicción sob=
re
el valor del atributo objetivo.
Llegado este punto, habría que puntualiz=
ar la
diferencia que existe entre el descubrimiento de reglas de predicción y el
descubrimiento de reglas de asociación (Freitas, 2000), una tarea similar pero algo más general, en la que el objetivo e=
s la
búsqueda de todas las posibles relaciones entre atributos y donde puede hab=
er
incluso varios atributos en el consecuente de la regla. La tarea de
descubrimiento de reglas de asociación, introducida por Agrawal
(Agrawal and Srikant, 1994)
que la define como el problema de encontrar todos los elementos que son
frecuentes con respecto a un umbral mínimo de soporte y confianza.
El soporte indica el porcentaje de insta=
ncias
que contienen tanto consecuente como el antecedente y la confianza indica el
porcentaje de instancias que contienen el consecuente también contienen al
antecedente. De forma, que el usuario debe especificar un valor mínimo de la
medida de soporte y confianza, siendo el objetivo de la tarea encontrar tod=
as
las reglas que superen esos valores. Una regla de predicción puede verse co=
mo
una regla de asociación con un solo elemento en su consecuente, por lo que
cualquier algoritmo de descubrimiento de reglas de asociación se puede
modificar fácilmente para añadir esta restricción y descubrir sólo reglas de
predicción. Hemos utilizado reglas de predicción en lugar de reglas de
asociación debido a que se pueden utilizar más fácilmente para la toma de
decisiones, son intuitivamente más comprensibles y muestran relaciones dire=
ctas
entre los elementos en lugar de todas las posibles relaciones. <=
/span>
2-2.
Descubrimiento de Reglas de Predicción utilizando Algoritmos Evolutivos.
La
tarea del descubrimiento de reglas ha sido abordada desde multitud de
paradigmas: construcción de árboles de decisión, aprendizaje inductivo,
aprendizaje basado en instancias y, más recientemente redes neuronales y
algoritmos evolutivos (Freitas, 2000).
El
tipo de búsqueda que realizan cada uno de estos algoritmos va a determinar
dónde se encuentran localizados dentro del panorama de la minería de reglas=
y
desde el punto de vista de la minuciosidad de la búsqueda.
Los
Algoritmos Evolutivos son algoritmos estocásticos de búsqueda basados en las
ideas de la evolución darwiniana. Los paradigmas de Computación Evolutiva q=
ue
se han aplicado para resolver el problema del descubrimiento de reglas
(Freitas, 2013) son los Algoritmos Genéticos y la Programación Genética.
La
Programación Genética (PG) se puede considerar como un paradigma de búsqueda
más abierta que el de Algoritmos Genéticos.
La
búsqueda realizada por la PG puede ser muy útil para clasificación y otras
tareas, ya que el sistema puede producir diferentes combinaciones de atribu=
tos,
utilizando las funciones disponibles en un conjunto preestablecido por la
codificación, que no se considerarían utilizando un algoritmo genético
convencional.
La
Programación Genética basada en gramáticas (Romero et al., 2005b) es un
paradigma de programación genética en el que los individuos vienen
representados como árboles de derivación de una gramática definida por el
usuario para especificar el espacio de soluciones al problema. <=
/span>
Se
ha elegido este paradigma por la expresividad que presenta, que va a facili=
tar
enormemente la interacción con el usuario. A continuaci=
ón
vamos a describir el algoritmo evolutivo utilizado y la codificación y la
función de evaluación concreta de los individuos.
Algoritmo genético. <=
o:p>
El
algoritmo evolutivo que hemos empleado para realizar la tarea específica de
descubrimiento de reglas de predicción (Romero et al., 2005b), se muestra e=
n la
Figura 1.1.
Figura 1.1:
Algoritmo evolutivo utilizado para la búsqueda de reglas de
<=
span
lang=3DES-EC style=3D'font-size:12.0pt;line-height:115%;font-family:"Times =
New Roman",serif'>predicción.
Fuente:
(Romero et al., 2005a).
El
algoritmo comienza con la inicialización de la población, consiste en la
generación del
conjunto o población
inicial de individuos o reglas. A continuación se
realiza la evaluación, que consiste en calcular el ajuste de cada individuo=
y
el almacenamiento de los mejores (en nuestro caso los no dominados) en una
población final. Después se determina si el algoritmo debe de terminar, es
decir, si ha alcanzado un número determinado de evoluciones o ha encontrado=
un
número determinado de reglas. Sino, se pasa a la=
etapa
de selección donde se elige de entre la población actual y la final a los
individuos que van a ser padres de la siguiente etapa de reproducción. La
reproducción consiste en la creación a partir de los padres seleccionados de
nuevos individuos mediante los operadores de cruce y mutación (Michalewicz, 1996) .Finalmente la
población actual es sustituida por la nueva población de padres y el proces=
o se
vuelve a repetir.
Función de Evaluación=
.
La
función de evaluación mide la calidad de los individuos o reglas en nuestro
caso. En la bibliografía hay descritas una gran cantidad de métricas para
evaluar reglas (Lavrač et al., 1999) (Tan =
and
Kumar, 2000) (soporte, confianza, interés, precisión, =
informatividad,
fiabilidad negativa, sensibilidad, especificidad, cobertura, innovación,
satisfacción, precisión relativa, etc.). Pero cada una mide un aspecto de la
regla. Este problema sugiere el uso de una aproximación multiobjetivo (Fons=
eca
and Fleming, 1993) para el descubrimiento de reglas, donde el valor de la
función ajuste a optimizar no es un valor escalar único, sino un vector de
valores, donde cada valor mide un aspecto diferente de la calidad de la reg=
la.
En nuestro caso la función de evaluación o función de ajuste utilizada está
formada por un vector de tres componentes donde cada uno mida uno de los
siguientes criterios de los individuos:
Exactitud de la regla=
.
Mide la exactitud o precisión de las reglas. Nosotros hemos utilizado la me=
dida
denominada factor de certeza (Shortliffe and
Buchanan, 1975).
Comprensibilidad de la
regla. Mide la comprensibilidad de la regla =
por
parte del usuario. Nosotros hemos utilizado la medida de simplicidad (Liu a=
nd Kwok, 2000) que depende de la longitud de la regla.
Interesabilidad de la regla.<=
/b>
Mide el interés objetivo y subjetivo de la regla. Nosotros hemos utilizado =
la
medida de interés (Tan and Kumar, 2000). En nuestra propuesta la función de
evaluación tiene la siguiente expresión:
Figura 1.2:
Medida de interés.
Donde
W1, W2 y W3 son pesos creados para el usuario, ya que el mismo puede darle
mayor peso a Completitud que a Confianza e Interés. Fin=
almente
todos los componentes de ecuación son normalizados.
El
objetivo global de la función de evaluación es orientar la búsqueda hacia
reglas que maximicen la precisión, minimizando el número de ejemplos negati=
vos
y no cubiertos.
Operadores Genéticos.=
El
AG utiliza un modelo de reproducción de estado estacionario. La recombinaci=
ón
se realiza a través del operador de cruce multipunto y un operador de mutac=
ión
uniforme sesgado con el que la mitad de las mutaciones realizadas tienen el
efecto de eliminar la variable correspondiente, para incrementar la general=
idad
de las reglas.
Esquema de reproducci=
ón.
El
AG utiliza un modelo de reproducción de estado estacionario modificado
(Casillas et al., 2001) que sigue el esquema siguiente: 1. Se genera una
población intermedia mediante asignación de probabilidades basada en ordena=
ción
lineal y en el esquema de selección de muestreo estocástico universal de
Baker. 2.
Se
aplican los operadores de cruce y mutación a algunos individuos de esta
población intermedia. El número de cromosomas a crear vendrá determinado po=
r la
probabilidad de cruce y mutación. =
3. Los
nuevos cromosomas creados sustituirán a los cromosomas peor adaptados de la
población original.
De
esta forma se sigue la filosofía de la reproducción estacionaria, ya que la
población original sólo se modifica mediante la sustitución de los peores
individuos por los individuos resultantes de la recombinación. <=
/span>
La
aplicación de los operadores de cruce y mutación a un porcentaje de cromoso=
mas
de una población intermedia, obtenida mediante selección de los individuos
mejor adaptados según un esquema de ordenación lineal y muestreo estocástico
universal, implica la generación de más de dos cromosomas nuevos introduce =
más
diversidad en la nueva población.
2.3.
Experimentos y resultados.
Para
poder utilizar el modelo de datos es necesario comenzar con la etapa de
preprocesamiento de los datos y así tener una idea más clara de
los conjunto de datos que analizaremos. Es de suponer que la prepara=
ción
de los datos puede generar un conjunto de datos más pequeño que el original=
, y
de esta manera mejorar la eficiencia de la Minería (ver Figura 2.1). <=
/o:p>
<=
span
lang=3DES-EC style=3D'font-size:12.0pt;line-height:115%;font-family:"Times =
New Roman",serif'> Figura 2.1:
Muestra del log de Moodle después de la etapa de preprocesamiento.
Fuente:
Elaboración propia.
Al
mismo tiempo que realiza la etapa de preprocesamiento se puede realizar la
identificación de entradas o transacciones que va dejando el usuario durant=
e la
navegación. Es importante determinar las entradas de los usuarios para poder
aplicar, en este caso el algoritmo genético multiobjetivo.
Después de realizado el prepocesamiento
de los datos se procede aplicar el algoritmo genético. A continuación se
muestra una regla obtenida y su interpretación.
Si
/dt/?c=3D11670 Entonces http://www.shop34.index/ls/index.php?&am=
p;id=3D98 (Interés=3D0.51, Factor Certeza=3D0.79,=
Simpleza=3D
1) .
Interpretación:
Esto indica que los usuarios visitan a la página /dt/?c=3D11670
y luego se van a la página http://www.shop34.index/ls/index.php?&id=3D9=
8 a
demás podemos afirmar esto con una certeza del 79%. Esta regla nos muestra
ciertos patrones de navegación del usuario con el cual podemos hacer ciertas
mejoras a nuestro curso para que el usuario pueda encontrar en estas páginas
información mucho más interesante.
Conclusiones.
· =
El Algoritmo Genético
Multiobjetivo propuesto permite obtiene reglas que facilitan la toma de
decisiones sobre posibles modificaciones que se pueden realizar en los curs=
os,
se han descrito las utilidades que pueden tener para la mejora del curso y =
se
han mostrado ejemplos concretos de reglas descubiertas con el curso. <=
/o:p>
·&nb=
sp;
La aplicación del
algoritmo a un problema real ha determinado un conjunto sencillo de reglas =
con
estructura también sencilla. Es un algoritmo que permite extraer conocimien=
to
comprensible en forma de pocas reglas nítidas o difusas con pocas variables=
.
· =
En los trabajos futur=
os
se debe mejorar la eficiencia del algoritmo, ya que es muy costoso
computacionalmente y no se puede expandir totalmente, por lo que no se obti=
enen
la cantidad de reglas óptimas deseadas. Se debe tratar de perfeccionar el
método de discretización de modo que no se genere tanta cantidad de interva=
los
y en consecuencia el AG tarde en converger.
Referencias
bibliográficas.
·&nb=
sp;
AGRAWAL,
R. & SRIKANT, R. Fast algorithms for mining association rules. Proc. 20th int. conf. very large data b=
ases,
VLDB, 1994. 487-499.
·
APONTE, F. A., HOYOS,=
J.
G. & MONSALVE, J. A.. Minería de usabilidad
aplicada a plataformas virtuales de aprendizaje. 2012.
·&nb=
sp;
CASILLAS,
J., CORDÓN, O., DEL JESUS, M. J. & HERRERA, F. Genetic feature selectio=
n in
a fuzzy rule-based classification system learning process for high-dimensio=
nal
problems. Information
Sciences, 136, 135-157. 2001.
·
CORSO, C. L. &
ALFARO, S. L. MINERIA DE USO WEB: PRESENTACIÓN DE CASO PRÁCTICO PARA EL
MEJORAMIENTO DE LA EDUCACIÓN, BASADA EN EL USO DE PLATAFORMAS VIRTUALES. 2007.
·
FONSECA,
C. M. & FLEMING, P. J. Genetic Algorithms for Mult=
iobjective
Optimization: FormulationDiscussion and General=
ization. ICGA, Citeseer,
416423. 1993. FREITAS, A. A.. Understanding the
crucial differences between classification and discovery of association rul=
es:
a position paper. AcM sIGK=
DD
Explorations Newsletter, 2, 65-69. 2000
·&nb=
sp;
FREITAS,
A. A. Data mining and knowledge discovery with evolutionary algorithms,
Springer Science & Business Media. 2013.
·
GARCÍA
, S. E., ROMERO, C., VENTURA, S. &
DE-CASTRO-LOZANO, C. Sistema recomendador
colaborativo usando minería de datos distribuida para la mejora continua de
cursos e-learning. IEEE-RITA=
, 3,
19-30. 2008.
·
HORTON,
W. K. Designing web-based training: how to teach anyone anything anwhere anytime. New York. 2000.
·
KLÖSGEN,
W. & ZYTKOW, J. M. Handbook of data mining and knowledge discovery, Oxf=
ord
University Press, Inc. 2002.
·
LAVRAČ,
N., FLACH, P. & ZUPAN, B. Rule evaluation measures: A unifying view,
Springer. 1999.
·
LIU,
J. J. & KWOK, J. T.-Y. An extended genetic rule induction algorithm. Evolutionary Computation, 2000. Proceed=
ings
of the 2000 Congress on, 2000. IEEE, 458-463.
·&nb=
sp;
MICHALEWICZ,
Z. Genetic Algorithms+ Data Structures=3D Evolution Programs (3rd edit.) Springer.
New York. 1996.
·&nb=
sp;
PALMA, J. A. L. Propu=
esta
de una metodología para perfeccionar la funcionalidad de plataformas virtua=
les
de aprendizaje. Serie Científica, 6. 2013.
·
ROMERO, C., VENTURA, =
S.,
DE CASTRO, C. & GARCÍA, E.. Algoritmos Evolu=
tivos
para Descubrimiento de Reglas de Predicción en la Mejora de Sistemas Educat=
ivos
Adaptativos basados en Web 47-60. 2005a
·
ROMERO, C., VENTURA, =
S.,
HERVÁS, C. & GONZÁLEZ, P.. Rule Discovery in web-based educational systems us=
ing
Grammar-Based Genetic Programming. Data Mining VI: Data Mining, Text Mining=
and
Their Business Applications, 205-214. 2005b
·
SHORTLIFFE,
E. H. & BUCHANAN, B. G. A model of inexact reasoning in medicine.
Mathematical biosciences, 23, 351-379. 1975.
·
SRIVASTAVA,
J., COOLEY, R., DESHPANDE, M. & TAN, P.-N. Web usage mining: Discovery =
and
applications of usage patterns from web data. ACM SIGKDD Explorations
Newsletter, 1, 12-23. 2000.
·&nb=
sp;
TAN,
P. & KUMAR, V. Interesting measures for association patterns. Proc. KDD Workshop on Postprocessing in
Machine Learning and Data Mining, Boston, USA, 2000. 1-9.
&n=
bsp;
&n=
bsp;
Para citar el artículo indexado.=
&n=
bsp;
&n=
bsp;
&n=
bsp;
&n=
bsp;
&n=
bsp;
El
artículo que se publica es de exclusiva responsabilidad de los autores y no
necesariamente reflejan el pensamiento de la Revista Ciencia Digital.
El articulo queda en propiedad de la revist=
a y,
por tanto, su publicación parcial y/o total en otro medio tiene que ser
autorizado por el director de la R=
evista
Ciencia Digital.
&n=
bsp;
&n=
bsp;
<=
/span>
<=
/span>
<=
/span>
<=
/span>