Classification supervisée du niveau des joueurs à StarCraft2

StarCraft2 : un jeu de stratégie en temps réel

StarCraft2 propose des parties dans un format plutôt cours (20 à 60 minutes), les joueurs ont pour but de dresser une armée à l’aide d’une micro et macro économie gérées depuis une base. L’objectif est de détruire tous les batiments de l’adversaire. Il faut alors allier stratégie et perception pour pouvoir avoir un coup d’avance. Avec l’essor des jeux videos, des nouvelles scènes compétitives sont apparues. En effet, l’e-sport attire de plus en plus de monde comme par exemple le tournoi Fornite dans lequel le vainqueur a empoché 3 millions d’euros. Les prix sont donc très élevés et des équipes naissent dans l’objectif de remporter les compétitions. De surcroît, de nombreux sponsors se tourne vers l’e-sport qui représente le futur du sport numérique. Il est donc intéressant de comprendre quels sont les facteurs qui influencent la réussite dans StarCraft2. La ligue dans laquelle le joueur est nous renseigne sur son niveau. Il y a 8 ligues (Bronze, Silver, Gold, Diamond, Platinum, Master, Grand-Master, Pro). Cette étude aura pour but de construire une méthode pouvant à la fois prédire et expliquer le niveau d’un joueur.

Introduction

Base de données

Nous avons récupéré une base de données concernant les attributs, et les compétences de 3395 joueurs StarCraft2. (source). Les individus sont les joueurs. Ces données ont été récoltées par aggrégation de séquences correspondantes aux games-replays. (crédits). Dans cette étude, une unité de temps est appelé timestamp, une seconde réelle équivaut à 88.5 timestamps. Voici les 20 variables qui constituent la base initiale :

1. GameID : Unique ID pour chaque joueur
2. LeagueIndex : La ligue dans lequel le joueur est : Bronze, Silver, Gold, Platinum, Diamond, Master, GrandMaster, et Professional codé 1-8 (ordinale)
3. Age : Age du joueur (integer)
4. HoursPerWeek : Heures jouées par semaine (integer)
5. TotalHours : Heures totales jouées (integer)
6. APM : Action par minute (continuous)
7. SelectByHotkeys : Nombre de sélections d’unités ou de bâtiments effectuées à l’aide de raccourcis clavier par timestamp (continuous)
8. AssignToHotkeys : Nombre de raccourcis clavier assignés à des unités ou des batiments par timestamp (continuous)
9. UniqueHotkeys : Nombre de raccourcis clavier uniques utilisés par timestamp (continuous)
10. MinimapAttacks : Nombre d’attaques effectuées sur la minimap par timestamp (continuous)
11. MinimapRightClicks : Nombre de “clique-droit” sur la minimap par timestamp (continuous)
12. NumberOfPACs : Nombre de cycle PACs (Perception action skill) par timestamp (continuous)
13. GapBetweenPACs : Durée moyenne, en milliseconds, entre chaque cycle PACs ( continuous)
14. ActionLatency : Latence moyenne, en milliseconds depuis le début d’un PACs jusqu’à la première action (continuous)
15. ActionsInPAC : Nombre moyen d’action dans un PACs (continuous)
16. TotalMapExplored : Le nombre de coordonnées que le joueur voit par timestamp (continuous)
17. WorkersMade : Nombre d’ouvriers créés per timestamp (continuous)
18. UniqueUnitsMade : Unité unique entrainé par timestamp (continuous)
19. ComplexUnitsMade : Nombre d’unité supérieur entrainés per timestamp (continuous)
20. ComplexAbilitiesUsed : Capacités nécessitant des instructions de ciblage précises utilisées par timestamp. (continuous)

Interessons nous à la distribution du niveau des joueurs.

On constate qu’il y a peu de joueurs professionnels et Grand Master. C’est vraiment ces deux ligues qui constituent le haut niveau. On pourrait s’intéresser également aux Master qui est une ligue forte pouvant déboucher sur le haut niveau. On décide donc de créer une variable binaire \(Y\) qui sera celle à expliquer :

\(Y_i\begin{cases}1 &\text{ si le ième joueur est de niveau {Master, Grand Master, Pro}}\\0 &\text{ sinon }\end{cases}\)

Data Management

a) anomalies

La base présente des individus abberants, en effet on ne peut pas avoir un total d’heures jouées plus faible que le nombre d’heures jouées par semaine. On va donc regarder quelles sont ces anomalies.

League_factor
2
3
3
1
1
2
1

Les anomalies ne sont pas des joueurs de haut niveau donc on peut les supprimer. En effet, on a déjà un effectif conséquent pour ce groupe on ne risque donc pas de perdre trop d’information.

De surcroît, on a pu observer une valeur abberante concernant le nombre totales d’heures jouées. Ainsi, un joueur a une expérience d’un millions d’heures, ce qui équivaut à 114 années de jeu. Il conviendra de le supprimer pour ne pas déstabiliser nos futurs modèles. Il est à noter que nous avons d’autres valeurs très fortes mais pas aussi extrême (25 000h, 20 000h..).

##      Min.   1st Qu.    Median      Mean   3rd Qu.      Max.      NA's 
##       7.0     300.0     500.0     962.4     800.0 1000000.0        57

b) Imputation

La base contient un certain nombre de NA. On peut en expliquer la plupart du au fait que l’on a pas les informations concernant l’âge, les heures jouées par semaine et le nombre total d’heures des 55 professionnels. Il y a aussi 2 joueurs du groupe \(Y=0\) qui ont des valeurs manquantes. Pour remédier à cela on propose d’imputer ces valeurs par la moyenne du groupe \(Y\) auquel il est associé. En ce sens on pourra compléter ces NA avec des valeurs représentant le groupe de niveau du joueur.

Y	Age_m	HoursPerWeek_m	TotalHours_m
0	21.89192	14.46148	574.6488
1	20.70427	21.65549	1020.0244

Puis on impute en fonction de la valeur de l’individu

Statistiques descriptives

1. Des joueurs réactifs

Ce graphique (source), montre la relation de nos variables réactions. Un cycle PAC est la durée de réaction suite à un évènement. Il est constitué d’une durée dit de latence avant la 1ère réaction (chaque tic vertical noir représente une action) sommée de la durée du reste des actions. De plus, deux cycles PAC sont toujours coupés d’une durée appelée “gap”.
Dans notre étude la variable ActionLatency représente la durée de latence avant la 1ère action, GapBetweenPACs est la durée gap entre deux PAC et ActionsInPAC est le nombre moyen d’actions dans un PAC.

Selon le graphique on peut observer que plus on joue dans une ligue forte et plus les joueurs ont des durées de perception rapides. En effet, les durées de latence et du gap sont plus courte. Enfin, à partir de la ligue Gold les joueurs réalisent 5 actions dans un PAC au lieu de 4 (cependant comme plus la ligue est forte plus le cycle est cours, réaliser 5 actions par PAC est une preuve de performance).

On peut s’intéresser à la corrélation entre toutes nos variables quantitatives

En restant dans le cadre de la réactivité on perçoit une corrélation conséquente entre la durée de latence et le nombre moyen de cycle PAC par timestamp.

Ce graphique nous confirme qu’on peut plutôt penser que les joueurs de haut niveau réagisse plus rapidemment avec un plus grand nombre de cycle de perception au cours d’une partie.

2. Des joueurs très actifs

Un facteur très important dans StarCraft2 est l’APM, qui est le nombre moyen d’action par minute d’un joueur. C’est vraiment la donnée sur laquelle les joueurs analysent les autres. Ils veulent tous avoir un APM le plus élevé possible. Regardons la distribution de cette variable au sein de chaque ligue.

Il semble y avoir un effet de l’APM sur le niveau des joueurs. Lorsque qu’on joue dans les 2 ligues les plus fortes, les joueurs ont tous minimum 100 actions par minutes. Cependant cet indice n’est pas forcément linéaire car on remarque que pas mal de pros ont les mêmes valeurs d’APM que les “Grand-Masters”.

En revenant à la matrice de corrélation on a pu constater une forte corrélation entre l’APM d’un joueur et le nombre d’unité ou batiment créer grâce à un raccourci clavier.

Premièrement on voit qu’il y a des joueurs \(Y=0\) qui ont de très fort APM. De plus, Le fait d’avoir un nombre d’action par minute élevé est corrélé à l’utilisation des raccourcis clavier. En effet dans ce jeu on nous incite au maximum a se créer nos propres hotkeys afin de performer et d’être plus rapide donc d’avoir une durée réactivité plus courte.

3. Une expérience de jeu élevée

Comme nous l’avions dit, le nombre totale d’heures jouées est une variable qui peut aller dans les extrêmes. Dans la plupart des ligues il y a toujours des individus qui ont des gros temps de jeu. Comme on a imputé toutes les valeurs pour les professionnels on n’analysera pas la distribution associée.

Malgré les valeurs hétérogènes on constate que les médianes et les troisièmes quartiles augmentent avec le niveau de la ligue.

4. Résumé en ACP

On propose de réaliser une analyse en composantes principales au vu du caractère quantitatif de nos variables explicatives. Nous réduisons nos données pour éviter les erreurs d’échelles. Puis on exécute la méthode.

Puis on trace l’ébouli des valeurs propres afin de voir combien d’axes nous devons prendre pour expliquer un pourcentage correcte de la variance de nos données.

On a affaire à un jeu de données complexe car le premier plan factoriel (deux premier axes) n’explique que 39.36 % de la variance. On décide de conserver trois axes pour avoir un pourcentage de variance cumulative expliquée de 47.69%.

Premier plan factoriel

Sur ce plan factoriel on peut voir que les très bons joueurs ont des coordonnées positives sur l’axe 1 (il se situe à droite dans le cercle). Le nombre d’action par minute, le nombre de cycle PACs par partie et enfin les durées de Latence/gap sont les variables qui construisent l’axe 1. Ainsi, un bon joueur aura tendance à avoir un nombre d’APM et de cycle PACs élevés. De plus, il est réactif car sa durée de latence avant 1ère action et la durée gap entre chaque cycle PAC sont courtes. Le second axe apporte l’information sur le type de jeu du joueur. Si le joueur a des valeurs positives sur cet axe (il se situe en haut du cercle) alors cela veut dire que ce joueur à un style de jeu plutôt fondé sur sa construction d’économie et sur la défensive. En effet, il utilise des unités, et sorts complexes qui mettent du temps à se former et qui coutent beaucoup de ressources. Sa stratégie est sur le long terme, il préfère défendre sa base jusqu’en fin de partie où il possèdera les meilleurs troupes.
PS: Le troisième axe n’apporte pas une information dsicriminante donc on se contentera du premier plan factoriel.

Nous avons donc une idée des facteurs qui influe sur le fait d’être un joueur de haut niveau (Master,Grand Master ou professionnel). Nous allons à présent comparer plusieurs méthodes dans le but d’expliquer et de prédire le niveau d’un joueur.

Méthodes de classification supervisée

Objectif

On cherche à expliquer la variable \(Y\) qui est le niveau d’un joueur StarCraft en fonction de \(p=18\) variables explicatives quantitatives.

\(Y_i\begin{cases}1 &\text{ si le ième joueur est de niveau {Master, Grand Master, Pro}}\\0 &\text{ sinon }\end{cases}\)

Il s’agit donc d’une discrimination binaire.

I - LDA

Le but est d’estimer les probabilités à postériori d’appartenance aux groupes 0 ou 1. Celles ci sont données par le théorème de Bayes:

\(P(Y=k|X=x) = \frac{\pi_kf_k(x)}{\sum\limits_{m=1}^2\pi_mf_m(x)}\)

avec :

• \(f_k(x)\), \(k=0,1\) les densités des lois \(X|Y = k\)
• \(f(x)\) la densité de \(X\)
• \(\pi_k = P(Y=k)\) les probabilités à priori d’appartenance aux groupes

L’analyse discriminante linéaire suppose que les lois \(X|Y=k\) sont des lois gaussiennes multivariées \(\mathcal N(\mu_k,\Sigma)\) où \(\mu_k \in \mathbf{R}^p\) et \(\Sigma\) est une matrice pxp définie positive.
Il faut alors estimer les paramètres inconnus du modèle: \(\pi_k=P(Y=k)\), \(\mu_k\) et \(\Sigma\) avec \(k=0,1\)

\(\widehat{\mu}_k=\frac{1}{n_k}\sum\limits_{i:Y_i=k}Xi\)       \(\widehat{\Sigma} =\frac{1}{n-2}\sum\limits_{k=0}^1\sum\limits_{i:Y_i=k}(X_i-\widehat{\mu}_k)(X_i-\widehat{\mu}_k)^t\)

\(\widehat{\pi}_k=\frac{n_k}{n}\) avec \(n_k=\sum\limits_{i=1}^n\mathbb{1}_{Y_i=k}\)

Echantillonage : Apprentissage/validation

On va séparer l’échantillon en deux sous échantillons de manière aléatoires pour éviter d’avoir un modèle peu robuste. En pratique, on construira nos méthodes à partir d’un échantillon \(d_{app}\) d’effectif \(n_{app} = \frac{2}{3}n\), puis nous pourrons tester leur performance sur l’échantillon \(d_{test}\). Ce n’est pas la méthode d’échantillonage qui garantit le plus de stabilité des estimations mais cela à l’avantage de n’être pas trop couteux en temps de calcul. Le but étant de pouvoir relancer l’étude en un temps de calcul faible, nous allons alors appliquer ce protocole, dit hold out, sur tous nos futures algorithmes afin de pouvoir les comparer. En effet, nous utiliserons différents critères afin de dégager la méthode la plus performante vis à vis de notre problème.

## 
##    0    1 
## 1785  473

## 
##   0   1 
## 891 238

Modélisation

## Call:
## lda(Y ~ ., data = dapp)
## 
## Prior probabilities of groups:
##         0         1 
## 0.7905226 0.2094774 
## 
## Group means:
##        Age HoursPerWeek TotalHours      APM SelectByHotkeys AssignToHotkeys
## 0 21.95014     14.18263    560.298 102.7101     0.003117570    0.0003235869
## 1 20.78647     21.01480   1022.326 168.9609     0.008679651    0.0005465566
##   UniqueHotkeys MinimapAttacks MinimapRightClicks NumberOfPACs GapBetweenPACs
## 0      4.001681   7.772764e-05       0.0003493866  0.003226764       43.42683
## 1      5.693446   1.812465e-04       0.0004988419  0.004354010       28.55972
##   ActionLatency ActionsInPAC TotalMapExplored  WorkersMade UniqueUnitsMade
## 0      68.16688     5.199489         21.46499 0.0009845508        6.481793
## 1      47.39439     5.460247         24.44186 0.0011864949        6.797040
##   ComplexUnitsMade ComplexAbilitiesUsed
## 0     5.601508e-05         0.0001322958
## 1     6.890459e-05         0.0001679882
## 
## Coefficients of linear discriminants:
##                                LD1
## Age                  -1.867909e-03
## HoursPerWeek          2.275807e-02
## TotalHours            1.802715e-04
## APM                   4.067346e-03
## SelectByHotkeys       4.438764e+01
## AssignToHotkeys       8.971550e+02
## UniqueHotkeys         6.099984e-02
## MinimapAttacks        1.476687e+03
## MinimapRightClicks    3.570474e+01
## NumberOfPACs          5.575539e+02
## GapBetweenPACs       -4.745936e-03
## ActionLatency         3.862922e-03
## ActionsInPAC          1.837178e-02
## TotalMapExplored     -7.677862e-03
## WorkersMade           1.843098e+01
## UniqueUnitsMade      -4.322713e-02
## ComplexUnitsMade     -4.012351e+02
## ComplexAbilitiesUsed -2.829713e+01

La sortie nous renvoi tout d’abord les estimations \(\widehat{\pi}_k\) et des vecteurs \(\widehat{\mu}_k\) (texte automatisé)

• \(\widehat{\pi}_0 =\) 0.79052 et \(\widehat{\pi}_1 =\) 0.20948
• \(\widehat{\mu}_0\) est le vecteur des moyennes de chaque variable dans le groupe \(0\), situé en face de la ligne \(0\) de group means
• \(\widehat{\mu}_1\) est le vecteur des moyennes de chaque variable dans le groupe \(1\), situé en face de la ligne \(1\) de group means
  
  
  

La dernière partie de la sortie représente l’axe optimal discriminant. c’est un vecteur \(\vec{a}\) composé de \(p\) coordonnées discriminantes. L’idée est que si on projette les individus sur ce nouvel axe alors la variance inter \(B(\vec{a})\) sera grande et la variance intra \(W(\vec{a})\) sera petite. Cela voudra dire que les joueurs 0 et 1 sont bien séparés et qu’au sein de leur groupe ils sont compactes.
On peut visualiser cet axe:

On voit que l’axe esseye d’opposer les très bons joueurs qui auront des coordonnées positives sur l’axe et les moins bons ayant des coordonnées discriminantes plus faibles. Cependant cet axe n’a pas l’air de discriminer très bien les joueurs car les histogrammes se chevauchent sur une portion de l’axe discriminant.
On pourra alors visualiser les projections des individus sur cet cet axe :

Cela confirme notre intuition visuelle comme quoi les très bons joueurs ont des coordonnées positives élevés. En revanche il y a une partie que l’algorithme peine à discriminer, il s’agît très certainement des individus de niveau Master qui doivent se confondre avec les joueurs de niveau Diamond.

Performance

On va s’intéresser à la performance du modèle lda, c’est à dire sa capacité à bien classer les joueurs. Pour cela on va regarder l’erreur de classification \(L\).

\(\widehat{L} = P(\widehat{g}(x) \ne Y)\) où \(g\) est la règle de classification

LDA.error
0.1558902

L’algorithme lda prédictive prédit bien sur les données de validation. En effet, l’estimation de l’erreur moyenne de classification est de 15.589%. Néanmoins l’interprétation de ce modèle reste difficile. En effet, la lda aura plutôt pour but de visualiser les individus sur un nombre réduit d’axes (ici 1 axe). En revanche si on veut prédire il ne faudrait pas choisir la règle géométrique (règle probabiliste où les probabilités à priori de chaque groupe sont identiques) car elle ne prédirait pas aussi bien que la lda predictive.

II - QDA

L’analyse discriminante linéaire implique de fortes hypothèses notamment que les matrices \(\Sigma\) de variance-covariance sont identiques pour le groupe 0 et le groupe 1. Afin d’être plus flexible on peut mettre en place une analyse quadratique discriminante qui prendra les mêmes hypothèses que la lda sauf que les deux matrices \(\Sigma_0\) et \(\Sigma_1\) seront différentes. on suposera désormais:

la loi de \(X|Y = k\) suit une loi \(\mathcal N(\mu_k,\Sigma_k)\) toujours avec k = 0,1

Les estimations seront les mêmes que la lda à l’exception des deux (une pour la lda) matrices variance-covariances \(\Sigma_k\) :

\(\widehat{\Sigma}_k=\frac{1}{n_k}\sum\limits_{i:Y_i=k}(X_i-\widehat{\mu}_k)(X_i-\widehat{\mu}_k)^t\)

Les fonctions linéaires discriminantes changent, mais l’idée reste la même. A savoir que choisir le groupe qui maximise \(P(Y=k|X=x)\) revient à choisir le groupe qui maximise ces nouvelles fonctions linéaires discriminantes.
Les frontières de la QDA ne seront plus linéaires mais quadratiques. Cela permettra de modéliser une plus large gamme de phénomènes.

Modélisation et performance

LDA.error	QDA.error
0.1558902	0.1895483

On constate que l’algorithme qda est moins performant que son homologue lda. En effet l’estimation de l’erreur moyenne de classificaion est plus élevé avec le modèle qda. On peut justifier cela du fait que le modèle qda est plus complexe (190 paramètres au lieu de 19). Il en résulte une construction d’estimateurs moins précis (avec un risque de sur-ajustement si p est grand).

III - RDA

Régularisation 1

En 1989, Friedman propose de combiner la LDA avec la QDA. L’analyse discriminante régularisée reste dans le cadre du modèle gaussien mais le changement réside encore une fois dans l’estimation des matrices variance-covariance des lois \(X|Y=k\). On va les estimer par la combinaison linéaire:

\(\widehat{\Sigma}_k(\lambda)=(1-\lambda)\widehat{\Sigma}_k + \lambda\widehat{\Sigma}\)

On constate que cette nouvelle matrice est une combinaison des matrices variances covariances de QDA et LDA

Rôle de \(\lambda\):

• Si \(\lambda=0\) alors c’est une QDA
• Si \(\lambda=1\) alors c’est une LDA
• \(\lambda \in [0,1]\) doit être calibrer

Régularisation 2

Friedman propose également une autre régularisation de la matrice \(\Sigma\) donc de la matrice variance-covariance de LDA par:

\((1-\gamma)\widehat{\Sigma}+\gamma\widehat{\sigma}^2I_p\)

Rôle de \(\gamma\):

• Si \(\gamma=0\) alors c’est une LDA
• \(\gamma \in [0,1]\) doit être calibrer

Combinaison de ces régularisations

On va combiner les deux pénalités en estimant les matrices variance-covariance par:

\((1-\gamma)\widehat{\Sigma}_k(\lambda)+\gamma\frac{trace(\widehat{\Sigma}_k(\lambda))}{p}I_p\)

Rôle de \(\gamma\) et \(\lambda\):

• Si \(\gamma=0\) et \(\lambda=0\) alors c’est une QDA
• Si \(\gamma=0\) et \(\lambda=1\) alors c’est une LDA
• Il faut alors choisir \(\gamma\) et \(\lambda\) tel que le modèle soit optimisé selon un critère.

Ce critère sera la précision \(A\), c’est à dire \(1-L\), où \(L\) est l’erreur moyenne de classification.

\(\widehat{A}=1-\widehat{L}\) avec \(\widehat{L} = P(\widehat{g}(x) \ne Y)\)

1. Modélisation avec le package caret

On veut sélectionner le modèle en fonction des valeurs de \(\lambda\) et \(\gamma\) tel que \(\widehat{A}\) soit maximisée par methode hold-out.

Voici les 11 premieres lignes du tableau représentant les valeurs de \(\gamma\) et\(\beta\) avec comme critère d’optimisation \(\widehat{A}\).

gamma	lambda	Accuracy
0	0.0	0.8104517
0	0.1	0.8157662
0	0.2	0.8193091
0	0.3	0.8193091
0	0.4	0.8228521
0	0.5	0.8219663
0	0.6	0.8237378
0	0.7	0.8272808
0	0.8	0.8272808
0	0.9	0.8325952
0	1.0	0.8441098

On va choisir les valeurs des deux paramètres :

	gamma	lambda
11	0	1

On peut également visualiser l’évolution de \(\widehat{A}\) en fonction des paramètres

On constate que l’algorithme a sélectionné le modèle avec \(\gamma=0\) et \(\lambda=1\) car il maximise \(A\). On a donc affaire au modèle LDA. Logiquement les erreurs de classifications de la LDA et RDA devraient être identiques au vu de la même méthode de validation hold-out.

2. Comparaison LDA/QDA/RDA

Critère de l’erreur de classification

Pour rappel, on a utilisé exactement les mêmes sous échantillons \(d_{app}\)/\(d_{test}\) pour nos trois modèles discriminants. La comparaison de leurs critères de performance sera donc bien quantifiable. On peut donc, finalement, comparer les erreurs moyennes de classification pour les trois modèles discriminants.

LDA.error	QDA.error	RDA.error
0.1558902	0.1895483	0.1558902

Comme énoncé plus haut, la méthode rda à selectionnée le modèle lda. Cela confirme que c’est le modèle le plus performant en terme de prédiction parmis les modèles discriminants.

Critère de la courbe ROC et de son AUC

Parfois, il est essentiel de s’intéresser au score d’un individu plutôt que le groupe où il va être placé. Dans notre cas, imaginons qu’un sponsor propose un contrat au meilleur joueur StarCraft2. Le sponsor voudra privilèger les contrats aux individus ayant le plus de chance de se classer parmis les \(Y=1\). Les prédictions des classes ne suffiront donc pas, il faudra impérativement mettre en place une fonction score \(S(x)\) qui prendras ses valeurs dans \(\mathbf{R}\). L’individu aura un score:

• élevé s’il a de grandes “chances” d’être dans le groupe 1
• faible s’il a des grandes “chances” d’être dans le groupe 0

On va alors utiliser la courbe ROC pour visualiser la performance d’un score concernant un modèle. Soit \(s\) un seuil qu’on se fixe on aura deux types d’erreurs \(\alpha(s)\) et \(\beta(s)\) qui nous donnerons les coordonnées:

\(\begin{cases}x(s)=\alpha(s)=P(g(x)=1|Y=0)\\y(s)=1-\beta(s) = 1-P(g(x)=0|Y=1)\end{cases}\)

On déduit de ce critère un risque pour les scores en considérant l’aire sous la courbe ROC (AUC):

\(R(S)=AUC(S)\)

L’AUC est donc comprise entre 0.5 et 1.

• Si \(AUC(S)=0.5\) alors \(S\) est un score aléatoire car il vérifié \(\alpha(s)=1-\beta(s)\)
• Si \(AUC(S)=1\) alors \(S\) est un score parfait car les deux types d’érreur sont nulles
• Donc plus l’\(AUC\) est grand est plus le score est performant
  
  

On va pouvoir modéliser les deux Scores correspondant à la LDA et QDA (on ne fait pas RDA car on a montré que RDA=LDA ici). Ces scores sont les probabilités estimées \(P(Y=1|X=x)\).

Visuellement le score LDA a l’air plus performant car sa courbe est tout le temps au dessus de celle de QDA. On vérifie ça par l’aire sous la courbe

Score	AUC
score.lda	0.879
score.qda	0.848

L’AUC du score lda est la plus élevée donc on retient également le modèle lda avec ce critère

IV - Régression logistique

1. Objectif

On cherche toujours à expliquer la variable \(Y\) qui est le niveau d’un joueur StarCraft en fonction de \(p=18\) variables explicatives quantitatives.

\(Y_i\begin{cases}1 &\text{ si le ième joueur est de niveau {Master, Grand Master, Pro}}\\0 &\text{ sinon }\end{cases}\)

On a donc \(y_1,...,y_n\) comme réalisations des variables aléatoires indépendantes \(Y_1,...,Y_n\). Il existe \(\beta\in \mathbf{R}\) tel que chaque \(Y_i|X_i=x_i\) suit une loi \(\mathcal B(p_\beta(x_i))\) où \(p_\beta(x_i) = P(Y_i=1|X_i=x_i)\). Le modèle logistique s’écrira alors:

\(logit\:p_\beta(x_i) = x_i^t\beta\)

• \(x_i\) est le vecteur colonne des données de l’individu i : \([1,x_{i,1},..,x_{i,p}]\)
• \(\beta\) est le vecteur colonne \([\beta_0,\beta_1,..,\beta_{p}]\)

2. Selections de modèles

On part du modèle complet \(M_{complet}\) et on va faire une sélection stepwise pas à pas avec comme critère l’AIC. En effet, pour sélectionner le meilleur modèle il faut définir un critère. Il faut savoir qu’un modèle est d’autant plus fiable que sa vraisemblance maximale est grande. Cependant, entre 2 modèles, la vraisemblance maximale sélectionne toujours le modèle le plus complexe. L’idée du critère AIC est alors de pénaliser la vraisemblance maximale par la complexité (i.e. la dimension) du modèle. Pour un modèle \(M\) à \(p\) paramètres, de log-vraisemblance maximale \(\widehat{Ln}(M)\), on a \(AIC(M) = −2\widehat{Ln}(M)+2p\). Entre 2 modèles, on choisira donc celui dont l’AIC est le plus petit.

## 
## Call:
## glm(formula = Y ~ HoursPerWeek + TotalHours + APM + SelectByHotkeys + 
##     AssignToHotkeys + UniqueHotkeys + MinimapAttacks + NumberOfPACs + 
##     GapBetweenPACs + ActionLatency + WorkersMade + UniqueUnitsMade, 
##     family = binomial, data = dapp)
## 
## Deviance Residuals: 
##      Min        1Q    Median        3Q       Max  
## -2.73164  -0.50218  -0.23400  -0.04026   2.99105  
## 
## Coefficients:
##                   Estimate Std. Error z value Pr(>|z|)    
## (Intercept)      2.350e+00  1.370e+00   1.716 0.086243 .  
## HoursPerWeek     3.091e-02  6.106e-03   5.062 4.14e-07 ***
## TotalHours       3.639e-04  1.103e-04   3.300 0.000967 ***
## APM             -1.483e-02  4.625e-03  -3.206 0.001346 ** 
## SelectByHotkeys  1.568e+02  3.034e+01   5.168 2.36e-07 ***
## AssignToHotkeys  1.052e+03  3.535e+02   2.977 0.002914 ** 
## UniqueHotkeys    1.090e-01  3.314e-02   3.289 0.001006 ** 
## MinimapAttacks   1.810e+03  4.026e+02   4.497 6.88e-06 ***
## NumberOfPACs     2.814e+02  1.326e+02   2.122 0.033864 *  
## GapBetweenPACs  -4.406e-02  8.962e-03  -4.916 8.84e-07 ***
## ActionLatency   -7.326e-02  1.360e-02  -5.388 7.11e-08 ***
## WorkersMade      4.056e+02  1.380e+02   2.938 0.003301 ** 
## UniqueUnitsMade -6.707e-02  3.973e-02  -1.688 0.091369 .  
## ---
## Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
## 
## (Dispersion parameter for binomial family taken to be 1)
## 
##     Null deviance: 2317.9  on 2257  degrees of freedom
## Residual deviance: 1409.9  on 2245  degrees of freedom
## AIC: 1435.9
## 
## Number of Fisher Scoring iterations: 6

La sortie nous donne un modèle avec 12 variables explicatives. On peut interprêter les \(\widehat{\beta}\) dont les variables sont dites significatives (au test de nullité individuel). Lorsque que le coefficient \(\widehat{\beta}_k\) est négatif on peut supposer que lorsque la variable \(k\) augmente alors on n’a moins de “chances” d’être un classé comme un joueur du groupe 1 et inversement pour un \(\widehat{\beta}_k\) positif. Plus un coefficient significatif est extrême et plus on dira que la variable associé à un impact linéaire important sur \(Y\).

3.Performance

Erreur de prédiction

Comme pour nos modèles précédents on va s’intéresser au critère de l’erreur de classification estimée \(\widehat{L} = P(\widehat{g}(x) \ne Y)\) où \(g = logit\:p_\beta(x)\) est la règle de classification du modèle logistique.

LDA.error	Logistic.error
0.1558902	0.1505757

La différence est légère mais la méthode logistique semble mieux classer les joueurs. On va regarder la table de confusion pour comprendre les deux types d’erreurs (énoncé comme étant \(\alpha(s)\) et \(\beta(s)\)) que fait la méthode.

##     observe
## pred   0   1
##    0 838 117
##    1  53 121

faux_negatifs	faux_positifs
117	53

On constate que le modèle logistique a tendance à se tromper plutôt sur les joueurs de niveau \(Y=1\). En effet 68.82% de son erreur de classification vient du fait que le modèle classe le joueur comme de niveau \(Y=0\) alors qu’en réalité il est de niveau \(Y=1\). Il a donc plus tendance à classer le joueur dans le groupe des 0, ce qui peut être un avantage dans le cadre d’obtention de contrat via un sponsor comme précédemment énoncé. Ainsi, le sponsor sera plus enclin à faire confiance en notre prédiction de joueur de niveau \(Y=1\).

Courbe ROC et scoring

Les courbes ont l’air presque identiques, on constate que la courbe du score logistique est légèrement au dessus de l’autre courbe par endroit. on va regarder l’aire sous celles-ci.

Score	AUC
score.Logistic	0.882
score.lda	0.879

Le modèle logistique à un scoring légèrement plus performant que le modèle lda. Ceci dit, on ne tranchera pas nettement sur le modèle le plus efficace de par le faible écart pour les deux critères de performances qui peut changer selon l’échantillonnage. La solution serait de choisir une validation plus couteuse en temps de calcul mais ce n’est pas le but de l’étude.

V - Arbres de décision

1. Objectif et présentation du problème

On cherche toujours à expliquer la variable \(Y\) qui est le niveau d’un joueur StarCraft en fonction de \(p=19\) variables explicatives quantitatives.

\(Y_i\begin{cases}1 &\text{ si le ième joueur est de niveau {Master, Grand Master, Pro}}\\0 &\text{ sinon }\end{cases}\)

2. Definition d’un arbre

Un arbre est une règle de classification (donc une fonction) qui vise à trouver une partition des observations qui discrimine “au mieux” les valeurs de \(Y\). La partition est construite par divisions successives dépendantes des données \((X_i,Y_i)\).
Choix des découpes : à chaque étape de l’algorithme (chaque découpe) on cherche un couple \((j,s)\) qui sépare un noeud père \(N\) en deux noeuds fils \(N_1\) et \(N_2\):

\(N_1(j,s) = \{X\in N|X_j\le s\}\) et \(N_2(j,s) = \{X\in N|X_j > s\}\)

avec \(j\in \{1,...,p\}\) et \(s \in \mathbf{R}\) car \(X_1,..X_p\) sont quantitatives.
Le couple \((j,s)\) est le couple qui optimise un critère dit d’ Impureté/hétérogénité des deux noeuds fils.

3. Critère de découpe

On note \(I\) l’impureté d’un noeud. On veut \(I(N_1)\) et \(I(N_2)\) petits car ca signifiera que les deux noeuds fils sont purs –> donc les valeurs de \(Y\) dans ces noeuds sont proches.
Dans notre étude, \(Y\) étant binaire nous allons utilisé la mesure de Gini pour décrire l’impureté d’un noeud \(N\):

\(I(N) = \sum\limits_{k = 1}^2 2p_k(1-p_k)\) où \(p_k\) désigne la proportion de k dans \(N\)

On choisira alors le couple \((j,s)\) qui minimise \(P_1 I(N_1) + P_2 I(N_2)\) ,avec \(P_1\) le poids du noeud 1 (effectif dans \(N_1\)).

4. Règle de classification

L’arbre aura pour règle de classification \(g\) :

\(\widehat{g}(x)\begin{cases}1 &\text{si }\sum\limits_{i X_i \in N(x)}\mathbb{1}_{Y_i=1}\ge \sum\limits_{i X_i \in N(x)}\mathbb{1}_{Y_i=0} \\0 &\text{ sinon }\end{cases}\)

c’est à dire que l’arbre va classer le point \(x\) dans le groupe 1 si il y a plus de 1 que de 0 dans le Noeud où il “tombe”.

Modélisation

1. Comparaison de 3 arbres

On utilisera toujours le même protocole apprentissage validation pour comparer la performance de nos méthodes.

Suites d’arbres et élagage

On va créer 3 arbres : simple,large et optimisé.
Pour se faire on construit d’abord l’arbre large \(T_{large}\) (très profond) qui sera peu biaisé mais avec une très forte variance. Il y a aura donc un sur-ajustement. Cet arbre contient une collection de sous arbres. Dans cette collection on va choisir un arbre \(T_{simple}\) tel qu’il soit peu profond donc avec une faible variance mais très biaisé. Enfin dans la collection de sous arbres de \(T_{large}\) on va choisir \(T_{opt}\) tel qu’un critère \(C_\alpha(T_{opt})\) soit minimisé. Pour cela on définit l’erreur dans le noeud \(N\):

\(R(N) = \frac{1}{|N|}\sum\limits_{i:X_i\in N}\mathbb{1}_{Y_i\ne Y_N}\)

Alors, avec \(\alpha > 0\), le critère s’écrit:

\(C_\alpha(T_{opt})=\sum\limits_{m=1}^{|T_{opt}|}N_mR(N_m) + \alpha|T_{opt}|\)

Ce critère est un compromis qui permet de pénaliser la qualité d’ajustement d’un arbre par sa complexité (son nombre de coupures).

Conlusion: On cherche un arbre \(T_{opt}\) tel que \(C_\alpha(T_{opt})\) soit minimisé pour une valeur de \(\alpha\) bien choisie.

Codage

Ce code permet d’effectuer la sélection des 3 arbres énoncés sur notre échantillon d’apprentissage. L’arbre optimal à été trouvé par la recherche de \(\alpha\) tel que le critère soit minimisé. De plus, les prédictions de ces trois arbres sur les données test ont été injectées dans un data.frame Par exemple la prédiction \(\widehat{Y}_{1 , T_{simple}}\) est le groupe 0 (texte automatisé en fonction des sorties).

pred.simple.Y1
0

Critère de comparaison

On va pouvoir comparer la performance de ces trois arbres en utilisant le critère de l’erreur de classification \(L\).

\(\widehat{L} = P(\widehat{g}(x) \ne Y)\)

Prev.error.simple	Prev.error.opt	Prev.error.large
0.1762622	0.1682905	0.2019486

On peut retrouver à la main ses erreurs par exemple avec l’erreur de prédiction de l’arbre simple

## [1] 0.1762622

2.Description et analyse des arbres

Arbre simple

L’arbre simple classe moins bien les joueurs mais a l’avantage d’être très peu couteux en variables. Il possède 2 coupures. Ici on gardera l’arbre optimisé car il classe ‘mieux’ les données et son coûts en variables n’est pas trop imposants.

Arbre optimisé

L’arbre optimisé a forcément une erreur de classification minimale car le critère optimisé est \(R(m)\). Cet arbre est composé de 4 coupures.

On constate que le facteur discriminant principal de l’abre est la durée moyenne en milliseconde avant que le joueur réagisse en faisant une action (c’est la variable ActionLatency). Si cette durée est trop importante alors le joueur a de grandes chances d’être classé dans le groupe 0. Ce qui est logique car les meilleurs joueurs réagisse pour la plupart très vite à une situation.

3.Limites des arbres

Cet algortihme est relativement instable et sensible à de légères perturbations de l’échantillon. En effet si on relance le code en perturbant les sous échantillons \(d_{app}\) et \(d_{dtest}\), on obtiendra un arbre final complétement différent dont son nombre de coupure pourra vraisemblablement varier de 4 à 30. L’erreur de classification \(\widehat{L}\) ne change pas drastiquement mais l’interprétation de l’arbre peut lui se compliquer/simplifier à travers le changement de sa profondeur.
Cependant, cette sensibilité à l’échantillon sera un avantage pour des aggrégations bootstrap (stabilisation) utilisé dans les forêts aléatoires.

VI - Forêts aléatoires

Une forêt aléatoire est une collection d’arbres. Chaque arbre de cette collection est construit à partir d’un échantillon bootstrap.

1. Echantillons bootstraps

L’idée est qu’on va construire \(B\) échantillons dits bootstraps afin d’obtenir \(B\) estimateurs de notre règle de classification \(g\). Puis on aggrège tous ces estimateurs afin d’obtenir un estimateur final très stable. La forêt aléatoire est donc logiquement plus stable et plus performante qu’un simple arbre de décision. Léo Breiman a montré que si les estimateurs de chaque echantillons bootstraps sont \(iid\) alors agréger permettra de tuer la variance et ne modifiera pas le biais.
On créer des échantillons bootstrap pour rajouter de l’aléa car ils sont tirés aléatoirement avec remise. Chaque échantillons sera composé de 3387 individus. Il est conseillé de tirer un maximum d’échantillons bootstrap pour que l’estimateur final soit de plus en plus stable.

2. Construction des arbres

On va donc construire \(B\) arbres qu’on veut très différents les uns des autres et très profonds. En effet, les abres profonds sont peu biaisés mais ont une forte variabilité. Comme nous l’avons dis, agréger ces arbres nous permettra de tuer cette variance tout en gardant un biais faible. Décrivons le processus de création d’un arbre :

1. D’abord, on tire un échantillon bootstrap dans notre jeu de données \(craft2\)
2. Puis on construit l’arbre sur cette échantillon
–> Un arbre va être découpé plusieurs fois, à chacune de ses découpes on va tirer aléatoirement \(m\) variables parmis les \(p\) de notre échantillon qui construiront un sous ensemble \(\{p_{decoupe}\}\) de variables. Pour découper un Noeud de l’arbre, on va choisir la variable parmis \(\{p_{decoupe}\}\) qui minimise le gain d’impureté de Gini évoqué dans la section des arbres.
3. On obtient alors un estimateurs \(T_B(x)\) qui sera le résultat de la règle de classification \(g_B\) (0 ou 1)

Une fois tous les arbres créés on agrège leur estimateurs en faisant voter les arbres à la majorité.

3. Modélisation

Il y a plusieurs paramètres qui faudra choisir pour lancer notre algorithme.

• \(B\) : le nombre d’arbres,on le veut le plus grand possible.
• \(m \in \{1,..,p\}\) : le nombre de variables qu’on va tirer aléatoirement à chaque découpe, on comparera plusieurs valeurs.
• \(depth\) : Profondeur maximale des arbres, par défault dans ranger cette profondeur est illimitée.
• \(n{min}\) : le nombre min d’observations par noeud terminal, par défaut ranger le définit à 1.

Tout d’abord on utilise le package randomForest car il possède l’avantage de pouvoir visualiser simplement la convergence des estimations d’une forêt aléatoire

Chaque courbe représente une estimation d’une erreur (erreur de classification en bleue, 1-spécificité en vert et 1- sensibilité en noir). Ce qui est intéressant c’est de voir qu’à partir de 500 arbres les estimateurs convergent radicalement vers une valeur). On utilisera donc par la suite le package ranger pour modéliser les forêts aléatoires en prenant pour valeur \(B = 1000\). Cela nous permettra d’assurer la stabilité des résultats.

## Ranger result
## 
## Call:
##  ranger(Y ~ ., data = dapp, num.trees = 1000) 
## 
## Type:                             Classification 
## Number of trees:                  1000 
## Sample size:                      2258 
## Number of independent variables:  18 
## Mtry:                             4 
## Target node size:                 1 
## Variable importance mode:         none 
## Splitrule:                        gini 
## OOB prediction error:             14.08 %

On construit, en premier lieu, la forêt aléatoire de 1000 arbres avec les valeurs par défaut de ranger. C’est à dire qu’ici \(m=\) 4, la profondeur de chaque arbre n’est pas plafonné, \(n_{min} = 1\). Le critère de découpe est bien le critère d’impureté \(I\) de Gini. L’OOB error est une estimation d’erreur de classification calculée à partir de la méthode out of bag. C’est une alternative à l’estimation d’erreur par validation croisée comme nous l’avons fait depuis le début de l’étude. Pour respecter le protocole, et ainsi pouvoir comparer au mieux toutes les méthodes nous nous intéresserons uniquement à l’erreur de classification \(\widehat{L} = P(\widehat{g}(x) \ne Y)\) sur les données test.

Nous voulons maintenant sélectionner les paramètres de la forêt tel quelle soit la plus optimisée au sens du critère \(\widehat{A} = 1-\widehat{L}\). Pour cela nous utilisons le package caret.

	mtry	splitrule	min.node.size
14	5	gini	2

Le critère est optimisé lorsque \(m=\) 5, et que le nombre minimal d’observation dans chaque noeud terminal est de 2. On peut visualiser la comparaison de ces paramètres avec le graphique suivant :

On va pouvoir comparer la performance de la forêt par défaut et la forêt calibré par nos soins grâce, encore et toujours, au critère \(\widehat{L}\)

error.foret.defaut	error.foret.calibre
0.1479185	0.1426041

Calibrer ces paramètres nous ont permis d’augmenter la performance de notre modèle. Nous allons à présent nous intéresser à l’interprétation de notre forêt aléatoire.

4. Interprétation

Interpréter une forêt est compliquée car on ne sais pas exactement quel a été le calcul exact qui a donnée la prédiction sur \(d_{test}\). Pour pouvoir interpréter une forêt on va s’intéresser à la notion d’importance des variables.

Tout d’abord on va créer \(B=1000\) échantillons appelés alors \(OOB_k\), avec \(k=1,..,B\). L’échantillons \(OOB_k\) contient les observations qui ne sont pas dans le \(k^{ème}\) échantillons bootstap. On calcul alors l’erreur moyenne de prédiction de l’arbre \(k\) :

\(E_{OOB_k}= \frac{1}{n}\sum\limits_{i\in OOB_k}\mathbb{1}_{\widehat{g}(X_i)\ne Y_i}\), avec \(n = 3387\)

Puis, on créer un même nombre d’échantillons appelés \(OOB_k^j\) dans lequel on a perturbé aléatoirement (par permutation dans notre cas) les valeurs de la variable \(j\). On calcule à nouveau l’erreur de prédiction de l’arbre \(k\) sur cet échantillon : \(E_{OOB_k^j}\).

Si la variable \(j\) a une très grande importance dans la forêt cela voudra dire que les erreurs \(E_{OOB_k}\) et \(E_{OOB_k^j}\) seront très différentes.

On définit l’importance de la \(j^{ème}\) variable par :

\(Imp(X_j)=\frac{1}{B}\sum\limits_{k=1}^B(E_{OOB_k^j} - E_{OOB_k})\)

Comme pour la régression logistique et les arbres, on constate que c’est bien la durée de latence avant la 1ère action qui est la variable la plus importante. La deuxième variable la plus importante est le nombre d’action par minute (APM). Un très bon joueur est très réactif aux changements (attaque ennemies, visualisation de la carte etc..) au cours d’une partie. De plus, il a tendance à réaliser beaucoup d’actions par minutes (création de batiments,formation de troupes).

Comparaison des trois meilleurs modèles.

Nous allons comparer les 3 meilleurs modèles à savoir la méthode LDA (parmis l’analyse discriminante), la régression logistique, et la forêt aléatoire. Pour faire cela nous allons reprendre les deux critères de comparaison :

• \(\widehat{L}\) : l’estimation de l’erreur de classification moyenne
• \(AUC\) : aire sous la courbe ROC, qui désigne permet de visualiser la performance de score

1. Erreur de classification

LDA.error	Logistic.error	Foret.error
0.1558902	0.1505757	0.1426041

La forêt aléatoire semble nettement plus performante du point de vue du critère de classification

2. Courbe ROC et AUC

C’est très dur de visualiser quelle courbe est la meilleure bien qu’on voit que la rouge semble être tout le temps au dessus ou égal aux autres. La courbe verte se détache vers \(\alpha(s)=0.15\), donc son score sera moins performant.
Il faut comparer l’aire sous la courbe pour être sûr.

Score	AUC
score.foret	0.888
score.Logistic	0.882
score.lda	0.879

On conclus donc la même chose qu’avec le critère de classification.
On gardera la forêt aléatoire pour prédire et classifier le niveau des joueurs à StarCraft2

3. Matrice de confusion

On va regarder la matrice de confusion de la méthode logistique et de la forêt aléatoire. Nous avions observé dans la section logistique que la méthode se trompait plutôt sur les faux négatifs. C’est à dire que parmis son erreur de classification, la plupart des erreurs provenait du fait qu’elle classait un joueur très bon en joueur “mauvais”.

faux_negatifs	faux_positifs
117	53

Pour la forêt aléatoire les erreurs sont :

faux_negatifs	faux_positifs
114	51

Donc la forêt aléatoire est un modèle similaire à la logistique car elle a plus de “mal” a classer un joueur en tant que très bon joueur

C’est un bon modèle dans le cas par exemple des sponsors qui veulent proposer un contrat aux meilleurs joueurs.

Conclusion de l’étude

Nous avons construit une méthode permettant de classer les joueurs en fonction de leur niveau. Cette méthode est une forêt aléatoires de 1000 arbres avec des paramètres calibrés pour optimisé le critère de performance. On peut interpreter ce modèle grâce à l’importance des variables combinée à nos analyses descriptives (ACP,bivariées).

La réaction d’un joueur est le facteur discriminant principal. Plus il réagit vite et meilleur il sera. De plus, on a constaté que le nombre d’actions par minute augmentait à chaque niveau (cf stats descriptives), comme c’est la deuxième variable la plus importante de notre modèle il convient de dire qu’avoir un nombre d’actions par minutes élevés contribue à la réussite d’un joueur. Le nombre de cycle PAC est corrélé avec la durée de réaction. Ensuite vient l’importance de temps de jeu. Ce qui semble logique, car plus un joueur va être expérimenté et meilleur il sera. Puis il y a les facteurs de raccourcis clavier. Dans starcraft2 (qui est un jeu de stratégie en temps réel), il est indispensable de se créer des raccourcis clavier et de les utiliser pour gagner du temps et donc augmenter son APM et réduire son temps de réaction. Les autres variables ne sont pas très importantes car soit l’information est déja comprise dans les premières ou soit elles sont quasiment indépendantes du niveau du joueur. Les variables comme utilisation d’unité complexe sont peu représentées car peu de joueurs ont une stratégie sur le long terme pour former des unités fortes. La plupart forme des unités de bases en grand nombres et les combinent à leur skills pour déborder au plus vite l’adversaire.

Nous avons une erreur de classification autour de 14-15%, ce qui pourrait être surement réduit si on codait:

\(Y_i\begin{cases}1 &\text{ si le ième joueur est de niveau Professionnel}\\0 &\text{ sinon }\end{cases}\)

En effet l’écart avec l’élite de Sarcraft2 serait plus important et donc le modèle pourrait surement mieux discriminer les individus. En revanche nous n’avons que peu d’individus professionnels c’est pourquoi nous avons fait le choix de coder \(Y\) comme expliqué dans l’étude.