Algorithme de recommandation d'ami basé sur les données mobiles
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:
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 = 105, cela fera ~(Xmax2) / 2 = 5.109 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:
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 28 = 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).
1 pièce(s) jointe(s)
Algorithme de recommandation d'ami basé sur les données mobiles
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:
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:
Pièce jointe 323300
# 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" :D) 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 .
