Comment puis-je regrouper un document à l'aide de k-means (Flann avec python)?

Je veux cluster de documents basé sur la similarité.

Je pense avoir essayé ssdeep (similitude de hachage), très rapide, mais on m'a dit que k-means est plus rapide et flann est le plus rapide de toutes les implémentations, et plus précis, alors que je suis en train flann avec des bindings python mais je ne peux pas trouver un exemple de comment le faire sur le texte (il ne support tableau de nombres).

Je suis très très nouveau dans ce domaine (k-means, traitement de la langue naturelle). Ce dont j'ai besoin, c'est la vitesse et la précision.

Mes questions sont:

  1. Pouvons-nous faire ressemblance du document de regroupement /Agrégation à l'aide de KMeans (Flann ne permettent pas la saisie de texte il me semble )
  2. Est Flann le bon choix? Si non, merci de me suggérer de Haute performance de la bibliothèque de textes/docs de clustering, qui ont wrapper python/API.
  3. Est-k-dire le droit de l'algorithme?

source d'informationauteur Phyo Arkar Lwin

  1. 19

    Vous avez besoin de représenter votre document comme un tableau de nombres (aka, un vecteur). Il y a beaucoup de façons de le faire, selon le degré de sophistication que vous voulez être, mais la façon la plus simple est juste de représenter est comme un vecteur de nombres de mots.

    Alors, voici ce que vous devez faire:

    1. Compter le nombre de fois que chaque mot apparaît dans le document.

    2. Choisir un ensemble de "fonctionnalité" des mots qui seront inclus dans votre vecteur. Cela devrait exclure extrêmement mots communs (aka "mots vides") comme "la", "a", etc.

    3. Faire un vecteur pour chaque document basé sur le compte de la fonction des mots.

    Voici un exemple.

    Si vos "documents" sont de simples phrases, et ils ressemblent (un doc par ligne):

    there is a dog who chased a cat
someone ate pizza for lunch
the dog and a cat walk down the street toward another dog

    Si mon set de longs mots sont [dog, cat, street, pizza, lunch]alors je peux convertir chaque document dans un vecteur:

    [1, 1, 0, 0, 0]  //dog 1 time, cat 1 time
[0, 0, 0, 1, 1]  //pizza 1 time, lunch 1 time
[2, 1, 1, 0, 0]  //dog 2 times, cat 1 time, street 1 time

    Vous pouvez utiliser ces vecteurs dans votre algorithme k-means et il sera, espérons-le groupe de la première et de la troisième phrase ensemble parce qu'ils sont semblables, et que la deuxième phrase soit un groupe à part, car il est très différent.

  2. 13

    Il y a un gros problème ici:

    K-means est conçu pour la distance Euclidienne.

    Le problème clé est la moyenne de la fonction. La moyenne sera de réduire la variance de la distance Euclidienne, mais il ne pourrait pas le faire pour une autre fonction de distance. Donc dans le pire des cas, k-means sera n'est plus convergent, mais de l'exécuter dans une boucle infinie (bien que la plupart des implémentations de soutien en s'arrêtant à un nombre maximum d'itérations).

    En outre, la moyenne n'est pas très judicieux pour éparses de données, de texte et de vecteurs ont tendance à être très rares. En gros le problème est que le dire d'un grand nombre de documents n'est plus ressembler à un vrai document, et de cette façon deviennent dissemblables à un véritable document, et plus semblable à d'autres dire des vecteurs. De sorte que les résultats de certains étendre dégénérer.

    Pour le texte des vecteurs, vous souhaiterez probablement utiliser une autre fonction de distance tels que la similarité cosinus.

    Et bien sûr, vous devez d'abord calculer le nombre de vecteurs. Par exemple en utilisant l'expression relative des fréquences, de les normaliser par TF-IDF.

    Il y a une variation de la k-means idée connue comme k-medoids. Il peut travailler avec d'arbitraire à distance des fonctions, et il évite toute "signifie" chose en utilisant le réel document qui est au cœur de la grappe (le "medoid"). Mais les algorithmes connus pour ce sont beaucoup plus lents que les k-means.