Algorithme de clustering basé sur la projection sur des ensembles convexes (POCS)

POCS : Projections sur des ensembles convexes. En mathématiques, un ensemble convexe est un ensemble dans lequel tout segment de droite entre deux points quelconques se trouve dans l'ensemble. La projection est l'opération consistant à mapper un point sur un sous-espace dans un autre espace. Étant donné un ensemble convexe et un point, vous opérez en trouvant la projection du point sur l'ensemble convexe. La projection est le point de l'ensemble convexe qui est le plus proche du point et peut être calculée en minimisant la distance entre ce point et tout autre point de l'ensemble convexe. Puisqu'il s'agit d'une projection, nous pouvons mapper les caractéristiques sur un ensemble convexe dans un autre espace, afin que des opérations telles que le regroupement ou la réduction de dimensionnalité puissent être effectuées.

Cet article passe en revue un algorithme de clustering basé sur la méthode de projection d'ensembles convexes, c'est-à-dire un algorithme de clustering basé sur POCS. L'article original a été publié à l'IWIS2022.

Ensemble convexe

Un ensemble convexe est défini comme un ensemble de points de données, dans lequel le segment de ligne reliant deux points x1 et x2 quelconques dans l'ensemble est complètement inclus dans cet ensemble. Selon la définition de l'ensemble convexe, l'ensemble vide ∅, l'ensemble simple, le segment de droite, l'hyperplan et la sphère euclidienne sont tous considérés comme des ensembles convexes. Un point de données est également considéré comme un ensemble convexe car il s'agit d'un ensemble singleton (un ensemble avec un seul élément). Cela ouvre une nouvelle voie pour appliquer le concept de POCS aux points de données clusterisés.

Projection d'ensembles convexes (POCS)

Les méthodes POCS peuvent être grossièrement divisées en deux types : alternées et parallèles.

1. POC alterné

Partez de n'importe quel point de l'espace de données, et la projection alternée de ce point vers deux (ou plus) ensembles convexes qui se croisent convergeront vers un point dans l'intersection de l'ensemble, comme la figure suivante :

Lorsque les ensembles convexes sont disjoints, les projections alternées convergeront vers des cycles limites gloutons qui dépendent de l'ordre de projection.

2. POCS parallèles

Différent de la forme alternée, les POCS parallèles projettent simultanément des points de données vers tous les ensembles convexes, et chaque projection a un poids important. Pour deux ensembles convexes sécants non vides, similaire à la version alternée, la projection parallèle converge vers un point à l'intersection des ensembles.

Dans le cas où les ensembles convexes ne se coupent pas, la projection convergera vers une solution minimale. L’idée principale de l’algorithme de clustering basé sur les POC vient de cette fonctionnalité.

Pour plus de détails sur les POCS, vous pouvez consulter l'article original

Algorithme de clustering basé sur les POC

Profitant de la convergence de la méthode POCS parallèle, l'auteur de l'article a proposé un algorithme de clustering très simple mais efficace dans une certaine mesure. Algorithme de classe. L'algorithme fonctionne de manière similaire à l'algorithme K-Means classique, mais il existe des différences dans la manière dont chaque point de données est traité : l'algorithme K-Means pondère l'importance de chaque point de données de la même manière, mais l'algorithme de clustering basé sur les POC. Chaque point de données est pondéré différemment en importance, qui est proportionnelle à la distance entre le point de données et le prototype du cluster.

Le pseudo-code de l'algorithme est le suivant :

Résultats expérimentaux

L'auteur a testé les performances de l'algorithme de clustering basé sur les POC sur certains ensembles de données de référence publiques. Le tableau ci-dessous résume les descriptions de ces ensembles de données.

L'auteur a comparé les performances de l'algorithme de clustering basé sur les POC avec d'autres méthodes de clustering traditionnelles, notamment les algorithmes k-means et flous c-means. Le tableau suivant résume l'évaluation en termes de temps d'exécution et d'erreur de clustering.

Les résultats du clustering sont présentés ci-dessous :

Exemple de code

Nous utilisons cet algorithme sur un ensemble de données très simple. L'auteur a publié un package à usage direct, que nous pouvons utiliser directement pour des applications :

pip install pocs-based-clustering

Créez un ensemble de données simple de 5000 points de données centré sur 10 clusters :

# Import packages
 import time
 import matplotlib.pyplot as plt
 
 from sklearn.datasets import make_blobs
 from pocs_based_clustering.tools import clustering
 
 
 # Generate a simple dataset
 num_clusters = 10
 X, y = make_blobs(n_samples=5000, centers=num_clusters, 
 cluster_std=0.5, random_state=0)
 
 plt.figure(figsize=(8,8))
 plt.scatter(X[:, 0], X[:, 1], s=50)
 plt.show()

Effectuez un clustering et affichez les résultats :

# POSC-based Clustering Algorithm
 centroids, labels = clustering(X, num_clusters, 100)
 
 # Display results
 plt.figure(figsize=(8,8))
 plt.scatter(X[:, 0], X[:, 1], c=labels, s=50, cmap='viridis')
 plt.scatter(centroids[:, 0], centroids[:, 1], s=100, c='red')
 plt.show()

总结

我们简要回顾了一种简单而有效的基于投影到凸集(POCS)方法的聚类技术，称为基于POCS的聚类算法。该算法利用POCS的收敛特性应用于聚类任务，并在一定程度上实现了可行的改进。在一些基准数据集上验证了该算法的有效性。

论文的地址如下：https://arxiv.org/abs/2208.08888

作者发布的源代码在这里：https://github.com/tranleanh/pocs-based-clustering

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!