Comment faire un clustering hiérarchique pour une matrice de grande similarité

J'ai environ 50K ensembles de données dont la valeur peut être comprise entre 0 et 10. Je souhaite appliquer le HAC pour regrouper ces données. Mais pour appliquer HAC, je dois préparer une matrice de similarité N * N.Comment faire un clustering hiérarchique pour une matrice de grande similarité

Pour N = 50 K, cette matrice serait simplement trop grande pour être conservée en mémoire, même si j'utilise short.

Y at-il un moyen de faire HAC par lots ou toute autre méthode qui pourrait m'aider à appliquer HAC avec 50K points de données. Je prévois de l'implémenter en Java.

Je suis également préoccupé par le temps total que cela prendrait, toute indication à ce sujet serait très utile.

Source

2015-07-27 Bankelaal

Si vous souhaitez appliquer une approche de regroupement de haut en bas, vous pouvez facilement le distribuer, l'article connexe: http://scgroup.hpclab.ceid.upatras.gr/faculty/stratis/Papers/tm07book.pdf

Longue histoire courte (citation d'un autre article): Après votre première division de noeud, chaque noeud créé peut être expédiés à un processus réparti pour être divisés à nouveau, etc. Chaque processus distribué doit uniquement connaître le sous-ensemble de l'ensemble de données qu'il partage. Seul le processus parent est conscient de l'ensemble de données complet.

L'approche ascendante est beaucoup plus difficile à distribuer et je ne vais pas essayer de suggérer quelque chose ici.

Mais bon, vous n'avez pas besoin d'écrire cela en Java vous-même, les bibliothèques Mahout ou MLLib l'ont déjà, et ils supportent java. Et Hadoop

Quoi qu'il en soit, voici votre exemple en Java pour Hadoop si vous voulez écrire vous-même: http://sujitpal.blogspot.ru/2009/09/hierarchical-agglomerative-clustering.html

Enfin, un bon et un grand travail sur la comparaison des différentes approches réparties pour la classification hiérarchique:

C. F. Olson. "Parallel Algorithms for Hierarchical Clustering." Parallel Computing, 21:1313-1325, 1995, doi:10.1016/0167-8191(95)00017-I.

Source

2015-07-27 14:55:38

Merci pour vos entrées. En ce moment je cherche une solution qui peut fonctionner sur une seule machine. J'ai lu à propos de l'approche descendante, mais selon le wiki, sa complexité temporelle pourrait être 2^N, ce qui est pire que N^2 ou N^3. Et comme je le sais, Mahout ne supporte pas HAC. – Bankelaal

Ensuite, utilisez scikit-learn. Les datacoints 50K + HAC me convient parfaitement, je l'habitude de regrouper un ensemble de documents de 100K avec cela et cela a fonctionné très bien pour moi - cela a pris quelque chose comme 5-10 minutes sur ordinal Core 2 Duo PC. –

Vous voulez dire que 100k * 100k similitude peut être fait en 10 minutes? Vous avez utilisé le haut ou le bas? Quel lien de cluster avez-vous choisi et combien de RAM avez-vous utilisé? – Bankelaal

Il existe différentes méthodes HAC, mais elles sont généralement toutes limitées par la complexité O (n^2). Alors que 50k est encore un nombre faisable de points de données, vous ne serez pas en mesure de l'étendre trop loin. Je ne sais pas quel code vous utilisez, mais vous n'avez pas à stocker explicitement la matrice de similarité de taille N^2, les valeurs de similarité peuvent être calculées à la volée/au besoin. Apprendre le fera sans former explicitement la matrice.

Source

2015-07-27 18:06:03

Merci pour vos contributions, j'ai vérifié le JSAT. Il calcule en fait la matrice de similarité à l'avance, ce qu'il fait c'est qu'il ne calcule pas les diagonales et la partie inférieure du triangle. Mais la matrice de similarité doit encore être calculée à l'avance. Dans mon cas, même si je suis comme JSAT, ma matrice va être trop grande. À l'heure actuelle, je dois le faire sur une seule machine et j'ai de la mémoire 10-15G disponible, mais mon souci est le temps et la complexité de l'espace causera un problème. – Bankelaal

Edward - J'ai réalisé que tu es l'auteur de JSAT. Donc, vous devez être sûr que dans votre implémentation vous ne stockez pas la matrice de similarité. Et je vois aussi que vous avez mis en œuvre à la fois top-down et bottom-up, Pour les points de données de 50 K Si j'ai 10-15G de mémoire puis-je gérer 50K ressources pour HAC, Combien de temps cela pourrait prendre pour le terminer? – Bankelaal

J'ai fait une erreur, le code dans JSAT fait la matrice complète, je dois avoir pensé à du code pour quelque chose d'autre. Scikit ne l'exige pas cependant –

Comment faire un clustering hiérarchique pour une matrice de grande similarité

Répondre

Questions connexes