ia aprendizaje no supervisado

Aprendizaje No-Supervisado

Inteligencia Artificial

Profesor: Alejandro Figueroa

Conceptos Bsicos

En algunas ocasiones no tenemos las clases asociadas en los datos de entrenamiento.

Pero an as queremos encontrar estructuras intrnsecas en los datos.

Clustering es un mtodo para lograr sto.

Clustering es llamado aprendizaje no-supervizado, sin embargo, no es lo nico que es llamado as.

Conceptos Bsicos

Clustering consiste en organizar los datos en grupos cuyos miembros son parecidos de alguna forma.

Es decir, un clster es un conjunto de datos que son similares de alguna forma, y a su vez son disimiles a los ejemplos contenidos en otros clsteres.

En la jerga de clustering, cada instancia en los datos es llamada objeto o data point.

Conceptos Bsicos

Conceptos Bsicos

Hay dos tipos de clustering: particional y jerrquico.

La idea es agrupaciones intrnsecas de los datos de entradas mediante el uso de un algoritmo de clustering y una medida de distancia.

Clustering Particional: K-means

Es simple y eficiente.

Dado un nmero de k de clsteres y un conjunto de datos, este algoritmo particionaiterativamente los datos en los k clsteres de acuerdo a una medida de distancia.

Supongamos que tenemos un conjunto de datos D={x1,x2,x3,,xn}, donde xi=(xi1,xi2,,xir) es un vector de valores reales Xr. Donde r es el nmero de atributos.


Cada clster tiene un centro, llamado centroid, que representa al clster.

El centroid es la media de todos los puntos dentro del clster.

Al comienzo el algoritmo escoge k datos como los centroides semilla.

Despus, calcula la distancia de centroidesemilla con cada dato. Cada dato es asignado al centroide que est ms cerca.


Despus que todos los datos son asignados, el centroide de cada clster es re-calculado utilizando los datos en cada clster.

El proceso se repite hasta una condicin de trmino: No hay ms, o muy pocas, re-asignaciones de datos a

otros clsteres. Es decir, no ha mucho movimiento. No hay ms, o muy pequeo, cambio en los

centroides. Muy poca disminucin en la suma del error cuadrtico

(SSE).


La suma del error cuadrtico se define como:

Donde k es el nmero de clsteres requeridos, Cj es el j-simo clster, mj es el centroide de Cjy dist(x,mj) es la distancia entre x y mj.

El centroide es el vector de medias de todos los datos en Cj.

k

j Cx

j

j

mxdistSSE1

2),(


En el espacio euclidiano, la media de es calculada como:

Donde |Cj| es la cantidad de puntos en Cj. La distancia desde un punto xj al centroide mj se calcula:

jj Cx

i

j

j xC

m1

22

22

2

11 )(...)()(),( jrirjijiji mxmxmxmxdist


Al comienzo se escogen k centroidesaleatoriamente:


Se asigna cada punto a uno de los dos clsteres:


Los centroides se re-calculan:


Los puntos se re-asignan:


Se recalculan los centroides:


Se re-asignan los puntos:


Se recalculan los centroides:


Clsteres vacios:

Durante el proceso algn clster puede quedar vacio.

Se utiliza un data point como el centroid de reemplazo, e.g., el que este ms lejos del otro centroid.

Si se utiliza SSE, se puede escoger el punto que minimiza el error.

Es un problema de K-means.


Las principales ventajas de K-means:

Es simple y eficiente.

Es fcil de entender y de implementar.

Su complejidad es O(tkn), donde n es el nmero de datos, k el de clsteres y t el nmero de iteraciones.

Dado que k y t son pequeos, normalmente, se considera un algoritmo lineal con respecto al tamao del conjunto de datos.


Otras debilidades: Es necesario tener definido el concepto de media.

Por ende, hay un problema con atributos basados en categoras. Hay una variacin llamada k-modes, que utiliza la moda en vez de la media. Entonces, cada componente es el valor ms frecuente de cada atributo, y la distancia es el nmero de atributo-valor que coinciden.

Muchas veces no se sabe el valor de k de ante-mano

El algoritmo es sensible a outliers.


Una forma de lidiar con los outliers es remover los puntos que estn ms lejos de los centroides que otros puntos.

Es primordial esperar varias iteraciones antes de remover un punto, porque podra ser un clster pequeo de puntos.

Se puede utilizar una cota.


Otra forma de combatir los outliers es randomsampling: Se escoge un pequeo subconjunto de los datos.

Se hace aleatoriamente.

Se utiliza este subconjunto para calcular los centroides.

Despus se aaden el resto de los puntos: Al centroide ms cercano, o

Utilizar los clsteres para hacer aprendizaje supervisado y etiquetar el resto de los puntos.

Usar los clsteres como semillas para aprendizaje semi-supervisado.


Una rpida resea a lo que es aprendizaje semi-supervisado.

Es un paradigma que aprende de un conjunto reducido de ejemplos etiquetados y de un conjunto grande de datos no etiquetados.

Otro problema de K-means son las semillas iniciales:

Diferentes semillas pueden terminar en diferentes centroides alcanzando un ptimo local.


Hay varios mtodos para escoger semillas iniciales:

Calcular el centroide del conjunto completo de datos. Se escoge el punto ms lejano al centroide, y despus se escoge el punto ms lejano al previamente escogido, as sucesivamente. Este mtodo no funciona bien con outliers.


En la prctica, frecuentemente resulta fcil para los humanos escoger las semillas. Por ejemplo, data points que son muy diferentes.

K-means no funciona bien cuando hay que descubrir datos que son hiper-esferas.

Clustering Jerrquico

Produce un rbol, tambin llamado dendrogram(a), que consiste en un conjunto de clsteres anidados.

Los datapoint estn en las hojas del rbol, y el rbol parte con un nico nodo llamado raz.

Cada nodo del rbol tiene hijos, y cada hermano particiona los datos que tiene el padre.


Hay dos tipos:

Agglomerativos (bottom-up): Construye el rbol mediante la amalgama de los clsteres ms cercanos. As sube niveles en el rbol. Es el mtodo ms usado

Divise (top-down): Parte con todos los datos en un clster, la raz. Divide los nodos en hijos sucesivamente, hasta alcanzar clsteres de puntos individuales.


Agglomerative (D)

1. Hacer de cada data point un clster.

2. Calcular todas las distancias entre los puntos en D

3. Repetir

1. Encontrar los dos clsteres que estn ms cerca.

2. Unirlos para formar un nuevo clster C.

3. Calcular la distancia de C a todos los clsteres.

4. Hasta que haya un solo clster.


Para calcular la distancia entre dos clsteres:

Single-Link

Complete-Link

Average-Link


Single-Link:

La distancia entre dos clsteres es la distancia de los dos puntos ms cercanos.

Bueno para encontrar clsteres de forma no-eliptica.

Es sensible a datos ruidoso.

La complejidad es O(n2), con n el nmero de datos.


Complete-Link:

Une dos clsteres tal que su distancia mxima es la mnima entre todos los clsteres.

No tiene el problema de los datos ruidosos, pero tiene el problema de los outliers.

En general, produce mejores resultados que el mtodo de Single-Link.

La complejidad es O(n2log n), con n como el nmero de datos.


Average-Link: La distancia es el promedio entre todos los pares de

puntos de un clster.

La complejidad es O(n2log n), con n como el nmero de datos.

Otros mtodos: Centroid: la distancia est dada por el centroide de los

dos clsteres.

Ward: Se amalgama los clsteres que incrementan el error de menor forma. El error (SSE) se calcula como la diferencia entre el clster nuevo y los que se une.


Clustering jerrquico tiene las ventajas: Puede tomar cualquier mtrica de distancia.

No tiene un k definido, es decir puede explorar cualquier nivel de granularidad.

Clster jerrquico agglomerativo produce generalmente los mejores resultados.

Las desventajas: Son ms complejos computacionalmente.

Ineficiente y poco prctico para conjuntos de datos muy grandes.


Alguna veces se puede aplicar mtodos de escalamiento (scale-up methods) para combatir el problema con los conjuntos de datos muy grandes.

La idea es encontrar en primera instancia muchos clsteres pequeos utilizando un algoritmo eficiente.

Despus se utiliza el centroide de esos clsteres para representar los clsteres, y de ah ejecutar el clustering jerrquico final.


Permite ver las agrupaciones a diferentes niveles, es decir podemos cortar a diferentes niveles el rbol y ver cmo se van formando los clsteres.

Cada nivel utiliza un nmero diferente de clsteres.

Agrupa instancias de acuerdo a cmo sus similitudes los conectan entre ellos.

Los outliers tienden a unirse muy tarde cuando hacemos clustering agglomerativo, entonces se vern aislados hasta niveles muy altos del rbol.


http://itol.embl.de/itol.cgi

Clustering jerrquico para un grupo de whiskies escoses de malta.Se puede ver que si se corta el dendograma de manera vertical, se ven los distintos grupos que se forman.El orden de los nombres es arbitrario.Datos en: http://adn.biol.umontreal.ca/~numericalecology/data/scotch.html

Funciones de Distancia

Para atributos numricos:

Minkowski

Euclidean

Manhattan

Weighted Euclidean

Squared Euclidean

Chebychev


La distancia de Minkowski de dos puntos xi y xj (h es un entero positivo) de r-dimensiones:

Si h=1, tenemos la distancia de Manhattan.

Si h=2, tenemos la distancia euclidiana.

hh

jrir

h

jiji xxxxxxdist ...),( 11


La distancia Manhattan toma su nombre porque es la distancia que se necesita (en trminos de nmero de cuadras) para viajar desde un punto a otro en una ciudad que tiene forma de grilla como Manhattan o el plano de Via del Mar.

La distancia total es una combinacin de las cuadras este-oeste y norte-sur caminadas.

Fuente: Wikipedia


La distancia euclidiana con pesos est dada por :

Esta distancia le asocia un peso/importancia a cada atributo.

La distancia euclidiana al cuadrado:

La idea es ubicar pesos ms grande de manera progresiva en puntos que estn ms separados.

2 22

111 )(...)(),( jrirrjiji xxwxxwxxdist

22

11 )(...)(),( jrirjiji xxxxxxdist


La distancia de Chebychev:

Esta distancia intenta acrecentar el contraste de puntos que tienen cualquier atributo diferente.

),...,max(),( 11 jrirjiji xxxxxxdist

Ejemplo

Si X1 es (1,3) y X2 es (5,6), entonces:

Minkowski:

Si consideramos w1=0.1 y w2=0.2 como los pesos de los features X1 y X2 respectivamente, tendramos como distancia euclidiana con pesos:

9,5393920191343

525342

77341

12),(

33 33

22 22

11 11

21

h

h

h

xxdist h hh

1,843908893*2.04*1.0),( 2 2221 xxdist

Ejemplo


Euclidiana al cuadrado:

La distancia de Chebychev sera el mximo entre 4 y 3, es decir 4.

Basta con que haya un atributo muy diferente para que la distancia sea grande, an cuando el resto tengan el mismo valor. Ergo, debe ser usada con cuidado.

2534),( 2221 xxdist

Otras Funciones de Distancia

Otras funciones menos conocidas:

Canberra

Squared Cord

Squared Chi-squared

jrir

jrir

ji

ji

jixx

xx

xx

xxxxdist

||...

||),(

11

11

22

11 )(...)(),( jrirjiji xxxxxxdist

jrir

jrir

ji

ji

jixx

xx

xx

xxxxdist

2

11

2

11 )(...

)(),(

Ejemplo


Canberra:

Squared Cord:

Squared Xi-squared:

154

54

54

1836

9

3

6

4

6,59

3

6

4 22

2,042582670,58144723)4-0,7174389(8)-1,2360679()63()51( 2222

Atributos Heterogneos

Si los atributos son numricos, las frmulas de distancias se aplican de manera directa.

Pero cuando los vectores tienen datos de tipos heterogneos el asunto se puede complicar:

Feature/Atributo Persona A Persona B

Gnero Masculino Femenino

Edad 23 40

Aos en la residencia actual 2 10

Estado residencial (1-propietario; 2-Inquilino; 3-Otro 2 1

Ingreso 50,000 90,000

Atributos Heterogneos

Este ejemplo nos muestra varios problemas con el clculo de la distancia: El atributo gnero es simblico (binario o

categrico). Para un atributo binario tal vez sea suficiente usar 0s y 1s, pero no si tiene mltiples valores.

La edad puede fluctuar entre 18 y 100, pero el ingreso no. El problema que una diferencia de 10 dlares sera tan significante como 10 aos de edad.


Otros tipos de atributos:

Binarios: Por ejemplo, el genero (masculino y femenino). Normalmente no hay una relacin de orden. Las mtricas se basan en la proporcin de coincidencias en los valores: ambos falsos o verdaderos.


Otros tipos de atributos (binario):

Simtricos: si ambos estados tienen la misma importancia, por ende tienen el mismo peso. La funcin de distancia ms usada es la distancia de simple coincidencias:

dcba

cbxxdist ji

),(


Ejemplo:

x1 1 1 1 0 1 0 0

x2 0 1 1 0 0 1 1

57.07

4

2122

22),(

ji xxdist


Otros tipos de atributos (binario):

Asimtricos: Si un valor es ms importante que el otro. Por convencin, se toma como el positivo (1) como el estado ms importante o raro. Una distancia que se puede utilizar es la Jaccard:

)(

)(),(

12

1

cbwaw

cbwxxdist ji

w1 y w2 son pesos que se le pueden dar a las no-coincidencias. En general, ambos son 1.


Ntese que tambin existe el coeficiente Jaccard que mide la similitud y no la distancia: a/(a+b+c).

Para atributos nominales con ms de dos estados o valores, la medida de distancia ms usada tambin basada en la distancia de coincidencias simples. Dado dos puntos xi y xj, el nmero de atributos r, y

q el nmero de valores que coinciden entre xi y xj:

r

qrxxdist ji

),(


Supongamos dos vectores de r=4 atributos X1={0,naranja, true, 1} y X2={1,naranja, falso, 0}

El valor de q entre estos dos vectores es 1, porque slo el atributo naranja coincide.

Por consiguiente, el valor de la fraccin es .

De esta misma forma, la distancia es .

Estandarizacin de Datos

La idea de estandarizacin es que todos los atributos puedan tener igual impacto en el cmputo de la distancia.

En especial, cuando se usa la distancia euclidiana.

El objetivo es prevenir que hayan clsteres dominados por atributos con una alta variacin.


Ejemplo: En un conjunto de dos dimensiones, el rango de un atributo es de cero a uno, mientras el rango del otro atributo es de 0 a 1000. Considere los siguientes data points:

Xi: (0.1,20)

Xj:(0.9,720)

La distancia euclidiana entre dos puntos es:

000457.700)20720()1.09.0(),( 22 ji xxdist


En el ejemplo vemos que la distancia est casi completamente dominada por (720-20)=700.

Lo que se hace es estandarizar los atributos, es decir que todos estn en el rango 0 a 1.

Entonces los valores 20 y 720 se transforman en 0.02 y 0.72.

La distancia en la primera dimensin se transforma en 0.8 y en la segunda 0.7.

Por ende, la dist(xi,xj)=1.063.


Este tipo de fenmeno tambin afecta a una representacin como la de bolsa de palabras. Una representacin donde cada palabra representa un

atributo, y el valor de ese atributo es la frecuencia en el documento.

Supongamos que tenemos los siguientes tres documentos: Doc 1={a=100, the=100, ball=5, nadal=10, net=2, win=2} Doc 2={a=95, the=102, ball=7, federer=8, net=3, win=3} Doc 3={a=98, the=102, phone=8, call=5, cost=3}

En trminos de distancia euclidiana, Cul par est ms cerca?


Vemos que al eliminar los stopwords, quedamos con vectores que tienen atributos que se mueven en intervalos de valores similares.


Atributos que representan escalas en intervalos:

Continuos y numricos.

Nmeros reales que siguen una escala.

E.g., edad, alto, peso, costo, etc.

La diferencia en edad oscila 10 y 20 es la misma que entre 40 y 50.

Hay dos tcnicas: range y z-score.


Range divide cada valor por el rango de valores vlidos de los atributos talque los rangos de los valores transformados estn entre 0 y 1.

Dado el valor xif del f-simo atributo del i-simo data point, el nuevo valor rg(xif) es,

)min()max(

)min()(

ff

fxxrg

if

if


Donde min(f) y max(f) son el mnimo y mximo valor posible del atributo.

Ergo, max(f)-min(f) es el rango de valores vlidos del atributo f. Calcular el rango de acuerdo a los valores posibles o los

mximos y mnimos vistos en los datos?

El mtodo de z-score transforma el valor de un atributo basado en la media y en la desviacin estndar del atributo.

El z-score indica cual lejos y en qu direccin el valor se desva desde la media del atributo, expresado en unidades de la desviacin estndar del atributo.


La desviacin estndar de f, denotada por f, se calcula mediante:

Donde n es el nmero de data points en el conjunto de datos, y uf es la media del atributo f:

1

)(1

2

n

xn

i

fif

f

n

i

iff xn 1

1


Entonces, el nuevo valor despus de la transformacin:

Si consideramos la bolsas de palabras como atributos a intervalos (en estricto rigor no los son, pero slo con efectos ilustrativos):

f

fif

if

xxz

)(


Atributos que representan escalas en radios:

Numricos que toman valores reales.

Al contrario de los atributos anteriores, las escalas no son lineales.

Por ejemplo los atributos que crecen exponencialmente: AeBt (A y B son constantes positivas),


Para este tipo de atributo, tenemos dos opciones:

Aunque no es recomendable, tratarlo como atributos que representan escalas en intervalos.

Desarrollar una transformacin logartmica para cada valor xif, i.e., log(xif). Despus de la transformacin, el atributo puede ser tratado con un atributo que representa escalas en intervalos.


Atributos nominales: el valor puede tomar cualquier estado dentro de un conjunto. Normalmente, no tienen lgica o orden numrico.

Por ejemplo el atributo fruta puede tener los siguientes valores posibles: manzana, naranja, y pera. Estos atributos no tienen orden.

Un atributo binario es un caso especial de atributo nominal con dos estados.


Se pueden convertir a un conjunto de atributos binarios.

Por ejemplo, para el atributo nominal fruta, podemos crear tres atributos binarios: manzana, naranja y pera en los datos nuevos. Si en particular un dato original tiene manzana como fruta, entonces en los datos transformados, se asigna al set al valor manzana como uno, y el valor de los otros atributos un cero.


Atributos ordinales son como los atributos nominales.

Por ejemplo, el atributo edad puede tener valores: joven, mediana edad y viejo.

Lo comn es tratarlos atributos que representan escalas en intervalos.

ia aprendizaje no supervisado

Documents