CAMA : ma05 Vectors propres – Applications

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.2x+1.45+U(-1,1)\text{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.

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.

On construit la matrice de covariance, le premier vecteur propre est égal au coefficient 0.2 et est le vecteur directeur de la droite recherchée. On fait la moyenne du nuage de point dans un point de la droite.

cov = np.cov(nuage.copy()) # estime la matrice de covariance

array([[2.744, 0.48 ],
       [0.48 , 0.168]])

val, vec = lin.eig(cov)
val = val.astype('float')  # on convertit puisqu'on sait que ce sont des réels

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]]

moyenne = nuage.mean(axis=1) # Point moyen du nuage

[0.328 2.085]

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.

$$\text{cov}(\mathbf{\text{x}},\mathbf{\text{y}})=\frac{1}{N}\sum _{i=1}^N(x_i-\overline{\mathbf{\text{x}}})(y_i-\overline{\mathbf{\text{y}}})$$

• $N$ le nombre de points du nuage
• $\overline{\mathbf{\text{x}}}$ et
  $\overline{\mathbf{\text{y}}}$ les moyennes de
  $\mathbf{\text{x}}$ et de
  $\mathbf{\text{y}}$.

La matrice de covariance exprime toutes les covariances possibles :

$$\text{Cov(nuage 2D)}=\left[\begin{array}{cc}\text{cov}(\mathbf{\text{x}},\mathbf{\text{x}})& \text{cov}(\mathbf{\text{x}},\mathbf{\text{y}})\\ \text{cov}(\mathbf{\text{y}},\mathbf{\text{x}})& \text{cov}(\mathbf{\text{y}},\mathbf{\text{y}})\end{array}\right]$$

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])

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 :

$$\begin{array}{rl}{x}_{n-1}& =x_{n-1}\\ x_n& =x_{n-2}+x_{n-1}\end{array}$$
ce qui donne

$$\left[\begin{array}{c}{x}_{n-1}\\ x_n\end{array}\right]=\left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]\left[\begin{array}{c}{x}_{n-2}\\ x_{n-1}\end{array}\right]$$

Calculer n produits matriciels n'est pas rentable.

Sachant que

$F=PD{P}^{-1}$, avec P matrice des vecteurs propres et D matrice diagonale des valeurs propres :

$$\left[\begin{array}{c}{x}_n\\ x_{n+1}\end{array}\right]={\left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]}^n\left[\begin{array}{c}{x}_0\\ x_1\end{array}\right]=(PD{P}^{-1}{)}^n\left[\begin{array}{c}{x}_0\\ x_1\end{array}\right]=P{D}^n{P}^{-1}\left[\begin{array}{c}{x}_0\\ x_1\end{array}\right]$$
On peut calculer

$x_n$ en temps constant.

fval, fvec = lin.eig(F)
fval = fval.astype('float')  # la matrice est symétrique donc ses valeurs propres sont réelles

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]]

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.

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

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.

val_pr, vec_pr = lin.eig(A)
np.abs(vec_pr[:,0]).astype(float) # valeur des pages
A.sum(axis=1) # nombre de citations

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]

• La page ayant le meilleur score n'a que 4 citations mais est citée par les 3 pages ayant 5 citations
• une page ayant 5 citations est moins bien notée que les autres car elle n'est pas citée par la meilleure page

La matrice A est une application linéaire dont l'orientation principale est celle du premier vecteur propre. Le coefficient le plus important de ce vecteur indique la page web la plus importante.