Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
Cette thèse présente des contributions à l'étude théorique des problèmes de clustering. Le vaste objectif de ces problèmes est de partitionner un ensemble de données en groupes, telles que les données d'un même groupe soient similaires. Les problèmes des k-médianes et des k-moyennes sont des façons habituelles de modéliser formellement ce problème, sur lesquelles nous nous concentrons dans cette thèse. Dans la première partie, nous présentons un schéma d'approximation en temps linéaire quand l'entrée est dans un espace Euclidien de dimension constante (ou, plus généralement, de doubling dimension constante), i.e., un algorithme très rapide qui calcule une approximation très précise de la solution optimale. Nous étendons les techniques utilisées pour traiter le problème du point de vue de la confidentialité différentielle. Dans la seconde partie, nous cherchons à calculer des représentation simplifiée de l'entrée, qui préservent la structure du problème: nous introduisons plusieurs techniques pour réduire le nombre de donnée, tout en s'assurant que résoudre le problème après la réduction soit presque équivalent à le résoudre sur l'ensemble initial. Nous montrons aussi que dans plusieurs cas, nos techniques sont optimales. Dans le cas particulier des espaces Euclidiens, une autre façon de simplifier l'entrée est de réduire la dimension (en préservant de la même façon la structure de l'entrée). Nous présentons le premier algorithme déterministe pour atteindre une dimension presque optimale. Finalement, nous utilisons les algorithmes et techniques introduits précédemment pour calculer très rapidement des indicateurs statistiques. ; This thesis presents contributions to the theoretical study of clustering problems.The broad objective of these problems is to partition a data set into groups, such that data in the same group are similar. The k-medians and k-means problems are common ways of formally modeling this problem, which we focus on in this thesis.In the first part of the thesis, we show the first linear time ...