lr_voronoi.rst

Régression logistique, diagramme de Voronoï, k-Means

régression logistique, diagramme de Voronoï, Voronoï

Ce qui suit explore les liens entre une régression logistique, les diagrammes de Voronoï pour construire un classifieur qui allient la régression logistique et les clustering type k-means. Le point de départ est une conjecture : les régions créées par une régression logistique sont convexes.

Diagramme de Voronoï

diagramme de Voronoï

Un diagramme de Voronoï est le diagramme issu des intersections des médiatrices entre n points.

On définit un ensemble de points (X₁, ..., X_n). La zone d'influence de chaque point est défini par V(X_i) = {x|d(x, X_i) ≤ d(x, X_j)∀j}. Si d est la distance euclidienne, la frontière entre deux points X_i, X_j est un segment sur la droite d'équation d(x, X_i) = d(x, X_j) :

$$\begin{aligned} \begin{array}{ll} &\norme{x-X_i}^2 - \norme{x-X_j}^2 = 0 \\\ \Longrightarrow & \norme{x}^2 - 2 \scal{x}{X_i} + \norme{X_i}^2 - (\norme{x}^2 - 2 \scal{x}{X_j} + \norme{X_j}^2) = 0 \\\ \Longrightarrow & 2 \scal{x}{X_j - X_i} + \norme{X_i}^2 - \norme{X_j}^2 = 0 \\\ \Longrightarrow & 2 \scal{x}{X_j - X_i} + \frac{1}{2} \scal{X_i + X_j}{X_i - X_j} = 0 \\\ \Longrightarrow & \scal{x - \frac{X_i + X_j}{2}}{X_i - X_j} = 0 \end{array} \end{aligned}$$

Ce système constitue $\frac{n(n-1)}{2}$ droites ou hyperplans si l'espace vectoriel est en dimension plus que deux. Le diagramme de Voronoï est formé par des segments de chacune de ces droites. On peut retourner le problème. On suppose qu'il existe $\frac{n(n-1)}{2}$ hyperplans, existe-t-il n points de telle sorte que les hyperplans initiaux sont les frontières du diagramme de Voronoï formé par ces n points ? La réponse est pas dans tous les cas ce qui veut dire non dans le cas générique. Les paragraphes qui suivent expliquent pourquoi.

Régression logistique

scikit-learn a rendu populaire le jeu de données Iris qui consiste à classer des fleurs en trois classes en fonction des dimensions de leurs pétales.

from sklearn.datasets import load_iris data = load_iris() X, y = data.data[:, :2], data.target

from sklearn.linear_model import LogisticRegression clr = LogisticRegression() clr.fit(X, y)

print(clr.coef) print(clr.intercept)

La fonction de prédiction est assez simple : f(x) = Ax + B. La classe d'appartenance du point x est déterminé par max_if(x)_i. La frontière entre deux classes i, j est définie par les deux conditions : max_kf(x)_k = f(x)_i = f(x)_j. On retrouve bien $\frac{n(n-1)}{2}$ hyperplans. On définit la matrice A comme une matrice ligne (L₁, ..., L_n) où n est le nombre de classes. L'équation de l'hyperplan entre deux classes devient :

$$\begin{aligned} \begin{array}{ll} & L_i X + B_i = L_j X + B_j \\\ \Longleftrightarrow & (L_i - L_j) X + B_i - B_j = 0 \\\ \Longleftrightarrow & \scal{L_i - L_j}{X} + B_i - B_j = 0 \\\ \Longleftrightarrow & \scal{L_i - L_j}{X - \frac{L_i + L_j}{2}} + \scal{L_i - L_j}{\frac{L_i + L_j}{2}} + B_i - B_j = 0 \\\ \Longleftrightarrow & \scal{L_i - L_j}{X - \frac{L_i + L_j}{2}} + \frac{1}{2}\norme{L_i}^2 - \frac{1}{2}\norme{L_j}^2 + B_i - B_j = 0 \\\ \Longleftrightarrow & \scal{L_i - L_j}{X - \frac{L_i + L_j}{2}} + \frac{1}{2}\norme{L_i}^2 + B_i - (\frac{1}{2}\norme{L_j}^2 + B_j) = 0 \end{array} \end{aligned}$$

Il y a peu de chance que cela fonctionne comme cela. Avant de continuer, assurons-nous que les régions associées aux classes sont convexes. C'est une condition nécessaire mais pas suffisante pour avoir un diagramme de Voronoï.

Soit X₁ et X₂ appartenant à la classe i. On sait que que ∀k, L_iX₁ + B_i ≥ L_kX₁ + B_k et ∀k, L_iX₂ + B_i ≥ L_kX₂ + B_k. On considère un point X sur le segment [X₁, X₂], donc il existe α, β ≥ 0 tel que X = αX₁ + βX₂ et α + β = 1. On vérifie que :

$$\begin{aligned} \begin{array}{ll} & L_i X + B_i = L_i (\alpha X_1 + \beta X_2) + B_i = \alpha(L_i X_1 + B_i) + \beta(L_i X_2 + B_i) \\\ \geqslant & \alpha(L_k X_1 + B_k) + \beta(L_k X_2 + B_k) = L_k (\alpha X_1 + \beta X_2) + B_k \forall k \end{array} \end{aligned}$$

Donc le point X appartient bien à classe i et celle-ci est convexe. La régression logistique forme une partition convexe de l'espace des features.

On définit l'application ℝ^d → ℕ qui associe la plus grande coordonnées f(X) = arg max_k(AX + B)_k. A est une matrice ℳ_dc, B est un vecteur de ℝ^d, c est le nombre de parties. L'application f définit une partition convexe de l'espace vectoriel ℝ^d.

Revenons au cas de Voronoï. La classe prédite dépend de max_k(Ax + B)_k. On veut trouver n points (P₁, ..., P_n) tels que chaque couple (P_i, P_j) soit équidistant de la frontière qui sépare leurs classes. Il faut également les projections des deux points sur la frontière se confondent et donc que les vecteurs P_i − P_j et L_i − L_j sont colinéaires.

$$\begin{aligned} \begin{array}{ll} &\left\{\begin{array}{l}\scal{L_i - L_j}{P_i} + B_i - B_j = - \pa{ \scal{L_i - L_j}{P_j} + B_i - B_j } \\\ P_i- P_j - \scal{P_i - P_j}{\frac{L_i-L_j}{\norm{L_i-L_j}}} \frac{L_i-L_j}{\norm{L_i-L_j}}=0 \end{array} \right. \\\ \Longleftrightarrow & \left\{\begin{array}{l}\scal{L_i - L_j}{P_i + P_j} + 2 (B_i - B_j) = 0 \\\ P_i- P_j - \scal{P_i - P_j}{\frac{L_i-L_j}{\norm{L_i-L_j}}} \frac{L_i-L_j}{\norm{L_i-L_j}}=0 \end{array} \right. \end{array} \end{aligned}$$

La seconde équation en cache en fait plusieurs puisqu'elle est valable sur plusieurs dimensions mais elles sont redondantes. Il suffit de choisir un vecteur u_ij non perpendiculaire à L_i − L_j de sorte que qui n'est pas perpendiculaire au vecteur L_i − L_j et de considérer la projection de cette équation sur ce vecteur. C'est pourquoi on réduit le système au suivant qui est équivalent au précédent si le vecteur u_ij est bien choisi.

$$\begin{aligned} \begin{array}{ll} \Longrightarrow & \left\{\begin{array}{l}\scal{L_i - L_j}{P_i + P_j} + 2 (B_i - B_j) = 0 \\\ \scal{P_i- P_j}{u_{ij}} - \scal{P_i - P_j}{\frac{L_i-L_j}{\norm{L_i-L_j}}} \scal{\frac{L_i-L_j}{\norm{L_i-L_j}}}{u_{ij}}=0 \end{array} \right. \end{array} \end{aligned}$$

Faisons un peu de géométrie avant de résoudre ce problème car celui-ci a dans la plupart des cas plus d'équations que d'inconnues. Chaque frontière entre deux classes est la médiatrice d'un segment [P_i, P_j]. Le dessin suivant trace un diagramme de Voronoï à trois points. L'intersection est le centre des médiatrices du triangle formé par les points de Voronoï. Pour les trouver, on trace un cercle, n'importe lequel, puis une droite perpendiculaire à l'une des médiatrice. On obtient deux points. Le troisième est obtenu en traçant une seconde perpendiculaire et par construsction, la troisième droite est perpendiculaire à la troisième médiatrice. Et on nomme les angles.

Les triangles formés par les côtés jaunes sont isocèles. On en déduit que a + b + c = 2π = 2(x + y + z). On en déduit aussi que :

$$\begin{aligned} \begin{array}{rcl} x + y &=& a \\\ y + z &=& c \\\ x + z &=& b \end{array} \end{aligned}$$

On en conclut que a + b + c = 2π = 2(x + y + z) = 2(x + c) et x = π − c. Il existe une infinité de triplets de 3 points qui aboutissent à ce diagramme de Voronoï. Il suffit de changer la taille du cercle. On montre aussi qu'en dimension 2 et 3 classes, il existe toujours une solution au problème posé. Maintenant, si on considère la configuration suivante avec des points disposés de telle sorte que le diagramme de Voronoï est un maillage hexagonal. $a=b=c=\frac{2\pi}{3}$ et $x=y=z=\frac{\pi}{3}$. Il n'existe qu'un ensemble de points qui peut produire ce maillage comme diagramme de Voronoï. Mais si on ajoute une petite zone (dans le cercle vert ci-dessous), il est impossible que ce diagramme soit un diagramme de Voronoï bien que cela soit une partition convexe.

On revient à la détermination du diagramme de Voronoï associé à une régression logistique. On a montré qu'il n'existe pas tout le temps, qu'il peut y avoir une infinité de solutions et qu'il est la solution d'un système d'équations linéaires.

Partition convexe

On a montré que la régression logistique réalise une partition convexe de l'espace vectoriel des variables. On peut se poser la question de la réciproque : est-ce que toute partition convexe d'un espace vectoriel peut être décrite avec une régression logistique ou plus précisément par la fonction décrite par le théorème convexité des classes formées par une régression logistique <th-thlogregpartconv>. Considérons d'abord deux parties voisines d'une partition convexe.

L'image qui précède montre une partition qui n'est pas convexe. La partie A l'est mais pas la partie B. En fait, il est facile de montrer que la seule frontière admissible entre deux parties convexe est un hyperplan. Si la partition contient n partie, il y a au pire $\frac{n(n-1)}{2}$ frontières, ce qui correspond également au nombre d'hyperplans définis par la fonction de prédiction associée à la régression logistique.

L'image qui précède présente une classification en trois zones (droites noires). On a choisi une droite bleue au hasard. En prenant son symétrique par rapport à une des droites noires (D), on a deux droites D₁, D₂. L'ensemble des points $\acc{x | d(x, D_1) = d(x, D_2)}$ correspond à la droite noire. Il doit être de même pour les trois droites bleues, autrement dit, l'intersection des droites est le centre du cercle inscrit dans le triangle bleu ce qui n'est visiblement pas le cas sur l'image.

Notebooks

boule unité

Le notebook qui suit reprend les différents éléments théoriques présentés ci-dessus. Il continue l'étude d'une régression logistique et donne une intuition de ce qui marche ou pas avec un tel modèle. Notamment, le modèle est plus performant si les classes sont situées sur la boule unité de l'espace des features.

../notebooks/logreg_voronoi