Discussion :

[valentin03]

Comme il s'agit des données mobiles (thèmes visités)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
participants: A  B   C  D   E   F
T           a x      x          x
h           b    x   x      x
e           c x  x      x   x   x
m           d    x          x
e           e x      x
s           f           x       x

Taux:
AB=1; AC=2; AD=2; AE=2; AF=2
BC=1; BD=1; BE=3; BF=1
CD=0; CE=1; CF=1
DE=1; DF=2
Il suffit de définir un taux minimum qui sera par définition la compatibilité
A aimant les oiseaux et les chiens; et F aimant les oiseaux et les chiens on DECRETE que A et F sont amis
@:wiwaxia et il apparaît que tu a raison puisque deux personnes peuvent avoir les mêmes taux mais pas les mêmes thèmes. Le problème est plus velu qu'il n'y paraît.

[tbc92]

Quel est l'objectif ?

- Pondre un truc sur 4 ou 5 pages, un peu superficiel.
- Faire une analyse poussée, qui aborde les différentes problématiques. 100 pages, ou même probablement plus ?
- Récolter une base de données existante, et faire des simulations, c'est à dire mettre en place les outils qu'elle aura conçus.

Là, on dit des trucs, mais ça paraît complètement superficiel.

On classe chaque individu en disant : s'intéresse-t-il à tel sujet ? Et on est en train de dire que cette information, c'est un booléen : Oui/Non. On n'envisage pas de réponse intermédiaire.
Plus compliqué, on est en train de dire : il y a des sujets, des sujets bien définis/cloisonnés, et on a l'information : tel individu s'intéresse à tel sujet.

On est donc capable de recenser une centaine de sujets, ou un millier de sujets, qui sont bien cloisonnés ?

Si je m'intéresse aux labradors, et si telle autre personne s'intéresse aux caniches, on va donc dire qu'on s'intéresse tous les 2 aux chiens ? Et donc qu'on a un point d'affinité.

Si l'idée est de faire un aperçu superficiel, sur 4 ou 5 pages, on peut effectivement faire cette impasse. Au delà, c'est une question qu'il va falloir aborder à un moment ou un autre.

[suzy91]

Pour une etude vraiment poussée et assez pertinente, quel approche devrais je adopter?

[tbc92]

Normalement, si tu écris un rapport sur le sujet, je pense que le mot 'Big-data' devrait apparaître très très vite.

[valentin03]

Je propose ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Collecter les x données: "Noms préf1 pref2...prefN" (thèmes visités)
Dimensionner un tableau de chaînes T$(x)= "Nom 
pref1 pref2 pref3 ...prefN"
Dimensionner un tableau de chaînes C$(x)
Faire:
Pour a=1 à x max
   Pour b=a+1 à x max-1
      Pour C=2 à prefN //on saute "1" qui est le nom
         Si T$(a)prefC=T$(b)prefC alors
            C$(a)=T$(a)nom1+" "+T$(b)nom2 
         Fin si
      next c
   next b
next a
//Affichage 
Pour a=1 à max x
   Afficher C$(a)Nom ami1 ami2 ami3...amiN
next a

Purée, il faut ajouter une boucle pour comparer toutes les pref de T$(a) à toutes les pref de T$(b)

[suzy91]

Tu peux m'expliquer un ptit peu, s'il te plait?

[valentin03]

Tu peux m'expliquer un ptit peu, s'il te plait?

Une chaîne est une suite de caractères (y compris espaces et chiffres)
"Nom1 préférence1 préférence2...pref3...prefN" c'est une chaîne
Le tableau T$() contient:
T$(1)="Nom1 préférence1 préférence2...pref3...prefN"
T$(2)="Nom2 pref1 pref2 pref3...ext"
La boucle: Pour a=1 à... va balayer toutes les chaines en commençant par 1 (évidemment il faut remplir le tableau en commençant par 1 car les tableaux commencent par 0)
Et dans la boucle: Pour b=a+1 à max-1 (max-1 car sinon, comme on comme on commence à a+1 (qui est déjà à 1) on sortirait de la taille du tableau, ce qui génèrerait une fatale error)
On comnence à a+1 pour ne pas comparer T$(1) à T$(1); on compare le contenu de T$(1) à celui de T$(2)
Dans la boucle: Pour c=2 (puisque le premier mot de la chaîne est le nom; on compare les préférences (et c'est ici qu'il faut insérer une boucle de plus pour balayer toutes les prefs car tel que c'est on les compare "membre à membre" alors qu'il faut les comparer toutes entres elles.
Si on a une égalité, on concatène (ajouter des maillons à une chaine ou accrocher deux chaînes entres elles) en ajoutant un espace (pour séparer les mots)
A chaque tour de boucle, chaque fois qu'il y aura égalité, un espace et un nom seront ajoutés à la chaîne dans C$(a).
Ce qui est dans la fenêtre ce n'est pas du Basic, c'est du pseudo code; la difficulté réside dans la formulation de la place des mots dans la chaîne qui dépend du langage utilisé et qu'en pseudo code, on écrit plus ou moins comme on veut. (pourvu qu'on y comprenne quelque chose)
Par exemple en Basic, il y a: word$(T$(a), 3) qui cible le troisième mot de la chaîne. En C, c'est plus compliqué.
Qu'est-ce que tu ne comprends pas ? En attendant les gros cerveaux pour ajouter la boucle manquante et proposer une écriture plus conventionnelle.

[suzy91]

La recomendation est basee sur le context et les data. A quel noveau ces deux aspects interviennent dans ton algorithme?

[valentin03]

La recomendation est basee sur le context et les data. A quel noveau ces deux aspects interviennent dans ton algorithme?

Le contexte, ce sont les termes: "données mobile" qui cadrent le sujet
Et les datas, ce sont les noms des participants et les thèmes visités.
En faisant remarquer que jusque là il ne t'est pas imposé de critères
Le plus simple étant de faire: Mêmes choix = amis sans autre considération.
Ce qui ne t'empêche pas d'évoquer d'éventuelles complexités telles que celle dont parle tbc92
Et qu'on peut détailler à l'infini (chiens blancs, chiens noirs, chiens blancs à poil ras, courts sur pattes...ext)

[suzy91]

Tu vas me trouver rabajoie, mais je ne vois pas bien ou li faut rajouter des boucles.

Cet algorithme a t il des limites? Si oui les quelles?

[suzy91]

Etant donne que la logique l ami de mon ami c est mon n est pas toujours vrai. Est ce qu il serait posdible de construire un algorithme capable d eviter ce genre de recommendation qui tres souvent sont erronées?

[valentin03]

Quand on est dans: Pour c=2 à...
on a dans une main T$(a) et dans l'autre T$(b) (qui est T$(a+1))
Mais on égrènne en même temps prefC de T$(a) et prefC de T$(a+1) (c étant le même indice pour les deux on compare membre à membre)
Il faut donc ajouter dans cette boucle; une boucle, qui pour chaque pref de T$(a) va comparer toutes les prefs de T$(b)

Les boucles étant finies les limites c'est la taille des données.
Et l'algo se limite à ce qu'on lui fait faire. Ce qui est plutôt rassurant.
Mais comme dit au début, et du fait des boucles imbriquées le temps de calcul flirte avec le redoutable "!" de factorielle.

L'ébauche d'algo qui est dans le conteneur ne fait pas de l'ami de mon ami mon ami; il n'associe que par choix communs.

[tbc92]

Avant de parler de boucle, il faut avoir une idée générale de l'organisation, des données à disposition.

Tu veux calculer la proximité géographique entre 2 personnes -> une fonction n°1 pour ça.
Tu veux calculer la proximité sociale entre 2 personnes (la majorité des amis de A sont aussi des amis de B) --> une fonction n°2 pour ça.
Tu veux calculer la proximité d'intérêt entre 2 personnes (les centres d'intérêts de A sont aussi les centres d'intérêt de B) --> une fonction n°3 pour ça.
Tu veux organiser/nettoyer les données d'origine : faut-il considérer que s'intéresser aux chiens en général, et s'intéresser aux labradors, c'est la même passion... --> une fonction n°4 pour ça.

Dans ces fonctions, il y aura probablement des boucles. Pour parler de boucle, il faut savoir si on parle de la fonction n°1, n°2, n°3 ou n°4.

Tu aurais certainement intérêt à lire 2 ou 3 trucs de présentation générale sur le big-data, sur l'analyse de données, sur les croisements d'informations avant de parler d'algorithme ou de boucles.

Tu as aussi besoin de cadrer le sujet. Si par exemple on parle de FaceBook, FB fait des suggestions d'amis, basés (uniquement ?) sur l'idée : Les amis de mes amis sont potentiellement mes amis.
Sur d'autres outils, les critères seront très différents. Google, en tant que moteur de recherche, sait qui s'intéresse à quoi. Les données à disposition sont donc très différentes. Les algorithmes vont donc aussi être très différents.

A toi de dire si tu es dans le cadre 1 ou le cadre 2, ou un autre cadre bien sûr. C'est la première question qu'on aurait dû te poser.

Rendez-vous dans une dizaine de jours, quand tu auras un peu avancé.

[suzy91]

Je suis dans le cadre 1 etant donne qu il s agit de la recommandation d amis comme sur facebook. Mais la problematique est de savoir si l' on pourrait construire un algorithme capable de filtrer les amis afin de suggerer de reels amis avec qui on pourrais avoir de reelle affinités sans pour autant se baser sur la reciproque l ami de mon ami c est mon ami. Car comme on le sait cette reciproque n est pas toujours vrai

[wiwaxia]

Ce message apparaîtra un peu décalé, faute d'avoir pu être achevé plus tôt; il suit en gros les réponses #21 à #26.
Je le poste tel quel, en espérant qu'il contienne une ou deux remarques utiles.
Quelques propos dans les échanges qui suivent me mettent mal à l'aise, parce qu'il ne paraît pas définitivement acquis que
les amis de nos amis ne sont pas forcément nos amis.
Hors du critère exclusif du lien d'amitié (Tc >= Limite fixe) - ou quelqu'autre forme qu'on lui donne - la poursuite d'une recherche devient vaine.

tbc92 a raison de poser la question de l'objectif; mais si tout le monde s'accorde sur le moyen de définir une paire d'amis, c'est au moins un pas de fait.

valentin03 propose une recherche exhaustive de toutes les paires possibles, dans la liste des (Xmax ?) abonnés dont chacun présente une liste de (N) préférences.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
FOR a:= 1 TO (Xmax - 1) DO                              // Il y a une petite erreur
  FOR b:= (a + 1) TO Xmax DO
    BEGIN
      Tc:= TauxC(Compte[a].Pref, Compte[b].Pref);       // Fonction de 2 listes de N termes, définie dans les messages précédents
      IF (Tc>Seuil) THEN ...                            // Seuil convenu du taux de compatibilité définissant une paire d'amis
    END

Questions:
1°) Combien de comptes présents dans la source de données ? S'il y en a Xmax = 10⁵, cela fera ~(Xmax²) / 2 = 5.10⁹ paires à tester: cela risque d'être lourd ...

2°) Que faire des réponses ? Consigner les relations d'amitié dans une matrice ? Un booléen peut suffire.
Consigner les préférences partagées ? Ce sera plus volumineux, et il faudra modifier la fonction en conséquence.
Dénombrer les amis ? C'est envisageable en ajoutant un élément à l'enregistrement, en l'initialisant à zéro puis en codant

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
        Inc(Compte[a].Namis); Inc(Compte[b].Namis)

3°) Indépendamment de ce qui précède, quelle est la valeur de (N) ? Ne peut-on pas envisager une étude statistique des préférences déclarées ?
Pour un nombre raisonnable de termes (N = 8), cela ferait 2⁸ = 256 arrangements à dénombrer, ce qui reste accessible; on pourrait repérer rapidement les domaines quasi-vides (Nliste << Xmax / 256) et ceux qui sont surpeuplés ((Nliste >> Xmax / 256)), et faire apparaître les associations surreprésentées.

4°) Comment définir des sous-ensembles de comptes, caractérisés par l'association de certaines préférences ?
Cela paraît difficile si l'on s'en tient au simple critère de proximité, qui peut réunir de proche en proche des listes qui n'ont rien en commun (voir #17).

[valentin03]

@: Susy:
Te voici face à un choix cornélien entre deux méthodes:
- La mienne: La méthode "bourrin", aussi appelée "procédurale": On va au but étape par étape sans se soucier de rien; l'algo est rigide, si on veut modifier, on jette tout et on fait un nouvel algo adapté à la nouvelle situation.
- Celle de tbc92, organisationnelle; où chaque chose est bien rangée dans des fonctions, ce qui permets les modifs sans toucher à l'architecture; quoi qu'en fonction des modifs on soit parfois obligés de tout jeter aussi.
Chacun prêchant pour sa paroisse; pendant que tbc92 te conseillera une belle architecture dénotant un esprit bien structuré; je te conseillerai un truc bien bourrin qui dénotera un sens de la concision.
L'informatique, c'est surtout des choix de stratégies.
Tout l'art consiste à éviter le sort de l'âne de Buridan mort de faim pour n'avoir su choisir entre deux bottes de foin

[wiwaxia]

Je voulais signaler que le profil d'une personne, défini par la séquence des réponses (0 , +), est réductible à une liste de (N) bits, donc d'encombrement minimal et que l'opérateur binaire XOR permet une comparaison rapide, terme à terme.
Une simple fonction livre directement la distance de Manhattan, qui sépare les listes envisagées:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 CONST Nbit = 15;

 TYPE LstNB = ARRAY[1..Nbit] OF Bool;          // Liste de 15 booléens

 VAR La, Lb: LstNB;

 FUNCTION Dist2L(Lu, Lv: LstNB): Byte;
   VAR d, k, x: Byte;
   BEGIN
     d:= 0; E(0013);
     FOR k:= 1 TO Nbit DO
       BEGIN
         x:= 21; Inc(x, 3 * k);
         IF (Lu[k] XOR Lv[k]) THEN BEGIN
                                     Inc(d); E(0012)
                                   END
                              ELSE E(0009);
         We(x, 6, d, 2)
       END;
     Dist2L:= d
   END;

  VAR Dab: Byte;
// ...
  Dab:= Dist2L(La, Lb);   // Appel de la fonction

On peut suivre sur l'exemple suivant le dénombrement des paires de termes différents:



# Le même opérateur peut s'appliquer aux entiers non signés de type Byte ou Word, pour le cas ou l'on souhaiterait par exemple faire intervenir la différence d'âge (à un facteur près).

# Si la liste n'est pas très longue et l'effectif suffisamment important, l'identité totale de deux profils (correspondant à une distance nulle) n'est plus du tout improbable: on pourrait envisager un nouveau lien de proximité maximale ("super-ami" ) qui lui serait transitif:
((X super-ami de Y) et (Y super-ami de Z)) implique ((Lx = Ly) et (Ly = Lz)) d'où: (Lx = Lz) soit encore: (X super-ami de Z)) .
Le repérage de sous-ensembles importants de super-amis (dont l'intersection est par définition vide) pourrait initier un partage de l'ensemble des membres.

Par extension, une gradation du lien d'amitié pourrait être associée aux faibles valeurs de la distance:
1-ami (pour d = 1), 2-ami pour d = 2, etc .

[valentin03]

@:wiwaxia:
L'analyse par paire a été abandonnée suite à ta démonstration
Le dernier algo par moi proposé (incomplet) n'associe que par choix communs exclusif en évacuant la notion de distance (algo minimal)
Ce qui, Sur le modèle de la grille (msg:13h17) donne avec taux mini=2:
A; amis: C D E F
B; ami: E
C; ami: A
D; ami: A F
E; amis: A B
F; amis: A D
Sauf erreur pas d'association illégale

[suzy91]

Qui a deja entendu parle des methodes:
- collaborative filtering,
- content based filtering
- hybrid method????


Si oui dans notre cas devrons nous utiliser l une de ses methodes?

[valentin03]

@Susy: Dis donc cocotte, faudrait voir à bosser un peu aussi
Alors va voir ça:--> https://fr.wikipedia.org/wiki/Filtrage_collaboratif
Et ça: --> https://fr.wikipedia.org/wiki/Syst%C...recommandation
Cogite...Et dis voir ce que tu en pense.