Un système de recommandation de filtrage collaboratif en Java

1. Introduction

Dans ce didacticiel, nous apprendrons tout sur l'algorithme Slope One en Java.

Nous montrerons également l'exemple d'implémentation du problème du filtrage collaboratif (CF) - une technique d'apprentissage automatique utilisée par les systèmes de recommandation .

Cela peut être utilisé, par exemple, pour prédire les intérêts des utilisateurs pour des éléments spécifiques.

2. Filtrage collaboratif

L'algorithme Slope One est un système de filtrage collaboratif basé sur les éléments. Cela signifie qu'il est entièrement basé sur le classement des éléments utilisateur. Lorsque nous calculons la similitude entre les objets, nous ne connaissons que l'historique des classements, pas le contenu lui-même. Cette similitude est ensuite utilisée pour prédire le classement des utilisateurs potentiels pour les paires utilisateur-élément non présentes dans l'ensemble de données.

L'image ci-dessous montre le processus complet d'obtention et de calcul de la note pour l'utilisateur spécifique:

Au début, les utilisateurs évaluent différents éléments du système. Ensuite, l'algorithme calcule les similitudes. Après cela, le système fait des prédictions pour les évaluations des éléments utilisateur, que l'utilisateur n'a pas encore notées.

Pour plus de détails sur le thème du filtrage collaboratif, nous pouvons nous référer à l'article Wikipédia.

3. L'algorithme Slope One

Slope One a été désigné comme la forme la plus simple de filtrage collaboratif non trivial basé sur des éléments et basé sur les évaluations. Il prend en compte à la fois les informations de tous les utilisateurs qui ont noté le même élément et des autres éléments notés par le même utilisateur pour calculer la matrice de similitude.

Dans notre exemple simple, nous allons prédire le classement des utilisateurs sur les articles du magasin.

Commençons par un modèle Java simple pour notre problème et notre domaine.

3.1. Modèle Java

Dans notre modèle, nous avons deux objets principaux - les éléments et les utilisateurs. La classe Item contient le nom de l'élément:

private String itemName;

D'autre part, la classe User contient le nom d'utilisateur:

private String username;

Enfin, nous avons une classe InputData qui sera utilisée pour initialiser les données. Supposons que nous créons cinq produits différents dans le magasin:

List items = Arrays.asList( new Item("Candy"), new Item("Drink"), new Item("Soda"), new Item("Popcorn"), new Item("Snacks") );

De plus, nous allons créer trois utilisateurs qui ont évalué au hasard certains des éléments mentionnés ci-dessus en utilisant l'échelle de 0,0 à 1,0, où 0 signifie aucun intérêt, 0,5 en quelque sorte intéressé et 1,0 signifie totalement intéressé. À la suite de l'initialisation des données, nous obtiendrons une carte avec les données de classement des éléments de l'utilisateur:

Map
    
      data;
    

3.2. Matrices de différences et de fréquences

Sur la base des données disponibles, nous calculerons les relations entre les éléments, ainsi que le nombre d'occurrences des éléments. Pour chaque utilisateur, nous vérifions sa note des articles:

for (HashMap user : data.values()) { for (Entry e : user.entrySet()) { // ... } }

Dans l'étape suivante, nous vérifions si l'élément existe dans nos matrices. S'il s'agit d'une première occurrence, nous créons la nouvelle entrée dans les cartes:

if (!diff.containsKey(e.getKey())) { diff.put(e.getKey(), new HashMap()); freq.put(e.getKey(), new HashMap()); } 

La première matrice est utilisée pour calculer les différences entre les notes des utilisateurs. Les valeurs de celui-ci peuvent être positives ou négatives (car la différence entre les notes peut être négative) et sont stockées comme Double . D'autre part, les fréquences sont stockées sous forme de valeurs entières .

Dans l'étape suivante, nous allons comparer les notes de tous les éléments:

for (Entry e2 : user.entrySet()) { int oldCount = 0; if (freq.get(e.getKey()).containsKey(e2.getKey())){ oldCount = freq.get(e.getKey()).get(e2.getKey()).intValue(); } double oldDiff = 0.0; if (diff.get(e.getKey()).containsKey(e2.getKey())){ oldDiff = diff.get(e.getKey()).get(e2.getKey()).doubleValue(); } double observedDiff = e.getValue() - e2.getValue(); freq.get(e.getKey()).put(e2.getKey(), oldCount + 1); diff.get(e.getKey()).put(e2.getKey(), oldDiff + observedDiff); }

Si quelqu'un a évalué l'élément auparavant, nous augmentons le nombre de fréquences de un. De plus, nous vérifions la différence moyenne entre les notes de l'élément et calculons le nouveau différentiel observé .

S'il vous plaît noter que nous mettons la somme des oldDiff et observedDiff comme une nouvelle valeur d'un élément.

Enfin, nous calculons les scores de similarité à l'intérieur des matrices:

for (Item j : diff.keySet()) { for (Item i : diff.get(j).keySet()) { double oldValue = diff.get(j).get(i).doubleValue(); int count = freq.get(j).get(i).intValue(); diff.get(j).put(i, oldValue / count); } }

La logique principale consiste à diviser la différence de notation de l'élément calculé par le nombre de ses occurrences. Après cette étape, nous pouvons imprimer notre matrice des différences finales.

3.3. Prédictions

En tant que partie principale du Slope One, nous allons prédire toutes les évaluations manquantes sur la base des données existantes. Pour ce faire, nous devons comparer les notes des éléments utilisateur avec la matrice des différences calculée à l'étape précédente:

for (Entry
    
      e : data.entrySet()) { for (Item j : e.getValue().keySet()) { for (Item k : diff.keySet()) { double predictedValue = diff.get(k).get(j).doubleValue() + e.getValue().get(j).doubleValue(); double finalValue = predictedValue * freq.get(k).get(j).intValue(); uPred.put(k, uPred.get(k) + finalValue); uFreq.put(k, uFreq.get(k) + freq.get(k).get(j).intValue()); } } // ... }
    

After that, we need to prepare the “clean” predictions using the code below:

HashMap clean = new HashMap(); for (Item j : uPred.keySet()) { if (uFreq.get(j) > 0) { clean.put(j, uPred.get(j).doubleValue() / uFreq.get(j).intValue()); } } for (Item j : InputData.items) { if (e.getValue().containsKey(j)) { clean.put(j, e.getValue().get(j)); } else if (!clean.containsKey(j)) { clean.put(j, -1.0); } }

The trick to consider with larger data set is to use only the item entries that have a large frequency value (for example > 1). Please note, that if the prediction is not possible, the value of it will be equal to -1.

Finally, very important note. If our algorithm worked correctly, we should receive the predictions for items that user didn't rate, but also the repeated ratings for the items that he rated. Those repeated rating's should not change, otherwise it means that there is a bug in your algorithm implementation.

3.4. Tips

There are few major factors that affect Slope One algorithm. Here are the few tips how to increase the accuracy and processing time:

  • envisagez d'obtenir les évaluations des éléments utilisateur côté base de données pour les grands ensembles de données
  • définir le délai pour la récupération des notes, car les intérêts des personnes peuvent changer avec le temps - cela réduira également le temps nécessaire pour traiter les données d'entrée
  • divisez les grands ensembles de données en plus petits - vous n'avez pas besoin de calculer des prévisions pour tous les utilisateurs chaque jour; vous pouvez vérifier si l'utilisateur a interagi avec l'élément prédit, puis l'ajouter / le supprimer de la file d'attente de traitement pour le jour suivant

4. Conclusion

Dans ce didacticiel, nous avons pu découvrir l'algorithme Slope One. De plus, nous avons introduit le problème de filtrage collaboratif pour les systèmes de recommandation d'articles.

L' implémentation complète de ce didacticiel se trouve dans le projet GitHub.