Encontrando grupos o análisis de Cluster

“The validation of clustering structures is the most difficult and frustrating part of cluster analysis. Without a strong effort in this direction, cluster analysis will remain a black art accessible only to those true believers who have experience and great courage”.. Jain and Dubes

La intención de esta entrada es complementar parte de los explicado en la entrada  “Análisis de Cluster, un ejemplo sencillo”. El código en esa entrada fue hecho en R project y expliqué pocos aspectos teóricos del tema.

En esta entrada intento cubrir los básico y dar más ejemplos de como usar esta técnica. El código  que comparto está hecho en Python  y poco a poco indico dónde y cómo descargar los datos de cada ejemplo.

La entrada anterior de esta categoría “Algo de sobre Python, análisis de datos y machine learning”, expliqué o di referencia sobre las librerías que usaría en el resto de entradas. Se debe de contar con ellas sino el código puede funcionar.

El ejemplo clásico “dato de Iris”.

Una muestra de datos clásica para analizar es sobre la morfología de las Iris setosa,  versicolor y virgínica, estos fueron inicialmente estudiados por R. Fisher aproximadamente en 1930.

Para ejemplificar la técnica uso dos librerías, mlpy y scikit-learn, en la última se cuenta con los datos de las Iris, así que solo se cargarán y se analizan primero gráficamente y luego se hace uso de un algoritmo estándar de análisis de Clusters.

Comentario: La ventaja de la librería Scikit-Learn es que pueden extraer datos de varios repositorios y además cuenta con ciertas bases de datos muestra, eso ayuda a practicar los algoritmos de ML.

#Cargamos los datos de Iris desde Scikit-learn

#Graficamos 

#Importamos las librerias necesarias

from matplotlib import pyplot as plt
from sklearn.datasets import load_iris

#Cargamos los datos y graficamos

datos=load_iris()
caract=datos.data
caract_names=datos.feature_names
tar=datos.target

# Graficamos los datos con colores distintos y tipo de marcas distintos

for t, marca,c in zip(xrange(3),">ox","rgb"):
 plt.scatter(caract[tar==t,0],caract[tar==t,1],marker=marca,c=c)
 
plt.show() 

Para correr el código de manera rápida se puede copiar en el IDLE que se descarga al instalar Python  y usar F5 o poner el código en un archivo “plano”, con terminación “.py” y correrlo en el cmd o consola. Los detalles se puede revisar en el libro digital “Learn Python the hard way”.

La mejor opción es hacer una carpeta y guardar los archivos .py , iniciar una sesión con IPython y ejecutar el código.

El programa anterior carga los datos y el gráfico. Siempre es recomendable al hacer análisis de datos explorar la información y la vía en general es revisar propiedades estadística, rango de datos, propiedades y por medio de algún gráfico visualizar la información.

La gráfica que obtenemos es la siguiente:

Cluster_1_1

Desde una postura un poco matemática se aprecia que los datos son puntos en el plano, en este caso en el primer cuadrante, al pintarlos de distinto color podemos apreciar su distribución y se aprecia como los datos están “mezclados”.

Ahora probamos correr un código donde exploraremos los datos mediante el algoritmo K-Medias, explico adelante en qué consiste este algoritmo.

#Importamos las librerias necesarias

from matplotlib import pyplot as plt
from sklearn.datasets import load_iris
import mlpy 
from sklearn.cluster import KMeans
 
#Cargamos los datos y graficamos

datos=load_iris()
dat=datos.data
caract_names=datos.feature_names
tar=datos.target

#Calculamos los cluster

cls, means, steps = mlpy.kmeans(dat, k=3, plus=True)

#steps
#Esta variable permite conocer los pasos que realizó el algoritmo para terminar

#Construimos las gráficas correspondiente

plt.subplot(2,1,1)
fig = plt.figure(1)
fig.suptitle("Ejemplo de k-medias",fontsize=15)
plot1 = plt.scatter(dat[:,0], dat[:,1], c=cls, alpha=0.75)
#Agregamos las Medias a las gráficas

plot2 = plt.scatter(means[:,0], means[:,1],c=[1,2,3], s=128, marker='d') 
#plt.show()

#Calculamos lo mismo mediante la librería scikit-lean

KM=KMeans(init='random',n_clusters=5).fit(dat)

#Extraemos las medias

L=KM.cluster_centers_

#Extraemos los valores usados para los calculos

Lab=KM.labels_

#Generamos las gráfica

plt.subplot(2,1,2)
fig1= plt.figure(1)
fig.suptitle("Ejemplo de k-medias",fontsize=15)
plot3= plt.scatter(dat[:,0], dat[:,1], c=Lab, alpha=0.75)

#Agregamos las Medias a las gráficas

plot4= plt.scatter(L[:,0], L[:,1],c=[1,2,3,4,5], s=128, marker='d')

#Mostramos la gráfica con los dos calculos

plt.show() 

El programa regresar una gráfica como la siguiente:

Cluster_4

 

Se aprecia en las gráficas que son los mismos datos pero pintados con distintas cantidad de colores, más aún en cada gráfica se encuentran 3 y 5 puntos, respectivamente, de tamaño mayor al resto.

Revisando el código anterior con cuidado, se observa que se hace uso de dos librerías mlpy y scikit-learn, en las cuales aplicamos el mismo algoritmo.

En la primera de las gráficas se aglomeran lo datos en 3 grupos y en la segunda en 5, que es lo que corresponde con los parámetros pedidos en las funciones mlpy.kmeans y KMeans respectivamente.

Entonces lo que se aprecia es que se estiman 3 y 5 clusters y además se inicializa el algoritmo de modo distinto (kmean++ y random) y para ver los detalles de las funciones se puede consultar en las páginas de referencia[1,2].

La inicialización del algoritmo es fundamental, ya que para procesar muchos datos la complejidad computacional se ve reflejada tanto de usos de memoria como de procesamientos, entonces es importante el método que se usa.

¿Qué con este ejemplo? Bueno, lo que se hace es explorar que se tienen 3 grupos de datos correspondientes a distintas Iris, luego se prueba explorar si el modelo de clusters describe los datos. Pero faltan muchos detalles, el primero que inmediatamente surge es confirmar cual es mejor modelo, el de 3 o 5 clusters, ¿cómo validar esto?, ¿qué usar para saber si el modelo es bueno?

Trato más adelante de contestar estas preguntas en otros ejemplos.

Pero lo anterior representa la idea escencial de análisis de Clusters, que es agrupar los datos en grupos similares[3].

El comentario anterior prácticamente dice todo, pero agrupar implica encontrar un algoritmo para hacerlo y por grupos similares implica saber cuando decir que dos cosas son similares, los dos detalles no son triviales.

Un poco de teoría

Por supuesto que lo que menciono como teoría es breve y para nada exhaustivo. Dejo algunas referencias que considero suficientes para revisar los aspectos teóricos, depende del gusto y formación [3,4,5].

Lo básico para entender los modelos de Cluster es tener la noción de métrica o distancia, con esa idea se define lo que es la matriz de similaridad y disimilaridad.

Métrica. En matemáticas esta noción permite el estudio de los espacios métricos, pero un ejemplo sencillo de métrica es el valor absoluto en los números reales, estos son los números que desde la primaria nos enseñan y los usamos para contar cosas con cierta precisión como 1.5 kilogramos de arroz, 2.15 metros, 355 ml, etc.

Observamos que si tenemos los número reales, el valor absoluto siempre es positivo o cero. Ejemplo, abs(2.15)= 2.15 y abs(-2.15)=2.15 y  para abs(0)=0.

Entonces podemos decir que si x es un número real, entonces abs(x) siempre es mayor o igual a cero.

Otra propiedad que tiene el valor absoluto es que el único número que tienen valor absoluto cero es el mismo cero, es decir; si abs(x)=0 entonces x=0.

La última implicación, para la gente que tiene poca familiaridad con matemáticas no resulta tan natural. Pero otra idea es pesar en caminatas, si del punto x al punto y se miden cierta cantidad de pasos y nos encontramos en el punto x. La distancia del punto x al mismo punto x debe ser cero y eso nos dice que sabiendo que nuestra posición inicial era el punto x, entonces estamos en el punto x. Medio en formalidad es, si distancia(x,y)=0, entonces x=y.

La siguiente idea se base es ver un triángulo rectángulo y medir sus lados con una regla, esto nos indicaría que la suma de los valores absolutos de su base y su altura es mayor o igual al valor absoluto de la hipotenusa. Si uno observa el teorema de Pitágoras, aprecia que a^2+b^2=c^2, pero eso no dice que la igual persista con los valores absolutos de a, b y c.

Entonces lo que se tiene es que abs(hipotenusa) es menor o igual a abs(altura)+abs(base). Esta propiedad se llama desigualdad del triángulo.

Lo que se tiene es que el valor abs() cumple con tres propiedades, que pueden ser vistas como la abstracción de medir con una regla líneas sobre una hoja en una mesa plana. Estas tres propiedades son lo que definen una métrica o distancia.

Recalco lo mencionado de “una mesa plana” por que si uno imagina medir rectar o segmentos de rectas sobre la superficie de un balón, la situación cambia drásticamente y da origen a cosas raras como triángulos que tienen como suma de sus ángulos más de 180°, eso es en general lo que se llama geometría no euclidiana o que el espacio no es euclidiano.

¿Por qué menciono eso de lo no-euclideano?

Ese punto en los algoritmos de clusters es importante, teóricamente para evitar complicaciones supone que los datos están en un espacio euclideano, pero en general muchos datos tienen comportamientos que implican ser modelados como no-euclideanos. Esto hace que se mejoren las técnicas y se estudien aspectos teóricos de los algoritmos[6].

Teniendo  en cuanta que la mayoría de datos que se analizan provienen de muchas variables, lo que tenemos es que las métricas o distancias que podemos usar con nuestros datos dependen de la naturaleza misma de los datos.

Es decir, si tenemos datos sobre 50 indicadores financieros medidos en un día, lo que podríamos considerar es usar la distancia Euclineana que es un modo de medir la distancia entre puntos de un plano o espacio, ya que posiblemente los valores de los datos se pueden modelar con lo números reales.

Pero no ocurre lo mismo si tenemos datos económicos y sociológicos de 100 países, ya que posiblemente varias variables serán categóricas u ordinales, para lo cual se debe de usar otro tipo de métricas.

 Similaridad y disimilaridad. La idea es tener una métrica y esto mide la cercanía o la distancia entre dos de nuestras variables, pero en la prática es difícil tener una distancia en el estricto sentido, sobre todo que satisfaga la desigualdad de triángulo. Lo que se hace es considerar que la métrica solo cumple las dos primeras propiedades, es decir, d(U,V)>0 y d(U,U)=0, donde U y V son variables.

Un poco de álgebra. En todos los algoritmos lo que se construye con las variables es una matriz de disimilaridad que tienen ciertas propiedades, se construye considerando la entrada Aij=d(Ui,Uj).

Los algoritmos piden que A sea una matriz simétrica o en caso de que A sea una matriz de similaridad se convierte en una de disimilaridad transformando la matriz por medio de una  función monótona no decreciente.

Si no se conoce mucho de matrices y sus propiedades, en una idea burda se pueden pensar en ellas como una tabla con números y su relevancia en los algoritmos  es que se sabe mucho de ellas para trabajar con operaciones matemáticas y representarlas en una computadora no es complicado. En especial en Python se cuenta con la librería Numpy que permite trabajar con matrices y en R project existe el tipo de dato matrix() para su manejo.

Métricas y tipo de variables. En resumen se pueden clasificar el tipo de variables en tres familias: cuantitativas, ordinales y categóricas [4].

Para cada tipo de variable se tienen varios tipo de métricas, entre las usuales son:

Para cuantitativas: Euclídea, Manhattan, L1, correlación estandarizada.

Para ordinales: Se convierten en cuantitativas, mediante un ajuste, si tenemos M valores posibles, de cambia cada entrada por (i-0.5)/M.

Para categóricas: la Discreta es usual.

Pero existen muchas métricas que pueden ser empleadas, dependiente del tipo de datos y análisis que se pretenda hacer, basta echar un vistazo a la variedad que existen.

Más aún, el concepto de métricas no restringe hacer uso de alguna métrica conocida, si uno define una regla para medir y se prueba que satisface por lo menos lo mínimo para obtener una medida de disimilaridad puede hacer uso de los algoritmos de análisis de Clusters.

Por su puesto que no es necesario aprenderse todas las métricas que se conocen, lo recomendable es explorar varias posibilidades de las métricas estándar por tipo de variable y probar con otras para explorar si existe algún beneficio en el análisis.

Sobre los Algoritmos. Los dos algoritmos más usados son agrupamiento jerárquico (Hierarchical Clustering) y K-Medias (K-means). Existen varias versiones y adecuaciones de ellos, sobre todo para casos cuando las condiciones implican que el modelo se encuentra en espacio no-euclideanos, donde los datos requieren cierto tipo de medida de disimilaridad o cuando se modelan datos de larga-escala[6].

Los detalles teóricos respecto a tiempo de convergencia y la descripción del algoritmo pueden ser consultadas en las referencias [4,5,6].

 Para ver como se comportan los algoritmos de un modo gráfico y con detalle de lo que pasa en cada etapa recomiendo consultar las notas de Andrew Moore[7].

Tomo dos imágenes sencillas de los algoritmos debidas a Toby Segaran[8].

HC

KM

El primero es una imagen para explicar como funciona el algoritmo jerárquico, la idea es que inicia con A y B, ve su disimilaridad y avanza el algoritmo para detectar que puede ser también agrupado C. Avanza un paso más y detecta que D y E estás “lejos”, por lo cual avanza y agrupa a estos últimos. Lo que se oculta la idea de un árbol en los datos, donde las primeras hojas con formadas por A y B, su padre es C y de manera independiente se encuentran las hojas D y E. Se ve en la siguiente figura:

AHC

El segundo algoritmo, K-media; en la imagen se inicia con dos puntos “aleatorios” en la primera etapa los cuales serían los centro de cada cluster. En la segunda etapa se calcula el centroide de los punto cercanos y se cambia el centro de los clusters al centroide calculado, se continua de este modo hasta que ya no hay variaciones en la posición de los clusters.

Los dos algoritmos tienen variaciones y definiciones de parámetros tratando de adecuarlos u optimizarlos ante cierto tipo de datos, en general el que k-medias tienen un tiempo menor de estimación con respecto al clusters jerárquicos.

Para mostrar lo simple que puede verse el algoritmo de k-medias describo los pasos desde el punto de vista de Machine Learning:

#Idea General del algoritmo
1)Inicialización
  -Se eligen la cantidad de clusters k
  -Se elige aleatóriamente k posiciones desde los datos de entrada
  -Se indica que el centro de los clusters tienen la posición de la media de los datos

2)Aprendizale
  -Se repiten los pasos:
      Para cada punto de los datos se hace:
       -Se calcula la distancia del punto al centro         del Cluster
       -Se aglomera los puntos con el centro del clu        ster más cercano
      Para cada Cluster
       -Se cambia la poción del cluster al centro al        centroide de los puntos agrupados o aglomera        dos
       -Se hacen cambios en el centro del Cluster ha        sta que ya no hay variación en el cambio de         posición
3)Tratamiento
      Para cada punto de prueba
       -Se calcula la distancia a cada cluster
       -Se asigna el punto al cluster con el cual ti        ene la distancia menor
      

 La visualización del algoritmo es tomado de la referencia [9], para ver en python como escribir estas indicaciones de manera básica solo se necesita la librería Numpy. El código es el siguiente:

#Implementación básica del Algoritmo en Python

from numpy import ones,argmin

#Calculo de distancia
dis=ones((1,self.nData))*sum((data-self.centre[0,:])**2,axis=1)

for i in range(self.k-1):
 dis=append(dis,ones((1,self.nData))*sum((data-self.centres[j-1,:])**2,axis=1),axis=0)

#Se identifican los clusters
cluster=dis.argmin(axis=0)
cluster=traspose(cluster*ones((1,self.nData)))

#Se actualizan los centros
for j in range(self.k):
 thisCluster=where(cluster==j,1,0)
 if sum(thisCluster)>0:
 self.centres[j,:]=sum(data*thisCluster,axis=0)/sum(thisCluster)

 La idea de compartir el anterior código y el esquema del algoritmo es mostrar como es sencillo el proceso del algoritmo e implementación, uno puede encontrar otras versiones en la referencia [8]. En los siguientes ejemplos no de hace uso del este código, se utiliza la librería scikit-learn, en particular el módulo llamado sklearn.cluster.

Clave: En programación no siempre es necesario inventar el hilo negro.

Ejemplos con datos

Los primeros dos ejemplos son variaciones a los ejemplos que se pueden encontrar en la página oficial de scikit-learn []. Lo que trato de hacer con estos dos ejemplos es explicar lo que hace el código y el algoritmo, pero sobre todo como son atractivos visualmente espero que esto motive un poco el interés sobre como usar estas técnicas.

En el segundo ejemplo es una variación y extensión un ejemplo de la referencia[10]. Para el cual explico como se procesan textos y cual es el objetivo al identificar clusters en este ejemplo, doy la referencia y el banco de bases de datos de donde puede descargar los archivos que se usan.

Ejemplo 1.Tomamos una imagen que vienen por default en scipy para hacer ejercicios de procesamiento de imágenes, es tan conocida que se llama Lena y corresponde a una fotografía de Lena Sjooblom una playmate de los años 70.

El código fue hecho por Vincent MichelAlexandre Gramfort, se puede consultar la versión original en example-cluster-plot-lean.

El código es el siguiente:

#Cargamos los datos de Iris desde Scikit-learn
#Manejo de imagenes y clusters

print(__doc__)
#Importamos las lib necesarias

import time as time
import numpy as np
import scipy as sp
import matplotlib.pyplot as plt
from sklearn.feature_extraction.image import grid_to_graph
from sklearn.cluster import AgglomerativeClustering

####################################################

# Generando datos

lena = sp.misc.lena()

# Se reduce la resolucion de la imagen por un factor de 4

lena = lena[::2, ::2] + lena[1::2, ::2] + lena[::2, 1::2] + lena[1::2, 1::2]
X = np.reshape(lena, (-1, 1))

####################################################

# Se define la estructura de la conexion de la imagen, de los pixeles y sus vecinos

connectivity = grid_to_graph(*lena.shape)

####################################################

# Se calculo de Cluster
#Mandamos un mensaje de lo que está haciendo

print("Calculando la estructura de los clusters jerarquicos...\n")
print("No te desesperes ya viene la imagen")

st = time.time()
n_clusters1 = 20 # Numero de regiones estimadas en el cluster
ward1 = AgglomerativeClustering(n_clusters=n_clusters1,
 linkage='ward', connectivity=connectivity).fit(X)
label1 = np.reshape(ward1.labels_, lena.shape)
print("Tiempo transcurrido: ", time.time() - st)
print("Num de pixeles: ", label1.size)
print("Num de clusters: ", np.unique(label1).size)

st = time.time()
n_clusters2 = 15 # Numero de regiones estimadas
ward2 = AgglomerativeClustering(n_clusters=n_clusters2,
 linkage='ward', connectivity=connectivity).fit(X)
label2 = np.reshape(ward2.labels_, lena.shape)
print("Tiempo transcurrido: ", time.time() - st)
print("Num de pixeles: ", label2.size)
print("Num de clusters: ", np.unique(label2).size)

####################################################

# Se agregan los resultados a la imagen y se muestran las regiones estimadas


plt.figure('Imagen1',figsize=(5, 5))
plt.imshow(lena, cmap=plt.cm.gray)
for l in range(n_clusters1):
 plt.contour(label1 == l, contours=1,
 colors=[plt.cm.spectral(l / float(n_clusters1)), ])
plt.xticks(())
plt.yticks(())

plt.figure('Imagen2',figsize=(5, 5))
plt.imshow(lena, cmap=plt.cm.gray)
for l in range(n_clusters2):
 plt.contour(label2 == l, contours=1,
 colors=[plt.cm.spectral(l / float(n_clusters2)), ])
plt.xticks(())
plt.yticks(())

plt.show()

 Lo que obtenemos como resultado al correr el código son dos imágenes como las siguientes:

Lena1Lena2

Las imágenes muestra como se divide en 20 y 15 clusters, lo que uno debe de tener claro es que la imagen se traduce a información numérica y esta es la que se procesa al aplicar el algoritmo.

Ejemplo 2. Se hace una comparación con el modo en el cual se calculan los clusters de un conjunto de imágenes digitalizadas de lo números del 0 al 9, esta base de datos es muy conocida y se encuentras varias similares en otro repositorios. Los números se ven de esta forma:

14.4

El siguiente código hace uso de una herramienta de visualización. La idea es usar una “proyección”, con esto trato de decir que la información es originada de un espacio de muchas dimensiones y se visualiza en una imagen de 2 dimensiones, es decir; sobre un plano.

Algo así:

Proyecciones-conicas

Esta técnicas implica mencionar otros conceptos, pero trato de compartir este ejemplo por que permite ver como los clusters como una herramienta de clasificación y siempre “una imagen vale más de mil palabras”.

Este código fue hecho por Gael Varoquaux y se puede consultar en embebimientos digitales y clusters.

#Docstring en python
print(__doc__)
#Librerias usadas

from time import time
import numpy as np
from scipy import ndimage
from matplotlib import pyplot as plt
from sklearn import manifold, datasets
from sklearn.cluster import AgglomerativeClustering

#Se extraen lo datos
digits = datasets.load_digits(n_class=10)
X = digits.data
y = digits.target
n_samples, n_features = X.shape

np.random.seed(0)

def nudge_images(X, y):
 # Se varia la muestra de datos
 shift = lambda x: ndimage.shift(x.reshape((8, 8)),
 .3 * np.random.normal(size=2),
 mode='constant',
 ).ravel()
 X = np.concatenate([X, np.apply_along_axis(shift, 1, X)])
 Y = np.concatenate([y, y], axis=0)
 return X, Y


X, y = nudge_images(X, y)


#----------------------------------------------------------------------
# Visualizacion
#Se define esta funcion para simplificar el proceso de regreas 3 imagenes
def plot_clustering(X_red, X, labels, title=None):
 x_min, x_max = np.min(X_red, axis=0), np.max(X_red, axis=0)
 X_red = (X_red - x_min) / (x_max - x_min)

 plt.figure(figsize=(6, 4))
 for i in range(X_red.shape[0]):
 plt.text(X_red[i, 0], X_red[i, 1], str(y[i]),
 color=plt.cm.spectral(labels[i] / 10.),
 fontdict={'weight': 'bold', 'size': 9})

 plt.xticks([])
 plt.yticks([])
 if title is not None:
 plt.title(title, size=17)
 plt.axis('off')
 plt.tight_layout()

#----------------------------------------------------------------------
# Se hace un proceso geometrico llamado embebimiento para poder visualizar 
#el resultado del proceso de deteccion de clusters

print("Computo del embedimiento")
X_red = manifold.SpectralEmbedding(n_components=2).fit_transform(X)
print("Realizado.")


for linkage in ('ward', 'average', 'complete'):
 clustering = AgglomerativeClustering(linkage=linkage, n_clusters=10)
 t0 = time()
 clustering.fit(X_red)
 print("%s : %.2fs" % (linkage, time() - t0))

 plot_clustering(X_red, X, clustering.labels_, "%s linkage" % linkage)


plt.show()

 Al correr el código se obtienen 3 imágenes de clusters de los dígitos del 0 al 9, son hasta cierto punto parecidas pero si uno tienen calma y les dedica tiempo puedo observar ligeras diferencias.

Lo interesante en este ejemplo es ver como un conjunto de imágenes son clasificadas y agrupadas hasta cierto punto bien.

El método es cluster jerárquicos, pero una de las versiones de este algoritmo se llama “aglomerativo” que es como fue usado en la función AgglomerativeClustering. Lo que hace distinto entre cada uno de los algoritmo, average, single linkage y complete linkage es la definición de la medida de disimilaridad, se pueden ver detalles en la referencia [4].

Digitos1Digitos2Digitos3

Ejemplo 3.- Este último ejemplo requiere descargar una base de datos y revisar algunos aspectos del análisis de textos. Todo el proceso de realizará con scikit-learn y solo para ciertos detalles de hará uso de NLTK, que es el módulo por excelencia para hacer procesamiento de textos.

La idea de como procesar textos.

En general si uno escribe una oración, como: “Esta entrada ha sido muy larga, ¿por qué no logro terminarla?”.

Uno puede ver el texto como algo que hacemos de manera normal, pero lo que podemos pensar en cosas básicas como: cuántas palabras tiene, cuántos símbolos no son palabras, como medir que tan larga es una oración, etc.

Este tipo de cosas resultan ser calculables y visibles de manera rápida. Pero ,¿qué pasa con esto cuando tenemos toda una colección de textos?,¿cómo analizar sus relación entre palabras, frases  o textos completos?

Lo que a un matemático se le ocurriría inmediatamente es “medir la longitud de la frase” o definir un tipo de métrica. Ejemplo, “esntrada”, “entrada”, “etnrada” tienen longitud por letra 8, 7 y 7. Pero solo midiendo la longitud no podemos distinguir entre las últimas dos palabras.

Lo que se puede hacer es definir otra métrica como la ” métrica de Levenshtein“. El problema con solo medir este tipo de propiedades es que hasta cierto punto son locales, es decir; en cada palabra existe cierta medida y una frase u oración está formada por palabras. Eso no informa mucho respecto a como se comporta una frase completa.

Otra estrategia para analizar textos, no solo palabras; es construir lo que se llama ” bolsa de palabras”. Suponiendo que se tienen dos o tres oraciones  formadas por varias palabras, lo que se busca es medir la frecuencia de las palabras en cada frase. Ejemplo, las  “Esta entrada ha sido muy larga, ¿por qué no logro terminarla?” y “Esta entrada trata sobre técnicas de aprendizaje no supervizado”.

La bolsa de palabras estaría formada por todas la palabras diferentes de las dos frases y a cada frase se le asocia un vector de formado con ceros y unos que indican si apareció la palabra en la frase o no. Ejemplo para la primera oración forman una bolsa de palabras de 17 elementos, se tienen palabras en común, por lo cual el vector de la primera frase se vería como: (1,0,0,1,1,1,1,1,1,1,1,0,0,0,1,0,0).

Lo que observamos de esta representación es que conforme más frases con palabras diferentes la bolsa de palabras crece y la dimensión del vector también, con dimensión en este caso corresponde al número de entradas. Formalmente corresponde con la dimensión del espacio vectorial.

Otro beneficio de la representación por vectores es la posibilidad de definir una métrica mucho más geométrica, como la distancia euclideana.

Esto no es suficiente para preprocesar textos, otro elemento que se debe de considerar es eliminar las puntuaciones, ya que estos siguen siendo caracteres de la frases.

Un aspecto sutil, es que al establecer una métrica entre frases, puede resultar que una frase es repetida más de dos ocasiones, ejemplo “Cómo estas, cómo estas, cómo estas”. Dentro de la bolsa de palabras lo que uno obtendrá será un vector como el de la frase “Cómo estas” pero multiplicado por 3. Es decir, un vector de la forma (3,0,0,3,0,0,0,0,), entonces lo que se hace para evitar este tipo de anomalías es algo usual en álgebra lineal, normalizar los vectores. Es decir, se cambia el vector origina (3,0,0,3,0,0,0,0) dividido entre raíz de 2, lo cual hace que el vector sea igual en la norma al obtenido de (1,0,0,1,0,0,0,0). Así esas dos frases ya pueden considerarse iguales en el espacio de frases.

Lo último que se hace al analizar textos es eliminar las palabras más usuales, ya que estas aparecerán con mayor frecuencia en todas la frases y no permiten distinguir entre lo que realmente hace diferente o similar a una frase de otra. Además de que reduce la bolsa de palabras. Ya una vez que se “limpio” la frase resta analizar la relación de sus palabras o la frecuencia de las palabras respecto a la colección de textos, esto da una media de que tan relevante es la palabra. A este valor de la palabra se le llama Tf-idf.

Resumen:

1.-Se limpia la frase o texto de puntuaciones.

2.-Se elimina las palabras frecuentes del lenguaje

3.-Se construye el vector y se normalizan

4.-Se calcula el Tf-idf para las palabras que construyeron el espacio.

Todo lo anterior si bien mal explicado o incompleto es para tratar de dar una idea de lo que se hace con los textos. Al tener como medida de similaridad la distancia Euclideana podemos hacer uso del algoritmo de K-medias y elegir una cantidad de clusters para el algoritmo.

Para el ejemplo se hace uso de una base de datos llamada : 20newsgroup. Se puede descargar de varios modos, directamente desde el servidor http://qwone.com/~jason/20Newsgroups/. Otra opción es descargarlo desde un repositorio que cuenta con muchas bases de datos y se encuentra en http://mlcomp.org/datasets/379. La opción que considero más simple, pero se requiere un poco de paciencia es descargarla haciendo uso del módulo scikit-learn, mediante la función sklearn.datasets, las instrucciones se pueden leer aquí: http://scikit-learn.org/dev/datasets/index.html#datasets

El código se puede descargar desde https://github.com/luispedro/BuildingMachineLearningSystemsWithPython, el código se encuentra en el capítulo 3.

Las instrucciones para replicar el ejemplo:

1.-Descargar la base de datos

#Correr este código en Python o en IPython

from sklearn.datasets import fetch_20newsgroups
>>> newsgroups_train = fetch_20newsgroups(subset='train')

>>> from pprint import pprint
>>> pprint(list(newsgroups_train.target_names))
['alt.atheism',
 'comp.graphics',
 'comp.os.ms-windows.misc',
 'comp.sys.ibm.pc.hardware',
 'comp.sys.mac.hardware',
 'comp.windows.x',
 'misc.forsale',
 'rec.autos',
 'rec.motorcycles',
 'rec.sport.baseball',
 'rec.sport.hockey',
 'sci.crypt',
 'sci.electronics',
 'sci.med',
 'sci.space',
 'soc.religion.christian',
 'talk.politics.guns',
 'talk.politics.mideast',
 'talk.politics.misc',
 'talk.religion.misc']

2.-Guardar el código y correrlos desde:

-La consola estando en el directorio donde esta el código poniendo 
C:\......\>python nombredelarchivo.py
-Iniciar sesión en IPython y correr el código
In [1]%run python nobredelarchivo.py

El código del ejemplo es el siguiente, dejo los datos de origen de los creadores del código y solo agregué comentarios y explicaciones de lo que hace.

#Dejo los comentarios de origen respetando el trabajo de los autores


# This code is supporting material for the book
# Building Machine Learning Systems with Python
# by Willi Richert and Luis Pedro Coelho
# published by PACKT Publishing
#
# It is made available under the MIT License


#Cargamos los módulos requeridos

import sklearn.datasets
import scipy as sp


#Este será el post de prueba

new_post = \
 """Disk drive problems. Hi, I have a problem with my hard disk.
After 1 year it is working only sporadically now.
I tried to format it, but now it doesn't boot any more.
Any ideas? Thanks.
"""
print '%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n'
print "Este sera nuestro poste de prueba\n"

print("""\
Dear reader of the 1st edition of 'Building Machine Learning Systems with Python'!
For the 2nd edition we introduced a couple of changes that will result into
results that differ from the results in the 1st edition.
E.g. we now fully rely on scikit's fetch_20newsgroups() instead of requiring
you to download the data manually from MLCOMP.
If you have any questions, please ask at http://www.twotoreal.com
""")

print ('%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%')
#Cargamos la base de datos

all_data = sklearn.datasets.fetch_20newsgroups(subset="all")

print("Numero total de posts: %i" % len(all_data.filenames))
# Number of total posts: 18846

#Los grupos que se analizarán

groups = [
 'comp.graphics', 'comp.os.ms-windows.misc', 'comp.sys.ibm.pc.hardware',
 'comp.sys.mac.hardware', 'comp.windows.x', 'sci.space']
#Se elige la parte de la base a la cual se aplicará el algoritmo

train_data = sklearn.datasets.fetch_20newsgroups(subset="train",
 categories=groups)

print ("Numero de post de entrenamiento en los grupos de tecnologia :", len(train_data.filenames))

# Number of training posts in tech groups: 3529

print ("Se tomaran 60 Clusters!!")
labels = train_data.target

num_clusters = 60 # sp.unique(labels).shape[0]

#Se inicia el procesamiento de los datos

import nltk.stem
english_stemmer = nltk.stem.SnowballStemmer('english')

from sklearn.feature_extraction.text import TfidfVectorizer

#Se define una clase para asignar el Tfdf

class StemmedTfidfVectorizer(TfidfVectorizer):

 def build_analyzer(self):
 analyzer = super(TfidfVectorizer, self).build_analyzer()
 return lambda doc: (english_stemmer.stem(w) for w in analyzer(doc))

#Se continua con el preprocesamiento de los datos

vectorizer = StemmedTfidfVectorizer(min_df=10, max_df=0.5,
 stop_words='english', decode_error='ignore'
 )

#Se contruyen el espacio de vectores que representan a los post que se analizan

vectorized = vectorizer.fit_transform(train_data.data)
num_samples, num_features = vectorized.shape

#Se presenta la cantidad de muestra

print("#Muestra: %d, #Caracteristicas: %d" % (num_samples, num_features))

# samples: 3529, #features: 4712

#Se importa la libreria para aplicar k-medias

from sklearn.cluster import KMeans

km = KMeans(n_clusters=num_clusters, n_init=1, verbose=1, random_state=3)
clustered = km.fit(vectorized)


print '%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%'

print("km.labels_=%s" % km.labels_)

# km.labels_=[ 6 34 22 ..., 2 21 26]


print("km.labels_.shape=%s" % km.labels_.shape)
# km.labels_.shape=3529

#Se cargan el submódulo de métricas para hacer la medición de similaridad

from sklearn import metrics

print '%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%'

print 'Metricas'

print("Homogeneity: %0.3f" % metrics.homogeneity_score(labels, km.labels_))
# Homogeneity: 0.400
print("Completeness: %0.3f" % metrics.completeness_score(labels, km.labels_))
# Completeness: 0.206
print("V-measure: %0.3f" % metrics.v_measure_score(labels, km.labels_))
# V-measure: 0.272
print("Adjusted Rand Index: %0.3f" %
 metrics.adjusted_rand_score(labels, km.labels_))
# Adjusted Rand Index: 0.064
print("Adjusted Mutual Information: %0.3f" %
 metrics.adjusted_mutual_info_score(labels, km.labels_))
# Adjusted Mutual Information: 0.197
print(("Silhouette Coefficient: %0.3f" %
 metrics.silhouette_score(vectorized, labels, sample_size=1000)))
# Silhouette Coefficient: 0.006

#Se procesa el post de prueba

new_post_vec = vectorizer.transform([new_post])
new_post_label = km.predict(new_post_vec)[0]

similar_indices = (km.labels_ == new_post_label).nonzero()[0]

similar = []
for i in similar_indices:
 dist = sp.linalg.norm((new_post_vec - vectorized[i]).toarray())
 similar.append((dist, train_data.data[i]))

similar = sorted(similar)
print '%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%'
print("Count similar: %i" % len(similar))

print '%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%'
#Se eligen los tres más similares
show_at_1 = similar[0]
show_at_2 = similar[int(len(similar) / 10)]
show_at_3 = similar[int(len(similar) / 2)]

#Se imprimen

print("=========================== #1 =========================")
print(show_at_1)
print()

print("=========================== #2 =========================")
print(show_at_2)
print()

print("=========================== #3 =========================")
print(show_at_3)

El código anterior parece raro o feo, a primera vista pero lo que hace es bastante interesante.

En primera se toman 3529 elementos de muestra para analizar, de entre ellos se construye un espacio con los vectores asignados a cada post, claro que para llegar a eso primero se procesan los textos.

Teniendo el espacio vectorial se procede a medir la distancia, esto permite la construcción de una matriz de términos, que permite aplicar el método de k-medias sobre los post vectorizados.

Teniendo esto se hacen mediciones de métricas usuales sobre los clusters.  Sobre estos indices o medidas, no menciono nada, pero se pueden consultar en la referencia [3].

Cuando los datos se han dividido por clusters, entonces se procede a calcular o estimar en cual es el cluster que le corresponde al post y se eligen los 3 post que tienen menor similaridad o distancia euclideana.Termina el programa presentando los 3 post más cercanos.

Espero este último ejemplo no desanime a la primera lectura, es menos visual que los otros dos ejemplos previos pero que es bastante interesante, no tan solo por que procesa una base considerablemente grande, sino por que se muestra como emplear el algoritmo de clusters en una actividad que no suele mencionarse en los textos con perfil muy estadístico.

Este tipo de procedimiento, es decir; procesar los datos y luego asignar un tipo de medida, puede ser llevado a la práctica con otro tipo de información que no solo sea texto. El más interesante es quizás el analizar base de datos de imágenes y comparar los resultados con otras técnicas de clasificación.

Referencias.

1.-http://en.wikipedia.org/wiki/K-means%2B%2B

2.-http://www.autonlab.org/tutorials/kmeans11.pdf

3.-Capítulo 25, http://www.cs.ubc.ca/~murphyk/MLbook/

4.-Capítulo 13 y 14, http://statweb.stanford.edu/~tibs/ElemStatLearn/

5.-Capítulo 9, http://research.microsoft.com/en-us/um/people/cmbishop/prml/index.htm

6.- Capitulo 7, http://www.mmds.org/

7.-http://www.autonlab.org/tutorials/kmeans11.pdf

8.-http://shop.oreilly.com/product/9780596529321.do

9.-Capitulo9,http://www.amazon.com/Machine-Learning-Algorithmic-Perspective-Recognition/dp/1420067184

10.Capitulo3y4, http://shop.oreilly.com/product/9781782161400.do

11.-Página Oficial de Scikit-Learn

Análisis de Cluster, un ejemplo sencillo.

El análisis de agrupamiento (cluster), es sencillo de explicar y de implementar en R project. Lo delicado es procesar la información y la definición de la métrica que consideramos apropiada para nuestros datos o experimento.

Hago un ejemplo sencillo antes de explicar qué se hace con esta técnica.

#Ejemplo de Cluster
data(iris)
#Generamos 5 grupos en nuestros datos
modelo5<-kmeans(iris[1:2],5)
plot(iris[1:2],col=modelo5$cluster,main="Ejemplo de 5 cluster",xlab="longitud de la Sápal",ylab="Ancho de la Sápal")
#Generamos 3 grupos en nuestros datos
modelo3<-kmeans(iris[1:4],3)
plot(iris[1:4],col=modelo3$cluster,main="Ejemplo de 3 cluster")

 Ejemplo_5_cluster

Ejemplo_3_cluster

Los dos gráficos muestran de colores distintos un conjunto de puntos, por lo que se ve en el código, usando una función kmeans para definir modelo5,modelo3. Luego indico al gráfico que tomara los colores partiendo de un valor $cluster. Esto podríamos deducirlo viendo solo el  código, la pregunta es cómo se define qué puntos pintar de cierto color. Si uno hace el “scatter plot” de los mismos datos se observa una “regla”.

#Scatter Plot 
data(iris)
plot(iris[1:4],col=c(2,3),main="Scatter Plot de parejas de vectores de datos")

Ejemplo_Scatter_Plot_Datos Iris

Si uno compara los 3 gráficos, la regla para determinar el color de los puntos tienen que ver con un modo de agruparlos, de tener un modo de verlos cuan cercanos o similares son. Eso se nota principalmente entre los dos últimos gráficos.

La idea de “similar”, puede ser pensada como un modo de comparar cosas, si se piensa en tres personas  donde dos estudiaron en la misma universidad, tienen casi la misma edad y alturas y tienen diferencia de peso de solo un par de kilos, son “casi iguales” con respecto al tercer individuo, que no estudió en la misma universidad, tiene más años, tiene sobrepeso y mide más que los otros dos. Entonces podemos pensar que los dos primeros son “similares” o al compararlos “son más cercanos o parecidos”.

La noción de “cercanía” está asociada con la noción de distancia, podemos definir que dos cafeterías tienen una distancia pequeña si las separa una calle, pensando que su unidad de medida son el número de calles entre ellas. Entonces la noción a través de todo esto es la de “métrica“, cómo medir similitudes.

En geometría, la métrica es la distancia entre puntos la cual tienen ciertas propiedades; medir del punto 1 al punto 2 es igual que iniciar midiendo desde el punto 2 hasta el punto 1 (simetría); la distancia entre los puntos es por lo menos cero (positiva) y  medir la distancia entre dos puntos es menor o igual que la suma de las distancia de los puntos a un punto intermedio (desigualdad del tringualo) y la última, si la distancia entre dos puntos es cero los puntos no pueden ser distintos (identidad de los indiscernibles).

Entonces la idea de la técnica es medir la distancia de cada pareja de puntos de los datos. Esto no necesariamente implica que la distancia sea para números o vectores, puede ser definida por las características de los datos o sobre cadenas de texto o mensajes, características de una persona,etc.

Aclarado el código anterior, lo que se hizo con el comando kmeans fue aplicar un algoritmo que permite separar entre los grupos de datos, tomando como parte inicial el  eligir la cantidad de grupos que se desean, después se calcula el centroide con respecto a todos los datos y se hace un proceso de separación e iteracciones para determinar los cúmulos, la técnica se llama k-Means Clustering. Para entender en detalles el algoritmo se puede revisar las notas de Andrew Ng o de Andrew Moore, las notas de éste último son acompañadas de varias  gráficas lo cual ayuda a visualizar el algoritmo de un modo sencillo.

Un ejemplo puede ser pensando en una matriz de datos, donde cada fila representa un individuo y cada columnas es una característica la cual puede tomar el valor de -1,0 o 1. Entonces lo que se hace es realizar el producto de la matriz y su transpuesta para obtener la correlación entre cada uno de los individuos y lo que se usa como métrica es la distancia euclidiana. Con ellos se puede tener una matriz con información sobre las distancia entre nuestros individuos.

#Ejemplos 
x.matriz<-matrix(sample(c(-1,0,1),24,replace=TRUE),nrow=4,ncol=6)
#Etiquetamos las columnas y las filas
row.names(ex.matriz)<-c('A','B','C','D')
colnames(ex.matriz)<-c('P1','P2','P3','P4','P5','P6')
#Multiplicamos por la transpuesta
ex.mult<-ex.matriz%*%t(ex.matriz)

#Calculamos la distancia
ex.dis<-dist(ex.mult)

Ahora usamos el comando cmdscale para calcular el escalamiento multidimensional, obtendremos como resultado los puntos que son cercanos o próximos, según la métrica.

#Cluster
ex.mds<-cmdscale(ex.dis)
plot(ex.mds,type='n')
text(ex.mds,c('A','B','C','D'))

Ejemplo_Escalado_Multidimensional

Se concluye del ejemplo anterior que la estrategia es; procesar nuestra información, definir o usar una métrica, construir la matriz de similaridad y aplicar el análisis de escalamiento multidimensional o un algoritmo de agrupamiento.

Polarización de un Senado

Muestro un ejemplo del texto Machine Learning for Hackers [1]. El ejemplo usa los datos del senado de EEUU, se encuentran en la plataforma http://www.voteview.com y en caso de tener una falla en la descargar se puede bajar del repositorio de GitHub en https://github.com/johnmyleswhite/ML_for_Hackers.

La idea es la siguiente, revisar el comportamiento de las votaciones del Senado y revisar el comportamiento del periodo 110 al 111 del congreso.

Lo que se hará es procesar la información, asignar ciertas variables categóricas que solo tendrán valores -1,0 y 1 para cada una de las características de los senadores analizados. Esto permite definir una métrica sencilla, como la del último ejemplo y basta considerar el productos de matrices para formar la matriz de similaridad.

#Análisis de votos 
library(foreign)
library(ggplot2)
#Tomamos la ruta de los archivos
data.dir 6, 0,no.pres[,i])
         no.pres[,i] 0 & no.pres[,i] < 4, 1, no.pres[,i])
         no.pres[,i] 1, -1, no.pres[,i])
 }
 
 return(as.matrix(no.pres[,10:ncol(no.pres)]))
}

#Aplicamos la función a cada entrada de rollcall.data
rollcall.simple

Con lo anterior pueden construir las gráficas que para apreciar la evolución del senado, donde la hipótesis inicial es que el congresos se polarizó en el 111 congreso.

Primero se revisa el comportamiento solo de las votaciones del 111 congreso y después se compara con respecto los congresos previos, partiendo desde el 101.

MDS_Votacion_Senado111_US

MDS_Votacion_Senado del 101 al 111_congreso_USEn resumen la última gráfica muestra que el Senado en distintos periodos se puede dividir en dos grupos, se puede decir que se polariza entre Republicanos y Demócratas. Los pocos senadores considerados como “independientes” parece, al revisar la última gráfica; que siempre votaran como los Demócratas.

La moraleja es que bajo una métrica sencilla se pueden extraer ciertas propiedades del comportamiento o dinámica del los datos. Sería interesante hacer un ejercicio similar para  el Senado de otros países.

Resumiendo, la técnica o análisis de agrupamientos (cluster) requiere como primer paso explorar nuestra información y procesarla si es necesario para poder definir una métrica que tenga coherencia con el tipo de información y datos.

Después se debe de calcular la matriz de distancias y por último aplicar escalamiento multidimensional o algún algoritmos para detectar aglomeraciones.

Como paso intermedio, tienen sentido plantearse una pregunta respecto a los posibles grupos que se busca encontrar en los datos y como siempre para cerrar el análisis, hacer usos de gráficos que permitan visualizar el resultado.

Ha esta entrada le falta mucho muchos ejemplos, que espero más adelante compartir otros. Respecto al tema falta mostrar varios detalles; tipos de métricas para tipos de datos, algoritmos de aglomeración para tipos de análisis y la creación de modelos basados en esta técnica.

Los aspectos teóricos se encontrarán en la categoría “Sobre Machine Learning”. Una disculpa para la gente de matemáticas por no haber puesto la definición formal de espacio métrico, métrica y mencionar algunas de sus propiedades, espero posteriormente hacer algunas entradas con un enfoque formal.

Actualización 19-05-2015

En la primera versión de esta entrada faltó mencionar muchos detalles sobre la técnica de K-medias, pero además no mencioné nada sobre otro algoritmo Hirarchical Clustering o Cluster jerárquico.

Comparto un ejemplo de esta técnica y en resumen lo que se hace en este algoritmo es construir un árbol que ayude aglomerar los datos en conjuntos los cuales al terminar el algoritmo muestra las aglomeraciones obtenidas.

El costo computacional es mucho mayor que los métodos k-medias, pero en general para muestras de datos relativamente grandes no resulta tan costoso implementarlo y además se han desarrollado algoritmos para reducir el costo en tiempo y procesamiento.

Los datos los tomo de la página del libro Elements of Stadistical Learning [2], en el código indico como descargarlo directamente.

Respecto al origen de los datos, cabe resaltar que corresponde al análisis de tumores cancerígenos, se analiza su valor genético a 64 tumores y por medio de las técnicas de Cluster se trata de detectar cuantos cánceres corresponde a qué tipo de tumor.

Algunas precisiones. Se descargaron los nombres de los tumores en un archivo txt, a que los nombres de las columnas no vienen por default en los datos. La matriz de datos está formada por 64 columnas y 6830 filas.

#Ejemplo de Cluster con datos de tumores 
#Ubicado en el directorio donde estan los nombres de los genes se procede a cargarlos en R
#Se carga como un vector
Nombres=read.table("nombres_tumores.txt")
#Visualizamos los datos
head(Nombres)
# V1
# CNS
# CNS
# CNS
# RENAL
# BREAST
# CNS

#Cargamos los datos de los genes

datos=scan("http://statweb.stanford.edu/~tibs/ElemStatLearn/datasets/nci.data")

#Visualizamos los datos
head(M)
#Tranformamos los datos en una matriz de 64 renglones por 6830 columnas
#Después invertimos la matrix
M=matrix(datos,nrow=64)
M2=t(M)

#Agremagamos los nombres a las columnas de M2

colnames(M2)=as.vector(t(Nombres))
 
head(M2)
#Así se visualiza la tabla de datos
# CNS CNS CNS RENAL BREAST CNS CNS BREAST NSCLC NSCLC RENAL RENAL RENAL RENAL RENAL RENAL RENAL BREAST NSCLC RENAL UNKNOWN
#[1,] 0.300 0.679961 0.940 2.800000e-01 0.485 0.310 -0.830 -0.190 0.460 0.760 0.270 -0.450 -0.030 0.710 -0.360 -0.210 -0.500 -1.060 0.150 -0.290 -0.200
#[2,] 1.180 1.289961 -0.040 -3.100000e-01 -0.465 -0.030 0.000 -0.870 0.000 1.490 0.630 -0.060 -1.120 0.000 -1.420 -1.950 -0.520 -2.190 -0.450 0.000 0.740
#[3,] 0.550 0.169961 -0.170 6.800000e-01 0.395 -0.100 0.130 -0.450 1.150 0.280 -0.360 0.150 -0.050 0.160 -0.030 -0.700 -0.660 -0.130 -0.320 0.050 0.080
#[4,] 1.140 0.379961 -0.040 -8.100000e-01 0.905 -0.460 -1.630 0.080 -1.400 0.100 -1.040 -0.610 0.000 -0.770 -2.280 -1.650 -2.610 0.000 -1.610 0.730 0.760
#[5,] -0.265 0.464961 -0.605 6.250000e-01 0.200 -0.205 0.075 0.005 -0.005 -0.525 0.015 -0.395 -0.285 0.045 0.135 -0.075 0.225 -0.485 -0.095 0.385 -0.105
#[6,] -0.070 0.579961 0.000 -1.387779e-17 -0.005 -0.540 -0.360 0.350 -0.700 0.360 -0.040 0.150 -0.250 -0.160 -0.320 0.060 -0.050 -0.430 -0.080 0.390 -0.080

#Aplicamos k-Means con 3 cluster a
KM3=kmeans(M2,3)

#Generamos una gráfica para visualizar los componentes

library(cluster)
clusplot(M2,KM3$clusteres,shape=TRUE,color=TRUE,labels=3)

#Aplicamos Hierarchical Clustering
H1<-hclust(dist(M),"average")
#Dendrograma
plot(H1,col=2,frame.plot=TRUE)

 Las gráficas que obtengo del código  son las  siguientes:

Dendrograma

Cluster_Genes

La primera gráfica es el modo visual en que se comportan los clusters en el método jerárquico y la segunda es una herramienta visual para observar el comportamiento del método k-medias.

Una observación entre los dos métodos es, k-medias pide como parámetro conocer cuantos clusters se buscamos en el algoritmo y el jerárquico no, de cierto modo la aglomeración por el jerárquico es cercana a lo que sería un método no supervisado.

Para el  algoritmo de k-medias resulta importante el análisis de la elección de la cantidad de clusters en los datos.

Existen varias técnicas para tratar de elegir el mejor valor de k, en R project, existen varias librerías entre las cuales están: “fpc” y “mclust”. Para los datos de este ejemplo probé con mclust, pero le resultaba muy costoso así que cancelé el proceso.

Pero otro modo muy sencillo y que no requiere ninguna librería es mediante el análisis de los cuadrados de las distancias de cada  dato aglomerado con respecto a la cantidad de clusters que se calculan.

#Elección de K para k-medias
wss <- (nrow(M2)-1)*sum(apply(M2,2,var))
 for (i in 2:10) wss[i] <- sum(kmeans(M2,centers=i)$withinss)
plot(1:10, wss, type="b", xlab="Númbero de Clusters",ylab="Suma de cuadrados dentro de cada cluster")

 La gráfica que se obtiene es la siguiente:

K-Medias

Esta última técnicas es sencilla, pero el problema es que no siempre indica de modo claro como elegir la cantidad de clusters de un modo óptimo. Por lo cual es bueno recurrir a otro tipo de algoritmo y compara nuestra selección y al final validar con alguna muestra de datos.

En un trabajo de investigación de Robert Tibshirani-G. Walther y Trevor Hastie[5] plantean un método para obtener un óptimo del número de clusters en el algoritmo k-meadias, sobre este reporte de investigación se basan varias librerías en R project para estimar el valor óptimo de k.

Espero que este complemente de una idea en general del tipo de análisis y de las técnicas básicas de como usar este tipo algoritmo. Cabe mencionar que las técnicas de Cluster están relacionadas con la Mezcla de Modelos y el algoritmo EM, lo cual se puede usar para la construcción de modelos. En otra entrada explico el uso y relación de esto.

Referencias:

1.-http://shop.oreilly.com/product/0636920018483.do

2.-http://statweb.stanford.edu/~tibs/ElemStatLearn/

3.-http://www.amazon.com/Cluster-Analysis-Brian-S-Everitt/dp/0470749911

4.-http://www.amazon.com/Machine-Learning-Probabilistic-Perspective-Computation/dp/0262018020

5.-http://web.stanford.edu/~hastie/Papers/gap.pdf