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.

Normalmente el usuario tiene  una  buena  capacidad de for- mar  las  clases  y se han  desarrollado herramientas visuales interactivas para ayudar al usuario.

An´alisis de  dependencias: El valor de un elemento  puede usarse  para  predecir el valor de otro. La dependencia puede ser  probabil´ıstica,  puede  denir una  red de  dependencias  o puede  ser  funcional (leyes  fsicas). Tambien se ha  enfocado a  encontrar si  existe  una  alta  proporcion de valores de al- gunos atributos que ocurren con cierta medida  de confianza junto  con valores de otros  atributos. Se pueden  utilizar  redes bayesianas, redes causales, y reglas de asociacion.

Detecci´on  de  desviaciones, casos extremos o  anoma- l´ıas: Detectar los cambios  mas  signicativos en los datos  con respecto a valores pasados  o normales. Sirve para filtrar grandes volu´menes  de datos  que son  menos  probables de ser intere- santes. El problema  esta en determinar cuando  una desviacio´n es signicativa para ser de interes.

Aprendizaje de   cual es   la mejor  acci´on  a tomar a partir de  experiencia: Esto  involucra bu´squeda y explo- racion del  ambiente. Esto  esta  relacionado principalmente con aprendizaje por refuerzo, pero tambit’rn con t´ecnicas co- mo aprendizaje de macro-operadores, chunking  y EBL.

Optimizaci´on y  bu´squeda: Existen  una  gran  cantidad de algoritmos de bu´squeda tanto  determin´ıstica como aleatoria, individual   como  poblacional, local  como  global,  que  se  uti- lizan  principalmente para resolver algu´n problema de  opti- mizacio´n. Aqu´ı podemos  incluir a  los algoritmos gen´eticos, recocido simulado, ant-colony,  tecnicas  de  busqueda  local, etc.

3.   TIPOS DE APRENDIZAJE

Aprendizaje  inductivo: Creamos modelos  de conceptos a partir de  generalizar ejemplos  simples.  Buscamos patrones comunes   que  expliquen  los  ejemplos.  Se  basa  en  el razon- amiento inductivo:

...