Clustering spectral en python

Le clustering est un problème d'apprentissage automatique largement utilisé où des points de données similaires sont regroupés pour former un ensemble de clusters. Il est largement utilisé dans des applications telles que les systèmes de recommandation, la détection des anomalies et la segmentation du client. Nous allons passer par une technique de regroupement moderne connue sous le nom Regroupement spectral et son implémentation dans Python en utilisant le sklearn bibliothèque.

Qu'est-ce que le regroupement?

Le clustering est un problème d'apprentissage automatique non surveillé dans lequel il faut diviser les observations «M» en grappes «k», les points du même cluster étant extrêmement similaires et les points dans différents grappes étant très différente. Des problèmes tels que la segmentation du client, les systèmes de recommandation, la détection des anomalies, etc., sont résolus à partir du clustering. Vous connaissez peut-être l'algorithme de clustering K-Means, dans lequel nous n'avons pas d'étiquettes et devons placer chaque point de données dans son cluster. La méthode de clustering spectrale est utilisée pour atteindre le même objectif que la méthode de clustering K-means mais avec une approche basée sur le graphique. L'image ci-dessous montre les trois grappes séparées les unes des autres et ont des points similaires ensemble.

Qu'est-ce que K-means clustering?

Le clustering K-Means implique d'identifier les clusters K de l'ensemble de données qui sont distincts les uns des autres. Seules les variables indépendantes sont utilisées pour créer des clusters. K signifie que le regroupement est un algorithme d'apprentissage non supervisé. Les points de données dans le même cluster sont assez similaires, tandis que les points de données dans différents clusters sont très distincts. Vous commencez par k centres aléatoires et attribuez des éléments à ceux qui sont les plus proches d'eux. Le centre de chaque collection est ensuite recalculé, entraînant de nouveaux centres K. Vous continuez à le faire jusqu'à ce que le nombre d'itérations atteigne un seuil prédéterminé ou que le centre des grappes se déplace à peine. La méthode du coude est couramment utilisée pour déterminer la valeur de k.

Classification vs. Regroupement

La classification est le résultat de l'apprentissage supervisé, ce qui signifie que vous voulez que le système génère une étiquette connue. Par exemple, si vous construisiez un classificateur d'images, il dirait: «C'est un chien, c'est un chat», sur la base d'échantillons de chiens et de chats que vous l'avez montré.

Le regroupement est la conséquence de l'apprentissage non supervisé, ce qui implique que vous avez vu beaucoup d'échantillons mais qui n'ont pas reçu d'étiquettes pour eux. Par exemple, nous pouvons utiliser le clustering pour segmenter les clients du même type à partir des clients de différents types. Il s'agit d'une déclaration de problème largement utilisée qui est résolue à l'aide de clustering.

Qu'est-ce que l'algorithme de clustering spectral?

Le clustering spectral est un algorithme de clustering moderne basé sur la théorie des graphiques. Il a surperformé plusieurs approches de regroupement classiques et évolue toujours. Cet algorithme prend chaque point de données comme un nœud graphique et utilise le partitionnement du graphique pour résoudre le problème de clustering.

Fonctionnement du regroupement spectral

Création d'une structure de données graphique

Vous pouvez visualiser n'importe quel ensemble de données comme un nuage de points, avec m pointe dans n dimensions. Vous pouvez faire un graphique à partir de ces points, les nœuds étant les points et les bords (représentés par w) être pondéré par la similitude des points. Une fois que nous avons nos données sous la forme d'un graphique, nous pouvons générer une matrice d'adjacence en entrant simplement le poids du bord entre les nœuds «i» et «j» dans chaque colonne de la matrice. C'est un m X m matrice symétrique. W est le nom de la matrice d'adjacence.

Projeter les données

Dans cette étape, les données sont projetées dans un espace de dimension inférieure pour se rapprocher les uns des autres dans l'espace dimensionnel inférieur. La formule donne le degré de chaque nœud:

La matrice de degré est ensuite calculée à l'aide de la formule:

Le laplacien du graphique peut être calculé à l'aide de la formule L = D-W. Nous pouvons calculer le spectre de cette matrice, ou ses vecteurs propres disposés du plus important au moins important, maintenant que nous avons le laplacien du graphique. Prendre les vecteurs propres les moins importants «K» vous donne une représentation de chaque nœud dans le graphique dans les dimensions «K», qui représente chaque point de l'ensemble de données. Les plus petites valeurs propres sont liées aux vecteurs propres les moins significatifs. Ceci est un type de réduction de la dimensionnalité qui n'est pas linéaire.

Clustering les données

Cette étape implique principalement de regrouper les données dimensionnelles réduites à l'aide de clustering K-means ou toute autre technique de clustering classique. La matrice laplacienne graphique normalisée est d'abord affectée à chaque nœud. Les données sont ensuite regroupées à l'aide de n'importe quelle méthode standard.

Dans un scénario idéal, vous prévoyez que vos données ne soient pas entièrement connectées, avec des composants connectés distincts pour chaque cluster. Cependant, dans la pratique, c'est rarement le cas: cela dépend de diverses choses, y compris les données elle-même et la façon dont vous concevez votre graphique d'adjacence. En termes d'efficacité, les meilleurs clusters sont séparés, le clustering plus spectral se comporte de manière prévisible: le graphique aura plus d'un composant connecté (idéalement K, le nombre de clusters dans l'ensemble de données), les premières valeurs propres k seront nulles et fonctionnent et fonctionnent K-means dans l'espace créé en prenant les premiers vecteurs propres du graphique Laplacien donnera des résultats assez satisfaisants. Plus les grappes sont étroites, plus les valeurs propres sont de 0, et plus les points de l'espace propre sont proches de Clusters distincts.

K-means vs. Regroupement spectral

Considérez les données ci-dessous.

Même lorsque le vrai nombre de clusters K est connu de l'algorithme, K-means ne parviendra pas à regrouper les données ci-dessus. En effet, K-means est un bon algorithme de clustering de données pour trouver des groupes globulaires comme ceux ci-dessous:

où tous les membres du cluster sont proches les uns des autres (au sens euclidien). Les approches de graphiques telles que le clustering spectral, en revanche, ne regroupent pas les points de données directement dans leur espace de données natif, mais construisent plutôt une matrice de similitude avec le (i, j)_e ligne représentant une distance de similitude entre le i_e et J_e points de données dans votre ensemble de données.

À certains égards, le regroupement spectral est plus général (et puissant) que les k-means car le regroupement spectral est applicable chaque fois que K-means ne l'est pas (utilisez simplement une distance euclidienne simple comme mesure de similitude). Cependant, l'inverse n'est pas vrai. Lorsque vous choisissez l'une de ces stratégies par rapport à l'autre, il y a des préoccupations pratiques à garder à l'esprit. La matrice de données d'entrée est factorisée avec des k-means, tandis que la matrice laplacienne est factorisée avec un regroupement spectral (une matrice dérivée de la matrice de similitude).

Implémentation de clustering spectral à l'aide de Python

Importation des bibliothèques

de Sklearn.Spectralcluster d'importation de cluster
Importer Numpy comme NP
Lire les données
X = np.Array ([[1, 1], [2, 1], [1, 0],
[4, 7], [3, 5], [3, 6]])

Notez que dans cet exemple, nous avons pris les données avec moins de dimensions. Si vous avez des données dimensionnelles plus grandes, vous pouvez appliquer l'analyse des composants principaux (PCA) pour réduire les dimensions des données.

Initialisation de notre modèle

modèle = spectralclustering (n_clusters = 2,
attribution_labels = 'discrétiser',
random_state = 0).ajustement (x)

Obtenez des étiquettes de chaque point de données

imprimer (modèle.Étiquettes_)

Sortir

Array ([1, 1, 1, 0, 0, 0])

Avantages du regroupement spectral

• Le clustering spectral ne suppose pas la forme des données. Il fonctionne bien sur toutes sortes de distributions de données. D'autres algorithmes classiques comme K-means supposent la forme des données comme sphériques.
• Cela fonctionne assez bien lorsque les relations sont à peu près transitives (comme la similitude).
• Nous n'avons pas besoin de l'ensemble de données entièrement en grappe; Juste une matrice de similitude / distance, ou peut-être juste le laplacien, suffira.

Inconvénients du regroupement spectral

• Les vecteurs propres informatiques sont le goulot d'étranglement; Par conséquent, c'est cher pour de très grands ensembles de données.
• Ne fonctionne pas bien avec les ensembles de données bruyants.
• Le nombre de clusters (k) doit être décidé à l'avance.

Des cas d'utilisation de clustering spectral

• Segmentation d'image
• Segmentation de la clientèle
• Résolution de l'entité
• Séquences de protéines regroupement spectral

Conclusion

Nous avons vu comment nous pouvons utiliser le regroupement spectral pour regrouper nos points de données. Nous projetons d'abord les points de données dans une structure de données graphiques, réduisons les dimensions des données, puis appliquons la technique de clustering traditionnelle sur les données réduites. Nous avons ensuite vu avec quelle facilité cet algorithme complexe pouvait être implémenté dans Python en utilisant quelques lignes de code.