|
Affiner ou élargir la recherche
8 entrées référencées
| Titre |
NP-difficulté de la détermination d’une relation d’équivalence médiane en classification (problème de Régnier) |
| Auteur |
HUDRY Olivier |
| Mots-clefs |
Agrégation de relations, Classification, Complexité, Distance de la différence symétrique, NP-complétude, Partition, Problème de Régnier, Problème de Zahn, Relation d'équivalence, Relation médiane |
| Thème |
Aucun |
| Résumé |
Étant donnée une collection Π de relations d’équivalence (ou partitions), le problème de Régnier consiste à déterminer une relation d’équivalence qui minimise l’éloignement par rapport à Π. L’éloignement est fondé sur la distance de la différence symétrique et mesure le nombre de désaccords entre Π et la relation d’équivalence considérée. Une telle relation d’équivalence minimisant l’éloignement est appelée une relation d’équivalence médiane de Π. On montre ici la NP-difficulté du problème de Régnier, c’est-à-dire du calcul d’une relation d’équivalence médiane d’une collection Π de relations d’équivalence, du moins quand le nombre de relations d’équivalence de Π est suffisamment grand. |
| Numéro |
197, Printemps 2012, n° spécial Catégories, classification, complexité, consensus... Autour des travaux de Jean-Pierre Barthélemy |
| Langue |
 Anglais | Lire l'article
| Titre |
Consensus de familles de Moore typées |
| Auteur |
DOMENACH Florent |
| Mots-clefs |
Classification, Fermeture, Hiérarchie, Implication, Relation d'emboîtement |
| Thème |
Aucun |
| Résumé |
Soit C un ensemble de classes d'éléments d'un ensemble S. On considère classiquement qu'il va contenir S et qu'il va être stable par intersection, i.e. que c'est une famille de Moore. Cet article porte sur les possibilités d'ajustement d'un système de classes à une relation d'emboîtement (et donc d'implication) donnée. Pour tout entier p entre 1 et k, et pour tout profil de familles de Moore, on associe la fonction consensus créée par les paires de sous-ensembles de S emboîtées dans au moins p familles du profil. Nous allons montrer que cette fonction consensus permet d'obtenir une famille de Moore spécifique, et ce pour des profils de familles de Moore emboîtées, hiérarchiques, distributives, topologiques, pour des arbres de parties ou encore pour des géométries convexes. |
| Numéro |
190, Été 2010, n° spécial Théories et usages. Numéro en hommage à Bruno Leclerc |
| Langue |
 Français | Lire l'article
| Titre |
Quelques remarques sur la méthode d'ajustement de Mayer : lien avec les méthodes de classifications |
| Auteur |
FALGUEROLLES Antoine |
| Mots-clefs |
Algorithme des transferts de Régnier, Classification, Histoire de la statistique, Méthode des moyennes de Mayer, Régression linéaire |
| Thèmes |
Classification - Partition, Histoire de la statistique, Statistique |
| Résumé |
Le cas simple de l'ajustement d'une droite de régression par la méthode de Mayer, au programme de l'enseignement secondaire français il y a quelques années, avait été introduit comme un succédané de la méthode des moindres carrés. Il apparaît que la démarche qui était ainsi proposée aux élèves fournit un exemple élémentaire d'arbre de régression. Il apparaît aussi que, dans le cas général, c'est un problème de classification pour lequel l'algorithme des transferts de Régnier [1965] est particulièrement bien adapté quoique possiblement suboptimal. L'exemple célèbre d'ajustement, que Mayer traite en 1750 par une méthode novatrice et très générale, est revu à la lumière de méthodes statistiques contemporaines usuelles. Les résultats numériques obtenus montrent l'extraordinaire maîtrise de Mayer. |
| Numéro |
187, Automne 2009, n° spécial Journée 2007 de la Société francophone de classification |
| Langue |
Français | Lire l'article
| Titre |
Condorcet et "L'art de former des tableaux historiques" |
| Auteur |
RIEUCAU Nicolas |
| Mots-clefs |
Base de données, Classification, Condorcet, Histoire, Informatique, Progrès |
| Thèmes |
Classification - Partition, Epistémologie, Histoire des sciences, Informatique |
| Résumé |
Membre du courant encyclopédique et Secrétaire perpétuel de l'Académie des Sciences, Condorcet (1743-1794) est particulièrement au fait de la question de la classification, que celle-ci s'applique au monde des idées ou à celui de la Nature. Il commente les réalisations de ses contemporains en la matière et nourrit son propos par une réflexion sur les principes de classification en tant que tels. Originale et méconnue, la classification qu'il consacre à l'histoire des progrès de l'esprit humain, dite Table de référence, est une émanation directe de cette réflexion. Elle est élaborée selon trois dimensions codées - lignes, colonnes, profondeur - devant permettre le stockage, le repérage et le traitement des données historiques. L'aspect inachevé de la Table de référence est aisément compréhensible si on la conçoit comme une construction exploratoire que Condorcet souhaiterait léguer aux générations futures. La Table de référence est aussi pour Condorcet une manifestation de la puissance de l'analyse, synonyme chez lui de calcul mathématique. Il en résulte une vision proprement mécanique de l'opération de classification, l'exposé de Condorcet annonçant, de manière explicite, l'avènement de la mécanographie et du traitement automatique de l'information. |
| Numéro |
176, Hiver 2006, n° spécial Contribution à l'histoire des probabilités. Numéro en hommage à Bernard Bru |
| Langue |
Français | Lire l'article
| Titre |
Condorcet et la mathématique sociale. Enthousiasmes et bémols |
| Auteur |
FELDMAN Jacqueline |
| Mots-clefs |
Classification, Condorcet, Langue universelle, Mathématique sociale |
| Thèmes |
Histoire des mathématiques, Histoire des sciences, Sociales (Sciences) |
| Résumé |
Condorcet est le dernier encyclopédiste : « géomètre », passionné par le « bien public », il croit dans un progrès indéfini de l'esprit humain et des connaissances. La Raison, qui a si bien réussi dans les sciences de la nature, doit à présent servir aussi les « sciences morales », dont le but est le bonheur de l'homme. Premier à proposer et penser une « mathématique sociale », après n'avoir guère été écouté là-dessus au 19e siècle, il a retrouvé, depuis un demi-siècle, une reconnaissance académique, en tant que précurseur des mathématiques appliquées aux sciences de l'homme et de la société. Ce texte rappelle l'évolution de ses idées, en particulier les réticences du début, qu'on peut retrouver dans certaines critiques actuelles. Il évoque aussi, éléments de sa pensée moins connus, l'importance qu'il accorde à « l'art de faire des tableaux » et à l'établissement d'une langue universelle, qui permettraient à tous de participer à la connaissance scientifique. Il signale enfin, au-delà de l'enthousiasme militant de la maturité, quelques réflexions qui montrent que Condorcet n'était pas dupe de la possibilité de certaines dérives. |
| Numéro |
172, Hiver 2005, n° spécial Modèles et méthodes mathématiques dans les sciences sociales : apports et limites |
| Langue |
Français | Lire l'article
| Titre |
Comparaison de données taxonomiques |
| Auteur |
LERMAN Israël-César |
| Mots-clefs |
Classification, Coefficients d'association, Données structurées, Indices de similarité |
| Thèmes |
Classification - Partition, Distances, Données (Analyse des) |
| Résumé |
La prise en compte fidèle de la structure des données est une des caractéristiques essentielles de la méthode de classification hiérarchique AVL de l'Analyse de la Vraisemblance des Liens. Pour cette méthode les variables descriptives sont interprétées en termes de relations sur l'ensemble des objets. Le cas où ces variables définissent des taxonomies sur l'ensemble des objets devient ces dernières années de plus en plus important en Classification. Néanmoins, les coefficients d'association entre variables ainsi que les indices de similarité (resp. dissimilarité) entre objets de la sorte obtenus, ont une portée très générale. Ils peuvent en effet être adaptés à toute méthode de classification. |
| Numéro |
151, Automne 2000 |
| Langue |
Anglais | Lire l'article
| Titre |
Graphes et classification : l'exemple des tables de mobilité sociale |
| Auteur |
DALUD-VINCENT Monique |
| Mots-clefs |
Classification, Composante (fortement) connexe, Graphe, Mobilité sociale, Table de contingence |
| Thèmes |
Classification - Partition, Graphes, Sociologie |
| Résumé |
L'objectif est de mettre en évidence, à partir d'un tableau de contingence croisant 2 variables utilisant la même nomenclature, une typologie des catégories de cette nomenclature. La recherche de cette typologie est basée sur l'hypothèse selon laquelle il existe des groupes de catégories en fonction des attractions entretenues entre elles ainsi que de leurs enchaînements. On s'appuie sur une modélisation sous forme de graphes et sur une méthode de décomposition des composantes (fortement) connexes. |
| Numéro |
147, Automne 1999, n° spécial Classification |
| Langue |
Français | Lire l'article
| Titre |
Segmentation de la sériation pour la résolution de #SAT |
| Auteur |
LERMAN Israël-César, ROUAT Valérie |
| Mots-clefs |
Classification, Dénombrement de solutions, Problèmes #P-complets, Satisfiabilité, Sériation, Théorie de la complexité |
| Thèmes |
Algèbre, Algorithmes - Algorithmique, Classification - Partition, Logique |
| Résumé |
Le problème général traité est celui de l'évaluation approchée du nombre de solutions d'une formule booléenne F sous forme normale conjonctive. En appliquant le principe "diviser pour résoudre", la méthode présentée permet de réduire de façon considérable la complexité algorithmique du problème. Elle est basée sur la segmentation d'une sériation établie sur la table d'incidence associée à F. Nous montrons, dans des cas aléatoires difficiles de génération d'une formule F, l'intérêt de la sériation et de sa meilleure coupure en deux parties connexes et de tailles comparables. De plus, nous définissons la notion d'indépendance en probabilité pour F. On propose ici et on valide théoriquement et par une vaste expérimentation la méthode. |
| Numéro |
147, Automne 1999, n° spécial Classification |
| Langue |
Français | Lire l'article
Droits des utilisateurs :
Cette création est mise à disposition sous un contrat Creative Commons
|
