Classification par plus proches voisins, compromis biais-variance 
=================================================================

CORRECTION


1. 
echo "0.42 0.58 q" | flreadasc 2 c1
echo "0.58 0.42 q" | flreadasc 2 c2
sample_gm -n 10 -s 0.16 c1 centres1
sample_gm -n 10 -s 0.16 c2 centres2
fconst visu_centres 128 400 400
fmpset -s 400 visu_centres centres1 0 visu_centres
fmpset -s 400 visu_centres centres2 255 visu_centres
cview -z 2 visu_centres &


2. 
sample_gm2 -n 100 -s 0.05 centres1 sample1
sample_gm2 -n 100 -s 0.05 centres2 sample2

fconst visu 128 400 400
fmpset -s 400 visu sample1 0 visu
fmpset -s 400 visu sample2 255 visu
cview -z 2 visu &


3.
classif_ppv -n 400 sample1 sample2 ppv1
ccopy ppv1 visu_ppv1
fmpset -s 400 visu_ppv1 sample1 0 visu_ppv1
fmpset -s 400 visu_ppv1 sample2 255 visu_ppv1
cview -z 2 visu_ppv1 &


4. 
sample_gm2 -n 1000000 -s 0.05 centres1 test1
sample_gm2 -n 1000000 -s 0.05 centres2 test2
test_error sample1 sample2 ppv1
test_error test1 test2 ppv1

Sur l'échantillon d'apprentissage, on trouve une erreur
de classification de 0.5 % (cette erreur est théoriquement
nulle, mais la discrétisation rend possible la coïncidence
de deux échantillons appartenant à des classes différentes)

Sur l'échantillon de test, l'erreur de classification est de 15.9 %
(ceci varie bien sûr d'une expérience à l'autre). 
En termes de compromis biais-variance, la situation n'est pas très 
équilibrée: il y a beaucoup de variance (la carte de classification change
beaucoup quand on change l'échantillon d'apprentissage) et un faible biais.


5.
Le classifieur qui minimise la probabilité d'erreur est celui qui 
attribue au point x la classe 1 si p1(x)>p2(x), et la classe 2 dans 
le cas contraire, p1 et p2 étant les densités des lois des classes 1 
et 2 (mélange de gaussiennes). 

classif_gk -s 0.05 -n 400 centres1 centres2 optimal
ccopy optimal visu_optimal
fmpset -s 400 visu_optimal sample1 0 visu_optimal
fmpset -s 400 visu_optimal sample2 255 visu_optimal
cview -z 2 visu_optimal &
test_error sample1 sample2 optimal
test_error test1 test2 optimal

L'erreur de classification est de 11.7 % (test set) et 13 % (train set)


6. 
Voir le module classif_kppv.c

# vérification
classif_kppv -n 400 1 sample1 sample2 ppvk
test_error sample1 sample2 ppvk
test_error test1 test2 ppvk

cview -z 2 visu_optimal &

# balayage de plusieurs valeurs de k
foreach k (3 5 7 11 15 21 31 41 51)
  echo k = $k
  classif_kppv -n 400 $k sample1 sample2 ppvk
  ccopy ppvk visu_ppvk
  fmpset -s 400 visu_ppvk sample1 0 visu_ppvk
  fmpset -s 400 visu_ppvk sample2 255 visu_ppvk
  cview -z 2 visu_ppvk 
end

Quand k augmente, la carte de classification devient plus régulière
(moins de composantes connexes), se rapproche de la carte de 
classification optimale, puis s'en éloigne à nouveau quand k devient 
trop grand (la carte devient trop simple).


7.
set k = 1
\rm erreur_test erreur_app
while ( $k <= 51 )
  echo "k = $k"
  classif_kppv -n 400 $k sample1 sample2 kppv
  echo $k >> erreur_test
  echo $k >> erreur_app
  test_error test1 test2 kppv >> erreur_test
  test_error sample1 sample2 kppv >> erreur_app 
  @ k += 2
end
echo "q" >> erreur_test
echo "q" >> erreur_app
flreadasc 2 erreur_test_fl < erreur_test
flreadasc 2 erreur_app_fl < erreur_app
flconcat erreur_test_fl erreur_app_fl erreur
fkview -g 4 -d 3 -a erreur &


On visualise parfaitement le compromis biais-variance, valeur de k pour 
laquelle l'erreur de classification (probabilité estimée sur l'ensemble 
de test) est minimale. Pour k=1, la variance domine, et quand k augmente,
le biais prend peu à peu le dessus. L'erreur de classification sur 
l'échantillon d'apprentissage, nulle pour k=1, rejoint peu à peu l'erreur
de classification estimée à mesure que la capacité de généralisation du
modèle augmente (ie quand k augmente).

Pour la meilleure valeur de k (ici k=21), on trouve une erreur de 
classification estimée de 13.3 %, ce qui est proche de la valeur obtenue 
pour le classifieur optimal (11.7 %). La méthode de classification au k-plus 
proches voisins est ici étonnament efficace compte tenu de sa simplicité
et de sa généricité.