Architectures Multi-agents combinant diffrentes techniques dapprentissage et de

mta apprentissage pour la classification des stades de sommeil

Khaoula Youssef, Lilia Rejeb, Ridha Ben Cheikh, Mohamed Hdi Bedoui
LaboratoireTechnologie et Imagerie Mdicale, LTIM-LR12ES06
Facult de Mdecine de Monastir, Universit de Monastir, 5019 Monastir, Tunisie.
[email protected],
[email protected]
[email protected]
[email protected]
RESUME
Nous proposons dutiliser dans ce travail les systmes multi-agents apprenants pour classifier les stades de sommeil travers
lanalyse du signal EEG (Electro-encphalogramme). Nous comparons dans ce travail deux architectures de systmes multiagents qui diffrent dune part par la technique dapprentissage utilise. Nous avons utilis dans ce cadre les systmes de
classifieurs apprenants XCS et UCS. Ces architectures diffrent aussi par les algorithmes utiliss pour modliser linteraction
entre ces agents et qui sont inspirs des techniques de mta-apprentissage (Adaboost-M1, Bagging). Le systme a atteint un
taux de classifications correctes de 98%. Larchitecture obtenue est flexible et peut tre analyse a posteriori par les experts
ou encore tendue dautres signaux.
MOTS CLES
Apprentissage, Mta-apprentissage, Systmes multi-agents, Classification, EEG.

1. Introduction
Le sommeil est une fonction vitale qui permet la reconstruction de l'nergie de l'tre humain. Cependant, il peut prsenter des
anomalies qui vont retentir sur la vie diurne. Parmi ces anomalies nous citons l'insomnie, SAOS (syndrome dapnes
obstructives du sommeil), .la narcolepsie, etc... Pour diagnostiquer ces pathologies, il faut tudier les paramtres de la
polysomnographie. Nous nous intressons l'hypnogramme qui prsente le nombre et la structure de chaque cycle du
sommeil en exposant les principaux signaux physiologiques tels que EEG (Electro-encphalogramme), EMG (Electromyogramme), EOG (Electro-occulogramme), etc.. Nous nous sommes focaliss dans notre tude sur la drivation C3-A2 du
trac EEG en se basant sur le travail de Susmakova et al [10].
Plusieurs mthodes ont t proposes pour la classification des signaux EEG telles que les rseaux de neurones, SVM etc.
[ 6]. Les rseaux de neurones ont de bons rsultats mais ne fournissent pas toujours des rgles exploitables par un expert. Le
rseau reste souvent une bote noire qui fournit une rponse quand on lui prsente une donne, mais il ne fournit pas de
justification facile interprter a postriori. Ainsi, nous proposons d'utiliser les systmes de classifieurs apprenants qui
reprsentent la connaissance sous forme de rgles explicites. Pour enrichir la base par des rgles utiles, le systme utilise une
composante d'volution et une autre d'valuation afin de maximiser la capacit de gnralisation. Les systmes de classifieurs
ont t appliqus dans plusieurs domaines tels que la classification des patients schizophrniques [9], la classification des
patients atteints par la dyslexie [ 8]. Ce sont gnralement des problmes bi-classes. Parmi les types de systmes de
classifieurs, nous distinguons ZCS (Zeroth Classifier System), ACS (Anticipated Classifier System), mais aussi XCS
(eXtended Classifier System) que nous avons adopt dans notre tude vu sa capacit de gnralisation et sa robustesse. XCS
utilise un mode d'apprentissage par renforcement. Ce dernier ncessite une grande base d'apprentissage pour former une
cartographie complte de l'environnement et converger vers une base de connaissances stable. Nous avons choisi galement
UCS (sUpervised Classifier System) qui se base sur l'apprentissage supervis pour former la meilleure cartographie en
explorant que des rgles correctes et consistantes.

Nous encapsulons ces systmes de classifieurs apprenants dans des agents et combinons leur apprentissage et lexploitation
de ses rsultats par un systme multi-agents. Plusieurs architectures qui diffrent par la technique dapprentissage quutilisent
les agents pour leur prise de dcision ainsi que la technique travers laquelle ces agents interagissent sont proposes. Pour
ceci, nous nous sommes inspirs de la technique Adaboost-M1 et le Bagging. Il nexiste pas notre connaissance
darchitecture proposant la combinaison des systmes de classifieurs apprenants avec les deux techniques sus-mentionnes.
Larchitecture propose est flexible et permet aux experts danalyser a postriori les rsultats de lapprentissage.
Cet article est organis comme suit. La section 2 introduit les stades de sommeil. La troisime section prsente les diffrentes
composantes de larchitecture multi-agents. La quatrime section prsente les principaux rsultats et nous terminons par une
conclusion o sont rsums les principaux apports de ce travail.

2. Les stades de sommeil

Le signal EEG est une mesure continue du potentiel lectrique produit par le cerveau. Il permet la discrimination des
tats de sommeil. Le signal EEG est dcoup en portions de 30 secondes. Pour chaque portion, nous dterminons le spectre
de frquence dans lintervalle [0.5,32Hz] en utilisant la technique de la Transforme de Fourrier Rapide. Nous calculons la
puissance spectrale relative PSRi :1..32 dans ce spectre. Nous obtenons 32 valeurs partir desquelles 5 bandes de
frquences sont extraites : delta [0.5-4Hz[, theta [4-8Hz[, alpha [8-12Hz[, sigma [12-16Hz[, bta [16-32Hz[ (voir figure 1).

Figure 1. Reprsentation des bandes spectrales issues de l EEG

Ces bandes de frquences permettent dextraire six classes de stades de sommeil : Eveil (Awa), stade de sommeil 1 St1,
deuxime stade de sommeil St2, St3, St4 et REM qui ressemble au stade 1 et est nomm sommeil paradoxal.

3. Description de larchitecture multi-agents

Nous proposons une architecture multi-agents [3] (voir figure 2) o les agents apprenants utilisent pour leur prise de dcision
des systmes de classifieurs apprenants XCS et UCS bass, respectivement, sur des techniques dapprentissage par
renforcement et dapprentissage supervis. Les interactions se font travers un agent manager qui gre dune part
laffectation des bases dapprentissage aux agents apprenants et est responsable aussi de lagrgation de leurs avis en phase
de test pour en dduire le meilleur classement. Les sections suivantes nous permettent de dcrire ces diffrentes composantes.

Figure 2. Architecture gnrale du SMA

3.1. Les agents XCS et UCS

Les connaissances dans ces systmes sont reprsentes par des classifieurs correspondant des rgles de type conditionaction o condition reprsente dans notre cas les bandes de frquence et laction correspond au stade de sommeil dtect.
Chaque classifieur est galement caractris par un ensemble de paramtres tel que la prdiction, lerreur de prdiction et la
mesure de la fitness qui indique la qualit du classifieur. Nous avons adopt la reprsentation en nombre rels pour les
lments composant le classifieur. La population de ces classifieurs est initialement vide. Elle est construite graduellement
par lactivation du systme de classifieurs. La table 1 prsente un exemple dun classifieur XCS.
Composantes dun classifieur

Exemple de valeurs

Condition

[0.637,0.99][0.0,0.20][0.0,0.59][0.0,0.601][0.0,0.19]

Action

Prdiction

0.18444313

Erreur de prdiction

0.1

Fitness

0.16778173

Exprience

620

Numrosit

9
Table 1. Exemple dun classifieur XCS

3.1.1. Fonctionnement de XCS

XCS [11] est utilis comme processus de dcision de lagent apprenant. Il est compos dune population de classifieurs,
dune technique dapprentissage par renforcement (le Q-learning) pour leur valuation et dun algorithme gntique pour leur
volution. Cest un systme de classifieur apprenant bas sur la prcision des prdictions.
Il fonctionne comme suit. Pour chaque portion du signal en entre, XCS construit [M] lensemble des classifieurs apparis
au signal. Si le nombre de classifieurs dans [M] ne dpasse pas un seuil donn, le recouvrement consistant crer de nouveau
classifieurs ayant comme condition les paramtres du signal en entre et dont laction est choisie alatoirement. Pour chaque
action dans [M], une prdiction moyenne est calcule. Elle inclut tous les classifieurs proposant cette action. Le choix entre
les actions est ralis soit par exploration (choix alatoire) ou par exploitation (choix de laction ayant la meilleure moyenne
de prdiction). Une fois quune action est choisie, elle est applique et son application engendre une rcompense qui sera
utilise par la suite pour mettre jour les paramtres dans lensemble [A] contenant les classifieurs proposant laction choisie.
Lalgorithme gntique est appliqu dans certaines tapes sous certaines conditions pour amliorer lensemble [A].
3.1.2. Fonctionnement de UCS
UCS [7] est un systme de classifieurs apprenant bas sur la prcision. Il est inspir de XCS mais explore uniquement les
classes correctes. Il se base sur lapprentissage supervis. A chaque tape, un signal est prsent avec ltiquette de la classe
correspondante c. Le systme cre lensemble [C] qui est constitu de classifieurs similaires lentre par leurs conditions et
qui proposent la classe c. Si [C] est vide une opration de recouvrement est ralise en crant un classifieur avec les
paramtres du signal en entre et laction c. La prcision est calcule dune manire diffrente de XCS. Elle est considre
dans UCS, comme le pourcentage des prdictions correctes de la rgle considre au lieu de la calculer partir de lerreur de
prdiction. Lalgorithme gntique est par la suite appliqu dans [C]. Le schma de fonctionnement de UCS est prsent dans
la figure 3.

Figure 3. Fonctionnement de UCS

3.2. Lagent Manager
Les agents XCS ou UCS sont coordonns par un agent Manager qui se charge dune part de rpartir les signaux aux
diffrents agents pour leur apprentissage. Il se charge, dautre part, de combiner les propositions des diffrents agents en
phases de test travers une technique de mta-apprentissage : Bagging ou Adaboost-M1. Ces deux algorithmes diffrent par
la gnration des sous-ensembles dapprentissage pour les agents et par leur activation.
3.2.1. Le Bagging
Le comportement de lagent Manager sinspirant du bagging est comme suit. Lagent construit pour chaque agent
apprenant un sous-ensemble dapprentissage de signaux EEG. Ces sous-ensembles sont gnrs par bootstrap, c'est--dire,
par un chantillonnage avec un tirage avec replacement de m instances partir de lensemble initial dapprentissage. Chaque
agent utilise le sous-ensemble, ainsi dtermin, pour apprendre indpendamment des autres. Pour chaque portion de signal
prsente en test, le manager envoie le signal chaque agent qui retourne un tat de sommeil Ci. La classe finale est dfinie
partir des Ci , C2 , , Ct propositions travers un vote majoritaire [1]. Le renforcement des classifieurs de tous les agents est
ensuite effectu en fonction de laction choisie.
3.2.2. Le Adaboost-M1
Lagent Manager sinspire ici de lalgorithme e Adaboost-M1 [4] qui est adopt pour les problmes multi-classes. Les
agents agissent ici dune manire squentielle. Lagent Manager construit pour chacun deux un sous-ensemble
dapprentissage en se basant sur lerreur effectue par les agents prcdents. Cette erreur est utilise pour mettre jour les
poids pour chaque entre dans lensemble dapprentissage. La slection du sous-ensemble dapprentissage pour lagent
suivant est faite partir de lensemble dapprentissage initial selon le poids des classifieurs. La combinaison des actions
proposes par chaque agent apprenant pour une entre de test est ralise par un vote majoritaire.

4. Exprimentations
Le systme a t dvelopp avec la plateforme multi-agents DIMA [5]. Nous prsenterons en premier lieu le protocole
dexprimentation avant de passer aux rsultats.
4.1. Protocole dexprimentation
Les rsultats exposs dans la section suivante sont obtenus partir d'une base de 4869 mesures. Ces mesures sont issues de
neuf sujets dont la tranche d'ge varie de 20 35 ans. Ces entres ont t analyses et tiquetes par un expert. Lensemble
dapprentissage contient en proportions gales les diffrentes classes de sommeil (500 entres pour chaque classe pour la
phase dapprentissage et le reste des entres pour le test). .Nous avons test plusieurs combinaisons de reprsentations des
conditions des signaux : 32 valeurs de frquences ou les 5 bandes de frquence. Nous avons fait aussi des exprimentations
avec 3 (veil, orthodoxe, paradoxal), 4 (veil, lger, non paradoxal, paradoxal) et 6 (veil, stade 1, 2, 3, 4 et paradoxal)
classes de sommeil respectivement.
XCS et UCS ont les mmes paramtres initiaux tels que la taille de la population (6400), la probabilit dexploration (0.8), la
probabilit dactivation de lalgorithme gntique (0.25). Les rsultats prsents sont les moyennes obtenues partir de
plusieurs exprimentations. Nous nous limitons dans le cadre de ce papier la prsentation des taux de russite et lanalyse
des matrices de confusion.

4.2. Rsultats
Nous avons appliqu dabord XCS et UCS sans les intgrer dans larchitecture multi-agent. Les rsultats de la table 2
correspondent au taux de classifications correctes en mode de test pour les diffrentes combinaisons des rpartitions des
stades du sommeil et le nombre de paramtres dans une condition du classifieur. Les rsultats montrent que XCS est meilleur
que UCS dans la majorit des cas et que plus la reprsentation de la condition est prcise (32 paramtres) plus le pourcentage
est meilleur. Ceci peut tre expliqu par la nature non-stationnaire de lenvironnement. De plus, la taille de lensemble initial
dapprentissage peut permettre XCS dapprendre correctement mais peut tre une cause de sur-apprentissage pour UCS.
XCS permet aussi lexploration des classifieurs corrects et incorrects.

Nombre des paramtres en

entre/ /nombre de classes
XCS
UCS

5/3

5/4

5/6

32/3

32/4

32/6

0.82
0.72

0.55
0.72

0.59
0.41

0.82
0.79

0.73
0.66

0.65
0.51

Table 2. Taux de classification de UCS et XCS

Nous allons analyser les matrices de confusion en mode test relatives aux cas 32/3 et 32/6 respectivement pour XCS et UCS.
UCS

Eveil

Ortho

Sommeil
paradoxal
187
33
511

Eveil
1164
182
Ortho
140
2285
Sommeil
252
66
paradaoxal
Table 3. Matrice de confusion de UCS avec le mode 32/3
UCS

Eveil

ST1

ST2

ST3

ST4

Sommeil
paradoxal
42
109
22
1
1
211

Eveil
92
47
52
3
10
ST1
6
90
16
40
2
ST2
1
10
143 117 7
ST3
0
2
60
135 43
ST4
0
0
17
63
193
Sommeil
9
24
16
30
1
paradaoxal
Table 5. Matrice de confusion de UCS avec le mode 32/6

XCS

Eveil

Ortho

Sommeil
paradoxal
107
18
266

Eveil
1194
232
Ortho
115
2325
Sommeil
431
132
paradaoxal
Table 4. Matrice de confusion de XCS avec le mode 32/3
XCS

Eveil

ST1

ST2

ST3

ST4

Sommeil
paradoxal
63
158
25
2
1
246

Eveil
60
72
50
0
0
ST1
6
52
45
2
0
ST2
1
17
253 3
1
ST3
0
4
179 50
6
ST4
2
0
56
93
123
Sommeil
4
17
23
1
0
paradaoxal
Table 6. Matrice de confusion de XCS avec le mode 32/6

En considrant les tables 3 et 4, nous remarquons quil y a principalement une confusion entre la REM ou sommeil paradoxal
et la veille. Ceci peut tre expliqu par la similarit de lactivit crbrale du stade de veille et le stade paradoxal surtout en
bandes alpha. Nous remarquons aussi daprs la table 4 que la confusion entre veil et sommeil orthodoxe est plus vidente
dans XCS que dans UCS, tant donn que XCS forme une cartographie complte et a besoin donc dune grande base
dapprentissage.
Nous remarquons au niveau de la table 5 une confusion entre les trois premiers stades de sommeil: le TP (taux de bonnes
dtections) du stade 1 est trs bas et il y a une confusion claire entre ST3 et ST2 qui peut tre amliore par la dtection des
spindles. La confusion existe aussi entre ST3 et (ST4-St2) vu que les trois phases contiennent la bande lambda et que thta
est prsente que ce soit dans ST3 et ST2. En paradoxal le TP est moyen ne pouvant tre amlior que par l'utilisation du
signal EMG.
Au niveau de XCS la confusion est entre St2 et St3 mais avec un TP plus faible que celui d'UCS (voire table 6). La
confusion dans la discrimination de l'tat St1, qui est un tat transitoire entre veil et St2, est lie l'absence des ondes
pointues de vertex qui sont actives ce stade et qui n'ont pas t prises en compte lors de notre tude.
La confusion dans la dtermination de l'tat St2 est relative la ngligence des fuseaux de sommeil et les complexes K
donnant une indication pertinente pour la distinction de ce stade. Ces mmes indicateurs sont prsents en (ST3-St4) qui est le
sommeil non paradoxal et ils peuvent amliorer les TP de ces deux stades. En sommeil paradoxal, nous notons la prsence
des ondes en dents de scie et un changement du tonus musculaire qui permettent de discriminer (veil-St1) de sommeil
paradoxal. Il faut noter aussi que l'activit crbrale en sommeil paradoxal et (Eveil-St1) est trs similaire tant donn que le
sommeil paradoxal o l'tre humain est endormi tandis que son cerveau est en pleine activit comme en veille.
Nous prsentons maintenant les rsultats de larchitecture du systme multi-agents combinant respectivement les agents bass
sur XCS et UCS avec les techniques de bagging and boosting. Le nombre dagents apprenants est gal 20.

Taux de classifications
correctes
Bagging+UCS
Bagging + XCS
ADABOOSTM1+UCS
ADABOOSTM1+XCS

5/3

5/4

5/6

32/3

32/4

32/6

1
0.45
0.78
0.36

0.89
0.33
0.69
0.17

0.83
0.17
0.54
0.16

1
0.4
0.78
0.36

0.99
0.33
0.68
0.2

1
0.18
0.59
0.15

Table 7. Taux de classification avec les architectures multi-agents

Daprs la table 7, nous remarquons que les meilleurs taux correspondent l'association UCS avec la mthode base sur le
bagging et que les rsultats se dgradent avec XCS bien que les mmes conditions d'excution aient t fournies. Les
performances de ce systme peuvent tre amliores par lagrandissement de la base dapprentissage propose XCS.
En effet, le systme multi-agent base de XCS a pu atteindre au maximum 46%, tandis que nous avons pu atteindre 100%
avec un systme multi-agent base d'UCS. Il est clair aussi que le bagging fournit toujours les meilleurs rsultats. Nous
pouvons rfrer cette dgradation pour le boosting au bruit de l'ensemble d'apprentissage [2].

5. Conclusion
Nous avons propos dans ce travail une architecture multi-agents intgrant les systmes de classifieurs apprenants et les
techniques de mta-apprentissage tel que le bagging et le boosting. Nous avons dmontr que pour la classification de
signaux non stationnaires, la combinaison de lapprentissage supervis UCS avec le bagging tait la meilleure. Larchitecture
propose est flexible et permet lintgration, facilement, dautres signaux ou encore dautres types dagents. Elle permet
galement lanalyse a postriori de la base de connaissance construite lors de lapprentissage. Les rsultats peuvent tre
amliors par lintgration dautres signaux ou encore par lapprentissage hybride de diffrentes catgories dagents
apprenants.

Rfrences
[1] Alpaydin, E. Introduction to Machine Learning. London: The MIT Press Cambridge, Massachusetts, 2010.
[2] Dieterich T.G. An experimental comparison of three methods of constructing ensembles of decision trees: bagging,
boosting and randomization. Machine learning, 2000, Volume 40 pp139-157.
[3] ] Ferber J. Multi-agent systems : an introduction to distributed artificial Intelligence. Wisley, 1997.
[4Freund Y. and Robert, E. S. Experiments with a New Boosting Algorithm. In : Machine Learning : Proceedings of the
thirteenth International Conference, 1996, pp.148-156.
[5] Guessoum Z., Briot J.-P. From Active Object to Autonomous Agents. IEEE Concurrency, 1999, Volume 7 N 3 , pp.
68-78.
[6] Majumdar, K. Human Scalp EEG. In Processing: Various Soft Computing Approaches. Applied Soft Computing .
July 2011, pp. 4433-4447.
[7] Orriols-Puig A. and Bernad-Mansilla. E. A Further Look at UCS Classifier System. In Proceedings of the Genetic
and Evolutionary Computation Conference, Seattle, W.A., USA, 2006, pp. 1-4.
[8] Prichep, L. S. and John ER. QEEG profiles of psychiatric disorders. Brain Topography 1992; Volume 4 , pp. 249257.
[9] Sabeti, M. H. (2007). Fuzzy Accuracy-based Classifier Systems for EEG Classification of Schizophrenic Patients.
Iranian Fuzzy Systems Society . In Proceedings of the first Joint Congress on Fuzzy and Intelligent Systems Iran, Aug
2007, pp. 29-31
[10] Susmakova K., Krakovska A. Selection of measures for sleep stages classification. In the proceedings of the 7th
International Conference on Measurement, Slovakia,2009. pp.86-89.
[11] Wilson S. Classifier Based on accuracy. Evolutionary Computation, 1996, Volume 2,N3, pp 149-175.