Soutenance mémoire
Les deux dernières décennies ont vu l’essor des méthodes d’analyses de données multidimensionnelles dans des domaines d’application aussi variés que les sciences humaines, la sociologie ou l’économie [124, 24, 116]. Le principe général à l’oeuvre est fondé sur la recherche d’une ou plusieurs informations statistiques permettant de résumer l’information afin d’établir un caractère d’homogénéité, s’il en existe, et donc de faciliter l’analyse par une tierce personne. La transformation de ou des informations vers un savoir intelligible n’en demeure pas moins une tâche peu évidente, car elle impose une altération de celles-ci sous l’influence de notre perception à déterminer ce qui est pertinent ou significatif.
Quelle que soit l’application, on souhaite pouvoir manipuler les informations extraites à l’aide de représentations symboliques des données et d’un ensemble de primitives, sous la forme de prédicats ou de relations, qui décrivent comment interagissent ces éléments entre eux. Une description ontologique permet alors de dégager l’ensemble des concepts permettant de qualifier ce qui existe en utilisant les notions du domaine. On distingue ainsi les entités et les prédicats comme étant les unités de base de la connaissance (c.f. [118] et les études plus récentes [61, 25]).
Les entités sont des unités ponctuelles ou discrètes qui forment naturellement l’univers du discours, soit le monde avec lequel on souhaite interagir ou le sujet sur lequel portent les prédicats. Par des combinaisons des prédicats avec des connecteurs logiques, on est alors en mesure de formuler des propositions logiques dont la véracité dépend des faits qui décrivent de manière abstraite l’état du monde à un instant particulier. Celles-ci sont également les propositions atomiques à partir desquelles toutes les autres sont formulables [34].
Éléments d’algèbre universelle
Introduction / Motivation
Traditionnellement, une algèbre est présentée comme la donnée d’un ensemble d’entités et d’opérations sur ces mêmes éléments, permettant d’en atteindre d’autres au sein du même ensemble. A cet égard, la porosité entre cette description et celle des relations apparaît clairement et illustre aisément la dualité autour de ces deux concepts. À titre d’exemple, l’opération d’addition (+) entre entiers naturels N lie entre eux certains nombres, de cela résulte alors un nouveau nombre, lui-même pouvant être librement et indéfiniment associé. A contrario, l’existence d’une opération inverse (−) semble aller de soi au premier abord, bien qu’elle soit infondée puisqu’elle transgresse une règle de base : le résultat d’une soustraction a − b peut ne pas être un entier naturel. Ce constat est loin d’être une argutie même si il paraît évident d’objecter par l’emploi des entiers relatifs pour lesquels cette opération est correctement définie. En particulier, la présentation duale a le merite d’exposer ce point avec concision :
a ≤ b ⇔ (∃x)(a + x = b ⇔ x = b − a) (∀a, b ∈ N) (2.1)
où ≤ est entièrement définie sur N × N. Cette dernière permet de définir l’addition comme une relation ternaire (a, x, b) ∈ N3 . La projection sur le second membre projette (au sens de la surjection) chaque paire (a, b) sur l’ensemble de ses élément adjoints {xi}.
Le résultat est défini implicitement par l’existence d’au moins un élément pouvant être adjoint à a pour obtenir b. Elle engendre deux copies de N représentant chacun l’ensemble contenant le résultat de la soustraction selon :
(∀a, b)(a − b ∈ Z− + Z+) (2.2)
où :
Z− = {−x | x ∈ N} (2.3)
Z+ = N (2.4)
Néanmoins, cette construction opérationnelle peut ne pas être possible dans tous les ensembles concrets, par exemple, les mots formés sur un alphabet Σ n’ont pas d’inverses naturels bien que les propriétés formelles codifiant la combinaison de leurs éléments sont semblables à celles de l’arithmétique (ce sont tous deux des monoïdes et obéissent donc aux axiomes idoines). Généralement, il existe des méthodes permettant sous certaines conditions de construire des inverses ; ces derniers devant répondre aux propriétés abstraites désirées.
Cet exemple illustre l’avantage d’employer les relations afin de faciliter l’étude ou l’émergence de nouvelles propriétés algébriques et réciproquement. Par ailleurs, cette dualité est profitable dans la présentation algébrique d’une logique selon qu’on souhaite insister sur la notion d’implication (liée à l’ordre) ou sur la notion de connecteurs logiques (liée aux opérateurs).
La prochaine section sera ainsi dévolue à la définition d’une structure d’algèbre et de relation, puis de l’étude de leurs propriétés communes.
Relations et Structures
Préliminaires
Définition 2.2.1 (Relation). Une relation d’arité n ou n-aire définie sur un domaine ou univers mathématique A, modélise une propriété que certaines de ses entités peuvent vérifier. L’extension de la relation est l’ensemble qui contient alors les tuples (xi)1≤i≤n ∈ An vérifiant cette propriété. Lorsque la définition d’une relation est une phrase ou une formule dans un langage, on parle plus spécialement de modèle.
Reprenant la définition de l’ordre sur les entiers naturels 2.1, on a :
a ≤ b ⇔ (a, b) ∈ ≤ ⊆ N² (2.5)
qui est une relation 2-aire ou binaire.
Définition 2.2.2 (Structure de relations). Une structure est, par définition, la donnée d’un ensemble A muni d’une famille indexée de relations (Ri) sur A. La structure se voit également associée la famille des arités de chaque relation représentant la structure. Cette famille représente le type de la structure. Deux structures sont similaires si elles ont le même type.
Par la suite, on notera indifféremment A le domaine d’une structure et la structure elle-même, en l’absence d’ambiguïté dans son usage.
Définition 2.2.3 (Opération). Par une opération sur un ensemble A, on entend une opération n-aire qui associe un élément de A à chaque n-uplet de A. Une opération est alors une fonction totale.
L’addition entre entiers naturels est donc une opération binaire associant un entier naturel à chaque paire d’entiers naturels.
Définition 2.2.4 (Structure algébrique). Une algèbre est définit comme un ensemble muni d’opérations n-aire soit une structure d’opérations (Oi) sur A.
|
Table des matières
1 Introduction
2 Éléments d’algèbre universelle
2.1 Introduction / Motivation
2.2 Relations et Structures
2.2.1 Préliminaires
2.2.2 Sous-structures et leurs propriétés
2.3 Homomorphismes et isomorphismes de structures
2.3.1 Généralités et Principes
2.3.2 Images, noyaux et compositions
2.4 Relations de congruence, algèbres quotients et modèles
3 Ensembles ordonnés, Treillis et leurs applications
3.1 Ensembles partiellement ordonnés
3.1.1 Préliminaires
3.1.2 Liens avec les ordres stricts
3.1.3 Relation de couverture et Diagramme de Hasse
3.1.4 Bornes et sous-ensembles remarquables
3.2 Treillis et algèbre de l’ordre
3.2.1 Préliminaires
3.2.2 Propriétés ordinales des treillis
3.2.3 Morphisme de treillis
3.3 Représentation des treillis
3.3.1 Éléments premiers et parties génératices
3.3.2 Extension canonique
3.4 Conclusion
4 Agrégation dans les entrepôts de données
4.1 Introduction
4.1.1 Notre proposition
4.2 Travaux connexes
4.3 Modélisation du cube de données
4.3.1 Préliminaires
4.3.2 Projections canoniques sur l’ensemble des attributs A
4.4 Construction du treillis des partitions annotées
4.5 Expériences
4.5.1 Aspects computationnels
4.5.2 Processus opérationnel global
4.6 Conclusion et perspectives
5 Application au consensus de partitions
6 Conclusion
