Information Entropy y k-means

Hace un par de semanas me encontre con la medida de la entropia de Shannon. Es simplemente esta formula:

I = -∑p_i*ln₂(p_i) donde p_i = N_i / N

N es la cantidad de elementos en todo el conjunto, y N_i es la cantidad de elementos en cada uno de los k i-subconjuntos

Parece una formula simple, pero en realidad, simplemente mirandola, no podia entender su significado.

En principio parece una esperanza, en particular, la -E(ln₂p_i), esto seria algo asi como la cantidad de bits necesarios para representar, en promedio, los elementos existentes en cada uno de los i grupos.

Pero seguia sin decirme demasiado, asi que gracias a la ayuda de Manuk, empezamos a destripar esta formula.

Partimos de:

I = -∑p_i*ln₂(p_i) 

= -∑p_i*ln₂(N_i/N)

= -∑p_i*[ln₂(N_i) - ln₂(N)]

= ∑p_iln₂(N) - ∑p_iln₂(N_i)

como ln₂(N) no depende de i, es una constante, y puede ser extraido de la suma.

= ln₂(N)*∑p_i - ∑p_i*ln₂(N_i)

como ∑p_i = 1, y el segundo termino es una esperanza, nos queda:

=ln₂(N) - E(ln₂(N_i))

El primer termino es constante, siemre que se mantengan constantes las cantidades de elementos del conjunto, entonces, si queremos maximizar o minimizar la entropia, tenemos que modificar el segundo termino (la distribucion de los elementos dentro de los conjuntos).

De hecho, la entropia va a ser maxima cuando cada conjunto tenga exactamente la misma cantidad de elementos. Es decir, cuando los N elementos esten distribuidos entre los k conjuntos. 

Cuando eso ocurra vamos a tener que N_i = N / k

Entonces,

I = ln₂(N) - ∑N/k*ln₂(N / k))

= ln₂(N) - ∑N/k*[ln₂(N) - ln₂ (k))]

= ln₂(N) - [ln₂(N) - ln₂ (k))]

= ln₂(N) - ln₂(N) + ln₂ (k))

=ln₂(k)

es decir, a la cantidad de bits necesarios para representar a todos los conjuntos

Todo esto con respecto a la entropia, ahora vayamos a k-means.

k-means , es un algoritmo para agrupar un conjunto de datos en k subconjuntos, minimizando alguna distancia (en general, la distancia euclidea).

la funcion a minimizar es la siguiente

V = ∑_i∑_jdist(x_ij;c_i)

donde c_i es el centro del subconjunto.

Si utilizamos el error cuadratico medio, lo que vamos a estar minimizando es esperanza de la varianza intragrupos (es decir, dentro de los grupos)

Esto de encontrar grupos que tengan algun sentido (minimizen alguna distancia), parecia que tenia bastante que ver con la teoria de la informacion, asi que empezamos a pensar un poco al respecto (aca vortex y tenuki me ayudaron un poco).

Como la funcion distancia, puede ser cualquier funcion distancia, que cumpla con las condiciones de una funcion distancia, utilize la distancia discreta multiplicada por ln(N_i)

dist(x_ij;c_i) = 0 sii x_ij = c_i

dist(x_ij;c_i) = ln₂(N_i) sii x_ij != c_i

como ninguno de los N_i elementos es c_i,  (si alguno fuese, multiplicamos y dividimos la distancia por algun valor, y el problema se resuelve), entonces,

∑dist(x_ij;c_i) = N_i*ln(N_i)

reemplazando en V, tenemos

V = ∑_iN_i*ln(N_i)

dividiendo m. a m. por N, tenemos

V / N =∑_iN_i*ln(N_i)/N

como N_i = p_i, entonces

V / N =∑_ip_i*ln(N_i)

V / N = E(ln(N_i)

Que es el segundo termino de la medida de la entropia.

Por lo tanto, en el espacio metrico definido por esta funcion distancia, es equivalente minimizar la distancia, a maximizar la informacion (No hay que olvidarse que en la formula de la informacion, el segundo termino aparece restando). Y es ahi donde las dos cosas tienen algo que ver.

Pero sin embargo, este resultado no me dejo completamente contento.

Por un lado, no refleja lo que yo queria (que era mostrar la cantidad de informacion que se concentra en los c_i; de hecho, estos ni siquiera se utilizan).

Ademas, quise utilizar otra funcion de distancia, como por ejemplo, la distancia de Hamming, pero no pude obtener el resultado que queria.

Espero que a alguien que lea este post se el ocurra alguna funcion distancia mas entretenida

saludos

/jb

ps: Tambien tengo que agradecer a tomas, que desde el mas alla (mas alla del meridiano de greenwich), siempre me da una mano con estas cosas

Acoplamiento y No Convexidad

Disclaimer:

• Este articulo tenia ganas de escribirlo hace un tiempo, pero habia un par de cosas que no me cerraban del todo, y queria esperar a que tenga el concepto cerradito y monono. Eso no paso, pero lo que si paso fue que me canse.
  
• Este es un articulo computronico

Lo que queria hacer era relacionar funciones, metodos, clases,  y namespaces con conjuntos.

Supongamos que tenemos una clase que sea una estacion climatica. Esta estacion climatica tiene sensores, como por ejemplo, termometros. 

Nosotros somos consumidores exernos de informacion, y solamente nos interesa lo

 que la estacion climatica nos puede ofrecer.

La imagen anterior vendria a ser una representacion de nuestro mundo.

A travez de los metodos, se producen relaciones entre los objetos.

Por ejemplo, si el consumidor externo quiere saber la temperatura, le pregunta a la estacion climatica la temperatura, se produce una relacion entre el consumidor y la estacion climatica.

Como la clase que define el consumidor tiene como variable de instancia una estacion climatica, la relacion ya esta establecida en la propia clase, por lo tanto, la relacion que genera el metodo es una relacion que va de la clase a la clase. 

A pesar de que por claridad yo dibuje las flechitas como saliendo de las clases, cuando estos nos encontramos con estos metodos, en realidad lo que ocurre es que todas las relaciones se producen dentro del conjunto que define la clase. Lo que se parece bastante al concepto de convexidad.

Por otro lado, puede ocurrir que el consumidor externo, en vez de preguntarle a la estacion climatica la temperatura, le pida su sensor de temperatura, y a la vez a este le pida la temperatura actual.

Esto es lo que vemos en este grafico:

En este caso, la relacion que generaria el metodo para obtener la informacion de la temperatura, iria mas alla de lo que define el conjunto de la clase consumidor externo (aunque volveria al consumidor externo, "salio por un rato" para buscar la temperatura).

Si trazacemos las flechas que define las relaciones producidas por este metodo, veriamos que pasa por la clase "sensor de temperatura", el cual no es conocido por el consumidor externo.

En este caso, las relaciones son relaciones no convexas, y por otro lado, este es un buen ejemplo de alto acoplamiento entre clases.

En que sentido esto no esta piola? 

Bueno, si por ejemplo cambiamos el sensor de temperatura por uno construido en el imperio, con las temperaturas medidas en grados farengein, en vez de en grados celcios, tendriamos un gran problema, ya que el consumidor externo no sabria nada sobre eso (problema que seguro estaria resuelto por la estacion climatica).

Por otro lado, hay algo interesante. A pesar de que estas tres clase estan acopladas entre si, las relaciones que producen sus metodos se mantienen dentro del conjunto definido por esas tres clases.

Si quisieramos definir un namespace que englobe esas tres clases, podriamos hacerlo, y tendriamos las caracteristicas de convexidad para ese namespace. 

Por lo que estariamos encapsulando este micromundo en ese namespace. Y maravillosamente, el minimo conjunto convexo que contiene a una serie de puntos se llama capsula convexa (o clausura convexa), por lo que el nombre de encapsulamiento parece tener aun mas sentido :)

Bueno, espero que a alguien le guste este post, a mi realmente no me gusta, pero ya no queria pensar mas en esto, y esta es la mejor manera de sacar un tema de la cabeza :)

saludos

/jb