algorithme de clustering pour les données non dimensionnelles

J'ai un ensemble de données de milliers de points et un moyen de mesurer la distance entre deux points, mais les points de données n'ont pas de dimensionnalité. je veux un algorithme pour trouver des centres de cluster dans cet ensemble de données. j'imagine que parce que les données n'ont pas de dimensions, un centre de cluster pourrait être composé de plusieurs points de données et d'une tolérance, et l'appartenance au sein du cluster pourrait être déterminée par la moyenne de la distance d'un point de données à chaque point de données du centre de cluster.

veuillez me pardonner si cette question a une solution bien connue, je connais très peu ce genre de problème! mes recherches (très limitées) n'ont révélé que des algorithmes de clustering pour les données dimensionnelles, mais je m'excuse à l'avance si j'ai raté quelque chose d'évident.

Merci!

Si la fonction de distance est une métrique, vous pouvez utiliser soit un regroupement à centres (où le rayon maximal d'une balle est minimisé) soit un cluster à médiane (qui minimise la somme des distances aux centres de cluster). Le regroupement des centres est facile: il suffit de choisir les -points les plus éloignés, et vous êtes assuré d'obtenir une approximation 2 via l'inégalité du triangle (c'est un ancien résultat dû à Gonzalez).k k $k$$k$$k$$k$

Pour le clustering median, il y a eu une tonne de travail, trop à examiner ici. Michael Shindler à UCLA a un bon aperçu des principales idées.$k$

Ces deux problèmes sont NP-dur en général, et sont difficiles à rapprocher à l'intérieur d'un facteur arbitraire. Notez que si vous supprimez la condition d'être une métrique, les choses s'aggravent beaucoup en termes d'approximation.

Une autre approche plus heuristique qui pourrait convenir à votre application consiste à utiliser une technique telle que MDS (mise à l'échelle multidimensionnelle) pour incorporer votre matrice de distance dans un espace euclidien, puis utiliser l'une des nombreuses méthodes de clustering euclidiennes différentes (ou même le clustering -means ). Si vous êtes sûr que votre fonction de distance est une métrique, vous pouvez effectuer une intégration légèrement plus intelligente dans l'espace euclidien et obtenir une garantie prouvable (quoique faible) sur la qualité de votre réponse.$k$

En fin de compte, comme pour la plupart des problèmes de clustering, votre choix final dépend de l'application, de la taille de vos données, etc.

Il existe également un cluster de corrélation , qui a comme informations d'entrée pour chaque paire d'éléments indiquant s'ils appartiennent au même cluster ou à des clusters différents.

Si vous recherchez simplement de bonnes performances empiriques, l'algorithme de propagation d'affinité fonctionne généralement mieux que les k-médianes. Il existe un code disponible dans plusieurs langues et des publications décrivant l'algorithme plus en détail sont ici: http://www.psi.toronto.edu/index.php?q=affinity%20propagation

$s$$c_i \in \mathbf{c}$$i$$s(i, i)$

Votre question semble impliquer que vous recherchez un algorithme avec un temps de calcul décent. Étant donné la taille de vos sommets (ou points), il faudrait créer une représentation graphique pondérée de vos données et utiliser l'algorithme de cluster de Markov (MCL) pour regrouper le graphique.

http://www.micans.org/mcl/

MCL est basé sur des parcours aléatoires à travers des graphiques pondérés et non pondérés pour trouver des sous-graphiques denses. Il est capable de gérer de grands graphiques et a été utilisé dans de nombreux programmes bioinformatiques bien connus et bien utilisés (tels que BLAST). -Boucher

Considérons l' algorithme k-le plus proche voisin .