ALGORITMOS DE APRENDIZAJE: KNN & KMEANS

ALGORITMOS DE APRENDIZAJE: KNN &  KMEANS

[Inteligencia  en Redes de Telecomuncicación]

Cristina García Cambronero

Universidad Carlos  III de Madrid

10003897@alumnos.uc3m.es

Irene Gómez Moreno

Universidad Carlos  III de Madrid

100039000@alumnos.uc3m.es

En el siguiente  trabajo, vamos a tratar el tema  del aprendiza- je. En  primer lugar  definiremos este concepto  y veremos los tipos de aprendizaje que existen y las clasificaciones que den- tro de este se pueden  realizar. A continuacio´n analizaremos mas profundamente el aprendizaje inductivo, explicando  me- diante  conceptos  teo´ricos y ejemplos  las caracter´ısticas fun- damentales del aprendizaje inductivo  supervisado (K-NN) y aprendizaje inductivo  no supervisado (K-MEANS).

1.   INTRODUCCION

Una  de las tareas m´as desafiantes en la ciencia  de la com- putacio´n es construir ma´quinas o programas de computado- ras que sean  capaces  de aprender. El darles  la capacidad de aprendizaje a las ma´quinas abre una  amplia  gama de nuevas aplicaciones. El entender tambi´en como estas  pueden  apren- der  nos  puede  ayudar a  entender las  capacidades y limita- ciones  humanas de aprendizaje.

Algunas  definiciones de ’aprendizaje’ son:

Cambios adaptivos en  el  sistema para hacer la  mis- ma tarea de  la  misma poblacion de  una manera mas eficiente y efectiva la pr´oxima  vez  [Simon, 83].

Un programa de  computadora se  dice que  aprende de experiencia E  con respecto a una clase de  tareas T y  medida de  desempen˜o  D, si su   desempen˜o  en   las tareas en  T, medidas con D, mejoran con experiencia E  [Mitchell, 97].

En  general, se  busca  construir programas que mejoren au- toma´ticamente con la experiencia.

El aprendizaje no s´olo se encarga de obtener  el conocimiento, sino  tambi´en la forma  en que ´este se representa. A contin- uaci´on se definen  tres conceptos  basicos  bajo este  contexto:

1.1   Conceptos básicos

[pic 1]

Figure  1:

1.  Conjunto de  datos: Se distinguen dos tipos,  el con- junto  de entrenamiento y el conjunto de prueba.  Para obtener estos,  dividimos  los  datos  muestrales en  dos partes; una  parte se  utiliza  como  conjunto de  entre- namiento para  determinar los  para´metros  del clasifi- cador  y la otra parte, llamada  conjunto de prueba  (o´ test  o´  conjunto de generalizacio´n)  se utiliza  para esti- mar  el error de generalizacio´n  ya que el objetivo  final es que el clasificador consiga un error de generalizaci´on pequen˜o evitando  el sobreajuste (o´ sobre-entrenamiento), que  consiste   en  una  sobrevaloraci´on  de  la  capacidad predictiva de los modelos obtenidos:  en esencia, no tiene sentido  evaluar la  calidad  del modelo  sobre los datos que  han  servido  para   construirlo ya  que  esta  pra´cti- ca  nos  lleva a  ser  demasiado optimistas acerca de su calidad.

La  p´erdida  de la capacidad de generalizacio´n  conlleva un comportamiento no deseado  (Ver  Figura 1).

El conjunto de entrenamiento suele a su vez dividirse en  conjuntos  de  entrenamiento  (propiamente  dicho) y conjunto de validacio´n para  ajustar el modelo  (Ver Figura 2).

Se suelen  utilizar  el 80 % de los datos  para  entrenar a la ma´quina,  el 10 % como  conjunto de validaci´on  y el

10 % restante para estimar la generalizaci´on  (pero  es so´lo un criterio orientativo).

2.  Modelo: o clasificador, es una conexi´on entre  las vari- ables que son dadas  y las que se van a predecir. Usual- mente  las variables que se van a predecir denominadas

[pic 2]

Figure  2:

[pic 3]

Figure 3:  Modelo de Aprendiza je

variables dependientes y las  restantes, variables  inde- pendientes.

3.  Aprendiz: (en  ingles  ”learner”): es cualquier proced- imiento utilizado  para construir un modelo a partir del conjunto de datos  de entrenamiento.

Desde  el punto  de vista  t´ecnico,  el aprendizaje se de- fine como el proceso  mediante el cual un sistema mejo- ra y adquiere  destreza en la ejecucio´n de sus tareas, y tiene  la capacidad de poseer inferencia inductiva sobre

´estas. Un  modelo  de aprendizaje puede  caracterizarse por  dos  cuerpos   de  informaci´on: ambiente y base  de conocimiento, y por dos  procedimientos: elemento  de aprendizaje (aprendiz) y elemento  de  ejecucio´n (pro- grama  de computacio´n), tal y como se representa en la siguiente  figura:

2.   CLASIFICACIÓN

Existen   diversas   tareas que  se  pueden  hacer   con  sistemas de aprendizaje. Entre ellas podemos  en general  clasificarlas como sigue:

Descripci´on: normalmente es usada  como analisis prelimi- nar de los datos  (resumen, caracter´ısticas de los datos,  casos extremos, etc.). Con  esto,  el usuario se sensibiliza  con  los datos  y su estructura. Busca  derivar descripciones concisas de caracter´ısticas de los datos  (e.g.,  medias, desviaciones es- tandares, etc.).

La Predicci´on  la podemos  dividir en  dos:  Clasicaci´on  y

Estimaci´on.

Clasificaci´on: Los datos son objetos caracterizados por atrib- utos que pertenecen a diferentes clases  (etiquetas discretas). La meta  es inducir un modelo para poder  predecir una  clase dados  los valores  de los atributos. Se usan  por ejemplo,  ar- boles de decisi´on, reglas, analisis de discriminantes, etc.

Estimaci´on o Regresi´on: las clases son continuas. La meta es inducir un modelo para poder  predecir el valor de la clase

dados  los valores  de los atributos. Se usan  por ejemplo,  ar- boles de regresi´on,  regresio´n  lineal,  redes neuronales, kNN, etc.

Segmentaci´on: separacio´n de los datos en subgrupos o clases interesantes.  Las  clases  pueden   ser  exhaustivas  y  mutua- mente  exclusivas  o jerarquicas y con traslapes. Se puede uti- lizar con otras tecnicas de minera de datos:  considerar cada subgrupo  de datos  por separado, etiquetarlos y utilizar un al- goritmo de clasificacion. Se usan  algoritmos de clustering, SOM  (self-organization maps),  EM(expectation maximiza- tion), k-means, etc.

...