Est-ce que le texte décrivant mon application a une importance dans ses ventes ? C’est en partant de cette question que j’ai commencé à réfléchir sur la manière de regrouper des applications selon leurs descriptions.

Après m’être familiarisé avec les algorithmes de fouilles de textes (text mining), j’ai codé quelques scripts expérimentaux pour déterminer des groupes d’applications. Mes résultats étant assez encourageants, j’ai envie de les partager avec vous.

Le but de cet outil est de vous donner quelques pistes pour mieux positionner votre application dans l’App Store. Après avoir obtenu des groupes assez équilibrés (en relançant plusieurs fois l’algo si nécessaire), vous pouvez analyser les descriptions des groupes dont les applications sont similaires à la vôtre. Une bonne pratique est de rajouter dans la description de votre application les mots-clés du groupe qui vous intéresse, il est probable que ces mots « attirent » les utilisateurs.

Mais ne vous attendez pas à des miracles, l’algorithme actuellement utilisé est loin d’être le meilleur. Je compte bien l’améliorer progressivement pour le rendre réellement performant d’ici quelques semaines.

Mots-stop

Lorsque vous devez regrouper des textes par similarité, il faut dans un premier temps retirer les mots trop courants. Ces mots partagés par tous les textes ne permettent pas de les distinguer les uns des autres, ce sont les mots-stop. On retrouve les articles, les pronoms, les auxiliaires… Tous ces mots forment une liste qui servira de filtre pour ne garder que les mots significatifs.

Lemmatisation

Le lemme d’un mot est sa forme canonique. Il n’est pas concevable de pouvoir traiter les documents à partir de tous leurs mots (moins les mots-stop). Il faut rajouter un nouveau filtre en ne gardant que la partie la plus informative du mot. Par exemple, quelle est la partie commune de petit, petits, petite ? La solution est évidente, c’est petit. Nous utilisons un lemmatiseur pour ne garder que les lemmes du texte. Le lemmatiseur retenu est Snowball, il a fait ses preuves sur de nombreux projets.

Représentation vectorielle

Tous les mots présents dans les descriptions sont mis dans un tableau trié alphanumériquement. Chaque description d’application peut ensuite être représentée par un vecteur de booléens obtenu à partir de la liste de tous les mots. Si un mot apparaît dans la description, alors sa valeur correspondante dans le vecteur est mise à 1. Tous les mots absents de la description ont la valeur 0 dans le vecteur de l’application. Au final, nous obtenons une matrice de 0 et de 1 avec les descriptions des applications en ligne et les mots en colonne.

La représentation booléenne est la plus simple, nous aurions pu choisir de mettre le nombre d’apparitions du mot dans la description. Nous pourrions même prendre en compte le nombre de fois où le mot apparaît dans la description avec le nombre de fois où il apparaît dans l’ensemble des documents (tf-idf). Pour l’instant, je n’ai mis en place que la représentation booléenne, mais j’espère tester les autres représentations dans une prochaine version.

Algorithme K-means

Le but de l’algorithme k-means est de regrouper les descriptions qui se ressemblent à partir de k descriptions artificielles. Après avoir généré aléatoirement k descriptions artificielles, les itérations de l’algorithme ajustent ces k descriptions artificielles en fonction des descriptions existantes situées autour des descriptions artificielles. L’algorithme k-means est un des algorithmes de regroupement les plus simples, il en existe beaucoup d’autres : EM, CAH, SOM, LSA…

La bibliothèque de clustering que j’utilise se nomme figue et contient actuellement les algorithmes k-means et CAH. J’ai de mon côté implémenté l’algorithme SOM en JavaScript et je devrais écrire un article là-dessus dans quelques temps. J’ai choisi de faire tourner les algos côté client, il faut donc éviter les algos trop gourmands. Ca m’oblige à regarder les technos de type web storage comme piste d’optimisation possible. Pour l’instant, tout se passe dans la  mémoire vive de votre ordinateur.

L’algorithme est lancé côté client, cela signifie que, selon la puissance de votre ordinateur, vous pouvez attendre plusieurs minutes avant d’obtenir le résultat.

Résultats

La page des résultats des regroupements contient les groupes d’applications payantes en fonction de leurs descriptions. L’algorithme s’exécutant côté client, il est nécessaire d’attendre plusieurs secondes, voire dizaines de secondes, avant l’affichage des résultats. J’ai d’ailleurs constaté des écarts de temps de traitement assez étonnants entre ces différents navigateurs selon leurs versions.

Regroupement des applications dans un autre onglet