Clustering de corrélation - Correlation clustering
Le clustering est le problème du partitionnement des points de données en groupes en fonction de leur similitude. Le clustering de corrélation fournit une méthode pour regrouper un ensemble d'objets dans le nombre optimal de clusters sans spécifier ce nombre à l'avance.
description du problème
Dans l'apprentissage automatique , la mise en cluster de corrélation ou l' édition de cluster opère dans un scénario où les relations entre les objets sont connues au lieu des représentations réelles des objets. Par exemple, étant donné un graphique pondéré où le poids de bord indique si deux nœuds sont similaires (poids de bord positif) ou différents (poids de bord négatif), la tâche consiste à trouver un clustering qui maximise les accords (somme des poids de bord positif dans un cluster plus la valeur absolue de la somme des poids des bords négatifs entre les clusters) ou minimise les désaccords (valeur absolue de la somme des poids des bords négatifs au sein d'un cluster plus la somme des poids des bords positifs entre les clusters). Contrairement à d'autres algorithmes de clustering, cela ne nécessite pas de choisir le nombre de clusters à l'avance car l'objectif, de minimiser la somme des poids des arêtes coupées, est indépendant du nombre de clusters.
Il peut ne pas être possible de trouver un clustering parfait, où tous les éléments similaires sont dans un cluster tandis que tous les éléments différents sont dans des clusters différents. Si le graphe admet en effet un clustering parfait, alors simplement supprimer tous les bords négatifs et trouver les composants connectés dans le graphe restant renverra les clusters requis.
Mais, en général, un graphe peut ne pas avoir un clustering parfait. Par exemple, étant donné les nœuds a, b, c tels que a, b et a, c sont similaires tandis que b, c sont différents, un clustering parfait n'est pas possible. Dans de tels cas, la tâche consiste à trouver un clustering qui maximise le nombre d'accords (nombre de + arêtes à l'intérieur des clusters plus le nombre d'arêtes - entre les clusters) ou minimise le nombre de désaccords (le nombre d'arêtes - à l'intérieur des clusters plus le nombre de + arêtes entre les clusters). Ce problème de maximisation des accords est NP-complet (le problème de la coupe multi-voies se réduit à la maximisation des accords pondérés et le problème du partitionnement en triangles peut être réduit à la version non pondérée).
Algorithmes
Bansal et coll. Discutez de la preuve d'exhaustivité NP et présentez également à la fois un algorithme d'approximation à facteur constant et un schéma d'approximation en temps polynomial pour trouver les clusters dans ce contexte. Ailon et coll. proposer un algorithme d'approximation aléatoire pour le même problème.
CC-Pivot(G=(V,E+,E−))
Pick random pivot i ∈ V
Set , V'=Ø
For all j ∈ V, j ≠ i;
If (i,j) ∈ E+ then
Add j to C
Else (If (i,j) ∈ E−)
Add j to V'
Let G' be the subgraph induced by V'
Return clustering C,CC-Pivot(G')
Les auteurs montrent que l'algorithme ci-dessus est un algorithme à 3 approximations pour le clustering de corrélations. Le meilleur algorithme d'approximation en temps polynomial connu à l'heure actuelle pour ce problème réalise une approximation de ~ 2,06 en arrondissant un programme linéaire, comme le montrent Chawla , Makarychev, Schramm et Yaroslavtsev .
Karpinski et Schudy ont prouvé l'existence d'un schéma d'approximation polynomiale du temps (PTAS) pour ce problème sur des graphes complets et un nombre fixe de clusters.
Nombre optimal de clusters
En 2011, Bagon et Galun ont montré que l'optimisation de la fonction de clustering de corrélation est étroitement liée aux méthodes d' optimisation discrète bien connues . Dans leur travail, ils ont proposé une analyse probabiliste du modèle implicite sous-jacent qui permet à la fonction de regroupement par corrélation d'estimer le nombre sous-jacent de grappes. Cette analyse suggère que la fonctionnelle suppose un a priori uniforme sur toutes les partitions possibles, quel que soit leur nombre de clusters. Ainsi, un a priori non uniforme sur le nombre de clusters émerge.
Plusieurs algorithmes d'optimisation discrets sont proposés dans ce travail qui évoluent gracieusement avec le nombre d'éléments (les expériences montrent des résultats avec plus de 100 000 variables). Les travaux de Bagon et Galun ont également évalué l'efficacité de la récupération du nombre sous-jacent de clusters dans plusieurs applications.
Clustering de corrélation (exploration de données)
Le regroupement par corrélation se rapporte également à une tâche différente, où les corrélations entre les attributs de vecteurs de caractéristiques dans un espace de grande dimension sont supposées exister pour guider le processus de regroupement . Ces corrélations peuvent être différentes dans différents clusters, donc une décorrélation globale ne peut pas réduire cela à un clustering traditionnel (non corrélé).
Les corrélations entre les sous-ensembles d'attributs se traduisent par différentes formes spatiales de clusters. Par conséquent, la similitude entre les objets de cluster est définie en tenant compte des modèles de corrélation locaux. Avec cette notion, le terme a été introduit en même temps que la notion discutée ci-dessus. Différentes méthodes de mise en cluster de corrélation de ce type sont décrites dans et la relation avec différents types de mise en cluster est abordée dans. Voir également Mise en cluster de données de grande dimension .
Le clustering de corrélation (selon cette définition) peut être étroitement lié au biclustering . Comme dans le biclustering, le but est d'identifier des groupes d'objets qui partagent une corrélation dans certains de leurs attributs; où la corrélation est généralement typique pour les grappes individuelles.