Lab 12 : Clustering ================== Durée estimée : 2 heures. Objectifs de la série --------------------- - Implémenter deux algorithmes de clustering - Comprendre l'intérêt et les limites de l'apprentissage non supervisé Fichiers squelettes ------------------- - :download:`distance.py` - :download:`maladies.py` - :download:`profits.py` - :download:`clusteringHierarchiqueTemplate.py <../../exercises/hw12/clusteringHierarchiqueTemplate.py>` - :download:`kMeansTemplate.py <../../exercises/hw12/kMeansTemplate.py>` - :download:`testkMeans.py` - :download:`testclusteringHierarchique.py` Énoncé ------- Le clustering est une méthode qui permet, à partir d'une base de données, de regrouper les données similaires en agrégats, ou clusters, afin de réduire la complexité apparente des données en découvrant une structure. Les classifications obtenues peuvent ensuite être utilisées pour diverses applications, comme dans les exemples suivants. - En bioinformatique, des méthodes de clustering peuvent être utilisées pour grouper des espèces d'êtres vivants similaires, en espérant pouvoir généraliser à tout le groupe les propriétés connues d'une espèce particulière. Par exemple, un traitement efficace contre un agent pathogène donné pourrait s'avérer aussi efficace pour d'autres micro-organismes du même cluster. - Dans le domaine de la vision, le nombre de pixels de différentes nuances de gris dans une image peut être réduit en regroupant plusieurs pixels en un même cluster, et en attribuant une nuance de gris commune à tous les pixels du cluster. - Une classification d'utilisateurs d'un site internet à partir de leurs habitudes de consultation du site peut permettre de concevoir des interfaces différentes pour chaque classe, afin d'adapter le site aux attentes des utilisateurs. De façon similaire, une classification du contenu d'un site internet peut aussi aider à décider comment diviser le contenu en plusieurs sections thématiques. Dans cette série d'exercices, nous vous proposons deux domaines particuliers : - Une liste de maladies, avec leurs symptômes ; une classification de ces maladies devrait permettre d'identifier des groupes d'affections similaires, susceptibles d'être traitées par des traitements similaires. - Une liste d'entreprises dans le domaine de l'informatique, dont une classification en différents groupes pourrait permettre d'identifier des proches concurrents sur le marché. Les deux algorithmes de clustering que vous allez implémenter dans les exercices suivants sont des algorithmes itératifs, qui construisent des clusters en suivant l'algorithme général suivant : :: FUNCTION clustering( données ) clusters <- chargeDonnees( données ) WHILE NOT fini( clusters ) DO clusters <- reviseClusters( clusters ) ENDWHILE afficheResultat() END clustering Cet algorithme vous est fourni, presque tel quel, dans le fichier ``clusteringHierarchiqueTemplate.py``. Les deux seules différences d'implémentation sont les suivantes : - La fonction ``chargeDonnees`` prend des arguments différents en fonction de l'algorithme particulier utilisé (clustering hiérarchique ou clustering de partitionnement). Elle sera donc appelée dans les fichiers correspondants. - Les variables représentant les données et les clusters seront des variables globales, si bien qu'elles ne sont pas explicitement utilisées dans le fichier ``clusteringHierarchiqueTemplate.py``. Exercice 1 : Le clustering de partitionnement par l'algorithme *k-means* ------------------------------------------------------------------------- L'algorithme k-means part d'une liste de noyaux, qui sont des données autour de chacune desquelles sera construit un cluster. A chaque itération, chaque donnée est réaffectée au cluster du noyau duquel elle est le plus proche, puis chaque cluster est recentré autour d'un nouveau noyau. L'algorithme termine quand l'ensemble des noyaux n'a pas changé d'une itération à la suivante. Comme indiqué dans l'algorithme général de clustering, les fonctions principales à implémenter sont ``chargeDonnees``, ``fini`` et ``reviseClusters``. La fonction ``chargeDonnees`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ La fonction ``chargeDonnees`` prend deux arguments : le nombre ``k`` de clusters désiré, et (en option) une liste de noyaux initiaux. La première partie de cette fonction vous est donnée. Vous devez implémenter la deuxième partie, qui crée la liste ``CLUSTERS`` des clusters initiaux. Initialement, ``CLUSTERS`` doit contenir ``k`` listes de données, la première donnée de chaque liste correspondant au noyau du cluster que la liste représente. .. note:: Remarque importante : ``CLUSTERS`` doit contenir toutes les données de ``DONNEES``. Celles qui ne sont pas des noyaux devront donc être attribuées à des clusters, d'une manière que vous choisirez et qui n'a pas d'influence sur la trace de l'algorithme. Nous vous proposons par exemple par défaut d'affecter toutes les données (qui ne sont pas des noyaux) au premier cluster. La fonction ``fini`` ~~~~~~~~~~~~~~~~~~~~~ Codez cette fonction, qui implémente la condition de terminaison de l'algorithme. Elle doit retourner ``True`` si et seulement si les noyaux générés à l'itération précédente (et stockés dans la liste ``VIEUXNOYAUX``) sont les mêmes que les noyaux courants. .. hint:: Utilisez la fonction :py:func:`~kMeans.retourneNoyaux`, que vous devrez préalablement implémenter, et qui retournera la liste des noyaux, générée à partir de la liste des clusters CLUSTERS. .. hint:: L'ordre des noyaux dans les listes n'a pas d'importance. La fonction doit retourner ``True`` si les deux listes contiennent les mêmes éléments, même s'ils ne sont pas dans le même ordre. La fonction ``reviseClusters`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Comme indiqué plus haut, cette fonction exécute deux étapes : #. En fixant les noyaux, les clusters sont mis à jour par la fonction :py:func:`~kMeans.formeClusters`, que vous devez implémenter. Cette fonction doit retourner une liste de clusters dont les noyaux sont inchangés, mais dont les autres données ont été réaffectées au cluster dont le noyau est le plus proche. #. Pour chaque cluster ainsi obtenu, le noyau est mis à jour afin d'être au "centre" du cluster. Cette opération est effectuée par la fonction :py:func:`~kMeans.recentreNoyau`, que vous devez implémenter. Cette fonction réordonne les données du cluster afin de mettre en tête de liste la donnée qui minimise la moyenne quadratique des distances aux autres données du cluster. En d'autres termes, le noyau x\ :sub:`n` doit minimiser l'expression suivante : .. math:: \sum_{x \in C} d(x_n, x)^2 *Indication*: Utilisez la fonction :py:func:`~kMeans.distance` pour calculer la distance entre deux données. .. tip:: A deux reprises, vous allez devoir parcourir une liste pour trouver l'élément de la liste qui minimise une certaine fonction. Ceci peut être implémenté en Python en une seule ligne, grâce à la fonction ``min(liste, key = fonction)``, qui prend en paramètres une liste d'éléments, et une fonction que l'on cherche à minimiser. Par exemple, pour retourner l'élément de la liste ``[1, 2, -3]`` qui a le plus petit carré, on peut utiliser la ligne de code suivante :: min( [1, 2, -3], key = lambda x: x**2 ) Le *key =* est nécessaire pour ne pas que Python interprète le deuxième argument comme un élément à comparer au premier argument. Discussion ~~~~~~~~~~~ Testez votre algorithme sur les deux exemples fournis : ``maladies.py`` et ``profits.py``. Faites varier le nombre de clusters, ainsi que les noyaux initiaux. Que pensez-vous de la qualité des clusters obtenus ? Les données classifiées dans un même cluster sont-elles toujours très similaires ? Est-il facile de choisir le nombre de clusters ? Exercice 2 : Le clustering hiérarchique ------------------------------------------- A la différence du clustering de partitionnement, le clustering hiérarchique par agglomération construit une classification en clusters de plus en plus grands, qui peut se présenter sous la forme d'un dendogramme. La classification hiérarchique obtenue est organisée en groupes et en sous-groupes, afin de discerner les agrégats de similarité grossière des agrégats de similarité plus fine. Dans la pratique, l'algorithme part d'un ensemble de clusters réduits à une seule donnée, et, à chaque itération, fusionne les deux clusters les plus similaires. La mesure de similitude entre deux clusters peut être calculée de différentes façons. Dans cet exercice, nous vous en proposons deux : la distance single-link et la distance complete-link. La distance single-link définit la similitude de deux clusters comme la plus courte distance entre deux données de ces clusters. A l'inverse, le complete-link considère la plus longue distance. L'algorithme termine quand toutes les données ont été regroupées en un seul et même cluster. Comme pour l'algorithme de k-means, les fonctions à implémenter sont ``chargeDonnees``, ``fini`` et ``reviseClusters``. La fonction ``chargeDonnees`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Afin de construire le dendogramme, vous devrez utiliser la classe :py:class:`~clusteringHierarchique.Noeud` qui représente un noeud du dendogramme, et auquel est associé un cluster. Plutôt que de travailler sur une liste de clusters comme dans l'exercice précédent, vous allez donc travailler sur une liste de noeuds ``NOEUDS``, qui contiendra la liste des noeuds dont le cluster reste encore à fusionner avec un autre cluster. Implémentez la fonction ``chargeDonnees``, qui initialise cette liste de noeuds, en créant un noeud pour chaque donnée, qui se retrouve donc être son propre cluster. Le constructeur de la classe ``Noeud`` prend trois paramètres : la profondeur du noeud dans le dendogramme, la liste des noeuds successeurs (vide pour les noeuds initiaux, qui sont les feuilles du dendogramme), et le cluster associé. .. note:: La profondeur d'un noeud dans le dendogramme est une mesure du degré de similarité de son cluster. Par exemple, le noeud racine du dendogramme, dont le cluster regroupe toutes les données, aura un degré de similarité le plus faible possible (par convention pris égal à 1). Les feuilles, dont le cluster est réduit à une seule donnée, auront le degré de similarité le plus élevé, égal au nombre total de données. A chaque itération de l'algorithme, la profondeur du noeud créé sera décrémentée d'une unité. La fonction ``fini`` ~~~~~~~~~~~~~~~~~~~~ L'algorithme termine après avoir construit la racine du dendogramme. Implémentez ce critère de terminaison, qui sera simplement vérifié lorsque la liste de noeuds ``NOEUDS`` ne contiendra plus qu'un seul élément (la racine). La fonction ``reviseClusters`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Implémentez la fonction reviseClusters, qui trouve les deux clusters les plus similaires dans ``NOEUDS``, les retire de la liste, les fusionne en un nouveau cluster, et ajoute à la liste ``NOEUDS`` un nouveau noeud correspondant. *Indication* : Pour mesurer la similitude entre deux clusters, utilisez la fonction :py:func:`~clusteringHierarchique.distanceClusters`, dont vous devrez parfaire l'implémentation. .. tip:: Vous pouvez à nouveau utiliser la fonction min (ou :py:func:`~distance.argmin`) pour trouver la paire de noeuds dont les clusters sont les plus similaires. Discussion ~~~~~~~~~~~ Testez votre algorithme sur les deux exemples fournis : ``maladies.py`` et ``profits.py``. Quelles différences obtenez-vous si vous alternez entre les méthodes single-link et complete-link ? Que pensez-vous de la qualité des clusters obtenus, en comparaison avec l'algorithme k-means ? .. -------------- Copyright LIA – 2007. Auteur : thomas.leaute (chez) epfl.ch – 27 mars 2007 – Dernière modification le 26 juin 2007 par l'auteur.