EXTENSION DU FLOCKING ET IMPLEMENTATION 

EXTENSION DU FLOCKING ET IMPLEMENTATION 

LE FORAGE DE DONNÉES 

INTRODUCTION AU FORAGE DE DONNÉES

Le forage ou la fouille de données (FD) est un ensemble de méthodes et d’algorithmes pour l’exploration et l’analyse de grandes bases de données. Ces méthodes ont pour objectif de détecter des règles, des associations, des tendances inconnues, des structures, désignées alors par le terme de connaissances relatives aux données analysées, et cela, afin de faciliter la prise de décisions [19, 20]. On peut ainsi reformuler le forage de données comme « l’analyse du passé pour prédire le futur ». Les motivations du développement du forage de données sont liées à la masse importante de données qui existe de nos jours, et qui double tous les 20 mois. La croissance en puissance des machines actuelles permet de supporter de gros volumes de données, et d’envisager l’exécution intensive dont requiert la fouille de donner. En effet, les données, souvent désignées par le terme « instance », sont multidimensionnelles, elles possèdent généralement des milliers d’attributs, et sont souvent inexploitables par les méthodes classiques. En autre, le traitement de ces données doit se faire en temps réel, car si les décisions prennent trop de temps à être prise elles seront probablement obsolètes.

La démarche méthodologique du forage de données est de comprendre le problème en sélectionnant un échantillon de donné avec une méthode d’échantillonnage adapté au problème, de supprimer le « bruit » de cet échantillon (les données superflues ou manquantes) si nécessaire, et éventuellement de sélectionner une partie des attributs pour réduire la dimension du problème. Pour ensuite, appliquer une ou plusieurs techniques de fouille de données avec un algorithme spécifique choisi au préalable pour chaque technique. La méthodologie du forage de données peut être résumé comme un processus itératif à plusieurs passes, interactif dans le sens où l’utilisateur est dans la boucle, valide et compréhensible .

LE FORAGE DE DONNÉES DANS LES HABITATS INTELLIGENTS 

Les méthodes classiques de reconnaissance d’activités se servent de différentes approches basées sur trois types de contraintes : les approches exploitant des contraintes logiques traditionnelles [6], les approches utilisant les contraintes temporelles [14] et celles exploitant les contraintes spatiales [15].

APPROCHES A VEC LOGIQUES TRADITIONNELLES
Kautz et Allen [12] ont établi l’une des plus importantes approches basées sur les logiques traditionnelles. Celle-ci consiste à utiliser la logique de premier ordre afin de formaliser le processus d’inférence de l’activité en cours. Cependant, dans le cadre des habitats intelligents, son approche est rarement utilisée, car elle ne prend pas en compte les erreurs potentielles des acteurs. De ce fait, son modèle interprète les erreurs comme des changements d’activités. De plus, l’approche logique part du principe que toutes les activités possibles sont connues et répertoriées, ceci n’est pas réaliste dans le contexte où l’acteur peut être erratique et peut se tromper. Certains chercheurs, comme Py et Nerzic [22, 23] ont proposé des approches logiques avec gestion des erreurs. Mais ces méthodes n’ont pas encore été formalisées ni implémentées, car elles soulèvent de nouveaux problèmes, comme le fait de devoir définir toutes les erreurs possibles d’un plan. D’autres approches logiques se basent aussi sur des modèles probabilistes (modèles de Markov cachés et ses extensions, réseau bayésien, etc.) [13], faisant partie des méthodes de classification du forage de données. Ces modèles consistent à attribuer une probabilité à chaque plan de la bibliothèque selon les actions observées. Entre autres, lorsque l’acteur fait quelque chose, la probabilité des plans qui contiennent cette action augmente. Ainsi, le plan ayant le plus haut score est probablement l’activité réalisée par l’agent observé. Les modèlent probabilistes comportent néanmoins deux problèmes [6]. Tout d’abord, le temps de calcul peut devenir très long lorsque le nombre de plans est élevé, car ils sont tous évalués à chaque action. Ensuite, en ajoutant une nouvelle activité à la bibliothèque, il faut recalculer la distribution des probabilités afin qu’elles soient uniformes. Ces inconvénients limitent l’ajout de nouveaux comportements. Toutefois, d’autres approches combinent le processus d’inférence probabiliste avec une approche symbolique [24]. Ainsi, la bibliothèque de plans est filtrée, et seulement un sous ensemble des plans est utilisé dans le processus d’inference, ce qui permet un temps de calcul plus raisonnable. Malgré tout, les approches avec logiques traditionnelles restent limitées, c’est pourquoi d’autres types de méthodes ont été développées, comme les approches temporelles.

APPROCHES TEMPORELLES
Les approches temporelles utilisent comme contraintes les durées, les délais, mais aussi des méthodes plus complexes comme les relations d’Allen [25]. Ces relations représentent 14 possibilités entre deux intervalles du temps, dont ce dernier est symbolisé par une droite infinie constituée d’un nombre infini de points. Par exemple, la partie temporelle du travail de Jakkula et Cook [14] est basé sur les relations d’Allen. Cela permet, dans les cas où une action est souvent suivie par une autre action spécifique, d’inférer une règle temporelle qui permet de savoir quelle est cette action suivante. Entre autres, si l’action PrendreUnOeuf est toujours suivie par l’allumage de la cuisinière, l’action CuireUnOeuf est inférée grâce aux relations d’Allen. De plus, ils utilisent les règles d’associations de l’exploration de données pour faire apprendre à leur système les activités clés. Cette technique est basée sur le la recherche des schémas d’associations [16] qui consistent à identifier les patrons séquentiels fréquents, et à les enregistrer. Cela leur permet d’apprendre à leur algorithme les activités fréquentes de l’agent grâce aux relations observées, et ainsi d’améliorer l’assistance procurée par leur système. Cependant, leur méthode dépend énormément de l’apprentissage de leur algorithme, car il doit connaître de nombreuses suites d’actions pour être efficace. Ceci demande beaucoup de temps d’apprentissage et doit être répété pour chaque nouvel agent observé. D’autres travaux [26,27] utilisent l’aspect temporel, mais aucun d’eux ne peut reconnaitre les problèmes de type spatiaux qui peuvent subvenir dans les habitats intelligents. Il est donc nécessaire d’ajouter l’aspect spatial dans la reconnaissance d’activités pour pouvoir gérer le plus de cas possible.

APPROCHES SPATIALES
Les approches spatiales sont peu nombreuses à ce jour malgré qu’elles soient reconnues comme un aspect fondamental de la reconnaissance d’activités. Dans cette section, nous allons présenter deux approches récentes qui intègrent des notions spatiales. La première est celle de Augusto [15]. Tout d’abord, pour pouvoir suivre la position de l’agent observé, ils ont combiné des détecteurs infrarouges ainsi qu’une étiquette intelligente RFID portée par l’acteur. Puis, ils ont accroché des antennes RFID aux portes pour détecter l’acteur lorsqu’il franchit la porte, mais aussi des capteurs de mouvement qui indiquent dans quelle pièce il est entré. Ainsi, Augusto a pu suivre l’acteur assez précisément dans l’habitat intelligent. La seconde a été conçue par Riedel [28] et traite l’aspect spatial de la reconnaissance d’activités grâce à un modèle chimiotactique. Celui-ci est tiré du mouvement des bactéries nommé le chimiotactisme [29] qui leur permet de se diriger vers des gradients physiques. En outre, le modèle de Riedel exploite une abstraction de ce processus afin de représenter et reconnaitre certaines activités. Cependant, dans ces deux précédentes approches seulement la position de l’acteur est utilisée, alors qu’il faudrait utiliser l’ensemble des objets. Dans cette optique, on aurait beaucoup plus de données à traiter et on pourrait intégrer pleinement la reconnaissance spatiale de l’habitat intelligent. C’est à ce niveau là que le forage de données intervient, puisque son objectif est d’extraire des informations à partir de grandes quantités de données.

En utilisant de nombreux capteurs on peut identifier tous les objets présents dans l’habitat intelligent, et ainsi combiner les approches temporelles et spatiales. Le fait d’effectuer une activité déclenche obligatoirement un déplacement des objets mobiles, un changement d’état des objets immobiles, et chacune de ces actions implique également un temps auquel elles ont été effectuées. Cependant, on ne peut pas directement reconnaitre les activités à partir de ces informations, on ne connait pas la « classe » des activités lorsqu’elles sont effectués. De ce fait, les méthodes de classifications ne sont pas appropriées pour ce problème, car il faut connaître la classe à l’avance. De même, les règles d’associations ne sont pas très utiles, car on ne veut pas obtenir des corrélations entre les attributs de position ou temps, mais reconnaitre des activités directement à partir des données des capteurs. C’est pourquoi les méthodes de segmentation semblent les plus adéquates pour notre problématique, nous allons donc voir en détail en quoi consiste la segmentation.

LA SEGMENTATION

La segmentation, de l’anglais « clustering », consiste à séparer un large ensemble de données en plusieurs sous-ensembles nommés clusters. Les éléments contenus dans un cluster sont similaires entre eux et différents des éléments des autres clusters [30, 31]. L’objectif de la segmentation est de trouver des structures inhérentes aux données et de les présenter sous forme d’un ensemble de clusters [32]. Les applications typiques de la segmentation sont comme outil d’exploration interne des distributions de données, ou comme étape de prétraitement pour les autres algorithmes. Recourir à la détection des clusters quand les regroupements naturels peuvent représenter des groupes de clients, de produits, ont beaucoup en commun. En effet, lors de la présence de plusieurs schémas en compétition au sein des données il est difficile d’extraire un schém particulier, c’est pourquoi la création de clusters peut réduire la complexité en organisant les données en clusters. Les techniques de segmentation se séparent en deux catégories : le partitionnement et la répartition hiérarchique [30, 31]. Les méthodes hiérarchiques construisent une hiérarchie de clusters et une unique partition d’objets. Dans ces techniques, le nombre de clusters n’est pas requis et une matrice de distance est généralement utilisée comme critère de segmentation. De même, ces méthodes sont souvent caractérisées comme des approches de segmentation de meilleure qualité. Cependant, la complexité de la répartition hiérarchique est en général au moins O(n2 ), cela rend ces techniques trop lentes pour les grands ensembles de données. Au contraire, la complexité algorithmique des techniques de partitionnement est la plupart du temps linéaire. Celles-ci divisent les données en groupes qui ne se chevauchent pas pour maximiser le temps de traitement.

LES MÉTHODES CLASSIQUES DE SEGMENTATION

Maintenant que les principes de la segmentation ont été présentés nous examinerons le fonctionnement de trois techniques, la première est l’une des méthodes les plus connues et utilisées depuis plusieurs décennies, c’est l’algorithme K-means [19] .

K-MEANS
L’objectif du K-means est de segmenter les données en k-groupes, il faut spécifier avant de lancer l’algorithme combien de clusters ont désire créer, c’est le paramètre k [33, 34]. Ensuite, k points sont choisi semi aléatoirement comme centre des clusters. Toutes les instances sont assignées au centre le plus proche d’eux, ceci étant calculé avec la distance euclidienne vue précédemment. Voici un exemple d’initialisation dans la Figure 2 cidessous avec trois clusters.

Algorithme 1 : K-means

L’algorithme K-means converge rapidement vers une solution dû à sa complexité linéaire, c’est l’un des algorithmes de segmentation le plus performant en terme de temps de calcul, qui résulte du nombre d’itérations dont il a besoin pour former ses clusters [19]. Cependant, cet algorithme a plusieurs inconvénients. Le premier est que les clusters finaux sont très dépendants de leurs positions initiales qui a été établi semi-aléatoirement. Le second est que l’algorithme converge vers un minimum local, les centres des clusters se déplacent pour réduire la distance avec leurs données, mais il n’y a pas de garantie que ce soit la distance globale minimale. Une version amélioré de l’algorithme appelé K means++ [19] consiste à choisir le centre du premier cluster aléatoirement parmi l’ensemble des données afin qu’il ait une probabilité de distribution uniforme, puis de déterminer le centre suivant de sorte que sa position soit proportionnelle à une certaine distance au carré par rapport au premier, et ainsi de suite jusqu’au nombre de clusters désirés. Cela augmente ainsi la vitesse d’exécution et la précision de l’algorithme. Malgré tout, il faut quand même choisir un nombre de clusters au départ et donc avoir connaissance à l’avance du problème à résoudre pour que l’algorithme soit efficace. Néanmoins, dans notre contexte d’habitat intelligent nous ne savons pas à l’avance combien d’activités vont être réalisées, ainsi nous avons besoin d’un algorithme qui n’a pas besoin de préciser le nombre de clusters à l’avance. Parmi les méthodes de segmentations, l’algorithme Expectation Maximisation (EM) fait partie de ceux qu’on peut exécuter sans lui préciser le nombre de clusters, nous allons ainsi détailler son fonctionnement.

EXPECTATION MAXIMISATION (EM)

Cet algorithme, proposé par Dempster et al. en 1977 [35], permet de trouver le maximum de vraisemblance des paramètres de modèles probabilistes [19]. Le maximum de vraisemblance est une statistique utilisée pour inférer les paramètres de la distribution de probabilité d’un échantillon donné, autrement dit c’est cette statistique qui va permettre de trouver le nombre de clusters qu’il doit créer, si on ne lui indique pas ce nombre à l’avance. En effet, l’algorithme EM qui est plus connu avec son nom anglais que son nom français : Espérance-Maximisation, permet de choisir ou non le nombre de clusters. Dans le cas où on ne lui indique pas de nombre, il va le chercher lui-même.

Algorithme 2 : Expectation Maximisation (EM)

Enfin, l’algorithme EM termine les itérations lorsque la moyenne des probabilités des clusters est inférieure à un certain seuil, 10~10 par exemple, sur une dixième d’itérations successives. Toutefois, l’algorithme converge vers un maximum local à cause de la toute première itération, pour obtenir un maximum global il faut répéter l’algorithme plusieurs fois.

Comme avec K-means les données sont statiques, ce sont seulement les clusters qui sont améliorés au fil des itérations. Nous allons étudier maintenant un autre type d’algorithme de segmentation qui est basé sur le déplacement des données pour la formation des clusters : les colonies de fourmis.

COLONIES DE FOURMIS

Les algorithmes de colonies de fourmis sont des algorithmes inspirés du comportement des fourmis et qui constituent une famille de métaheuristiques d’optimisation. Mis en lumière par Marco Dorigo et al. en 1990 [36], le premier algorithme s’inspire du comportement des fourmis recherchant un chemin entre leur colonie et une source de nourriture, pour la recherche de chemins optimaux dans un graphe. L’idée originale s’est depuis diversifiée pour résoudre une classe plus large de problèmes et plusieurs algorithmes ont vu le jour, s’inspirant de divers aspects du comportement des fourmis. En anglais, le terme consacré à la principale classe d’algorithme est « Ant Colony Optimization » (abrégé ACO), ou « Ant Clustering ».

Algorithme 3 : Colonie de fourmis

Les fourmis peuvent ainsi être vu comme des agents simple réflexe [39]. Ce type d’agent choisit ses actions uniquement sur le percept courant en ignorant les percepts précédents. Ainsi, la colonie de fourmis s’adaptera de façon relativement flexible aux changements. A partir de ces avantages, des recherches ont été effectué afin d’utiliser les colonies de fourmis comme algorithme de segmentation [40, 41]. Le principe est le suivant : Chaque agent se déplace d’une manière aléatoire au départ, puis en suivant les phéromones des autres agents. Durant son déplacement l’agent peut lâcher les données qu’il transporte selon une certaine probabilité. S’il rencontre sur son chemin des données et qu’il n’en transporte pas, il peut ramasser ces nouvelles données. Après plusieurs itérations des clusters vont émerger à partir de l’activité collective. De plus, les colonies de fourmis n’ont pas besoin de connaitre le nombre de clusters au départ puisqu’ils vont être créés par les agents.

LE FLOCKING ET SES UTILISATIONS COMME ALGORITHME DE SEGMENTATION

Le Flocking, mis en lumière par Craig Reynolds [42], est à la base, un comportement attribué à certains animaux lorsqu’ils se déplacent en groupe, comme les oiseaux ou les poissons par exemple. Toutefois, le Flocking est plus qu’un simple modèle,c’est un comportement émergent [43]. Ces comportements peuvent sembler complexes aux yeux des observateurs, mais en réalité ils reposent sur des règles très simples. Les agents virtuels, premièrement désignés avec le terme « boid » par Reynolds, suivent ces règles sans connaitre le but recherché, ils sont seulement conscients d’eux-mêmes et de quelquesuns de leurs voisins. Le modèle du Flocking [42] repose donc sur une combinaison de trois règles : l’alignement, la séparation et la cohésion. Ces règles, présentées à la figure 1, sont exécutées à chaque boucle du programme pour tous les agents, et permettent ainsi un déplacement cohérent.

L’alignement donne la même direction aux agents, elle est calculée en faisant la moyenne des directions de leurs voisins. La séparation éloigne les agents entre eux en fonction de la distance qui les sépare. La cohésion attire l’agent vers le centre de masse de ses voisins.

CONCLUSION GÉNÉRALE 

L’assistance technologique des personnes est un domaine encore jeune, mais très prometteur pour l’avenir. Les nouvelles technologies permettant d’obtenir plus de données dans les habitats intelligents de nombreuses recherches sont réalisées pour améliorer les algorithmes de reconnaissance d’activités afin de donner une meilleure assistance aux utilisateurs de l’habitat d’une manière non intrusive. Parmi toutes les techniques de reconnaissance d’activités et de forage de données, le Flocking est une méthode pertinente pour la segmentation des données grâce à son comportement émergent. Il permet aussi bien de traiter de petit ou de grand ensemble de données, sans baisser la qualité des clusters formés, car les agents peuvent changer facilement et rapidement de cluster. En effet, les agents suivent seulement quelques règles simples par rapport à leurs voisins et ont ainsi peu de probabilité de se retrouver dans le mauvais cluster, contrairement à beaucoup d’algorithmes comme le K-means où les données sont statiques et peuvent donc engendrer plus d’erreurs. En terme de temps de calcul, le Flocking nécessite effectivement plus d’itérations que les algorithmes classiques, mais au prix d’une meilleure segmentation. De plus, la durée de traitement reste raisonnable en temps humain, nous n’avons pas besoin que la segmentation se fasse en moins de quelques millisecondes, car la personne assistée n’effectuera pas plus d’une action par seconde de toute façon. Enfin, le Flocking a été mis en lumière depuis 1987 [42] mais il est utilisé comme méthode de segmentation seulement depuis quelques années, il y a donc de nombreuses possibilités d’améliorations qui pourront rendre la méthode encore plus performante.

Table des matières

CHAPITRE 1  INTRODUCTION 
1.1 CONTEXTE DE LA RECHERCHE
1.2 LA RECONNAISSANCE D’ACTIVITES
1.3 LE FORAGE DE DONNEES
1.3 CONTRIBUTION DE CE MÉMOIRE
1.4 MÉTHODOLOGIE DE LA RECHERCHE
1.5 ORGANISATION DU MÉMOIRE
CHAPITRE 2  LE FORAGE DE DONNEES 
2.1 INTRODUCTION AU FORAGE DE DONNÉES
2.1.1 LE FORAGE DE DONNEES DANS LES HABITATS INTELLIGENTS
2.1.1.1 APPROCHES AVEC LOGIQUES TRADITIONNELLES
2.1.1.2 APPROCHES TEMPORELLES
2.1.1.3 APPROCHES SPATIALES
2.1.2 LA SEGMENTATION
2.2 LES MÉTHODES CLASSIQUES DE SEGMENTATION
2.2.1 K-MEANS
2.2.2 EXPECTATION MAXIMISATION (EM)
2.2.3 COLONIES DE FOURMIS
2.3 LE FLOCKING ET SES UTILISATIONS COMME ALGORITHME DE SEGMENTATION
2.3.1 LA SEGMENTATION DE DOCUMENT AVEC DU FLOCKING PAR CUI ET AL
2.3.1.1 REPRESENTATION DES DOCUMENTS
2.3.1.2 MESURE DE SIMILARITÉ
2.3.1.3 DEUX NOUVELLES RÈGLES : SIMILARITÉ ET DISSIMILARITE
2.3.1.4 EXPERIMENTATIONS ET RÉSULTATS
2.3.2 DETECTION DES « OUTLIERS » DE PUCE A ADN AVEC LE FLOCKING
2.3.2.1 REPRESENTATION DES DONNÉES
2.3.2.2 ALGORITHME OFLOSCAN
2.3.2.3 EXPERIMENTATIONS ET RÉSULTATS
2.4 CONCLUSION SUR LA REVUE DE LITTÉRATURE
CHAPITRE 3  EXTENSION DU FLOCKING ET IMPLEMENTATION 
3.1 INTRODUCTION
3.1.1 FORCES D’ALIGNEMENT, DE SEPARATION ET DE COHESION
3.1.1.1 ALIGNEMENT
3.1.1.2 SEPARATION
3.1.1.3 COHESION
3.1.2 EXTENSION DU FLOCKING POUR LA SEGMENTATION
3.1.2.1 DISSIMILARITE
3.1.2.2 SIMILARITÉ
3.1.2.3 FORCE RÉSULTANTE
3.2 IMPLEMENTATION DU FLOCKING
3.2.1 L’INFRASTRUCTURE DU LIARA
3.2.2 SPECIFICATIONS LIÉES A LA BASE DE DONNÉES
3.2.3 CHOIX D’IMPLEMENTATIONS DE L’ALGORITHME
3.2.3.1 LES ÉTAPES D’UNE ITERATION
3.2.3.2 PARTITIONNEMENT DU MONDE VIRTUEL EN ZONES
3.3 EXPERIMENTATIONS ET RESULTATS
3.3.1 SCÉNARIOS DE CAS RÉELS
3.3.1.1 SCENARIO LIRE UN LIVRE
3.3.1.2 SCENARIO ALLER AUX TOILETTES
3.3.1.3 SCENARIO DORMIR DANS LA CHAMBRE
3.3.1.4 SCÉNARIO CUISINER POUR LE SOUPER
3.3.1.5 SCENARIO CUISINER POUR LE DEJEUNER
3.3.2 INTERFACE GRAPHIQUE ET PROTOCOLE EXPERIMENTAL
3.3.3 EXEMPLE D’EXÉCUTION ET RÉSULTATS
3.4 CONCLUSION DU CHAPITRE
CHAPITRE 4  CONCLUSION GÉNÉRALE

Télécharger le rapport complet