Algorithme d’apprentissage d’un classifieur basé sur un ensemble de profils

Dès qu’un phénomène, qu’il soit physique, biologique ou autre, est trop complexe ou encore trop bruité pour accéder à une description analytique débouchant sur une modélisation déterministe, un ensemble d’approches est élaboré afin d’en décrire au mieux le comportement à partir d’une série d’observations. On appelle apprentissage statistique l’ensemble d’approches élaboré [5]. C’est une combinaison à la fois de l’apprentissage automatique et de la statistique [26]. L’apprentissage automatique consiste à utiliser des ordinateurs pour optimiser un modèle de traitement de l’information selon certains critères de performance à partir d’observations. Tandis que la statistique permet de formaliser le processus, de garantir sa qualité et éventuellement de suggérer de nouvelles techniques. Cependant le principe de l’apprentissage reste le même, mais la démarche est différente selon que la taille du jeu de données est grande ou petite.

 Présentation de l’algorithme de construction du classifieur

 Lorsque la taille des données est suffisamment grande, on adoptera l’approche Apprentissage/Validation/Test pour la sélection d’un ensemble optimal de profils. Cette approche consiste à subdiviser les données de manière aléatoire en trois ensembles : un ensemble d’apprentissage, un ensemble de validation et un ensemble test. L’apprentissage statistique que nous proposons peut être résumée par les différentes étapes suivantes : 1. Discrétiser toutes les variables numériques par une méthode de discrétisation (au choix) 2. A partir d’un ensemble d’apprentissage : (a) Spécifier le paramètre d’apprentissage λ = (s0, c0, l0) (b) Générer un ensemble Uλ de profils (c) Elaguer les profils redondants dans Uλ pour constituer un petit ensemble U 1 λ = {[φ(X, U) = 1] → [Y = 1]; U ∈ Uλ} 3. A partir d’un ensemble de validation : (a) Réévaluer l’ indicateur de performance VPP (ou RVP ou RVN) de toutes les règles dans U 1 λ (b) Supprimer les profils dont le RVP est inférieur à un (1) (c) Parmi les profils dans U 1 λ qui sont emboîtés, ne retenir que le profil dont le VPP (ou le RVP ou le RVN) est le plus significatif. Au sortir de l’étape 3, on dispose alors d’un ensemble de profils U 2 λ tel que |U 2 λ | ≤ |U 1 λ |. 5. Définir la règle de classement (classifieur) φ d’une observation X par φ(X, λ) =    1 si |U2 λ X | m=1 φ(X, Um) > 0 0 sinon Le classifieur φ(X, λ) est un cas particulier du classifieur défini au chapitre II à la section 3.2 où on a choisi k égal à zéro. On choisit alors de classer positive une observation X lorsqu’elle vérifie au moins un profil parmi ceux qui sont dans l’ensemble U 2 λ . Dans tout ce qui suit, on fixe à un le nombre minimum de profils à vérifier pour qu’une observation soit classée positive. 3 Prétraitement des données : discrétisation des covariables numériques Un ensemble de données pour un classement est normalement sous la forme d’un tableau de données qui est décrit par un ensemble de variables distinctes. La plupart des applications réelles (données réelles) pour une classification supervisée comportent à la fois des variables numériques (continues) et des variables nominales (catégorielles). Certaines méthodes de classement, particulièrement l’algorithme d’apprentissage des règles d’association, exigent que toutes les covariables soient nominales. Ainsi il est nécessaire de convertir les variables continues en des variables discrètes. L’idée consiste à transformer chaque variable numérique Xj en une variable catégorielle X∗ j . La variable X∗ j est obtenue en subdivisant le domaine des valeurs de Xj en qj intervalles m Xj h , h = 1 : qj . La variable X∗ j sera utilisée à la place de Xj pour construire le classifieur. En général une variable continue est une variable dont le domaine de définition est totalement ordonné. La discrétisation doit être choisie de manière à apporter des informations de classification utiles sans modifier les classes auxquelles les observations du domaine de la variable appartiennent. En général, une discrétisation est simplement une condition logique, en termes d’une ou plusieurs valeurs évaluées, qui sert à partitionner les données en au moins deux sous-ensembles. Supposons que Xj soit une variable numérique et l’intervalle [a, b] soit son domaine. Une partition πXj sur [a, b] est définie comme le sous-ensemble des k intervalles suivants πXj = {[xj0, xj1), [xj1, xj2), . . . , [xj(k−1), xjk]} où xj0 = a, xj(i−1) < xji pour i = 1 : k et xjk = b. Ainsi la discrétisation est le processus qui produit une partition πXj sur [a, b]. Plusieurs méthodes de discrétisation des variables numériques ont été étudiées dans la littérature. On peut, par exemple, considérer des combinaisons linéaires de plusieurs variables et comparer le résultat avec un seuil (Breiman et al., 1984)[7]. Il est aussi possible d’éviter le seuillage en formant une condition qui compare les valeurs de deux ou plusieurs variables directement. Cependant le nombre de telles expressions possibles rend l’espace de recherche très vaste. La méthode de discrétisation d’une variable numérique la plus simple reste la méthode de largeur d’intervalle égale (Equal Interval Width Method). Elle consiste à partitionner son domaine en intervalles de largeur égales. Une méthode de discrétisation de variable numérique par la discrétisation adaptative a été proposée dans [8]. La méthode consiste à diviser d’abord le domaine de la variable en deux intervalles de largeur égale et un processus d’apprentissage est lancé pour générer les règles. Ensuite, la qualité des règles est testée en évaluant les performances des règles. Si la mesure de performance est inférieure à un seuil fixe, l’un des intervalles est subdivisé en outre, et le processus est répété. Le principal inconvénient de cette méthode, cependant, est la répétition du processus d’apprentissage jusqu’à ce que le niveau de performance finale soit atteint. Une discrétisation basée sur l’entropie marginale maximale a été introduite dans [30]. Ce procédé consiste à diviser le domaine de la variable numérique de telle sorte que la fréquence d’échantillonnage dans chaque intervalle soit approximativement égale. Ce procédé est généralement appelé la méthode par intervalle de fréquence égale (Equal Frequency per Interval Method). Le seul paramètre fourni par l’utilisateur est le nombre d’intervalles à induire sur le domaine d’origine. La discrétisation par la mesure de l’entropie utilise les bornes du domaine de la variable pour induire les intervalles souhaités. Cette méthode de sélection d’un point de coupure est utilisée dans l’algorithme ID3 [23], dans l’algorithme CART [6], et d’autres [15]. Lorsque nous traitons un problème de classification supervisée, il est naturel de penser à discrétiser les variables numériques en fonction de la variable réponse. Ceci constitue l’un des points faibles des différentes méthodes de discrétisation citées précédemment. Ce concept est pris en compte par la méthode de discrétisation avec la classe-entropie comme critère pour sélectionner le meilleur point de coupure [13]. Dans tout ce qui suit, nous avons utilisé la méthode de discrétisation dont le critère d’arrêt est basé sur le principe de la longueur de description minimum plus connu sous le nom de MDLP (Minimum Description Length Principle). Cette méthode est initiée par Fayyad et Irani [13, 14]. La méthode est présentée comme une méthode efficace pour la discrétisation pour l’apprentissage des arbres de décision et du classifieur de Bayes Naïf [2] (voir l’annexe B pour plus de détails).

Extraction d’un ensemble initial de profils

L’ensemble des profils Uλ, généré au départ pour l’apprentissage du classifieur, est caractérisé par c0, une estimation de la VPP, et s0, une estimation du support. L’un des plus connus algorithmes d’exploration des règles d’association, utilisant c0 et s0 pour l’extraction des règles les plus fréquentes, reste l’algorithme « apriori ». Il est l’un des algorithmes d’extraction de règles d’association qui a utilisé en premier l’élagage basé sur le support pour contrôler systématiquement la croissance exponentielle des règles candidates. C’est la raison pour laquelle, nous avons choisi de l’utiliser pour la suite. On pouvait utiliser d’autres algorithmes d’extraction de règles fréquentes existant dans la littérature par exemple l’algorithme « FP-Growth »(FPtree structure) [17]. Un choix de l’algorithme d’extraction est laissé à l’utilisateur. Ci-après (Tableau III.1), nous présentons un pseudo code de la partie de génération des profils fréquents par l’algorithme « apriori ». Soit Ck l’ensemble des profils de longueur k candidats, D l’ensemble de toutes les observations et Fk l’ensemble des profils fréquents et de longueur k. Algorithme : Génération de règles fréquentes par l’algorithme « apriori » – Entrées : D un ensemble d’observations, s0 un support minimum et c0 une confiance minimum – Sorties : Uλ un ensemble de profils fréquents 1 : k=1 2 : Fk = {Trouver tous les 1-itemsets fréquents} 3 : répéter 4 : k=k+1 5 : Ck = apriori-gen(Fk−1 ). {Générer les profils candidats} 6 : pour chaque observation t ∈ D faire 7 : Ct = subset(Ck , t). {Identifier tous les candidats contenus dans t} 8 : pour chaque profil candidat c ∈ Ct faire 9 : supp(c) = supp(c) + 1. {Incrémenter le compte du support} 10 : si t.class = c.class faire { t.class : la classe associée à l’observation t} 11 : conf(c) = conf(c) + 1. {Incrémenter le compte de la confiance} 12 : fin si 13 : fin pour 14 : fin pour 15 : Fk ={c ∈ Ck | supp(c) ≥ s0 ; conf(c)/supp(c) ≥ c0 } {Extraire les profils fréquents de taille k} 16 : jusqu’à Fk = ∅ 17 : Retourner : Uλ = S k Fk

Elagage des profils redondants 

Dans cette section, nous nous intéressons aux profils qui sont liés à la variable réponse. La suppression des profils qui ne sont pas corrélés à la variable réponse et des profils redondants permettra de sélectionner un ensemble réduit de profils dont on pourra se servir pour construire un classifieur performant. Soient U1 =  m Xj h  j∈J et U2 =  m Xl h  l∈L deux profils tels que U2 soit emboîté dans U1. L’application des résultats théoriques précédents nécessite de faire un test d’hypothèse sur l’égalité des couvertures, sur l’égalité des supports ou sur l’égalité des spécificités de deux profils emboîtés. Pour cela, il est possible de faire un test stochastique

Test stochastique (randomisé) pour la sélection entre deux profils emboîtés

En principe, si l’égalité n’est pas vérifiée sur un échantillon donné, on peut affirmer qu’elle n’est pas vérifiée sur la population dont est issu l’échantillon. Par contre on ne peut pas en dire autant lorsqu’elle est vraie sur un échantillon. C’est la raison pour laquelle un test stochastique (ou test randomisé) est nécessaire. On note par φ(X, U1) = Y j∈J 1l  Xj = m Xj h  et φ(X, U2) = Y l∈L 1l  Xl = m Xl h  les fonctions de classement générées respectivement par U1 et U2. Puisque U2 est emboîté dans U1, on a [φ(X, U2) = 1] ⊂ [φ(X, U1) = 1]. (a) Soit le paramètre θ1 défini par θ1 = Pr(φ(X, U1) = 1) − Pr(φ(X, U2) = 1). Nous voulons tester si oui ou non θ1 est nulle i.e décider entre les deux hypothèses H1 0 : θ1 = 0 vs H1 1 : θ1 6= 0 Nous allons considérer la variable aléatoire définie par Z1(X) = φ(X, U1) − φ(X, U2)

Algorithme de la procédure d’élagage

En se basant sur les résultats présentés dans la section précédente, on peut proposer une procédure d’élagage des profils redondants comme suit. Algorithme : Procédure d’élagage des profils redondants – Entrées : R un ensemble de profils – Sorties : R ′ un ensemble de profils non redondants 1 : On se donne R un ensemble de profils 2 : pour tout profil U ∈ R faire 3 : SU = subset(U, R) {le sous-ensemble de profils de R emboîtés dans U} 4 : pour tout profil U ′ ∈ SU faire 5 : Tester H1 0 : Pr {φ(X, U) = 1} = Pr {φ(X, U′ ) = 1} vs H1 1 : Pr {φ(X, U) = 1} 6= Pr {φ(X, U′ ) = 1} 6 : Si H1 0 est vraie, S ′ U = delete(U ′ , SU ) {supprimer U ′ de SU en vertu de la proposition 3.} 7 : Sinon 8 : Tester H2 0 : Pr {φ(X, U) = 1,Y = 1} = Pr {φ(X, U′ ) = 1,Y = 1} contre son opposée H2 1 9 : Si H2 0 est vraie, S ′ U = delete(U, SU ) {supprimer U de SU en vertu de la proposition 4.} 10 : Tester H3 0 : Pr {φ(X, U) = 0,Y = 0} = Pr {φ(X, U′ ) = 0,Y = 0} contre son opposée H3 1 11 : Si H3 0 est vraie, S ′ U = delete(U ′ , SU ) {supprimer U ′ de SU selon la proposition 5.} 12 : fin si 13 : fin pour U ′ 14 : fin pour U 15 : Retourner R ′ = S U∈R S ′ U Tableau III.2 – Algorithme d’élagage des profils redondants Le test stochastique présenté ci-dessus est applicable quelle que soit la taille des données d’analyse. Habituellement, l’ensemble U 1 λ contient un grand nombre de profils, certainement plus qu’il en faut pour construire une fonction de classification qui est efficace et facile à mettre en œuvre.