Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Les réseaux de neurones artificiels connaissent des succès dans plusieurs domaines. Maisles utilisateurs des réseaux de neurones sont souvent confrontés aux problèmes de définitionde son architecture et d’interprétabilité de ses résultats. Plusieurs travaux ont essayé d’apporterune solution à ces problèmes. Pour les problèmes d’architecture, certains auteurs proposentde déduire cette architecture à partir d’un ensemble de connaissances décrivant le domaine duproblème et d’autres proposent d’ajouter de manière incrémentale les neurones à un réseauayant une taille initiale minimale. Les solutions proposées pour le problème d’interprétabilitédes résultats consistent à extraire un ensemble de règles décrivant le fonctionnement du réseau.Cette thèse contribue à la résolution de ces deux problèmes. Nous nous limitons à l’utilisationdes réseaux de neurones dans la résolution des problèmes de classification.Nous présentons dans cette thèse un état de l’art des méthodes existantes de recherche d’architecturede réseaux de neurones : une étude théorique et expérimentale est aussi faite. Decette étude, nous observons comme limites de ces méthodes la disponibilité absolue des connaissancespour construire un réseau interprétable et la construction des réseaux difficiles à interpréteren absence de connaissances. En alternative, nous proposons une méthode appelée CLANN(Concept Lattice-based Artificial Neural network) basée les treillis de Galois qui construit undemi-treillis à partir des données et déduire de ce demi-treillis l’architacture du réseau. CLANNétant limitée à la résolution des problèmes à deux classes, nous proposons MCLANN permettantd’étendre cette méthodes de recherche d’architecture des réseaux de neurones aux problèmes àplusieurs classes.Nous proposons aussi une méthode appelée ’Approche des MaxSubsets’ pour l’extractiondes règles à partir d’un réseau de neurones. La particularité de cette méthode est la possibilitéd’extraire les deux formats de règles (’si alors’ et ’m parmi N’) à partir d’une structure quenous construisons. Nous proposons aussi une façon d’expliquer le résultat calculé par le réseauconstruit par la méthode MCLANN au sujet d’un exemple. / The artificial neural networks are successfully applied in many applications. But theusers are confronted with two problems : defining the architecture of the neural network able tosolve their problems and interpreting the network result. Many research works propose some solutionsabout these problems : to find out the architecture of the network, some authors proposeto use the problem domain theory and deduct the network architecture and some others proposeto dynamically add neurons in the existing networks until satisfaction. For the interpretabilityproblem, solutions consist to extract rules which describe the network behaviour after training.The contributions of this thesis concern these problems. The thesis are limited to the use of theartificial neural networks in solving the classification problem.In this thesis, we present a state of art of the existing methods of finding the neural networkarchitecture : we present a theoritical and experimental study of these methods. From this study,we observe some limits : difficulty to use some method when the knowledges are not available ;and the network is seem as ’black box’ when using other methods. We a new method calledCLANN (Concept Lattice-based Artificial Neural Network) which builds from the training dataa semi concepts lattice and translates this semi lattice into the network architecture. As CLANNis limited to the two classes problems, we propose MCLANN which extends CLANN to manyclasses problems.A new method of rules extraction called ’MaxSubsets Approach’ is also presented in thisthesis. Its particularity is the possibility of extracting the two kind of rules (If then and M-of-N)from an internal structure.We describe how to explain the MCLANN built network result aboutsome inputs.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

La fouille de données est l'extraction non triviale d'informations implicites, inconnues et utiles à partir des données (Piatetsky-Shapiro & Frawley, 1991). Plus récemment, la notion de systèmes de gestion de base de données inductive (SGBDI) propose l'union de la base de données traditionnelle à la fouille de données et d'une base de motifs ou patrons de données. Ces derniers sont les agents fondamentaux dans les SGBDI. Dans ce mémoire le motif examiné est le concept formel. Cependant, pour un ensemble de données (nommé contexte formel dans l'AFC) de grande taille où les données sont fortement corrélées, l'extraction peut être difficile à cause des problèmes de combinatoire inhérente à cette structure. Il est vrai que l'extraction de la collection des concepts formels fréquents, donc un iceberg plutôt qu'un treillis, est une solution. Cependant, d'une part, pour un seuil de fréquence trop faible, l'extraction des concepts formels fréquents peut demeurer difficile et la combinatoire de l'extraction demeure. D'autre part, les utilisateurs pourraient préférer conserver le treillis mais appliquer une certaine relaxation sur le formalisme des concepts formels. Cette relaxation se ferait en acceptant des exceptions dans les concepts dont les seuils sur les exceptions seraient choisis par l'utilisateur. En dernier lieu, le contexte formel pourrait bien avoir des erreurs dans ses transactions. Ces erreurs pourraient donc être la cause du nombre indu de concepts formels extraits. Une relaxation au niveau de l'extraction des concepts formels pourrait être une solution à ce problème. Notre contribution se situe au niveau d'un motif en particulier et de son mode d'extraction. Ce mémoire propose donc un concept tolérant des exceptions bornées par des seuils, soit les concepts denses et explore la possibilité d'extraire un tel motif par l'algorithme incrémentaI par cardinalité. En dépit du fait que le concept ne soit plus formel mais tolérant des exceptions, les principales notions de l'analyse formelle de concepts, (e.g. la relation de précédence, le treillis) sont fortement désirées. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Concepts formels, Concepts denses, Treillis de concepts formels, Analyse formelle de concepts, Concepts tolérant des exceptions, Algorithme d'extraction de concepts, Représentation condensée.

Les données dites multimédia (images, vidéos) se distinguent des données classique par une densité variable d'information et l'impossibilité de normaliser ces données. Du fait de ces particularités, de nouvelles techniques d'indexation et de recherche d'information ont du être etudiées. Il y a principalement deux problèmes a résoudre pour la recherche d'information dans les collections multimédia (ou les bases de données multimédia) : (1) la représentation des données et (2) le processus de recherche du point de vue de l'utilisateur. Dans le cas des bases de données, l'indexation est fortement liée a ces deux problèmes. Dans le cas particulier des images, on distingue trois grandes classes: – la recherche par requêtes formelles, héritée des bases de données classiques ; – la recherche avec boucle de retour, où l'utilisateur fait partie intégrante du processus de recherche ; – la navigation où les images sont organisées en une structure preparée à l'avance, utilisée comme index et comme structure de recherche. C'est sur cette troisième approche que nos travaux se sont portés ; nous nous sommes en effet interessés au treillis de Galois, une structure de graphe permettant d'organiser les éléments d'une relation binaire. Une telle structure de navigation a plusieurs avantages sur une approche classique basée sur des requêtes : en particulier, elle permet d'affranchir l'utilisateur d'une phase de rédaction de requête.

Dans cette thèse, nous avons développé FindMeDIA destiné à répondre aux besoins de conservation du patrimoine culturel marocain filmé et photographié. Nous avons donc à gérer une base d'images et de vidéos. Une vidéo pouvant être perçue comme une succession d'images fixes, nous avons traité les vidéos comme une extension qui s'appuie sur la modélisation des images de manière quasi transparente. Notre principal but est, d'une part, de répondre aux besoins de généricité et de flexibilité permettant de traiter ces différents types de médias visuels et, d'autre part, de proposer un système qui permette de naviguer en basculant indistinctement entre images et vidéos. Pour la modélisation des vidéos, nous avons proposé FindViDEO. En partie modèle, en partie métamodèle, FindViDEO est flexible et englobe une large gamme d'applications et de modèles préexistants. Pour la navigation, nous appliquons la technique des treillis de Galois sur une base de données composée d'images clés extraites des vidéos ainsi que d'images fixes. Le système FindMeDIA résultant est générique et offre la possibilité d'utiliser plusieurs techniques de descriptions des images en vue de la navigation. Pour tester l'intérêt de nos approches, la modélisation des images clés (extraites des vidéos) et des images fixes est effectuée par ClickImAGE qui propose une représentation semi-structurée des données basée sur le contenu des images.

Cette thèse en informatique se place dans le cadre de l'Analyse de Concepts Formels (ACF) ou les treillis de Galois. Ce sont des outils basés sur des opérateurs mathématiques appelés fermetures de Galois permettant de calculer des concepts. Un concept est formé d'un ensemble d'objets partageant tous un ensemble d'attributs communs. Ces concepts sont extraits à partir d'un contexte qui est une table de relation binaire entre ces objets et ces attributs. Nous nous intéressons à des contextes complexes dont la complexité repose sur deux axes. D'une part, les contextes multi-valués dont les attributs se divisent en plusieurs modalités. D'autre part, les contextes flous dont la relation entre objets et attributs n'est pas binaire. Nous définissons les contextes multi-valués flous qui héritent de ces deux complexités et présentons deux conversions des données multi-valuées floues. La première conversion est une binarisation par une disjonction totale des attributs permettant d'une part l'exploitation d'outils comme des implications et d'autre part de comparer et combiner les treillis avec des méthodes statistiques telles que l'analyse factorielle. La seconde conversion est issue de l'échelonnage histogramme que nous définissons et qui permet de convertir les attributs en histogrammes. Afin de générer les concepts à partir des histogrammes, nous proposons une nouvelle fermeture de Galois basée sur une mesure de similarité entre ces histogrammes. Cette fermeture permet d'obtenir des concepts pour lesquels les objets possèdent des attributs non plus égaux mais similaires compris entre un minimum et un maximum communs. Nous proposons également des mesures de seuillage pour limiter le nombre de concepts générés et diminuer les temps de calculs. Enfin, deux algorithmes ont été testés pour implémenter cette fermeture : MinMaxNC et MinMaxC, dont nous comparons les performances. Cette thèse trouve son application notamment dans le domaine hydrobiologique dont une problématique est la sélection de traits écologiques de taxons permettant de caractériser l'état écologique des cours d'eau par le comportement des espèces au sein de leur environnement. La sélection de ces traits s'appuie sur la recherche de groupes de taxons possédant des caractéristiques morphologiques et physiologiques (appelés traits biologiques) communes. Ces groupes correspondent à des concepts au sens de l'ACF et les données biologiques se présentent sous la forme d'un contexte multi-valué flou pour lequel nous montrons l'efficacité de notre approche.

Nous abordons, par une modélisation à base de graphes, deux problèmes de structuration de données. Phylogénie: Nous utilisons la famille de graphes associée à une dissimilarité pour définir la notion nouvelle de distance triangulée, plus générale qu'une distance additive d'arbre. Nous proposons un algorithme d'ajustement de données à une distance triangulée par triangulation des graphes associés. Nous introduisons pour cela le concept nouveau de sous-triangulation maximale, afin de prendre en compte la sous-évaluation intrinsèque des données phylogénétiques. Nous procédons ensuite à une étude théorique complémentaire. Analyse Formelle de Concepts: Nous codons une relation binaire R et son treillis des concepts L(R) par un graphe non orienté co-biparti G(R). Nous montrons que les éléments de L(R) sont en bijection avec les séparateurs minimaux de G(R), et que les chaînes maximales de L(R) sont en bijection avec les triangulations minimales de G(R). Des procédés algorithmiques appliqués à G(R) trouvent ainsi leurs correspondants dans L(R). En particulier, des treillis de taille polynomiale peuvent être obtenus à partir de L(R), par plongement de G(R) dans un graphe faiblement triangulé. Nous mettons ensuite en évidence un ordre de domination sur les modules complets maximaux de G(R), domination qui s'hérite quand on parcourt une chaîne maximale de L(R). Une structure de données, la table de domination, gère dynamiquement les relations de domination. Nous utilisons cette table pour deux applications algorithmiques: - Mise à jour d'une sous-hiérarchie de Galois matérialisant une hiérarchie d'héritage orienté-objet; - Génération efficace d'un treillis des concepts.

Cette thèse est composée de deux contributions à l'étude des bases de données : (i) la première contribution porte sur l'amélioration de la compréhension, par l'étude formelle, de la tension entre les fonctionnalités de cohérence et de confidentialité. Cette tension permet, dans certaines situations, d'utiliser les contraintes d'intégrité (cohérence) pour révéler des secrets (confidentialité) et donc réaliser des fraudes. L'étude fixe tout d'abord un cadre général de recherche en donnant une définition formelle des notions de secret, révélation et fraude. Puis, une occurrence particulière, et originale, de tension est formalisée selon une méthode inspirée des méthodes de programmation. Cette occurrence s'est avérée liée aux treillis de Galois. (ii) la deuxième contribution porte sur la spécification et l'implémentation d'une fonctionalité originale : le classement d'objets selon leur histoire. A cette fin, l'étude répond successivement aux trois questions : qu'est-ce que l'histoire d'un objet, comment exprimer des propriétés sur l'histoire des objets, et comment les vérifier efficacement ? L'expression est réalisée par des formules de logique temporelle et la méthode de vérification repose sur la traduction de ces formules en expressions régulières puis en automates d'états finis. L'implémentation réalisée utilise cette méthode de classement pour classer a posteriori des objets du langage prototypique NewtonScript.