• Manuel
 | 
• Feuille de route
 | 
• Glossaire
 | 
• FAQ
 | 
• Pense-bête
 | 
• Travaux notés
• Bibliowebographie

Accueil  / Semaine 14 / Le filtrage collaboratif par article

Le filtrage collaboratif par article

L’approche par article

On distingue deux types de filtrage collaboratif : les techniques comparant les utilisateurs entre eux et les techniques comparant les articles (devant être notés ou recommandés) entre eux. Nous nous intéressons ici à l’approche par article.

Deux modèles par article

Il existe au moins deux grands types de filtrage collaboratif par article. D’abord, les modèles binaires ne se basent que sur le fait qu’un utilisateur donné ait acheté/sélectionné/coché ou non un bien donné ; dans les modèles avec évaluations, les utilisateurs sont invités à noter (par exemple, sur une échelle de 1 à 10) les différents produits.

Amazon item-to-item

L’algorithme de recommandation basé sur les achats le plus connu est sans doute l’algorithme basé sur l’article, « item-to-item » développé par Linder et al. [1] pour Amazon (voir la figure 1).
L’algorithme est d’une grande simplicité.

Prenons la matrice suivante :

Utilisateur	Article 1	Article 2	Article 3
Peter	achat	achat	non achat
Steve	non achat	achat	non achat
Arthur	non achat	achat	achat

On convertit la matrice en matrice « binaire » selon qu’un achat a eu lieu par le passé ou non (1 et 0) :

Utilisateur	Article 1	Article 2	Article 3
Peter	1	1	0
Steve	0	1	0
Arthur	0	1	1

Chaque article devient donc un vecteur constitué de zéros et de uns.

Ensuite, si un utilisateur donné s’intéresse à l’article 1, par exemple, on lui suggérera l’article dont le cosinus avec l’article 1 est le plus élevé. Notons que le cosinus de deux vecteurs binaires est une quantité nécessairement non négative. Dans le cas de notre exemple, nous avons :

article 1- article 2,

article 1- article 3, .

Ainsi, l’article 2 sera recommandé à tout utilisateur s’intéressant à l’article 1.

Une évaluation de cet algorithme a été produite par Demiriz [2]. La conclusion fut sans équivoque : « (..) item-based recommender systems are very efficient and robust in
terms of both scalability and prediction accuracy. Cosine-based algorithms, especially, are superior to other
methods mentioned in this paper. » (Les algorithmes par articles sont très efficaces et robustes en ce qui a trait à leur extensibilité et à l’exactitude de leurs prédictions ; l’approche par cosinus est supérieure à toutes les autres approches analysées).

Outre le cosinus, il est suggéré d’utiliser la similarité de Tanimoto définie comme  [3].

Slope One

L’algorithme non trivial le plus simple pour le filtrage collaboratif par article avec évaluations, est sans doute l’algorithme Slope One [4].

Imaginons que vous ayez deux articles, article 1 et article 2. Vous voulez prédire les notes reçues par l’article 2 à partir de l’article 1.

Prenons un exemple concret :

Utilisateur	Article 1	Article 2
u1	4/10	sans note
u2	3/10	7/10
u3	8/10	7/10
u4	sans note	3/10
u5	2/10	2/10

L’algorithme Slope One calcule l’écart moyen entre les notes de l’article 2 et celles de l’article 1, soit 1/10 dans le cas présent [5], et il l’ajoute simplement aux notes de l’article 1 pour faire une prédiction quant aux notes de l’article 2 :

4/10 devient 4/10 + 1/10 = 5/10

Ce qui équivaut à trouver une fonction de prédiction de la forme (d’où le nom Slope One - pente de valeur 1).

Slope One avec plusieurs articles

L’algorithme Slope One, dans sa version de base, prédit les notes d’un article à partir des notes d’un autre article. Dans l’éventualité où un utilisateur a déjà noté plus d’un article, on doit donc combiner plusieurs prédictions. On le fait avec une moyenne pondérée où le poids est le nombre d’utilisateurs ayant noté les deux articles.

Par exemple, si la différence moyenne entre l’article 2 et l’article 1 est 1.5, et que douze utilisateurs ont noté les deux articles (1 et 2), alors que la différence moyenne entre l’article 3 et l’article 1 est -0.5, mais que 114 utilisateurs ont noté les deux articles (3 et 1), alors pour un utilisateur ayant donné une note de 3 à l’article 2 et une note de 5 à l’article 3, nous aurons une prédiction pour sa note à l’article 1 donnée par .

Bryan O’Sullivan a écrit un excellent tutoriel sur l’algorithme Slope One (en anglais).

Mise en oeuvre en Java

Voici une classe Java simple qui met en oeuvre l’algorithme Slope One. Vous êtes invité à la compiler et à l’utiliser, mais c’est optionnel. Il vous est permis de l’utiliser pour faire les travaux [6].

(Note.- Avant de tenter de compiler ce fichier, assurez-vous d’avoir Java 1.5, ou mieux en tapant « javac -version ». Vous devriez ensuite voir un numéro de version 1.5 (ou supérieure).)

Cold start

Les algorithmes par article ne posent pas de problèmes lorsqu’un utilisateur n’a noté qu’un seul article. Par contre, il est possible qu’on ne puisse pas faire certaines prédictions si aucun utilisateur n’a noté une certaine paire d’articles.

Mise à l’échelle

Si l’utilisateur a noté  articles, on peut prédire la note sur un autre article en faisant une moyenne pondérée sur  articles. La complexité algorithmique est donc où est le nombre d’articles, ce qui est moindre que ce que l’on observe avec les algorithmes utilisateurs-utilisateurs ().

Par contre, il peut être nécessaire de stocker une matrice où les différentes moyennes entre les articles ont été précalculées (taille maximale de ). Si on offre 100 000 produits, la matrice aura 10 milliards de cellules. L’espace de stockage n’est pas un facteur critique, mais la vitesse d’accès peut poser des problèmes. Il existe diverses stratégies pour réduire la quantité de stockage utilisée, notamment la partition des articles par catégories.

---