El Algoritmo De Agrupamiento K-Modas: Un Caso De Estudio

ArtículoYa que durante este periodo puede estardefinida la continuidad de los estudiosuniversitarios. En este estudio se dividen lasvariables en factores académicos, personales ysocioeconómicos, tomando en cuenta el éxitoacadémico como la acreditación oportuna de lasasignaturas, exámenes departamentales y unapuntuación determinada durante los primeros 2años de la carrera Médico Cirujano de laFacultad de Medicina de la UNAM en la Ciudadde México.El éxito académico del estudiante delicenciatura proporciona ciertos beneficios a lasociedad por su contribución al desarrolloeconómico, cultural y social del país, que semanifiesta en la productividad de susactividades docentes, de investigación ydifusión de la cultura.Definiciones preliminaresAlgoritmo de agrupamientoEl objetivo de los algoritmos de agrupamientoes encontar particiones disjuntas de un conjuntode datos o base de datos, de tal manera que losobjetos en el misno grupos sean lo mássimilares que los objetos de los otros grupos(Jain, 1988).Descripción del algoritmo k-modasEl algoritmo k-modas (Zhexue., 1998), fuediseñado para agrupar grandes conjuntos dedatos categóricos, y tiene como objetivo obtenerlas k modas que representan al conjuntoDominios y atributos categóricosZhexue en (Zhexue., 1998), describe los datoscategóricos como objetos descritos únicamentepor atributos categóricos o como una versiónsimplificada de los objetos simbólicos definidosen (Godwa, 1992).ISSN-2410-3993ECORFAN Todos los derechos reservados932Revista Tecnología e InnovaciónDiciembre 2015 Vol.2 No.5 929-941Considera a todos los atributosnuméricos (cuantitativos) al categorizarlos y noconsidera los atributos categóricos que estáncontenidos por una combinación de valoresdeterminados. Los objetos y atributoscategóricos aceptados por el algoritmo k-modasson definidos en (Zhexue., 1998).Suponga que 𝐴1 , 𝐴2 , . . . , 𝐴𝑚 son los matributos que describen a un objeto en unespacioΩydominio𝐷𝑂𝑀(𝐴1 ), 𝐷𝑂𝑀(𝐴2 ), , 𝐷𝑂𝑀(𝐴𝑚 ).Un dominio 𝐷𝑂𝑀(𝐴𝑗 ) es definido comocategórico si es un conjunto finito y noordenado. Ω Es un espacio categórico si todo𝐴1 , 𝐴2 , . . . , 𝐴𝑚 es categórico.Objetos categóricosComo en (Godwa K.C., 1991), un objetocategórico 𝑋𝜀 Ω es representado como laconjunción lógica de pares atributo-valor [𝐴1 𝑋1 ] [𝐴2 𝑋2 ] [𝐴𝑚 𝑋𝑚 ],donde𝑋𝑗 𝜀 𝐷𝑂𝑀(𝐴𝑗 ), para 1 1 𝑗 𝑚 mismo paraatributo-valor [𝐴𝑗 𝑋𝑗 ] es llamado selector. Xes un vector de la forma [𝑋1 , 𝑋2 , , 𝑋𝑚 ] y cadaobjeto en Ω tiene exactamente m valoresatributos y si el valor para el atributo 𝐴𝑗 no estádisponible para un objeto 𝑋 , entonces 𝐴𝑗 𝜀donde 𝜀 representa al valor de un atributo nodisponible.Sea 𝑋 {𝑋1 , 𝑋2 , , 𝑋𝑛 } un conjunto den objetos categóricos 𝑋 Ω .El objeto 𝑋𝑖 esrepresentado como [𝑋𝑖1 , 𝑋𝑖2 , , 𝑋𝑖𝑚 ]. Dosobjetos 𝑋𝑖 , 𝑋𝑘 son iguales 𝑋𝑖 𝑋𝑘 si 𝑥𝑖𝑗 𝑥𝑘𝑗para todo1 𝑗 𝑚. La relación 𝑋𝑖 𝑋𝑘 noquiere decir que 𝑋𝑖 , 𝑋𝑘 sean algunos objetos enlas bases de datos del mundo real. Esto implicaque dos objetos tienen igual valor categórico ensus atributos 𝐴1 , 𝐴2 , , 𝐴𝑚 .RENDÓN, Eréndira, ZEPEDA, Ricardo, BARRUETA, Elizabeth yITZEL-MARÍA, Abundez. El algoritmo de agrupamiento K-Modas: Uncaso de estudio. Revista de Tecnología e Innovación 2015

933Revista Tecnología e InnovaciónDiciembre 2015 Vol.2 No.5 929-941ArtículoAsuma que X consiste de n objetos endonde p objetos son distintos. Sea N ��1 )𝑥 𝐷𝑂𝑀(𝐴2 )𝑥 𝑥 𝐷𝑂𝑀(𝐴𝑚 ).Tenemos que p N. De cualquier modo, npuede ser tan grande como N.Medidas de disimilaridad utilizadasModas de un conjuntoSea 𝑋 un conjunto de objetos descritos poratributos categóricos. Una moda de 𝑋 es unvector 𝑄 [𝑞1 , 𝑞2 , . , 𝑞𝑚 ] Ω que minimizaa𝐷(𝑄, 𝑋) 𝑛𝑖 1 𝑑(𝑋𝑖 , 𝑄)donde𝑋 (𝑋1 , 𝑋1 , . . , 𝑋𝑛 , ) y 𝑑 pueden ser calculadascon la ecuación 2 o la ecución 3.Sean X, Y dos objetos categóricos descritos porm atributos categóricos. La medida dedisimilaridad entre X y Y se define por el totalde las no coincidencias de los atributoscategóricos de los objetos. El número máspequeño de las diferencias significa que losobjetos son similares (Zhexue., 1998).Función criterioFormalmente:𝐸 𝑘𝑙 1. 𝑖 1 𝑦𝑖,𝑙 𝑑(𝑋𝑖 , 𝑄𝑙 )𝑛𝑑(𝑋, 𝑌) 𝑚𝑗 1 𝛿(𝑋𝑗 , 𝑌𝑖 )(1)Donde:𝛿(𝑋𝑗 , 𝑌𝑖 ) {0 (𝑥𝑗 𝑦𝑖 )(2)1 (𝑥𝑗 𝑦𝑖 )d(X,Y) da igual importancia a cadacategoría del atributo. Si se toma en cuenta lasfrecuencias de las categorías en el conjunto dedatos, se define la medida de disimilaridad,(4)Donde 𝑦𝑖,𝑙 es un elemento de la matrizde la partición 𝑌𝑛𝑥𝑙 como en (Godwa, 1991) y dpuede ser definida como la ecuación 1 o laecuación 3. Similar al algoritmo k-medias, elobjetivo de agrupar el conjunto X es encontrarun conjunto {𝑄1 , 𝑄2 , , 𝑄𝑘 , }que puedeminimizar E. La ecuación 4, puede serminimizada por el algoritmo k-modas.El algoritmo K-ModasEl algoritmo k-modas es una versión del kmedias para datos categóricos.Como:𝑑𝑥 2 (𝑋, 𝑌) 𝑚𝑗 1Suponga que {𝑆1 , 𝑆2 , , 𝑆𝑘 } es una particiónde X donde 𝑆1 (conjunto vacío), para 1 𝑙 𝑘 y {𝑄1 , 𝑄2 , , 𝑄𝑘 , } las modas de{𝑆1 , 𝑆2 , , 𝑆𝑘 } . El costo total de la partición esdefinido por:𝑛𝑥𝑗 𝑛𝑦𝑗𝑛𝑥𝑗 𝑛𝑦𝑗𝛿(𝑋𝑗 , 𝑌𝑗 )(3)Donde 𝑛𝑥𝑗 y 𝑛𝑦𝑗 son el número de objetosen el conjunto de datos, que tienen lascategorías 𝑥𝑗 y 𝑦𝑗 para el atributo j. Zhexuedenomina a la ecuación 3, distancia xicuadrada y la propone para descubrir grupos deobjetos con baja representación en la base dedatos.ISSN-2410-3993ECORFAN Todos los derechos reservadosEn k-modas se hacen 3 modificaciones ak-medias: Uso de diferentesdisimilaridad.medidasde Sustitución de k medias por k modaspara formar los centros. El método basado en las frecuencias delos datos para actualizar las modas.RENDÓN, Eréndira, ZEPEDA, Ricardo, BARRUETA, Elizabeth yITZEL-MARÍA, Abundez. El algoritmo de agrupamiento K-Modas: Uncaso de estudio. Revista de Tecnología e Innovación 2015

934Revista Tecnología e InnovaciónDiciembre 2015 Vol.2 No.5 929-941ArtículoLa actualización de las modas se realizaen cada asignación de un objeto a su grupo,mientras que en k-medias es al final de cadaiteración del algoritmo. El algoritmo k-modas aligual que el algoritmo k-medias producesoluciones óptimas locales, que dependen delconjunto de modas iniciales y el orden de losobjetos en el conjunto de datos.Tomando como muestra a los alumnosde la carrera de Ingeniería en SistemasComputacionales de las generaciones 2000 a2003.De acuerdo a los datos obtenidos seadmitirán en el estudio a todos los alumnos quecumplan con los siguientes criterios: Contar con expediente individual en elInstituto Tecnológico de Toluca.Descripción del algoritmo K-modasPaso 1: Seleccionar k modas iniciales, una paracada grupo. Haber cursado la carrera sinprovenientes de otra institución.Paso 2: Asignar cada objeto a la moda máscercana utilizando la distancia d. Actualizar lamoda del grupo después de cada asignación.Paso 3: Después que todos los objetos han sidoasignados a un grupo, volver a examinar ladisimilaridad de los objetos con las modasactuales. Si un objeto es encontrado tal que sumoda más cercana corresponde a otro grupo,asignar el objeto a su nueva moda y actualizar lamoda de ambos grupos.Paso 4: Repetir el paso 3 hasta que no existanobjetos cambiados de grupo.MetodologíaLa investigación es de tipo descriptiva yexperimental, la cual consta de 3 etapas(descriptiva, iterativa y resultante), querepresentan la recolección y procesamiento delos datos, así como los resultados obtenidos.Estas etapas se encuentran definidas acontinuación.ser Contar con la información completa delas variables estudiadas.Las variables empleadas en el estudiohan sido asignadas a partir de investigacionesdirigidas al análisis y comportamiento de losfactores que influyen en el proceso académicodel estudiante a nivel licenciatura, dichasinvestigaciones realizan procesos diferentes almomento de evaluar los factores, sin embargo,regularmente se encuentran dentro de unaclasificación conformada por tres grupos:1.Factores académicos.2.Factores personales.3.Factores socioeconómicos.De acuerdo con la clasificación anteriorse han elegido las variables que intervendrán demanera trascendental en el desarrollo delestudio, son definidas como variablesindependientes y señaladas a continuación:Etapa descriptivaLa información se obtuvo a partir de laherramienta de análisis de documentos a travésde las oficinas de Servicios Escolares yDesarrollo Académico del Instituto Tecnológicode Toluca.ISSN-2410-3993ECORFAN Todos los derechos reservadosa)Estado Civil.b)Edad.c)Trabajo.RENDÓN, Eréndira, ZEPEDA, Ricardo, BARRUETA, Elizabeth yITZEL-MARÍA, Abundez. El algoritmo de agrupamiento K-Modas: Uncaso de estudio. Revista de Tecnología e Innovación 2015

Artículod)Dependientes Económicos.e)Institución de procedencia.f)Tiempo de egreso.g)Periodo de ingreso.h)Promedio.Se determinó como variable dependienteal éxito académico (obtención del título a nivellicenciatura) considerado 7 años a partir de laúltima generación evaluada.Etapa iterativaEl paradigma de construcción de prototiposinicia con la comunicación. El ingeniero desoftware y el cliente encuentran y definen losobjetivos globales para el software, identificanlos requisitos conocidos y las áreas del esquemaen donde es necesaria más definición. Entoncesse plantea con rapidez una iteración deconstrucción de prototipos y se presenta elmodelado (en la forma de un diseño rápido). Eldiseño rápido conduce a la construcción de unprototipo. Después, el prototipo lo evalúa elcliente/usuario y con la retroalimentación serefinan los requisitos del software que sedesarrollará. (Pressman, 2005).Siguiendo el modelo anterior, seplantearon diversos apartados para llevar a cabola construcción de prototipos, validarlos ycontinuar con el desarrollo de la aplicación. Acontinuación se describen de manera práctica,dichos apartados.Pantalla principalDe manera inicial se determinó el requerimientode áreas de texto para visualizar los resultados.ISSN-2410-3993ECORFAN Todos los derechos reservados935Revista Tecnología e InnovaciónDiciembre 2015 Vol.2 No.5 929-941Las opciones para elegir los parámetrosde entrada (número de grupos a formar, tipo deecuación y selección de modas iniciales).También contar con los botones para realizar lasacciones de agrupamiento y las frecuencias dedominios. Así como la lógica principal delalgoritmo de agrupamiento k-modas.Posteriormente se identificó que sedebería contar con ciertas validaciones, deacuerdo a las opciones elegidas comoparámetros de entrada, ya que las variantes noson aplicables en todos los casos.Se presentó el prototipo y se agregó lavalidación del número de grupos a formar, paraque sea mayor o igual a 2, y menor al númerototal de elementos. A su vez se colocó la barradonde aparece el nombre y la ruta del archivoque se está utilizando para el agrupamiento.Se colocó una barra de menú en la partesuperior de la interfaz, originalmente con elapartado de “abrir” en la sección de archivo. Yaque con esta opción, se carga el archivo para seranalizado y agrupado.Una vez identificado el agrupamiento dedatos, se solicitó la creación de una rutina quepermita guardar archivos de texto, con losresultados que genera la aplicación. Definiendo3 tipos de archivos: 1. Resultados con etiquetade grupo. 2. Resultados con etiqueta de grupo ylos parámetros de entrada ocupados. 3.Resultados ordenados de acuerdo con lasetiquetas de grupo.De manera final se valoró y se integró laopción cerrar, para complementar el menú. Ycomenzar con la asignación de teclas rápidas,así como el inicio de generar otros apartadosdentro de la barra de menú.RENDÓN, Eréndira, ZEPEDA, Ricardo, BARRUETA, Elizabeth yITZEL-MARÍA, Abundez. El algoritmo de agrupamiento K-Modas: Uncaso de estudio. Revista de Tecnología e Innovación 2015

Artículo936Revista Tecnología e InnovaciónDiciembre 2015 Vol.2 No.5 929-941Barra de menú complementariaLos demás apartados añadidos en la barra demenú (editar, herramientas, ayuda), sedeterminó mediante un cambio de color eneditar, la creación de archivos a través de unaconsulta a la base de datos con la opción deherramientas y contar con una guía rápida einformación del software.Se redefinió la parte de generación dearchivos, debido a que varía de acuerdo a losparámetros de la base de datos y las opcionesque pueden desarrollarse al crear los archivos detexto, que serán utilizados para realizar elagrupamiento.Se presentaron las diversas iniciativas ycon los cambios requeridos, se validaron losapartados mencionados en los párrafosanteriores, para finiquitar el proceso en lacreación de la aplicación. Tomando en cuentaque se encuentra abierta la posibilidad defuturas mejoras o modificaciones, en caso de serrequeridas.Etapa resultanteLos datos que proporciona la aplicación kmodas7, serán representados en forma degrupos, etiquetando cada uno de sus elementos,para validar y determinar los factores queinfluyen en el desarrollo del estudiante paralograr la obtención del título y perfil de éxitoacadémico.Figura 2 Etapas del procesamiento de informaciónLa etapa descriptiva efectúa larecolección de datos y la definición de lasvariables que se utilizan en la investigación.La parte intermedia se forma a partir dela base de datos y la interacción con laaplicación k-modas7 mediante archivos detexto.Los resultados son identificados porcírculos que representan agrupaciones dealumnos con características similares.Aplicación K-Modas7La aplicación k-modas7 es una herramienta quepermite agrupar grandes cantidades de datos,mediante parámetros de entrada y archivos detexto. En primera instancia se presenta lapantalla inicial, para describir los elementos quela contienen, que puede observarse en la Figura3.Estos resultados podrán ser observadosen la aplicación o también generar un archivo detexto, con los datos correspondientes. Loscuáles serán analizados por expertos delDepartamento de Desarrollo Académico delTecnológico de Toluca.Finalmente en la Figura 2 puedenobservarse las etapas del procesamiento deinformación en forma gráfica y simplificada.ISSN-2410-3993ECORFAN Todos los derechos reservadosFigura 3 Pantalla inicialRENDÓN, Eréndira, ZEPEDA, Ricardo, BARRUETA, Elizabeth yITZEL-MARÍA, Abundez. El algoritmo de agrupamiento K-Modas: Uncaso de estudio. Revista de Tecnología e Innovación 2015

Artículo937Revista Tecnología e InnovaciónDiciembre 2015 Vol.2 No.5 929-941Existen 3 elementos principales en losque se compone la interfaz principal, hay unabarra de menú en la parte superior, en la cual seefectúan las diversas acciones para iniciar elproceso de agrupamiento, así como opciones deedición y ayuda.Seleccionar el menú Archivo-Abrir,ubicado en la Figura 4 y elegir un documento detexto almacenado en el equipo.En el menú Archivo se elige eldocumento de texto (.txt) que se va agrupar,contando con una serie de datos identificadospor un separador y con el mismo número deelementos por cada registro.Figura 4 Barra de menúSi no se cuenta con un archivo de datoselaborado, se utiliza el menú Herramientas paragenerar un archivo, haciendo una consulta a labase de datos para obtener la informaciónnecesaria, para ser agrupada.Generar un archivo en el menúHerramientas, identificado en la Figura 5 através de una consulta a la base de datos, paracrear el documento de texto (.txt) que se estaráagrupando con el uso de la aplicación. Hay quedeterminar los parámetros de conexión a la basede datos, así como la tabla y las condicionesnecesarias para hacer uso de este apartado.Finalizando con el nombre del archivo a crear.El menú Editar permite cambiar de colorlos datos resultantes en pantalla, y en el menúde Ayuda vienen una serie de instrucciones quesirven de apoyo para el uso de la aplicación.Para la segunda parte, puede verse una serie deopciones a elegir. En las que se encuentra elnúmero de grupos a formar, el tipo de ecuacióny la elección de las modas iniciales. Estasección se representa por el número 2, se debellenar el cuadro de texto con la cantidad degrupos que deseamos formar, posteriormente lasecuaciones con las que cuenta el algoritmo es laecuación binaria y xi-cuadrada. Para finalizar laelección de parámetros, seleccionar entreprimeros k elementos o modas ficticias.En la última zona de la interfaz, sepueden ver los resultados que generan el archivoelegido, dominios de frecuencias y elagrupamiento. Todo de acuerdo a losparámetros seleccionados y que se mencionaronanteriormente.A continuación se presenta una serie depasos, para hacer uso correcto de la aplicación.Ejecutar la aplicación k-modas7 para iniciar elproceso.ISSN-2410-3993ECORFAN Todos los derechos reservadosFigura 5 Pantalla generar archivoUna vez seleccionado el archivo que sedesea agrupar, se deberá escribir el número degrupos a formar (k), con el cual se determina lasparticiones con las que contaran los resultadosfinales.RENDÓN, Eréndira, ZEPEDA, Ricardo, BARRUETA, Elizabeth yITZEL-MARÍA, Abundez. El algoritmo de agrupamiento K-Modas: Uncaso de estudio. Revista de Tecnología e Innovación 2015

ArtículoSe debe tomar en cuenta que estosgrupos deben ser mayores a 1 y menores al totalde elementos para analizar.Después se tiene que elegir el tipo deecuación que utilizará el algoritmo k-modas,dentro de la aplicación, contando con lasopciones de ecuación 1 (binaria) o ecuación 2(xi-cuadrada).En caso de seleccionar la ecuación 2, sedeberá obtener las frecuencias de dominios parapoder continuar el proceso, dando clic en elbotón de Obtener frecuencias.Ahora se tendrá que seleccionar elmétodo de elección de modas iniciales, ya quedeben crearse una serie de modas para que apartir de ellas se genere el agrupamiento. Secuenta con las opciones de primeros kelementos y modas ficticias. A continuación semuestran los parámetros mencionados en laFigura 6.938Revista Tecnología e InnovaciónDiciembre 2015 Vol.2 No.5 929-941Presionarelbotónefectuaragrupamiento, para que se generen losresultados correspondientes, de acuerdo a losparámetros seleccionados. En esta parte terminael proceso que genera los grupos, para hacer usode estos hay que hacer clic en el menú ArchivoGuardar, con lo que se va a generar una carpetaque contiene 3 archivos de texto para utilizar losresultados agrupados.ResultadosDiseño de pruebasPara desarrollar las pruebas de la investigación,fue necesario utilizar diversos parámetros quedeterminan el rumbo del proceso y de losresultados.Se tendrá que elegir inicialmente unarchivo de texto que contenga los datos paraanalizar, después se debe asignar el número degrupos a formar (k), seleccionar el tipo deecuación (binaria o xi-cuadrada) y finalmente elmétodo para determinar las modas iniciales(primeros k-elementos o modas ficticias).De acuerdo a las opciones antesmencionadas, se presentará de maneraestructurada, las posibles combinaciones pararealizar las pruebas necesarias en el estudio, deacuerdo a la figura 7.Figura 6 Sección de parámetros de entradaFigura 7 Representación estructurada del diseño de laspruebas.ISSN-2410-3993ECORFAN Todos los derechos reservadosRENDÓN, Eréndira, ZEPEDA, Ricardo, BARRUETA, Elizabeth yITZEL-MARÍA, Abundez. El algoritmo de agrupamiento K-Modas: Uncaso de estudio. Revista de Tecnología e Innovación 2015

ArtículoDescripción de las pruebas realizadasEn esta sección se muestran los resultadosobtenidos al agrupar el archivo alumnos 145.txtcon la aplicación k-modas7, empleandodiferentes opciones de configuración, al elegir elnúmero de grupos a formar, el tipo de ecuacióny la forma de elección de modas iniciales.Para llevar a cabo las diversas pruebas,se utilizó principalmente un equipo DellInspiron 1420, con procesador Core2 Duo, unamemoria RAM de 2GB y un disco duro de 80GB.Resultados de las pruebasEn este apartado se describen los resultados delas pruebas desarrolladas, presentando una partede la tabla que contiene los parámetrosutilizados en la aplicación, así como los datosfinales del perfil del estudiante y la pureza de laagrupación. Ver Tabla 1.939Revista Tecnología e InnovaciónDiciembre 2015 Vol.2 No.5 929-941Para la aplicación que emplea elalgoritmo de agrupamiento k-modas. En la tabla1 se presentan los resultados de las tres mejorespruebas, las cuales obtuvieron la mejor purezade grupos.Apartirdelosexperimentosdesarrollados puede verse que en la pruebadonde k 4, la ecuación empleada es la binaria(ecuación 1) y el método de elección de modases primeros k elementos, que se encuentrantiene un porcentaje de los más altos en elestudio para los alumnos que si logran obtenerel título de Ingeniería en SistemasComputacionales (66 de 69 elementos),contando con una pureza de 95.65%. Para estaprueba el perfil de los estudiantes se describecon las siguientes características {Estado Civil Soltero, Edad 26, Trabajo No, DependientesEconómicos 0, Institución de procedencia Preparatoria Estatal, Tiempo de Egreso 5,Periodo de Ingreso Agosto – Diciembre 2003,Promedio 84, Titulo Si}.Para la prueba donde el número degrupos a formar (k) 5, ecuación 1 y primeros kelementos como modas iniciales, tiene unapureza de

El algoritmo de agrupamiento K Modas: Un caso de estudio. Revista de Tecnología e Innovación 2015 Ya que durante este periodo puede estar definida la continuidad de los estudios universitarios. En este estudio se divid