Entrepôts, Représentation et Ingénierie des Connaissances

JOURNEE ANALYSE RELATIONNELLE MATHEMATIQUE (ARM)

Date : Lundi 16 janvier 2017

Lieu : Université Lyon 2, Campus Porte des Alpes à Bron, bât H, salle H213.

Inscription : Gratuite mais obligatoire ici

Programme :

  • 9h-9h30 : Accueil des participants

  • 9h30-10h30 : Jean-François Marcotorchino (LSTA, Univ. Paris 6), Modèles fondamentaux des critères de l’Analyse Relationnelle Mathématique (ARM): Théorèmes d’impossibilité d’Arrow (ordres) et Kleinberg (partitions) vs les propriétés intrinsèques et validantes de l’ARM.

  • 10h30-11h30 : Julien Ah-Pine (ERIC, Univ. Lyon 2),  ARM et programmes linéaires en nombres entiers associés. Applications en aide multicritère à la décision et en apprentissage non supervisé.

  • 11h30-12h30 : Saïd Chah Slaoui (Univ. Mohammed 5 de Rabat), (1) Algorithmes de sélection de variables discriminantes hétérogènes et (2) Nouvelles heuristiques en ARM.

  • 12h30-14h : Pause déjeuner (au resto'U).

  • 14h-15h : Patricia Conde-Céspedes, (LISITE/ISEP), Modélisations et extensions du formalisme de l’ARM à la modularisation des grands graphes et réseaux complexes.

  • 15h-16h : Lazhar Labiod (LIPADE, Univ. Paris 5), Classification croisée dans l’optique de l’ARM.

  • 16h-16h30 : Pause café

  • 16h30-17h30 : Damien Nogues, (Thalès/LIP6, Univ. Paris 6) Détection d’Anomalies en cyber sécurité par l’ARM.

  • 17h30- : Discussions et conclusion.

Résumés


  • 9h30-10h30 : Jean-François Marcotorchino (LSTA, Univ. Paris 6),
    Modèles fondamentaux des critères de l’Analyse Relationnelle Mathématique : Théorèmes d’impossibilité d’Arrow (ordres) et Kleinberg (partitions) vs les propriétés intrinsèques et validantes de l’ARM.

    Si désormais l’ARM (Analyse Relationnelle Mathématique) est connue d’un nombre important de scientifiques, elle n’a pas été comprise dans sa philosophie intrinsèque de façon claire. C’est pourtant une approche qui a des bases axiomatiques formelles solides et qui peut être utilisée dans des contextes et des cadres méthodologiques très différents par nature: Classifications, Clusterings, Ordres , Ordonnances , Bi-clustering, Sériation, Analyse Factorielle Relationnelle, etc. Mais elle permet également dans le contexte très à la mode du "Big Data" , de simplifier par linéarisation ou "pseudo-linéarisation" des modèles assez fréquemment rencontrés en Analyse des Données. Dans cette présentation nous insisterons sur les bases axiomatiques des théorèmes d’impossibilité connus (Arrow et Kleinberg) en montrant qu’il existe des biais dans cette axiomatique d’impossibilité dus à la notion de problèmes bien ou mal posés (Principe de Cournot), et nous montrerons comment l’ARM répond à ces biais en vérifiant une axiomatique de "non impossibilité" tout à fait cohérente. Nous en profiterons pour présenter en quelques transparents les fondamentaux notoires de l’Analyse Relationnelle Mathématique et rappeler que certains de ces résultats (ceux concernant le clustering) n’ont été compris et redécouverts dans leurs grandes lignes, que très récemment, par des chercheurs de haut niveau aux USA sous le vocable de "Correlation Clustering". Nous introduirons pour terminer quelques intersections entre la théorie du "Transport Optimal" et l’ARM en montrant les implications que cette dualité permet.


  • 10h30-11h30 : Julien Ah-Pine, (ERIC, Univ. de Lyon 2),
    ARM et programmes linéaires en nombres entiers associés. Applications en aide multicritère à la décision et en apprentissage non supervisé.

    Dans cet exposé nous étendons à d'autres types de relations binaires, les programmes linéaires en nombres entiers de l'ARM associés aux problèmes d'agrégation de relations d'ordre et de relations d'équivalence.
    Nous nous intéressons d'abord à des relations binaires sur un ensemble et rappelons dans ce cas, les relations de semi-ordre et d'ordre intervalle qui permettent une représentation plus riche des relations de préférence. Nous présentons alors les contraintes linéaires associées à ces types de relation. Ceci nous permet d'élargir le champ des possibles dans le cadre du problème d'agrégation de préférences dans la mesure où un ensemble de relations binaires peut alors être ajusté par plusieurs types de relations de préférence.
    Ensuite, nous abordons les relations binaires sur deux ensembles distincts. Nous rappelons notamment dans ce cas, les propriétés de surjectivité, injectivité et bijectivité. Ces propriétés permettent de caractériser algébriquement, les différents types de fonction d'un ensemble vers un autre. Il apparaît alors que la modélisation par l'ARM de ces propriétés permettent d'englober le problème de co-clustering/sériation en apprentissage non supervisé. En effet, ce problème peut alors être vu comme l'ajustement d'une matrice de données par une bijection.
    Ainsi, l'objectif de cet exposé est de donner un point de vue purement relationnel des fondements de plusieurs problèmes traités en aide multicritère à la décision et en apprentissage non supervisé. Par ailleurs, l'ARM apparaît alors comme une approche unifiante pour la résolution exacte de ces différents problèmes combinatoires.

    Références :
    - J. Ah-Pine, "On aggregating binary relations using 0-1 integer linear programming", In: ISAIM 2010, "International Symposium on Artificial Intelligence and Mathematics", 2010. En ligne: ici.
    - J. Ah-Pine, "Sur des aspects algébriques et combinatoires de l'analyse relationnelle : applications en classification automatique, en théorie du choix social et en théorie des tresses", Thèse de doctorat, Univ. Paris 6, 2007.


  • 11h30-12h30 : Saïd Chah Slaoui (Univ. Mohammed V de Rabat),
    Algorithmes de sélection de variables discriminantes hétérogènes et Nouvelles heuristiques en ARM.

    (1) Algorithmes de sélection de variables discriminantes hétérogènes
    Compte tenu de ses applications multiples dans toutes les le problématiques ayant un caractère prévisionnel, et plus récemment dans la détection des fraudes sur Internet, La sélection des variables a été largement traitée dans le cadre classique des variables explicatives homogènes (qualitative ou quantitative). L’objectif de la première partie de ma présentation est de proposer de nouveaux algorithmes de sélection de variables explicatives hétérogènes (qualitatives, quantitative ou ordinales). Il s’agit d’une adaptation des procédures pas à pas descendantes et pas à pas ascendantes dans le cas des variables explicatives hétérogènes. Ces algorithmes utilisent des critères d’association simples, multiples et partielles entre variables hétérogènes, introduits par l’auteur. Appliquées à des variables explicatives qualitatives, ces techniques permettent de retrouver le critère de discrimination du chi-deux de contingence. Il s’agit donc d’une généralisation de ce critère au cas de variables explicatives hétérogènes.
    (2) Nouvelles heuristiques en Analyse Relationnelle
    Depuis l’avènement d’Internet, les NTIC ont connu un essor fulgurant permettant le développement de l’EDI (Echange de données informatisées), la GED (la gestion électronique des documents), les ERP (Entreprise Ressource Planning), ainsi que l’émergence des média sociaux (réseaux sociaux, forums, blogs, wikis, sites de partage vidéo), du commerce électronique et du Cloud Computing. Ces domaines, entre autres, ont une caractéristique commune, à savoir la production d’un volume considérable de données dont l’exploitation pertinente constitue une opportunité concurrentielle pour les entreprises; d’où un besoin de plus en plus croissant en matière de techniques d’extraction des connaissances permettant l’exploitation des gisements des données échangées sur le Net et persistantes sur les référentiels des entreprises et organismes publics. Pour s’imposer comme technique incontournable de forage des données, l’analyse relationnelle métahématique devrait mettre à la disposition du grand public de nouvelles heuristiques d’implémentation, opérationnelles, simples à mettre en ouvre, fournissant des résultats stables et consistants, avec la possibilité de parallélisation pour la mise en œuvre dans un environnement de Big Data. L’objectif de la deuxième partie de mon intervention s’inscrit dans l’optique du développement de nouvelles heuristiques en analyse relationnelle mathématique qui s’articulent autour de l’idée de la recherche de la relation transitive la plus proche, au sens d’un critère donné, d’une relation réflexive et symétrique. La version de base de l’heuristique est intitulée TRANSITIVE, dont plusieurs versions sont en cours de développement, elles ont pour objectif de générer une solution stable (indépendante de l’initialisation et de l’ordre de traitement du fichier des données) pertinente (ne génère pas de fausses classes). Ainsi, l’exposé portera sur la version de base de Transitive, une version plus performante intitulée Transitive II, et une troisième version parallèle sous « Map Reduce » itératif avec une application au text mining.

    Références:
    - S.Chah Slaoui, H. Chamlal, Nouvelles Approches pour la sélection de variables discriminantes, RSA, 2000, XLVIII(4), 59,82.
    - S.Chah.Slaoui, Yassmine lamari, IEEE, ISCV 215, Clustering of large Data Based on Relational Analysis, The first International Conference On Intelligent System en Computer vision, March 25, 26 2105, Fez Morocco.
    - Yassmine Lamari, S.Chah Slaoui, Parallel Document Clustering Using Iteratiive mape Reduce, International Conference On Big Data and Advanced Wireless technologies, 10, 11 November 2016 Americain University in Bulgaria.


  • 14h-15h : Patricia Conde-Céspedes, (LISITE/ISEP),
    Modélisations et extensions du formalisme de l’ARM à la modularisation des grands graphes et réseaux complexes.

    Un graphe étant un ensemble d'objets liés par une certaine relation typée, le problème de "modularisation" des grands graphes (qui revient à leur partitionnement en classes) peut, alors, être modélisé mathématiquement en utilisant l'Analyse Relationnelle Mathématique. Cette modélisation permet de comparer sur les mêmes bases un certain nombre de critères de découpage de graphe c'est-à-dire de modularisation. Nous proposons une réécriture Relationnelle des critères de modularisation connus tels le critère de Newman-Girvan, Zahn-Condorcet, Owsinski-Zadrozny, Demaine-Immorlica, la Différence de profils, Michalski-Goldberg, l'Ecart à l'Indétermination, l'Ecart à l'Uniformité, etc. L'écriture relationnelle nous permet d'identifier les propriétés vérifiées par ces critères. Notamment pour les critères linéaires, nous caractérisons les partitions obtenues via leur optimisation dans le but de faciliter leur compréhension et d'interpréter plus clairement leurs finalités en y associant la preuve de leur utilité dans certains contextes pratiques. Les résultats trouvés par le bais de la notation relationnelle sont testés sur des graphes réels et sur des graphes synthétiques LFR de tailles différentes. Nous utilisons pour ceci l'algorithme de Louvain générique. Les partitions obtenues présentent des caractéristiques différentes, concernant notamment le nombre de classes. Le formalisme relationnel nous permet de justifier ces différences d’un point de vue théorique. En outre, l'approche relationnelle permet d’identifier facilement les critères ayant une limite de résolution (phénomène qui empêche en pratique la détection de petites communautés sur de grands graphes).

    Références :
    - P. Conde-Céspedes, F. Marcotorchino and E. Viennet, "Comparison of linear modularization criteria using the relational formalism, an approach to easily identify resolution limit", In AKDM6, "Advances in Knowledge Discovery and Management Journal. Springer, Vol 6, pp 101-120 to appear in 2017.
    - P. Conde-Céspedes, F. Marcotorchino and E. Viennet, "Comparison of linear modularization criteria using the relational formalism, an approach to easily identify resolution limit". Proceedings of 15th Conférence Internationale Francophone sur l'Extraction et la Gestion des Connaissances (EGC'15), Luxembourg, January 2015.
    - P. Conde-Céspedes and F. Marcotorchino, "Modularisation et Recherche de Communautés dans les réseaux complexes par Unification Relationnelle" , Revue des Nouvelles Technologies de l’Information (RNTI-A6), pages 71–97, June 2012.
    - R. Campigotto, P. Conde-Céspedes and J-L Guillaume, A Generalized and Adaptive Method for Community Detection, preprint on arxiv: http://arxiv.org/abs/1406.2518


  • 15h-16h : Lazhar Labiod, (LIPADE, Univ. Paris 5),
    Classification croisée dans l’optique de l’ARM.

    Lorsque les données mettent enjeu deux ensembles, ce qui est le cas le plus rencontré dans la pratique, les méthodes habituelles de classification automatique en ne faisant porter la structure recherchée que sur un seul de ces deux ensembles agissent de façon dissymétrique et privilégie un des deux ensembles.
    Le but de la classification croisée est d’obtenir une structure en blocs homogènes, une approche simple consiste à appliquer une méthode de classification simple (de type k-means) sur l’ensemble des objets et sur l’ensemble des attributs séparément, les blocs résultent du croisement des deux partitions obtenues. Une telle démarche ne permet pas d’expliquer la relation spécifique pouvant exister entre un groupe d’objet et un groupe d’attributs. Donc il est préférable d’appliquer des méthodes de classification croisée mieux adapter aux problèmes qui cherchent simultanément une partition en ligne et une partition en colonne.
    Dans cet exposé, nous présentons dans sa première partie une vue relationnelle unifiée d’un certain nombre de méthodes de classification croisée (les méthodes de type Double k-means et N-cut). La deuxième partie sera consacrée à la résolution du problème de classification croisée en s’appuyant sur les bonnes propriétés générées par la modélisation relationnelle des données et de la solution recherchée. En particulier, nous mettons en évidence des connexions mathématiques entre le formalisme relationnel de la classification croisée et son approximation par 1) une décomposition spectrale 2) par matrices bi-stochastiques et 3) par factorisation non négative. Enfin, nous illustrons l’intérêt de ces différentes approximations sur des données réelles et simulées.


  • 16h30-17h30 : Damien Nogues, (Thalès/LIP6, Univ. Paris 6),
    Détection d’Anomalies en cyber sécurité par l’ARM.

    Nous présenterons des travaux menés dans le cadre d’une thèse entre Thales et l’équipe complex network du LIP6. La détection d’intrusion est une problématique importante en cyber-sécurité. Cependant, de nombreuses approches classiques utilisent une approche à base de règles. Pour chaque attaque, une signature de détection est créée. Ces approches ne permettent donc pas de détecter de nouvelles attaques, ou des attaques connues mais modifiées. Pour cette raison, nous nous sommes intéressés aux approches de détection d’anomalies. Ces méthodes utilisent des techniques d’apprentissage non supervisé pour détecter des déviations à la norme. Ainsi, les techniques de clustering sont fréquemment utilisées. Mais les algorithmes classiques de clustering, tel que k-means, ne sont pas très adaptés à ce problème. En effet, ces derniers nécessitent souvent de fixer a priori le nombre de classes désiré. De plus, ces algorithmes sont en général conçus pour traiter des données quantitatives, ou parfois qualitatives. En détection d’intrusions, les données sont souvent hétérogènes. Nous détaillerons donc à l’aide de l’ARM un nouveau critère de clustering adapté aux données hétérogènes, ainsi qu’un algorithme d’optimisation de ce critère. Enfin, nous verrons comment il est possible d’utiliser la partition obtenue pour effectuer une détection d’anomalies sur des flux réseaux.