View
7
Download
1
Category
Preview:
Citation preview
Analyse de données probabilistes:Treillis de concepts et classification
Paula BritoFac. Economia / LIACC, Univ. Porto, Portugal
avec
Géraldine Polaillon - SUPELEC, France
Francisco de A. T. de Carvalho, CIn - UFPE, Brésil
2
Plan
• Données Probabilistes - Variables Modales• Généralisation• Correspondances de Galois• Classification Hiérarchique / Pyramidale
� Mesures de Généralité• Applications• Conclusion • Perspectives
3
Données Probabilistes
Y = “Type d’emploi”Y = {administration, enseignement, nettoyage }
a1 = [Y~{admin. (30 %), enseignement (70 %)}]a2 = [Y~{ admin. (60 %), ens. (20 %), nett.(20 %)}]
Exemple :
Distributions sur des variables discrètes
4
Distribution de probabilités : données incertaines
Distribution de fréquences : données résultant d’une agrégation
Exemple : Dans une région, 50% des gens sont actifs, 20% sont étudiants, 10% sont à la retraite 20% sont dans une situation“autre”.
Exemple : Il fera “bon” avec probabilité 0.6, “mauvais” avec probabilité 0.4.
Statistiques officellesExpériences répétées
5
1AnglaisMI4
1PortuguaisMI3
1FrançaisFI2
2PortuguaisFI1
nb. enfantsnationalitésexe
1(1/2), 2(1/2)Port(1/2), Fr (1/2)F
1 (1)Port(1/2), Ang (1/2)M
nb. enfantsnationalité
6
GROUPE INSTRUCTION FOOTBALL
Étudiants Pr(0.08), Sec(0.88), Sup(0.03)
oui (0.51), non (0.49),s/rep (0.01)
Retraités Pr(0.92), Sec(0.05), Sup(0.03)
oui (0.12), non (0.88)
Employés Pr(0.59), Sec(0.39), Sup(0.02)
oui (0.22), non (0.78)
Petits Indépendants Pr(0.62), Sec(0.31), Sup(0.07)
oui (0.32), non (0.67), s/rep (0.01)
Femmes au Foyer Pr(0.93), Sec(0.07) oui (0.10), non (0.90)
Cadrres Moyens Pr(0.17), Sec(0.50), Sup(0.33)
oui (0.26), non (0.73), s/rep (0.01)
Ouvriers Industriels Pr(0.73), Sec(0.27), Sup(0.01)
oui (0.40), non (0.60)
Prof. Intellectuels et Scientifiques Sec(0.01), Sup(0.99) oui (0.22), non (0.78)
Autres Pr(0.72), Sec(0.229), Sup(0.07)
oui (0.19), non (0.80), s/rep (0.01)
Directeurs etProfes. Libéraux
Sec(0.02), Sup(0.98) oui (0.28), non (0.70), s/rep (0.02)
Entreprenneurs Pr(0.08), Sec(0.33), Sup(0.58)
oui (0.42), non (0.58)
7
GROUPE INSTRUCTION FOOTBALL
Étudiants Pr, Sec, Sup oui , non , s/rep
Retraités Pr, Sec, Sup oui , non
Employés Pr, Sec, Sup oui , non
Petits Indépendants Pr, Sec, Sup oui , non , s/rep
Femmes au Foyer Pr, Sec oui , non
Cadrres Moyens Pr, Sec, Sup oui , non , s/rep
Ouvriers Industriels Pr, Sec, Sup oui , non
Prof. Intellectuels et Scientifiques Sec, Sup oui , non
Autres Pr, Sec, Sup oui , non , s/rep
Directeurs etProfes. Libéraux
Sec, Sup oui , non , s/rep
Entrepenneurs Pr, Sec, Sup oui , non
8
GROUPE INSTRUCTION FOOTBALL
Étudiants Sec(0.88) oui (0.51)
Retraités Pr(0.92) non (0.88)
Employés Pr(0.59) non (0.78)
Petits Indépendants Pr(0.62) non (0.67)
Femmes au Foyer Pr(0.93) non (0.90)
Cadrres Moyens Sec(0.50) non (0.73)
Ouvriers Industriels Pr(0.73) non (0.60)
Prof. Intellectuels et Scientifiques Sup(0.99) non (0.78)
Autres Pr(0.72) non (0.80)
Directeurs etProfes. Libéraux
Sup(0.98) non (0.70)
Entreprenneurs Sup(0.58) non (0.58)
9
Variables dont les valeurs sont des distributions :“Variables Modales” (Bock, Diday, 2000).
Une variable modale Y de domaine Ydéfinie sur un ensemble E ={ω1, ω2, …}est une variable multi-valuée qui, pour chaque ω de E indique
• un ensemble de modalités Y(ω)• pour chaque m ∈ Y(ω), une fréquence
f(m) ou probabilité p(m) ou un poids.
Quand une distribution empirique est donnée,la variable est appelée variable histogramme.
10
Variable Modale : Définition formelle
Une variable modale Y sur un ensemble
E ={ω1, ω2,…}, de domaine Y = {m1, m2, …, mk}
est une application
Y : E →→→→ M(O)
de E dans la famille M(O) des distributions π sur
Y, avec valeurs Y(ω) = πω:
}{ ))(k(pkm,,))(1(p1mωπ ωω= K
11
Evénement Modal
DÉFINITIONUn événement modal est une expression de la forme
e = [Y(ω) R {m1(p1), m2(p2), …, mk(pk)}]
où Y = {m1, m2, …, mk} est le domaine de Y, et p
lest la probabilité, fréquence ou poids de m
l.
Il n’est pas imposé que p1+ p2+…+ pk= 1.
R est une relation dans l’ensemble des distributions sur Y .
12
Evénement Modal : Relations
On considère les relations suivantes:
ii) “≤” tel que [Y(ω) ≤ {m1(p1),…, mk(pk)}]
est vrai ssi
iii) “≥” tel que [Y(ω) ≥ {m1(p1),…, mk(pk)}]
est vrai ssi
i) “~” tel que [Y(ω) ~ {m1(p1),…, mk(pk)}]
est vrai ssi k,,1,p)(p Klll
==ω
k,,1,p)(p Klll
=≤ω
k,,1,p)(p Klll
=≥ω
13
Objet Modal
Un objet modal est une conjonction d’événementsmodaux.
Chaque élément ω ∈ E est décrit par un objet modal probabiliste:
1)(jkp )(j1pavec
))}(jkp(jkm,)),(j1p(j1m{)(Y)(s
j
jj][ j
p
1j
=ω++ω
ωω∼ω∧=ω=
K
L
14
Extension
][ )}jkp(jkm,),j1p(j1m{R)(Ysjj
jp
1jLω∧=
=
L’extension d’un objet modal
est l’ensemble
}p,,1j,)}jkp(jkm,),j1p(j1m{R)(Y
:E{)s(EExt
jjj KL =ω
∈ω=
15
Relation d’Ordre
Ordre partiel sur S:
Si
alors s1 ≤ s2 ssi pl j ≤ q
l j , l =1,…,kj, j=1,..., p.
[ ])}q(m,),q(m{RYs jkjkj1j1j
p
1j2 jj
L∧=
=
Soit S l’ensemble de tous les objets modauxdéfinis sur les variables Y1, ... , Yp.
[ ])}p(m,),p(m{RYs jkjkj1j1j
p
1j1 jj
L∧=
=
16
Généralisation
s est plus général que s’ si son extension contient l’extension de s’s’ est plus spécifique que s
Généraliser deux objets s et s’ : determiner s’’ tel que
s’’ est plus général que s et s’.
Ext (s ∪ s’) ⊇ Ext (s) et Ext (s ∪ s’) ⊇ Ext (s’)
17
Généralisation : variables modales
Deux méthodes sont considérées :
Prendre pour chaque modalité le minimumde ses fréquences
Prendre pour chaque modalité le maximumde ses fréquences
18
Genéralisation par le Maximum
[couleur ∼ ∼ ∼ ∼ { rouge (30 %), orange (70 %)}] ∪∪∪∪∪∪∪∪ [couleur ∼∼∼∼{ rouge (60 %), orange (20 %), jaune (20 %)}] =
[couleur ≤≤≤≤ { rouge (60 %), orange (70 %), jaune (20 %)}]
Exemple :
Extension : k} , 1,= , p )( p : E { …≤ω∈ω ll
principe “au plus”
= ] } )(pm , ,)(pm R [Y ] } )(pm , ,)(pm R [Y qkk
q11
1kk
111 …………{{{{∪∪∪∪∪∪∪∪…………{{{{ K
] } )(pm , ,)(pm R[Y kk11 …………{{{{
{{{{ }}}}qj
1jj p, , pMax p K====avec
{{{{ }}}}≤≤≤≤∈∈∈∈ ,~RSoit
19
Genéralisation par le Minimum
[couleur ∼ ∼ ∼ ∼ { rouge (30 %), orange (70 %)}] ∪∪∪∪∪∪∪∪ [couleur ∼∼∼∼{ rouge (60 %), orange (20 %), jaune (20 %)}] =
[couleur ≥≥≥≥ { rouge (30 %), orange (20 %)}]
Exemple :
Extension : k} , 1,= , p )( p : E { …≥ω∈ω ll
principe “au moins”
= ] } )(pm , ,)(pm R [Y ] } )(pm , ,)(pm R [Y qkk
q11
1kk
111 …………{{{{∪∪∪∪∪∪∪∪…………{{{{ K
] } )(pm , ,)(pm R[Y kk11 …………{{{{
{{{{ }}}}qj
1jj p, , p Min p K====avec
{{{{ }}}}≥≥≥≥∈∈∈∈ ,~RSoit
20
Correspondances de GaloisSoient (A, ≤≤≤≤1 ) e (B, ≤≤≤≤2 ) des ensembles ordonnés.Une correspondance de Galois est une paire (f,g)
f : A →→→→ B, g : B →→→→ A, telles que
f et g sont monotones décroissantes, h = f o g et h’ = g o f sont extensives.
Formellement :
x ≤1 x1 ⇒ f(x) ≥2 f(x1), ∀ x, x1 ∈ A
y ≤2 y1 ⇒ g(y) ≥1 g(y1) ,∀ y, y1 ∈ B
x ≤1 g (f (x) ) ∀ x ∈ A ∧ y ≤2 f (g(y) ) ∀ y ∈ B
h e h’ sont des opérateurs de fermeture, dénomés “fermetures de Galois”.
21
Correspondances de Galois - 1THÉORÈME 1
Soientfu : S →→→→ P(E)
s →→→→ ExtE s = { ωωωω ∈∈∈∈ E : s(ωωωω) ≤≤≤≤ s }
gu : P(E) →→→→ S
{ ωωωω1, … , ωωωωm } →→→→
avec
][ )}t(m,),t(m{Ys jkjkj1j1j
p
1j jjL≤= ∧
=
p,1,j,k,1,m},1,i),(ωp{j jijMaxt LKlKl l ====
22
Correspondances de Galois - 1
(fu,gu) forment une correspondance de Galois entre (P(E) , ⊆) et (S , ≥).
h = gu o fu : S → S
est anti-extensive, monotone et idempotente.
h’ = fu o gu : P(E) → P(E)
est un opérateur de fermeture,
i.e. est extensive, monotone et idempotente.
23
Exemple
Soit A = {ω 1, ω 2}gu (A) =
fu (gu (A)) = {ω 1, ω 2}
Sexe Instruction
ω 1 Masc.(0.4), Fem.(0.6) Prim.(0.3), Sec.(0.4), Sup.(0.3)
ω 2 Masc.(0.1), Fem.(0.9) Prim.(0.1), Sec.(0.2), Sup.(0.7)
ω 3 Masc.(0.8), Fem.(0.2) Prim.(0.2), Sec.(0.3), Sup.(0.5)
ω 4 Masc.(0.5), Fem.(0.5) Prim.(0.3), Sec.(0.2), Sup.(0.5)
{ }[ ]
{ }[ ]Sup.(0.7)(0.4),Sec.,Prim.(0.3)nInstructio
.(0.9)Fem(0.4),Masc.Sexe
≤∧
∧≤
24
Correspondances de Galois - 2THÉORÈME 2
Soientfi : S →→→→ P(E)
s →→→→ ExtE s = { ωωωω ∈∈∈∈ E : s(ωωωω) ≥≥≥≥ s }
gi : P(E) →→→→ S
{ ωωωω1, … , ωωωωm } →→→→
avec
≥∧=
=
}{ )t(m,),t(mYs jkjkj1j1jp
1j jjL
p,1,j,k,1,m},1,i),(ωp{j jijMint LKlKl l ====
25
Correspondances de Galois - 2
( fi , gi) forment une correspondance de Galois entre (P(E) , ⊆ ) et (S, ≤).
h = gi o fi : S → S
sont des opérateurs de fermeture,
i.e. sont extensives, monotones et idempotentes.
eth’ = fi o gi : P(E) → P(E)
26
Exemple
Soit B = {ω 2, ω 3}.
gi (B) =
fi (gi (B)) = {ω 2, ω 3, ω 4}
Sexe Instruction
ω 1 Masc.(0.4), Fem.(0.6) Prim.(0.3), Sec.(0.4), Sup.(0.3)
ω 2 Masc.(0.1), Fem.(0.9) Prim.(0.1), Sec.(0.2), Sup.(0.7)
ω 3 Masc.(0.8), Fem.(0.2) Prim.(0.2), Sec.(0.3), Sup.(0.5)
ω 4 Masc.(0.5), Fem.(0.5) Prim.(0.3), Sec.(0.2), Sup.(0.5)
{ }[ ]
{ }[ ]Sup.(0.5)(0.2),Sec.,Prim.(0.1)nInstructio
.(0.2)Fem(0.1),Masc.Sexe
≥∧
∧≥
27
Objet complet, Concept
DÉFINITION
Un objet modal s est complet si h(s) = s.
i. e. intention ( extension (s)) = s
DÉFINITION
Un concept est une paire (A , s), où A ⊆ E, s ∈ S, s est complet et A = f(s).
(ensemble, description)
28
THÉORÈME 3
Soit (fu,gu) la correspondance de Galois du théorème 1.
Si et
on définit
s1 ∪ s2 =
avec
et s1 ∩ s2 =avec
= ∧=
)r(m,),r(m~Ys jkjkj1j1jp
1j1
jjL
= ∧=
)q(m,),q(m~Ys jkjkj1j1jp
1j2
jjL
≤∧=
)t(m,),t(mY jkjkj1j1jp
1j jjL
≤∧=
)z(m,),z(mY jkjkj1j1jp
1j jjL
p 1,...,j ,k,1, },q ,{rMax t jjjj =…== llll
p 1,...,j ,k,1, },q ,{rMin z jjjj =…== llll
29
L’ensemble des concepts, ordonnés par
(A1 , s1) ≤ (A2 , s2) ⇔ A1 ⊆ A2
est un treillis, avec :
inf ( ( A1, s1 ), ( A2 , s2 ) ) = ( A1 ∩∩∩∩ A2 , (gu o fu) ( s1 ∩∩∩∩ s2 ))
sup (( A1, s1 ), ( A2 , s2 ) ) = ( (fu o gu) (A1 ∪∪∪∪ A2) , s1 ∪∪∪∪ s2 )
Ce treillis est appellé “treillis de l’union”.
30
THÉORÈME 4
Soit (fi,gi) la correspondance de Galois du théorème 2.
Si et
on définit
avec
etavec
= ∧=
)r(m,),r(m~Ys jkjkj1j1jp
1j1
jjL
= ∧=
)q(m,),q(m~Ys jkjkj1j1jp
1j2
jjL
p 1,...,j ,k,1, },q ,{rMin t jjjj =…== llll
p 1,...,j ,k,1, },q ,{rMax z jjjj =…== llll
≥∧=∪
=
)t(m,),t(mYss jkjkj1j1jp
1j21
jjL
≥∧=∩
=
)z(m,),z(mYss jkjkj1j1jp
1j21
jjL
31
L’ensemble des concepts, ordonnés par
(A1 , s1) ≤ (A2 , s2) ⇔ A1 ⊆ A2
est un treillis, avec :
inf ( ( A1, s1 ), ( A2 , s2 ) ) = ( A1 ∩∩∩∩ A2 , (gi o fi) ( s1∩∩∩∩ s2 ))
sup (( A1, s1 ), ( A2 , s2 ) ) = ( (fi o gi) (A1 ∪∪∪∪ A2) , s1 ∪∪∪∪ s2 )
Ce treillis est appellé “treillis de l’intersection”.
32
Enquête CultureTreillis de l’intersection
33
Exemple de concept
c22 = ( {cadres moyens, autres, entreprenneurs,}, s22)
avec
s22 = [Instruction ≥ {sec. (0.22), sup. (0.07)}] ^[Football ≥ {non (0.58), oui (0.19)}]
Enquête Culture
Treillis de l’intersection
34
Classification
Objectif :
Classification ascendante
– hiérarchique, pyramidale –
telle que chaque classe formée soit un concept du
treillis.
Détermine un sous-ensemble du treillis.
35
Algorithme
• p1, ... ,pr sont agrégeables (selon la structure choisie)
• p = p1 ∪∪∪∪ ... ∪∪∪∪ pr
• s généralise s1 , ... , sr
• s complet
• ExtE s = p
Partant des concepts associés aux singletons
( {ωωωωi} , ai ), i=1,...,nÀ chaque étape, et jusqu’à la formation de (E, sE),former un concept (p , s) agrégeant (p1 , s1), ... , (pr , sr):
Soient E = {ωωωω1 , ... , ωωωωn} l’ensemble à classifierai = s(ωωωωi), i=1,...,n
36
Algorithme
Non - unicité Þ critère numérique
Former d’abord les classes associés auxobjets moins généraux –Concepts “plus bas” dans le treillis
Mesure compatible avec la généralisation.
Degré de géneralité
37
Mesures de Généralité - 1
∏∏∏∏====∑∑∑∑∏∏∏∏================
p
1jj1
k
1j
p
1j j1 )e(Gp
k1
)s(Gj
l
l
coefficient d’affinité (Matusita, 1951) entre
(p1j,…,pkj) et la distribution uniforme (1/kj, …, 1/kj)
a) Si - Généralisation par le Maximum{{{{ }}}}≤≤≤≤∈∈∈∈ ,~R
∑∑∑∑====
====j
j
k
jj11
pk1
)(eGl
l est le
38
Mesures de Généralité - 1
On considère un objet d’autant plus général que les distributions associéessont proches de la distribution uniforme.
Si
G1(ej) est maximal (=1) quand
pllllj = 1/kj, llll =1,…kj , i=1,…k : distrib. uniforme
G1(ej) est minimal quand la distribution est
dégénérée.
1pp jk1j j====++++++++K
39
Mesures de Généralité - 2
∏∏∏∏====∑∑∑∑ −−−−∏∏∏∏−−−−
================
p
1jj2
k
1j
p
1j jj2 )e(G)p1(
)1k(k1
)s(Gj
l
l
Si , G2(ej) est maximal (=1)quand p
llllj = 1/kj, llll =1,…kj : distrib. Uniforme.
Minimal quand la distribution est dégénérée.
b) Si - Généralisation par le Minimum{{{{ }}}}≥≥≥≥∈∈∈∈ ,~R
1pp jk1j j====++++++++K
40
Mesures de Généralité
G1 et G2 sont compatibles avec la généralisation :
Dans chaque cas ,
)}2s(G),1s(G{Max)2s1s(G ≥≥≥≥∪∪∪∪
41
Algorithme
• p1, ... ,pr sont agrégeables (selon la structure choisie)
• p = p1 ∪∪∪∪ ... ∪∪∪∪ pr
• s = s1 ∪∪∪∪ ... ∪∪∪∪ sr (Max ou Min)
• s complet
• ExtE s = p
• G (s) Min
Partant des concepts associés aux singletons
({ ωωωωi} , ai ), i = 1,…,n
À chaque étape, et jusqu’à la formation de (E, sE), formerun concept (p , s) agrégeant (p1 , s1), ... , (pr , sr) tels que :
42
ExempleTinnitus Maux de tête Pression
Nom Fréq. Rare Fréq. Rare Haute Normale Basse
Ann 0.8 0.2 0.9 0.1 0.8 0.2 0.0
Bob 1.0 0.0 0.0 1.0 0.6 0.4 0.0
Chris 1.0 0.0 0.1 0.9 0.9 0.1 0.0
Doug 0.3 0.7 0.7 0.3 0.0 0.6 0.4
Eve 0.6 0.4 0.7 0.3 0.0 0.8 0.2
(Herrmann, Hölldobler, Strohmaier (1996))
43
Treillis de l’union
44
Comparaison(Herrmann, Hölldobler, Strohmaier (1996))
c : {{Ann, Bob, Chris}{Tinnitus (Fréq.), Pression (Haute),αααα=0.85, σσσσ=0.11}
Du treillis de l’intersection:
a7 i = [Tinnitus ≥≥≥≥ {Fréq. ((((0.8), Rare((((0.0)}] ^[Pression ≥≥≥≥ {Haute ((((0.6), Normale (0.1), Basse ((((0.0)}]
Ext (a7 i) = {Ann, Bob, Chris}
Du treillis de l’union :
a7u = [Tinnitus ≤≤≤≤ {Fréq. ((((1.0), Rare ((((0.2)}] ^ [Pression ≤≤≤≤ {Haute ((((0.9), Normale (0.4), Basse ((((0.0)}]
Ext (a7 u) = {Ann, Bob, Chris}
45
HiérarchieGénéralisation par le Maximum
46
PyramideGénéralisation par le Maximum
47
Exemple - comparaison
Comme prévu, la hiérarchie est contenue dans la pyramide, qui est elle-même une partie du treillis.
Le nombre de concepts formés a été réduit de 31, dans le treillis, à 15 dans la pyramide etseulement 9 dans la hiérarchie.
48
Exemple - comparaison
L'ordre induit par par pyramide,
Bob-Chris-Anne-Eve-Doug
semble traduire une importance décroissante du symptome Tinnitus - fréquent.
La pyramide permet la formation de concepts qui ne sont pas présents dans la hiérarchie.
Par exemple le concept ((Anne, Eve), s3) avec
s3 = [Tinnitus ≤≤≤≤ {Fréq. ((((0.8), Rare ((((0.4)}] ∧∧∧∧[Maux de Tête ≤≤≤≤ {Fréq. ((((0.9), Rare (0.3)} ∧∧∧∧[Pression ≤≤≤≤ {Haute ((((0.8), Normale (0.8), Basse ((((0.2)}]
49
Conclusion
� Résultats permettant de construire deux treillis de Galois sur des données modales.
� Permet d'organiser les données modales directement, sans besoin d’une transformation préalable.
� L'application pratique reste limitée par la tailledes treillis obtenus:
� le nombre de concepts tend à augmenterexponentiellement avec le nombre d'individus et de variables.
50
Conclusion�Alternative : limiter le nombre de concepts formés,en imposant un modèle de classification plus simple.
� Méthode de classification est proposée, modèles hiérarchique ou pyramidale.
�Construit une hiérarchie ou une pyramide : chaque classe est un concept du treillis correspondant
�Permet d'ordonner les concepts par le degré degénéralité de leurs intentions
� mesuré par l'affinité des distributions associées avec la distribution uniforme.
51
Perspectives
� Variables modales ordinales
� utiliser la fonction de répartition ?
(Diday, Emilion, 2004)
� Autres mesures de généralité ?
� Comparaison des classification directes avec
les classifications extraites du treillis
(Polaillon 2000).
� Critères de simplification du treillis.
Recommended