Partitionnement de données diffus

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

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

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

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

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

L'algorithme des C-moyennes tente de partitionner une collection finie de ${\displaystyle n}$ éléments ${\displaystyle 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 ${\displaystyle c}$ centres de groupe ${\displaystyle C=\{\mathbf {c} _{1},...,\mathbf {c} _{c}\}}$ et une matrice de partition

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

Le C-moyennes vise à minimiser une fonction objectif :

${\displaystyle {\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ù:

${\displaystyle 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}}}}.}$

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

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.

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