Accueil🇫🇷Chercher

Partitionnement de données diffus

Le partitionnement diffus ou souple (en anglais, fuzzy clustering) est une forme de partitionnement de données dans laquelle chaque observation peut appartenir à plusieurs groupes (ou clusters).

Le partitionnement de données implique d'assigner des observations à des groupes de telle sorte que les éléments d'un même groupe soient aussi similaires que possible, tandis que les éléments appartenant à différents groupes sont aussi dissemblables que possible. Ces groupes, ou clusters, sont identifiés par des mesures de similarité, telles qu'une distance, connectivité ou intensité. Différentes mesures de similarité peuvent être choisies en fonction des données ou de l'application[1].

Comparaison avec le partitionnement fort

Dans le partitionnement non-diffus (également appelé partitionnement fort), les données sont divisées en groupes distincts, où chaque observation ne peut appartenir qu'à un seul groupe. Dans le partitionnement diffus, les observations peuvent appartenir à plusieurs groupes. Par exemple, dans le partitionnement fort, une pomme peut être rouge ou verte ; alors que dans un partitionnement souple, une pomme peut aussi être rouge et verte.

Scores d'appartenance

Chaque observation a un score ou degré d'appartenance à un groupe, pour chacun des groupes. Ces scores indiquent le degré d'appartenance des observations à chaque groupe. Ainsi, les points situés loin du centre d'un groupe pourront avoir des scores d'appartenance faibles et être considérés comme dans le groupe à un degré moindre que les points au centre du groupe.

C-moyennes

L'une des méthodes de partitionnement diffus les plus largement utilisés est l'algorithme des C-moyennes (en anglais Fuzzy C-means).

Histoire

Le partitionnement en C-moyennes a été développé par J. C. Dunn en 1973[2], et amélioré par James C. Bezdek en 1981[3].

Description générale

L'algorithme de partitionnement en C-moyennes est très similaire à celui des K-moyennes :

  • Fixer un nombre de groupes ;
  • Attribuer des coefficients au hasard à chaque observation pour être dans les groupes ;
  • Répéter les étapes suivantes jusqu'à la convergence de l'algorithme (c'est-à-dire que la variation des coefficients entre deux itérations ne dépasse pas le seuil de sensibilité ) :
    • Calculer le centroïde de chaque groupe ;
    • Pour chaque observation, calculer ses coefficients d'appartenance aux différents groupes.

Centroïde

Tout point a un ensemble de coefficients correspondant aux degrés d'appartenance aux groupes. Ainsi, le coefficient d'appartenance au ème groupe est noté . Avec des C-moyennes, le centroïde (ou barycentre) d'un groupe est la moyenne de tous les points pondérés par leur degré d'appartenance au groupe, ou, mathématiquement :

où est l'hyperparamètre qui contrôle le degré de diffusion du groupe. m est appelé paramètre de diffusion ou fuzzifier.

Algorithme

L'algorithme des C-moyennes tente de partitionner une collection finie de éléments en une collection de c groupes par rapport à un critère donné.

Étant donné un ensemble fini de données, l'algorithme renvoie une liste de centres de groupe et une matrice de partition

, où chaque élément indique dans quelle mesure l'élément appartient au groupe .

Le C-moyennes vise à minimiser une fonction objectif :

où:

Comparaison avec le partitionnement en K-moyennes

Le partitionnement en K-moyennes (en anglais K-means) tente également de minimiser la fonction objectif mentionnées ci-dessus. La fonction objectif des C-moyennes diffère de celle des K-moyennes par l'addition des valeurs d'appartenance et le fuzzifier (paramètre de diffusion), , avec . Le fuzzifier détermine le niveau de diffusion du groupe. Un grand se traduit par des scores d'appartenance plus petits, , et par conséquent, des groupes plus diffus. À la limite , les scores d'appartenance, , convergent vers 0 ou 1, ce qui implique un partitionnement net. L'algorithme minimise également la variance intra-groupe, mais présente les mêmes problèmes que les K-moyennes ; le minimum est un minimum local, et les résultats dépendent du choix initial des poids.

Applications

Les problèmes de partitionnement ont des applications dans la science des surfaces, la biologie, la médecine, la psychologie, l'économie et de nombreuses autres disciplines.

Bioinformatique

Dans le domaine de la bioinformatique, le partitionnement est couramment utilisé. Il est par exemple utilisé comme technique de reconnaissance de formes pour analyser les données d'expression génique à partir de puces à ADN ou autres technologies[4]. Dans ce cas, les gènes avec des modes d'expression similaires sont regroupés dans le même groupe, et des groupes différents affichent des modèles d'expression bien distincts. L'utilisation du partitionnement peut fournir des informations sur la fonction et la régulation des gènes[5].

Le partitionnement souple permet aux gènes d'appartenir à plus d'un groupe, donc il permet l'identification de gènes qui sont conditionnellement co-régulés ou co-exprimés. Par exemple, un gène peut être influencé par plusieurs facteurs de transcription ou peut coder pour une protéine qui a plusieurs fonctions. Ainsi, le partitionnement souple peut être préférable dans ces cas.

Analyse d'images

Les C-moyennes ont été un outil très important pour le traitement d'images, pour le partitionnement d'objets au sein d'une image. Dans les années 1970, les mathématiciens ont introduit un paramètre spatial dans l'algorithme des C-moyennes afin d'améliorer la précision du partitionnement en présence de bruit[6]. De plus, des algorithmes des C-moyennes ont été utilisés pour distinguer différentes activités à l'aide de caractéristiques basées sur des images telles que les moments Hu et Zernike[7]. Alternativement, un modèle de logique floue peut être décrit sur des ensembles flous qui sont définis sur trois composantes de l'espace colorimétrique HSL. Dans ce cas, les fonctions d'appartenance visent à décrire les couleurs en suivant l'intuition humaine d'identification des couleurs[8].

Notes et références

  1. « Fuzzy Clustering », reference.wolfram.com (consulté le )
  2. J. C. Dunn, « A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters », Journal of Cybernetics, vol. 3, no 3,‎ , p. 32–57 (ISSN 0022-0280, DOI 10.1080/01969727308546046)
  3. Bezdek, James C. (1981). Pattern Recognition with Fuzzy Objective Function Algorithms. (ISBN 0-306-40671-3).
  4. (en) Faramarz Valafar, « Pattern Recognition Techniques in Microarray Data Analysis », Annals of the New York Academy of Sciences, vol. 980, no 1,‎ , p. 41–64 (ISSN 1749-6632, PMID 12594081, DOI 10.1111/j.1749-6632.2002.tb04888.x)
  5. (en) Amir Ben-Dor, Ron Shamir et Zohar Yakhini, « Clustering Gene Expression Patterns », Journal of Computational Biology, vol. 6, nos 3-4,‎ , p. 281–297 (ISSN 1066-5277 et 1557-8666, DOI 10.1089/106652799318274, lire en ligne, consulté le )
  6. (en) Mohamed N. Ahmed, Sameh M. Yamany, Nevin Mohamed et Aly A. Farag, « A Modified Fuzzy C-Means Algorithm for Bias Field Estimation and Segmentation of MRI Data », IEEE Transactions on Medical Imaging, vol. 21, no 3,‎ , p. 193–199 (PMID 11989844, DOI 10.1109/42.996338, lire en ligne).
  7. (en) Tanvi Banerjee, James C. Keller, Marjorie Skubic et Erik Stone, « Day or Night Activity Recognition From Video Using Fuzzy Clustering Techniques », IEEE Transactions on Fuzzy Systems, vol. 22, no 3,‎ , p. 483–493 (DOI 10.1109/TFUZZ.2013.2260756)
  8. (en) Alireza Kashanipour, Amir Reza Kashanipour, Nargess Shamshiri Milani, Peyman Akhlaghi et Kaveh Khezri, Robust Color Classification Using Fuzzy Reasoning and Genetic Algorithms in RoboCup Soccer Leagues, vol. 5001, coll. « Lecture Notes in Computer Science », , 548–555 p. (ISBN 978-3-540-68846-4, DOI 10.1007/978-3-540-68847-1_59)
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.