algorithme de clustering pour les données non dimensionnelles

12

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!

pot de peinture
la source
Pourquoi la non-dimensionnalité rend ce problème spécial?
Raphael
1
Certains algorithmes que j'ai vus pour le clustering (vraiment juste k-means) nécessitent la génération de points de données aléatoires comme graines, ce qui n'est pas possible avec des données sans dimension. Ainsi, l'exigence particulière est que les centres de cluster doivent être représentés par un ensemble de points de données existants (peut-être pondérés).
paintcan

Réponses:

15

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 kkkkk

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.

Suresh Venkat
la source
3
Merci pour l'aperçu rapide et clair. Il me faudra au moins quelques jours pour déterminer si vous avez répondu à ma question. Il semble que j'ai beaucoup à apprendre avant de comprendre suffisamment mon problème :)
paintcan
5

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.

Warren Schudy
la source
oui, c'est un autre bon exemple. Et bien sûr, Warren est un expert en la matière! Je ne sais pas si l'entrée de l'OP était +/- cependant, ou pouvait être convertie via un seuillage. si tel est le cas, c'est certainement une option viable.
Suresh Venkat
5

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

is(i,ci)

scicis(i,i)

dan_x
la source
5

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

Christina Boucher
la source
1

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

Raphael
la source
Raphael, l'algorithme k-NN n'est pas vraiment un algorithme de clustering, n'est-ce pas? sauf si vous retirez à plusieurs reprises les k voisins d'un nœud?
Suresh Venkat
k