Le clustering hiérarchique de 1 million d'objets

Quelqu'un peut-il m'indiquer un clustering hiérarchique de l'outil (de préférence en python) qui peuvent cluster ~1 Million d'objets? J'ai essayé hcluster et aussi Orange.

hcluster avait des problèmes avec 18k d'objets. Orange a réussi à cluster 18k objets en quelques secondes, mais a échoué avec 100 objets (saturé la mémoire et, éventuellement, s'est écrasé).

Je suis en cours d'exécution sur un Xeon 64 bits CPU (2.53 GHz) et de 8 go de RAM + 3 GO de swap sur Ubuntu 11.10.

  • sont vos points en 2d, 3d, 10d, 128d ?
  • Je ne comprends pas ce que vous entendez par là. En tant QUE tel, la limitation semble provenir du fait qu'un nxn matrice de distance de 1M objets cant tenir en mémoire, et chaque de la le regroupement des bibliothèques, j'ai indiqué ci-dessus (orange et scipy) prendre un en mémoire matrice de distance en entrée (ce qui n'est pas possible de fournir en entrée pour 1M objets...)
  • les points/objets sont de simples fichiers texte, que je suis en train de cluster basé sur le texte qu'ils contiennent.... pouvez-vous également m'expliquer si c'est en 2d ou quoi? merci.
  • L'idée de la 2d ou de la nd est de qui fonction de la dimension que vous exploitez? Donc, si vous vous attachez à chacun de le mot "longueur" et "départ" lettre de fonctionnalités, ce serait 2d fonctionnalité de l'espace. Highdimensional et sparsed de données nécessite des structures de données pour faire efficace de clustering.
InformationsquelleAutor Atish Kathpal | 2012-02-06
  1. 11

    À battre en O(n^2), vous devrez d'abord à réduire votre 1M de points (documents)
    par exemple de 1000 piles de 1000 points chacun, ou de 100 piles de 10k chacun, ou ...

    Deux approches possibles:

    • construire un arbre hiérarchique de dire 15k points, puis ajouter le reste un par un:
      temps ~ 1M * treedepth

    • d'abord construire des 100 ou de 1000 à plat des clusters,
      puis construire votre arbre hiérarchique de l'100 ou 1000 cluster centres.

    Comment bien l'un de ces pourrait fonctionner dépend de façon critique
    sur la taille et la forme de votre arborescence cible --
    combien de niveaux, combien de feuilles ?

    Quel logiciel utilisez-vous,
    et combien d'heures ou de jours que vous avez à faire le clustering ?

    Pour la plate-approche cluster,
    K-d_tree s
    beau travail pour points en 2d, 3d, 20d, même 128d-pas votre cas.
    Je sais presque rien sur le clustering de texte;
    Localité-sensitive_hashing ?

    Prendre un coup d'oeil à scikit-learn clustering --
    il y a plusieurs méthodes, y compris DBSCAN.

    Ajoutée: voir également

    google-tous-paires-la similitude de recherche
    "Algorithmes pour trouver toutes les paires de vecteurs dans éparses vecteur de données", Beyardo et el. 2007

    De manière hiérarchique-clusterization-heuristiques

    • Je ne pense pas qu'il existe une manière générale, pour battre O(n^2) pour clustering hiérarchique. Vous pouvez faire certaines choses pour le cas particulier de la liaison simple (voir ma réponse), et bien sûr, vous pouvez utiliser autres algorithmes (par exemple DBSCAN). Ce qui est beaucoup plus judicieux pour cette grande les données de toute façon que clustering hiérarchique. Notez que scikit-learns DBSCAN est O(n^2), comme il le fait autant que je sache, ne pas utiliser les index.
    • Sur O(n^2): si vous accepter un taux d'erreur supérieur, vous pouvez échantillon (mon premier trivial suggestion), ou de la LSH. Il y a beaucoup de articles sur rapide de clustering certains d'entre eux en écriture seule. Sur le clustering hiérarchique, je suis d'accord, mais ce serait bien si l'OP dirais comment grand un arbre, il ou elle le veut, et pourquoi.
    InformationsquelleAutor denis
  2. 15

    Le problème est probablement qu'ils vont essayer de calculer le plein 2D matrice de distance (environ 8 GO naïvement avec la double précision), puis leur algorithme sera exécuté dans O(n^3) temps de toute façon.

    Vous devriez sérieusement envisager d'utiliser un différents algorithme de clustering. La classification hiérarchique est lente et les résultats ne sont pas du tout convaincante habituellement. En particulier pour des millions d'objets, où vous ne pouvez pas il suffit de regarder le dendrogramme de choisir la coupe.

    Si vous voulez vraiment continuer de clustering hiérarchique, je pense que ELKI (Java si) a un O(n^2) mise en œuvre de SLINK. Qui à 1 million d'objets doit être d'environ 1 million de fois plus rapide. Je ne sais pas si ils ont déjà CLINK, trop. Et je ne suis pas sûr si il y a en fait des sous-O(n^3) algorithme pour d'autres variantes que le single-link et link.

    Envisager l'utilisation d'autres algorithmes. k-means par exemple des échelles très bien avec le nombre d'objets (c'est juste pas très bon en général, sauf si vos données est très propre et régulier). DBSCAN et OPTICS sont assez bon, à mon avis, une fois que vous avez une idée pour les paramètres. Si votre jeu de données est de faibles dimensions, ils peuvent être accélérés assez bien avec un la structure de l'index. Puis ils doivent s'exécuter dans O(n log n), si vous avez un index avec O(log n) moment de la requête. Qui peut faire une énorme différence pour les grands ensembles de données. J'ai personnellement utilisé OPTICS sur un 110k images ensemble de données sans problèmes, donc j'imagine qu'il s'adapte bien à 1 million de dollars sur votre système.

    InformationsquelleAutor Anony-Mousse