Esta son las practicas propuestas por la asignatura Reconocimiento de Formas de la Universidad Politécnica de Madrid (UPM), España1.
Las practica consiste en programar 4 reconocedores:
-
Supervisados
- Distancias Euclideas
- Gauss
-
No supervisados
- K-mean clustering
- sequential clustering
uno basado en distancias euclídeas
Es cierto que la practica se propuso para ser hecha en python pero, debido a ciertos errores causados por el sistema de tipos en el que, al almacenar datos propios de la librería Numpy 1 en estructuras built-in de python, los valores de las variables variaban al ser redondeadas o truncadas. Por ello he decidido hacer la practica en Julia 2, un lenguaje de programación matemático al estilo de Matlab 3. Perdón por las molestias.
Antes de nada, decir que es son mis primeros programas en Julia y, por tanto, no es de extrañar que el código no sea el mas óptimo así como que ciertas funciones estén tipadas y otras se haga uso de la inferencia de Julia.
Dada la falta de tiempo, se ha buscado que los reconocedores hagan lo que debe por encima de la eficiencia del codigo.
Perdonar la ausencia de tildes, es lo que tiene usar un teclado americano
En este apartado se aplica el analisis supervisado, esto es, se tiene un set de datos inicial ya categoriados mediante el cual se puede entrenar y comparar los resultados.
NOTA: Toda la implementación se puede encontrar aquí https://github.com/Yawolf/calssifier
La implementación de los clasificadores es sencilla. Como he mencionado antes, han sido programados en Julia, lo que nos permite un manejo de matrices muy bueno, facilitándonos la programación.
Este clasificador se ajusta al siguiente algoritmo:
get_matrix from file
get_classes from matrix
get_average from matrix and classes
categorize using matrix, classes and average
- En primer lugar se obtiene la matriz leyéndola del CSV o .data
- De la matriz que hemos leído se extraen las clases y se hace un nub4 del vector resultante.
- Creando un diccionario usando las clases como key, calculamos la media de cada uno de los valores de los "vectores" de cada clase y se insertan como value.
- Una vez hecho todo lo anterior por cada elemento de la matriz se calcula su distancia euclidea con cada uno de los averages anteriores, el que este mas cerca sera la clase que se le asigne y se comparara con la que se nos da para ver si es verdad.
Como se puede observar, el funcionamiento e implementación de dicho reconocedor es sencillo.
Este clasificador tiene un algoritmo mas complejo de implementación:
get training and testing from file
separate training by classes
get covariance from classes
get mean from classes
classify using testing, classes, mean and covariance
- En primer lugar se hace un split de la matriz dando lugar a 2 "submatrices", una sera la matriz de entrenamiento, otra sera la de testing
- Una vez obtenida la matriz de entrenamiento, esta se subdivide en otras matrices mas pequeñas en la que todos los elementos de cada una de ellas pertenecen a la misma clase. Esto es, submatrices por clases.
- Una vez conseguidas las matrices de clases, se calcula la covarianza de cada una de ellas.
- Usando otra vez las matrices de clases se calcula la media de cada uno de los parámetros de cada clase.
- Usando el subset testing, las matrices de clases, sus covarianzas y sus medias, se calcula la probabilidad de que, cada elemento del dataset testing pertenezca a una u otra clase, para ello se usa la formula de la distribución gaussiana y se compara el resultado de la mejor opción con el original.
Siguiendo estos pasos se consigue reconocer estadísticamente cada elemento.
Ahora se presentaran los resultados para los dataset sacados de la UCI 5. Estos dataset son los siguientes:
- wine.data
- cancer.data
- iris.data
- wineR.data
- cancerR.data
- irisR.data
Todos ellos se pueden encontrar en la carpeta test de este repositorio. Cabe destacar que los dataset cuyo nombre termina en una 'R' contienen los mismos datos que sus equivalentes sin 'R', solo que sus datos han sido desordenados para obtener una mejor aleatoriedad.
$> sort -R wine.data >> wineR.data
Se presentan ahora las tasas de acierto de los clasificadores, tanto el euclidiano como el estadístico:
| Clasificador | wine.data | iris.data | cancer.data |
|---|---|---|---|
| Euclideo | 72.47191011235955% | 92.66666666666666% | 61.86291739894551% |
| Estadístico | 99.43820224719101% | 98.0% | 97.36379613356766% |
Notese que la precisión del clasificador estadístico es superior en muchos sentidos a la del euclideo, siendo este mas sencillo de programar, pero mas ineficiente a la hora de clasificar
Un ejemplo de como se ejecutan los test:
# Dentro del mismo direcotrio del src
$> julia
julia> include("clasific_eucl.jl")
julia> include("clasific_estad.jl")
julia> include("clasific_gauss.jl")
# euclideo
julia> euclideo.start("wineR.data")
...
# estadistico gaussiano
julia> gauss.start("wineR.data")
Ahora se van a presentar los resultados de la validación cruzada, para ello se ha decidido que el fichero de entrenamiento y el de test sea el mismo, se han hecho 10 folds para estar acorde al apartado siguiente. Los resultados son los siguientes
| Clasificador | wine.data | iris.data | cancer.data |
|---|---|---|---|
| Euclideo | 71.99197860962568% | 92.66666666666666% | 59.68614718614719% |
| Estadístico | 99.43820224719101% | 98.0% | 97.36379613356766% |
Ahora se usara el dataset MNIST 6, la cual contiene 60.000 elementos con 10 variables cada uno de ellos.
Para ejecutar se usan estos mandatos:
# Dentro del mismo direcotrio del src
$> julia
julia> include("clasific_eucl.jl")
julia> include("clasific_estad.jl")
julia> include("clasific_gauss.jl")
#euclideo
julia> euclideo.start("datos_procesados.npy",(1,500),1)
# estadistico gaussiano
julia> gauss.start("datos_procesados.npy",(1,500),1)
En este caso estamos usando las primeras 500 filas del CSV para entrenar y, al haber pasado un 1 como argumento, usaremos el mismo subset para entrenar y para testear. Cambiando dicho flag, se usara el segundo subset para testear.
julia> euclideo.start("datos_procesados.npy",(1,500),2)
...
julia> gauss.start("datos_procesados.npy",(1,500),2)
Los resultados son los siguientes:
| Estadístico | Euclideo | |
|---|---|---|
| D1 and D1 | 84.90420168067226% | 88.6% |
| D1 and D2 | 94.6% | 85.8890756302521% |
Se observa que para cantidades pequeñas, el euclideo y el estadístico tienen una diferencia mucho menor que en el caso de tener muchos elementos.
Igual que en el apartado de validación cruzada con UCI, aquí se ha subdividido la matriz en 10 submatrices.
Los resultados son los siguientes:
| Euclideo | Estadístico | |
|---|---|---|
| D1 and D1 | 88.6% | 84.90420168067229% |
| D1 and D2 | 85.8890756302521% | 94.6 |
En este apartado se utiliza el analisis no supervisado, esto es, el set inicial no esta clasificado y es el propio clasificador o reconocedor el encargado de obtener las clases mediante un entrenamiento previo. Para este apartado se usan exactamente los mismos set de datos y, aunque a nivel de codigo, se cargan con la clasificacion de cada elemento, esta es completamente ignorada por la logica de los clasificadores y se usa solo en la implementacion, muy mundana cabe decir, de un comparador de resultados entre los datos originales clasificados y los obtenidos.
NOTA: Toda la implementación se puede encontrar aquí https://github.com/Yawolf/calssifier
Igual que en el caso de los clasificadores no supervisados, estos han sido programados en Julia, a continuacion se explica el algoritmo usado en cada uno de los clasofocadores.
La implementacion responde al algoritmo clasico de sequential clustering:
get_matrix from file
(ck, iterable_matrix) = initial_cn_matrix
itreate for every x in iterable_matrix
get_min_distance(x,cn) where cn ∈ ck
if dist(x,ckk) > θ and n_ck > 0
cm = {x}
n_ck = n_ck - 1
else
ck = ck ∩ {x}
update_averages
end
end
save_matrix
compare
Los pasos son sencillos:
- Obtenemos la matriz de datos desde el fichero.
- Obtenemos un elemento como cn inicial y el resto de la matriz como matriz sobre la que iterar. En la primera version se elegia un elemento al azar en la matriz pero, dada la falta de tiempo, al final se decidio usar el primer elemento de la matriz como cn y el resto de la matriz como iterable.
- Por cada elemento de la matriz se calcula la distancia (euclidea en este caso) con cada cn existente (los he llamado ck, el conjunto de cn), si se da el caso de que una distancia es mayor al umbral dado (θ) y no se ha sobrepasado el numero maximo de clusters posibles (nck), entonces ese nuevo elemnto copone un nuevo cn,que se unira a ck. En caso contrario, dicho elemento se asignara a el cn mas cercano y dicho cn tendra que volver a reclacular su media.
- Una vez se ha terminado de clasificar, se guarda la matriz en un fichero seq.nombreDelSet.data. Este es el resultado real de la clasificacion.
- Se comparan los nuevos resultados con los originales.
Esta implementacion, un poco mas compleja que la anterior, se ajusta al algoritmo de k-mean clustering, aunque a nivel de codigo es un poco caotico:
get_matrix
get_K_clusters
get_K_Centroids
assign_each_D_data_closest_K
recalculate_centroinds and classify D set again
if differences then iterate again else end of algorithm
save_matrix
compare
- Se obtiene la matriz del datos.
- Se generan los K clusters con K elementos.
- Por cada elemento de la matriz, se clasifica al cluster Kn mas cercano.
- Se recalculan los centroides de las clases resultantes.
- Usando los nuevso centroides se clasifica D otra vez.
- Si hay diferencias entre una clasificacion y la anterior (centorides), se vuelve a clasificar; en caso de que no contrario, se acaba el algoritmo.
- Se guarda la nueva matriz. Este es el resultado real de la clasificacion.
- Se compara con los datos originales.
Como ya se sabe, los resultados de los analisis no supervisados son, en general, menos precisos que los del analisis supervisado, no obstante, la tasa de aciertos se suele mantener entre los 60 y 70%:
| Clasificador | wine.data | cancer.data | iris.data |
|---|---|---|---|
| Sequential | 72.47191011235955% | 62.741652021089635% | 87.33333333333333% |
| K-means | 74.15730337078652% | 63.620386643233736% | 98.0% |
| Clasificador | pimaIndians.data | datos_procesados.npy |
|---|---|---|
| Sequential | 70.44270833333334% | 69.95% |
| K-means | 73.95833333333334% | 85.94333333333334% |
Como se puede observar, el clasificador K-means tiene un porcentaje de acierto superior que el Sequential.
Para la obtencion de estos resultados se han ejecutado los sigueintes mandatos. Cabe destacar que, dado que existe una aleatoriedad en K-means, los resultados obtenidos pueden llegar a variar entre un 0 y un 1%.
# Dentro del mismo direcotrio del src
$> julia
julia> include("clasific_eucl.jl")
julia> include("clasific_estad.jl")
julia> include("kmeans.jl")
julia> include("sequential.jl")
# sequential.start(dataSet, th, nClusters)
julia> sequential.start("../test/wineR.data",50,3)
julia> sequential.start("../test/cancerR.data",50,3)
julia> sequential.start("../test/irisR.data",1,3)
julia> sequential.start("../test/pimaIndians.data",10,2)
julia> sequential.start("../test/datos_procesados.npy",13,10)
# kmean.start(dataSet, Knumber)
julia> kmeans.start("../test/wineR.data", 13)
julia> kmeans.start("../test/cancerR.data", 12)
julia> kmeans.start("../test/irisR.data", 7)
julia> kmeans.start("../test/pimaIndians.data", 15)
julia> kmeans.start("../test/datos_procesados.npy", 60) # Mi maquina no da mas
La razon por la que se importa clasific_eucl.jl y clasific_estad.jl es porque se usan, algunas de las funciones ahi declaradas.
tanto los valores de th como de Knumber son los que han dado mejores resultados de una bateria de pruebas. nClusters es el mismo proceso, pero, evidentemente, los mejores resultados son para nClusters = Clases originales.
El set kmean.datos_procesados.data se guarda como .data y no como .npy por sencillez de formato de matriz.