1 #!/usr/bin/env python
   2 # -*- coding: utf-8 -*-
   3 
   4 '''
   5 Introducción
   6 ============
   7 
   8 El práctico consta de dos partes:
   9 
  10 1) Clustering, en donde se deberá implementar el algoritmo k-means
  11 
  12 2) Clasificación, en donde se deberá entrenar un clasificador lineal
  13 
  14 Se trabajará sobre un dataset de dígitos manuscritos a que provee la librería sklearn
  15 (http://scikit-learn.org)
  16 
  17 Descripcioń del dataset
  18 =======================
  19 
  20 Cada muestra corresponde a una imagen de 8x8 de un dígito manuscrito
  21 
  22 ----------------------------------
  23 Clases                          10
  24 Muestras por clase            ~180
  25 Total de muestras             1797
  26 Dimensionalidad                 64
  27 Features              enteros 0-16
  28 ----------------------------------
  29 
  30 Ejemplo de uso:
  31 
  32   >>> from sklearn.datasets import load_digits
  33   >>> digits = load_digits()
  34   >>> print(digits.data.shape)
  35   (1797, 64)
  36   >>> print(digits.target.shape)
  37   (1797,)
  38 
  39 Los miembros mas importantes en estructura asociada al dataset son:
  40 
  41   data: Es una matriz de 1797x64 en donde cada fila corresponde a una muestra (imagen vectorizada)
  42 
  43   images: Es un arreglo de 1797x8x8 con las imágenes. Contiene escencialmente la misma informacioń
  44   que "data"
  45 
  46   target: Es un vector de 1797 elementos con las etiquetas asociadas a las muestras de entrenamiento
  47   (números del 0 al 9)
  48 
  49 Se van a tomar 2/3 de las muestras para el entrenamiento y el 1/3 para test.
  50 
  51 ===================
  52 PARTE 1: Clustering
  53 ===================
  54 
  55 Se provee una implementación simple del algoritmo k-means. El parámetro K se fijó inicialmente a
  56 10. Se pide:
  57 
  58 1) Analizar y entender cada paso del código que se provee. Los comentarios en las definiciones de
  59 funciones contienen información que le será útil a la hora de resolver el problema. Asegúrse de
  60 entender cada paso.
  61 
  62 2) Computar el error cuadrático medio (MSE) en el conjunto de test (ver MSE_TEST)
  63 
  64 3) En la implementacioń actual, los centroides se inicializan con valores aleatorios (ver
  65 INICIALIZACIÓN). Cambie esta política de forma tal que los centroides se inicializen a muestras
  66 aleatorias tomadas del conjunto de entrenamiento, es decir, elija K muestras de forma aleatoria y
  67 úselas como valores iniciales del algoritmo.
  68 
  69 4) Varíe el parámetro K del algoritmo (1, 10, 100) y compute el MSE sobre el conjunto de test para
  70 cada caso. Que observa?. A que se debe?.
  71 
  72    (su respuesta aquí)
  73 
  74 Al finalizar el práctico envíe la solución (programa modificado) a: jsanchez@famaf.unc.edu.ar
  75 
  76 '''
  77 
  78 import numpy as np
  79 
  80 from numpy import random, linalg
  81 
  82 import pylab as pl
  83 
  84 from sklearn.datasets import load_digits
  85 
  86 # Calcula el cuadrado de la distancia Euclidea entre dos vectores
  87 def squared_distance(a, b):
  88     assert(a.shape == b.shape)
  89     return linalg.norm(a-b, ord=2)
  90 
  91 # Computa la matriz de distancias. Para un problema con K centroides y N muestras (datos), la matriz
  92 # de distancias es una matriz de NxK en donde la entrada [i][j] almacena la distancia de la muestra
  93 # "j" al centroide "i". Por lo tanto, si se considera la fila "i" de la matriz es fácil obtener a
  94 # que centroide corresponde la muestra de índice "i" (ver K-MEANS PASO #1 más abajo)
  95 def distance_matrix(centroids, data):
  96     N = data.shape[0]
  97     K = centroids.shape[0]
  98     dm = np.ndarray((N,K), dtype='float')
  99     for i, data_i in enumerate(data):
 100         for j, centroid_j in enumerate(centroids):
 101             dm[i][j] = squared_distance(data_i, centroid_j)
 102     return dm
 103 
 104 # Calcula el error cuadrático medio (MSE) sobre un conjunto de datos. El MSE es una medida de la
 105 # distorsión que se genera al reemplazar cada muestra del conjunto de datos con el centroide más
 106 # cercano.
 107 def mean_square_error(centroids, data):
 108     N = data.shape[0]
 109     dm = distance_matrix(centroids, data)
 110     mse = 0.0
 111     for i in range(N):
 112         mse += dm[i].min()
 113     return mse / float(N)
 114 
 115 # programa principal
 116 def main():
 117 
 118     # carga dataset
 119     digits = load_digits()
 120 
 121     train_data = digits.data[0:600,:]
 122     train_labels = digits.target[0:600]
 123 
 124     test_data = digits.data[600:,:]
 125     test_labels = digits.target[600:]
 126 
 127     # si show_samples es True, muestra las primeras 10 muestras del conjunto de entrenamiento
 128     show_samples = False
 129     if show_samples:
 130         pl.gray()
 131         for i in range(10):
 132             pl.subplot(2, 5, i)
 133             img = train_data[i].reshape(8,8)
 134             pl.matshow(img, fignum=False)
 135             pl.xlabel(train_labels[i])
 136         pl.show()
 137 
 138     # N: número de muestras de entrenamiento
 139     N = train_data.shape[0]
 140 
 141     # D: dimensionalidad
 142     D = train_data.shape[1]
 143 
 144     # número de clusters
 145     K = 100
 146 
 147     # INICIALIZACIÓN: K vectores de D dimensiones con valores aleatorios entre el mínimo y el máximo
 148     # en el conjunto de entrenamiento
 149     min_val = train_data.min()
 150     max_val = train_data.max()
 151     centroids = random.random_integers(min_val, max_val, (K, D)).astype('float')
 152 
 153     # (TAREA #2)
 154 
 155     # calcula error cuadrático medio inicial
 156     mse_prev = 0.0
 157     mse_curr = mean_square_error(centroids, train_data)
 158     mse_eps = 1.0
 159 
 160     niter = 1
 161     while niter <= 100 and mse_eps > 1e-5:
 162 
 163         # K-MEANS PASO #1: asignación de muestras a centroides
 164         distances = distance_matrix(centroids, train_data)
 165 
 166         assignments = [0] * N
 167         for i in range(N):
 168             assignments[i] = distances[i].argmin()
 169 
 170         # K-MEANS PASO #2: reestimación de centroides
 171         new_centroids = np.zeros(centroids.shape, dtype='float')
 172 
 173         counts = [0] * K
 174         for i in range(N):
 175             j = assignments[i]
 176             new_centroids[j] += train_data[i]
 177             counts[j] += 1
 178 
 179         for j in range(K):
 180             centroids[j] = new_centroids[j] / float(counts[j] + 1e-6)
 181 
 182         mse_prev = mse_curr
 183         mse_curr = mean_square_error(centroids, train_data)
 184         mse_eps = (mse_prev - mse_curr) / mse_curr
 185 
 186         print 'iter = %d, mse = %.3f (eps = %.2e)' % (niter, mse_curr, mse_eps)
 187 
 188         niter += 1
 189 
 190     # (MSE_TEST)
 191 
 192 if __name__ == "__main__":
 193     main()