Clustering

Contexto.
1. Se aprende directamente de las similitudes o diferencias de los datos (Aprendizaje no supervisado).
2. A diferencias de la clasificación no se cuenta con conjuntos de entrenamiento (Aprendizaje supervizado).
3. Se basa principalmente en funciones de similitud o distancia.
4. Busca maximizar la similitud intraclase y minimizar la similitud interclase.
5. Organiza las instancias de datos en grupos de similitud llamados Clusters o Segmentos.
6. Areas de aplicación diversas...
  1. Sistemas de información geográfica.
  2. Medicina.
  3. Bioinformatica.
  4. Investigación de mercados.
  5. Tratamiento de imagenes.
    1. Reconocimiento de rostros.
    2. Detección de bordes.
  6. En mineria web de contenido se usa para organizar documentos provenientes de la red.
  7. En el análisis de redes sociales puede ser usado para reconocer comunidades ocultas en grandes grupos de personas
  8. Agrupamiento en los resultados de búsquedas.
Conceptos Básicos.
1. En clustering, una instancia de datos es vista como un punto en un espacio r-dimensional, donde r es el número de atributos que tiene la instancia.
2. Tres grupos naturales en un espacio de 2 dimensiones.
3. Casos de aplicación
  1. Definir las dimensiones de las prendas de vestir en grupos de personas con tallas similares.
    1. Una talla para cada quien = demasiado costoso.
    2. Una talla para todos = clientes descontentos.
  2. En campañas de publicidad se segmenta al mercado objetivo para ofrecerles productos o servicios más acorde a sus necesidades y gustos.
  3. Las agencias de noticias deben organizar todos los artículos que les llegan de acuerdo a una jerarquia de temas.
4. La calidad de los resultados del clustering dependen del algoritmo, la función de distancia y de la aplicación.
5. Tipos de clustering
  1. Por Partición.
    1. K-means
    2. Mapas auto-organizativos
  2. Por Jerarquia.
    1. Divisivo
    2. Aglomerativo
      1. Enlace sencillo
      2. Enlace completo
      3. Enlace promedio
      4. Centroides
6. Representación de clusters
  1. Usar el centroide (centro geométrico) de cada cluster para representarlo.
    1. Calcular el radio y la desviación estandar para determinar su distribución en cada dimensión.
    2. Funciona bien si los clusters tienen forma hiper-esférica, si tienen otras formas, el centroide no es suficiente.
  2. A través de un modelo de clasificación.
    1. Todas las instancias en un cluster son marcadas con una etiqueta. Ej: el número del cluster.
    2. Se corre un algoritmo de aprendizaje supervisado para generar un modelo.
    3. Conjunto de reglas a partir de la generación de 3 clusters.
  3. Usar los valores más frecuentes para representar el cluster.
    1. Este método es principalmente usado en clustering de datos categóricos (e.g., k-modes clustering).
    2. Principal método usado en text clustering, donde un pequeño conjunto de palabras frecuentes son seleccionadas para representar el cluster.
K-means.
1. K-means es un algoritmo de clustering por Partición.
2. El algoritmo k-means divide los datos en k clusteres.
3. Cada cluster tiene un centro llamado centroide que lo identifica.
4. k es especificado por el usuario.
5. El algoritmo
6. Criterios de parada o convergencia.
  1. Ninguana o minima reasignacion de data points a un diferente cluster.
  2. Ninguno o minimo cambio en los centroides.
  3. Reducción minima en la sumatoria del error cuadrado calculado en cada iteración.
7. Ejemplo
  1. Sea el conjunto de data points ...
  2. Selección aleatoria de k centroides (k=2).
  3. Asignación de cada data point a su centroid y cálculo de los nuevos centroides.
  4. Se repite el proceso de asiganción y re - cálculo.
  5. Ultima iteración, como los clusteres no cambian, el algoritmo se detiene.
8. K-means puede ser aplicado a cualquier conjunto de datos donde el promedio tenga sentido y se pueda aplicar una función de distancia.
9. Debilidades del Algoritmo
  1. El algoritmo es solo aplicable si un promedio esta definido.
  2. Para datos categóricos, se plantea el uso de k-mode donde el centroide es representado por el valor más frecuente.
  3. El usuario necesita especificar el valor de k.
  4. El algoritmo es sensible a outliers (datos anomalos o fuera de rango).
    1. Clusters mal definidos.
    2. Clusters ideales.
  5. El algoritmo es sensible a la escogencia de los centroides iniciales (semillas).
    1. Una aleatoria selección de semillas puede generar clusters no naturales.
    2. Al escoger otras semillas (seeds) se generan clusters diferentes.
  6. El algoritmo no es apropiado para identificar clusters que no sean hiper-esferas.
10. Resumen
  1. A pesar de sus debilidades k-means es aún el algoritmo más popular de clustering debido a su simplicidad y eficiencia.
  2. No hay una clara evidencia que otros algoritmos desempeñen mejor eso depende de la aplicación.
  3. Comparar diferentes algoritmos de clustering es muy complicado, ya que no se tiene certeza si los clusters generados son los correctos.
Clustering Jerárquico.
1. Produce una secuencia de clusters anidados en forma de árbol también llamado dendograma.
2. Tipos de clustering jerárquico.
  1. Clustering Divisivo (top down)
    1. Comienza con todos los datos agrupados en la raiz del dendograma.
    2. Parte el nodo raiz en un conjunto de clusters hijos y luego recursivamente con cada nodo hijo.
    3. Se detiene cuando los nodos hijos poseen una solo instancia de datos (nodos hojas).
  2. Clustering Aglomerativo (down top)
    1. Este contruye el dendograma desde el nivel inferior.
    2. Agrupa cada par de nodos según los más cercanos o similares.
    3. Se detiene cuando todos los nodos confluyen en un unico nodo raiz.
    4. El algoritmo.
    5. Un ejemplo de clustering aglomerativo en un espacio bidimensional.
    6. Según el método usado para la determinar la distancia entre clusters se puede dividir en ...
      1. Por enlace sencillo.
      2. La distancia es determinada por los dos elementos más cercanos en cada cluster.
      3. Es susceptible a datos ruidosos generando encadenamientos.
      4. Por enlace completo.
      5. La distancia es determinada por los dos elementos más alejados en cada cluster.
      6. Es susceptible a datos outlier.
      7. Por enlace promedio.
      8. La distancia entre dos clusters es la distancia promedio entre todos los elementos de cada cluster.
      9. Cubre parcialmente las falencias de los métodos anteriores.
      10. Por centroides.
      11. La distancia es determinada por la distancia entre los centroides de cada cluster.
      12. Tiende a ser un método más rápido que los anteriores.
3. Ventajas y desventajas.
  1. Este puede tomar cualquier forma de función de distancia o similitud.
  2. Permite al usuario exploara clusters a cualquier nivel de granularidad.
  3. Algunos estudios muestran que el clustering jerarguico aglomerativo arroja mejores resultados que k-means.
  4. Puede encontrar clusters de formas arbitrarias usando métodos de enlace sencillo.
  5. Como ya se vio pueden ser sensibles a efectos de cadena o susceptibles a outliers.
  6. Su mayor desventaja es su costo computacional y uso de recursos.
Ejemplos prácticos con Weka y R.
1. R y K-means
  1. En R existe la funcion kmeans
  2. Dado el conjunto iris (150 instancias, 4 atributos numéricos y una clase categórica).
  3. iris_csv <- read.csv('/data/Downloads/iris.csv')
  4. iris_petals <- iris_csv[,3:4]
  5. kr <- kmeans(iris_petals, 2)
  6. plot(iris_petals, col=kr$cluster, pch=64+kr$cluster)
  7. points(kr$centers, col=kr$centers, pch=8, cex=5)
  8. kr <- kmeans(iris_petals, 3, algorithm="Forgy")
2. R y clustering jerárquico
  1. En R existe la función hclust
  2. Usando el conjunto small_iris.csv
  3. smalliris <- read.csv('Projects/Datamining/small_iris.csv')
  4. hc <- hclust(dist(smalliris[,1:4]), method="average") plot(hc, hang = -1)
  5. Probar con diferentes valores de method = {single, complete, centroid}.
3. Weka y SimpleKMeans
  1. Utilizando el mismo conjunto iris.csv
  2. Cargamos el conjunto de datos
  3. Aplicamos el filtro Normalize
  4. Eliminamos la clase
  5. Ejecutamos el Algoritmo SimpleKMeans en la etiqueta Cluster.
  6. Cambiar los parametros por defecto para evaluar k=3.
  7. Click derecho en la sección de Result List.
  8. Seleccionar Visualize cluster assignments
  9. Evaluar graficamente los clusters generados.