Esta charla está disponible en github.com/sebastiandres/charlas para libre descarga.
Puede verse en línea:
De manera interactiva con binder: https://bit.ly/2Ub89mU
De manera estática en el mismo github: https://bit.ly/33WmSa2
Data science es una ciencia interdisciplinaria, que se apoya en conocimientos de Matemática, Estadística, Informática, entre otros.
Es como ciencia forense, pero en lugar de cadáveres, se investigan datos.
Es como Jurassic Park, donde se tiene parte del ADN de cada dinosaurio, y para poder completar la información se utilizó otro ADN compatible.
Las matrices representan combinaciones lineales.
Nada más que eso.
Pero eso es suficientemente poderoso.
Multiplicar un vector por una matriz permite obtener una combinación lineal de las distintas filas.
Multiplicar un vector por una matriz permite obtener una combinación lineal de las distintas filas.
Multiplicar una matriz por un vector columna (por la derecha) permite obtener una combinación lineal de las columnas de la matriz.
Multiplicar una matriz por un vector columna (por la derecha) permite obtener una combinación lineal de las columnas de la matriz.
Sólo podemos resolver problemas lineales.
Todo lo demás es reducir el problema a algo que se parezca o se aproxime a un problema lineal.
Desde lo más "clásico" (sistemas de ecuaciones, ecuaciones diferenciales ordinarias, ecuaciones diferenciales parciales, etc.) hasta lo más moderno (inteligencia artificial y Machine Learning): todo depende de matrices y vectores de datos, cada vez de mayor tamaño.
El producto u-exam busca asignar de manera eficiente y sin conflictos las evaluaciones de los estudiantes. Cada estudiante toma varias asignaturas, y se necesita que en una única semana se agenden las evaluaciones para cada asignatura:
Importante: Una parte crucial del modelamiento de un problema es utilizar una notación apropiada.
En nuestro caso hablaremos de:
Definamos la matriz $E$ (del inglés "enrollments") de dimensiones $N_e$ estudiantes y $N_c$ asignaturas, donde:
¿Cuántas filas hay? ¿Cuántas columnas hay?
Por ejemplo, consideremos los siguientes asignaturas:
Y consideremos los siguiente alumnos:
¿Cuánto vale $N_e$? ¿Cuánto vale $N_c$?
$N_e=5$ estudiantes y $N_c=7$ asignaturas.
Supongamos que toman los siguientes cursos:
¿Cómo quedaría la matriz?
¡Depende de cómo ordenemos los estudiantes y los cursos!
Consideremos el siguiente orden
CORE102, MAT106, MAT113, FIS101, TE101, LID101, GYM102:
Obtenemos entonces la siguiente matriz: $$ E = \left( \begin{matrix} 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1 & 0 & 0 \end{matrix} \right) $$
¿Cómo contar la cantidad de inscripciones por estudiante?
¿Cantidad de inscripciones por asignatura?
¿Cantidad de inscripciones totales?
Para contar las inscripciones por estudiante, necesitamos sumar los elementos de cada fila. Eso es equivalente a ...
¡una multiplicación con un vector por la derecha!
Para contar la cantidad de estudiante por curso, necesitamos sumar los elementos de cada columna. Eso es equivalente a ...
¡una multiplicación con un vector fila por la izquierda!
¿Cómo podríamos contar el total de inscripciones?
Matemáticamente, lo anterior se obtiene por lo siguiente:
$$E_{sum} = \sum_{i=1}^{N_e} \sum_{j=1}^{N_c} E_{ij} = \sum_{i=1}^{N_c} 1 \sum_{j=1}^{N_c} E_{ij} 1$$¿Cómo podríamos la cantidad de créditos que tomó cada estudiante?
Para contar los créditos por estudiante, necesitamos ponderar los elementos de cada fila. Eso es equivalente a una multiplicación por un vector columna por la derecha.
Como $E$ tiene $N_e$ filas y $N_c$ columnas, $E^T \cdot E$ debe tener $N_c$ filas y $N_c$ columnas.
De alguna manera, esta matriz está relacionando cursos con cursos. Pero ¿cómo?
Definamos la matriz $A = E^T \cdot E$
El elemento $A_{i,j}$ está definido como $$A_{i,j} = \sum_{k=1}^{N_e} (E^T)_{i,k} (E)_{k,j}$$
¿Alguna idea?
Recordemos que $E_{k,j}$ toma únicamente los valores $0$ y $1$, y por lo tanto, $E_{k,i} E_{k,j}$ sólo es igual a $1$ cuando ambos términos son iguales a $1$, es decir, si el estudiante $k$ está en ambos cursos.
La suma sobre todos los elementos de $k$ representa entonces que para cursos $i$ y $j$ fijos, estamos tomando todos los estudiantes y contando (sumando) sólo aquellos que están simultáneamente en $i$ y $j$.
¡La suma anterior dará el total de estudiantes que existen en común entre el curso $i$ y el curso $j$!
Observación: Lo anterior funciona porque $E$ toma los valores 0 y 1.
Si $E_{kj}$ fueran las horas que invierte el estudiante $k$ en el curso $j$, entonces la interpretación no sería correcta.
Por supuesto, la matriz es simétrica. Esta matiz se llama "matriz de clashing" o "matriz de conflicto" y permite conocer que asignaturas no pueden programarse a la misma hora (y cuales sí pueden programarse de manera simultánea).
Recordemos que la matriz era la siguiente: $$ E = \left( \begin{matrix} 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1 & 0 & 0 \end{matrix} \right) $$
De manera completamente análoga, $E \cdot E^T$ posee dimensiones $N_e$ filas y $N_e$ columnas, y su elemento $i,j$ representa la cantidad de cursos que el estudiante $i$ tiene en común con el estudiante $j$.
import numpy as np
E = np.matrix([ [0 , 1 , 1 , 1 , 0 , 1 , 0 ],
[1 , 0 , 0 , 0 , 1 , 1 , 1 ],
[1 , 1 , 1 , 1 , 1 , 1 , 1 ],
[1 , 1 , 1 , 1 , 1 , 1 , 1 ],
[1 , 1 , 1 , 1 , 1 , 0 , 0 ],
])
print(E)
[[0 1 1 1 0 1 0] [1 0 0 0 1 1 1] [1 1 1 1 1 1 1] [1 1 1 1 1 1 1] [1 1 1 1 1 0 0]]
Multiplicación por vector fila por la izquierda:
vf = np.matrix([1,1,1,1,1])
print(vf.shape, E.shape)
print(vf * E)
(1, 5) (5, 7) [[4 4 4 4 4 4 3]]
Multiplicación por vector columna por la derecha:
vc = np.matrix([1,1,1,1,1,1,1])
print(E.shape, vc.shape)
print(E * vc.T)
(5, 7) (1, 7) [[4] [4] [7] [7] [5]]
Contar el total de inscripciones:
vf = np.matrix([1,1,1,1,1])
vc = np.matrix([1,1,1,1,1,1,1]).T
print(vf.shape, E.shape, vc.shape)
print(vf * E * vc)
(1, 5) (5, 7) (7, 1) [[27]]
¡Ojo! Obtenemos una matriz de 1x1
Cantidad de estudiantes en común entre distintos cursos, $E^T \cdot E$:
print(E.T * E)
[[4 3 3 3 4 3 3] [3 4 4 4 3 3 2] [3 4 4 4 3 3 2] [3 4 4 4 3 3 2] [4 3 3 3 4 3 3] [3 3 3 3 3 4 3] [3 2 2 2 3 3 3]]
Cantidad de cursos en común entre estudiantes, $E \cdot E^T$:
print(E * E.T)
[[4 1 4 4 3] [1 4 4 4 2] [4 4 7 7 5] [4 4 7 7 5] [3 2 5 5 5]]
Consideremos un conjunto de datos real, con las siguientes características:
Considerando 5 inscripciones por estudiante, deberían ser cerca de 55 mil inscripciones.
Carguemos la matriz con datos reales:
import numpy as np
E = np.matrix(np.loadtxt("E.csv", delimiter=";"))
print(E.shape)
(11249, 919)
print(E[:5,:7]) # Mostrando los primeros 5 estudiantes y los primeros 7 cursos
[[1. 0. 0. 0. 0. 0. 0.] [1. 0. 0. 0. 0. 0. 0.] [1. 0. 0. 0. 0. 0. 0.] [1. 0. 0. 0. 0. 0. 0.] [1. 0. 0. 0. 0. 0. 0.]]
En realidad, no necesitamos que sean "números flotantes" (floats) basta con que sean números enteros (ints). Esto nos permitiría incluso ahorrar RAM, pero cuidado, puede traer efectos colaterales si no se maneja con cuidado.
E_float = np.matrix(np.loadtxt("E.csv", delimiter=";"))
E_int = np.matrix(np.loadtxt("E.csv", delimiter=";", dtype=np.int8))
print(E_float.dtype)
print(E_int.dtype)
float64 int8
print(E_float.shape)
print(E_int.shape)
(11249, 919) (11249, 919)
print(E_float[:1,:1].nbytes)
print(E_int[:1,:1].nbytes)
print(E_float.nbytes / E_int.nbytes)
8 1 8.0
Volvamos a cargar los datos, considerando elementos de tipo entero:
%%time
E = np.matrix(np.loadtxt("E.csv", delimiter=";", dtype=int))
CPU times: user 8.31 s, sys: 385 ms, total: 8.7 s Wall time: 7.75 s
print("Tamaño: ", E.shape) # Estudiantes, cursos
print("Tipo elementos: ", E.dtype) # 64 bits
print("Tamaño de un elemento: ", E[:1,:1].nbytes) # tamaño de cada elemento
print("Tamaño matriz (en Mb): ", E.nbytes/(1024*1024)) # tamaño de matriz en la RAM
print("Algunos elementos:\n", E[:5,:7]) # Algunos elementos
Tamaño: (11249, 919) Tipo elementos: int64 Tamaño de un elemento: 8 Tamaño matriz (en Mb): 78.87139129638672 Algunos elementos: [[1 0 0 0 0 0 0] [1 0 0 0 0 0 0] [1 0 0 0 0 0 0] [1 0 0 0 0 0 0] [1 0 0 0 0 0 0]]
Tratemos de mirar la matriz usando algunas herramientas gráficas:
from matplotlib import pyplot as plt
fig, ax = plt.subplots(figsize=(32,32))
ax.matshow(E.T, aspect='equal')
plt.box(False)
plt.xlabel("Estudiante")
plt.ylabel("Curso")
plt.show()
Tratemos de mirar la matriz usando algunas herramientas gráficas:
from matplotlib import pyplot as plt
fig, ax = plt.subplots(figsize=(32,32))
ax.matshow(E.T, cmap=plt.cm.Greys, aspect='equal')
plt.xlabel("Estudiante")
plt.ylabel("Curso")
plt.show();
Tratemos de examinar algunos elementos de la matriz usando algunas herramientas gráficas de manera apropiada:
from matplotlib import pyplot as plt
fig, ax = plt.subplots(figsize=(32,10))
cax = ax.matshow(E[:5,:7], cmap=plt.cm.Greys, aspect='equal')
plt.colorbar(cax)
plt.xlabel("Curso")
plt.ylabel("Estudiante")
plt.grid(True)
plt.suptitle("Algunos elementos de la matriz - Numeración parte en 0")
plt.show()
Calculemos la cantidad de inscripciones totales usando varios métodos distintos y midiendo el tiempo que toma realizar la operación.
Recordemos que la matriz es de un tamaño mediano, $11,500 * 900$ aproximadamente.
%%time
# Version Naive
Ne, Nc = E.shape
E_sum = 0
for i in range(Ne):
for j in range(Nc):
E_sum = E_sum + E[i,j]
print("Cantidad de inscripciones: ", E_sum)
Cantidad de inscripciones: 51252 CPU times: user 8.18 s, sys: 51.8 ms, total: 8.23 s Wall time: 7.8 s
El tiempo de ejecución depende del computador usado.
%%time
vector_uno_cursos = np.matrix(np.ones([Nc,1]))
vector_uno_estudiantes = np.matrix(np.ones([Ne,1]))
E_sum = (vector_uno_estudiantes.T * E) * vector_uno_cursos
print(E_sum)
[[51252.]] CPU times: user 85.4 ms, sys: 29.7 ms, total: 115 ms Wall time: 55 ms
%%time
vector_uno_cursos = np.matrix(np.ones([Nc,1], dtype=int))
vector_uno_estudiantes = np.matrix(np.ones([Ne,1], dtype=int))
E_sum = (vector_uno_estudiantes.T * E) * vector_uno_cursos
print(E_sum)
[[51252]] CPU times: user 332 ms, sys: 6.94 ms, total: 339 ms Wall time: 57.6 ms
Destacan 2 cosas: existe el fenómeno de "casting" en el cual el numero real (flotante) toma precedencia sobre el entero, y que el resultado sigue siendo una matriz (de 1 fila por 1 columna).
%%time
# Versión nativa - matricial
E_sum = E.sum()
print("Cantidad de inscripciones: ", E_sum)
Cantidad de inscripciones: 51252 CPU times: user 46.2 ms, sys: 2.75 ms, total: 49 ms Wall time: 8.14 ms
Resultado:
Puede existir una diferencia de hasta 1000 veces en el tiempo de ejecución de un conteo tan sencillo como la suma de los elementos de una matriz.
Seguir el principio KISS: Keep It Simple, Stupid!
%%time
# Versión Naive : Toma demasiado tiempo!
N_aux = 10
ETE_v2 = np.zeros([N_aux, N_aux])
for i in range(N_aux):
print("Fila %d de %d. Porcentaje de las filas completado: %.2f" %(i+1, N_aux, 100.*(i+1)/N_aux))
for j in range(N_aux):
for k in range(Ne):
ETE_v2[i,j] = ETE_v1[i,j] + E[k,i]*E[k,j]
Fila 1 de 10. Porcentaje de las filas completado: 10.00
--------------------------------------------------------------------------- NameError Traceback (most recent call last) <timed exec> in <module> NameError: name 'ETE_v1' is not defined
print(ETE_v2[:5,:5])
[[0. 0. 0. 0. 0.] [0. 0. 0. 0. 0.] [0. 0. 0. 0. 0.] [0. 0. 0. 0. 0.] [0. 0. 0. 0. 0.]]
Para una matriz de $10$ por $10$ $=$ $100$ combinaciones de cursos necesitamos aproximadamente 2 segundos.
Para una matriz de $919$ cursos por $919$ cursos existen $844,561$ combinaciones y necesitamos 2.2 * 844,561 / 100 segundos, es decir, ¡más de 4 horas!.
print(919 * 919)
t = 2.0
print(t * 919 * 919 / 100 / 3600)
844561 4.692005555555556
E.dtype
dtype('int64')
%%time
# Versión matricial (nativa)
ETE_v3 = E.T * E
CPU times: user 1min 17s, sys: 688 ms, total: 1min 18s Wall time: 1min 18s
print(ETE_v3[:5,:5])
[[ 5 0 0 0 0] [ 0 545 0 0 0] [ 0 0 135 40 2] [ 0 0 40 97 2] [ 0 0 2 2 50]]
Podemos calcular todas el resultado para todos los cursos mediante multiplicación matricial en menos de 90 segundos.
from matplotlib import pyplot as plt
def plot_matrix(A):
fig, ax = plt.subplots(figsize=(12,12))
A_aux = A.astype(float)
masked_matrix = np.ma.array(A_aux, mask=(A_aux==0))
cmap = plt.cm.Reds
cmap.set_bad(color='white')
cax = ax.matshow(masked_matrix, cmap=cmap, aspect='equal', interpolation='none')
plt.colorbar(cax)
plt.box(False)
plt.grid(True)
plt.xlabel("Curso", fontsize=10)
plt.ylabel("Curso")
plt.show()
plot_matrix(ETE_v3[:,:])
/miniconda3/lib/python3.7/site-packages/ipykernel_launcher.py:8: MatplotlibDeprecationWarning: You are modifying the state of a globally registered colormap. In future versions, you will not be able to modify a registered colormap in-place. To remove this warning, you can make a copy of the colormap first. cmap = copy.copy(mpl.cm.get_cmap("Reds"))
Para asignar las evaluaciones de manera compatible, es necesario:
Acá sólo hemos considerado la matriz de estudiantes y cursos, pero también es necesario:
Las otras características también son representadas mediante matrices sobre las cuales las operaciones de álgebra lineal permiten obtener soluciones en un tiempo acotado a pesar de la dificultad del problema.