Rappels sur les graphes

Section 2.4 Rappels sur les graphes

L'enjeu des méthodes que l'ont va introduire par la suite est de comprendre/capturer la variété qui explique l'échantillon des données. Pour représenter une variété au niveau discret, la notion de graphe apparaît très vite. On va donc introduire des rappels sur ces objets.

Subsection 2.4.1 Graphes et définition

Définition 2.30.

Soit \(V\) un nombre fini de sommets. Un graphe est définie par une paire \(G=[V,E]\) avec \(V\) l'ensembles des noeuds et \(E\) l'ensemble des arêtes ou un élément de \(E\) est une paire d'élément de \(V\) noté \((x,y)\) avec \(x,y \in V\text{.}\)

Dans la suite on considérera que des graphes non-orientés c'est à dire des graphes ou les arêtes \((x,y)\) et \((y,x)\) sont les mêmes.

Définition 2.31.

Soit \(x \in V\) un sommet on nomme \(d_x\) le degré de \(x\) le nombre d'arêtes qui connecte \(x\) à d'autre noeud. En général on note \(\Delta(G)\) et \(\delta(G)\) les degrés maximal et minimal. On parle d'un graphe régulier si \(\Delta(G)=\delta(G)\text{.}\)

Définition 2.32.

Soit \(x \in V\) un sommet on nomme le voisinage \(N(x)\) l'ensemble de sommets connectés à \(x\) par une arête.

En général afin de définir les connections entre l'ensembles des sommets, on introduit une matrice décrivant les connections.

Définition 2.33.

Soit \(G=[V,E]\) un graphe. La matrice d'adjacence est une matrice \(A\in \mathcal{M}_{n,n}(\mathbb{R})\) tel que

\begin{equation*} A_{ij}=\left\{\begin{array}{l} 1,\quad \mbox{ si } (x_i,x_j)\in E,\\ 0 ,\quad \mbox{ else }. \end{array}\right. \end{equation*}

On peut aussi nommé le graphe \(G=[V,A]\text{.}\)

Si le graphe est non-orientés la matrice est symétrique. On peut aussi considérer des graphes pondérés qui seront très utilisés pour travailler sur les échantillons de données. Cela revient a munir chaque arête d'un poids. Cela peut correspond a un coût par exemple.

Définition 2.34.

Soit \(G=[V,A]\) un graphe. Le graphe est pondéré si il est munit d'une matrice \(W\) tel que

\begin{equation*} W_{ij}=\left\{\begin{array}{l} w_{ij},\quad \mbox{ si }\quad A_{ij}\neq 0,\\ 0,\quad \mbox{else}. \end{array}\right. \end{equation*}

On peut le noter \(G=[V,W]\text{.}\)

Définition 2.35.

Soit \(G=[V,W]\) un graphe pondéré. On définit le volume (notion qui remplace le degré) d'un noeud comme

\begin{equation*} d_i = \sum_{j\in N(i)}w_{ij} \end{equation*}

Un graphe pondéré est non-orienté si \(W\) est symétrique. Dans le cas non-pondéré on peut toujours définir \(W=A\text{.}\)

Définition 2.36.

Soit \(G_1=[V_1,A_1]\) et \(G_2=[V_2,A_2]\) deux graphes. On dit que \(f:V_1\rightarrow V_2\) est une isométrie si pour toute paire \((u,v) \in V_1\) qui forment une arête de \(G_1\) la paire \((f(u),f(v)) \in V_2\) forment une arête de \(G_2\text{.}\)

Comme on a définit la notion de distance sur une variété par le chemin (courbe paramétrée) le plus court entre deux points, on peut définir la distance sur une graphe comme étant le chemin minimal entre ces deux points.

Définition 2.37.

Soit \(G=[V,A]\) un graphe. On définit un chemin entre \(x\) et \(y\) par:

\begin{equation*} \gamma(x,y) = ((x,z_1),(z_1,z_2),...,(z_n,y)) \end{equation*}

une succéssion d'arête qui relie les deux point. On définit la distance par

\begin{equation*} dis(x,y) = \operatorname{min}_{\gamma} \mid \gamma \mid \end{equation*}

avec \(\mid \gamma \mid\text{.}\) La longueur du chemin est donnée par le nombre d'arête dans le cas non-pondéré et par la somme des poids sur les arêtes du chemin dans le cas pondéré.

On voit une analogie entre la distance sur un graphe et la distane géodésique. Pour calculer la distance entre deux points sur graphe il existe différents algorithmes. Les plus connus sont les algorithmes de Dijkstra ou celui de Floyd-Warshall. On verra dans la suite que le graphe sera utilisé sur les données afin d'approcher la variété sous acjente.

Subsection 2.4.2 Algorithme des plus proche voisins

La méthode des k plus prochez voisins ( ou KNN) est une méthode très simple d'apprentissage supervisé et plus précisement de classification. On part du principe qu'on a un échantillon de taille \(n\text{:}\) \((x_1,...x_n)\) dont on connait la classe. On a un nouveau point \(x\) dont on cherche a déterminer la classe. Pour cela on trouve les \(k\) points les plus proches au sens d'une certaine distance \(d(x,y)\) puis on determine la classe de \(x\) à partir de la classe majoritaire chez les \(k\) voisins. On peut aussi pour construire un graphe à partir des données. Pour cela on connecte chaque noeud \(x\) a ses voisins. Il existe deux variantes: on connecte notre point a ses \(k\) plus proche voisins ou a tous les points dans une boule \(B(x,\epsilon)\text{.}\)

Algorithm 2.38. Algorithme des \(K\) plus proches voisins.

On part d'une matrice d'adjacence remplie de zéro
pour \(i \lt n\text{:}\)
- on calcule la distance \(d(x_i,x)\)
- on ajoute la distance à une liste des distance \(t_d\)
On trie \(t_d\) par ordre croissant.
on selection les \(K\) premiers élements du tableau et on modifie la matrice

\begin{equation*} A_{i,j_k}=d(x_i,x_{j_k}) \end{equation*}

avec \(j_1,...,j_k,...,j_K\) les indices associés aux \(K\) plus petites distances.

Il existe une autre variante ou on relie a un point \(x\) tous les sommets qui sont dans une boule de rayon epsilon \(\epsilon\) et de centre \(x\text{.}\)

Algorithm 2.39. Algorithme des \(\epsilon\) plus proches voisins.

On part d'une matrice d'adjacence remplie de zéro
pour \(i \lt n\text{:}\)
- pour \(j \lt n\text{:}\)
  - on calcule la distance \(d(x_i,x_j)\)
  - Si \(d(x_i,x_j)\lt \epsilon\)
    
    \begin{equation*} A_{i,j_k}=(x_i,x_j) \end{equation*}