Classification Flashcards

1
Q

Quels sont les concepts de base de la classification?

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Qu’est que la classification et la prédiction?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Que sont les arbres de décision?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Quelles sont les mesures de sélection des attributs?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Qu’est-ce que le gain d’information?

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Qu’est-ce que les règles de classification?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Qu’est-ce que la sélection et l’évaluation du modèle?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Qu’est-ce que la méthode de validation croisée?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Qu’est-ce que la matrice de confusion?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Quelles sont les métriques d’un classifieur?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Conclusion de la classification.

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly