53 research outputs found
Un algorithme efficace pour reconnaitre les dissimilarités dont tous les chemins de tous les arbres de longueur minimale sont Robinsoniens
No full textInternational audienceÉtant donné une dissimilarité d sur un ensemble X, un arbre T = (X, E) est compatible avec (X, d) si pour tous x, z ∈ X et tout y sur le chemin entre x et z, d(x, z) ≥ max{d(x, y), d(y, z)}. Si T est compatible avec (X, d), alors T est un arbre de longueur minimale (ALM) de (X, d). Étant donné (X, d) avec |X| = n, nous présentons dans cet article un algorithme en O(n 2 ) pour vérifier si un ALM donné T est compatible (avec (X, d)) et un algorithme en O(n 3 ) qui détermine si tous les ALM de (X, d) sont compatibles. Ceci répond (approximativement) à une question de Brucker (2013)
About weak connectivity
No full textAbstractWe characterise the directed graphs such that, for every induced subgraph, one can define (disjoint) weakly connected components. When oriented, these graphs are exactly the locally semi-complete oriented digraphs and we give the structure of such graphs when infinite and locally finite. Then we show that the general case can be reduced to the oriented case by contraction of the cycles of length two
Fractal Self-Avoiding Walks
No full textInternational audienceFor any odd integer K > 1, we define F K , a new family of self-avoiding walks (SAW) on the square lattice Z ⇥ Z, called K-fractal walks. These families have a simple and natural characterization and they seem to all have a critical exponent ⌫ for mean-square displacement in ]0.5, 1[. For small values of K at least , these families are easy to count and it is also very easy to randomly generate a K-fractal walk. In addition, lim K!1 F K is the set of all SAWs on Z ⇥ Z. We present also some variants of fractal SAWs, e.g. fractal SAWs on the d-dimensional grid Z d
Actes des 30es rencontres de la Société Francophone de Classification: SFC 2025
No full textNational audienceIn NLP, handling underrepresented topics is challenging, particularly in unsupervised tasks where clustering may fail to capture minority topics effectively. To address this, we propose an unsupervised data augmentation method that combines Gaussian Mixture Models (GMMs) and Large Language Models (LLMs). GMMs identify underrepresented clusters, while LLMs generate synthetic documents to enrich them. Experiments on various imbalanced text datasets show that our approach maintains clustering performance and often improves interpretability, providing a robust and scalable solution for enhancing data representation in unsupervised NLP
DISTANCES, ORDERS AND SPACES
No full textInternational audienceA dissimilarity d on a set X is said to be Robinson if there exists a total order, said compatible, on X such that x < y < z =⇒ d(x, z) ≥ max{d(x, y), d(y, z)}. Roughly speaking, d is Robinson if the points of X can be represented on a line ie. Robinson dissimilarities generalize line distances. In this paper, we define k-dimensional Robinson dissimilarities, which generalize the possibility, for a metric set (X, d), to be embedded into a k-dimensional Euclidean space. This generalization is more flexible than the classical embedding and we show that every dissimilarity on an n-set X is (log n)-dimensional Robinson. We give an O(n 3) algorithm which builds such an embedding. This algorithm is based on an incremental algorithm to recognize Robinson dissimilarities
Graphs and topologies on discrete sets
No full textAbstractWe show that a graph admits a topology on its node set which is compatible with the usual connectivity of undirected graphs if, and only if, it is a comparability graph. Then, we give a similar condition for the weak connectivity of oriented graphs and show there is no topology which is compatible with the strong connectivity of oriented graphs. We also give a necessary and sufficient condition for a topology on a discrete set to be ‘representable’ by an undirected graph.fr|Nous montrons qu'un graphe admet une topologie sur l'ensemble de ses sommets compatible avec la connexité usuelle des graphes non-orientés si, et seulement si c'est un graphe de comparabilité; puis nous donnons une condition similaire pour la connexité faible des graphes orientés et montrons la non-existence d'une topologie compatible avec la connexité forte. Nous donnons également une condition nécessaire et suffisante pour qu'une topologie sur un ensemble discret soit ‘représentable’ par un graphe non-orienté
Actes des 30es rencontres de la Société Francophone de Classification
No full textCes rencontres ont pour objectif de présenter des résultats récents et des applications originales en classification sous toutes ses formes, mathématique, informatique et statistique, de favoriser les échanges scientifiques entre ces trois communautés autour de la thématique commune de la classification et de faire connaitre à divers partenaires extérieurs les travaux de ses membres. Le thème des rencontres est la classification et l\u27analyse de données au sens large et, en particulier, ces thèmes classiques : - Classification et discrimination - Modèles de mélange - Méta-heuristiques en classification - Représentation et visualisation - Analyse de données topologiques - Analyse de données symboliques - Arbres, graphes et treillis - Applications de la classification dans tous les domaines - Structures combinatoires pour la classification - Sériation. Une journée commune est organisée avec CAp (Conférence sur l\u27Apprentissage Automatique), consacrée aux applications de l\u27apprentissage automatique à la classification ou de la classification à l\u27apprentissage automatique, et plus généralement aux liens entre ces deux domaines
Distance sequences in infinite regular tessellations
No full textAbstractWe give formulae which yield linear algorithms for calculating distance sequences in Euclidean and hyperbolic tessellations. Then, we characterize the Euclidean tessellations as the regular tessellations whose distance sequence is linear and show that, in a hyperbolic or Euclidean tessellation {p, q}, for every n > 0, q divides the circumference of the circles of radius n
Totally Balanced Formal Context Representation
No full textInternational audienceWe show in this paper that doubly lexical orders of totally balanced formal context matrices yield a unique graphical representation binding formal contexts, associated concepts and underlying lattice directed cover graphs. Moreover this representation can be done linearly in the size of the formal context matrix
- …
