2024-12-29
© [Link]
République Tunisienne
Ministère de l'Enseignement Supérieur et de la recherche Scientifique
Deep Learning
Dr. Ikram BEN AHMED
benahmedikram@[Link]
APPRENTISSAGE NON SUPERVISÉ
[Link] BEN AHMED 2
1
2024-12-29
Motivations
L'étiquetage coûte cher
Mieux comprendre la structure des données
Trouver des prototypes dans les données
1.3
[Link] BEN AHMED 4
2
2024-12-29
Proposer un regroupement
C’est subjectif !
Simpson's Family School Employees Females Males
1.3
Qu'est-ce que la similarité ?
La similitude est difficile à définir, mais…"On le sait quand on le voit’’
3
2024-12-29
Définition des mesures de distance
Définition : Soient O1 et O2 deux objets de l'univers des
objets possibles. La distance (dissimilarité) entre O1 et
O2 est un nombre réel noté D(O1,O2)
Peter Piotr
0.23 3 342.7
1.7
Edit Distance Example How similar are the names
“Peter” and “Piotr”?
Assume the following cost function
Il est possible de transformer n'importe quelle Substitution 1
chaîne Q en chaîne C, en utilisant uniquement la Unit
substitution, l'insertion et la suppression. Insertion 1 Unit
Deletion 1 Unit
Supposons que chacun de ces opérateurs ait un
coût qui lui est associé.
D(Peter,Piotr) is 3
La similarité entre deux chaînes peut être définie
comme le coût de la transformation la moins
chère de Q en C.
Peter
Substitution (i for e)
Piter
Insertion (o)
Pioter
Deletion (e)
Piotr
4
2024-12-29
A generic technique for measuring similarity
Pour mesurer la similitude entre deux objets,
transformez l'un en l'autre et mesurez l'effort que
cela a demandé. La mesure de l'effort devient la
mesure de la distance.
La distance entre Patty et Selma :
Changer la couleur de la robe, 1 point
Changer la forme de la boucle d'oreille, 1 point
Changer la partie des cheveux, 1 point
D(Patty,Selma) = 3
La distance entre Marge et Selma :
Changer la couleur de la robe, 1 point
Ajouter des boucles d'oreilles, 1 point
Diminuer la hauteur, 1 point C'est ce qu'on appelle la
Commencer à fumer, 1 point "distance d'édition" ou la
Perdre du poids, 1 point "distance de
D(Marge,Selma) = 5 transformation”
1.9
Quelles propriétés doit avoir une mesure de
distance ?
D(A,B) = D(B,A) Symétrie
D(A,A) = 0 Constance de l'auto-similarité
D(A,B) = 0 Si A= B Positivité (Séparation)
D(A,B) D(A,C) + D(B,C) Inégalité triangulaire
1.10
5
2024-12-29
Deux types de clustering
• Partitional algorithms: construisez diverses partitions,
● puis évaluez-les selon certains critères
• Hierarchical algorithms: créer une décomposition hiérarchique de l'ensemble d'objets à l'aide
de certains critères
Hierarchical Partitional
1.11
Clustering hierarchique
Comme nous ne pouvons pas tester tous les arbres possibles, nous devrons effectuer
une recherche heuristique de tous les arbres possibles. On pourrait faire ça..
Ascendant (agglomératif) : en commençant par chaque élément dans son propre
cluster, trouvez la meilleure paire à fusionner dans un nouveau cluster. Répétez jusqu'à
ce que tous les clusters soient fusionnés.
Descendant (division) : en commençant par toutes les données d'un seul cluster,
envisagez toutes les manières possibles de diviser le cluster en deux. Choisissez la
meilleure division et opérez récursivement des deux côtés.
1.12
6
2024-12-29
Nous commençons avec
une matrice de distance qui
contient les distances entre
chaque paire d'objets dans
notre base de données.
0 8 8 7 7
0 2 4 4
0 3 3
D( , ) = 8 0 1
D( , ) = 1 0
Clustering Partitionnel
• Non hiérarchique, chaque instance est placée
dans exactement un des K clusters non
superposés.
• Étant donné qu'un seul ensemble de clusters
est généré, l'utilisateur doit normalement
saisir le nombre de clusters K souhaité.
1.14
7
2024-12-29
K Means
Ikram BA 3 GL EPI degital 13
Partition Algorithm 1: k-means
1. Décidez d'une valeur pour k.
2. 2. Initialiser les k centres de cluster (au hasard, si
nécessaire).
3. 3. Décidez des appartenances de classe des N objets en
les affectant au centre de cluster le plus proche.
4. 4. Ré-estimer les k centres de cluster, en supposant que
les appartenances trouvées ci-dessus sont correctes.
5. 5. Si aucun des N objets n'a changé d'appartenance lors
de la dernière itération, quittez. Sinon passez au 3.
1.16
8
2024-12-29
Comments on k-Means
▪ Les points forts
• Relativement efficace
• Se termine souvent à un optimum local.
▪ Les points faibles
• Applicable uniquement lorsque la moyenne est définie, alors qu'en est-il
des données catégorielles ?
• Nécessité de spécifier k, le nombre de clusters, à l'avance
• Incapable de gérer les données bruyantes et les valeurs aberrantes
• Ne convient pas pour découvrir des clusters aux formes non convexes
1.17
Exercise: K-means clustering
▪ Use the k-means algorithm and Euclidean distance to cluster the following
8 examples into 3 clusters:
▪ A1=(2,10), A2=(2,5), A3=(8,4), A4=(5,8), A5=(7,5), A6=(6,4), A7=(1,2),
A8=(4,9).
1.18
9
2024-12-29
STEP 1
10
2024-12-29
STEP 2
STEP 3
11
2024-12-29
STEP 4
STEP 5
12
2024-12-29
COMPLETE
13