CLASIFICACION MEDIANTE K-MODAS PARA EL CASO DE ?· Como una ilustraci on del m etodo este fue aplicado…

  • Published on
    17-Feb-2019

  • View
    212

  • Download
    0

Embed Size (px)

Transcript

<p>CLASIFICACION MEDIANTE K-MODAS PARA EL CASODE VARIABLES CATEGORICAS</p> <p>Luisa Fernanda Pastran RamrezNataly Jineth Roa Pena</p> <p>Universidad del TolimaFacultad de Ciencias</p> <p>Departamento de Matematicas y EstadsticaIbague- TolimaFebrero 2015</p> <p>CLASIFICACION MEDIANTE K-MODAS PARA EL CASODE VARIABLES CATEGORICAS</p> <p>Luisa Fernanda Pastran Ramirez.Nataly Jineth Roa Pena.</p> <p>Trabajo de grado como requisito parcial para optar al ttulo deProfesional en Matematicas con Enfasis en Estadstica</p> <p>Director:Jairo Alfonso Clavijo</p> <p>Magister en Estadstica</p> <p>Universidad del TolimaFacultad de Ciencias</p> <p>Departamento de Matematicas y EstadsticaIbague - Tolima</p> <p>Febrero 2015</p> <p>Indice general</p> <p>Agradecimientos 5</p> <p>Resumen 7</p> <p>Introduccion 8</p> <p>Objetivos 9</p> <p>1. PRELIMINARES 121.1. Distribucion de probabilidad para Variables Categoricas . . . . 121.2. Clasificacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12</p> <p>1.2.1. Semejanza, similaridad, disimilaridad y medidas de di-similaridad . . . . . . . . . . . . . . . . . . . . . . . . 13</p> <p>1.3. Clasificacion Jerarquica . . . . . . . . . . . . . . . . . . . . . . 181.4. Clasificacion no Jerarquica . . . . . . . . . . . . . . . . . . . . 22</p> <p>1.4.1. Metodo de K-Means . . . . . . . . . . . . . . . . . . . 231.4.2. Nubes Dinamicas . . . . . . . . . . . . . . . . . . . . . 25</p> <p>2. CLASIFICACION CON VARIABLES CATEGORICAS 272.1. Variable categorica . . . . . . . . . . . . . . . . . . . . . . . . 272.2. Clasificacion de Variables Categoricas . . . . . . . . . . . . . . 292.3. Disimilaridad en variables categoricas . . . . . . . . . . . . . . 30</p> <p>2.3.1. Metodo de K-Modas . . . . . . . . . . . . . . . . . . . 362.3.2. Algoritmo de K-Modas . . . . . . . . . . . . . . . . . . 36</p> <p>3. APLICACION 383.1. Fases del Algoritmo de K-Modas . . . . . . . . . . . . . . . . 38</p> <p>3.1.1. Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . 46</p> <p>3</p> <p>INDICE GENERAL 4</p> <p>3.2. Estudio de un Caso Especfico . . . . . . . . . . . . . . . . . . 483.2.1. Resultados encuesta de salud . . . . . . . . . . . . . . 49</p> <p>4. CONCLUSIONES 54</p> <p>5. ANEXOS 555.1. Encuesta, Anexo 1: . . . . . . . . . . . . . . . . . . . . . . . . 55</p> <p>Bibliografa 60</p> <p>INDICE GENERAL 5</p> <p>Agradecimientos</p> <p>Agradecimientos Luisa Fernanda Pastran Ramrez</p> <p>Primeramente quiero dar gracias a Dios, por llenarme de sabidura, tran-</p> <p>quilidad, inteligencia, ser mi fortaleza en momentos de debilidad y por brin-</p> <p>darme tantos anos de aprendizaje, experiencias y felicidad.</p> <p>Gracias a mis padres Fermn y Amparo por estar conmigo en cada mo-</p> <p>mento que los necesitaba, por darme amor, animo y fuerza en los momentos</p> <p>que senta flaquear. Gracias por inculcarme tantos valores en el transcurso</p> <p>de mi vida.</p> <p>A mis hermanos Ricardo y Sandra, y a su esposo,por ser parte de mi</p> <p>vida, representar el amor sincero, la union familiar, apoyarme, y ademas, por</p> <p>ser mi ejemplo a seguir como personas y profesionales que son. Amis lindos</p> <p>sobrinos gracias por llenar mis das de felicidad.</p> <p>A todos los profesores de la UT, en especial, a los profesores Leonardo</p> <p>Solanilla, Jesus Avila, Maximiliano Machado y Horacio Molano,por cada en-</p> <p>senanza que me brindaron, por cada granito de arena que aportaron a mi</p> <p>formacion como profesional.</p> <p>Gracias a todos!!!</p> <p>Agradecimientos Nataly Jineth Roa Pena</p> <p>Hoy doy gracias a Dios y a mi familia que ha permitido con su apoyo en</p> <p>estos duros anos de carrera, en especial a mi madre que no solo con el apoyo</p> <p>INDICE GENERAL 6</p> <p>economico, sino tambien emocional en los momentos de tristeza y tambien</p> <p>en los momentos de alegra que han sido muchos mas, ella ah estado ah pa-</p> <p>ra m, ha mi esposo que con su ayuda academica ha sabido guiarme en las</p> <p>correcciones de este documento.</p> <p>Agradecimientos por las autoras</p> <p>Queremos agradecer a nuestro director de tesis Jairo Clavijo, quien siem-</p> <p>pre nos brindo su apoyo desde el da que le dijimos que queramos que fuera</p> <p>nuestro director. Gracias profesor por su paciencia y las ensenanzas da a da.</p> <p>Queremos dar las gracias especialmente al Ph.D. Hector Andres Granada</p> <p>Diaz por su gran apoyo en este proyecto de grado, el cual con su gran cono-</p> <p>cimiento, orientacion y paciencia, logramos la elaboracion del algoritmo, ya</p> <p>que el fue autor del codigo en Matlab.</p> <p>INDICE GENERAL 7</p> <p>Resumen</p> <p>El presente trabajo presenta un metodo particular para clasificar indi-</p> <p>viduos caracterizados por variables aleatorias de tipo categorico las cuales</p> <p>difieren sustancialmente de las variables numericas usualmente usadas para</p> <p>clasificar y formar conglomerados.</p> <p>La primera parte del trabajo esta dedicada a la presentacion de los ele-</p> <p>mentos basicos que rigen la teora de variables categoricas as como a la</p> <p>presentacion del metodo k-means que es el prototipo de tecnica utilizada con</p> <p>los cambios convenientes para manejar variables categoricas, dando origen al</p> <p>metodo de k-modas.</p> <p>La segunda parte proporciona la esencia del metodo k-modas al igual que</p> <p>el algoritmo que lo implementa y las rutinas de programacion necesarias para</p> <p>su aplicacion.</p> <p>Finalmente se aplica los temas anteriores a un caso particular de una</p> <p>muestra tomada en Empresas Prestadoras de Salud en el Tolima</p> <p>INDICE GENERAL 8</p> <p>Introduccion</p> <p>En el presente trabajo de grado se enuncian las acciones desarrolladas</p> <p>para realizar la clasificacion de variables categoricas mediante k-Modas. La</p> <p>teora expuesta en el trabajo se ilustra mediante la clasificacion realizada a</p> <p>una encuesta que se hizo en entidades de salud en Ibague y el Espinal.</p> <p>Debdo al caracter especial de las variables categoricas que no permiten</p> <p>operaciones aritmeticas, los metodos tradicionalmente usados para variables</p> <p>de tipo continuo no pueden ser implementados con variables categoricas, lo</p> <p>que hace necesario recurrir a otro tipo de herramientas, entre las cuales se</p> <p>puede citar el metodo de k-Modas, al que se dedica este trabajo.</p> <p>Como una ilustracion del metodo este fue aplicado a un caso particu-</p> <p>lar, en 3 entidades de salud (dos en Ibague y una en el Espinal) en las que,</p> <p>mediante preguntas de tipo categorico, se pretendio evaluar la calidad del</p> <p>servicio prestado. Se debe recalcar sin embargo, que el objetivo perseguido</p> <p>en el trabajo no fue la evaluacion del servicio sino la clasificacion de los en-</p> <p>cuestados.</p> <p>INDICE GENERAL 9</p> <p>Objetivo General</p> <p>Hacer una presentacion del metodo k-Modas como herramienta de clasi-</p> <p>ficacion para individuos caracterizados mediante variables categoricas.</p> <p>Objetivos Especficos</p> <p>1. Mostrar los fundamentos teoricos en que se basa el metodo k modas.</p> <p>2. Disenar y programar el algoritmo de clasificacion.</p> <p>3. Aplicar el metodo a una situacion concreta.</p> <p>Indice de figuras</p> <p>1.1. Ejemplo de clasificacion en la biologa . . . . . . . . . . . . . . 13</p> <p>1.2. Dendograma que muestra la clasificacion segun el metodo Sin-</p> <p>gle Linkage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22</p> <p>1.3. Esquema de agrupacion de K-MEANS . . . . . . . . . . . . . 24</p> <p>2.1. variables definidas sobre el individuo hj . . . . . . . . . . . . . 28</p> <p>2.2. Asignacion de valores de las caractersticas de la poblacion . . 32</p> <p>3.1. clasificacion de los elementos, grupo 1 . . . . . . . . . . . . . . 49</p> <p>3.2. clasificacion de los elementos, grupo 2 y grupo 3 . . . . . . . . 50</p> <p>3.3. Modas finales . . . . . . . . . . . . . . . . . . . . . . . . . . . 50</p> <p>10</p> <p>Indice de cuadros</p> <p>1.1. Indices de similaridad. . . . . . . . . . . . . . . . . . . . . . . . 15</p> <p>1.2. Valor de por parametros los cuales determinan casos particu-</p> <p>lares de Lance-Williams. . . . . . . . . . . . . . . . . . . . . . 20</p> <p>2.1. Tabla de poblacion . . . . . . . . . . . . . . . . . . . . . . . . 32</p> <p>2.2. Posibles distancias . . . . . . . . . . . . . . . . . . . . . . . . 34</p> <p>2.3. Posibles Modas . . . . . . . . . . . . . . . . . . . . . . . . . . 35</p> <p>5.1. Base de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . 58</p> <p>5.2. Base de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . 59</p> <p>11</p> <p>Captulo 1</p> <p>PRELIMINARES</p> <p>Este primer captulo muestra algunos conceptos basicos de la estadstica,</p> <p>aplicables a variables categoricas. Cabe resaltar que en la clasificacion el</p> <p>analisis exploratorio de datos y la Estadstica Multivariada juegan un papel</p> <p>muy importante.</p> <p>1.1. Distribucion de probabilidad para Varia-</p> <p>bles Categoricas</p> <p>Puesto que una variable categorica X asume valores de acuerdo con cier-</p> <p>to grado de probabilidad, pi, la suma de tales valores pi es igual a 1. En</p> <p>consecuencia , el valor 1 se distribuye entre las diferentes categoras. Por es-</p> <p>ta razon se dice que el conjunto {p1, p2, . . . , pk} forma una distribucion deprobabilidad para X. Si X tiene k categoras C1, C2, . . . , Ck,se acostumbra a</p> <p>escribir P (X = Ci) = pi, con lo cual se indicara como es la funcion f() dedistribucion.</p> <p>1.2. Clasificacion</p> <p>Clasificar es una actividad frecuente en la que se busca organizar un</p> <p>conjunto de elementos en grupos caracterizados por una alta homogeneidad</p> <p>12</p> <p>CAPITULO 1. PRELIMINARES 13</p> <p>o semejanza en su interior, y a la vez una gran diferenciacion entre grupos</p> <p>distintos. Un ejemplo tpico de clasificacion se da en biologa como lo muestra</p> <p>en la Figura 1 1:</p> <p>Figura 1.1: Ejemplo de clasificacion en la biologa</p> <p>Una clasificacion se dice jerarquica si en ella esta explcito el orden o</p> <p>jerarqua en el que se agrupan los individuos vistos como conglomerados y</p> <p>es no jerarquica cuando es una simple particion de un conjunto.</p> <p>1.2.1. Semejanza, similaridad, disimilaridad y medidas</p> <p>de disimilaridad</p> <p>De acuerdo con lo anterior, la clasificacion de individuos se basa en una</p> <p>medida de la semejanza que hay entre ellos. Se han ideado varias formas de</p> <p>medir la similaridad o similitud entre individuos, basados en los valores que</p> <p>tomen algunas variables observadas sobre ellos. [3]</p> <p>En general una similaridad en H es una funcion S : H H R+ quecumple:</p> <p>(i, j) HxH</p> <p>S(i.j) = S(j, i),i, j H</p> <p>CAPITULO 1. PRELIMINARES 14</p> <p>S(j.j) = S(i, i) = M</p> <p>donde M es el maximo valor de similaridad casi siempre, M = 1.</p> <p>Dada una similaridad en H se define automaticamente una disimilardad</p> <p>en H mediante la formula:</p> <p>d(i, j) = M S(i, j)</p> <p>Y se cumple:</p> <p>i H, d(i, i) = 0</p> <p>d(i, i) &gt; 0</p> <p>d(i, j) = d(j, i)</p> <p>Dado un conjunto de individuos H = {h1, h2, . . . , hn} se define la matrizde distancias (o disimilaridades) como:</p> <p>D = (di,j)nn donde di,j = d(hi, hj), i, j. Esto es:</p> <p>D=</p> <p>h1 h2 . . . hj . . . hn</p> <p>h1 d11 d12 . . . d1j . . . d1n</p> <p>h2 d21 d22 . . . d2j . . . d2n...</p> <p>hj dj1 dj2 . . . dij . . . din...</p> <p>hn dn1 dn2 . . . dnj . . . dnn</p> <p>Donde D es claramente una matriz simetrica, ya que di,j = d(hi, hj) =</p> <p>d(hj, hi) = dj,i</p> <p>CAPITULO 1. PRELIMINARES 15</p> <p>En el caso particular en que di,j sean distancia se cumple las siguientes</p> <p>propiedades:</p> <p>d(i, j) 0; d(i, j) = 0 si y solamente si i = j</p> <p>d(i, j) = d(j, i), i, j I</p> <p>d(i, j) d(i, k) + d(k, j), i, j, k H</p> <p>En el caso mas general de que di,j sea una disimilaridad no se puede garan-</p> <p>tizar el cumplimiento de la tercera propiedad, en estos casos dos individuos</p> <p>i, j son mas cercanos o mas parecidos cuanto mas pequeno sea el valor d(i, j).</p> <p>Nota: Una forma muy frecuente de definir similaridades y por tanto,</p> <p>disimilaridades, es el uso de ndices de similaridad, como los que se mencionan</p> <p>el cuadro 1 1:</p> <p>INDICES En terminos de a,b,c</p> <p>Jaccard aa+b+c</p> <p>Sorensen; Dice 2a2a+b+c</p> <p>Ochiai a[(a+b)(a+c)]1/2</p> <p>Russel-Rao aa+b+c+d</p> <p>Sokal- Sneath 1 2(a+d)2(a+d)+b+c</p> <p>Sokal- Sneath 2 aa+2(b+c)</p> <p>Sokal- Sneath 3 a+db+c</p> <p>Cuadro 1.1: Indices de similaridad.</p> <p>Tomando a el numero de caractersticas comunes entre los objetos i y j;</p> <p>b el numero de caractersticas i que no tiene j; c el numero de caractersticas</p> <p>j que no tiene i; d el numero de caractersticas de ninguno.</p> <p>CAPITULO 1. PRELIMINARES 16</p> <p>De acuerdo con lo dicho anteriormente se concluye que toda distancia es</p> <p>una disimilaridad mas no al contrario. La notacion de distancia entre indi-</p> <p>viduos puede generalizarse a conjuntos, lo que resulta util en el momento de</p> <p>fusionardos conglomeados para formar uno nuevo. Los casos mas utiliza-</p> <p>dos de distancias entre grupos se definen mediante las distancias entre sus</p> <p>elementos, de acuerdo con las formulas siguientes:</p> <p>Single Linkage (Vecino mas cercano) Este metodo consiste en unir</p> <p>los grupos considerando la menor de las distancias existentes entre los</p> <p>objetos mas cercanos de distintos grupos. Es decir, mide la proximidad</p> <p>entre dos grupos calculando la distancia entre sus objetos mas proximos</p> <p>o la similitud entre sus objetos mas semejantes [1].</p> <p>d(A,B) = min{d(a, b)/a A, b B} (1.1)</p> <p>Complete Linkage (Enlace completo): En este metodo los grupos</p> <p>se unen considerando la mayor de las distancias existentes entre los</p> <p>miembros mas lejanos de los dos conjuntos [1].</p> <p>d(A,B) = max{d(a, b)/a A, b B} (1.2)</p> <p>CAPITULO 1. PRELIMINARES 17</p> <p>Centroide Linkage (Centroide): En este metodo, la distancia entre</p> <p>dos grupos esta dada por la distancia (usualmente la distancia eucldea</p> <p>o eucldea cuadrada) entre sus centros o centroides. Los centroides de</p> <p>los grupos corresponden a la media o el promedio del grupo [1].</p> <p>d(A,B) = d(a, b) (1.3)</p> <p>Average Linkage (Promedio): Se unen los grupos cuya distancia</p> <p>entre los grupos se define como el promedio de las distancias entre</p> <p>sus elementoss, este metodo no depende de un par de elementos extre-</p> <p>mos.[1]</p> <p>d(A,B) =1</p> <p>nAnB</p> <p>aAbB</p> <p>d(a, b) (1.4)</p> <p>CAPITULO 1. PRELIMINARES 18</p> <p>Ward: Con frecuencia se usa tambien la distancia de ward, basada en</p> <p>la variabilidad ENTRE y DENTRO. Este metodo agrupa elementos de</p> <p>modo que se minimice una determinada funcion objetivo que por lo</p> <p>general es la suma de las distancias cuadradas intra-grupo [1].</p> <p>SSEA =</p> <p>nAi=1</p> <p>(yi yA)(yi yA) (1.5)</p> <p>SSEB =</p> <p>nBi=1</p> <p>(yi yB)(yi yB) (1.6)</p> <p>SSEAB =</p> <p>nABi=1</p> <p>(yi yAB)(yi yAB) (1.7)</p> <p>1.3. Clasificacion Jerarquica</p> <p>La clasificacion jerarquica es util cuando el numero de individuos a cla-</p> <p>sificar es relativamente pequeno. Podemos saber que tan separados estan los</p> <p>grupos como los individuos, mediante dendogramas.</p> <p>Estos metodos tienen por objetivo agrupar clusters para formar uno nue-</p> <p>vo o bien separar alguno ya existente para dar origen a otros dos, de tal forma</p> <p>que se minimice alguna funcion de distancia o bien se maximice alguna me-</p> <p>CAPITULO 1. PRELIMINARES 19</p> <p>dida de similitud.</p> <p>Los metodos jerarquicos se subdividen a su vez en aglomerativos y di-</p> <p>sociativos. Los aglomerativos comienzan el analisis con tantos grupos como</p> <p>individuos haya en el estudio, a partir de ah, se van formando grupos de</p> <p>forma ascendente, hasta que al final del proceso, todos los casos...</p>