Regroupement non supervisé avec un nombre inconnu de clusters

Question

J'ai un grand ensemble de vecteurs en 3 dimensions. J'ai besoin de regrouper ces vecteurs en fonction de la distance euclidienne de sorte que tous les vecteurs dans un cluster particulier aient une distance euclidienne entre eux inférieure à un seuil "T".

Je ne sais pas combien de clusters existent. À la fin, il peut y avoir des vecteurs individuels qui ne font pas partie d'un cluster parce que leur distance euclidienne n'est pas inférieure à "T" avec aucun des vecteurs de l'espace.

Quels algorithmes / approches existants devraient être utilisés ici?

Answer 1

Vous pouvez utiliser le regroupement hiérarchique. C'est une approche plutôt basique, donc il existe de nombreuses implémentations disponibles. Par exemple, il est inclus dans scipy de Python.

Voyez par exemple le script suivant :

import matplotlib.pyplot as plt
import numpy
import scipy.cluster.hierarchy as hcluster

# générer 3 clusters de 100 points environ et un point orphelin
N=100
data = numpy.random.randn(3*N,2)
data[:N] += 5
data[-N:] += 10
data[-1:] -= 20

# regroupement
thresh = 1.5
clusters = hcluster.fclusterdata(data, thresh, criterion="distance")

# tracé
plt.scatter(*numpy.transpose(data), c=clusters)
plt.axis("equal")
title = "seuil : %f, nombre de clusters : %d" % (thresh, len(set(clusters)))
plt.title(title)
plt.show()

Ce qui produit un résultat similaire à l'image suivante.

Le seuil donné en tant que paramètre est une valeur de distance sur la base de laquelle la décision est prise quant à savoir si les points / clusters seront fusionnés en un autre cluster. La métrique de distance utilisée peut également être spécifiée.

Notez qu'il existe diverses méthodes pour calculer la similarité intra-/inter-cluster, par exemple la distance entre les points les plus proches, la distance entre les points les plus éloignés, la distance aux centres des clusters, etc. Certaines de ces méthodes sont également prises en charge par le module de regroupement hiérarchique de scipy (liaison simple/complète/moyenne...). Selon votre message, je pense que vous voudriez utiliser le regroupement à liaison complète.

Remarquez que cette approche permet également des petits clusters (un seul point) s'ils ne remplissent pas le critère de similarité des autres clusters, c'est-à-dire le seuil de distance.

---

Il existe d'autres algorithmes qui fonctionneront mieux, ce qui sera pertinent dans des situations avec beaucoup de points de données. Comme le suggèrent d'autres réponses/commentaires, vous voudrez peut-être également regarder l'algorithme DBSCAN :

• https://en.wikipedia.org/wiki/DBSCAN
• http://scikit-learn.org/stable/auto_examples/cluster/plot_dbscan.html
• http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html#sklearn.cluster.DBSCAN

---

Pour un bel aperçu de ces algorithmes et d'autres, jetez également un œil à cette page de démonstration (de la bibliothèque scikit-learn de Python) :

• http://scikit-learn.org/stable/modules/clustering.html

Image copiée de cet endroit :

Comme vous pouvez le voir, chaque algorithme fait certaines hypothèses sur le nombre et la forme des clusters qui doivent être pris en compte. Que ce soit des hypothèses implicites imposées par l'algorithme ou des hypothèses explicites spécifiées par la paramétrisation.

Answer 2

La réponse de moooeeeep recommandait d'utiliser le clustering hiérarchique. Je voulais donner des détails sur comment choisir le seuil du clustering.

Une façon de procéder est de calculer des clusterings basés sur différents seuils t1, t2, t3,... et ensuite calculer une métrique de la "qualité" du clustering. L'idée est que la qualité d'un clustering avec le nombre de clusters optimal aura la valeur maximale de la métrique de qualité.

Un exemple d'une bonne métrique de qualité que j'ai utilisée par le passé est Calinski-Harabasz. En bref : vous calculez les distances moyennes inter-clusters et vous les divisez par les distances intra-cluster. L'attribution de clustering optimale aura des clusters qui sont séparés les uns des autres autant que possible, et des clusters qui sont les plus "compacts".

En passant, vous n'êtes pas obligé d'utiliser le clustering hiérarchique. Vous pouvez également utiliser quelque chose comme le clustering k-means, le précalculer pour chaque k, et ensuite choisir le k qui a le score Calinski-Harabasz le plus élevé.

Dites-moi si vous avez besoin de plus de références, et je fouillerai dans mon disque dur à la recherche d'articles.

Answer 3

Découvrez l'algorithme DBSCAN. Il regroupe en fonction de la densité locale des vecteurs, c'est-à-dire qu'ils ne doivent pas être plus éloignés de plus de quelques distances ε, et peut déterminer automatiquement le nombre de clusters. Il prend également en compte les valeurs aberrantes, c'est-à-dire les points n'ayant pas un nombre suffisant de voisins ε, comme n'étant pas partie d'un cluster. La page Wikipedia propose quelques implémentations.

Answer 4

Utilisez OPTICS, qui fonctionne bien avec de grands ensembles de données.

OPTICS: Ordre des points pour identifier la structure de regroupement Étroitement lié à DBSCAN, trouve un échantillon central de haute densité et étend les clusters à partir de ceux-ci 1. Contrairement à DBSCAN, il conserve la hiérarchie des clusters pour un rayon de voisinage variable. Mieux adapté à une utilisation sur de grands ensembles de données que l'implémentation actuelle de DBSCAN dans sklearn

from sklearn.cluster import OPTICS
db = OPTICS(eps=3, min_samples=30).fit(X)

Ajustez finement eps, min_samples selon vos besoins.

Answer 5

Je veux ajouter à la réponse de moooeeeep en utilisant le clustering hiérarchique. Cette solution a fonctionné pour moi, bien que ce soit assez "aléatoire" de choisir une valeur de seuil. En me référant à d'autres sources et en testant par moi-même, j'ai trouvé une méthode meilleure et le seuil pourrait être facilement choisi par le dendrogramme :

from scipy.cluster import hierarchy
from scipy.spatial.distance import pdist
import matplotlib.pyplot as plt

ori_array = ["Votre_liste_ici"]
ward_array = hierarchy.ward(pdist(ori_array))
dendrogram = hierarchy.dendrogram(hierarchy.linkage(ori_array, method  = "ward"))
plt.title('Dendrogramme')
plt.xlabel('Clients')
plt.ylabel('Distances euclidiennes')
plt.show()

Vous verrez le graphique comme ceci cliquez ici. Ensuite, en traçant la ligne horizontale, disons à une distance = 1, le nombre de conjonctions sera le nombre de clusters souhaité. Donc ici, je choisis un seuil = 1 pour 4 clusters.

seuil = 1
clusters_list = hierarchy.fcluster(ward_array, seuil, criterion="distance")
print("Liste de clustering : {}".format(clusters_list))

Maintenant, chaque valeur dans clusters_list sera un identifiant de cluster attribué au point correspondant dans ori_array.