Lien de la note Hackmd
Cours du 30 / 03
Nuage de points
On peut étudier la forme d’un nuage de points par une analyse en composantes principales (ACP), c.a.d. chercher les vecteurs propres de la matrice de covariance ou de corrélation.
On vérifie avec un nuage de points ayant une corrélation forte entre $x$ et $y$ : \(y = 0.2 \, x + 1.45 + U(-1,1) \quad \textrm{avec U la loi uniforme qui simule du bruit.}\) Entre x et y il y a:
- une pente de 0.2
- un décalage vertical de 1.45 en x = 0
On essaye de retrouver la corrélation entre x et y malgré le bruit avec seulement le nuage de points.
1
2
3
N = 50
x = 6 * np.random.rand(N) - 3
nuage = np.array([x, 0.2 * x + 1.45 + np.random.rand(N)])
On cherche la droite qui minimise la distance entre les points et leur projection sur la droite.
1
cov = np.cov(nuage.copy()) # estime la matrice de covariance
1
2
array([[2.744, 0.48 ],
[0.48 , 0.168]])
1
2
val, vec = lin.eig(cov)
val = val.astype('float') # on convertit puisqu'on sait que ce sont des réels
1
2
3
4
5
Valeurs propres de la matrice de covariance : [2.831 0.081]
Vecteurs propres de la matrice de covariance :
[[ 0.984 -0.177]
[ 0.177 0.984]]
1
moyenne = nuage.mean(axis=1) # Point moyen du nuage
1
[0.328 2.085]
1
eq_droite = lambda x: pente * (x - moyenne[0]) + moyenne[1]
Matrice de covariance
La covariance entre deux variables indique à quel point elles sont liées. \(\textrm{cov}(\textbf{x},\textbf{y}) = \frac{1}{N} \sum_{i=1}^N (x_i - \overline{\textbf{x}}) (y_i - \overline{\textbf{y}})\)
- $N$ le nombre de points du nuage
- $\overline{\textbf{x}}$ et $\overline{\textbf{y}}$ les moyennes de $\textbf{x}$ et de $\textbf{y}$.
La matrice de covariance exprime toutes les covariances possibles :
\[\textrm{Cov(nuage 2D)} = \begin{bmatrix} \textrm{cov}(\textbf{x},\textbf{x}) & \textrm{cov}(\textbf{x},\textbf{y}) \\ \textrm{cov}(\textbf{y},\textbf{x}) & \textrm{cov}(\textbf{y},\textbf{y}) \\ \end{bmatrix}\]1
2
3
cov = lambda x,y : np.dot((x - x.mean()), (y - y.mean())) / len(x)
Cov = lambda x,y : np.array([[cov(x,x), cov(x,y)], [cov(y,x), cov(y,y)]])
Cov(nuage[0], nuage[1])
1
2
array([[2.69 , 0.47 ],
[0.47 , 0.164]])
Fibonnacci
Tu le sais, je le sais, on le sais Fibonnacci c’est ca : \(x_n = x_{n-2} + x_{n-1}\)
- $x_0 = 1$
- $x_1 = 1$.
Quelle est la complexité pour calculer $x_n$?
Ecrivons fibonnacci sous forme d’un système matriciel :
\[x_{n-1} = x_{n-1} \\ x_n = x_{n-2} + x_{n-1} \\\]ce qui donne
\[\begin{bmatrix} x_{n-1}\\ x_n \\ \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix} \begin{bmatrix} x_{n-2}\\ x_{n-1} \\ \end{bmatrix}\]Calculer n produits matriciels n’est pas rentable.
1
2
fval, fvec = lin.eig(F)
fval = fval.astype('float') # la matrice est symétrique donc ses valeurs propres sont réelles
1
2
3
4
5
Valeurs propres de la matrice de fibonnacci : [-0.618 1.618]
Vecteurs propres de la matrice de fibonnacci :
[[-0.851 -0.526]
[ 0.526 -0.851]]
1
fibo = lambda n : (fvec @ np.diag(fval**n) @ lin.inv(fvec) @ x0)[0]
Google page rank
Soit $N$ pages web numerotées qui font référence les unes aux autres. La i-ième ligne montre par qui est référencée la i-ième page web. Il y a 1 dans la j-ième colonne si la page j cite la page i et 0 sinon.
1
2
3
4
np.random.seed(42)
A = np.random.randint(2,size=(8,8))
for i in range(len(A)):
A[i,i] = 0 # on ne compte pas les auto-référencements
1
2
3
4
5
6
7
8
array([[0, 1, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0],
[1, 1, 0, 0, 1, 0, 1, 1],
[1, 1, 1, 0, 1, 1, 0, 0],
[1, 1, 1, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0, 1, 0],
[1, 1, 0, 1, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0]])
Le classement des pages utilise les vecteurs propres de cette matrice.
1
2
3
val_pr, vec_pr = lin.eig(A)
np.abs(vec_pr[:,0]).astype(float) # valeur des pages
A.sum(axis=1) # nombre de citations
1
2
Valeur des pages : [0.217 0.153 0.376 0.489 0.243 0.514 0.47 0.071]
Nombre de citations : [2 1 5 5 3 4 5 1]