Conception et Pratique de l'algorithmique
UPMC - 4I505 CPA - C. Dürr

TME 4 - Problème k-means

Dans cette séance nous allons implémenter l'algorithme k-means++ pour le problème de k-means. Celui-ci est décrit dans les notes de cours.

L'entrée

L'entrée est un fichier texte contenant des points dans le plan. Chaque ligne contient le caractère v suivi d'un entier et de deux nombres réels de la forme 
  v [identifiant] [latitude] [longitude]
où *identifiant* est un identifiant unique du point et *longitude, latitude* sont des nombres flottants qui représentant des degrés des coordonnées GPS. Concrètement chaque point représente un carrefour dans un réseau routier. Pour la distance entre deux points, nous utilisons la distance à vol d'oiseau. La distance entre deux points GPS peut être calculée par la formule de haversine.

Les fichiers

Tous les fichiers distribués se trouvent dans ce fichier ZIP et ils sont aussi dans `/Vrac/cpa2017/tme4/`.

Trois fichiers d'entrée sont mis à votre disposition, qui contiennent les coordonnées GPS des carrefours dans le réseau routiers de quatre îles.

saintlouis.txt
L'île saint louis - de l'ordre de 140 points
man.txt
L'île de man - de l'ordre de 5 000 points
malte.txt
L'île de malte - de l'ordre de 18 000 points
idf.txt
L'île de France - de l'ordre de 1 000 000 points
Déterminez à l'aide du plus gros des fichiers l'erreur que nous faisons en utilisant la distance de Haversine, plutôt que la distance euclidienne sur les points projetés dans le plan. On s'attend à ce que cette erreur soit négligeable.

Nous vous fournissons aussi du code pour visualiser votre solution.

visualize.py
Un script python qui lit sur l'entrée standard la sortie produite par votre programme et qui produit le contenu pour un fichier 'visualize.js'.
visualize.html
Une page web à ouvrir dans votre navigateur. Elle nécessite le fichier 'visualize.js'
Une exécution de votre programme `kmeansplusplus` suivra alors les étapes suivantes, pour k=10 par exemple. 
  ./kmeansplusplus 10 man.txt | ./visualize.py > visualize.js
  # ouvrir ou rafraîchir visualize.html

Votre programme

Votre programme reçoit deux paramètres en ligne de commande, un entier k, qui est le nombre de centres recherchés, et le nom du fichier d'entrée. Il affichera alors en sortie une copie du fichier d'entrée et k lignes de la forme 
  s [latitude] [longitude]
représentant les cordonnées GPS des centres calculés par votre programme, ainsi qu'une dernière ligne de la forme 
  o [valeur_objectif]

Les étapes de programmation

  • Commencez par écrire un code simple qui lit l'entrée et choisit simplement les k premiers points de l'entrée comme centre
  • Écrivez la fonction de distance de haversine. Faites attention à la conversion entre degrés et radians. Testez en comparant son résultat avec cette page web.
  • Puis écrivez une fonction qui sélectionne k centres par l'algorithme k-means++
  • Et finalement appliquez la recherche locale de Llyod sur ces centres
  • Saisissez vos résultats dans cette feuille de calcul. Obtenez vous une solution avec une valeur objectif similaire, pire ou meilleure que la moyenne ?
    •

    Pour aller plus loin

    Implémentez la procédure d'initialisation de Ostrovsky, Rabani, Schulman et Swamy. Est-ce que les résutats obtenus sont similaires qu'avec k-means++ ?

    Pour aller encore plus loin

    Dans /Vrac/cpa2016/gutenberg vous trouverez une collection de quelques milliers de fichiers texte en français, récupérés de gutenberg.org. Ces fichiers ont une entête contenant titre et auteur. Vous pouvez utiliser votre programme pour les classifier. Choisissez une petite constante c, par exemple 2. Puis pour chaque document produisez un vecteur, qui compte la fréquence de c lettres adjacentes dans le document. Puis appliquez votre programme sur ces vecteurs pour classifier les documents en k groupes distincts. Avec un peu de chance si c est suffisamment grand et k bien choisit vous pourriez peut-être déterminer des groupes de textes similaires, par exemple écrits par un même auteur. Il peut être une bonne idée d'ignorer les ponctuations (considérer tout caractère inférieur à 'A' comme un espace ' ') et de convertir les lettres en minuscules.

    Une correction