Discussion :

[apicard3]

Bonjour,

Durant mon stage, travail actuellement sur la classification d'individus mobile au sein d'une ville (à partir de données mobiles sur SGBD). En gros, j'aimerais retrouver et identifier les individus dont les déplacements sont ressemblants. Pour cela j'ai travaillé dans un premier temps sur la classification de chemins denses (à partir de la méthode NETSCAN). J'ai donc obtenu des clusters (groupe) de chemin. J'aimerais maintenant associer ses chemins aux individus, et établir des similarités entre individus par la proportion de chemins denses en commun. Mon but est d'établir des similitudes générales entre individus, c'est à dire regrouper ces similitudes sur un plan global (non pas établir une similitude d'un individu envers les autres). J'ai tout d'abord pensé au positionnement multidimensionnel permettant de projeter les données sur un plan (nuage de points) 2D. Étant données que le nombre d'individu est de 200 000, la matrice n*n est impossible à mettre en place, et je me penche actuellement sur des méthodes non linéaires comme Sammon. Est-il possible de mettre en place cette projection sur un plan 2D grâce à des notions de distances non euclidiennes mais par le nombre de clusters en commun entre 2 individus?

Merci d'avance, si vous avez des idées, ou des endroits mieux adaptés pour poser ce genre de questions délicates.

Cordialement,
Alexis

[apicard3]

Pour synthétiser l'information, je cherche à projeter les ressemblance entre individus en 2D par rapport au nombre d'objets qu'il ont en commun deux à deux. Ce nombre variant de 0 à n, plus il est grand plus deux individus sur le plan 2D seront proches. Les individus étant au nombre de 200 000, je cherche une méthode rapide. Merci

[dinobogan]

As-tu aussi une problématique temporelle ? Les positionnements des individus sont-ils uniquement géographiques ?
Pour calculer tes groupes de chemins denses, t'es-tu uniquement appuyé sur les positionnements ?
Combien as-tu de routes (portions de routes entre deux carrefours) ?

[apicard3]

Merci de ton aide.

Les chemins denses ont été calculés temporellement (notamment à l'aide d'un découpage temporel par périodes constantes sur un réseau d'environ 15000 nœuds et 50000 routes). Je suis capable de retrouver pour chaque chemin (avec signature temporel) quels individus sont passés, et également quels sont les chemins en commun entre deux individus. Je peux donc déjà faire ressortir une matrice des chemins en commun entre individus : matrice creuse (sparse matrix), car une matrice de 200 000*200 000 est beaucoup trop large.

Plusieurs problèmes se posent pour faire un MDS classique
- plus le nombre de chemin en commun est grand, moins les individus projetés doivent être éloignés (peut être résolu par soustraction avec le max de chemin en commun)
- lorsque deux individus n'ont pas de chemins en commun, la distance ne peut pas être évaluée.
- le temps de calcul en n*n est trop long

je me penche actuellement sur ce genre d'articles, le positionnement multidimensionnel avec matrice creuse http://www.cmap.polytechnique.fr/~pe..._landmarks.pdf
En ayant toutefois un peu de mal dans la compréhension de ces méthodes.

[dinobogan]

Si j'ai bien compris ce que tu cherches, alors j'ai l'impression que tu cherches un résultat global (pour chaque individu) sur des données déjà agrégées (les groupes de chemins denses) donc avec perte d'information.
Toujours si j'ai bien compris ce que tu cherches à faire, alors il faut sélectionner les groupes de chemins denses qui sont intéressants et supprimer le reste. Puis pour chaque individu, chercher à le placer dans un groupe de chemin dense en analysant son itinéraire. Il est possible qu'il ne soit sur aucun groupe. A la fin, tu vas obtenir un pourcentage des individus sur chaque groupe de chemins denses.
J'imagine qu'un groupe de chemin dense est un ensemble de sous-graphes avec très peu de liaisons entre eux. Alors il serait possible de supprimer des noeuds et des routes pour simplifier les zones de haute densité. Idem pour les individus. Ce prétraitement permettrait probablement un gain sur les temps de calcul de similarité.

[apicard3]

Merci encore de ton aide
L'idée général est dans ce que tu as dis, mais mon but premier est d'obtenir une vue globale en ne gardant que l'individu comme variable, et non l'associer aux chemins. Le principe du MDS permet de projeter ca sur un plan 2D en ne gardant qu'une variable. Voila un exemple du net :

Chaque point représente un individu, les individus proches ont des chemins en commun. Le but étant après de pouvoir sélectionner plusieurs individus à main levée ou de refaire une classification du style k-means derrière etc.
Puisque je suis capable de ressortir la matrice de similarités entre individus, je suis également capable (c'est la même chose quasiment) d'établir un graphe ou les nœuds sont les individus et les arêtes sont les liens entre eux (avec un poids représentant le nombre de chemins denses en commun). Je recherche donc un algorithme qui positionne sur un plan 2D ces nœuds, en prenant en compte que plus le poids entre deux nœuds est élevé plus les nœuds sont proches dans l'espace. Au final, en enlevant les arêtes, on obtiendra le nuage de point que je souhaite avoir. (Je suis en train de lire ceci http://papers.nips.cc/paper/2510-fas...ity-graphs.pdf )

[tbc92]

Regarde du coté des AFC (analyse factorielle des correspondances)