Classification Flashcards
Quels sont les concepts de base de la classification?
Plusieurs méthodes d’apprentissage supervisé
- Arbre de décision
- Réseau de neurones (Neural network)
- Machine à vecteurs de support (Support Vector Machine)
- Méthode des k plus proches voisins (k-nearest neighbors)
- Classification naïve bayésienne (Naive Bayes classifier)
- Espace de versions, etc.
Apprentissage supervisé : classification
- Les observations (ou exemples) ont des étiquettes indiquant leur classe d’appartenance. Notion d’ensemble d’apprentissage (training set)
- Les nouvelles données sont alors classifiées selon l’ensemble d’apprentissage via les règles de classification générées. Il s’agit de l’ensemble de test (validation/test set)
Qu’est que la classification et la prédiction?
Classification
- Prédit l’étiquette d’une classe (valeur discrète ou nominale), c.-à-d. la classe d’appartenance
- Étape 1: classifie les données en construisant un modèle sur la base de l’ensemble d’apprentissage et les modalités de l’attribut de classification
- Étape 2 : utilise le modèle pour classifier de nouvelles données
Prédiction numérique
- Prédit la valeur d’une variable continue inconnue
Applications typiques
- Approbation de prêt, diagnostic médical, détection de fraude, marketing ciblé, etc.
Que sont les arbres de décision?
Technique de classification : On veut classifier en fonction d’un attribut de classification
Intrant
- Une table de valeurs discrètes ou nominales
Extrant
- un arbre de décision
- Chaque nœud non terminal spécifie un test d’attribut
- Chaque branche partant d’un nœud correspond à une valeur possible de l’attribut concerné
Construction de l’arbre de décision – deux phases :
- Construction de l’arbre
- Élagage de l’arbre
* Identification et suppression des branches comportant du bruit (erreurs) ou des cas d’exception
Utilisation de l’arbre : classification d’un exemple inconnu
- Test des valeurs d’attributs de l’exemple par rapport à l’arbre de décision
Structure
- Les feuilles de l’arbre représentent la classification
- La forme de l’arbre dépend de l’ordre dans lequel les attributs sont testés
- On peut calculer le “gain” induit par chaque attribut et placer les attributs par ordre décroissant du gain.
- L’attribut avec le plus grand gain est placé au niveau de la racine de l’arbre
- L’attribut ayant le plus faible gain est représenté au niveau le plus bas (autre que les feuilles)
- Possibilité de générer des règles de classification
Règles de classification peuvent être extraites de l’arbre
Algorithme de base (vorace)
- Arbre construit selon une approche descendante (diviser pour régner)
- Au début, tous les exemples sont placés dans la racine de l’arbre
- Les exemples sont ensuite partitionnés récursivement sur la base des attributs sélectionnés
- L’ordre de prise en compte des attributs se fait à l’aide d’une mesure statistique ou heuristique (ex. gain d’information)
- Les attributs doivent avoir des valeurs discrètes
Conditions d’arrêt
- Tous les exemples contenus dans un nœud donné appartiennent à une même classe
- Il n’y a plus d’attributs à partitionner.
- Il ne reste plus aucun exemple à classer.
Quelles sont les mesures de sélection des attributs?
Gain d’information (ID3/C4.5)
- Suppose que les attributs ont des valeurs discrètes
- Possibilité d’utiliser des valeurs continues
Gini index (IntelligentMiner d’IBM)
- Suppose que les attributs ont des valeurs continues
- Diverses possibilités de recodification des valeurs d’attributs
- Peut être adapté au cas des attributs catégoriels
Qu’est-ce que le gain d’information?
Gain d’information
- Détermine l’ordre d’apparition des attributs dans l’arbre
- La racine de l’arbre a l’attribut avec le plus grand gain
Montant d’information I(p, n)
- Soient deux classes P et N
- Si l’ensemble S d’apprentissage (training set) contient p exemples de la classe P (ex. exemples positifs) et n exemples de la classe N (exemples négatifs)
- I(p, n) permet de décider si un exemple quelconque dans S appartient à P ou à N :
I(p, n) = -(p/(p+n)) log2 (p/(p+n)) - (n/(p+n)) log2 (n/(p+n))
Entropie d’un attribut A
- Si l’ensemble S est partitionné en sous-ensembles {S1, S2 , …, Sv} selon les diverses valeurs de A
- Si Si contient pi exemples de P et ni exemples de N, l’entropie (information permettant de classer les exemples dans les sous-arbres de Si) est :
E(A) = Σ((pi + ni)/(p+n)) I (pi, ni)
- Gain d’information pour A :
Gain(A) = I(p,n) - E(A)
Qu’est-ce que les règles de classification?
Règles simples à lire et comprendre
Une seule règle pour le chemin de la racine vers la feuille
Chaque paire <attribut‐valeur> forme une conjonction et la feuille prédit la classe
Règles mutuellement exclusives et exhaustives
Qu’est-ce que la sélection et l’évaluation du modèle?
Principe
- Utiliser l’ensemble de test pour évaluer l’exactitude du modèle
Méthodes d’estimation
- Échantillonnage
- Validation croisée à k plis (k-fold cross-validation)
- Bootstrap, etc.
Comparaison de classifieurs
- Intervalles de confiance
- Analyse coût-bénéfice et courbes ROC
Qu’est-ce que la méthode de validation croisée?
Validation croisée à k plis
- Quelques variantes
- Souvent incorporée dans les outils
- Valeur de k souvent à 10
- Partitionner aléatoirement en k fois les données en k sous-ensembles disjoints de même taille
- À l’iteration i, utiliser un sous-ensemble pour le test et les k-1 sous-ensembles restants comme ensemble d’apprentissage
- Calculer la moyenne de l’exactitude (accuracy) du modèle des diverses itérations.
Qu’est-ce que la matrice de confusion?
Avec m classes, la valeur ai,j d’une matrice de confusion indique le nombre de tuples de la classe i étiquetés par le classifieur comme classe j.
On compare la classe observée avec la classe prédite pour déterminer les vrais positifs, les faux positifs, les faux négatifs et les vrais négatifs.
Quelles sont les métriques d’un classifieur?
Exactitude (Accuracy) :
- Pourcentage des tuples de test qui sont correctement classifiés
= (VP + VN)/Total
Taux d’erreur (Error rate)
= 1 – accuracy = (FP + FN)/Total
Problème:
- Une classe peut être rare, e.g. fraudeur ou séropositif
- Majorité significative d’une classe (ex. positive)
Sensibilité
- Sensitivity: True Positive recognition rate
= VP/P
Spécificité (Specificity): True Negative recognition rate
= VN/N
Rappel (Recall)
- Notion de complétude, identique à la sensibilité
- Proportion des tuples positifs que le classifieur a étiqueté positifs = VP/P
Précision (Precision)
- Proportion des tuples qui sont effectivement positifs parmi les instances étiquetées positives par le classifieur = VP/(VP + FP)
Relation inverse entre le rappel et la précision
Mesure F (F-score):
- Moyenne harmonique de la précision PR et du rappel
RP = 2(PR x RP)/(PR + RP)
Courbe ROC
- ROC : Receiver Operating Characteristic
- Courbe représentant la performance d’un classifieur
- Relation entre la sensibilité et la spécificité pour divers seuils de classification.
- Le taux de vrais positifs (sensibilité) est sur l’ordonnée
- L’abscisse correspond au taux de faux positifs (1 – spécificité = FP/(FP + VN)
- AUC : aire sous la courbe ROC est une mesure de l’exactitude du modèle
- Si le modèle de classification est parfait, l’aire AUC est proche de 1
- Le modèle est d’autant plus inexact que sa courbe est proche de la diagonale.
Conclusion de la classification.
La classification est une technique de fouille de données et d’apprentissage machine
Plusieurs méthodes et métriques d’évaluation
Validation croisée à k plis recommandée pour l’estimation de l’exactitude
Aucune méthode de classification n’est la meilleure pour toutes les collections de données
Compromis entre l’exactitude, le temps d’exécution, l’extensibilité et la robustesse
