Précédent Index Suivant
Chapitre 2 Présentation des méthodes de filtrage collaboratif

La motivation du Collaborative Filtering (terme introduit en 1994) est d'étendre la notion de bouche à oreille entre amis à des milliers de personnes sur Internet : vos amis (quelques personnes) peuvent vous recommander ce qu'ils ont apprécié; sur Internet des milliers d'individus sont susceptibles de vous donner leur avis.
Les objets pour lesquels on veut évaluer l'intérêt des internautes peuvent être de toute sorte: films, restaurants, jeux, blagues, articles, etc... Dans le cadre de la collaboration avec la société Rosebud, les objets pour lesquels nous tentons d'évaluer l'intérêt porté par les utilisateurs sont les pages des sites web qu'ils gèrent. C'est donc dans le cadre de l'évaluation de pages web que nous nous plaçons dans ce rapport.
La figure 2.1 présente l'organisation générale d'un système de recommandation. Typiquement, les étapes du système sont les suivantes:


Figure 2.1 : Schéma général d'un système de recommandation


Typiquement, ensuite, un utilisateur peut demander au système de: Chaque recommandation est accompagnée d'une mesure de confiance dépendant de facteurs tels que le nombre d'utilisateurs utilisé pour la recommandation, la consistance de la valeur fournie par ces utilisateurs, etc...


2.1 Première étape: l'évaluation des articles par les utilisateurs

Tout d'abord, la première notion à prendre en compte est celle du taux de satisfaction des utilisateurs pour les pages qu'ils parcourent. En effet, pour caractériser un profil d'utilisateur, la première chose à comprendre, c'est si ce qu'il a lu lui a plus ou moins plu, ou pas du tout. Pour cela, deux choix sont possibles: demander à l'utilisateur de noter lui-même les pages à partir d'une échelle de notes fixée (par exemple de 0-Nul à 7-génial), ou bien évaluer automatiquement cette note, grâce aux informations que l'on peut récolter à partir des données du protocole de communication Internet.

2.1.1 Évaluation avec investissement de l'utilisateur

L'idéal pour apprendre les goûts, et donc le profil d'un utilisateur, est que celui-ci nous donne son avis lui-même sur le plus de documents possible de la base de données. Pour cela, la plupart des systèmes de recommandation demandent à leurs nouveaux utilisateurs de participer à la définition de leur profil initial, en passant d'abord par une phase de notation, selon une échelle de notes fixée, d'articles qui leurs sont proposés. Pour cette méthode, un problème est alors de trouver l'échelle de notes la plus adaptée pour permettre une notation aussi précise que possible des articles par les utilisateurs. Une autre problématique est celle du choix de l'échantillon: comment le générer? propose-t-on le même à tous? quelle quantité d'articles suggérer? demande-t-on à l'utilisateur de noter chaque nouvel article qu'il lira dorénavant?
Remarquons à ce niveau que la façon de noter des articles varie fortement selon l'utilisateur. Par exemple, certains ne notent que les articles qui leur plaisent, alors que d'autres utilisent l'entièreté de l'échelle proposée. Il faut donc bien comprendre ce que chaque note signifie pour chaque utilisateur. De plus, si on fournit la même liste d'articles à un utilisateur à différents moments, les notes attribuées aux articles peuvent déjà être légèrement différentes.

2.1.2 Évaluation sans participation de l'utilisateur

Si l'on veut éviter à l'utilisateur de s'investir dans la définition de son profil, au lieu de lui demander si une page lui a plu ou non, on peut le deviner, en se servant des informations que l'on peut obtenir lors de son passage sur le site. En effet, chaque fois qu'un internaute visite une page d'un site web, il laisse derrière lui des traces de son passage. Pour traiter ce problème, P.K. Chan [Cha99] propose de développer un Page Interest Estimator, pour prédire si la page proposée a été appréciée ou non. Pour cela, quatre sources générales d'informations ont été identifiées: l'historique et le bookmark du côté utilisateur; l'access log et le contenu des pages du côté serveur:

  1. Typiquement, l'historique global d'un browser maintient une marque du dernier moment où chaque page a été visitée. On peut donc utiliser cette donnée pour calculer combien de fois un utilisateur passe sur une page et depuis quand il n'est pas retourné la visiter. On conjecture alors qu'une plus haute fréquence de visites, et des visites plus récentes d'une URL, indique un intérêt plus fort de l'utilisateur pour l'URL concernée.
  2. Chaque entrée dans un access log correspond à une requête http, qui contient typiquement l'adresse IP du client, une marque du moment de connexion, des méthodes d'accès, une URL, un protocole, un status, et une taille de fichier.
    Typiquement, une ligne de fichier de log se présente comme suit:
    216.221.34.111 - - [22/Apr/2001:04:04:54 +0200] "GET /polys/access-1997/node2.html HTTP/1.1" 200 2856

    Grâce à ces informations, le temps passé sur chaque page peut être calculé. Cependant, le temps passé sur une page dépendant également de la longueur de cette page, l'intérêt d'un utilisateur pour une page sera approximé par le temps passé sur la page, normalisé par la taille de la page. Notons également que d'autres activités que le surf sur le web (par exemple répondre à un coup de téléphone) peuvent être inclues dans le temps passé sur une page; mais on ne peut manifestement pas éviter ce problème. Pour réduire cette limitation, on peut par contre fixer une borne supérieure pour le temps (10 minutes par exemple).
  3. On peut ensuite également supposer qu'une URL présente dans le bookmark d'un utilisateur est considérée comme très intéressante pour celui-ci.
  4. Enfin, chaque page contient des liens vers d'autres pages. On suppose que si un utilisateur est intéréssé par une page, il va probablement visiter les liens référencés par celle-ci. Ainsi, on conjecture qu'un fort pourcentage de liens visités à partir d'une page dénote un intérêt spécial pour cette page.
Finalement, P.K. Chan définit le degré d'intérêt d'une page par:

Interest(Page) = Frequency(Page) ×
(1 + IsBookmark(Page) + Duration(Page) + Recency(Page) + LinkVisitPercent(Page)),

Frequency(Page), la fréquence de visite de la page, est considérée comme l'information la plus discriminante quant à l'intérêt porté par un utilisateur sur une page. L'utilisation de ``1'' dans la parenthèse sert à éviter au terme entre parenthèse de s'annuler. Avec cette formule, l'intérêt pour une page est alors compris entre Frequency(Page) et 5 × Frequency(Page).

IsBookmark(Page)= ì
í
î
1 si la page appartient au bookmark de l'utilisateur
0 sinon

Duration(Page)=
TotalDuration(Page)/Size(Page)
max
 
page Î VisitedPage
TotalDuration(Page)/Size(Page)
,

Recency(Page)=
Time(LastVisit)-Time(StartLog)
Time(Now)-Time(StartLog)
,

et

LinkVisitPercent(Page)=
NumberOfLinksVisited(Page)
NumberOfLinks(Page)
.

Puis il nous faudra ensuite normaliser ces valeurs pour qu'elles appartiennent à l'intervalle qu'on se sera fixé pour l'échelle de notes sur les articles.
On ne peut cependant pas supposer que toute page non visitée n'est pas intéressante, puisque l'utilisateur ne connait sûrement même pas son existence. Une approche pour identifier les pages inintéressantes serait de considérer les liens non suivis par l'utilisateur sur une page visitée, ou bien les pages quittées trop tôt (et il nous faudrait dans ce cas rechercher le seuil temporel le plus adapté pour séparer les pages intéressantes des autres).
Notons enfin que d'autres informations, contenues dans les cookies (fichiers utilisateur), peuvent être très instructives. Mais ce qui est écrit dans ces fichiers étant propre à chaque site, nous ne pourrons exploiter ces informations que dans un cadre précis, où l'on connait les traces laissées dans ces fichiers.
La société Rosebud avec laquelle nous travaillons serait intéréssée par ce genre de méthode car ses responsables veulent éviter à leurs clients de s'investir dans la définition de leur profil. Pour plus de détails pour notre application, il nous faut pour l'instant attendre que Rosebud nous transmette les données qu'ils collectent à partir des différentes visites de leurs clients sur leurs sites. En attendant, les expérimentations ont donc été effectuées sur les fichiers de log du site de l'équipe GRAPPA.

2.1.3 Stockage des données

Les notes obtenues sont alors stockées dans la base de données utilisateur.
Typiquement, on représente ces données par une matrice de notes des utilisateurs sur les pages qu'ils ont parcourues.

La base de données utilisateur se présente alors sous la forme du tableau 2.1 suivant (que nous utiliserons comme exemple dans la suite de ce chapitre).

  Article 1 Article 2 Article 3 Article 4 Article 5
Utilisateur 1     7 6  
Utilisateur 2     5 6 7
Utilisateur 3     6 6 7
Utilisateur 4 7 5     7
Utilisateur 5 7 6     7

Table 2.1 : Une matrice des notes attribuées aux articles par les utilisateurs


Formellement, cette matrice correspond à en un ensemble de votes vi,j des utilisateurs (i) sur les pages (j). Par exemple ici, on a v3,3=6.

vi correspond au vecteur décrivant l'utilisateur i (l'ensemble de ses votes, {vi,j | i}). Dans notre exemple, on a v3=(0,0,6,6,7).

On utilise la notation Ii pour désigner l'ensemble des pages pour lesquelles l'utilisateur i a voté. On a alors I3={3,4,5}.

Et nous noterons pi,j l'estimation du vote de l'utilisateur i sur la page j, le but étant que pi,j soit le plus proche possible de vi,j. Nous verrons alors dans la suite quelle est l'estimation p3,3 du vote de l'utilisateur 3 sur la page 3, pour les méthodes présentées.

2.2 Les méthodes de filtrage collaboratif

Deux classes d'algorithmes de filtrage collaboratif, exploitant ensuite ces données pour aider les utilisateurs dans leurs futures recherches, ont été distinguées [BHK98]:

2.2.1 Méthodes basées sur la mémoire

L'idée de base des systèmes basés sur la mémoire est la suivante: Pour prédire la pertinence d'un article pour un utilisateur, on calcule donc la moyenne des notes données aux articles par les utilisateurs ayant les mêmes goûts (ou des goûts opposés), en utilisant des poids différents selon la mesure de similarité entre utilisateurs.

Pearson

Formellement, la base de données utilisateur consiste donc en un ensemble de votes vi,j correspondant au vote de l'utilisateur i sur l'article j. Si Ii désigne l'ensemble des articles pour lesquels l'utilisateur i a voté, alors on définit le vote moyen pour l'utilisateur i par:
vi
=
1
|Ii|
 
å
j Î Ii
vi,j
Soit a l'utilisateur considéré (actif). Alors l'estimation du vote de l'utilisateur actif pour l'article j, pa,j, est le vote pondéré des autres utilisateurs:
pa,j=
va
+
n
å
i=1
w(a,i)(vi,j-
vi
)
n
å
i=1
|w(a,i)|
,
avec n le nombre d'utilisateurs de la base dont le poids n'est pas nul, et ayant notés l'article j. Les poids w(a,i) peuvent refléter distance, corrélation, ou similarité entre chaque utilisateur i et l'utilisateur actif a.


Figure 2.2 : Recommander un article à un utilisateur


Pour affecter les poids entre utilisateurs, typiquement, la similarité entre utilisateurs est mesurée en représentant chaque utilisateur comme un vecteur de votes pour les articles de la base, puis en calculant le cosinus (cos(u,v)) de l'angle formé par les deux vecteurs (u et v) représentant les deux utilisateurs considérés:
cos(
u
,
v
)=
u
.
v
||
u
||.||
v
||
=
 
å
i
ui.vi
æ
ç
ç
è
 
å
i
ui2.
 
å
i
vi2 ö
÷
÷
ø
1/2



 

Une mesure possible pour le poids entre les utilisateurs a et i est alors le coefficient de similarité
w(a,i)=
 
å
j
va,j*vi,j
æ
ç
ç
è
 
å
j
va,j2
 
å
j
vi,j2 ö
÷
÷
ø
1/2



 
,
où la somme sur j concerne l'ensemble des articles pour lesquels les utilisateurs a et i ont tous deux affecté une note (j Î Ia Ç Ii).
Mais le coefficient de corrélation de Pearson s'est avéré être une mesure plus efficace, en considérant plutôt le cosinus de l'écart à la moyenne des deux utilisateurs considérés: il pose:
w(a,i)=cos(
va
-
va
,
vi
-
vi
)=
(
va
-
va
).(
vi
-
vi
)
||
va
-
va
||.||
vi
-
vi
||
d'où
w(a,i)=
 
å
j Î Ia Ç Ii
(va,j-
va
)(vi,j-
vi
)
æ
ç
ç
è
 
å
j Î Ia Ç Ii
(va,j-
va
)2
 
å
j Î Ia Ç Ii
(vi,j-
vi
)2 ö
÷
÷
ø
1/2



 
,

Pour observer l'utilisation de cette méthode selon Pearson, revenons maintenant à l'exemple que nous avons présenté précédemment, et voyons quelle est l'estimation de vote de l'utilisateur 3 sur l'article 3. Nous supposons donc cette note non attribuée, et allons voir quelle estimation de note l'algorithme va fournir.

Les utilisateurs que nous considérons sont alors ceux ayant noté l'article 3, et qui ont noté au moins un article en commun avec l'utilisateur 3. Dans notre cas, il s'agit des utilisateurs 1 et 2.

La première étape est alors le calcul des moyennes des utilisateurs concernés: v1=6.5 ; v2=6 ; v3=6.5.

Puis on calcule les corrélations entre utilisateurs concernés. Pour la corrélation entre 1 et 3, on considère les articles appartenant à I1 Ç I3 = {4}, et on trouve w(1,3)=1. Pour la corrélation entre 2 et 3, on considère les articles appartenant à I2 Ç I3 = {4,5}, et on trouve w(2,3)=1.

Puis on peut enfin calculer l'estimation de vote de l'utilisateur 3 sur l'article 3, et on trouve p3,3=6.25, qu'on arrondi à 6, et qui correspond effectivement à la note réellement attribuée.

Nous détaillerons davantage les calculs de cette approche dans le chapitre suivant.

Bayes

Une autre approche, envisagée pendant le stage, est d'estimer les probabilités P(vij=k|vi) d'attribuer une note k à un article j par un utilisateur i, connaissant sa description vi (vecteur de notes vip sur les articles parcourus p), et les informations sur les autres utilisateurs de la base.
L'idée ici est alors d'utiliser la règle de Bayes suivante:
P(vij=k|
vi
) =
P(vij=k)*P(
vi
|vij=k)
P(
vi
)

P(vij=k) correspond à P(vj=k), la probabilité d'attribuer la note k sur l'article considéré j.

P(vi|vij=k) correspond à P(vi|vj=k), la probabilité de la description vi de l'utilisateur i sachant qu'on a attribué la note k sur l'article j.

et P(vi) est la probabilité de la description vi de l'utilisateur i.
Ainsi, estimer la probabilité P(vij=k|vi) revient à calculer P(vi|vj=k) et P(vj=k), ce qui peut être fait en consultant la base de données utilisateur des notes déjà attribuées aux articles, puis à attribuer, pour l'utilisateur i sur l'article j, la note k qui maximise la probabilité P(vi|vj=k)*P(vj=k).
Soient les notations suivantes:

NbNotes(k,j) = nombre de notes égales à k pour l'article j.

TotalNotes(j) = nombre total de notes attribuées à l'article j.

On pose alors

P(vj=k) =
NbNotes(k,j)
TotalNotes(j)

En ce qui concerne P(vi|vj=k), en faisant une hypothèse d'indépendance entre les notes attribuées aux articles, on pose

P(
vi
|vj=k) =
 
Õ
p Î Ii
P(vp=vip|vj=k)

avec P(vp=vip|vj=k) la probabilité d'attribuer la note vip sur l'article p sachant qu'on a attribué la note k sur l'article j.
Soient les notations suivantes:

NbNotes(vp=vip|vj=k) = nombre de notes égales à vip pour l'article p, pour les utilisateurs ayant noté k sur l'article j,

TotalNotes(p|vj=k) = nombre total de notes attribuées à l'article p, pour les utilisateurs ayant noté k sur l'article j,

et MaxEchelle le maximum de l'échelle de notation utilisée.
Étant donné qu'il faut éviter d'avoir P(vp=vip|vj=k)=0, qui annulerait directement P(vi|vj=k), on ne pose pas
P(vp=vip|vj=k) =
NbNotes(vp=vip|vj=k)
TotalNotes(p|vj=k)
On pose plutôt
P(vp=vip|vj=k) =
1+NbNotes(vp=vip|vj=k)
MaxEchelle+TotalNotes(p|vj=k)
Ainsi, P(vp=vip|vj=k) ne risquera pas d'annuler P(vi|vj=k), et on obtient bien ån=1MaxEchelleP(vp=n|vj=k)=1:
MaxEchelle
å
n=1
P(vp=n|vj=k)
=
MaxEchelle
å
n=1
1+NbNotes(vp=n|vj=k)
MaxEchelle+TotalNotes(p|vj=k)
=
MaxEchelle
å
n=1
1 +
MaxEchelle
å
n=1
NbNotes(vp=n|vj=k)
MaxEchelle+TotalNotes(p|vj=k)
=
MaxEchelle+TotalNotes(p|vj=k)
MaxEchelle+TotalNotes(p|vj=k)
= 1

Finalement, par la méthode de Bayes, pour estimer la note attribuée par l'utilisateur i sur l'article j, on cherche donc k qui maximise

Mk=
NbNotes(k,j)
TotalNotes(j)
 
Õ
p Î Ii
æ
ç
ç
è
1+NbNotes(vp=vip|vj=k)
MaxEchelle+TotalNotes(p|vj=k)
ö
÷
÷
ø

Pour observer l'utilisation de cette méthode selon Bayes, revenons à notre exemple, et voyons quelle est l'estimation de vote de l'utilisateur 3 sur l'article 3. Nous supposons donc cette note non attribuée, et allons voir quelle estimation de note l'algorithme va fournir.

Dans un premier temps, on regarde les notes déjà attribuées à l'article considéré. Ici, deux notes sont envisageables: 5 et 7. À partir de là, pour chaque note k envisageable, on calcule la probabilité Mk de l'attribuer, étant donnée la description de l'utilisateur considéré:

M5=
1
32
et M7=
1
56

Puis on sélectionne la note de plus forte probabilité: M5>M7, donc la note attribuée à l'article 3 pour l'utilisateur 3 sera 5 par la méthode de Bayes.

Nous détaillerons davantage les calculs de cette approche dans le chapitre suivant.

vote moyen pondéré de Bayes

Une autre utilisation de cette approche de Bayes a été envisagée: effectuer un vote moyen pondéré sur l'article j, en prenant en compte la description vi de l'utilisateur i:
On renvoie alors la note
MaxEchelle
å
k=1
P(vj=k|
vi
)*k

2.2.2 Méthodes basées sur les modèles

D'un point de vue probabiliste, la tâche du filtrage collaboratif peut être vue comme le calcul de la valeur la plus probable d'un vote, étant donné ce que nous savons à propos de l'utilisateur, et le modèle que l'on aura construit à partir de la base de données utilisateur.

Le modèle cluster

L'idée du modèle cluster est de regrouper (en clusters) les gens ayant les mêmes goûts, et de regrouper (en clusters) les articles portant sur les mêmes sujets, ou qui tendent à plaire aux mêmes personnes. Ainsi, pour prédire la note qu'un utilisateur donnera à un article, on pourra utiliser les avis des utilisateurs qui appartiennent à son groupe. En d'autres termes, on veut associer une classe (ou plusieurs) à chacun des utilisateurs, ainsi qu'à chacun des articles. Mais ces classes étant a priori inconnues, elles doivent être dérivées du processus d'estimation du modèle.
Typiquement, les systèmes de clustering se différencient par la fonction objectif choisie pour évaluer la qualité du clustering, et la stratégie de contrôle pour parcourir l'espace des clusters possibles. Mais tous suivent le principe général traditionnel en clustering qui consiste à maximiser la similarité des observations à l'intérieur d'un cluster, et minimiser la similarité des observations entre clusters, pour arriver à une partition de la base aussi pertinente que possible.
En entrée, ce que nous avons, c'est un ensemble d'enregistrements de qui a apprécié quoi, représenté par une matrice d'appréciations des articles par les utilisateurs (cf. exemple tableau 2.2).

  Article 1 Article 2 Article 3 Article 4 Article 5
Utilisateur 1     7 6  
Utilisateur 2     5 6 7
Utilisateur 3     6 6 7
Utilisateur 4 7 5     7
Utilisateur 5 7 6     7

Table 2.2 : Une matrice des notes attribuées aux articles par les utilisateurs


L'idée du clustering est alors de former des blocs les plus pertinents et significatifs possibles, à partir de cette matrice, et former ainsi des clusters d'utilisateurs et des clusters d'articles, tels que les utilisateurs considérés comme similaires tendent à noter de la même façon les articles considérés comme similaires (cf. exemple tableau 2.3).

  Article 1 Article 2 Article 3 Article 4 Article 5
Utilisateur 1     7 6  
Utilisateur 2     5 6 7
Utilisateur 3     6 6 7
Utilisateur 4 7 5     7
Utilisateur 5 7 6     7

Table 2.3 : Partition de la matrice précédente articles/utilisateurs


Puis la partition est évaluée en estimant, pour chaque bloc formé, la probabilité que les utilisateurs d'un même cluster k apprécient les articles d'un même cluster l, le but étant que ces probabilités soient les plus proches possible de 1, c'est à dire que tout le monde soit du même avis dans le groupe.
Un bloc Bc est en fait caractérisé par k, l'ensemble des lignes de la matrice faisant partie de ce bloc (le cluster des utilisateurs considéré), et l, l'ensemble des colonnes de la matrice faisant partie de ce bloc (le cluster des articles considéré), et il est défini par l'ensemble des notes {vij | i Î k , j Î l}, et |Bc| le nombre d'éléments du bloc. Pour évaluer la pertinence d'un bloc Bc (cf. exemple tableau 2.4), une méthode simple que nous avons générer est la suivante: tout d'abord, on calcule la moyenne Mc des notes attribuées de ce bloc; puis pour chaque élément vij tel que i Î k, j Î l, et vij ¹ 0, on calcule son écart à la moyenne eij=|vij-Mc|; on somme ensuite cet ensemble des écarts à la moyenne; et puis on normalise pour obtenir un réel compris entre 0 et 1; l'évaluation de la pertinence Pc du bloc peut alors être donnée par:
Pc=1-2*
 
å
i
 
å
j
eij
MaxEchelle*|Bc|
Ainsi, plus les notes d'un bloc sont proches les unes des autres, plus la probabilité Pc sera proche de 1, et inversément, plus les notes d'un bloc sont éloignées les unes des autres, et plus la probabilité Pc sera proche de 0.


  Cluster d'articles 1 Cluster d'articles 2 Cluster d'articles 3
Cluster d'utilisateurs 1 1 0.90 1
Cluster d'utilisateurs 2 0.86 1 1

Table 2.4 : Evaluation de la partition précédente


Ensuite, pour évaluer la partition générale de la matrice M, partitionnée en blocs Bc, on pose
P=
 
å
c
|Bc|Pc
|M|

L'idée de l'utilisation d'une pondération ici est de favoriser les ``gros clusters pertinents''.

Dans notre cas, la pertinence de la matrice est alors P=0.91
Après cette présentation générale du clustering, rentrons maintenant dans les détails des approches existantes. Comme nous l'avons énoncé précédemment, les systèmes de clustering sont définis par la fonction objectif utilisée pour évaluer la qualité du clustering, et la stratégie de contrôle pour parcourir l'espace des clusters possibles.

Voyons d'abord les différentes stratégies de contrôle qu'on peut utiliser pour parcourir l'espace des clusters possibles:
Dans un premier temps, on utilise donc une stratégie simple pour former une partition initiale, puis on utilise ensuite plusieurs stratégies de contrôle pour lancer une optimisation itérative du modèle courant. Se définir une fonction objectif va alors permettre d'évaluer la pertinence de la partition effectuée. Voyons donc maintenant quelques fonctions objectif qu'on peut utiliser pour cela:
  1. Soient Vij les notes attribuées par les utilisateurs (i) sur les articles (j), et Cn les clusters d'utilisateurs formés. Alors une mesure de la Qualité d'un Cluster peut être donnée par:
    QC(Cn)=P(Cn)
     
    å
    j
     
    å
    k
    [P(Vij=k | i Î Cn)2-P(Vij=k)2]
    L'idée ici est de favoriser les clusters qui vont accroître la prédictabilité, c'est à dire P(Vij=k | i Î Cn)>P(Vij=k).
    Une mesure de la Qualité d'une Partition peut alors être:
    QP({C1,C2,···,CN})=
    N
    å
    n=1
    |Cn|QC(Cn)
     
    å
    n
    |Cn|
    De nouveau, l'idée ici est de favoriser les ``gros clusters pertinents''.
  2. Une autre idée est de minimiser la distance moyenne entre éléments d'un même cluster tout en maximisant la distance entre clusters:
    Soient N utilisateurs vi appartenant à un même cluster.

    On définit d'abord le centroïd X0 du cluster par:
    X0
    =
    N
    å
    i=1
    vi
    N

    Puis deux mesures sont proposées ici pour définir la distance entre éléments d'un même cluster:



    1. Le radius R correspond à la distance moyenne entre points membres du cluster et son centroïd:
      R= æ
      ç
      ç
      è
      N
      å
      i=1
      (
      vi
      -
      X0
      )2
      N
      ö
      ÷
      ÷
      ø
      1/2



       

    2. Et le diamètre D correspond à la distance moyenne entre paires de membres du cluster:
      D= æ
      ç
      ç
      è
      N
      å
      i=1
      N
      å
      j=1
      (
      vi
      -
      vj
      )2
      N(N-1)
      ö
      ÷
      ÷
      ø
      1/2



       


    Ces deux mesures doivent alors être minimisées pour maximiser la similarité des observations à l'intérieur d'un cluster.
    Et ensuite, deux méthodes sont proposées ici pour définir la distance entre deux clusters et mesurer leur proximité:



    1. Etant donné les centroX02 de deux clusters, la distance euclidienne D0 entre centroïds est donnée par:
      D0= æ
      ç
      è
      (
      X
       
      01
      -
      X
       
      02
      )2 ö
      ÷
      ø
      1/2


       

    2. Et D1, la distance de Manhattan entre centroïds est donnée par:
      D1=|
      X
       
      01
      -
      X
       
      02
      |=
      d
      å
      i=1
      |
      X
       
      01
      (i)-
      X
       
      02
      (i)|,
      avec d la dimension des vecteurs.

    Ces deux mesures doivent alors être maximisées pour minimiser la similarité des observations entre clusters.
Le modèle réseau de Bayes

Un réseau de Bayes [Hec96] est un graphe acyclique dirigé qui représente une distribution de probabilités de dépendance entre un ensemble de variables. Chaque noeud dans le graphe représente une variable, et chaque arc une dépendance directe entre variables. Ainsi, chaque variable est indépendante de ses non-descendants dans le graphe, étant donné l'état de ses parents.
Par exemple, si on représente un classifieur naif de Bayes sous la forme d'un réseau de Bayes, on obtient une structure simple telle que décrite dans la figure 2.4. En effet, chaque attribut (les feuilles du réseau) est indépendant des autres attributs, étant donné l'état de la variable de classe (la racine du réseau).


Figure 2.4 : La structure d'un réseau de Bayes naif


Si on dispose d'un ensemble d'apprentissage, l'idée pour l'algorithme d'apprentissage est alors d'effectuer une recherche parmi les différentes structures de modèle possible, en terme de dépendance pour chaque article, pour que dans le réseau résultant, chaque article ait un ensemble d'articles parents qui soient les meilleurs prédicteurs de ses votes.
Une idée pour notre application est alors d'associer un réseau de Bayes à chaque article de la base. À chaque feuille de l'arbre est associée une probabilité d'attribuer une note à l'article, étant donné l'état des parents identifiés. Pour prédire l'estimation de note d'un client sur un article, on se déplace alors dans le réseau de Bayes correspondant, selon les notes que l'utilisateur considéré a donné aux articles parents présents dans le réseau, et on attribue, pour l'article considéré, la note la plus probable.
Formellement, on obtient:
Soit U={X1,...,Xn} un ensemble fini de variables aléatoires discrètes, où chaque Xi prend ses valeurs dans un ensemble fini Val(Xi). Soit PB une distribution de probabilités sur les variables de U. Un réseau de Bayes B pour U est un couple <G,Q>. Le graphe G code les hypothèses d'indépendance suivantes: chaque variable Xi est indépendante de ses non-descendants, étant donné l'état de ses parents dans G. Et Q représente l'ensemble des paramètres qui quantifient le réseau. Il contient les paramètres qxi|Õxi=PB(xi|Õxi) pour chaque valeur possible xi de Xi, et Õxi de ÕXi, où ÕXi est l'ensemble des parents de Xi dans G.
Un réseau bayesien B définit donc une unique distribution de probabilités sur U, donnée par:
PB(X1,...,Xn)=
n
Õ
i=1
PB(Xi|Õ Xi)=
n
Õ
i=1
q
 
Xi|
 
Õ
Xi

Par exemple, soit U={A1,...,An,C}, où les variables Ai sont les attributs et C est la variable de classe. Soit la structure de graphe où la variable de classe est la racine du graphe (c'est à dire ÕC=Ø), et chaque attribut a la variable de classe comme son unique parent (c'est à dire ÕAi={C} pour tout 1 £ i £ n). Pour ce type de structure de graphe, on obtient:
PB(A1,...,An,C) = PB(C)
n
Õ
i=1
PB(Ai | C),
PB(C) et PB(Ai | C) étant calculés à partir de la base de données utilisateur, servant d'ensemble test de votes de clients. De la définition de probabilité conditionnelle, on obtient:
PB(C | A1,...,An) = a PB(C)
n
Õ
i=1
PB(Ai | C),
a est une constante de normalisation. Ceci est en fait la définition de Bayes naif connue dans la littérature.
Le problème d'apprentissage d'un réseau bayesien peut alors être formulé comme suit: étant donné un ensemble test D={u1,...,un} d'instances de U, trouver un réseau B qui correspond le mieux à D. De nouveau, il nous faut une fonction de score pour évaluer nos réseaux.

2.2.3 Les limites de cette approche

Les points sensibles du filtrage collaboratif sont :

© Équipe Grappa, Février 2001.
Précédent Index Suivant