Université de TunisInstitut Supérieur de Gestion de TunisÉcole Doctorale Sciences de Gestion
Motifs Corrélés Rares : Caractérisation etNouvelles Représentations Concises
Réalisé par :Souad B OUASKER
Encadrée par :Mr. Sadok B EN YAHIA (Maître de Conférences, FST)
Mr. Tarek H AMROUNI (Maître Assistant, ISAMM)
18 Mai 2012
Plan
1 Introduction
2 Caractérisation de l’ensemble MCR des motifs corrélés rares
3 Nouvelles représentations concises des motifs corrélés rares
4 Évaluation expérimentale
5 Application : Détection d’intrusions
6 Conclusion et perspectives
Plan
1 Introduction
2 Caractérisation de l’ensemble MCR des motifs corrélés rares
3 Nouvelles représentations concises des motifs corrélés rares
4 Évaluation expérimentale
5 Application : Détection d’intrusions
6 Conclusion et perspectives
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Introduction et motivations
Fouille de données
La fouille de données : Étape du processus d’ECD.
Extraction des motifs fréquents .
Génération des règles associatives .
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 4 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Introduction et motivations
Exemple : Contexte d’extraction K
N◦ client A : Chocolat B : Lait C : Chips D : Caviar E : Boissons1 1 0 1 1 02 0 1 1 0 13 1 1 1 0 14 0 1 0 0 15 1 1 1 0 1
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 4 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Introduction et motivations
Exemple : Contexte d’extraction K
N◦ client A : Chocolat B : Lait C : Chips D : Caviar E : Boissons1 1 0 1 1 02 0 1 1 0 13 1 1 1 0 14 0 1 0 0 15 1 1 1 0 1
O = {1, 2, 3,4, 5}I = {A,B,C,D,E}
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 4 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Extraction de motifs
Définition : Supports d’un motif
Le support conjonctif d’un motif I : Supp(∧I) (ou simplementSupp(I)).
Le support disjonctif d’un motif I : Supp(∨I).
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 5 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Extraction de motifs
Exemple : Contexte formel K
A B C D E1 1 0 1 1 02 0 1 1 0 13 1 1 1 0 14 0 1 0 0 15 1 1 1 0 1
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 5 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Extraction de motifs
Exemple : Contexte formel K
A B C D E1 1 0 1 1 02 0 1 1 0 13 1 1 1 0 14 0 1 0 0 15 1 1 1 0 1
Supp( ∧ AD) = 1
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 5 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Extraction de motifs
Exemple : Contexte formel K
A B C D E1 1 0 1 1 02 0 1 1 0 13 1 1 1 0 14 0 1 0 0 15 1 1 1 0 1
Supp( ∨ AD) = 3
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 5 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Extraction de motifs
Exemple : Contexte formel K
A B C D E1 1 0 1 1 02 0 1 1 0 13 1 1 1 0 14 0 1 0 0 15 1 1 1 0 1
Supp( ∧ ACE ) = 2
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 5 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Extraction de motifs
Exemple : Contexte formel K
A B C D E1 1 0 1 1 02 0 1 1 0 13 1 1 1 0 14 0 1 0 0 15 1 1 1 0 1
Supp( ∨ ACE ) = 5
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 5 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Motifs Rares versus Motifs Fréquents
Motifs fréquents : Support conjonctif ≥ minsupp.➥ La contrainte de fréquence est anti-monotone.
Motifs rares : Support conjonctif < minsupp.➥ La contrainte de rareté est monotone.
Pour minsupp = 3
Quelques motifs fréquents : (B, 4), (BE, 4), (BCE, 3)
Quelques motifs rares : (D, 1), (AB, 2), (ACD, 1)
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 6 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Motifs Rares versus Motifs Fréquents
Motifs fréquents : Support conjonctif ≥ minsupp.➥ La contrainte de fréquence est anti-monotone.
Motifs rares : Support conjonctif < minsupp.➥ La contrainte de rareté est monotone.
Pour minsupp = 3
Quelques motifs fréquents : (B, 4), (BE, 4), (BCE, 3)
Quelques motifs rares : (D, 1), (AB, 2), (ACD, 1)
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 6 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Motifs Rares versus Motifs Fréquents
Motifs fréquents : Support conjonctif ≥ minsupp.➥ La contrainte de fréquence est anti-monotone.
Motifs rares : Support conjonctif < minsupp.➥ La contrainte de rareté est monotone.
Pour minsupp = 3
Quelques motifs fréquents : (B, 4), (BE, 4), (BCE, 3)
Quelques motifs rares : (D, 1), (AB, 2), (ACD, 1)
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 6 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Motivations d’extraction des motifs rares
Cadres d’application des motifs rares :
La détection des maladies rares
La détection de fraudes dans les systèmes financiers
L’analyse du désordre génétique
La sécurité informatique
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 7 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Motivations d’extraction des motifs rares
Adresse IP Port Authentification Date196.24.12.21 23 V t1132.44.32.11 8080 V t2197.23.22.2 80 V t322.20.12.98 21 NV t410.24.12.21 1221 V t5
L’adresse 22.20.12.98 peut être à l’origine d’une attaque sur le port 21 !
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 8 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Motivations d’extraction des motifs rares
Adresse IP Port Authentification Date196.24.12.21 23 V t1132.44.32.11 8080 V t2197.23.22.2 80 V t322.20.12.98 21 NV t410.24.12.21 1221 V t5
L’adresse 22.20.12.98 peut être à l’origine d’une attaque sur le port 21 !
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 8 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Motivations d’extraction des motifs rares
Adresse IP Port Authentification Date196.24.12.21 23 V t1132.44.32.11 8080 V t2197.23.22.2 80 V t322.20.12.98 21 NV t410.24.12.21 1221 V t5
L’adresse 22.20.12.98 peut être à l’origine d’une attaque sur le port 21 !
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 8 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Problématique
Problématique
Absence de lien sémantique entre les items des motifs raresextraits :Exemple : “Lait” et “Caviar”.
Le nombre élevé des motifs rares extraits.
Solutions
Intégration des mesures de corrélation : Motifs corrélés rares
Extraction d’une représentation concise des motifs rarescorrélés.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 9 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Problématique
Problématique
Absence de lien sémantique entre les items des motifs raresextraits :Exemple : “Lait” et “Caviar”.
Le nombre élevé des motifs rares extraits.
Solutions
Intégration des mesures de corrélation : Motifs corrélés rares
Extraction d’une représentation concise des motifs rarescorrélés.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 9 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Problématique
Problématique
Absence de lien sémantique entre les items des motifs raresextraits :Exemple : “Lait” et “Caviar”.
Le nombre élevé des motifs rares extraits.
Solutions
Intégration des mesures de corrélation : Motifs corrélés rares
Extraction d’une représentation concise des motifs rarescorrélés.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 9 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Problématique
Problématique
Absence de lien sémantique entre les items des motifs raresextraits :Exemple : “Lait” et “Caviar”.
Le nombre élevé des motifs rares extraits.
Solutions
Intégration des mesures de corrélation : Motifs corrélés rares
Extraction d’une représentation concise des motifs rarescorrélés.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 9 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Introduction et MotivationsProblématique
Problématique
Problématique
Absence de lien sémantique entre les items des motifs raresextraits :Exemple : “Lait” et “Caviar”.
Le nombre élevé des motifs rares extraits.
Solutions
Intégration des mesures de corrélation : Motifs corrélés rares
Extraction d’une représentation concise des motifs rarescorrélés.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 9 / 36
Plan
1 Introduction
2 Caractérisation de l’ensemble MCR des motifs corrélés rares
3 Nouvelles représentations concises des motifs corrélés rares
4 Évaluation expérimentale
5 Application : Détection d’intrusions
6 Conclusion et perspectives
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
L’ensemble MCR des motifs rares corrélés
Définitions : Motif rares versus Motifs corrélés
L’ensemble des motifs rares est défini par :
MR = {I ⊆ I | Supp(I) < minsupp}
L’ensemble des motifs corrélés est défini par :
MC = {I ⊆ I | bond(I) ≥ minbond}
avec bond (I) =Supp( ∧ I)Supp( ∨ I)
.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 11 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
L’ensemble MCR des motifs rares corrélés
Définitions : Motif rares versus Motifs corrélés
L’ensemble des motifs rares est défini par :
MR = {I ⊆ I | Supp(I) < minsupp}
L’ensemble des motifs corrélés est défini par :
MC = {I ⊆ I | bond(I) ≥ minbond}
avec bond (I) =Supp( ∧ I)Supp( ∨ I)
.
Conjonction de deux contraintes de types opposés
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 11 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Motifs raresLe contexte K pour minsupp = 3
{}
BC AD CD BE CE
ABE ABD ACDACE BDE CDEABC
A B C E
ABCD ACDE ABCE ABDE BCDE
ABCDE
Motif rare minimal
BCD
3 4 4 1 4
2 3 2 3 10 1 4 3 0
2 2 2 0 31 0 0 0 0
20 0 0 0
Bordure séparant les motifs rares de ceux fréquents
D
AC
BCE
5
Motif rare
Motif fréquent
ADE
0
AB AEBD DE
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 12 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Motifs raresLe contexte K pour minsupp = 3
{}
BC AD CD BE CE
ABE ABD ACDACE BDE CDEABC
A B C E
ABCD ACDE ABCE ABDE BCDE
ABCDE
Motif rare minimal
BCD
3 4 4 1 4
2 3 2 3 10 1 4 3 0
2 2 2 0 31 0 0 0 0
20 0 0 0
Bordure séparant les motifs rares de ceux fréquents
D
AC
BCE
5
Motif rare
Motif fréquent
ADE
0
AB AEBD DE
“être rare” : contrainte monotone induisant un filtre d’ordreSouad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 12 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Motifs corrélés selon la mesure bondLe contexte K pour minbond = 0,20
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 13 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Motifs corrélés selon la mesure bondLe contexte K pour minbond = 0,20
“être corrélé” : contrainte anti-monotone induisant un idéal d’ordre
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 13 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Motifs corrélés rares
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 14 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Motifs corrélés rares
Ni un idéal d’ordre ni un filtre d’ordre :Extraction plus complexe et plus coûteuse
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 14 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Motifs corrélés rares
Définition
L’ensemble MCR des motifs corrélés rares est défini par :
MCR = {I ⊆ I | Supp(I) < minsupp et bond(I) ≥ minbond}
avec bond (I) =Supp( ∧ I)Supp( ∨ I)
.
Pour minsupp = 4 et minbond = 0,20
Quelques motifs corrélés rares :
(D, 1, 11 ), (AB, 2, 2
5 ), (BCE, 3, 35 ), (ABCE, 2, 2
5 ).
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 15 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Motifs corrélés rares
Définition
L’ensemble MCR des motifs corrélés rares est défini par :
MCR = {I ⊆ I | Supp(I) < minsupp et bond(I) ≥ minbond}
avec bond (I) =Supp( ∧ I)Supp( ∨ I)
.
Pour minsupp = 4 et minbond = 0,20
Quelques motifs corrélés rares :
(D, 1, 11 ), (AB, 2, 2
5 ), (BCE, 3, 35 ), (ABCE, 2, 2
5 ).
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 15 / 36
Plan
1 Introduction
2 Caractérisation de l’ensemble MCR des motifs corrélés rares
3 Nouvelles représentations concises des motifs corrélés rares
4 Évaluation expérimentale
5 Application : Détection d’intrusions
6 Conclusion et perspectives
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
Les classes d’équivalence corrélées rares
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 17 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
Les classes d’équivalence corrélées rares
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 17 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
MMCR versus MFCR
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 18 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
MMCR versus MFCR
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 18 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
MMCR versus MFCR
Tous les éléments d’une classe d’équivalence partagent :
La même fermeture par rapport à la mesure bond.
Les mêmes supports conjonctif, disjonctif, et négatif.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 18 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
Les représentations concises exactes proposées
Définitions
RMCR = MFCR ∪ MMCR.
RMMaxF = max⊆{MFCR} ∪ MMCR.
RMinMF = MFCR ∪ min⊆{MMCR}.
Pour minsupp = 4 et minbond = 0,20
MCR = {A, D, AB, AC, AD, AE, BC, CD, CE, ABC, ABE, ACD, ACE, BCE,ABCE}
RMCR = {A, D, AB, AC, AD, AE, BC, CD, CE, ACD, BCE, ABCE}
RMMaxF = {A, D, AB, AC, AD, AE, BC, CD, CE, ACD, ABCE}
RMinMF = {A, D, AC, AD, BC, CE, ACD, BCE, ABCE}.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 19 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
Les représentations concises exactes proposées
Définitions
RMCR = MFCR ∪ MMCR.
RMMaxF = max⊆{MFCR} ∪ MMCR.
RMinMF = MFCR ∪ min⊆{MMCR}.
Pour minsupp = 4 et minbond = 0,20
MCR = {A, D, AB, AC, AD, AE, BC, CD, CE, ABC, ABE, ACD, ACE, BCE,ABCE}
RMCR = {A, D, AB, AC, AD, AE, BC, CD, CE, ACD, BCE, ABCE}
RMMaxF = {A, D, AB, AC, AD, AE, BC, CD, CE, ACD, ABCE}
RMinMF = {A, D, AC, AD, BC, CE, ACD, BCE, ABCE}.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 19 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
Les représentations concises exactes proposées
Définitions
RMCR = MFCR ∪ MMCR.
RMMaxF = max⊆{MFCR} ∪ MMCR.
RMinMF = MFCR ∪ min⊆{MMCR}.
Pour minsupp = 4 et minbond = 0,20
MCR = {A, D, AB, AC, AD, AE, BC, CD, CE, ABC, ABE, ACD, ACE, BCE,ABCE}
RMCR = {A, D, AB, AC, AD, AE, BC, CD, CE, ACD, BCE, ABCE}
RMMaxF = {A, D, AB, AC, AD, AE, BC, CD, CE, ACD, ABCE}
RMinMF = {A, D, AC, AD, BC, CE, ACD, BCE, ABCE}.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 19 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
Les représentations concises exactes proposées
Définitions
RMCR = MFCR ∪ MMCR.
RMMaxF = max⊆{MFCR} ∪ MMCR.
RMinMF = MFCR ∪ min⊆{MMCR}.
Pour minsupp = 4 et minbond = 0,20
MCR = {A, D, AB, AC, AD, AE, BC, CD, CE, ABC, ABE, ACD, ACE, BCE,ABCE}
RMCR = {A, D, AB, AC, AD, AE, BC, CD, CE, ACD, BCE, ABCE}
RMMaxF = {A, D, AB, AC, AD, AE, BC, CD, CE, ACD, ABCE}
RMinMF = {A, D, AC, AD, BC, CE, ACD, BCE, ABCE}.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 19 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
Les représentations concises exactes proposées
Définitions
RMCR = MFCR ∪ MMCR.
RMMaxF = max⊆{MFCR} ∪ MMCR.
RMinMF = MFCR ∪ min⊆{MMCR}.
Pour minsupp = 4 et minbond = 0,20
MCR = {A, D, AB, AC, AD, AE, BC, CD, CE, ABC, ABE, ACD, ACE, BCE,ABCE}
RMCR = {A, D, AB, AC, AD, AE, BC, CD, CE, ACD, BCE, ABCE}
RMMaxF = {A, D, AB, AC, AD, AE, BC, CD, CE, ACD, ABCE}
RMinMF = {A, D, AC, AD, BC, CE, ACD, BCE, ABCE}.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 19 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
Les représentations concises exactes proposées
Définitions
RMCR = MFCR ∪ MMCR.
RMMaxF = max⊆{MFCR} ∪ MMCR.
RMinMF = MFCR ∪ min⊆{MMCR}.
Pour minsupp = 4 et minbond = 0,20
MCR = {A, D, AB, AC, AD, AE, BC, CD, CE, ABC, ABE, ACD, ACE, BCE,ABCE}
RMCR = {A, D, AB, AC, AD, AE, BC, CD, CE, ACD, BCE, ABCE}
RMMaxF = {A, D, AB, AC, AD, AE, BC, CD, CE, ACD, ABCE}
RMinMF = {A, D, AC, AD, BC, CE, ACD, BCE, ABCE}.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 19 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
Les représentations concises exactes proposées
Définitions
RMCR = MFCR ∪ MMCR.
RMMaxF = max⊆{MFCR} ∪ MMCR.
RMinMF = MFCR ∪ min⊆{MMCR}.
Pour minsupp = 4 et minbond = 0,20
MCR = {A, D, AB, AC, AD, AE, BC, CD, CE, ABC, ABE, ACD, ACE, BCE,ABCE}
RMCR = {A, D, AB, AC, AD, AE, BC, CD, CE, ACD, BCE, ABCE}
RMMaxF = {A, D, AB, AC, AD, AE, BC, CD, CE, ACD, ABCE}
RMinMF = {A, D, AC, AD, BC, CE, ACD, BCE, ABCE}.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 19 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
Les représentations concises exactes proposées
Définitions
RMCR = MFCR ∪ MMCR.
RMMaxF = max⊆{MFCR} ∪ MMCR.
RMinMF = MFCR ∪ min⊆{MMCR}.
Pour minsupp = 4 et minbond = 0,20
MCR = {A, D, AB, AC, AD, AE, BC, CD, CE, ABC, ABE, ACD, ACE, BCE,ABCE}
RMCR = {A, D, AB, AC, AD, AE, BC, CD, CE, ACD, BCE, ABCE}
RMMaxF = {A, D, AB, AC, AD, AE, BC, CD, CE, ACD, ABCE}
RMinMF = {A, D, AC, AD, BC, CE, ACD, BCE, ABCE}.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 19 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
La représentation approximative RMinMMaxF
Définition
RMinMMaxF = max⊆{MFCR} ∪ min⊆{MMCR}
Pour minsupp = 4 et minbond = 0,20
RMinMMaxF = {A, D, BC, CE, ACD, ABCE}.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 20 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
Aperçu des représentations proposées
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 21 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
Aperçu des représentations proposées
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 21 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
Aperçu des représentations proposées
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 21 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
L’algorithme CRPR_MINER
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 22 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
L’algorithme CRPR_MINER
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 22 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
L’algorithme CRPR_MINER
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 22 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
L’algorithme CRPR_MINER
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 22 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
Intérrogation de la représentation RMCR
Exemple :
ACE : Motif corrélé rare? Si oui, dériver son supportconjonctif et sa valeur de la mesure bond.
AE ∈ MMCR et ABCE ∈ MFCR avec AE ⊆ ACE et ACE ⊆ABCE
➥ ACE ∈ MCR
Supp(ACE) = Supp(ABCE) = 2
bond (ACE) = bond (ABCE) =25
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 23 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
Intérrogation de la représentation RMCR
Exemple :
ACE : Motif corrélé rare? Si oui, dériver son supportconjonctif et sa valeur de la mesure bond.
AE ∈ MMCR et ABCE ∈ MFCR avec AE ⊆ ACE et ACE ⊆ABCE
➥ ACE ∈ MCR
Supp(ACE) = Supp(ABCE) = 2
bond (ACE) = bond (ABCE) =25
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 23 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
Régénération de l’ensemble MCRExemple :
Initialement, MCR = RMCR = {(D, 1,11
), (AB, 2,25
), (AD, 1,13
),
(AE, 2,25
), (CD, 1,14
), (ACD, 1,14
), (ABCE, 2,25
)}.
Génération des motifs ABE et ABC compris entre le minimal AB etson fermé ABCE.
Génération du motif ACE compris entre le minimal AE et sonfermé ABCE.
MCR = {(D, 1,11
), (AB, 2,25
), (AD, 1,13
), (AE, 2,25
), (CD, 1,14
),
(ABC, 2,25
), (ABE, 2,25
), (ACD, 1,14
), (ACE, 2,25
), (ABCE, 2,25
)}.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 24 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
Régénération de l’ensemble MCRExemple :
Initialement, MCR = RMCR = {(D, 1,11
), (AB, 2,25
), (AD, 1,13
),
(AE, 2,25
), (CD, 1,14
), (ACD, 1,14
), (ABCE, 2,25
)}.
Génération des motifs ABE et ABC compris entre le minimal AB etson fermé ABCE.
Génération du motif ACE compris entre le minimal AE et sonfermé ABCE.
MCR = {(D, 1,11
), (AB, 2,25
), (AD, 1,13
), (AE, 2,25
), (CD, 1,14
),
(ABC, 2,25
), (ABE, 2,25
), (ACD, 1,14
), (ACE, 2,25
), (ABCE, 2,25
)}.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 24 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
Régénération de l’ensemble MCRExemple :
Initialement, MCR = RMCR = {(D, 1,11
), (AB, 2,25
), (AD, 1,13
),
(AE, 2,25
), (CD, 1,14
), (ACD, 1,14
), (ABCE, 2,25
)}.
Génération des motifs ABE et ABC compris entre le minimal AB etson fermé ABCE.
Génération du motif ACE compris entre le minimal AE et sonfermé ABCE.
MCR = {(D, 1,11
), (AB, 2,25
), (AD, 1,13
), (AE, 2,25
), (CD, 1,14
),
(ABC, 2,25
), (ABE, 2,25
), (ACD, 1,14
), (ACE, 2,25
), (ABCE, 2,25
)}.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 24 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
Régénération de l’ensemble MCRExemple :
Initialement, MCR = RMCR = {(D, 1,11
), (AB, 2,25
), (AD, 1,13
),
(AE, 2,25
), (CD, 1,14
), (ACD, 1,14
), (ABCE, 2,25
)}.
Génération des motifs ABE et ABC compris entre le minimal AB etson fermé ABCE.
Génération du motif ACE compris entre le minimal AE et sonfermé ABCE.
MCR = {(D, 1,11
), (AB, 2,25
), (AD, 1,13
), (AE, 2,25
), (CD, 1,14
),
(ABC, 2,25
), (ABE, 2,25
), (ACD, 1,14
), (ACE, 2,25
), (ABCE, 2,25
)}.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 24 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Les classes d’équivalence corrélées raresLes représentations concises exactes proposéesLa représentation concise approximative proposéeAlgorithme d’extraction des représentations concises
Régénération de l’ensemble MCRExemple :
Initialement, MCR = RMCR = {(D, 1,11
), (AB, 2,25
), (AD, 1,13
),
(AE, 2,25
), (CD, 1,14
), (ACD, 1,14
), (ABCE, 2,25
)}.
Génération des motifs ABE et ABC compris entre le minimal AB etson fermé ABCE.
Génération du motif ACE compris entre le minimal AE et sonfermé ABCE.
MCR = {(D, 1,11
), (AB, 2,25
), (AD, 1,13
), (AE, 2,25
), (CD, 1,14
),
(ABC, 2,25
), (ABE, 2,25
), (ACD, 1,14
), (ACE, 2,25
), (ABCE, 2,25
)}.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 24 / 36
Plan
1 Introduction
2 Caractérisation de l’ensemble MCR des motifs corrélés rares
3 Nouvelles représentations concises des motifs corrélés rares
4 Évaluation expérimentale
5 Application : Détection d’intrusions
6 Conclusion et perspectives
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Variation des cardinalités en fonction de minsupp
1024
2048
4096
8192
16384
32768
65536
131072
0 10 20 30 40 50 60
Nom
bre
de m
otifs
Minsupp (%)
Pumsb* (minbond = 0.5)
MCRRMCR
RMMaxFRMinMF
RMinMMaxF
256 512
1024 2048 4096 8192
16384 32768 65536
131072 262144
10 20 30 40 50 60 70 80 90N
ombr
e de
mot
ifsMinsupp(%)
Accidents (minbond = 0,30)
MCRRMCR
RMMaxFRMinMF
RMinMMaxF
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 26 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Variation des cardinalités en fonction de minbond
1024 2048 4096 8192
16384 32768 65536
131072 262144 524288
40 50 60 70 80 90 100
Nom
bre
de m
otifs
Minbond (%)
Pumsb* (minsupp = 40%)
MCRRMCR
RMMaxFRMinMF
RMinMMaxF
256
1024
4096
16384
65536
262144
1.04858e+006
20 30 40 50 60 70 80 90 100N
ombr
e de
mot
ifs
Minbond (%)
Accidents (minsupp = 50%)
MCRRMCR
RMMaxFRMinMF
RMinMMaxF
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 27 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Temps d’extraction
64
128
256
512
1024
2048
10 20 30 40 50 60 70 80 90
Tem
ps E
xtra
ctio
n (s
ec)
Minsupp(%)
Pumsb (minbond = 0,80)
Tps-RMCRTps-RMMaxF
Tps-RMinMFTps-RMinMMaxF
32
64
128
5 10 15 20 25 30T
emps
Ext
ract
ion
(sec
)Minsupp (%)
T40I10D100K (minbond = 0,10)
Tps-RMCRTps-RMMaxF
Tps-RMinMFTps-RMinMMaxF
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 28 / 36
Plan
1 Introduction
2 Caractérisation de l’ensemble MCR des motifs corrélés rares
3 Nouvelles représentations concises des motifs corrélés rares
4 Évaluation expérimentale
5 Application : Détection d’intrusions
6 Conclusion et perspectives
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Démarche de l’application : Schématisation duprocessus
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 30 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Évaluation expérimentale pour les bases de donnéesDARPA 1998
Figure: Évaluation expérimentale pour les cinq classes d’attaques.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 31 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Évaluation expérimentale
Figure: Comparaison entre les régles génériques corrélées rares declassification et l’approche WIFI MINER.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 32 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Évaluation expérimentale
Figure: Comparaison entre les régles génériques corrélées rares declassification et l’approche WIFI MINER.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 32 / 36
Plan
1 Introduction
2 Caractérisation de l’ensemble MCR des motifs corrélés rares
3 Nouvelles représentations concises des motifs corrélés rares
4 Évaluation expérimentale
5 Application : Détection d’intrusions
6 Conclusion et perspectives
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Conclusion
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 34 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Perspectives
L’optimisation des algorithmes proposés.
L’extraction des formes généralisées des règles d’associationscorrélées rares.
L’extension de l’approche proposée pour les motifs corrélés raresselon d’autres mesures de corrélation.
L’intégration du noyau réalisé dans un système interactif.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 35 / 36
IntroductionCaractérisation de l’ensemble MCR des motifs corrélés rares
Représentations ConcisesÉvaluation expérimentale
Application : Détection d’intrusionsConclusion et perspectives
Merci de votre attention.
Souad B OUASKER Représentations Concises des Motifs Corrélés Rares Mai 2012 36 / 36