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.

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, et amélioré par James C. Bezdek en 1981.

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é $\varepsilon$) :
  • Calculer le centroïde de chaque groupe ;
  • Pour chaque observation, calculer ses coefficients d'appartenance aux différents groupes.

Centroïde

Tout point $x$ a un ensemble de coefficients correspondant aux degrés d'appartenance aux groupes. Ainsi, le coefficient d'appartenance au $k$ème groupe est noté $w_{k}(x)$. 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 :

$c_{k}={{\sum _{x}{w_{k}(x)}^{m}x} \over {\sum _{x}{w_{k}(x)}^{m}}},$

où $m$ 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 $n$ éléments $X=\{\mathbf {x} _{1},...,\mathbf {x} _{n}\}$ 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 $c$ centres de groupe $C=\{\mathbf {c} _{1},...,\mathbf {c} _{c}\}$ et une matrice de partition

$W=w_{i,j}\in [0,1],\;i=1,...,n,\;j=1,...,c$, où chaque élément $w_{ij}$ indique dans quelle mesure l'élément $\mathbf {x} _{i}$ appartient au groupe $\mathbf {c} _{j}$ .

Le C-moyennes vise à minimiser une fonction objectif :

${\underset {C}{\operatorname {arg\,min} }}\sum _{i=1}^{n}\sum _{j=1}^{c}w_{ij}^{m}\left\|\mathbf {x} _{i}-\mathbf {c} _{j}\right\|^{2},$

où:

$w_{ij}={\frac {1}{\sum _{k=1}^{c}\left({\frac {\left\|\mathbf {x} _{i}-\mathbf {c} _{j}\right\|}{\left\|\mathbf {x} _{i}-\mathbf {c} _{k}\right\|}}\right)^{\frac {2}{m-1}}}}.$

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 $w_{ij}$ et le fuzzifier (paramètre de diffusion), $m\in R$, avec $m\geq 1$. Le fuzzifier $m$ détermine le niveau de diffusion du groupe. Un grand $m$ se traduit par des scores d'appartenance plus petits, $w_{ij}$, et par conséquent, des groupes plus diffus. À la limite $m=1$, les scores d'appartenance, $w_{ij}$, 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. 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.

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. 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. 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.