Data-Mining
Examen 2007/2008 4ème année
G. Gasso
– Durée : 3h
– Documents autorisés : cours et calculatrice
– La copie du voisin n’est pas un document autorisé
– L’annexe 1 est à rendre avec la copie finale
1 Ka-mines (4 points)
1. On veut regrouper les points (les ronds) des figures en annexe 1 en deux clusters. On utilise
l’algorithme de K-means avec K = 2. L’initialisation des centres µ1 et µ2 est marquée sur
la figure en haut à gauche.
Détailler sur les figures en annexe chaque itération (affectation des points et calcul des nou-
veaux centres) de l’algorithme jusqu’à convergence.
Aucun calcul numérique n’est demandé. Justifier graphiquement les résultats de chaque
itération.
2 SVM à pénalisations différentes en fonction des points (7 points)
Soit un ensemble de données étiquettées {(xi , yi ) ∈ X × Y}i=1,...,n avec Y = {−1, +1}.
On cherche à résoudre un problème SVM où on utilise un terme de régularisation Ci spécifique
pour chaque point xi . Le problème d’apprentissage est alors
1 2
Pn
minw,b,ξi 2 kwk + i=1 Ci ξi
s.c. yi (hw, xi i + b) ≥ 1 − ξi ∀ i = 1, . . . , n
ξi ≥ 0 ∀ i = 1, · · · , n
Dans cette formulation du problème, les ξi représentent les variables d’écart, les paramètres
Ci représentent les termes de régularisation fixés par l’utilisateur.
1. Exprimer le lagrangien L correspondant à ce problème.
2. Exprimer les conditions d’optimalité du lagrangien par rapport aux variables primales w, b, ξi .
3. Donner la formulation du problème dual. Quelle méthode connaissez-vous pour résoudre ce
problème dual ?
4. Proposer une façon de calculer le paramètre b.
5. On note respectivement D + = {(xi , yi ), yi = 1} et D − = {(xi , yi ), yi = −1)} les en-
sembles de points des classes "positive" et "négative". On considère Ci = C+ , ∀i ∈ D + et
Ci = C− , ∀i ∈ D − .
En s’inspirant de la question 1, donner la nouvelle formulation du problème SVM. Que
devient le problème dual ?
p.1/3
ASI4 Examen DM 2007/2008
3 Bayes et moindres carrés (9 points)
Soit un problème de classification à deux classes C1 et C2 avec des données {(xi , yi ) ∈
IRp ×Y}i=1,...,n où Y = {C1 , C2 }. On veut construire un classifieur en utilisant l’analyse linéaire
discriminante (LDA).
1. Montrer qu’un point quelconque x est affecté à la classe C2 si
1 ⊤ −1
w⊤ x > µ Σ µ2 − µ⊤ −1
1 Σ µ1 + log(Pr(C1 )) − log(Pr(C2 ))
2 2
avec w = Σ−1 (µ2 − µ1 ), Pr(C1 ) et Pr(C2 ) les probabilités a priori des classes C1 et C2 .
2. On veut estimer les moyennes µ1 , µ2 et la matrice de covariance Σ à partir des données
{(xi , yi )}i=1,...,n . On notera n1 le nombre de points de la classe C1 et n2 le nombre de
points de la classe C2 (n1 + n2 = n).
Donner l’expression des estimations µ̂1 , µ̂2 et Σ̂.
3. Plutôt que de faire la LDA, on veut estimer directement une fonction de décision f (x) =
x⊤ β + β0 avec β ∈ IRp et β0 ∈ IR en utilisant la méthode des moindres carrés. Pour cela,
on fait l’encodage suivant :
Classe C1 : yi = −n/n1 Classe C2 : yi = −n/n2
et on minimise le critère
n
X
J= (yi − x⊤
i β − β0 )
2
i=1
Ecrire le critère sous la forme matricielle J = (Y − Xa βa )⊤ (Y − Xa βa )
avec βa = [β ⊤ 1]⊤ . On précisera le vecteur Y et la matrice Xa .
4. Ecrire la condition d’optimalité de ce problème des moindres carrés par rapport à βa .
5. Montrer que le vecteur β vérifie la relation
n1 n2
(n − 2)Σ̂ + M̂ β = n(µ̂2 − µ̂1 ) avec M̂ = (µ̂2 − µ̂1 )(µ̂2 − µ̂1 )⊤
n
6. Déduire que M̂ β est colinéaire au vecteur (µ̂2 − µ̂1 ) càd M̂ β ∝ (µ̂2 − µ̂1 ).
7. En déduire alors que la solution de β obtenue par moindres carrés est colinéaire au vecteur
Σ̂−1 (µ̂2 − µ̂1 ). Comparer par rapport au vecteur w de la LDA. Quelle conclusion peut-on
tirer ?
p.2/3
ASI4 Examen DM 2007/2008
Annexe 1
Initialisation
4 4
3.5 µ1 3.5
3 3
2.5 2.5
2 2
1.5 1.5
1 µ2 1
0.5 0.5
0 0
−0.5 −0.5
−1 −1
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6
4 4
3.5 3.5
3 3
2.5 2.5
2 2
1.5 1.5
1 1
0.5 0.5
0 0
−0.5 −0.5
−1 −1
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6
4 4
3.5 3.5
3 3
2.5 2.5
2 2
1.5 1.5
1 1
0.5 0.5
0 0
−0.5 −0.5
−1 −1
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6
p.3/3
