Cluster efficace dans l'espace

La plupart des algorithmes de clustering que j'ai vus commencent par créer des distances de chaque point entre tous les points, ce qui devient problématique sur des ensembles de données plus importants. Y en a-t-il un qui ne le fait pas? Ou le fait-il dans une sorte d'approche partielle / approximative / échelonnée?

Quel algorithme / implémentation de clustering prend moins d'espace O (n ^ 2)?

Existe-t-il une liste d'algorithmes et de leurs besoins en temps et en espace quelque part?

K-Means et Mean-Shift utilisent les descripteurs d'échantillon bruts (pas besoin de pré-calculer une matrice d'affinité).

Sinon, pour le regroupement spectral ou le regroupement par itération de puissance, vous pouvez utiliser une représentation matricielle clairsemée (par exemple, des lignes clairsemées compressées) de la matrice d'affinité k-plus proches voisins (pour une métrique de distance ou d'affinité). Si k est petit (disons 5 ou 10). Vous obtiendrez une représentation très économe en espace (2 * n_échantillons * k * 8 octets pour les valeurs à virgule flottante double précision).

$O(n\log n)$$O(\log n)$

$O(n^2)$

$n$$n^2$$O(n^3)$

$O(n^2)$$n\times n$$k$$O(n^2)$$O(n)$$O(n \log n)$$O(n)$

Bonne question. Une méthode de l'homme de paille pour, disons, 3 voisins les plus proches consiste à échantillonner Nsample voisins de chaque point de données, en gardant le 3. le plus proche. , facilement tracé pour vos données. Une astuce supplémentaire consiste à vérifier ensuite les voisins des voisins, pour voir si l'un d'eux est plus proche que les voisins directs. De plus, si les données d'entrée sont déjà bien mélangées, échantillonnez par blocs, sinon le cache se débordera.

(Ajouté): voir fastcluster dans R et je crois en SciPy v0.11.
Pour le texte, voir google-all-pairs-similarity-search .

Répétez: «Une mesure de dissimilarité appropriée est beaucoup plus importante pour obtenir le succès du clustering que le choix de l'algorithme de clustering» - en choisissant la méthode de clustering .