Catégories principales de métriques d’évaluation pour les systèmes de recommandation – 2ème partie

Métriques d’aide à la décision. Ces métriques sont, généralement, utilisées dans l’évaluation des systèmes de repérage d’informations. À l’opposé des fonctions d’erreurs, les métriques d’aide à la décision n’évaluent pas la qualité de la prédiction, mais la pertinence des documents. Ainsi, ces mesures prennent seulement en considération la pertinence du document [1-5]. Pour mieux illustrer les mesures qui vont suivre, on prend pour point de départ le tableau suivant de classes de documents.

Tableau 1 – Les classes de documents

Choisi Refusé Total
Pertinent Npc Npr Np
Non pertinent Nnc Nnr Nn
Total Nc Nr N

On définit à partir des classes de ce tableau les mesures suivantes :

  • Précision (« Precision ») : cette mesure représente la probabilité qu’un article choisi soit pertinent [6].

Métriques d’évaluation - Métriques d'aide à la décision - Precision

  • Rappel (« Recall ») : cette métrique calcule la probabilité qu’un article pertinent soit choisi [6-9].

Métriques d’évaluation - Métriques d'aide à la décision - Recall

  • F1 : cette mesure est une façon courante de combiner le rappel et la précision dans une seule métrique afin de faciliter la comparaison [6, 10, 11].

Métriques d’évaluation - Métriques d'aide à la décision - F1

  • Breese score : Breese et al. [12] proposent une extension à la métrique de Rappel appelée Breese score ou Rappel pondéré. L’idée principale sur laquelle repose cette métrique dérive du fait que l’utilité d’une recommandation se base essentiellement sur la probabilité que cette dernière soit consultée. Ainsi, cette mesure tient compte de l’ordre de présentation des recommandations en leur assignant différents poids. Pour ce faire, la métrique pénalise les n premières recommandations incorrectes, déterminées à partir d’une fonction appelée Breese-points, en leur assignant un poids fort et en diminuant de plus en plus ce dernier au fur et à mesure qu’on descend dans la liste de recommandations [3, 13].
  • La courbe ROCReceiver Operating Characteristic ») : une courbe ROC permet de comparer des algorithmes de recommandation indépendamment de la de la qualité des prédictions. ROC mesure le point auquel un système de filtrage de l’information peut distinguer avec succès les articles pertinents des articles non pertinents. De plus, cette mesure évalue l’ordre de présentation des recommandations (rang). Dans ce but, cette courbe met en relation dans un graphique, illustré par la figure 1, les taux de faux positifs (en abscisse) et les taux de vrais positifs (en ordonnée) [3, 14-18]. Une amélioration de la courbe ROC, notée CROC, a été proposée par Shein et al. [19].

Métriques d’évaluation - Métriques d'aide à la décision - Roc   Curve

Figure 1 – La courbe ROC [21]

  • NDPM Normalized Distance-based Performance Measure ») : rarement utilisée, cette mesure, comme pour la courbe ROC, évalue l’ordre de présentation des recommandations. Plus précisément, cette métrique mesure la « distance » entre le rang de l’article dicté par l’évaluation de l’utilisateur et le rang prédit par le l’algorithme de recommandation [20].

Références

[1]        C.-N. Ziegler, « Towards Decentralized Recommender Systems, » Albert-Ludwigs-Universitat Freiburg – Fakultat fur Angewandte Wissenschaften, Institut fur Informatik, 2005.

[2]        P. Haase, A. Hotho, L. S. Thieme, and Y. Sure, « Collaborative and Usage-Driven Evolution of Personal Ontologies., » ESWC, vol. 3532, pp. 486-499, 2005.

[3]        C.-N. Ziegler, S. M. McNee, J. A. Konstan, and G. Lausen, « Improving recommendation lists through topic diversification, » in Proceedings of the 14th international conference on World Wide Web Chiba, Japan: ACM, 2005.

[4]        J. L. Herlocker, « Understanding and improving automated collaborative filtering systems, » University of Minnesota, 2000, p. 144.

[5]        G. Adomavicius and A. Tuzhilin, « Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions, » Transactions on Knowledge and Data Engineering, vol. 17, pp. 734-749, 2005.

[6]        B. Sarwar, G. Karypis, J. Konstan, and T. J. Riedl, « Application of dimensionality reduction in recommender systems-a case study, » in ACM WebKDD 2000 Web Mining for E-Commerce Workshop Boston, MA, USA, 2000.

[7]        B. N. Miller, J. A. Konstan, and J. T. Riedl, « PocketLens: Toward a personal recommender system, » ACM Trans. Inf. Syst., vol. 22, pp. 437-476, 2004.

[8]        Z. Zaier, R. Godin, and L. Faucher, « Recommendation Quality Evolution Based on Neighborhood Size, » in Third International Conference on Automated Production of Cross Media Content for Multi-Channel Distribution. AXMEDIS ’07 Barcelona, Spain, 2007, pp. 33-36.

[9]        Z. Zaier, R. Godin, and L. Faucher, « Recommendation Quality Evolution Based on Neighbors Discrimination, » in MCETECH Conference on e-Technologies Montreal, 2008, pp. 148-153.

[10]      Z. Huang, H. Chen, and D. Zeng, « Applying associative retrieval techniques to alleviate the sparsity problem in collaborative filtering, » ACM Trans. Inf. Syst., vol. 22, pp. 116-142, 2004.

[11]      M. Montaner, « Collaborative Recommender Agents Based on Case-Based Reasoning and Trust. » vol. Ph.D. Girona, Spain: Universitat de Girona, Girona, 2003.

[12]      J. S. Breese, D. Heckerman, and C. Kadie, « Empirical Analysis of Predictive Algorithms for Collaborative Filtering, » Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI-98), pp. 43-52, 1998.

[13]      M. Stritt, K. Tso, and L. Schmidt-Thieme, « Attribute-Aware Anonymous Recommender Systems, » in 30th Annual Conference of the Gesellschaft für Klassifikation (GfKl), Springer, Ed. Berlin, Germany, 2006, pp. 497–506.

[14]      N. Good, B. J. Schafer, J. A. Konstan, A. Borchers, B. Sarwar, J. Herlocker, and J. Riedl, « Combining collaborative filtering with personal agents for better recommendations, » AAAI ’99/IAAI ’99: Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, pp. 439-446, 1999.

[15]      P. Melville, R. J. Mooney, and R. Nagarajan, « Content-boosted collaborative filtering for improved recommendations, » in Eighteenth national conference on Artificial intelligence Edmonton, Alberta, Canada: American Association for Artificial Intelligence, 2002.

[16]      A. Schein, A. Popescul, L. Ungar, and D. Pennock, « Methods and metrics for cold-start recommendations, » Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2002), pp. 253-260, 2002.

[17]      M. Van Setten, M. Veenstra, A. Nijholt, and B. Van Dijk, « Case-based reasoning as a prediction strategy for hybrid recommender systems, » Second International Atlantic Web Intelligence Conference (AWIC 2004), vol. 3034, pp. 13-22, May 2004.

[18]      E. Rojsattarat and N. Soonthornphisaj, « Hybrid Recommendation: Combining Content-Based Prediction and Collaborative Filtering., » INTELLIGENT DATA ENGINEERING AND AUTOMATED LEARNING: IDEAL, vol. 2690, pp. 337-344, 2003.

[19]      A. I. Schein, A. Popescul, L. H. Ungar, and D. M. Pennock, « CROC: A New Evaluation Criterion for Recommender Systems, » Electronic Commerce Research, vol. 5, pp. 51-74, 2005.

[20]      M. Balabanovi and Y. Shoham, « Fab: content-based, collaborative recommendation, » Commun. ACM, vol. 40, pp. 66-72, 1997.

[21]      L. J. Herlocker, A. J. Konstan, G. L. Terveen, and T. J. Riedl, « Evaluating collaborative filtering recommender systems, » ACM Trans. Inf. Syst., vol. 22, pp. 5-53, 2004.

Catégories principales de métriques d’évaluation pour les systèmes de recommandation – 1ère partie

La revue de la littérature, la plus exhaustive et la plus complète, sur les métriques d’évaluation pour les systèmes de recommandation est fournie par Herlocker et al. [1]. Cette étude montre que les métriques d’évaluation se divisent généralement en 3 catégories principales. En premier lieu, il y a les fonctions d’erreurs qui évaluent la prédiction faite par le système en la comparant à l’évaluation réelle. Ensuite, il existe les métriques d’aide à la décision qui jugent de l’efficacité du choix des documents pertinents. Enfin, d’autres métriques ont été proposées pour évaluer des critères qui ne sont pas liés aux prédictions [1-4].

Fonctions d’erreurs. Ces dernières sont les mesures les plus utilisées dans la littérature. Elles évaluent la qualité des prédictions générées par le système de recommandation [1]. Il existe plusieurs types de fonctions d’erreur qui consistent à mesurer la « distance » moyenne entre les prévisions et les observations correspondantes. Ainsi, une valeur proche de 0 indique des prédictions parfaites et une valeur avoisinante de 1 désigne de mauvaises prédictions [1, 2, 5-7]. Pour mieux illustrer les mesures qui vont suivre, on suppose que wi représente la valeur observée et ri représente la valeur prédite pour un ensemble de Bi prévisions. Ainsi, on peut calculer :

  • L’erreur absolue moyenne (MAE : « Mean Absolute Error ») : cette mesure est la fonction d’erreur la plus populaire. Elle évalue la qualité des prédictions fournies par le système de recommandation. À cet effet, le MAE mesure la déviation absolue moyenne entre une estimation prévue et l’estimation vraie de l’utilisateur [8-13].

Métriques d’évaluation - Fonctions d’erreurs - MAE

  • L’erreur moyenne quadratique (MSE : « Mean Squared Error ») : cette fonction d’erreur est appréciée pour sa grande sensibilité à l’erreur en comparaison au MAE. En effet, on peut voir que la distance, entre la prévision et l’observation, est élevée au carré  [6].

Métriques d’évaluation - Fonctions d’erreurs - MSE

  • La racine de l’erreur moyenne quadratique (RMSE : « Root Mean Squared Error ») : dans la littérature, le RMSE est largement utilisé, à la place du MSE, pour évaluer les systèmes de recommandation. Il est utilisé par le fameux concours Netflix Prize (http://www.netflixprize.com/) pour identifier les meilleurs algorithmes de filtrage [14-19].

Métriques d’évaluation - Fonctions d’erreurs - RMSE

  • L’erreur absolue moyenne normalisée (NMAE : « Normalized Mean Absolute Error») : cette mesure est définie comme le MAE divisé par la gamme des valeurs possibles des évaluations observées. Certains chercheurs préfèrent utiliser le NMAE plutôt que le MAE [20, 21]. Son utilisation se justifie quand on doit procéder à des expérimentations utilisant différents corpus d’évaluation. En effet, cette mesure fournit une valeur normalisée du MAE facilitant la comparaison pour des échelles de notation différentes [22].

Métriques d’évaluation - Fonctions d’erreurs - NMAE

  • L’erreur absolue utilisateur moyenne (MAUE : « Mean Absolute User Error ») : cette mesure, introduite par Massa et Avesani [23], calcule d’abord l’erreur absolue moyenne pour chaque utilisateur ; ensuite, elle calcule la moyenne de ces erreurs utilisateurs sur l’ensemble de tous les utilisateurs. Ainsi, chaque utilisateur aura le même poids dans le calcul de l’erreur absolue utilisateur moyenne [23, 24].

Références

[1]        L. J. Herlocker, A. J. Konstan, G. L. Terveen, and T. J. Riedl, « Evaluating collaborative filtering recommender systems, » ACM Trans. Inf. Syst., vol. 22, pp. 5-53, 2004.

[2]        C.-N. Ziegler, « Towards Decentralized Recommender Systems, » Albert-Ludwigs-Universitat Freiburg – Fakultat fur Angewandte Wissenschaften, Institut fur Informatik, 2005.

[3]        A. Zenebe and A. F. Norcio, « Evaluation Framework for Fuzzy Theoretic-Based Recommender System  » in HCI International 2005: The 11th International Conference on Human-Computer Interaction Las Vegas, Nevada, USA, 2005.

[4]        S. M. McNee, J. Riedl, and J. A. Konstan, « Being accurate is not enough: how accuracy metrics have hurt recommender systems, » CHI ’06: CHI ’06 extended abstracts on Human factors in computing systems, pp. 1097-1101, 2006.

[5]        J. L. Herlocker, « Understanding and improving automated collaborative filtering systems, » University of Minnesota, 2000, p. 144.

[6]        C.-N. Ziegler, S. M. McNee, J. A. Konstan, and G. Lausen, « Improving recommendation lists through topic diversification, » in Proceedings of the 14th international conference on World Wide Web Chiba, Japan: ACM, 2005.

[7]        G. Adomavicius and A. Tuzhilin, « Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions, » Transactions on Knowledge and Data Engineering, vol. 17, pp. 734-749, 2005.

[8]        B. Sarwar, G. Karypis, J. Konstan, and T. J. Riedl, « Analysis of recommendation algorithms for e-commerce, » in Proceedings of the 2nd ACM conference on Electronic commerce Minneapolis, Minnesota, United States: ACM, 2000.

[9]        J. Canny, « Collaborative Filtering with Privacy, » in Proceedings of the 2002 IEEE Symposium on Security and Privacy: IEEE Computer Society, 2002.

[10]      B. N. Miller, J. A. Konstan, and J. T. Riedl, « PocketLens: Toward a personal recommender system, » ACM Trans. Inf. Syst., vol. 22, pp. 437-476, 2004.

[11]      Z. Zaier, R. Godin, and L. Faucher, « Recommendation Quality Evolution Based on Neighborhood Size, » in Third International Conference on Automated Production of Cross Media Content for Multi-Channel Distribution. AXMEDIS ’07 Barcelona, Spain, 2007, pp. 33-36.

[12]      Z. Zaier, R. Godin, and L. Faucher, « Recommendation Quality Evolution Based on Neighbors Discrimination, » in MCETECH Conference on e-Technologies Montreal, 2008, pp. 148-153.

[13]      D. Lemire and A. Maclachlan, « Slope One Predictors for Online Rating-Based Collaborative Filtering, » in SIAM Data Mining (SDM’05) Newport Beach, California, USA, 2005, pp. 21-23.

[14]      R. Bell and Y. Koren, « Lessons from the Netflix prize challenge, » SIGKDD Explor. Newsl., vol. 9, pp. 75-79, 2007.

[15]      R. Bell and Y. Koren, « Improved Neighborhood-based Collaborative Filtering, » 2007.

[16]      R. Bell and Y. Koren, « Scalable Collaborative Filtering with Jointly Derived Neighborhood Interpolation Weights, » in Data Mining, 2007. ICDM 2007. Seventh IEEE International Conference on, 2007, pp. 43-52.

[17]      R. Bell, Y. Koren, and C. Volinsky, « Modeling relationships at multiple scales to improve accuracy of large recommender systems, » in Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining San Jose, California, USA: ACM, 2007.

[18]      R. Bell, Y. Koren, and C. Volinsky, « The BellKor solution to the Netflix Prize, » 2007.

[19]      R. Bell, Y. Koren, and C. Volinsky, « Chasing $1,000,000: How We Won The Netflix Progress Prize   » Statistical Computing and Statistical Graphics Newsletter, vol. 18, pp. 4-12, 2007.

[20]      J. Canny, « Collaborative filtering with privacy via factor analysis, » in Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval Tampere, Finland: ACM, 2002.

[21]      D. Lemire, « Scale and Translation Invariant Collaborative Filtering Systems, » Information Retrieval, vol. 8, pp. 129–150, 2005.

[22]      K. Goldberg, T. Roeder, D. Gupta, and C. Perkins, « Eigentaste: A Constant Time Collaborative Filtering Algorithm, » Information Retrieval, vol. 4, pp. 133-151, 2001.

[23]      P. Massa and P. Avesani, « Trust-Aware Collaborative Filtering for Recommender Systems, » On the Move to Meaningful Internet Systems 2004: CoopIS, DOA, and ODBASE: OTM Confederated International Conferences, CoopIS, DOA, and ODBASE, vol. 3290, 2004.

[24]      P. Massa and P. Avesani, « Trust-aware recommender systems, » in Proceedings of the 2007 ACM conference on Recommender systems Minneapolis, MN, USA: ACM, 2007.