Éditeur(s) : HAL CCSD Springer Verlag
Résumé : A preliminary version appeared in the 18th ACM-SIAM Symposium on Discrete Algorithms, pp. 746- 755, 2007
International audience
The Voronoi diagram of a finite set of objects is a fundamental geometric structure that subdivides the embedding space into regions, each region consisting of the points that are closer to a given object than to the others. We may define various variants of Voronoi diagrams depending on the class of objects, the distance function and the embedding space. In this paper, we investigate a framework for defining and building Voronoi diagrams for a broad class of distance functions called Bregman divergences. Bregman divergences include not only the traditional (squared) Euclidean distance but also various divergence measures based on entropic functions. Accordingly, Bregman Voronoi diagrams allow one to define information-theoretic Voronoi diagrams in sta- tistical parametric spaces based on the relative entropy of distributions. We define several types of Bregman diagrams, establish correspondences between those diagrams (using the Legendre transformation), and show how to compute them efficiently. We also introduce extensions of these diagrams, e.g. k-order and k-bag Bregman Voronoi diagrams, and introduce Bregman triangulations of a set of points and their connection with Bregman Voronoi diagrams. We show that these triangulations capture many of the properties of the celebrated Delaunay triangulation.
ISSN: 0179-5376

hal-00488441
https://hal.archives-ouvertes.fr/hal-00488441
https://hal.archives-ouvertes.fr/hal-00488441/document
https://hal.archives-ouvertes.fr/hal-00488441/file/BVD-DCG.pdf

Éditeur(s) : HAL CCSD Elsevier
Résumé : International audience
Recently, a large amount of work has been devoted to the study of spectral clustering — a powerful unsupervised classification method. This paper brings contributions to both its foundations, and its applications to text classification. Departing from the mainstream, concerned with hard membership, we study the extension of spectral clustering to soft membership (probabilistic, EM style) assignments. One of its key features is to avoid the complexity gap of hard membership. We apply this theory to a challenging problem, text clustering for languages having permeable borders, via a novel construction of Markov chains from corpora. Experiments with a readily available code clearly display the potential of the method, which brings a visually appealing soft distinction of languages that may define altogether a whole corpus.
ISSN: 0031-3203

hal-00329991
https://hal.archives-ouvertes.fr/hal-00329991
DOI : 10.1016/j.patcog.2008.06.024