Calculer et représenter graphiquement la frontière de décision LDA

19

J'ai vu un tracé LDA (analyse discriminante linéaire) avec les limites de décision de The Elements of Statistical Learning :entrez la description de l'image ici

Je comprends que les données sont projetées sur un sous-espace de dimension inférieure. Cependant, je voudrais savoir comment nous obtenons les limites de décision dans la dimension d'origine de telle sorte que je puisse projeter les limites de décision sur un sous-espace de dimension inférieure (comme les lignes noires dans l'image ci-dessus).

Existe-t-il une formule que je peux utiliser pour calculer les limites de décision dans la dimension d'origine (supérieure)? Si oui, de quels intrants cette formule a-t-elle besoin?

mon nom est Jeff
la source
3
Plutôt que des limites de décision, vous trouverez probablement plus d'utilité dans l'examen des probabilités postérieures d'appartenance à une classe. Cela peut être fait avec moins d'hypothèses en utilisant une régression logistique polytomique (multinomiale) mais peut aussi être fait avec des LDA (probabilités postérieures).
Frank Harrell
2
Au sein de la LDA, ces limites de classification constituent ce que l'on appelle une carte territoriale . Je travaille avec SPSS, et il le trace , bien qu'au format texte. Selon un concepteur de SPSS, les limites se trouvent facilement par approche pratique:
ttnphns
3
(suite) chaque point d'une grille fine est classé LDA, puis si un point a été classé comme ses voisins, ce point n'est pas affiché. Ainsi, seules les frontières en tant que «bandes d'ambiguïté» sont finalement laissées. Référence: they (bondaries) are never computed. The plot is drawn by classifying every character cell in it, then blanking out all those surrounded by cells classified into the same category.
ttnphns

Réponses:

22

Ce chiffre particulier dans Hastie et al. a été produit sans calculer les équations des limites des classes. Au lieu de cela, l'algorithme décrit par @ttnphns dans les commentaires a été utilisé, voir la note de bas de page 2 de la section 4.3, page 110:

Pour cette figure et de nombreuses figures similaires dans le livre, nous calculons les limites de décision par une méthode de contourage exhaustive. Nous calculons la règle de décision sur un réseau fin de points, puis utilisons des algorithmes de contour pour calculer les limites.

Cependant, je vais continuer à décrire comment obtenir des équations des limites de classe LDA.

Commençons par un exemple 2D simple. Voici les données du jeu de données Iris ; Je rejette les mesures des pétales et ne considère que la longueur et la largeur des sépales. Trois classes sont marquées avec des couleurs rouge, vert et bleu:

Ensemble de données Iris

Notons les moyennes de classe (centroïdes) comme . LDA suppose que toutes les classes ont la même covariance intra-classe; étant donné les données, cette matrice de covariance partagée est estimée (jusqu'à l'échelle) comme , où la somme est sur tous les points de données et le centroïde de la classe respective est soustrait de chaque point.μ1,μ2,μ3W=je(Xje-μk)(Xje-μk)

Pour chaque paire de classes (par exemple les classes et ), il y a une limite de classe entre elles. Il est évident que la frontière doit passer par le point médian entre les deux centroïdes de classe . L'un des résultats centraux de la LDA est que cette frontière est une droite orthogonale à . Il y a plusieurs façons d'obtenir ce résultat, et même si cela ne faisait pas partie de la question, j'en mentionnerai brièvement trois dans l'annexe ci-dessous.12(μ1+μ2)/2W-1(μ1-μ2)

Notez que ce qui est écrit ci-dessus est déjà une spécification précise de la frontière. Si l'on veut avoir une équation linéaire sous la forme standard , alors les coefficients et peuvent être calculés et seront donnés par des formules désordonnées. Je peux difficilement imaginer une situation où cela serait nécessaire.y=uneX+buneb

Appliquons maintenant cette formule à l'exemple d'Iris. Pour chaque paire de classes, je trouve un point médian et trace une ligne perpendiculaire à :W-1(μje-μj)

LDA de l'ensemble de données Iris, limites de décision

Trois lignes se croisent en un point, comme on aurait pu s'y attendre. Les limites de décision sont données par des rayons partant du point d'intersection:

LDA de l'ensemble de données Iris, limites de décision finale

Notez que si le nombre de classes est , alors il y aura paires de classes et donc beaucoup de lignes, toutes se croisant dans un désordre emmêlé. Pour dessiner une belle image comme celle de Hastie et al., Il suffit de ne garder que les segments nécessaires, et c'est un problème algorithmique distinct en soi (pas lié à LDA en aucune façon, car on n'en a pas besoin pour faire la classification; pour classer un point, vérifiez la distance de Mahalanobis à chaque classe et choisissez celle qui a la distance la plus faible, ou utilisez une série ou des LDA par paire).K2K(K-1)/2

Dans les dimensions , la formule reste exactement la même : la frontière est orthogonale à>2W-1(μ1-μ2) et passe par . Cependant, dans les dimensions supérieures, il ne s'agit plus d'une ligne, mais d'un hyperplan de dimensions . À des fins d'illustration, on peut simplement projeter l'ensemble de données sur les deux premiers axes discriminants, et ainsi réduire le problème au cas 2D (c'est, je crois, ce qu'a fait Hastie et al. Pour produire cette figure).(μ1+μ2)/2-1

appendice

Comment voir que la frontière est une ligne droite orthogonale à W-1(μ1-μ2) ? Voici plusieurs façons d'obtenir ce résultat:

  1. La manière fantaisiste:W-1 induit la métrique de Mahalanobis dans le plan; la frontière doit être orthogonale à dans cette métrique, QED.μ1-μ2

  2. La méthode gaussienne standard: si les deux classes sont décrites par des distributions gaussiennes, la probabilité logarithmique qu'un point appartient à la classe est proportionnelle à . A la frontière les probabilités d'appartenance aux classes etXk(X-μk)W-1(X-μk)12 sont égales; écrivez-le, simplifiez et vous obtiendrez immédiatement , QED.XW-1(μ1-μ2)=const

  3. La manière laborieuse mais intuitive. Imaginez que est une matrice d'identité, c'est-à-dire que toutes les classes sont sphériques. La solution est alors évidente: la frontière est simplement orthogonale à . Si les classes ne sont pas sphériques, alors on peut les faire en sphères. Si la décomposition propre de est , alors matrix fera l'affaire (voir par exemple ici ). Donc, après avoir appliqué et demandé à quoi il est maintenant orthogonal, la réponse (à gauche comme exercice) est:Wμ1-μ2WW=UUS=-1/2US , la frontière est orthogonale à . Si nous prenons cette limite, retransformez-la avecS(μ1-μ2)S-1SS(μ1-μ2) . En branchant l'expression de , nous obtenons QED.S

amibe dit réintégrer Monica
la source
Je n'ai pas étudié votre réponse. Cela semble sophistiqué et peut-être correct. Qu'en est-il de l'approche pratique et plus simple de «saupoudrer, classer puis déduire des limites» que j'ai décrite dans un commentaire? Votre approche est-elle comparable à ses résultats (qui sont évidemment corrects)? Qu'est-ce que tu penses?
ttnphns
1
@ttnphns: La seule partie technique de ma réponse (une liste numérotée avec 3 éléments) fournit des preuves et peut être sautée en toute sécurité. Le reste, je crois, n'est pas particulièrement sophistiqué! Peut-être devrais-je déplacer cette partie "supplémentaire" vers le bas, en annexe? Concernant vos commentaires: je pense que c'est une approche valable, et j'aime l'aspect ASCII de la "carte territoriale" du SPSS. Peut-être pourriez-vous déplacer vos commentaires dans une réponse séparée (et donner une image exemplaire de la carte SPSS là-bas), je pense que ce serait utile pour de futures références. Les résultats doivent bien entendu être équivalents.
amibe dit Réintégrer Monica
@ttnphns: Il s'avère que Hastie et al. utilisé exactement la méthode que vous avez décrite ici pour tracer leurs chiffres, y compris celui reproduit dans le PO. J'ai trouvé une note de bas de page disant exactement cela (et mis à jour ma réponse, en la citant au début).
amibe dit Réintégrer Monica
Waouh! excellente réponse (3 ans plus tard!) puis-je vous demander comment vous avez pu dessiner les segments dans ce problème particulier?
Xavier Bourret Sicotte